一种基于密度峰值的颜色量化方法
【技术领域】
[0001] 本发明涉及一种颜色量化方法。特别是涉及一种基于密度峰值的颜色量化方法。
【背景技术】
[0002] 颜色量化(colorquantization,CQ)是一种降低数字彩色图像颜色种类,同时 使重构图像保持良好视觉效果的方法。真彩色图像的颜色有上千万种,这给它们的存储、 传输、显示、处理带来了很大的困难。例如,对于一幅中等分辨率的真彩色图像(分辨率 640X480, 24bit/像素)而言,它能表现出1600多万种颜色,比特数为640X480X24 = 7. 37Mb,需占约0. 9MB的存储空间。通过颜色量化减少颜色种类,能够降低图像的编码位 数,从而有益于图像的存储、传输和显示。除此之外,颜色量化还减小了图像的特征空间,从 而有益于图像识别和检索。
[0003] -般来说,颜色量化包含两步:调色板设计和图像编码。调色板设计就是找出一组 具有代表性的颜色来代表原始图像中的颜色值,这组颜色的种类数远小于原始图像。通常, 24bit的颜色能够降至8bit,甚至更低。图像编码也叫做像素映射,是把原始图像中的像素 映射为调色板中的像素。编码后图像的颜色种类减少,编码位数降低,从而达到图像压缩的 目的。
[0004] 对于颜色量化而言,调色板的设计最为重要,是决定整个系统性能的关键。根据它 的不同可以将颜色量化大致分为两类,与图像无关的方法和与图像相关的方法。与图像无 关的方法不考虑单幅图像的具体特性,设计的调色板对任何图像都是固定的。虽然这种方 法的算法复杂度低,运行速度快,但是没有考虑图像的具体特征,量化后重构效果较差。因 此,大多数的研宄都着眼于与图像相关的方法。
[0005] 与图像相关的方法的主要难点在于平衡算法复杂度和量化效果,根据所 选聚类方法的不同,可以大致分为两类,前向聚类(pre-clustering)和后向聚类 (post-clustering)。前向聚类一般基于对颜色分布的统计分析,其中重要的两大类是分 裂式方法和聚合式方法。分裂式方法首先定义一个包含所有颜色的类别,然后递归地细分 成K个类别。常见的方法有中位切分(median-cut)、八叉树(octree)、基于方差的方法 (variance-basedmethod)等。聚合式方法先定义N个只包含一个元素的类别,然后不断聚 合直至留下K个类别。
[0006] 前向聚类生成调色板是一次完成的,而后向聚类则是先定义一个初始调色板,然 后逐次迭代,改进调色板。典型的方法有k均值(k-means)、k调和平均数(k-harmonic means)、竞争学习(competitivelearning)等。和前向聚类相比,后向聚类的量化效果要 更好,因为它们涉及到了循环迭代或随机优化的步骤,但同时计算时间也有所增加。
[0007] 峰值密度是AlexRodriguez和AlessandroLaio提出的一种新的聚类方法 (Science,2014)。它的基本思想是,聚类中心点和它们的相邻点相比有更大的密度,并且和 具有更大密度的点(其他聚类中心点)之间距离相对较远。这是一种基于密度的方法,算 法的基础是样本点之间的距离。和经典的聚类方法k均值不同,它可以检测到非球形的聚 类结构,而且能自动找出合适的聚类数。除此之外,和后向聚类方法相比,峰值密度不用指 定初始值,也不用通过循环迭代来达到收敛,聚类过程更加鲁棒。
【发明内容】
[0008] 本发明所要解决的技术问题是,提供一种在调色板设计中采用峰值密度的思想, 以达到良好的量化效果,并使得整个过程更加灵活、鲁棒的基于密度峰值的颜色量化方法
[0009] 本发明所采用的技术方案是:一种基于密度峰值的颜色量化方法,包括如下步 骤:
[0010] 1)设图片包含N个像素点,计算像素点两两之间的欧氏距离dyi,」=1,2,..., N,构造距离矩阵D=
[0011] 2)设定截止距离d。,根据距离矩阵D,计算各个像素点的局部密度pi:
[0013] 其中,如果dij-d^O,则x(dij-d。)= 1 ;否贝1」,x(dij-d。)= 0 ;这样计算得到的每 个像素点的局部密度Pi,也就是这个像素点所在的截止距离d。范围之内的像素点的数目; [0014] 3)根据各像素点的局部密度Pp对于每一个像素点,找出所有局部密度比它大的 像素点,再根据距离矩阵D,找出所述像素点和局部密度比它大的像素点之间的欧氏距离, 并定义其中的最小欧氏距离为\,即
[0015] 4)计算每一像素点的参数yi=piS^并将所有参数yjf序排列,选择前K个 参数Yi所对应的像素点作为聚类中心点,其中K是大于1的整数;
[0016] 5)对于第K个像素点之后的每个像素点,分别根据步骤3)的计算结果找出最小 欧式距离所对应的像素点,并根据所述像素点的最小欧式距离将所述像素点归类于步骤 4)中所述的聚类中心点中所对应的那一类,然后用每一类的像素平均值代表该类所有像素 值,完成颜色量化。
[0017] 步骤2)所述的截止距离d。是将步骤1)中获得的欧氏距离由小至大排列,取排列 中第NX0. 02个距离为截止距离d。,其中,N为像素点的个数。
[0018] 本发明的一种基于密度峰值的颜色量化方法,具有以下特点:
[0019] (1)鲁棒性:峰值密度属于前向聚类方法,一次就可以完成。而k-means等后向聚 类方法,需要先设定初始值,然后迭代直至收敛,从而出现因为初始点选择不当而陷入局部 最优的情况。
[0020] (2)有效性:通过与其他颜色量化方法相比较,本发明表现出良好的性能,能够有 效而鲁棒地进行颜色量化。
[0021] (3)灵活性:峰值密度既能根据实际要求人为指定聚类数,又能根据样本具体情 况,由y差值自动确定,从而能够灵活地满足不同需求。
【附图说明】
[0022] 图1是像素点的分布图,像素点的标号按密度递减排列;
[0023] 图2是图1所对应的决策图。
【具体实施方式】
[0024] 下面结合实施例和附图对本发明的一种基于密度峰值的颜色量化方法做出详细 说明。
[0025] 本发明的一种基于密度峰值的颜色量化方法,
采用密度峰值(densitypeaks)聚 类方法,将彩色图像的像素值聚类,用各类别像素的平均值表示该类原始像素值,实现颜色 量化,从而压缩图像大小,减小图像特征空间。本发明是根据以下假设找出聚类中心点:
[0026] (1)聚类中心点的密度比周围点的密度要高;
[0027] (2)聚类中心点与密度更高的点之间的距离较远。
[0028] 本发明的一种基于密度峰值的颜色量化方法,包括如下步骤:
[0029] 1)设图片包含N个像素点,计算像素点两两之间的欧氏距离dyi,」=1,2,..., N,构造距离矩阵D=
[0030] 2)设定截止距离d。,所述的截止距离d。是将步骤1)中获得的欧氏距离由小至大 排列,取排列中第NX0. 02个距离为截止距离d。,其中,N为像素点的个数,根据距离矩阵D, 计算
[0031] 各个像素点的局部密度Pi:
[0033] 其中,如果扎-(1。〈0,则x(dij-d。)=1 ;否则,x(dij-d。)=0 ;这样计算得到的每个 像素点的局部密度Pi,也就是这个像素点所在的截止距离d。范围之内的像素点的数目;由 于对算法结果产生影响的只是样本点局部密度Pi的相对大小,所以当数据集较大时,d。的 取值对最终结果影响较小。而当数据集较小时,可以采用幂指数核(exponentialkernel) 来减小误差。
[0034] 3)根据各像素点的局部密度Pi,对于每一个像素点,找出所有局部密度比它大 的像素点,再根据距离矩阵D,找出所述像素点和局部密度比它大的像素点之间的欧氏距 离,并定义其中的最小欧氏距离为\,即
[0035] 4)计算每一像素点的参数yi=PiS^并将所有参数y 序排列,选择前K个 参数Yi所对应的像素点作为聚类中心点,其中K是大于1的整数;
[0036] 如果用P和S作为描述样本点的参数,聚类中心就是p和S都很大的点。为 了方便演示,假设像素值是一个二维向量,如图1所示,图1是像素点的分布图,像素点的标 号按密度递减排列;图2是图1对应的决策图(decisiongraph)。从决策图可以看出,点 1和10有很高的P和S,所以将它们定为聚类中心点。而点26、27、28虽然有较高的S, 但是局部密度P非常小,这是因为它们是离群点。
[0037] 5)对于第K个像素点之后的每个像素点,分别根据步骤3)的计算结果找出最小 欧式距离所对应的像素点,并根据所述像素点的最小欧式距离将所述像素点归类于步骤 4)中所述的聚类中心点中所对应的那一类,然后用每一类的像素平均值代表该类所有像素 值,完成颜色量化。可以看出,这一聚类过程不需要迭代,一次便可完成。
[0038] 将峰值密度聚类方法用于颜色量化时,需要将像素值看作三维空间(RGB、HSV等) 中的点,然后用上述方法计算各点的P和8,得到决策图。因为聚类中心点是p和S同 时较大的点,本发明引入参数Yi= P并将Y降序排列。然后根据实际要求,选择前 K个点作为聚类中心点;若对聚类数没有具体要求,也可以根据前后Y之间的差值自动确 定聚类数,因为聚类中心之间的Y差值要明显大于普通的点。
[0039]确定聚类中心后,就要把剩余各个样本点分到各自所属的类别。聚类规则如前 所述,各点所属类别与局部密度P更高且距离最近的点所在的那一类相同。同一类的像 素值可以用同一种颜色来表示。为了使重构图像与原始图像间的均方误差(meansquare error,MSE)最小,将这种颜色定为同一类所有像素的平均值。这样,一幅图像的颜色种类 就被压缩至K,从而达到量化的效果。
【主权项】
1. 一种基于密度峰值的颜色量化方法,其特征在于,包括如下步骤: 1) 设图片包含N个像素点,计算像素点两两之间的欧氏距离du,i,j = 1,2,...,N,构 造距离矩阵D = [φ」]ΝΧΝ; 2) 设定截止距离d。,根据距离矩阵D,计算各个像素点的局部密度Pi:(1) 其中,如果屯-(1。〈0,则X (Clij-CQ = 1 ;否则,X (Clij-CQ = O ;这样计算得到的每个像 素点的局部密度Pi,也就是这个像素点所在的截止距离d。范围之内的像素点的数目; 3) 根据各像素点的局部密度Pi,对于每一个像素点,找出所有局部密度比它大的像素 点,再根据距离矩阵D,找出所述像素点和局部密度比它大的像素点之间的欧氏距离,并定 义其中的最小欧氏距离为S i,即4 = . J ? 4) 计算每一像素点的参数Yi= P Ji,并将所有参数Yi降序排列,选择前K个参数 γ #对应的像素点作为聚类中心点,其中K是大于1的整数; 5) 对于第K个像素点之后的每个像素点,分别根据步骤3)的计算结果找出最小欧式距 离所对应的像素点,并根据所述像素点的最小欧式距离将所述像素点归类于步骤4)中所 述的聚类中心点中所对应的那一类,然后用每一类的像素平均值代表该类所有像素值,完 成颜色量化。2. 根据权利要求1所述的一种基于密度峰值的颜色量化方法,其特征在于,步骤2)所 述的截止距离d。是将步骤1)中获得的欧氏距离由小至大排列,取排列中第ΝΧΟ. 02个距 离为截止距离d。,其中,N为像素点的个数。
【专利摘要】一种基于密度峰值的颜色量化方法:设图片包含N个像素点,计算像素点两两之间的欧氏距离dij,构造距离矩阵D;设定截止距离dc,根据距离矩阵D,计算各个像素点的局部密度ρi;对于每一个像素点,找出所有局部密度比它大的像素点,再根据距离矩阵D,找出所述像素点和局部密度比它大的像素点之间的欧氏距离,并定义最小欧氏距离为δi;计算每一像素点的参数γi=ρiδi,并将所有参数γi降序排列,选择前K个参数γi所对应的像素点作为聚类中心点;对于第K个像素点之后的每个像素点,归类于聚类中心点中所对应的那一类,然后用每一类的像素平均值代表该类所有像素值,完成颜色量化。本发明表现出良好的性能,能够有效而鲁棒地进行颜色量化,能够灵活地满足不同需求。
【IPC分类】G06T7/40
【公开号】CN104899899
【申请号】CN201510324808
【发明人】冀中, 谢于中, 庞彦伟
【申请人】天津大学
【公开日】2015年9月9日
【申请日】2015年6月12日