结合图论的JSEG彩色图像分割算法_耿永政_陈坚

图像;识别;视觉

网络出版时间：2014-02-11 16:18

网络出版地址：http://wendang.chazidian.com/kcms/detail/61.1450.TP.20140211.1618.047.html

结合图论的JSEG彩色图像分割算法

耿永政，陈坚

（西南大学计算机与信息科学学院重庆400715）

摘要：静态图像压缩标准（JSEG）分割算法是一种经典的图像分割方法，它充分考虑到了图像的局部信息，可以获得比较精确的分割边界。但JSEG算法在分割过程中计算量相当大并且分割结果容易出现过分割现象。由此，本文提出一种结合图论的JSEG图像分割算法。首先去除JSEG算法中在多个尺度上反复计算J值的过程，改为仅在一个小尺度上进行计算。其次，在得到的J图上使用K-means方法进行聚类，分割得到过分割区域。最后，将分割后的小区域对应为图中的点，进而利用图理论的方法进行区域合并。实验结果表明新算法具有高精度和低复杂度的优势。关键词：K-means；JSEG算法；图理论；图像分割

TheJSEGColorImageSegmentationAlgorithmTheory

GengYong-zheng,(CollegeofComputerandInformationScience,Abstract:JointSystemsEngineeringGroup(JSEG)isaalgorithm.Itfullytakesthelocalimageinformationintoaccount,somoreboundary.ButtheJSEGalgorithmhasthelargecomputationandForthisreason,thispaperproposesasegmentationalgorithmcombiningJvalueonlyonasmallscaleinsteadoftheiterativeprocessonclusteringmethodontheJ-maptogetover-segmentationregions.aandthenusethegraphtheoryforregionmerging.Experimentalnewhasahighaccuracyandlowcomplexityadvantage.

Keywords:K-means;JSEGsegmentation1引言

效工具。而在这其中，图像分割[1]是一个最基本的问题，它从一副含有丰富信息的图像中分割出人们需要的区域，进而再进行后期处理。因此图像分割在各个领域都有着广泛应用前景。

现有的图像分割方法主要分为以下几类：基于阈值的分割方法、基于边缘的分割方法、基于区域的分割方法以及基于特定理论的分割方法等。1998年以来，研究人员在原有的分割算法基础上不断改进创新，并把其他学科的一些新理论新方法引入到图像分割中来，提出了很多新的分割方法。其中，基于特定理论的分割方法主要有：聚类分析方法、模糊集理论方法、统计学理论方

法、图理论方法等。然而到目前为止图像分割技术仍然不够成熟，还没有一种方法能够适合于不同类型的图像，这也成了阻碍图像分割大规模和大范围应用的一个重要因素[2]。

其中，文献[3]提出的JSEG算法是一种经典的基于颜色纹理无监督的区域生长的图像分割方法，其分割结果较准确、鲁棒性较高。但JSEG算法的缺点也是显而易见的。首先，算法在分割中需要在多个尺度下反复进行局部J值计算和区域生长，计算量大，算法复杂度高。其次，在后期区域合并的时候JSEG算法没有考虑到各个区域之间的相关性，而仅采用的是简单的基于颜色直方图的合并方法，合并效果比较差。

针对以上两点，本文提出了一种结合图论的JSEG的新的图像分割方法。新算法使用的是图论中经典的Ncut(NormalizedCuts,归一化割)[4]分割算法。在大多数图像分割应用中，Ncut算法都是直接利用图像像素进行分割，对于大图像，由于像素个数非常多，所以计算量相当的大。因此

图像;识别;视觉

我们将JSEG算法和Ncut算法的思想相结合，各取其精华。在新算法中，过程简化了JSEG中反复计算J值的过程，然后使用K-means聚类方法产生初步的分割区域，最后在小区域的基础上运用Ncut方法进行合并。实验证明它有效克服了JSEG算法计算复杂和区域合并不准确的缺点。2JSEG算法和图论分割方法2.1JSEG分割算法

JSEG图像分割算法主要包括两个过程，即颜色量化和空间分割[5]。颜色量化的目的是为了减

PGF（J描设w?(x,y均值为JSEG算法的具体分割流程如图1所示。从过

程上来说，由图1容易看出JSEG算法为了获得较精确的边界，需要增大或者降低尺度反复进行J值计算、种子选择、区域生长等过程。

在JSEG算法中，用颜色量化的方式将图像的颜色信息转化成“类图”，用类标签来代替每一个像素，这样方便了图像分割，但这样也势必使图像丧失了许多空间信息。另外，JSEG算法采用种子选取，区域分割的方式进行分割，由于种子选取的不准确性，这样必然会带来过分割的情况。为此，很多人提出了不同的基于JSEG算法的改进JSEG）。等，miSTSW差，而S为：

J?图1JSEG算法流程图

图像;识别;视觉

2.2图论分割方法

图理论作为一种新型的工具被应用到图像分割中，其主要思想是将图像（image）映射为带权的无向图（graph）。图中的每一个节点对应图像中每一个像素点。而图节点之间的权重则表示两个像素点之间的差异或者相似性[11,12]。

图分割的思想是：在图G=(V,E)(V为图中所有顶点的集合,E为图中边的集合)中,通过移除图的某些边,把图分割成两个不相交的顶点集合A和B,而集合A和B须满足A?B=V,A?B=?。而移除边的权重总和,作为A

图论中经典的Ncut算法，将分割后的每一个过分割区域对应到图中的相应节点，通过图论的方法对图进行分割，从而实现对过分割区域合并[15]的目的。

Ncut方法是Shi和Malik提出的针对最小割方法分割时所存在的缺陷进行改进的一个图分割方法。Ncut准则不仅计算分割子集之间的不相关度而且计算各个子集内部的总的相关度。这样就避免了最小割准则分割出单个顶点或者区域的情况。相关方程式如下：

Ncut(A,B)?

cut(A,B)cut(A,B)

?

)

（8）（9）

使（值问题转换（10）

di。

其元素值（11）

得到“类图”。

2）用一个以该像素点为中心点的圆形模板扫描“类图”得到的对应的“J图”。

3）在“J图”上使用K-means聚类算法进行空域分割，得到过分割小区域。

4）取出每个区域，并用一个区域点代替一个区域，区域点的信息包括特征向量信息和空间位置信息等。

5）根据步骤4），原始图像就变为了由这些区域点组成的无向图，这个无向图作为Ncut的输入，并利用这些区域点构造出权值矩阵W和D,然后对式（11）进行求解完成聚类分割。

3传统的彩色图像分割算法[13]都是首先将彩色图像转化成灰度图像，再对灰度图像进行处理。而JSEG算法是一个经典的彩色图像分割方法，本文所提出的新算法是借助JSEG算法的思想，然后对其进行扩展和改进的彩色图像分割算法。

新算法取消了原JSEG在多个尺度上进行局部J值计算、种子选择和区域生长的过程。改为只在一个小尺度上进行J值计算，得到相应的“J图”，然后直接使用K-means[14]算法对“J图”进行聚类。由于仅在一个小尺度上进行J值计算和K-means中聚类质心点选取不准确的原因，分割区域必然会出现过分割的情况。接下来新算法引入

图像;识别;视觉

步骤4）中我们选取的权值矩阵W如下：

?F(i)?F(j)

2

2

?X(i)

?X(j)

表1JSEG和新得到初始分割的时间对比表

Wij?e

?I2

*?

e0

?2X

2

2

ifi,j相邻ifi,j不相邻

其中，F(i)是区域点i的颜色空间向量信息。X(i)为区域点空间坐标信息。?I,?X是区域点值域差异及空域差异的敏感程度参数。取值根据人工经验所得。新算法的全部流程图如图3所示。

24%算法计算过程所示。

(a3)

4根据前文的理论分析，新算法减少了迭代计算J值的过程，分割结束时所用的时间应该比原JSEG算法要少。并且最后得到的分割区域，会有效的减少分割块数，而且分割后的区域会更符合人类视觉感知。由此，针对以上两点预期，做了两组对比实验。

实验一：随机选取了5张图片分别对原JSEG算法和改进的新算法进行程序运行时间的测试和比较，其实验结果如表1所示。

(b3)

(c1)

原图像

(c2)

JSEG算法分割结果

(c3)

算法改进后分割结果

图4新算法和原JSEG算法分割的结果对比图（(a1)-(c1)为原图像，(a2)-(c2)为JSEG分割结果，(a3)-(c3)为新算法

分割结果）

图像;识别;视觉

从图4中可以看出（a2）、（b2）分割后的图片存在明显的过分割现象。而（a3）和（b3）中分割区域不但减少了，而且更符合人类的视觉感知。如（a3）中，新算法充分的把图片分割成为了瀑布、土地、船和人几个大类，分割边界也较精确。

而对于图片内容比较简单，物体区分比较明显的（c1）图片来说，两种方法分割效果都比较好，没有太大差别。可见，与原JSEG算法相比较，新算法对颜色复杂的图片改进效果更明显。

由以上实验可以看出，正如我们之前预想的，新算法有效地缩短了程序运行时间和减少了图像过分割的情况，而且对物体的边界分割较准确。另一方面新算法对颜色简单的目标分割效果较好，对内部色彩变化剧烈、边界轮廓复杂的目标分割效果较差。这一点也是图像分割一直存在和难于突破的重点难点所在，需要图像方面的专家学者和众多研究人员一起努力克服。5结束语

本文通过结合JSEG了JSEG觉感知。同时也解决了Ncut进一步的研究。参考文献：

[1]黄长专,王彪,杨忠.[J].计算

机技术与发展,2009,19(1):76-79.

[2]范静辉,吴建华,刘晔.基于颜色信息与区域

生长的图像分割新算法[J].中国图象图形学报,2005,10(9):1079-1081.[3]YiningDeng,BSManJunath.Unsupervised

SegmentationofColor-TextureRegionsinImagesandVideo[J].IEEETransactionsOnPatternAnalysisandMachineIntelligence,2001,23(8):800-808.[4]J.Shi,J.Malik.NormalizedCutsandImage

Segmentation[J].IEEETransactionsonPattern

AnalysisandMachineIntelligence,2000,22(8):888-905.

[5]孙卫芳.基于JSEG的视频/图像分割技术研

究[D].郑州:郑州大学,2010.[6]YZheng,JYang,YZhou.Unsupervised

segmentationonimagewithJSEGusingsoftclassmap[J].IntelligentDataEngineeringandAutomatedLearning-IDEAL2004LectureNotesinComputerScienceVolume3177,2004,pp197-202.

[7]ChenHC,ChienWJ,andWangSJ.

Contrast-basecolorimagesegmentation[J].IEEELetters,vol.11,no.7,pp.[8]Yang,YuChouChang.

byintoJSEGmethodofPatternRecognitionvol.16,pp.1983-1990,2006.[9]M.Kibria,Md.MonirulIslam.

SegmentationUsingVisibleandCannyEdgeDetector[J].andInformationTechnology(ICCIT),15thInternationalConferenceon.22-24Dec.2012.

K.S.Komati,E.O.T.Salles,M.

Sarcinelli-Filho.Unsupervisedcolorimagesegmentationbasedonlocalfractal.descriptorandJimages[J],IEEEICIT2010InternationalConferenceonIndustrialTechnology,2010,pp.303-308.

[11]刘建龙.基于图论的图像分割算法研究[D].

哈尔滨工业大学,2006.

[12]陈彦至,黄永锋.Ncut在图像分割中的应用[J].

计算机技术与发展,2009,19(1):228-233.

[13]林开颜,吴军辉,徐立鸿.彩色图像分割方法

综述[J].中国图象图形学报,2005,10(1):1-10.[14]周爱武,于亚飞.K-Means聚类算法的研究[J].

计算机技术与发展.2011,21(2):62-65.

[15]郑洪英.数据挖掘聚类算法的分析和应用研

究[D].重庆:重庆大学,2002.