Analysis and Design of Image Segmentation Algorithm Based on Super-pixel and Graph Cut

## Publications

/ Export Citation / / / Text size:

#### International Journal of Advanced Network, Monitoring and Controls

Xi'an Technological University

Subject: Computer Science , Software Engineering

eISSN: 2470-8038

13
33
Visit(s)
0
Comment(s)
0
Share(s)

SEARCH WITHIN CONTENT

FIND ARTICLE

Volume / Issue / page

Archive
Volume 5 (2020)
Volume 4 (2019)
Volume 3 (2018)
Volume 2 (2017)
Volume 1 (2016)
Related articles

VOLUME 3 , ISSUE 4 (Oct 2018) > List of articles

### Analysis and Design of Image Segmentation Algorithm Based on Super-pixel and Graph Cut

Citation Information : International Journal of Advanced Network, Monitoring and Controls. Volume 3, Issue 4, Pages 25-30, DOI: https://doi.org/10.21307/ijanmc-2019-017

Published Online: 14-October-2019

### ARTICLE

#### ABSTRACT

Image segmentation has always been a research hotspot in computer vision. Traditional image segmentation is based on pixels, and it is difficult to achieve the desired target effect. The manual segmentation method is too cumbersome and has limited precision. There is a certain degree of instability in the selection of interactively segmented pixels, which will affect the final segmentation results to a large extent.

In this paper, the superpixel block generated by the SLIC algorithm is used to preprocess the image, and then based on the Graph cut algorithm, the selection of seed points is improved, and the pixels of the background area are attempted to be optimized to obtain a more excellent target point sample. On top of the image segmentation, the foreground object is further divided with a frame, the pixels in the background are optimized, and the advantages of other segmentation algorithms are extracted to achieve the goal of global optimization, and interactive image segmentation is achieved.

## I. INTRODUCTION

Image segmentation is the division process of independent regions in an image with particular meaning which makes the same region represent the same features. The purpose is extracting the interesting parts called “the foreground”, and the rest parts are called “the background”. However, the characteristic differences between the foreground and the background may be reflected in various aspects such as grayscale, contour, texture, etc., so there is currently no general algorithm to solve the both problems. The result of image segmentation will directly affect the subsequent image processing results. At present, the application field of interactive image processing is very broad, and there are many researches on segmentation algorithms for stereoscopic images and color images.

The superpixel is a set of adjacent pixels which have similar features in space. The superpixel block can retain the effective information of image without affecting the boundary information of the images. In the conventional image processing, the pixel is regarded as a basic processing unit with high complexity. If replace the pixel point with superpixel block, the complexity in the process can be reduced. Therefore, in image segmentation, the image is preprocessed by using superpixels to improve the accuracy and speed of image segmentation.

## II. SLIC SUPERPIXEL SEGMENTATION

### A. SLIC algorithm

The basic idea of the SLIC (simple linear iterative clustering) algorithm is converting a color image into a 5-dimensional feature vectors in CIELAB color space, and setting a specific distance metric for the vectors, finally clustering the pixels in the image. The superpixel produced by the SLIC algorithm is not only fast, compact, but also nearly uniform and with good contour.

Specific implementation steps of the SLIC algorithm:

• 1) Initializing the seed points (or call the cluster center): to distribute the seed points evenly in the inner area of the image according to the number of superpixels we set. If the pixel of image is N and the number of divided superpixels is K, so the N/K is the size occupied by one superpixel, and the S=sqrt(N/K) is the distance between adjacent seed points.

• 2) Finding new seed points in the n*n proximity range: to calculate the gradient values of all the pixels in the range, and to set the seed points at the minimum.

• 3) Label distributing: to distribute the corresponding label for each pixel of each seed point in the adjacent area. It should be noted that the SLIC algorithm can only be searched within the range of 2S*2S.

• 4) Distance measuring: to calculate color distance and spatial distance of each searched pixel point and seed point separately. The calculation method of each distance is as shown in formulas (1), (2), and (3):

##### (1)
$dc=(li−lj)2+(ai−aj)2+(bi−bj)2$
##### (2)
$ds=(xi−xj)2+(yi+yj)2$
##### (3)
$D'=(dcNc)2+(dsNs)2$

Among them, dc represents the color, ds represents the space, Ns represents the maximum spatial distance within the class, and the formula Ns=S=sqrt(N/K) is applicable to every cluster. The maximum color distance is related to the image and is usually replaced by a fixed constant m. The calculation formula of the distance metric D' in the above formula can be changed to the following formula (4):

##### (4)
$D'=(dcm)2+(dss)2$

Since some pixels are not searched by only one but multiple seed points, it is necessary to calculate all their distances and to compare the minimum value as the cluster center of this pixel.

• 5) Optimizing: to optimize the code by iterative method, the specific iteration idea pseudo code is implemented as follows.

/*initialization*/

Sampling the pixel by the step size S, initializing the cluster center Ck = [lkakbkxkyk]T

Moving the smallest gradient seed point position in the S*S cluster center

Setting the label for each pixel i = -1

Setting the distance for each pixel d(i) = ∞

/*distribution*/

for every cluster center

for each pixel i is in a surrounding 2S*2S area calculating the distance D between C and i

if D<d(i)

setting d(i)=D

setting l(i)=k

/*Update*/

calculating a new cluster center

calculating the residual E

If E<= threshold

End the cycle

• 6) Enhancing connectivity: after iterative optimization, the algorithm may have some shortcomings. For example, multiple connectivity phenomena, the generated superpixels are too small, one superpixel is cut into many discontinuous superpixels, and the like. The main solution to the problems is increasing connectivity. The specific method is employing a new tag table, setting the elements as -1 and using the "Z" type to redistribute the generated undesirable superpixels. Then stop experiment after all the points traversal ends.

## B. SLIC segmentation result analysis

In the SLIC superpixel generation algorithm, the segmentation results of the image are different because of the number of superpixel generation and the setting of the compact coefficient. The compact coefficient is the ratio of tightness between the color feature and the XY coordinate feature. Generally, compact coefficient affects the shape of the superpixel.

The number of superpixels has a certain influence on the segmentation effect. In the case where the compact coefficient is 32, change the number of superpixels, and the number of superpixels generated is 128, 256, 512. Segmenting the images (a) and (b) in Fig. 1 respectively, and the experimental results are as follows:

##### Figure 1.

Image (a) segmentation result of different superpixels with the 32compact factor

It can be seen from Fig. 1 that, sometimes, the number of divided super-pixels is slightly smaller than the set value. It is mainly because that the too small segmentation regions are merging together in the processing. We can obtain from the experimental results that as the set value of superpixel number increase, the edge degree of generated superpixel block and the accuracy of segmentation result are high and vice versa.

According to the definition of compact coefficient, it will affect the shape of generated superpixel. Figure 2, the image (a) is divided with the size of the compact factor changing. The experimental results are as follows:

##### Figure 2.

Image (a) different compact coefficient segmentation results when the number of superpixels is 64

It can be seen from Fig. 2, in the case where the number of superpixels is set to be certain, as the compact coefficientIt can be seen from Fig. 2, in the case where the number of superpixels is set to be certain, as the compact coefficient increases, the generated superpixels become more and more regular; on the contrary, they become more and more irregular. However, the larger compact coefficient changes, the greater time complexity of the algorithm will be. After multiple experiments, it is found that when the compact coefficient is set at 40-60, the generated superpixel blocks are relatively regular, which is in line with the further experimental requirements of this paper.

## III. GRAPH CUT INTERACTIVE SEGMENTATION ALGORITHM

The basic idea of the Graph cut algorithm: users mark the foreground object and the background object, and assign the pixels with the highest probability to the pixels of unknown label according to the existing labels. The algorithm needs to combine the image segmentation problem with the image min cut problem, to parse and store the digital image by related properties of the matrix. Pixels in the grayscale image can be represented by a matrix, the row of the matrix represents the height of the image, the columns represents the width, the elements stored in the matrix are the pixels of image, and the values of matrix elements are the grayscale of pixels.

Step 1: Construct an undirected graph to represent an image which will be split, wherein V and E represent the sets of vertex and edge respectively. Using the Graph Cut algorithm to process the graphs, and the two endpoints are represented by "S" and "T", which called terminal vertices. The remaining endpoints are all connected with these two terminal vertices to form a part of edge collection. There are two different vertices, simultaneously there are also two edges in Graph Cut algorithm, as shown in Fig. 3.

