# Research on Multifeature Segmentation Method of Remote Sensing Images Based on Graph Theory

Authors: Wenxing Bao; Xiuhong Yao
Journal: Journal of Sensors
 (2016)

---

## Abstract

According to the characteristics of high-resolution remote sensing (RS) images, a new multifeature segmentation method of high-resolution remote sensing images combining the spectrum, shape, and texture features based on graph theory is presented in the paper. Firstly, the quadtree segmentation method is used to partition the original image. Secondly, the spectrum, shape, and texture weight components are calculated all based on the constructed graph. The matching degree between pixels and the texture is computed similarity. Finally, the ratio cut standards combination of the spectrum, shape, and texture weight components is used for the final segmentation. The experimental results show that this method can obtain more ideal results and higher segmentation accuracy applied to RS image than those traditional methods.


---

## Body

## 1. Introduction

In the past decade, many scholars have done the research about graph-based approaches to image segmentation. Graph theory has got a lot of attention because of its representational power and flexibility properties. Bai et al. [1] apply graph cut (GC) theory to the classification of hyperspectral remote sensing images. Fuzzy SVM classifier and the GC-based classification were used in two-step classification strategy in this paper. Felzenszwalb and Huttenlocher [2] define a predicate for measuring the evidence for a boundary between two regions using a graph-based representation. The time complexity of the method runs in O
(
m
l
o
g
m
) time for m graph edges. The work of Wang and Siskind [3] presents cut ratio as a new cost function of graph methods for segmenting image. This method is useful for some image segmentation applications. Cui and Zhang [4] use Minimum Span Tree optimal theory to realize object based on high-resolution image segmentation. The result proved that this method can obtain high quality segmentation. Kato et al. [5, 6] propose a Markov random field (MRF) image segmentation model based on the integration of colour and texture descriptors. This method can use both synthetic and natural color images. Another early approach to image segmentation based on graph cut has been proposed [7–15].The objectives of this paper are to obtain better image segmentation results and relative high segmentation accuracy for high-resolution RS images. For RS image, the algorithm’s time complexity and space complexity rate will be high if only graph theory for image segmentation is used. Quarter-tree segmentation method is a fast image segmentation algorithm, but it cannot divide meaningful target area for RS images. If the threshold is set too low, oversegmentation phenomenon will be very serious. If the threshold is set too high, it cannot form a more accurate target edge [1, 13]. Therefore, this paper designs a new method by combining the merits of quarter-tree segmentation and ratio cut (
R
-
c
u
t
) algorithm, and the method can be used in high-resolution RS images. This method is effective to reduce the size of the graph vertices, improving the accuracy of image segmentation. It first establishes the mapping relation of RS image and graph and then sets an energy function of the graph according to the remarkable weights. We can solve the energy function to get the minimum which will lead to the result of graph segmentation. At last we mapped the graph segmentation result back to image. Because the construction of graph and the extraction of remarkable weights can be based on both pixel and image blocks, the methods based on graph theory will be good in image segmentation.The organization of this paper is as follows. In the second section, quadtree segmentation method andR-cut theory for multifeature segmentation of RS image are described. Results and discussion are given in Section 3. The final section is the conclusions.


## 2. TheR-Cut Theory for Multifeature Segmentation of RS Image

### 2.1. Quadtree Segmentation Method

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to zone a two-dimensional space by recursively subdividing it into four quadrants or regions [16]. Quadtree decomposition is currently a valuable method in image processing and computer graphics. The procedure of quadtree segmentation is as follows.Step 1.
The original image (typically2
N
×
2
N) is divided into four same size regions.Step 2.
It is to detect the constant gray level of each region segmentation image.Step 3.
If it cannot meet the request of constant gray level of the image, then each district will be divided into four areas of the same size and go to Step2.Step 4.
If it meets the request, then stop the iterative process.


### 2.2.R-Cut Standards

The graph partition problem is defined on data represented in the form of a graphG
=
(
V
,
E
), with V vertices and E edges. Where in form, G corresponds to the image, the vertices correspond to regions, and the edges correspond to adjacent relations between the regions. Ratio cut represents the ratio of the corresponding sums of two different weights of edges along the cut boundary. A minimum ratio cut refers to the smallest cut ratio [3].The energy function ofR-cut standards is as follows:(1)
R
-
c
u
t
A
,
B
≜
c
1
A
,
B
c
2
A
,
B
,where A and B represent two different image blocks, respectively, and c
1
(
A
,
B
) and c
2
(
A
,
B
) calculated the energy of cut sets by using two methods of weight calculation, respectively:(2)
c
1
A
,
B
≜
∑
u
∈
A
,
v
∈
B
,
u
,
v
∈
E
w
1
u
,
v
,
c
2
A
,
B
≜
∑
u
∈
A
,
v
∈
B
,
u
,
v
∈
E
w
2
u
,
v
,where u denotes the vertex of A, v denotes the vertex of B, w
1
(
u
,
v
) and w
2
(
u
,
v
) denote the weights associated with each edge (
u
,
v
), respectively, w
1
(
u
,
v
) is the first edge weight, and w
2
(
u
,
v
) is the second edge weight.


### 2.3.R-Cut Reduction Algorithm

TheR-cut reduction algorithm steps are as follows.Step 1 (calculate minimum ratio cut).
In order to simplify the calculation, we calculate the minimum ratio ring instead of the minimum ratio. The dual graphG
′
=
(
V
′
,
E
′
) of the graph G is constructed and shown in Figure 1. There is a one-to-one correspondence between the minimum ratio cut of graph G and the minimum ratio ring of the dual graph G
′, therefore, the problem that calculate the minimum ratio cut set {
e
1
,
e
2
,
…
,
e
l
} of the original G can be transformed into the minimum ratio  ring  of  the dual graph G
′.Figure 1
Dual graph.Step 2 (calculate the minimum ratio ring).
In order to simplify the calculation, the negative simple ring is computed instead of the minimum ratio ring. TheG
′
(
b
) representations of the dual graph G
′ with the linear conversion w
11
′, where w
11
′ is obtained by doing the conversion: w
11
′
=
w
1
′
-
b
w
2
′ and functions w
1
′ and w
2
′ are the edge weights function of graph G
′. The conversion of weights function will not change the minimum ratio ring loop of the dual graph G
′, so it will not change the minimum ratio cut of the original G. Only the minimum loop cost of G
′
(
b
∗
) is nil consideration, and the graph G
′ has a minimum ratio of the loop which contains the loop ratio b
∗. The graph G
′ has a minimum ratio of the loop which contains the loop ratio b
∗, if and only if the minimum loop cost of G
′
(
b
∗
) is equal to zero. The relationship between b
∗ and b is as follows.
IfG
′
(
b
) has a negative cost loop, then b
∗
<
b. While if G
′
(
b
) does not have negative cost loop, then b
∗
≥
b. Let r
m
i
n and r
m
a
x, respectively, be the minimum and maximum loop ratio of d, so b
m
i
n
=
r
m
i
n and b
m
a
x
=
r
m
a
x. Then, b
m
i
n
≤
b
∗
≤
b
m
a
x. Let b
=
b
m
i
n
+
b
m
a
x
/
2; if G
′
(
b
) has a negative cost loop,  then b
m
a
x value is set to b; otherwise the b
m
i
n value is set to b, continuing the repeated calculation, until we cannot find a negative cost of simple loop concerning the one corresponding to b; and now b  is the minimum loop ratio b
∗ and at the same time the negative cost simple loop of G
′
(
b
) is the negative cost simple loop which we want to find.Step 3 (calculate the minimum cost perfect matching).
In order to reduce the calculation, the negative simple ring is computed instead of the minimum cost perfect matching. Construct a new graphG
′
′
=
(
V
′
′
,
E
′
′
) from the graph G
′ which is obtained by the previous step. Graph G
′contains a negative cost loop, if and only if G
′
′ has the minimum cost perfect matching. From graph G
′ to graph G
′
′, the specific conversion principles are as follows.(i)
For each vertexu
1
′ of graph G
′, graph G
′
′ contains two vertices u
1
′
′
,
u
2
′
′ and an edge (
u
1
′
′
,
u
2
′
′
) of which weight value is equal to zero.
(ii)
For each edge(
u
′
,
v
′
) of graph G
′, graph G
′
′contains two corresponding vertices u
v
′
′ and v
u
′
′ and five corresponding edges. Figure 2 shows the weight value of the five edges.Figure 2
Transform toG
′
′.According toG
′
′ which is obtained through the above three steps, we can calculate the c
1
(
A
,
B
) and c
2
(
A
,
B
) and obtain the minimum ratio cut according to formula (1).


### 2.4. Weight Calculation

In this paper, a multifeature segmentation method which takes into account the spectrum, shape, and texture features of RS image is applied.The weight component based on the spectrum is defined asW
i
j
s
p
e
c
t
r
u
m, the weight component based on the shape is defined as W
i
j
s
h
a
p
e, the weight component based on the texture is defined as W
i
j
t
e
x
t
u
r
e, and W
i
j is the combination of the above three aspects of information [8]:(3)
W
i
j
=
W
i
j
s
p
e
c
t
r
u
m
×
W
i
j
s
h
a
p
e
×
W
i
j
t
e
x
t
u
r
e
.The weight component based on the spectrum W
i
j
s
p
e
c
t
r
u
m is(4)
W
i
j
s
p
e
c
t
r
u
m
=
e
x
p
-
χ
2
C
i
,
C
j
σ
c
o
l
o
r
.In formula (4), σ
c
o
l
o
r denotes the standard deviation of the pixel color. χ
2 can be described as follows:(5)
χ
2
C
i
,
C
j
=
1
2
∑
k
=
1
k
C
i
k
-
C
j
k
2
C
i
k
+
C
j
k
,where k is the number of filter’s types. If i and j correspond to two pixels, χ
2 is used to record the spectral similarity between the pixels i and j. If i andj are corresponding to the two blocks, χ
2 is used to record the spectral similarity between the blocks i and j.The weight component based on the shapeW
i
j
s
h
a
p
e is(6)
W
i
j
s
h
a
p
e
=
1
-
m
a
x
x
∈
M
i
j
p
c
o
n
x
,where m
a
x
x
∈
M
i
j
p
c
o
n
(
x
) is used to mark the matching degree between the two pixels or blocks i and j, which is obtained by calculating the maximum value of all the probability coefficient along the line C of the set of pixels M
i
j after connecting i and j in a straight line. If this line exactly intersects with a profile, then m
a
x
x
∈
M
i
j
p
c
o
n
(
x
) is large, the weight is small, and i and j may belong to two classes; on the contrary, if the line is parallel to the profile, then m
a
x
x
∈
M
i
j
p
c
o
n
(
x
) is small, the weight is greater, and i and j may belong to the same class.The weight component based on the textureW
i
j
t
e
x
t
u
r
e is(7)
W
i
j
t
e
x
t
u
r
e
=
e
x
p
-
χ
2
h
i
,
h
j
σ
t
e
x
t
u
r
e
,where h
i and h
j are the histogram obtained by doing texture operator transform for i and j, respectively, and σ
t
e
x
t
u
r
e denotes the standard deviation of the texture of object. χ
2 is used to record the texture similarity between i and j. If the difference between h
i and h
j is too large, the values of χ
2 will be large, and W
i
j
t
e
x
t
u
r
e is very small. So i and j do not belong to the same class [1–4, 8].The algorithm flowchart is shown in Figure3.Figure 3
The algorithm flowchart.


## 2.1. Quadtree Segmentation Method

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to zone a two-dimensional space by recursively subdividing it into four quadrants or regions [16]. Quadtree decomposition is currently a valuable method in image processing and computer graphics. The procedure of quadtree segmentation is as follows.Step 1.
The original image (typically2
N
×
2
N) is divided into four same size regions.Step 2.
It is to detect the constant gray level of each region segmentation image.Step 3.
If it cannot meet the request of constant gray level of the image, then each district will be divided into four areas of the same size and go to Step2.Step 4.
If it meets the request, then stop the iterative process.


## 2.2.R-Cut Standards

The graph partition problem is defined on data represented in the form of a graphG
=
(
V
,
E
), with V vertices and E edges. Where in form, G corresponds to the image, the vertices correspond to regions, and the edges correspond to adjacent relations between the regions. Ratio cut represents the ratio of the corresponding sums of two different weights of edges along the cut boundary. A minimum ratio cut refers to the smallest cut ratio [3].The energy function ofR-cut standards is as follows:(1)
R
-
c
u
t
A
,
B
≜
c
1
A
,
B
c
2
A
,
B
,where A and B represent two different image blocks, respectively, and c
1
(
A
,
B
) and c
2
(
A
,
B
) calculated the energy of cut sets by using two methods of weight calculation, respectively:(2)
c
1
A
,
B
≜
∑
u
∈
A
,
v
∈
B
,
u
,
v
∈
E
w
1
u
,
v
,
c
2
A
,
B
≜
∑
u
∈
A
,
v
∈
B
,
u
,
v
∈
E
w
2
u
,
v
,where u denotes the vertex of A, v denotes the vertex of B, w
1
(
u
,
v
) and w
2
(
u
,
v
) denote the weights associated with each edge (
u
,
v
), respectively, w
1
(
u
,
v
) is the first edge weight, and w
2
(
u
,
v
) is the second edge weight.


## 2.3.R-Cut Reduction Algorithm

TheR-cut reduction algorithm steps are as follows.Step 1 (calculate minimum ratio cut).
In order to simplify the calculation, we calculate the minimum ratio ring instead of the minimum ratio. The dual graphG
′
=
(
V
′
,
E
′
) of the graph G is constructed and shown in Figure 1. There is a one-to-one correspondence between the minimum ratio cut of graph G and the minimum ratio ring of the dual graph G
′, therefore, the problem that calculate the minimum ratio cut set {
e
1
,
e
2
,
…
,
e
l
} of the original G can be transformed into the minimum ratio  ring  of  the dual graph G
′.Figure 1
Dual graph.Step 2 (calculate the minimum ratio ring).
In order to simplify the calculation, the negative simple ring is computed instead of the minimum ratio ring. TheG
′
(
b
) representations of the dual graph G
′ with the linear conversion w
11
′, where w
11
′ is obtained by doing the conversion: w
11
′
=
w
1
′
-
b
w
2
′ and functions w
1
′ and w
2
′ are the edge weights function of graph G
′. The conversion of weights function will not change the minimum ratio ring loop of the dual graph G
′, so it will not change the minimum ratio cut of the original G. Only the minimum loop cost of G
′
(
b
∗
) is nil consideration, and the graph G
′ has a minimum ratio of the loop which contains the loop ratio b
∗. The graph G
′ has a minimum ratio of the loop which contains the loop ratio b
∗, if and only if the minimum loop cost of G
′
(
b
∗
) is equal to zero. The relationship between b
∗ and b is as follows.
IfG
′
(
b
) has a negative cost loop, then b
∗
<
b. While if G
′
(
b
) does not have negative cost loop, then b
∗
≥
b. Let r
m
i
n and r
m
a
x, respectively, be the minimum and maximum loop ratio of d, so b
m
i
n
=
r
m
i
n and b
m
a
x
=
r
m
a
x. Then, b
m
i
n
≤
b
∗
≤
b
m
a
x. Let b
=
b
m
i
n
+
b
m
a
x
/
2; if G
′
(
b
) has a negative cost loop,  then b
m
a
x value is set to b; otherwise the b
m
i
n value is set to b, continuing the repeated calculation, until we cannot find a negative cost of simple loop concerning the one corresponding to b; and now b  is the minimum loop ratio b
∗ and at the same time the negative cost simple loop of G
′
(
b
) is the negative cost simple loop which we want to find.Step 3 (calculate the minimum cost perfect matching).
In order to reduce the calculation, the negative simple ring is computed instead of the minimum cost perfect matching. Construct a new graphG
′
′
=
(
V
′
′
,
E
′
′
) from the graph G
′ which is obtained by the previous step. Graph G
′contains a negative cost loop, if and only if G
′
′ has the minimum cost perfect matching. From graph G
′ to graph G
′
′, the specific conversion principles are as follows.(i)
For each vertexu
1
′ of graph G
′, graph G
′
′ contains two vertices u
1
′
′
,
u
2
′
′ and an edge (
u
1
′
′
,
u
2
′
′
) of which weight value is equal to zero.
(ii)
For each edge(
u
′
,
v
′
) of graph G
′, graph G
′
′contains two corresponding vertices u
v
′
′ and v
u
′
′ and five corresponding edges. Figure 2 shows the weight value of the five edges.Figure 2
Transform toG
′
′.According toG
′
′ which is obtained through the above three steps, we can calculate the c
1
(
A
,
B
) and c
2
(
A
,
B
) and obtain the minimum ratio cut according to formula (1).


## 2.4. Weight Calculation

In this paper, a multifeature segmentation method which takes into account the spectrum, shape, and texture features of RS image is applied.The weight component based on the spectrum is defined asW
i
j
s
p
e
c
t
r
u
m, the weight component based on the shape is defined as W
i
j
s
h
a
p
e, the weight component based on the texture is defined as W
i
j
t
e
x
t
u
r
e, and W
i
j is the combination of the above three aspects of information [8]:(3)
W
i
j
=
W
i
j
s
p
e
c
t
r
u
m
×
W
i
j
s
h
a
p
e
×
W
i
j
t
e
x
t
u
r
e
.The weight component based on the spectrum W
i
j
s
p
e
c
t
r
u
m is(4)
W
i
j
s
p
e
c
t
r
u
m
=
e
x
p
-
χ
2
C
i
,
C
j
σ
c
o
l
o
r
.In formula (4), σ
c
o
l
o
r denotes the standard deviation of the pixel color. χ
2 can be described as follows:(5)
χ
2
C
i
,
C
j
=
1
2
∑
k
=
1
k
C
i
k
-
C
j
k
2
C
i
k
+
C
j
k
,where k is the number of filter’s types. If i and j correspond to two pixels, χ
2 is used to record the spectral similarity between the pixels i and j. If i andj are corresponding to the two blocks, χ
2 is used to record the spectral similarity between the blocks i and j.The weight component based on the shapeW
i
j
s
h
a
p
e is(6)
W
i
j
s
h
a
p
e
=
1
-
m
a
x
x
∈
M
i
j
p
c
o
n
x
,where m
a
x
x
∈
M
i
j
p
c
o
n
(
x
) is used to mark the matching degree between the two pixels or blocks i and j, which is obtained by calculating the maximum value of all the probability coefficient along the line C of the set of pixels M
i
j after connecting i and j in a straight line. If this line exactly intersects with a profile, then m
a
x
x
∈
M
i
j
p
c
o
n
(
x
) is large, the weight is small, and i and j may belong to two classes; on the contrary, if the line is parallel to the profile, then m
a
x
x
∈
M
i
j
p
c
o
n
(
x
) is small, the weight is greater, and i and j may belong to the same class.The weight component based on the textureW
i
j
t
e
x
t
u
r
e is(7)
W
i
j
t
e
x
t
u
r
e
=
e
x
p
-
χ
2
h
i
,
h
j
σ
t
e
x
t
u
r
e
,where h
i and h
j are the histogram obtained by doing texture operator transform for i and j, respectively, and σ
t
e
x
t
u
r
e denotes the standard deviation of the texture of object. χ
2 is used to record the texture similarity between i and j. If the difference between h
i and h
j is too large, the values of χ
2 will be large, and W
i
j
t
e
x
t
u
r
e is very small. So i and j do not belong to the same class [1–4, 8].The algorithm flowchart is shown in Figure3.Figure 3
The algorithm flowchart.


## 3. Experimental Results and Analysis

### 3.1. Evaluation Method of Segmentation Results

Evaluation method of image segmentation is divided into qualitative and quantitative analysis.This paper makes a quantitative analysis on the segmentation results by using the theory proposed in [14, 17–20]. The specific evaluation index is defined as follows.


#### 3.1.1. Homogeneity

From [14], we handle the standard deviation of all the pixels as a measure of the object homogeneity criterion. The standard deviation of the object can be written as(8)
σ
=
1
n
-
1
∑
i
=
1
n
C
i
-
C
-
2
,where n is the number of all pixels within the object, C
i represents the pixel gray value of pixel i, and C
- represents the gray mean of the object.


#### 3.1.2. Heterogeneity

For each object, we calculate the average difference absolute value of the object with the neighborhood to reflect the degree of difference between the object and the adjacent object [14]. The formula of heterogeneity can be written as(9)
Δ
C
=
1
l
∑
i
=
1
n
l
i
C
-
-
C
-
u
,where l is the boundary length of the current object, l
i is the common edge length of the current object with i adjacent objects, C
- is the gray mean of the current object, C
-
u is the gray mean of i adjacent objects, and n is the number of adjacent objects with the current object.


#### 3.1.3. Segmentation Evaluation Index (SEI)

SEI is inversely proportional with its homogeneity and proportional with its heterogeneity [14]. The SEI of the object is defined as follows: (10)
S
E
L
=
Δ
C
l
σ
.


#### 3.1.4. Probabilistic Rand Index (PRI)

The Probabilistic Rand Index (PRI) counts the similarity of pairs of pixels whose labels are consistent between the computed segmentation and the ground truth. The expression of PRI can be defined as(11)
P
R
S
t
e
s
t
,
G
k
=
1
N
2
∑
i
,
j
,
i
≺
j
c
i
j
p
i
j
+
1
-
c
i
j
1
-
p
i
j
.This measure takes values in [
0,1
]
-
0 when two images have no similarities, and c
=
1 when two images are identical, where S
t
e
s
t is the segmentation that is to be compared with the reference segmentation image and {
G
k
} is ground-truth segmentations, where c
i
j denotes the event of a pair of pixels i and j having the same label and p
i
j its probability [17–19].


#### 3.1.5. The Variation of Information (VoI)

The Variation of Information (VoI) metric defines the distance between two segmentations as the average conditional entropy of one segmentation given the other one and thus roughly measures the amount of randomness in one segmentation which can be explained by the other [20]. The formula of VoI can be written as(12)
d
V
I
C
,
C
′
=
H
C
+
H
C
′
-
2
I
C
,
C
′
,where H and I, respectively, represent the entropies and the mutual information between two clustering of data C and data C
′. This measure takes values in [
0,1
].


#### 3.1.6. The Global Consistency Error (GCE)

The Global Consistency Error (GCE) measures the extent to which one segmentation can be viewed as a refinement of the other. GCE can be defined as(13)
G
C
E
S
1
,
S
2
=
1
n
m
i
n
∑
i
E
S
1
,
S
2
,
p
i
,
∑
i
E
S
2
,
S
1
,
p
i
.
S
1 and S
2 are input segmentations images. E
(
S
1
,
S
2
,
p
i
) and E
(
S
1
,
S
2
,
p
i
) are the local refinement error, respectively. E
(
S
1
,
S
2
,
p
i
) is zero precisely when S
1 is a refinement of S
2 as pixel p
i, but not vice versa. [21].


### 3.2. The Experiment Results

In this section, we apply the proposed algorithms to real high-resolution data by the ALOS high-resolution RS images of Shi Zuishan Industrial Park, Ningxia, China. Its ground spatial resolution is 2.5 m and the size is512
×
512 pixels. According to the human visual, field surveys and spectral measurement results, we select five samples, lime pile, cinder heap, house, road, and wasteland. To validate the algorithm, the images were segmented from the spectral, shape, texture, and multifeature segmentation based on graph theory, respectively, and then made a comparison among the four segmentation results. Original image and various algorithms segmentation results are shown in Figures 4 and 5, respectively. From Figure 4, the spectral segmentation based on graph theory has certain limitation; it is prone to split too small for textured areas, but it is less likely to split for the areas of relatively close texture. The shape segmentation based on graph theory is prone to split too small. Although the method of the texture segmentation based on graph theory can get a better segmentation of all types of surface features, it is not obvious to the boundary between the surface features. The multifeature segmentation method of remote sensing images based on graph theory not only can make the measurement, the spectra, and texture information of different objects better, reflect the differences between the different types of surface features, and achieve better segmentation, but also can accurately obtain the boundary between different types of objects; in short, it can ensure the accuracy of subsequent analysis.Figure 4
Results of various segmentation algorithms based on graph theory (RS image 1). (a) Original image 1. (b) Spectral segmentation. (c) Shape segmentation. (d) Texture segmentation. (e) Multifeature segmentation of proposed algorithms.
(a)
(b)
(c)
(d)
(e)Figure 5
Results of various segmentation algorithms based on graph theory (RS image 2). (a) Original image 2. (b) Spectral segmentation. (c) Shape segmentation. (d) Texture segmentation. (e) Multifeature segmentation.
(a)
(b)
(c)
(d)
(e)To be more accurate and objective evaluation of segmentation results of the algorithm, this paper uses the above-mentioned evaluation method for quantitative evaluation of the segmentation results. The lime heap and cinder heap are selected as evaluation object because the paper mainly monitors industry solid waste. Specific segmentation scale evaluation results of origin RS image 1 are shown in Table1.Table 1
Evaluation of segmentation scale (RS image 1).
Segmentation algorithm
Homogeneity (σ)
Heterogeneity (Δ
C)
Segmentation evaluation index (SEI)
Lime heap
Cinder heap
Lime heap
Cinder heap
Lime heap
Cinder heap
Spectral
5.1580
0.1000
97.8235
22.8538
18.9654
228.5380
Shape
5.5125
0.9150
17.5005
3.6434
3.1747
3.9819
Texture
1.0646
4.0370
112.4847
50.4797
105.6591
12.5043
Multifeature
2.1045
0.9877
124.1282
52.5459
58.9822
53.2003From Table1, we can see that the lime heap homogeneity index is 2.1045 with the multifeature segmentation method of remote sensing images based on graph theory, which is smaller than the lime heap homogeneity index of spectral-based and shape-based segmentation, and the cinder heap homogeneity index is 0.9877, which is smaller than the cinder heap homogeneity index of texture-based segmentation and is close to the cinder heap homogeneity index of shape-based segmentation; this comparison and contrast herein prove that, by using the multifeature segmentation method based on graph theory, one can get a better measurement of the spectrum and texture information of surface features. The heterogeneity index of the multifeature segmentation based on graph theory is greater than the other three segmentation methods, and it further shows that the multifeature segmentation method based on graph theory can obtain more precise boundaries between different types of surface features. In summary, the results of the multifeature segmentation method based on graph theory make good internal object homogeneity, and at the same time there is an obvious contrast between adjacent objects.The results obtained with the other segmentation methods and the proposed algorithm over two high-resolution RS images are shown in Table2. The parameters of PRI, GCA, and VoI of each segmentation methods are computed. Quadtree, watershed, mean shift, multiresolution, and the proposed method are the region-based segmentation methods. The quadtree method starts at the root of the tree that represents the whole image. If it is found nonuniform (not homogeneous), then it splits into four son squares (the splitting process). If, in contrast, four son squares are homogeneous, they are merged as several connected components (the merging process). This process continues recursively until no further splits or merges are possible. The multiresolution approach partitions the image at different scale, using a pyramid or quadtree structure. The watershed approach considers the gradient magnitude of an image as a topographic surface. Pixels having the highest gradient magnitude intensities correspond to watershed lines, which indicate the region boundaries. Mean shift method is defined as finding modes in a set of data samples, showing an underlying probability density function. Canny operator and sobel operator are boundary-based segmentation method.Table 2
Segmentation evaluation results over region-based algorithm and boundary-based algorithm.
Segmentation methods
Origin image 1
Origin image 2
PRI
GCE
VoI
PRI
GCE
VoI
Quadtree
0.8821
0.8737
12.1816
0.9564
0.9564
13.5365
Watershed
0.8797
0.8778
11.8219
0.9542
0.9568
13.2924
Mean shift
0.8818
0.8703
12.0964
0.9377
0.9607
12.9237
Multiresolution
0.8781
0.8741
11.9189
0.9543
0.9568
13.4735
Canny
0.2851
0.2201
5.4241
0.2030
0.1434
6.8397
Sobel
0.1543
0.0563
5.0602
0.0899
0.0427
6.6001
This paper
0.8815
0.8758
12.2234
0.9572
0.9573
13.7379From Table2, taking into account the quality of the results from the evaluation parameters, it will be noticed that the best results are reached by the proposed method. The value of PRI of this method is the highest compared with the other segmentation methods. This is mainly due to the fact that this method combines the spectrum, shape, and texture of image and the segmentation region is close to real region. From the results of Table 2, we can see that the results of region-based segmentation methods are better than the boundary-based segmentation methods.


## 3.1. Evaluation Method of Segmentation Results

Evaluation method of image segmentation is divided into qualitative and quantitative analysis.This paper makes a quantitative analysis on the segmentation results by using the theory proposed in [14, 17–20]. The specific evaluation index is defined as follows.


### 3.1.1. Homogeneity

From [14], we handle the standard deviation of all the pixels as a measure of the object homogeneity criterion. The standard deviation of the object can be written as(8)
σ
=
1
n
-
1
∑
i
=
1
n
C
i
-
C
-
2
,where n is the number of all pixels within the object, C
i represents the pixel gray value of pixel i, and C
- represents the gray mean of the object.


### 3.1.2. Heterogeneity

For each object, we calculate the average difference absolute value of the object with the neighborhood to reflect the degree of difference between the object and the adjacent object [14]. The formula of heterogeneity can be written as(9)
Δ
C
=
1
l
∑
i
=
1
n
l
i
C
-
-
C
-
u
,where l is the boundary length of the current object, l
i is the common edge length of the current object with i adjacent objects, C
- is the gray mean of the current object, C
-
u is the gray mean of i adjacent objects, and n is the number of adjacent objects with the current object.


### 3.1.3. Segmentation Evaluation Index (SEI)

SEI is inversely proportional with its homogeneity and proportional with its heterogeneity [14]. The SEI of the object is defined as follows: (10)
S
E
L
=
Δ
C
l
σ
.


### 3.1.4. Probabilistic Rand Index (PRI)

The Probabilistic Rand Index (PRI) counts the similarity of pairs of pixels whose labels are consistent between the computed segmentation and the ground truth. The expression of PRI can be defined as(11)
P
R
S
t
e
s
t
,
G
k
=
1
N
2
∑
i
,
j
,
i
≺
j
c
i
j
p
i
j
+
1
-
c
i
j
1
-
p
i
j
.This measure takes values in [
0,1
]
-
0 when two images have no similarities, and c
=
1 when two images are identical, where S
t
e
s
t is the segmentation that is to be compared with the reference segmentation image and {
G
k
} is ground-truth segmentations, where c
i
j denotes the event of a pair of pixels i and j having the same label and p
i
j its probability [17–19].


### 3.1.5. The Variation of Information (VoI)

The Variation of Information (VoI) metric defines the distance between two segmentations as the average conditional entropy of one segmentation given the other one and thus roughly measures the amount of randomness in one segmentation which can be explained by the other [20]. The formula of VoI can be written as(12)
d
V
I
C
,
C
′
=
H
C
+
H
C
′
-
2
I
C
,
C
′
,where H and I, respectively, represent the entropies and the mutual information between two clustering of data C and data C
′. This measure takes values in [
0,1
].


### 3.1.6. The Global Consistency Error (GCE)

The Global Consistency Error (GCE) measures the extent to which one segmentation can be viewed as a refinement of the other. GCE can be defined as(13)
G
C
E
S
1
,
S
2
=
1
n
m
i
n
∑
i
E
S
1
,
S
2
,
p
i
,
∑
i
E
S
2
,
S
1
,
p
i
.
S
1 and S
2 are input segmentations images. E
(
S
1
,
S
2
,
p
i
) and E
(
S
1
,
S
2
,
p
i
) are the local refinement error, respectively. E
(
S
1
,
S
2
,
p
i
) is zero precisely when S
1 is a refinement of S
2 as pixel p
i, but not vice versa. [21].


## 3.1.1. Homogeneity

From [14], we handle the standard deviation of all the pixels as a measure of the object homogeneity criterion. The standard deviation of the object can be written as(8)
σ
=
1
n
-
1
∑
i
=
1
n
C
i
-
C
-
2
,where n is the number of all pixels within the object, C
i represents the pixel gray value of pixel i, and C
- represents the gray mean of the object.


## 3.1.2. Heterogeneity

For each object, we calculate the average difference absolute value of the object with the neighborhood to reflect the degree of difference between the object and the adjacent object [14]. The formula of heterogeneity can be written as(9)
Δ
C
=
1
l
∑
i
=
1
n
l
i
C
-
-
C
-
u
,where l is the boundary length of the current object, l
i is the common edge length of the current object with i adjacent objects, C
- is the gray mean of the current object, C
-
u is the gray mean of i adjacent objects, and n is the number of adjacent objects with the current object.


## 3.1.3. Segmentation Evaluation Index (SEI)

SEI is inversely proportional with its homogeneity and proportional with its heterogeneity [14]. The SEI of the object is defined as follows: (10)
S
E
L
=
Δ
C
l
σ
.


## 3.1.4. Probabilistic Rand Index (PRI)

The Probabilistic Rand Index (PRI) counts the similarity of pairs of pixels whose labels are consistent between the computed segmentation and the ground truth. The expression of PRI can be defined as(11)
P
R
S
t
e
s
t
,
G
k
=
1
N
2
∑
i
,
j
,
i
≺
j
c
i
j
p
i
j
+
1
-
c
i
j
1
-
p
i
j
.This measure takes values in [
0,1
]
-
0 when two images have no similarities, and c
=
1 when two images are identical, where S
t
e
s
t is the segmentation that is to be compared with the reference segmentation image and {
G
k
} is ground-truth segmentations, where c
i
j denotes the event of a pair of pixels i and j having the same label and p
i
j its probability [17–19].


## 3.1.5. The Variation of Information (VoI)

The Variation of Information (VoI) metric defines the distance between two segmentations as the average conditional entropy of one segmentation given the other one and thus roughly measures the amount of randomness in one segmentation which can be explained by the other [20]. The formula of VoI can be written as(12)
d
V
I
C
,
C
′
=
H
C
+
H
C
′
-
2
I
C
,
C
′
,where H and I, respectively, represent the entropies and the mutual information between two clustering of data C and data C
′. This measure takes values in [
0,1
].


## 3.1.6. The Global Consistency Error (GCE)

The Global Consistency Error (GCE) measures the extent to which one segmentation can be viewed as a refinement of the other. GCE can be defined as(13)
G
C
E
S
1
,
S
2
=
1
n
m
i
n
∑
i
E
S
1
,
S
2
,
p
i
,
∑
i
E
S
2
,
S
1
,
p
i
.
S
1 and S
2 are input segmentations images. E
(
S
1
,
S
2
,
p
i
) and E
(
S
1
,
S
2
,
p
i
) are the local refinement error, respectively. E
(
S
1
,
S
2
,
p
i
) is zero precisely when S
1 is a refinement of S
2 as pixel p
i, but not vice versa. [21].


## 3.2. The Experiment Results

In this section, we apply the proposed algorithms to real high-resolution data by the ALOS high-resolution RS images of Shi Zuishan Industrial Park, Ningxia, China. Its ground spatial resolution is 2.5 m and the size is512
×
512 pixels. According to the human visual, field surveys and spectral measurement results, we select five samples, lime pile, cinder heap, house, road, and wasteland. To validate the algorithm, the images were segmented from the spectral, shape, texture, and multifeature segmentation based on graph theory, respectively, and then made a comparison among the four segmentation results. Original image and various algorithms segmentation results are shown in Figures 4 and 5, respectively. From Figure 4, the spectral segmentation based on graph theory has certain limitation; it is prone to split too small for textured areas, but it is less likely to split for the areas of relatively close texture. The shape segmentation based on graph theory is prone to split too small. Although the method of the texture segmentation based on graph theory can get a better segmentation of all types of surface features, it is not obvious to the boundary between the surface features. The multifeature segmentation method of remote sensing images based on graph theory not only can make the measurement, the spectra, and texture information of different objects better, reflect the differences between the different types of surface features, and achieve better segmentation, but also can accurately obtain the boundary between different types of objects; in short, it can ensure the accuracy of subsequent analysis.Figure 4
Results of various segmentation algorithms based on graph theory (RS image 1). (a) Original image 1. (b) Spectral segmentation. (c) Shape segmentation. (d) Texture segmentation. (e) Multifeature segmentation of proposed algorithms.
(a)
(b)
(c)
(d)
(e)Figure 5
Results of various segmentation algorithms based on graph theory (RS image 2). (a) Original image 2. (b) Spectral segmentation. (c) Shape segmentation. (d) Texture segmentation. (e) Multifeature segmentation.
(a)
(b)
(c)
(d)
(e)To be more accurate and objective evaluation of segmentation results of the algorithm, this paper uses the above-mentioned evaluation method for quantitative evaluation of the segmentation results. The lime heap and cinder heap are selected as evaluation object because the paper mainly monitors industry solid waste. Specific segmentation scale evaluation results of origin RS image 1 are shown in Table1.Table 1
Evaluation of segmentation scale (RS image 1).
Segmentation algorithm
Homogeneity (σ)
Heterogeneity (Δ
C)
Segmentation evaluation index (SEI)
Lime heap
Cinder heap
Lime heap
Cinder heap
Lime heap
Cinder heap
Spectral
5.1580
0.1000
97.8235
22.8538
18.9654
228.5380
Shape
5.5125
0.9150
17.5005
3.6434
3.1747
3.9819
Texture
1.0646
4.0370
112.4847
50.4797
105.6591
12.5043
Multifeature
2.1045
0.9877
124.1282
52.5459
58.9822
53.2003From Table1, we can see that the lime heap homogeneity index is 2.1045 with the multifeature segmentation method of remote sensing images based on graph theory, which is smaller than the lime heap homogeneity index of spectral-based and shape-based segmentation, and the cinder heap homogeneity index is 0.9877, which is smaller than the cinder heap homogeneity index of texture-based segmentation and is close to the cinder heap homogeneity index of shape-based segmentation; this comparison and contrast herein prove that, by using the multifeature segmentation method based on graph theory, one can get a better measurement of the spectrum and texture information of surface features. The heterogeneity index of the multifeature segmentation based on graph theory is greater than the other three segmentation methods, and it further shows that the multifeature segmentation method based on graph theory can obtain more precise boundaries between different types of surface features. In summary, the results of the multifeature segmentation method based on graph theory make good internal object homogeneity, and at the same time there is an obvious contrast between adjacent objects.The results obtained with the other segmentation methods and the proposed algorithm over two high-resolution RS images are shown in Table2. The parameters of PRI, GCA, and VoI of each segmentation methods are computed. Quadtree, watershed, mean shift, multiresolution, and the proposed method are the region-based segmentation methods. The quadtree method starts at the root of the tree that represents the whole image. If it is found nonuniform (not homogeneous), then it splits into four son squares (the splitting process). If, in contrast, four son squares are homogeneous, they are merged as several connected components (the merging process). This process continues recursively until no further splits or merges are possible. The multiresolution approach partitions the image at different scale, using a pyramid or quadtree structure. The watershed approach considers the gradient magnitude of an image as a topographic surface. Pixels having the highest gradient magnitude intensities correspond to watershed lines, which indicate the region boundaries. Mean shift method is defined as finding modes in a set of data samples, showing an underlying probability density function. Canny operator and sobel operator are boundary-based segmentation method.Table 2
Segmentation evaluation results over region-based algorithm and boundary-based algorithm.
Segmentation methods
Origin image 1
Origin image 2
PRI
GCE
VoI
PRI
GCE
VoI
Quadtree
0.8821
0.8737
12.1816
0.9564
0.9564
13.5365
Watershed
0.8797
0.8778
11.8219
0.9542
0.9568
13.2924
Mean shift
0.8818
0.8703
12.0964
0.9377
0.9607
12.9237
Multiresolution
0.8781
0.8741
11.9189
0.9543
0.9568
13.4735
Canny
0.2851
0.2201
5.4241
0.2030
0.1434
6.8397
Sobel
0.1543
0.0563
5.0602
0.0899
0.0427
6.6001
This paper
0.8815
0.8758
12.2234
0.9572
0.9573
13.7379From Table2, taking into account the quality of the results from the evaluation parameters, it will be noticed that the best results are reached by the proposed method. The value of PRI of this method is the highest compared with the other segmentation methods. This is mainly due to the fact that this method combines the spectrum, shape, and texture of image and the segmentation region is close to real region. From the results of Table 2, we can see that the results of region-based segmentation methods are better than the boundary-based segmentation methods.


## 4. Summary

In this paper, we took into account a number of feature information of the image and usedR-cut theory for RS images segmentation. Experimental comparison shows that multifeature segmentation method based on graph theory achieved better segmentation results than the methods based on single feature. Overall, the method can be used in high-resolution RS images. Even though the method also has shortcomings, such as the effectiveness and the implementing speed of algorithms which are not very satisfactory, in the future, we will keep on seeking an efficient solving process and the weight calculation formula to apply to RS image segmentation.



---

*Source: 8750927-2015-11-15.xml*