一种用于谱聚类图像分割的像素相似度计算方法*

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

一种用于谱聚类图像分割的像素相似度计算方法*

纳跃跃，于剑**

出版日期:2015-11-03 发布日期:2015-11-03
作者简介: (北京交通大学计算机与信息技术学院，北京，100044)
基金资助:
中央高校基本科研业务费专项资金

A new pixel affinity for spectral image segmentation

Na Yue-Yue ,Yu Jian

Online:2015-11-03 Published:2015-11-03
About author: (Department of Computer Science，Beijing Jiaotong University, Beijing, 100044 ,China)

摘要/Abstract

摘要： 图像分割是许多计算机视觉任务中的关键步骤，而谱聚类算法是目前图像分割的主要方法之
一为了使用谱聚类算法进行图像分割，首先需要计算用于反映像素间相似程度的相似矩阵，所采用的
相似度计算方法是否能真实的反映出像素间的视’觉相似度将显著影响算法的输出结果.针对普聚类图
像分割算法的相似度计算问题，提出了一种新的像素间相似度计算方法.与传统方法相比，该方法不但
考虑了像素自身的特征，而且考虑了其邻域内像素的视觉特征，以及两像素之间的边缘信息，使得计算
所得的相似度更加符合人类的直观感受，且不易受到纹理的影响.另外，提出了一种针对该相似度计算
方法的相似矩阵构造方法.在BSDS300图像库上的实验表明，使用该相似度能得到较好的图像分割
结果.

Abstract: image segmentation is a key step in many computer vision tasks, one of the main approaches for image
segmentation is spectral clustering, In order to use spectral clustering algorithms to group image pixels into regions，
affinity matrix for pixels must be calculated first. Whether the adopted pixel affinity criteria can reveal the true un-
denying visual similarity among pixels will dramatically affect the algorithm outputs. A method is proposed to calcu-
late pixel affinities for spectral image segmentation algorithms,the proposed affinity is not only decided by the visual
similarity between two pixels，but also affected by their neighborhoods, and the edge information between them.
Compared with traditional approaches,the new similarity is more compatible with human visual sensation,and more
robust against the influence from texture. In addition,an affinity matrix construction method is also presented to co-
operate with the new affinity metric. Experiments on BSDS300 image dataset show that the new approach can obtain
good results on spectral image segmentation tasks.

纳跃跃，于剑**
. 一种用于谱聚类图像分割的像素相似度计算方法*[J]. 南京大学学报(自然科学版), 2013, 49(2): 159–168.

Na Yue-Yue ,Yu Jian. A new pixel affinity for spectral image segmentation[J]. Journal of Nanjing University(Natural Sciences), 2013, 49(2): 159–168.

参考文献

[1]Fowlkes C，Martin D, Malik J. Learning affinity functions for image segmentation; Combining
patch-based and gradient- based approaches. Com- puter Vision and Pattern Recognition, 2003，2:54~61.
[2]Lihi Z M, Pietro P. Self-tuning spectral clustering. Advances in Neural Information Processing Systems 2004，17:1601一1608.
[3]Sharon E, Galun M, Sharon D, et al. Hierarchy and adaptivity in segmenting visual scenes. Na- ture,2006,442:810一813.
[4]Ng A Y,Jordan M I,Weiss Y. On spectral clustering; Analysis and an algorithm. Advances in Neural Infor-
mation Processing Svstems,2001,849一856.
[5]Shi J，Malik J. Normalized cuts and image seg-mentation. IEEE Transactions on Pattern Analy-
sis and Machine Intelligence，2000，22(8):888~905.
[6]Martin D, Fowlkes C，Tal D,et al. A database of human segmented natural images and its applica-
tion to evaluating segmentation algorithms and measuring ecological statistics. The 8th IEEE In-
ternational Conference on Computer Vision,2001,2:416~423.
[7]Wang J Z,Li J,Wiederhold G.SIMPLIcity; Semantics- sensitive integrated matching for picture libraries.
IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(9):947一963.
[8]Cardson C，Belongice S J，Greenspan H K，et al. Blobworld:Image segmentation using expecta-
tion-maximization and its application to image querying, IEEE Transactions on Pattern Analysis
and Machine Intelligence, 2002，24(8):1026 一1038.
[9]Comaniciu D, Meer P. Mean shift; A robust approach towards feature space analysis, IEEE Transactions on
Pattern Analysis and Machine intelligence, 2002, 24(5):603~619.
[10]Brox T,Rousson M,Deriche R,et al. Color,cexture,and motion in level set based segmentation and
tracking. Journal image and Vision Computing, 2010,28(3):376一390.
[11]Liu G G,Lin Z C, Yu Y，et al. Unsupervised ob- ject segmentation with a hybrid graph model
(HGM), IEEE Transactions on Pattern Analysis and Machine Intclligence,2010，32(5):910一924.
[12]Zhang L Ji Q,Image segmentation with a unified graphical model, IEEE Transactions on Pattern
Analysis and Machine Intelligence，2010，32(8): 1406一1425.
[13]Zhang J Y，Zheng J M，Cai J F. A diffusion ap proach to seeded image segmentation, IEEE Con-
ference on Computer Vision and Pattern Recogni tion,2010，2125一2132.
[14]Cai X Y，Dai G Z, Yang L B. Survey on spectral clustering algorithms. Computer Science,2008，35
(7):14-18.蔡晓妍，戴冠中，杨黎斌.谱聚类算法综述.计算机科学，2008,35(7) : 14一18).
[15]Ulrike von L. A Tutorial on spectral clustering. Sta-tistics and Computing, 2007，17(4);395一416.
[16]Hamad D, Biela P.Introduction to spectral cluster- ing, International Conference on Information and
Communication Technologies:From Theory to Ap- plications, 2008，1一6.
[17]Filippone M,Camastra F, Masulli F, et al. A survey of kernel and spectral methods for clustering. Pattern
Recognition, 2008 , 41:176一190.
[18]Cour T,Benezit F,Shi J B. Spectral segmentation with multiscale graph decomposition, IEEE Com-
puter Society Conference on Computer Vision and Pattern Recognition,2005,2:1124一1131.
[19]Kim T H，Lee K M，Lee S U. Learning full pair-wise affinities for spectral segmentation, IEEE
Conference on Computer Vision and Pattern Rec- ognition, 2010，2101一2108.
[20]Rafael C G, Richard E W. Digital image processing. The 2^nd Edition. Prentice Ha11,2008，976.
[21]Rotem O，Greenspan H K, Goldberger J. Combining region and edge cues for image segmentation in a
probabilistic Gaussian mixture framework, IEEE Conference on Computer Vision and Pattern Recog- nition, 2007，1一8.
[22]Palmer S E. Vision science; Photons to phenomeno- logy. MlT Press,1999,810.
[23]Gehler P，Nowozin S. On feature combination for multiclass object classification.The IEEE 12^th In-
ternational Conference on Computer Vision, 2009,221一228.
[24]Canny J. A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine
lntelligence,1986,8(6):679一698.
[25]Martin D R，Fowlkes C C，Malik J. Learning to detect natural image boundaries using local
brightness,color,and texture clues. IEEE Trans actions on Pattern Analysis and Machine lntelli-gence,2004,26(5):530~549
[26]Qin L,Zhang L,Jane Y,et al. Dark line detection with line width extraction.The 15th IEEE lnter-
national Conference on Image Processing, 2008,621~624.
[27]The msncut algorithm, http;//www, seas, upenn.edu/一timothee/software/ncut multiscale/ ncut multiscale. htm1,2010-10-01.
Kim’s algorithm, http;//cv.snu. ac.kr/thkim/FNCUT CVPR10/index, htm1,2013-02-23.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed