Journal of Jilin University(Engineering and Technology Edition) ›› 2018, Vol. 48 ›› Issue (6): 1931-1937.doi: 10.13229/j.cnki.jdxbgxb20171009

Previous Articles     Next Articles

Image segmentation algorithm based on SLIC and fast nearest neighbor region merging

LIU Zhong-min1(),WANG Yang1,LI Zhan-ming1,HU Wen-jin2   

  1. 1. College of Electrical and Information Engineering,Lanzhou University of Technology,Lanzhou 730050,China
    2. College of Mathematics and Computer Science,Northwest Minzu University,Lanzhou 730030,China
  • Received:2017-09-27 Online:2018-11-20 Published:2018-12-11

RICH HTML

 23   

PDF (PC)

225

Abstract:

It is difficult to search the global optimal solution when traditional region adjacency graph is used to describe the data structure. To solve this problem, an image segmentation algorithm based on SLIC and fast nearest neighbor region merging is proposed. This method introduces the nearest neighbor graph to optimize the global search based on the region adjacency graph. First, an image is divided into small regions by SLIC superpixel algorithm, in which the relation between regions is described by the adjacency table structure of the Region Adjacency Graph (RAG) and the Nearest Neighbor Graph (NNG). Then, the value of the dissimilarity function is calculated between each region to be merged with all of its adjacent regions. Finally, the region with the least similarity is merged. The experimental results show that the proposed algorithm can combine the most similar regions, and reduce the complexity of the merging calculation compared with the traditional region merging algorithm, which greatly improves the accuracy of the regional merging.

Key words: information processing technology, image segmentation, simple linear iterative clustering(SLIC), region adjacency graph(RAG), nearest neighbor graph(NNG), region merging

CLC Number: 

  • TP391.4

Fig.1

Segmentation results with different k values"

Fig.2

Segmentation results with different m values"

Fig.3

Schematic diagrams of RAG and NNG"

Fig.4

RAG schematics and conversion to NNG schematics"

Fig.5

Segmentation results"

Table 1

Segmentation evaluation index"

算法 第1幅图像 第2幅图像 第3幅图像
Precision Recall F-score Precision Recall F-score Precision Recall F-score
NCUT 0.4752 0.5621 0.5150 0.4092 0.6561 0.5040 0.5628 0.5426 0.5525
SCOW 0.6193 0.7036 0.6587 0.7969 0.8126 0.8046 0.6927 0.7683 0.7285
SLIC 0.6279 0.7964 0.7021 0.8024 0.7873 0.7947 0.7638 0.7026 0.7319
SLIC+DBSCAN 0.4235 0.6718 0.5195 0.6499 0.7263 0.6859 0.7289 0.6732 0.6999
MeanShift+MSRM 0.2843 0.3726 0.3225 0.8529 0.8021 0.8267 0.7046 0.7624 0.7323
本文算法 0.6754 0.9186 0.7784 0.8354 0.7980 0.8162 0.6830 0.7862 0.7309

Table 2

The algorithm complexity analysis"

算法 时间复杂度
NCUT O(N2)
SCOW O(N)
SLIC O(N)
SLIC+DBSCAN O(N+N2)
MeanShift+MSRM O(TN2)
本文算法 O(N+log2(‖E‖))
[1] 章毓晋 . 图像分割中基于过渡区技术的统计调查[J]. 计算机辅助设计与图形学报, 2015,27(3):379-381.
Zhang Yu-jin . A survey on transition region-based techniques for image segmentation[J]. Journal of Computer-Aided Design & Computer Graphics, 2015,27(3):379-381.
[2] 舒速, 杨明 . 基于分水岭分割和稀疏表示的高光谱图像分类方法[J]. 计算机科学, 2016,43(2):89-94.
doi: 10.11896/j.issn.1002-137X.2016.2.020
Shu Su, Yang Ming . Hyperspectral image classification method based on watershed segmentation and sparse representation[J]. Computer Science, 2016,43(2):89-94.
doi: 10.11896/j.issn.1002-137X.2016.2.020
[3] Ren X, Malik J. Learning a classification model for segmentation [C]//9th IEEE International Conference on Computer Vision, Washington DC, 2003: 10-17.
[4] Wang W J, Nevatia R. Robust object tracking using constellation model with superpixel [C]//Proc of the 11th Asian Conference on computer Vision, Berlin, 2012: 191-204.
[5] Mori G, Ren X. Recovering human body configurations combining segmentation and recognition [C]//Proc of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Washington DC, 2004: 326-333.
[6] Mori G. Guiding model search using segmentation [C]//Proc of the 10th IEEE International Conference on Computer Vision, Washing DC, 2005: 1417-1423.
[7] Achanta R, Shaji A, Smith K , et al. SLIC superpixels compared to state-of art superpixel methods[J]. IEEE Trans on Pattern Analysis and Intelligence, 2012,34(11):2274-2282.
doi: 10.1109/TPAMI.2012.120 pmid: 22641706
[8] 张亚亚, 刘小伟, 刘福太 , 等. 基于改进SLIC方法的彩色图像分割[J]. 计算机工程, 2015,41(4):205-209.
doi: 10. 3969/ j. issn. 1000-3428. 2015. 04. 039
Zhang Ya-ya, Liu Xiao-wei, Liu Fu-tai , et al. Color image segmentation based on improved SLIC method[J]. Computer Engineering, 2015,41(4):205-209.
doi: 10. 3969/ j. issn. 1000-3428. 2015. 04. 039
[9] 胡志立, 郭敏 . 基于SLIC的改进GrabCut彩色图像快速分割[J]. 计算机工程与应用, 2016,52(2):186-190.
doi: 10.3778/j.issn.1002-8331.1401-0088
Hu Zhi-li, Guo Min . Fast segmentation in color image based on SLIC and GrabCut[J]. Computer Engineering and Applications, 2016,52(2):186-190.
doi: 10.3778/j.issn.1002-8331.1401-0088
[10] 凌朝东, 陈虎, 杨骁 , 等. 结合SLIC超像素和DBSCAN聚类的眼底图像硬性渗出检测方法[J]. 华侨大学学报:自然版, 2015,36(4):399-405.
doi: 10.11830/ISSN.1000-5013.2015.04.0399
Ling Chao-dong, Chen Hu, Yang Xiao , et al. Fundus image hard exudates detection based on SLIC and superpixels and DBSCAN clustering[J]. Journal of Huaqiao University(Natural Science), 2015,36(4):399-405.
doi: 10.11830/ISSN.1000-5013.2015.04.0399
[11] Hu Zhong-wen, Zou Qiu. Watershed superpixel [C]//Proc of Internation Conference on Image Processing, Québec City, 2015.
[12] 李健宏, 付淇 . 一种基于图的分水岭区域合并算法[J]. 南昌大学学报:理科版, 2009,33(2):200-204.
doi: 10.3969/j.issn.1006-0464.2009.02.024
Li Jiang-hong, Fu Qi . A graph-based area merge algorithm which can be applied to watershed segmentation method[J]. Journal of Nanchang University(Natural Science), 2009,33(2):200-204.
doi: 10.3969/j.issn.1006-0464.2009.02.024
[13] Haris K, Efstratiadis S N, Maglaveras N , et al. Hybrid image segmentation using watersheds and fast region merging[J]. IEEE Transactions on Image Processing, 1998,7(12):1684-1699.
doi: 10.1109/83.730380 pmid: 18276235
[14] 孙丰, 秦开怀, 孙伟 , 等. 基于区域合并的图像显著性检测[J]. 计算机辅助设计与图形学学报, 2016,28(10):1679-1687.
Sun Feng, Qin Kai-huai, Sun Wei , et al. Image saliency detection based on region merging[J]. Journal of Computer-Aided Design & Computer Graphics, 2016,28(10):1679-1687.
[15] Yang J, He Y, Caspersen J . Region merging using local spectral angle thresholds: a more accurate method for hybrid segmentation of remote sensing images[J]. Remote Sensing of Environment, 2017,190:137-148.
doi: 10.1016/j.rse.2016.12.011
[16] Achanta R, Shaji A, Smith K . SLIC superpixels[DB/OL].[2017-09-19]..
[17] Achanta R, Shaji A, Smith K , et al. SLIC superpixels compared to state-of art superpixel methods[J]. IEEE Trans on Pattern Analysis and Machin Intelligence, 2012,34(11):2274-2282.
doi: 10.1109/TPAMI.2012.120 pmid: 22641706
[18] Shi J, Maiik J . Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002,22(8):888-905.
[19] Ning J, Zhang L, Zhang D , et al. Interactive image segmentation by maximal similarity based region merging[J]. Pattern Recognition, 2010,43(2):445-456.
doi: 10.1016/j.patcog.2009.03.004
[20] Crevier D . Image segmentation algorithm development using ground truth image data sets[J]. Computer Vision & Image Understanding, 2008,112(2):143-159.
doi: 10.1016/j.cviu.2008.02.002
[21] 毛亮, 薛月菊, 孔德运 , 等. 基于稀疏场水平集的荔枝图像分割算法[J]. 农业工程学报, 2011,27(4):345-349.
doi: 10.3969/j.issn.1002-6819.2011.04.060
Mao Liang, Xue Yue-ju, Kong De-yun , et al. Litchi image segmentation algorithm based on sparse field level set[J]. Transactions of the Chinese Society of Agricultural Engineering, 2011,27(4):345-349.
doi: 10.3969/j.issn.1002-6819.2011.04.060
[1] Tohtonur,Hai⁃long ZHANG,Jie WANG,Na WANG,Xin⁃chen YE,Wan⁃qiong WANG. High speed median filtering algorithm based on graphics processing unit [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 979-985.
[2] Lu⁃tao LIU,Na LI. Source detection based on coprime array [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 986-993.
[3] Yin⁃juan FU,Yong LI,Li⁃qin XU,Kun⁃hui ZHANG. Design and analysis of NLFM⁃Costas RF stealth radar signal [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 994-999.
[4] YING Huan,LIU Song-hua,TANG Bo-wen,HAN Li-fang,ZHOU Liang. Efficient deterministic replay technique based on adaptive release strategy [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1917-1924.
[5] SHAN Ze-biao,LIU Xiao-song,SHI Hong-wei,WANG Chun-yang,SHI Yao-wu. DOA tracking algorithm using dynamic compressed sensing [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1938-1944.
[6] YAO Hai-yang, WANG Hai-yan, ZHANG Zhi-chen, SHEN Xiao-hong. Reverse-joint signal detection model with double Duffing oscillator [J]. 吉林大学学报(工学版), 2018, 48(4): 1282-1290.
[7] QUAN Wei, HAO Xiao-ming, SUN Ya-dong, BAI Bao-hua, WANG Yu-ting. Development of individual objective lens for head-mounted projective display based on optical system of actual human eye [J]. 吉林大学学报(工学版), 2018, 48(4): 1291-1297.
[8] CHEN Tao, CUI Yue-han, GUO Li-min. Improved algorithm of multiple signal classification for single snapshot [J]. 吉林大学学报(工学版), 2018, 48(3): 952-956.
[9] CHEN Mian-shu, SU Yue, SANG Ai-jun, LI Pei-peng. Image classification methods based on space vector model [J]. 吉林大学学报(工学版), 2018, 48(3): 943-951.
[10] MENG Guang-wei, LI Rong-jia, WANG Xin, ZHOU Li-ming, GU Shuai. Analysis of intensity factors of interface crack in piezoelectric bimaterials [J]. 吉林大学学报(工学版), 2018, 48(2): 500-506.
[11] LIN Jin-hua, WANG Yan-jie, SUN Hong-hai. Improved feature-adaptive subdivision for Catmull-Clark surface model [J]. 吉林大学学报(工学版), 2018, 48(2): 625-632.
[12] WANG Ke, LIU Fu, KANG Bing, HUO Tong-tong, ZHOU Qiu-zhan. Bionic hypocenter localization method inspired by sand scorpion in locating preys [J]. 吉林大学学报(工学版), 2018, 48(2): 633-639.
[13] YU Hua-nan, DU Yao, GUO Shu-xu. High-precision synchronous phasor measurement based on compressed sensing [J]. 吉林大学学报(工学版), 2018, 48(1): 312-318.
[14] LIU Dong-liang, WANG Qiu-shuang. Instantaneous velocity extraction method on NGSLM data [J]. 吉林大学学报(工学版), 2018, 48(1): 330-335.
[15] WANG Fang-shi, WANG Jian, LI Bing, WANG Bo. Deep attribute learning based traffic sign detection [J]. 吉林大学学报(工学版), 2018, 48(1): 319-329.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Guo Kong-hui，Wu Hai-dong，Lu Dang . Brush model for steadystate sideslip of tire on icy road[J]. 吉林大学学报(工学版), 2007, 37(02): 253 -0258 .
[2] Zhang Feng-jun，Liu Jia-hong，Ma Jiu-tong，Hui Jin . Application of starch based degradable carrier in
simultaneous nitrification and denitrification[J]. 吉林大学学报(工学版), 2008, 38(02): 319 -0322 .
[3] KONG Fan-sen,WANG Jun,SUN Hai-gang . Fuzzy comprehensive evaluation of equipment usability of engine cylinder block production line based on AHP[J]. 吉林大学学报(工学版), 2008, 38(06): 1332 -1336 .
[4] LI Suo-jun,GAO Hai-bo,DENG Zong-quan. Multi-objective optimization of rocker-bogie suspension parameters of  lunar rover for energy-saving passing obstacle[J]. 吉林大学学报(工学版), 2010, 40(03): 729 -0734 .
[5] ZHANG Xiao-wei1，LIU San-yang1，CHI Xiao-ni2 . Efficient interval-genetic algorithm for multipeak global optimization[J]. 吉林大学学报(工学版), 2008, 38(04): 876 -879 .
[6] YAO Guo-feng，GAO Xue-fei . Controllability of structure with repeated eigenvalues[J]. 吉林大学学报(工学版), 2008, 38(06): 1359 -1365 .
[7] JING Zhong-Qing, QIN Yu-Chun, ZHAN Feng. [J]. 吉林大学学报(工学版), 2009, 39(04): 948 -952 .
[8] DUAN Bin, SUN Tong-jing,LI Zhen-hua, HUANG Chang-wei,ZHANG Guang-xian. IIR Butterworth digital filter for full digital inverter[J]. 吉林大学学报(工学版), 2009, 39(增刊2): 311 -0314 .
[9] MA Xun,WANG He,NA Jing-xin. Rib equivalence model of CAE analysis in car body concept design phase[J]. 吉林大学学报(工学版), 2009, 39(06): 1431 -1434 .
[10] HUANG Yan-guo, XU Lun-hui, KUANG Xian-yan. Application of fuzzy Kalman filter in travel time estimation in urban expressway[J]. 吉林大学学报(工学版), 2014, 44(3): 648 -654 .
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd