基于简单线性迭代聚类和快速最近邻区域合并的图像分割算法

doi:10.13229/j.cnki.jdxbgxb20171009

摘要/Abstract

摘要：

针对传统区域邻接图在描述数据结构时,搜索全局最优解难的问题,提出了一种基于简单线性迭代聚类(SLIC)和快速最近邻区域合并的图像分割算法。该方法在区域邻接图基础上引入了最近邻接图来优化全局搜索,首先用SLIC超像素算法将图像分割成小区域,利用区域邻接图(RAG)和最近邻接图(NNG)的邻接表数据结构来描述区域之间的关系,然后计算每个待合并区域与其所有邻接区域之间的不相似度函数值,最后合并不相似度值最小的区域。实验结果表明:本文方法能较好地将最相似的区域进行合并,与传统的区域合并算法相比,降低了合并计算的复杂度,大幅度提高了区域合并的准确性。

关键词: 信息处理技术, 图像分割, 简单线性迭代聚类, 区域邻接图, 最近邻接图, 区域合并

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

中图分类号:

TP391.4

刘仲民,王阳,李战明,胡文瑾. 基于简单线性迭代聚类和快速最近邻区域合并的图像分割算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1931-1937.

LIU Zhong-min,WANG Yang,LI Zhan-ming,HU Wen-jin. Image segmentation algorithm based on SLIC and fast nearest neighbor region merging[J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1931-1937.

图/表 7

图1

图2

图3

图4

图5

表1

表2

参考文献 21

[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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

算法	第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

算法	时间复杂度
NCUT	O(N²)
SCOW	O(N)
SLIC	O(N)
SLIC+DBSCAN	O(N+N²)
MeanShift+MSRM	O(TN²)
本文算法	O(N+log₂(‖E‖))