基于颜色量化和密度峰聚类的彩色图像分割

基于颜色量化和密度峰聚类的彩色图像分割

王鹏宇，游有鹏，杨雪峰

南京航空航天大学机电学院，南京210001

摘

要：彩色图像分割是簇绒地毯数字化制造的关键技术，图像的分割质量直接影响到后续的图像处理。为解决地

毯的彩色图像分割问题，针对人眼在RGB颜色空间中感知不均匀的特性，提出了一种基于颜色量化和密度峰聚类的彩色图像分割算法。基于Lab颜色空间进行颜色量化，在HVC颜色空间中用NBS距离来衡量人眼对颜色差异的感知程度，采用改进的密度峰聚类算法自动确定聚类中心，从而分割地毯图案。实验结果表明，该算法能在不影响人眼感知的前提下得到颜色种类少且边缘清晰的地毯分割图像。关键词：Lab颜色空间；NBS距离；密度峰聚类；图像分割文献标志码：A

中图分类号：TP391.41

doi：10.3778/j.issn.1002-8331.1810-0147

王鹏宇，游有鹏，杨雪峰.基于颜色量化和密度峰聚类的彩色图像分割.计算机工程与应用，2020，56（2）：211-215.WANGPengyu,YOUYoupeng,YANGXuefeng.Colorimagesegmentationbasedoncolorquantizationanddensitypeakclustering.ComputerEngineeringandApplications,2020,56（2）：211-215.

ColorImageSegmentationBasedonColorQuantizationandDensityPeakClustering

WANGPengyu,YOUYoupeng,YANGXuefeng

CollegeofMechanicalandElectricalEngineering,NanjingUniversityofAeronauticsandAstronautics,Nanjing210001,ChinaAbstract：Colorimagesegmentationisthekeytechnologyoftuftedcarpetdigitalmanufacturing.Thequalityofimagesegmentationdirectlyaffectsthesubsequentimageprocessing.Inordertosolvetheproblemofcarpetcolorimageseg-mentation,acolorimagesegmentationalgorithmbasedondensitypeakclusteringandcolorquantizationisproposedtoovercometheinhomogeneousperceptionofhumaneyesinRGBcolorspace.Firstly,colorquantizationisperformedbasedonLabcolorspace,andthenNBSdistanceisusedtomeasurethedifferenceofcolorperceptioninHVCcolorspace.Finally,densitypeakclusteringalgorithmisusedtoautomaticallydeterminetheclusteringcenterandsegmentthecarpetimage.Experimentalresultsshowthatthealgorithmcangetcarpetsegmentationimageswithfewcolorcategoriesandclearedgeswithoutaffectinghumanperception.

Keywords：Labcolorspace;NBSdistance;densitypeakclustering;imagesegmentation

1引言

到色块图。图像分割质量的好坏，直接影响到后续图像传统簇绒地毯在簇绒前需要根据客户提供的图案

处理的效果。

在平面设计软件中重新绘制，然后进行光照制版、印染、传统的图像分割方法可分为基于阈值的分割方簇绒等工序，制作过程复杂。为了实现簇绒地毯的数字法[1]、基于区域的分割方法[2]和基于边界的分割算法[3]。化制造，需要通过图像处理和计算机图形学方法来得到聚类理论在图像分割中也取得了较好的效果，常用的聚地毯填充路径的矢量描述。整个过程需要经过图像分类算法包括：K-means聚类[4]、层次聚类[5]、谱聚类[6]、模割、边缘提取、轮廓追踪、曲线拟合和路径填充等步骤。糊C均值[7]和蚁群聚类[8]。为了使分割算法适用于地毯其中图像分割的作用是提取图像中的主要构成色，去除制造，本文算法需要在不影响人眼感知的前提下，得到杂色点，得到边界清晰的分割图像，从而按颜色分离得

颜色种类少且边界清晰的地毯分割图像。本文先通过

作者简介：王鹏宇（1994—），男，硕士研究生，主要研究方向：图像处理与计算机图形学，E-mail：pengyuwang@nuaa.edu.cn；游有鹏

（1960—），男，博士，教授，主要研究方向：机电控制及自动化；杨雪峰（1984—），男，讲师，主要研究方向：智能加工过程优化与监测。

收稿日期：2018-10-15

修回日期：2018-12-20

文章编号：1002-8331（2020）02-0211-05

