一种新的基于超像素的谱聚类图像分割算法*

南京大学学报(自然科学版) ›› 2013, Vol. 49 ›› Issue (2): 169–175.

一种新的基于超像素的谱聚类图像分割算法*

高尚兵¹**，周静波²，严云洋¹

出版日期:2015-11-02 发布日期:2015-11-02
作者简介: (1.淮阴工学院计算机工程学院，淮安,223003;
2.南京理工大学计算机科学与技术学院，南京，210094)
基金资助:
江苏省高校自然科学基金(11KJA460001,12KJB520002)，江苏省青蓝工程，淮安市“533”工程，淮安市科技项目
(SN12076，HASZ2012050)

A new superpixel based spectral clustering for image segmentation

Gao Shang- Bing¹，Zhou Jinh Bo²,Yan Yun-Yang¹

Online:2015-11-02 Published:2015-11-02
About author: (1.Faculty of Computer Engineering, Huaiyin institute of Techlonogy, H uai’an, 223003 , China;
2.Computer School，Nanjing University of Science and Technology,Nanjing,210094,China)

摘要/Abstract

摘要： 谱聚类是近十年来出现的一种极具竞争力的聚类算法，许多扩展和应用算法相继出现，比如
图像分割.但是，对图像分割而言，由于基于谱聚类的方法计算量十分庞大，使其应用受到严重挑战;而
降低图像分辨率的策略则会导致细节信息的丢失，使得图像的分割结果不够准确.提出一种新的基于超
像素的谱聚类图像分割算法.首先，新算法将图像分割成小区域，这些小区域称为超像素，相邻的两个超
像素之间的相似性用Bhattacharyya系数进行度量;然后，利用谱聚类将超像素聚类成有意义的区域.实
验结果表明，相较于经典算法，新算法在Berkeley图像数据库上能产生较好的分割结果，并且没有增加
计算复杂度.

Abstract: In the last decade, spectral clustering has become one of the most popular clustering algorithms, with
many extensions and applications of the algorithm being developed，c. g. image segmentation. Unfortunately, scal-
ability is a common challenge with spectral clustering based image segmentation，since the computation can be-
come intractable for large images. Down-sizing the image will cause a loss of finer details and can lead to less accu-
rate segmentation results.To address this challenge，we propose a new algorithm namely super-pixel based spec
tral clustering. First，the algorithm over-segments an image to small regions, called superpixcls.TheTurboPixcls
method proposed by Alex Levinshtcin is chosen to get the superpixcls.This algorithm uses Level set boundary in-
dication method to represent the boundary of the superpixcls.The number of superpixcls is crucial for boundary
error rate and consuming time.The number ranging from 200 to 300 is best by the experiments.The color simi-
larity between superpixcls of one object is high，and the color similarity between different superpixcls of different
objects is low.Thus，color histogram is chosen to represent the characteristics of the superpixels.Of course，the
use of color histogram calculating the similarity between the superpixcl also cause problems.Two dissimilar su-
perpixcls may have similar color histograms.To reduce the probability of occurrence，superpixcls adjacency ma-
trix is calculated before calculating the similarity matrixs.There arc two benefits by the superpixcls adjacency ma-
tnx，:1)reducing the computation cost;2)considering the position information of super pixels and increasing the
accuracy of the segmentation.The similarity between two adjacent super pixels is measured by Bhattacharyya co-
efficient.Then，we group the superpixcls by spectral clustering for finding the meaningful regions. According to
the obtained paired similarity matrix，to the superpixcls arc clustered by spectral clustering algorithm. Experimen-
tal results indicate that compared with state-of-arts, this algorithm can achieve better segment results on Berkeley
image database without significant computational demands.

高尚兵¹**，周静波²，严云洋¹. 一种新的基于超像素的谱聚类图像分割算法*[J]. 南京大学学报(自然科学版), 2013, 49(2): 169–175.

Gao Shang- Bing¹，Zhou Jinh Bo²,Yan Yun-Yang¹. A new superpixel based spectral clustering for image segmentation[J]. Journal of Nanjing University(Natural Sciences), 2013, 49(2): 169–175.

参考文献

[1]Ng A, Jordan M, Weiss Y. On spectral clustering; A-nalysis and an algorithm. Proceedings of Advances in
Neural information Processing Systems. Vancouver British Columbia,Canada,2001,849一856.
[2]Datta R,Joshi D,Li J，et al. lmage retrieval Ide- as，influences, and trends of the new age.ACM
Computing Surveys,2008，40(2):1一60.
[3]Li S J，Wang W G,Xie P,et al. An adaptive level set model with feature selection for remote sens-
ing image segmentation. Journal of Nanjing Uni- versity(Nature Sciences)，2012，48(4):482一
490.(李士进，王万国，谢萍等.面向遥感图像分割的自适应特征选择水平集模型.南京大学学报(自然科学),2012,48(4):482-490).
[4]Shi J，Malik J. Normalized cuts and image segmenta- tion. IEEE Transactions on Pattern Analysis and
Machine lntelligence,2000,22(8) :888一905.
[5]Chang H，Yeung D Y. Robust path-based spectral clustering with application to image segmentation.
Proceedings of IEEE international Conference on Computer Vision, Beijing, China, 2005 ; 278一285.
[6]Fowlkes C, Belongie S, Chung F, et al. Spectral grouping using the NystrOm method, IEEE
Transactions on Pattern Analysis and Machine lntelligence,2004,2602):214一225.
[7]Lihi Z M, Pietro P. Self-tuning spectral clustering. Proceedings of Advances in Neural Information Pro-
cessing Systems, Vancouver, British Columbia, Cana- da,2004(17):1601一1608.
[8]Alex L.TurboPixels:Fast superpixels using geo-metric flows. IEEE Transactions on Pattern A-
nalysis and Machine intelligence，2009(31):2290~2297.
[9]Von Luxburg U. A tutorial on spectral cluste- ring. Max Planck institute for Biological Cyber netics. Technical Report,TR-149,2006.
[10]Xiang T，Gong S. Spectral clustering with eigen- vector selection. Pattern Recognition, 2008，4: 1012一1029.
[11]Dorm C，Ramesh V,Peter M. Kernel-based object tracking.lEEE Transactions on Pattern Analysis
and Machine lntelligence,2003,25(5):564一575.
[12]Martin D,Fowlkes C,Tal D,et al. A database of hu- man segmented natural images and its application to
evaluating segmentation algorithms and measur- ing ecological statistics. IEEE international Con-ference
on Computer Vision,2001 ,416一423.
[13]Frederick T, Alexander W, David A C. Enabling scalable spectral clustering for image segmentation.
Pattern Recognition,2010,43(12);4069一4076.
[14]Ozcrtem U, Erdogmus D, Jenssen R. Mean shift spectral clustering. Pattern Recognition, 2008，41 (6):1924一1938.
[15]Tao W B,Jin H,Zhang Y M. Color image segmentx tion based on mean shift and normalized cuts, IEEE
Transactions on Systems, Man, and Cybernetics-Part B; Cybernetics, 2007 ( 37 ):1382一1389.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed