FAST IMAGE SEGMENTATION USING REGION MERGING WITH A K-NEAREST NEIGHBOR GRAPH
The present invention has disclosed a process of image segmentation, which comprises applying edge detection to an image to obtain an edge image and preprocessing the image; oversegmentating the preprocessed image to obtain the plurality of initial partitions; constructing k-NN Graph for the oversegmented image based on the similarity between the initial partitions; and using k-NN Graph to merge the initial partitions. With the present invention, the merging process can be accelerated and the segmentation accuracy can be improved.
1 . A process of image segmentation, which comprises:
applying edge detection to an initial image to obtain an edge image, and preprocessing the initial image;
oversegmentating the preprocessed image to obtain the plurality of initial partitions;
constructing k-NN Graph for the oversegmented image based on the similarity between the initial partitions as well as the edge image; and
using k-NN Graph to merge the initial partitions.
2 . The process of claim 1 , wherein the preprocessing step comprises applying smooth filter to the image.
3 . The process of claim 1 , wherein the oversegmentation step can be realized by Watersheds-based Segmentation Algorithm.
4 . The process of claim 1 , wherein the oversegmentation step can be realized by a Region-based Algorithm.
5 . The process of claim 4 , wherein the Region-based Algorithm is Region Growing Algorithm.
6 . The process of claim 1 , wherein the similarity between the partitions is computed based on the sum of the similarity between pixels in the partitions, and is divided by a normalized item to make the similarity value between regions to be irrelevant to the size of the regions.
7 . The process of claim 6 , wherein similarity W between the partitions is computed as follows:
W
(
A
,
B
)
=
∑
i
∈
A
,
j
∈
B
ω
ij
(
∑
i
∈
A
d
i
)
(
∑
i
∈
B
d
i
)
wherein, W(A,B) is the similarity between partitions A and B; ω ij is the similarity between pixels p i and p j ; and d i =Σ j ω ij is the total connection from p i to all other pixels.
8 . The process of claim 6 , wherein the similarity between two pixels is computed based on the pixel's intensity, the maximum value on the line connecting the two pixels, and the spatial distance between the two pixels.
9 . The process of claim 6 , wherein the similarity between the pixels is computed as follows:
ω
ij
=
{
I
i
-
I
j
2
σ
1
2
Edge
2
(
i
,
j
)
σ
2
2
X
i
-
X
j
≤
r
0
X
i
-
X
j
>
r
wherein X i denotes the coordinate of p i ; I i denotes the intensity of p i ; Edge(i,j) is Edge feature, that is the maximum value on the line connecting p i and p j in the edge image; σ 1 and σ 2 are the parameters to modify the force of intensity and edge features in ω ij ; and r represents radius.
10 . The process of claim 9 , wherein features other than intensity, Edge feature and spatial distance can also be used for computing the similarity by defining an item in the form like Edge feature and making ω ij multiplied by the defined item.
11 . The process of claim 1 , wherein the similarity between the initial partitions is computed in the brute force manner.