CNKI网络出版：2019-01-17,http://kns.cnki.net/kcms/detail/11.2127.tp.20190116.1731.017.html

2122020，56（2）ComputerEngineeringandApplications计算机工程与应用

颜色量化算法对图像进行预处理，合理减少颜色种类。本文首次将密度峰聚类算法应用于图像分割，并结合应用背景对算法进行了改进。最终的实验结果表明，改进后的算法能取得较好的彩色图像分割效果。

2Lab颜色空间

数字图像通常是在RGB（红、绿、蓝）颜色空间对像

素点进行描述，但人眼对RGB颜色空间的感知是不均匀的。在表1中，颜色2与颜色1在RGB分量上的变化分别为30，－35，－35，颜色4与颜色3具有相同的变化量。但在人眼中，从颜色3到颜色4的变化更为强烈。因此需要将像素从RGB颜色空间变换到人眼感知均匀的颜色空间中。

表1

相同RGB差值下的颜色对比

序号颜色

R值G值B值103535230003180701504

210

35

115

Lab颜色空间由国际照明委员会在1976年提出。Lab颜色空间是一种设备无关且人眼感知均匀的颜色空间。其中，L为明度分量，a和b为颜色分量。从RGB颜色空间到Lab颜色空间的转换公式[9]如下：

éêXù=éê0.41200êYúúê0..213ëZûë0019

0..358

7150..180ùéRù0.019.072ú950úêêGú0ú（1）

ûëBû

ìY13L=ïï116(YYY0)-16,0>0.008856í

ï（2）

ïî903.3(YYY0),Y0≤0.008856a=500(f(XX0)-f(YY0

))（3）b=200(f(YY0)-f(ZZ0

))

（4）

其中：

ì

t1f(t)=íï3ï,t>0.008856î7.787t+116,t≤0.008856

（5）[X0Y0

Z0]=[0.9501.01.089]（6）

3颜色量化

3.1量化目的

图1（a）按像素的RGB值进行统计，颜色种类共有749种。图像中的颜色种类过多会给聚类中心的选择带来困难。所以在进行聚类前，需要先在Lab颜色空间内对图像进行颜色量化，合理减少图像中的颜色种类。图1（b）为图像的局部放大图，可以看到在色块边界处存在许多杂色点。通过颜色量化可以减少杂色点，有利于色块的分离和减少地毯所需纱线的颜色种类。

（a）原图

（b）局部放大图

图1

簇绒地毯图像

3.2量化方法

常用的颜色量化方法有统一量化方法、频度序列算

法[10]、中位切割法[11]和八叉树量化方法[12]。本文采用的颜色量化方法基于Lab颜色空间，根据色差最小原则对颜色种类进行归并[13]。X和Y是Lab颜色空间的两种颜色，那么X和Y的色差定义如下：

EXY=(ΔLXY)2+(ΔaXY)2+(ΔbXY)2

（7）

式中，

ΔL、Δa、Δb为两种颜色的Lab分量之差。根据色差最小原则，在地毯图像中找出色差最小的两个颜色A和B。假设用颜色C来替代这两种颜色，则替换后总的色差如下：

E总=NAEAC+NBEBC

（8）

式中，NA、NB表示颜色A和颜色B在一幅图像中的像素数。公式（8）又可以表示为：

E总=EL+Ea+Eb

（9）EL=NA(LA-LC)2+NB(LB-LC)2（10）Ea=NA(aA-aC)2+NB(aB-aC)2（11）Eb=NA(bA-bC)2+NB(bB-bC)2

（12）

为使总色差最小，三个分量应达到最小。令EL、

Ea、Eb的导数为0，在导数为0时总色差可取得最小

值，求得颜色C的Lab值：

LC=NANLA

++NNBLB

AB（13）aC=NANaA

+NBaB

A+NB（14）bC=NANbA

++NNBbB

AB

（15）

根据上述颜色量化方法，可以得到将M种颜色归纳合并为N种颜色的量化方法：

步骤1读取图像，将图像中所有像素转换到Lab颜色空间。得到图像中的M种颜色，以及每种颜色的像素数。

步骤2遍历所有的颜色，根据色差公式（7）找到色差最小的两种颜色，并根据公式（13）~（15）求得替代颜色，用新颜色替换原有颜色，新颜色像素数为原先两种颜色像素数之和。