##### Figure 3.

Network of terminal vertices and ordinary vertices

If there is a value whose sum of edge weights is the smallest, then this energy-minimization-based algorithm can be converted into the formula (5):

##### (5)
$E(f)=∑p∈PDp(lp)+∑(p,q)Vp,q(lp,lq)$

How to cut these edges to find the minimum cut? In order to solve this problem, we can regard the entire Graph cut image segmentation as a pixel mark problem. The target label set as 1, and the background label set as 0. The entire setup process can be obtained by the energy minimization function described above. Then the cut which can separate the target from the background is the requirements of this article. Using the found cut to classify the pixels in the image and to make different marks on the background and foreground, then the segmentation process of the entire image ends.

The process of energy minimization can be solved according to the maximum flow algorithm, as shown in Fig. 4:

##### Figure 4.

Maximum flow minimum cut diagram

## IV. ALGORITHM DESIGN AND IMPLEMENTATION

In this paper, the SLIC algorithm and the Graph cut algorithm are combined to segment the image. We use the average pixel of all pixels in the generated superpixel block to instead the original pixel, and the interactive factor is added. The user object selects the area where the target object is located, and the rest of the area is treated as the background point. The image is segmented by the Graph cut algorithm, and the segmentation result and the standard segmentation image are compared each other to analyze the segmentation effect. The algorithm flow is shown in Fig. 5:

##### Figure 5.

Algorithm flowchart

## V. ANALYSIS OF RESULTS

### A. Images comprehensive comparison

We selected a set of images for segmentation, and compared the results by three data: scorpion rate, accuracy, and recall rate. Among them, the scorpion rate is a more comprehensive indicator that can reflect the regression rate and accuracy rate. The segmentation results are shown in Table 1:

##### Table I.

MULTIPLE SETS OF IMAGE SEGMENTATION RESULTS

##### Figure 6.

Relationship between recall rate and accuracy

Among the above 10 pictures, the 6th image "soldier" has a high accuracy rate, but a low regression rate, only 75%, similarly as the 1st image "house" and the 4th image "athlete". These three images are relatively complicate in gray value of the main object, all of which have the pixels of high and low gray value simultaneously. For example, "soldier" has a lower gray value clothing, while the helmet has a higher one. When the helmet is divided into the background, the final segmentation result lost a part of foreground object, so the accuracy is high, but the recall rate is low. On the contrary, it is also the reason why the 2nd image "chicken" has a high recall rate.

### B. Study on the influence of the selection of parameter K

The parameter K value determines the proportional relationship between the boundary term and the region term. In this section, we study the difference between the image segmentation results under different K values. As shown in Fig. 7.

##### Figure 7.

Relationship between K value and recall rate

Figure 7 analyzes the change of recall rate under different K values, and we find that not all curves have a recall rate that increases with the rise of K value. This shows that when the image is segmented, only adjusting K value does not effectively increase the recall rate. Through the rate of change in the line chart, it is found that when K increases from 500 to 40500, the curve with the largest amplification in recall value changes by less than 7%. The change of K value is very limited to adjust the recall rate.

Figure 8 analyzes the relationship between K value and accuracy. We find that not all the accuracy of images increase with K value. Some images do not change much with increase of K, such as "cat"; some images will decrease as the K value increases, such as "car." It shows that the increase of K value is not as good as the selection of previous scenic spots and background points, or the selection of the frame selection. It can only distinguish the influence on segmentation result by eyes. Therefore, in actual operation, K value does not have to be set as a variable parameter, but can be specified as an appropriate value by users at the beginning.

It is concluded by complexed Fig. 7 and Fig. 8 that the selection of the K value can only change the edge of the image segmentation in terms of visual effects, and does not significantly affect the segmentation result numerically, and the difference in the influence of the K value on different images is also very big. The 11th sample "dog" image of Fig. 5 is significantly less accurate than the other images. Compared with other samples, we found that the foreground gray value of "dog" is larger than the background gray value, and the detection algorithm uses the small gray value points as the segmentation target to intersect with the marker image (GT image), which makes the image with light color as the main object has a high recall rate in the segmentation task but a obviously low accuracy. On the contrary, when the foreground and background of the image are quite different, the recall rate and accuracy will be high, so the image segmentation effect will be better.

##### Figure 8.

Relationship between K value and accuracy diagram

### C. Research on the Influence of the Selection of Super Pixels

Figure 9 analyzes the effect of the number of superpixels on the segmentation results. The algorithm process is: first, preprocess the superpixel block generated by the image; then use the superpixel block average value to instead the original pixel value; finally, the preprocessed image is operated by the Graph cut algorithm. If the number of super pixel blocks is different, the experimental results will be different. As shown in Fig. 9, we analyze the segmentation result by changing the number of superpixel blocks generated in a same photo.

As can be seen from Fig. 9, the effect of the number of superpixels on the segmentation result is different for different divided images. Within a certain range, as the number of superpixels increases, the accuracy of the segmentation result increases. While after exceeding this range, the accuracy of segmentation results will decrease when the number of superpixels increases. From the segmentation results of the above several images, we can infer that it is not the more the number of superpixels divided, the better the segmentation effect. When the number of superpixels increases to a certain range, the segmentation effect is almost no longer improved.

##### Figure 9.

Relationship between the number of super pixels and the accuracy rate

## VI. CONCLUSION

This paper implements an improved image segmentation software design based on the combination of superpixel and Graph cut algorithm. Test and analyze different scenarios and parameters, we have achieved a better robustness of the software, and making it adapt to most interactive segmentation tasks.

In the result detection, we find that the selection of the K value and the number of superpixels will determine the degree of detail retention at the edge of the image foreground. Since the changed points are the small proportion of the whole picture pixels, currently it is difficult to judge by the recall rate and the accuracy rate, and only the method of human eye recognition can be used to identify the advantages and disadvantages. Compared with the selection of the K value and the number of superpixels, the selection of the foreground or background points and the optimization of the frame clipping method can have a numerical influence on the segmentation result. The foreground gray value selection should be as large as possible from the background, which is beneficial to the image segmentation result. In the selection of the optimization frame, the foreground object should be framed as completely as possible, and the background should be placed as little as possible to achieve the effect of optimizing the segmentation.

The point and frame selection steps reflect the superiority of interactive segmentation, which can achieve the users' subjective willingness to split in the program. Even if there are multiple theme objects in some scenes, you can divide the different objects by framing them.

## ACKNOWLEDGMENT

This work was supported by National Natural Science Foundation of China (Grant No. 61572392, 61671362), Natural Science Foundation in Shaanxi Province of China (Grant No.2017JC2-08) and National Joint Engineering Laboratory Fund Project of New Network and Detection Control (Grant No. GSYSJ2016006).

## References

1. Greig D, Porteous B, Seheult A. Exact maximum a posteriori estimation for binary images[J].J.Royal Statistical Soc., Series B, 1989,51(2):271-2279
[PUBMED]
2. Boykov Y Y, Jolly M. Interactive graph cut for optimal boundary & region segmentation of objects in N-D images[C], Proceedings of Internation Conference on Computer Vision. Vancouver, Cannada: IEEE Computer Society, 2001, I: 105-112
3. Boykov Y, Kolmogorov V. An experimental comparison of min-cut/max flow algorithms for energy minimization in vision[J]. IEEE Transactions on Pattern Analysis and Machine Intelligen-ce, 2004, 26(9): 1124-1137
[CROSSREF]
4. ROTHER C. KOLMOGOROV V. BLAKE A. GrabCut: interactive foregroud extraction using iterated graph cuts [J]. ACM Transactions on Graphics (TOC), 2004,23(3),309-314.
[CROSSREF]
5. Qiang Nan. Image Segmentation Algorithm Based on Morphological Watershed and Spectral Clustering [D]. Chang'an University, 2014.
6. Zhang Jiashu, Li Beichuan. Research on Two-Dimensional Maximum Entropy Threshold Segmentation of Gray Image[J].Journal of Southwest China Normal University(Natural Science), 1995,(06):643-647.
7. Xi Jing. Remote Sensing Image Edge Detection and Its Application in Channel GIS [D]. Southeast University, 2006.
8. Wu Jian. Research and application of motion human detection and tracking in video sequences [D]. Lanzhou Institute of Technology, 2010.
9. Meng Jie, Cheng Yongqiang. Application of Image Location and Segmentation in Vehicle License Plate Recognition[J]. Information Communication, 2015,(09):159-160.
10. Tang Xiaojing. Color vector error diffusion algorithm based on edge detection[J]. Science and Technology Information, 2009, (35):482-483
11. Guo Zhenfeng. Interactive Image Segmentation Based on Graph Cuts [D]. Central South University, 2013.
12. Cao Jiannong, FANG Danxia. Image Segmentation Method Based on Graph Theory and Its Limitations[J]. Surveying and Mapping Techniques, 2006, (02)
13. Wang Chunyao, CHEN Junzhou, LI Wei. Review of research on superpixel segmentation algorithm[J]. Journal of Computer Applications, 2014, (01): 6-12.
14. Yin Li,JianSun,Chi-keung Tang and Heung-Yeung Shum. Lazy Snapping.ICCV 2004
15. Li Xuchao, Zhu Shanan. A Survey of Markov Random Field Methods in Image Segmentation[J]. Journal of Image and Graphics, 2007, (05): 789-798.
16. Xu Huanhuan. Research on image segmentation method based on energy function[D]. University of Science and Technology of China, 2009.
17. Xu Qiuping. Research on target extraction method based on graph cut theory [D]. Shaanxi Normal University, 2009.
18. Wang Yarong. Research on interactive image segmentation based on graph cut[D]. Northwest University, 2011.
19. Automatic Segmentation of Magnetic Resonance Brain Image Based on Watershed Algorithm[J]. SONG Liwei, SONG Chaoyu, ZHUANG Tiange. Journal of Shanghai Jiaotong University. 2003(11)
20. Song Yutan, JI Xiu. Research on Binary Image Segmentation Algorithm Based on Mathematical Morphology[J]. Journal of Changchun Institute of Technology (Natural Science Edition), 2008, (3): 68-70.
21. Xu Huanhuan. Research on image segmentation method based on energy function[D]. University of Science and Technology of China, 2009.
22. Shi Dianguo. Gray Image Segmentation Based on Graph Theory[D]. Wuhan University of Technology, 2009.
23. LI Minguang,DENG Kazhong,ZHAO Yin. Remote Sensing Image Segmentation Based on Improved Watershed Transform[J]. Remote Sensing Information, 2009,(06):3-6.
24. Liu Chen. Application of Filtering Preprocessing in Watershed Segmentation Algorithm[J]. Journal of Kashgar Teachers, 2014, (06): 45-49
25. Zhang Xiaolong. Small class division of forest resources survey based on high spatial resolution remote sensing image[D]. Xi'an University of Science and Technology, 2010.
26. Liu Huan, Zhang Mei, Peng Xingxing. Research on color image segmentation based on edge detection and region growing[J]. China New Communication, 2016, (11):153-154.
27. Wang Kang. Improvement of k-means clustering algorithm and its application [D]. Dalian University of Technology, 2014.

### FIGURES & TABLES

Figure 1.

Image (a) segmentation result of different superpixels with the 32compact factor

Figure 2.

Image (a) different compact coefficient segmentation results when the number of superpixels is 64

Figure 3.

Network of terminal vertices and ordinary vertices

Figure 4.

Maximum flow minimum cut diagram

Figure 5.

Algorithm flowchart

Figure 6.

Relationship between recall rate and accuracy

Figure 7.

Relationship between K value and recall rate

Figure 8.

Relationship between K value and accuracy diagram

Figure 9.

Relationship between the number of super pixels and the accuracy rate

### REFERENCES

1. Greig D, Porteous B, Seheult A. Exact maximum a posteriori estimation for binary images[J].J.Royal Statistical Soc., Series B, 1989,51(2):271-2279
[PUBMED]
2. Boykov Y Y, Jolly M. Interactive graph cut for optimal boundary & region segmentation of objects in N-D images[C], Proceedings of Internation Conference on Computer Vision. Vancouver, Cannada: IEEE Computer Society, 2001, I: 105-112
3. Boykov Y, Kolmogorov V. An experimental comparison of min-cut/max flow algorithms for energy minimization in vision[J]. IEEE Transactions on Pattern Analysis and Machine Intelligen-ce, 2004, 26(9): 1124-1137
[CROSSREF]
4. ROTHER C. KOLMOGOROV V. BLAKE A. GrabCut: interactive foregroud extraction using iterated graph cuts [J]. ACM Transactions on Graphics (TOC), 2004,23(3),309-314.
[CROSSREF]
5. Qiang Nan. Image Segmentation Algorithm Based on Morphological Watershed and Spectral Clustering [D]. Chang'an University, 2014.
6. Zhang Jiashu, Li Beichuan. Research on Two-Dimensional Maximum Entropy Threshold Segmentation of Gray Image[J].Journal of Southwest China Normal University(Natural Science), 1995,(06):643-647.
7. Xi Jing. Remote Sensing Image Edge Detection and Its Application in Channel GIS [D]. Southeast University, 2006.
8. Wu Jian. Research and application of motion human detection and tracking in video sequences [D]. Lanzhou Institute of Technology, 2010.
9. Meng Jie, Cheng Yongqiang. Application of Image Location and Segmentation in Vehicle License Plate Recognition[J]. Information Communication, 2015,(09):159-160.
10. Tang Xiaojing. Color vector error diffusion algorithm based on edge detection[J]. Science and Technology Information, 2009, (35):482-483
11. Guo Zhenfeng. Interactive Image Segmentation Based on Graph Cuts [D]. Central South University, 2013.
12. Cao Jiannong, FANG Danxia. Image Segmentation Method Based on Graph Theory and Its Limitations[J]. Surveying and Mapping Techniques, 2006, (02)
13. Wang Chunyao, CHEN Junzhou, LI Wei. Review of research on superpixel segmentation algorithm[J]. Journal of Computer Applications, 2014, (01): 6-12.
14. Yin Li,JianSun,Chi-keung Tang and Heung-Yeung Shum. Lazy Snapping.ICCV 2004
15. Li Xuchao, Zhu Shanan. A Survey of Markov Random Field Methods in Image Segmentation[J]. Journal of Image and Graphics, 2007, (05): 789-798.
16. Xu Huanhuan. Research on image segmentation method based on energy function[D]. University of Science and Technology of China, 2009.
17. Xu Qiuping. Research on target extraction method based on graph cut theory [D]. Shaanxi Normal University, 2009.
18. Wang Yarong. Research on interactive image segmentation based on graph cut[D]. Northwest University, 2011.
19. Automatic Segmentation of Magnetic Resonance Brain Image Based on Watershed Algorithm[J]. SONG Liwei, SONG Chaoyu, ZHUANG Tiange. Journal of Shanghai Jiaotong University. 2003(11)
20. Song Yutan, JI Xiu. Research on Binary Image Segmentation Algorithm Based on Mathematical Morphology[J]. Journal of Changchun Institute of Technology (Natural Science Edition), 2008, (3): 68-70.
21. Xu Huanhuan. Research on image segmentation method based on energy function[D]. University of Science and Technology of China, 2009.
22. Shi Dianguo. Gray Image Segmentation Based on Graph Theory[D]. Wuhan University of Technology, 2009.
23. LI Minguang,DENG Kazhong,ZHAO Yin. Remote Sensing Image Segmentation Based on Improved Watershed Transform[J]. Remote Sensing Information, 2009,(06):3-6.
24. Liu Chen. Application of Filtering Preprocessing in Watershed Segmentation Algorithm[J]. Journal of Kashgar Teachers, 2014, (06): 45-49
25. Zhang Xiaolong. Small class division of forest resources survey based on high spatial resolution remote sensing image[D]. Xi'an University of Science and Technology, 2010.
26. Liu Huan, Zhang Mei, Peng Xingxing. Research on color image segmentation based on edge detection and region growing[J]. China New Communication, 2016, (11):153-154.
27. Wang Kang. Improvement of k-means clustering algorithm and its application [D]. Dalian University of Technology, 2014.