步骤3颜色更新完后，颜色种类M减1。若M大于N，则跳回步骤2继续执行，否则结束量化。

本文在对图像进行量化时，将N设为256。对图1进行量化后得到的结果如图2所示，图像的颜色种类从

王鹏宇，等：基于颜色量化和密度峰聚类的彩色图像分割749减为256种。由图2（b）可知，量化后图像还存在大量杂色点，需要通过聚类去除。

（a）量化后

（b）局部放大图

图2

量化后簇绒地毯图像

4

密度峰聚类应用与改进

聚类是指根据数据的相似性，将数据集划分为不同的簇或类，是一种无监督的数据分类方法，在分类时没有类别标签。聚类算法在机器学习、模式识别等领域得到广泛使用。基于密度的密度峰聚类（DensityPeaksClustering，DPC）算法是RodriguezA等人新提出的一种聚类算法[14]

。密度峰聚类算法不需要指定聚类中心的数目和对聚类中心进行初始化，且不存在收敛速度慢等问题。该算法基于数据点间的欧氏距离进行计算，不受数据的维度影响，可以用来处理高维数据。鉴于密度峰聚类的以上优点，本文首次将密度峰聚类应用于图像分割，并结合具体应用对算法进行了改进。

4.1NBS距离

在介绍密度峰聚类算法前，首先需要引入NBS距

离的概念。为了衡量人眼对色差的感知程度，Miyahara等人提出了NBS距离概念[15]。表2给出了NBS距离与人眼对色差感知的对应关系。当两种颜色的NBS距离大于3.0时，人眼即认为两种颜色色差是明显的。

表2

NBS距离与人眼感知关系

NBS距离0~0.50.5~1.51.5~3.03~66以上感知色感觉感觉感觉感觉感觉差程度

极小

轻微

细微

明显

强烈

NBS距离的计算需要先将RGB颜色空间中的点转换到XYZ空间中，转换的方法见公式（1）。再从XYZ空间变换到HVC空间，转换到HVC空间的过程如下：ìïH1=f(X)-f(Y)

íïH2=f(Z)-f(Y)（16）

îH3=f(Y)其中：

f(t)=11.6t1

3-1.6（17）ìïM1=H1íïM2=00..423HH2（18）

îM3=3

ì

ïM1ï

H=arctan(íM2)

ï

V=M3（19）

ïî

C=M12+M22

2020，56（2）213

在计算两种颜色A和B的NBS值前，先根据上述计算方法转化为HVC值，分别记为(HAVA

CA)和

(HBVBCB)。则NBS距离的计算公式可以表示如下：

NBS=2CACB(1-cos(2πΔ100H))+(ΔC)2+(4ΔV)2（20）

其中：

ìï

ΔH=|HA-HB|íï

ΔV=||VA-VB|）

îΔC=CA-CB|（214.2

算法分析

密度峰聚类算法一共可以分为3步：（1）计算所有

的数据点得到决策图；（2）通过决策图人工找出数据集的密度峰，即聚类中心；（3）将数据集中的数据点分配到距离最近的聚类中心，得到聚类结果。作为密度峰的数据点应该具有以下2个特点：（1）作为密度峰的数据点被密度相对较低的邻近数据点包围；（2）与密度更高的数据点之间存在较大的距离。所以寻找密度峰时主要是用到距离特征和密度特征。对于每个数据点i，只需要计算数据点i自身密度和到达具有更高密度的数据点的最小距离。

通常DPC算法在计算数据点间的距离时，采用的是欧氏距离。本文结合应用背景，为了符合人眼对色差的感知，计算数据点间的距离时采用的是NBS距离。颜色节点i的密度ρ∑i定义为：

ρi=f(dij)

（22）

j

f(dì1,dijij)=íî0,dij≥dNBS

（23）

其中，dij是两颜色节点i和j之间的NBS距离，dNBS

是人眼能明显分辨色差的阈值，由表2可知该值取3。从公式（22）可以看出在计算颜色节点i的密度时，需要计算颜色节点i和其余所有颜色节点间的NBS距离。对于一幅有n个像素点的图像，计算完所有像素点的密度需要计算n(n-1)次，时间复杂度为O(n2)。而在一幅图像中存在着许多RGB值重复的像素点。为了减少计算量，在计算密度前先建立关于颜色的链表，每个链表节点中含有颜色的RGB值和该颜色的像素数。在计算密度时就无需逐像素计算，只需要先统计像素信息再逐颜色节点计算。所以密度计算的相关公式（23）相应地修改如下：

f(dìNij)=íj,dijî

0,dij≥dNBS（24）

其中Nj为颜色j的像素个数。在计算完每种颜色的密

度后，对所有的颜色节点按密度值进行降序排列。对排序完成后的颜色节点，还需要计算每个颜色节点的更高密度最小距离δi，定义如下：

2142020，56（2）ComputerEngineeringandApplications计算机工程与应用

δi=jmin:ρj>ρi

(dij)

（25）

距离δi是指比颜色节点i具有更高密度的所有颜色节点与i的最小距离。对于节点i，密度更高的颜色节点一定排在i的前面。只需从第1个节点开始到第i-1个节点结束，依次计算与节点i的NBS距离，并取NBS距离的最小值即可。对于排在第一个的颜色节点，

δi值取与其余颜色节点NBS距离的最大值，即max(dij)。

DPC算法将密度和更高密度最小距离都相对较大的点作为聚类中心。为了更直观地找到聚类中心，根据数据点绘制出决策图。决策图的横轴为密度，纵轴为更高密度最小距离。由于图像中的像素数较多，密度轴的数值会远大于距离轴的数值，更高密度最小距离的权重过小，使得决策图在选取聚类中心较为困难。因此对需要对密度进行归一化处理，密度归一化更新公式如下：

ρ=K⋅ρiwidth⋅heighti

（26）

其中，K是常数，取20，width和height为图像宽度和高度方向的像素数。对量化后的图2进行DPC聚类，得到图3所示的决策图。在决策图中，右上角的数据点同时具有较大的密度和较大的更高密度最小距离，可以作为图像的聚类中心。将这些数据点标记为相应的颜色，发现与图像主要构成色一致。

4040353530302525δ20201515101055000010102020300300ρ

600600图3决策图

4.3算法改进

决策图上除了一些很明显的密度峰外，一些数据点

具有较大的ρ和较小的δ，或者是较小的ρ和较大的δ。人工指定聚类中心容易多选或少选密度峰。为了

使聚类中心被准确找出，改进后的算法引入了优先级变量λ，

λ的定义如下：λ=ρ⋅δ

（27）

对每个颜色节点计算λ的值，并按λ的值进行降序排列。λ值越大的颜色节点，成为聚类中心的可能性越大。将所有颜色节点关于λ值的排序结果绘制成图4，并将成为聚类中心可能性较大的颜色节点标记为相应的颜色。λ值排序图的排序结果如图4所示，与图1（a）主要构成色一致。本文利用排序图，通过以下步骤自动确定出图像的聚类中心：

步骤1将λ值最大的颜色节点作为第一个聚类中心。步骤2按照λ值排序的顺序，计算下一个颜色节点与已确定为聚类中心的所有颜色节点的NBS距离。若该颜色节点与已有聚类中心的NBS距离均大于3，则添加到聚类中心，然后继续重复步骤2。若颜色节点与已有聚类中心的存在NBS距离小于等于3，聚类中心寻找结束。

2000

1000400λ3002001000

0

50

100150

200

250

序号

图4λ值排序图

5实验与结果分析5.1算法实现

整个算法实现可以分为以下几个步骤：

步骤1将图像中所有像素转换到Lab颜色空间。步骤2基于色差最小的原则，在Lab颜色空间内对图像进行颜色量化。

步骤3采用改进后的密度峰聚类方法对量化后的图像进行聚类，找到聚类中心。

步骤4将图像所有像素值替换为NBS距离最小的聚类中心的像素值，得到最终的分割图像。

5.2

图像分割效果对比

K均值聚类是彩色图像分割最常用的算法，因此实

验将随机K均值聚类结果和DPC聚类结果进行对比。K均值算法存在着聚类中心数目需要人工指定和对初

始聚类中心敏感的问题。为了使K均值聚类取得较好效果，聚类中心数目均根据人眼感知到的颜色种类来确定，聚类中心的初始值则随机生成。由图5（b）的实验结果可知，随机初始化的K均值聚类算法在进行色彩分割时，算法的图像分割性能并不稳定，很大程度上依赖于初始聚类中心的初始化好坏。图5（b）中除了第三和第四幅图获得了较为满意的彩色图像分割效果外，其余图像都存在着聚类中心偏移的问题。K均值算法虽然有时能获得理想的彩色分割效果，但需要人工指定聚类中心数目且算法的性能不稳定。图5（c）是使用本文方法的图像分割聚类结果，首先利用最小色差颜色量化算法对图像进行量化，再对量化后的图像进行DPC聚类分析。实验结果显示，改进后DPC聚类算法能自动确定聚类中心数目，且具有稳定的彩色图像分割性能，不

王鹏宇，等：基于颜色量化和密度峰聚类的彩色图像分割2020，56（2）215

（a）原图

（b）随机K均值不稳定分割结果

（c）量化后DPC聚类分割结果

图5

聚类结果分析

存在对初始聚类中心敏感的问题。表3是对图5中原图1410-1419.

和DPC分割图像的颜色种类统计，DPC分割图像的颜[4]AlbayrakS.ColorquantizationbymodifiedK-meansalgo-色种类与人眼感知的颜色种类一致，说明本文算法能有rithm[J].JournalofAppliedSciences，2001，1（4）：508-511.效减少图像的颜色种类，从而减少地毯制造过程中所需[5]ZhaoY，KarypisG，FayyadU.Hierarchicalclusteringalgo-的纱线颜色种类。

rithmsfordocumentdatasets[J].DataMining&Knowl-表3

图5中原图和DPC图像颜色种类分析

edgeDiscovery，2005，10（2）：141-168.

[6]MaX，WanW，JiaoL.Spectralclusteringensemblefor

图像序号12345imagesegmentation[C]//ACM/SIGEVOSummitonGenetic原图颜色种类12074950539684聚类后颜色种类

7

7

5

8

6

andEvolutionaryComputation，2009：415-420.

[7]王文慧，杨庚，葛炜，等.噪声不均条件下的模糊C均值聚

6结束语

类算法及应用[J].计算机工程与应用：2018，54（19）：172-178.本文针对簇绒地毯的彩色图像，提出了一种基于颜

[8]杨欣斌，孙京诰，黄道.基于蚁群聚类算法的离群挖掘方法[J].

色量化和密度峰聚类的图像分割方法。首先在人眼均计算机工程与应用，2003，39（9）：12-13.

匀感知的Lab颜色空间中基于色差最小原则对图像进[9]FordA.Colourspaceconversions[Z].London：Westminster

University，1998.

行量化。然后使用改进后的密度峰聚类DPC算法，对[10]李忠明，李忠远.基于频度严格优先的八叉树色彩量化算

地毯图案进行图像分割。实验结果表明，DPC算法在对法[J].兰州大学学报（自然科学版），2013（2）：255-259.彩色图像进行颜色分割时，能够在不影响人眼感知的前[11]吕建平，黄英.几种图像色彩量化方法的分析比较[J].计

提下有效减少图像中的颜色。与经典的K均值图像分算机应用，2002，22（5）：86-88.

割算法相比，本文的图像分割算法不需要人工指定聚类[12]GervautzM，PurgathoferW.Asimplemethodforcolor

中心数目，并且图像分割性能稳定，能够满足地毯图案quantization：octreequantization[M]//Graphicsgems.[S.l.]：有效减少颜色种类的需求。

AcademicPressProfessional，Inc，1990：287-293.

[13]王婷婷.彩色图像分割方法的研究与实现[D].山东青岛：

参考文献：

山东科技大学，2005.

[1]申铉京，潘红，陈海鹏.基于一维Otsu的多阈值医学图像

[14]RodriguezA，LaioA.Clusteringbyfastsearchandfind

分割算法[J].吉林大学学报（理学版），2016，54（2）：344-348.ofdensitypeaks[J].Science，2014，344（6191）：1492.[2]牛天瑞.基于图像区域分割的虹膜识别算法研究与实现[D].

[15]MiyaharaM，YoshidaY.Mathematicaltransformof（R，G，

沈阳：东北大学，2015.

B）colordatatomunsell（H，V，C）colordata[C]//Visual[3]钮圣虓，王盛，杨晶晶，等.完全基于边缘信息的快速图像

CommunicationsandImageProcessing’88：Thirdina分割算法[J].计算机辅助设计与图形学学报，2012，24（11）：

Series，1988：650-657.