着色算法

2024-08-26

着色算法（精选6篇）

着色算法篇1

摘要：介绍了一种简单的灰度图像着色算法,它通过引入优化约束方程,尽可能地使着色后的图像在相应的色度空间内,其色度值的全局变化最小。在实际应用中,用户只要预先指定某些像素点的颜色,利用该算法就可以达到较好的主观着色效果。峰值信噪比的分析结果显示,在仅仅指定0.1%像素的颜色时,利用该算法着色后图像的平均峰值信噪比已经在26 dB以上。而且与先前的着色算法比较,该算法在使用更低的采样率下,着色后图像有更高的峰值信噪比,也即该算法优化估计的结果与原始图像的误差更小。

关键词：图像着色,梯度,优化,伪彩色,色彩空间

0 引言

图像的着色技术是对灰度图像或黑白电影增加色彩。它是在1970年由Wilson Markle提出的,最早用于对阿波罗计划中拍到的月球照片的着色[1]。现在该技术主要应用在影视娱乐中对黑白老照片或早期黑白电影的着色,有时也用在彩色图像编辑(局部色彩变化)或图像压缩方面。而且由于人眼对彩色图像的分辨率要高于灰度图像,该技术也经常用于对各类科学图像如:核磁共振图像[2]、声呐成像[3]等的图像增强处理。

迄今为止,已有不少文献对图像的着色技术进行了研究。传统的着色技术一般称之为伪彩色(pseudo color)技术。伪彩色处理的基本思想是采用某种映射关系,将像素灰度值映射到色彩值,具体可以用以下公式表示

[r,g,b] = [fr(y),fg(y),fb(y)] (1)

式中:y表示某像素点的亮度值;(r,g,b)表示通过映射关系该亮度值所对应的色彩值;fr,fg,fb分别表示由亮度值到对应的红、绿、蓝三分量的映射函数。

近年来发展起来着色技术主要分为基于色彩传递的方法和基于优化的方法这两大类。在基于色彩传递的方法中,用户需要额外提供一幅与即将着色的灰度图像比较相似的彩色图像。该方法一般采用灰度图像的局部纹理信息,在彩色图像上搜索相似的区域,然后将该区域对应的色彩值传递到灰度图像上,完成对灰度图像的着色。该算法最早是由Welsh等人[4]提出的,其借鉴了Hertzmann 等人[5]图像类比的理念以及Reinhard等人[6]提出的在不同风格的彩色图像间进行色彩传递的技术。其后Blasi等人[7]改进了该算法,有效地加速了匹配的搜索过程。在Wang[8]等人的工作中,又通过使用用户定义的色彩变化曲线,提出了针对图像序列的色彩传递技术。整体而言,该算法适合对纹理丰富且色彩多变的图像着色。但是,由于纹理匹配的复杂性,算法自动搜索的准确度难以控制,这就需要人为地在灰度图像和选择的彩色图像间指定对应的窗口,增加了用户的工作量。

在基于优化的方法中,一般需要在即将着色的灰度图像上预先指定某些点的色彩值,以之为初值进行优化处理[9,10,11,12]。本文采用的方法即属于该类。其中经典的算法是Levin等人[10]提出的,其主要通过假设在局部时空邻域内亮度相似的像素点的色彩值也相似,构造相应的代价函数,通过优化求解该代价函数完成图像或视频的着色。还有一些人从其他角度提出了相应的优化着色算法。如:Horiuchi等人[1]通过定义像素点与其邻域间的RGB差异距离,采用松弛算法的计算,使所有像素的差异距离累加和最小; Noda等人[12]采用对彩色图像做马尔科夫随机场建模,通过贝叶斯后验概率最优化估计灰度图像对应的色彩值。李志永等人提出像素不平度描述连接两像素的最平坦路径的坎坷度,并以此利用动态规划算法,确定最佳的像素着色颜色,并进行颜色混合。

本文主要利用图像色彩在局部邻域窗口内连续平滑变化的特点,假设着色后的图像在色度空间内的总梯度和最小。若用户事先已经在灰度图像上指定一些像素点的色彩值,则通过简单的优化处理,就可以完成图像的着色问题。该算法简单方便,易于实现。实验结果显示利用本文算法着色后的图像与原始彩色图像对比,在仅有0.1%像素的色彩已知的情况下,其平均峰值信噪比已经在26 dB以上。而且通过与Horiuchi等人[1]算法处理结果的比较,可知本文算法需要指定色彩的像素点较少,着色图像的峰值信噪比较高。

色彩空间在数字图像处理中,存在多种类型的色彩空间。通常最为常用的是RGB色彩空间,即其中的每个像素都由红(R)、绿(G)、蓝(B)三基色分量表示。但是灰度图像中只有亮度分量,为了着色处理的方便,本文采用先在YUV色彩空间下,计算U,V空间内待定的色彩值,然后再将YUV色彩空间转变到RGB色彩空间。一般RGB到YUV的变换关系以及其逆转换关系可分别由式(2)和(3)所示

undefined

由以上公式可知,从灰度图像中某个像素的灰度值其对应的色彩值恰好位于RGB空间内由该灰度值所确定的某个平面片上,该平面片的方程为

0.299R + 0.587G + 0.144B-Y = 0 (4)

式中:Y 为该像素的亮度值;R,G,B为其对应的色彩分量值,且R,G,B∈[0,255]。

3 着色问题的优化求解

从色度空间的分析可知,灰度图像的着色问题其实是个欠约束的问题。所以通常情况下,求解该问题都需要引入一些相对合理的假设条件。如:Welsh等人[4]假设源图像和目标图像间纹理相似的区域其色彩值也相似;Levin等人[10]假设在某个像素点的邻域内亮度相似的像素其色彩值也相似。本文是从图像梯度域考虑该问题,假设待定的色彩值在保持亮度约束的条件下,使得图像在U,V空间内对应的色度变化最小。也就是说,使着色后的图像在U,V空间内尽可能地平滑。可由如下方程表示

undefined

式中:undefined为图像的梯度算子;Q是所有颜色值待定的像素点的集合;U,V分别表示这些像素在U,V空间内对应的色度值。

由Euler-Lagrange方程可知,可以通过解如下方程得到式(5)～(6)的优化解

ΔU=0 (7)

ΔV=0 (8)

式中:Δ为图像的拉普拉斯梯度算子。

通常在离散情况下,在四邻域和八邻域下计算图像的拉普拉斯梯度的模板如图1所示。考虑到引入较多邻域点的情况下可能造成着色图像的色度分量过度平滑,本文采用四领域的模版。实验结果也证实采用四邻域下计算的着色图像,其平均峰值信噪比要略高于八邻域下的计算所得,如图2所示。

具体的求解过程如下:

若灰度图像除了给定色度值的像素点外,还有N个像素点的色度未知。假设其中第i个像素点在U空间对应的色度分量值为ui,则所有这些待定的色度值构成N×1维列矢量U。

若第 i个像素点的邻域各像素点的色度值均未知,且其在列矢量U中对应的索引分别为k,r,s,t,则

uk+ur+us+ut-4ui=0 (9)

若已知其四邻域内像素点k的色度值为uk0,则

ur+us+ut-4ui=-uk0 (10)

以此类推,最后联立这N个色度值未知的像素点所构成的方程,有

AU=b (11)

式中:A 是相应的系数矩阵,它是一个N×N维的稀疏矩阵,其第i 行元素只在第i 列以及其四邻域内色度值未知点处有值,其他元素值均未零;b 是一个N×1维列矢量,由N个方程的右端相联立而成。

由以上分析可知,det A≠0。根据Cramer法则,矩阵方程(11)有一组唯一的解。求解矩阵方程,即可得到所有色彩值未知的像素点在U空间内的估计值。同理,可以得到V空间内的估计值。

最后,通过YUV色彩空间到RGB色彩空间变换,即可得到对原灰度图像着色后的彩色图像。

3 结果分析

本文的算法需要预先指定一些像素点的色彩值为初始值,实际应用中可以由用户指定,然后利用本文算法估计着色后的图像,效果如图3所示。

在实验过程中为了单纯地检测算法的精度,以一些彩色图像作为测试图像,从这些原始的彩色图像中均匀地采样一些像素点,以其色彩值作为已知值。采样像素点的个数与图像中总像素点的比值称之为采样率。而且,为了客观地衡量着色后的图像与原始图像间的误差,实验采用了峰值信噪比PSNR的这一指标。令

undefined

则

PSNR=10lg(2552/σundefined) (13)

式中,m,n分别为图像的高度和宽度;x(i,j)为原始图像在(i,j)处的色彩值;undefined为着色后图像在(i,j)处的色彩值。

实验中各类图像在不同采样率时,其平均峰值信噪比的变化曲线如图2所示。当采样率越高,也即颜色已知的像素点数越多,着色的效果越好,但即使在采样率为0.1%时本文算法的平均峰值信噪比也在26 dB以上。

为了便于与其他算法比较结果,实验中采用SIDBA标准图像库中的图像作测试,其中各图的峰值信噪比随采样率的变化曲线如图4所示。其中采样率较低时,着色图像的PSNR有些波动,这主要由于均匀采样时,在不同采样率下,各采样点的位置不同。而当采样点很少时,该因素就显得相当突出,从而影响了最后的着色效果。比较Horiuchi等人[1]的结果:其算法在采样率为1%～7%时,Lena的峰值信噪比为20～28 dB,Milkdrop的峰值信噪比为20～27 dB。而本文的算法在采样率为1%～7%时,Lena的峰值信噪比为29～34 dB;Milkdrop的峰值信噪比为26～31 dB。

图5给出了本文着色算法在采样率1%及0.5%下,从原始灰度图像计算得到的R,G,B三分量图和原始彩色图像的R,G,B三分量图之间的比较,从中可以清楚地看到本文算法可以达到较好的着色效果。表1具体显示了本文着色算法计算的图像各个像素点处R,G,B三分量值和原始图像的R,G,B三分量值之间的平均相对误差。

4 结束语

图像的着色问题在改善图像的人眼分辨率和提高图像画面的美观程度,以及彩色图像压缩等方面都有广泛的使用。由于图像的着色问题实质上是由单独的亮度分量去确定合适的RGB三色分量,这是一个欠约束的问题。本文利用图像各分量在邻域内的渐变性,假设待定的色彩值使得图像在各色度分量内的全局变化最小,从而引入解决着色问题的优化方程。最后,保持图像亮度分量不变,通过色彩空间变换,就可以得到着色好的彩色图像。

实验结果表明该方法在已知色彩的像素点数较少的情况下也可以比较好地完成图像的着色问题。实验中各类图像在采样率为0.1%时平均峰值信噪比达到26 dB以上。而且通过与Horiuchi等人的着色结果比较可知,在使用更低的采样率下,使用本文算法着色后图像有更高的峰值信噪比,也即本文算法优化估计的结果与原始图像的误差更小。

着色算法篇2

考试时间安排属于典型的时间表问题 (Time Table Problem, 简称TTP) , 本文对时间表问题的论述就是针对大学考试时间表问题的。为提高考试时间安排的科学性和合理性, 本文设计并实现一种新的图着色方法来解决考试时间安排问题, 并使得算法满足以下需要:

(1) 通过合理安排考试时间, 使冲突人数减少到最低。

(2) 多数学生的考试时间间隔尽量大, 以保证学生有足够的休息时间。

1问题的描述

大学考试时间表问题即在一些有限的时间段中安排考试, 同时要求避免冲突并且满足一些约束条件, 本文所要解决的考试时间安排有以下要求:

硬约束条件:

(1) 考试时间段固定, 一般是每天4个考试时间段。

(2) 集中考试时间, 全校所有专业的考试都安排在一周之内。

(3) 所有学生的正考科目 (当学期所开设课程) 不允许有冲突。

(4) 考场有限, 监考老师有限, 这两者属于一体要求。

软约束条件:

(1) 各个时间段安排的考试科目数目尽量均衡。

(2) 同一年级的学生参加的考试课程在时间安排上应有一定的间隔。

(3) 使得补考学生出现考试时间冲突的数目降到最低。

2算法的总体设计思想

本文所研究的图着色类型是给定颜色数m, 要求对图的顶点或边进行着色。

m着色:给定一个无向连通图G和m 种不同的颜色, 用这些颜色为图G的各顶点着色, 每个顶点着一种颜色。是否有一种着色法, 使G中每条边的两个顶点着不同颜色, 这个问题是图的m 可着色判定问题。若一个图可用m种颜色着色, 求一个图的m着色方案, 为m 可着色优化问题。m可着色判定问题是NP难度的问题。

在求解时间表问题时, 要求在一定数目的时间段内完成所有活动, 使有冲突的活动被安排在不同的时间段中。与图着色问题相关联, 将图中的顶点看作活动, 有冲突的活动 (顶点) 之间用一条边相连, 相应的问题求解转化为有连边的节点分配不同的颜色, 使得所用的颜色数目最少。

2.1建立图着色模型

在考试时间安排的问题中共有n门课程, 要安排在m个时段中进行考试, 每门课程的考试人数不等, 构造图G, 包含n个顶点, 每个顶点表示一门课程。每个顶点的权值表示报考该顶点所代表课程的总人数, 边上的权值表示同时报考该边相连的两个顶点所表示课程的学生人数。

在构造无向图时, 先选择一个专业, 将该专业的各个年级在本学期所学的课程分别提取出来, 形成一个一个的无向完全子图 (也称为团) , 并根据学生人数形成每个团中顶点的权值。

考试问题描述:假设某系有三个年级同时进行期末考试, 假设不考虑补考和公共课的情况。一年级共有50人, 需要考试的科目有ABCD四门, 这里我们称为一年级的正考科目为ABCD四门, 二年级共有60人, 正考科目为EFGH四门, 三年级共40人, 正考科目为I和J两门。其中二年级中有15人需要补考课程C, 又有5人需要补考课程A, 三年级的考生中有8人需补考B课, 那么二年级中有15人不仅要参加课程E、F、G、H的考试还要参加课程C的考试, 就需要将C分别和团中的顶点E、F、G、H连接起来, 并将权值15加到对应的边上。其他补考的连接方法以及权值设置同上, 这样就使得原来孤立的各个团之间建立起联系, 如图1所示:

针对具体考试问题, 本文中我们给出一个自定义的概念——原始团, 后文中提到的原始团都是指:每个年级的正考科目所组成的一个团。

这样, 图1中共有ACEFGH, ABCD, IJB三个团, 其中最大团ACEFGH是在原始团EFGH (二年级正考科目) 的基础上, 因为有个别人需要补考其他年级的课程AC, 连接后形成的, 这就使得A和C都不能和EFGH之一分在同一个时间段。而团IJB, 是在原始团IJ (三年级正考科目) 的基础上, 因为有个别人需要补考其他年级课程B连接后形成的, 显然补考现象的出现加大了考试课程时间安排的复杂度。对于公共课和补考情况大同小异, 这里不再具体阐述。

图1中每个顶点的权值表示报考该顶点课程的总人数, 边上的权值表示同时报考该边两个顶点所表示课程的学生人数。

一般来说, 在考试安排中, 所提供的考试时间段不应少于最大原始团的顶点个数。应首先安排正考科目, 使得科目之间的考试时间尽量有一定的间隔, 在安排补考科目 (对其他人也是正考科目) 时, 既要考虑不产生冲突, 也要考虑与已经安排好的时间段之间有一定的间隔。

2.2设计思路

在算法设计上, 模拟人工安排考试时间的方式, 先安排一些特殊课程, 如公共课, 因为参加公共课考试的人数较多, 所以一般将公共课考试的时间选在某个上午时间段中;再按照专业年级来划分课程, 将正考课程最多的一个年级的各门考试分散到各个时间段中, 注意产生间隔, 后面依次安排各个年级的考试课程, 既要产生一定间隔又要防止产生冲突。

3算法的设计

3.1算法的初始化

(1) 构造边集数组Gset={{ v11, v21, p1}, { v12, v22, p2}, { v13, v23, p3}, …, { v1k, v2k, pk}} (其中k为图中边的总数) 用来存放图, 数组中每个单元包括三个域, 分别为顶点v1、顶点v2、顶点v1和v2之间边的权值p。

(2) 构造G'= (T', V') 其中T'和V'分别表示已着色的团集合和点集合, G = (T, V) 用来表示还没有着色的团集和点集。

(3) 构造数组Color = ( c1 , c2 , ..., cm ) 初始值为0, 表示每种颜色已着色顶点的权值之和, m为可提供的颜色总数。

(4) 对于每个团都构造一个数组c[m+1]为布尔型, 初始值为false, c[i] (其中i>=1&&i<=m) 的值为false表示该颜色i可用, true表示该颜色i不可用。

3.2算法的设计

该算法是基于团集的图着色算法, 算法描述为:

(1) 首先令已着色的团集合和点集合分别为空, 即T'=θ, V'=θ。未着色的团集合T={ T1, T2, T3, ……, Tk }, k为图中团的个数, 点集合V={V1, V2, V3, ……, Vn}, n为图中顶点的总数。

(2) 找出T中包含顶点最多的一个团Ti 即最大团, 计算出该最大团中顶点个数vnum, 如果m>=vnum, 即所给颜色数不少于最大团的顶点个数, 则将该最大团Ti的顶点集合Vi着为不同的颜色;否则, 即所给颜色数少于最大团的顶点个数, 也就是颜色数不够用的情况, 这时着色过程中必然会产生冲突, 那么找出包含最大原始团的那个团Tj, 将该最大团Tj的顶点集合Vj着为不同的颜色。

对最大团中顶点着色后计算V'=Vi, V=V-Vi, T=T-{Ti}, T'={Ti}, Color=Color+u, 即将已着色的团和顶点加入到G'= (T', V') 中, 并从G= (T, V) 中删除, 同时更新数组C。

(3) 对T中每一个团计算ai=|{u|u∈Ti, u∉V}| , 即计算T中每个团尚未着色顶点的个数ai。若ai = 0, 则该团中的所有点都已经着色, 运行T=T-{Ti}, T'=T'∪{Ti} , 若ai=|Ti|, 则该团中的所有点都尚未着色, 说明V'与V是不相连的, 返回第2步。若ai <|Ti|, 则该团中有部分点已经着色, 找出一个ai值最小的团Ti。

(4) 对于Ti中的顶点u, 若u∈V, 那么必有u∉V', 在V'中遍历该团已着色点的颜色值, 对应将c[colorsize+1]中的值设为true, 如果可用颜色数多于未着色的顶点数则在选择颜色数的时候也要尽量产生一定的间隔;如果可用颜色数等于未着色的顶点数, 则依次将这些顶点着色为所剩颜色数;如果可用颜色数小于未着色的顶点数, 即颜色不够用的情况, 则优先安排顶点权值大的顶点着色, 对于当前一个权值较小的顶点v, 依次和已安排着色的顶点之间的边权值进行比较, 将v着色为与之相连的边权值最小的那个顶点颜色。

对u着色后运行V=V-{u}, V'=V'∪{u}, 对T中所有顶点着色结束后运行T=T-{Ti}, T'=T'∪{Ti}。Color=Color+u。

(5) 判断T=ϕ吗, 如果为空则计算结束返回着色结果G, 否则返回第3步。

3.3考试时间间隔的优化

算法中的颜色值与实际的时间段是对应的, 为使同一年级甚至是同一个学生所参考的课程在时间安排上有所间隔, 就必须在着色时注意颜色的选取。因此在给同一个团中的每个顶点进行着色时, 按照一定的算法来完成。

当一个团中的所有顶点都还没有着色时, 则所提供的颜色数m对于当前团可能是全部可用, 也可能是部分可用。

如果m种颜色全部可用, 则对于团中顶点着色时的可选空间很大, 这时应尽量使得该团中的顶点着色均衡分布, 即产生一定的间隔。产生间隔的方法是:

(1) 当前总颜色数为m, 团中共有vnum个顶点, 首先令团中第一个顶点着色为1, 记为k=1, 令vnum--;

(2) 判断当前团中是否还有未着色点, 如果有就转到第3步, 如果没有就停止;

(3) 计算k+= (m-k) /vnum;使得当前顶点着色为k。令vnum--;转到第2步。

如:所提供的颜色数目总数为m=16, 1-16为16种颜色代号, 如图2所示, 当前待着色团为Ti={ABCDE}, 根据算法, 将Ti中的顶点ABCDE分别着色为:

A——1, B——4, C——8, D——12, E——16, 如图3所示:

这样就使得团Ti中的顶点均衡分布在整个区间中, 也就相当于将课程均匀分布在考试时间段中了。

如果m种颜色只有部分可用, 则对于团中顶点着色时的可选空间相对减少, 这时也要尽量使得该团中的顶点着色均衡分布, 但不能用以上的方法来实现, 所以设计一个算法, 该算法每次都能够找到最大可用区间, 将当前顶点放到该区间中。

最大可用区间的查找方法:

(1) 初始化颜色值为i=1, 可用颜色区间中包含的颜色总数为max=0

(2) 如果i小于m+1, 则转到第3步, 否则停止。

(3) 初始化当前可用颜色区间中包含的颜色总数为count=0

(4) 当前的颜色i是否可用?如果能用则转到第5步;如果不能用则i=i+1, 转到第2步。

(5) 执行count++, 令j=i+1, j为颜色i的下一个颜色

(6) 如果j小于m+1, 则转到第7步, 否则停止。

(7) 判断当前颜色j可用吗?如果可用则令count++, j++, 转到第6步, 如果不可用则转到第8步

(8) 判断count>max吗?如果是, 则令max=count, 用end=j-1, beg=end-count+1, 否则另i=i+count并转到第2步。

算法结束后用beg和end记住的分别是区间的起始位置和结束位置。

如:当前需着色团为Tj=BDFGH, 因BD在团Ti中已经被着色, 所以颜色4和颜色12不能用, 如图4所示:

这就使得当前可用颜色共有3个可用区间, 分别是[1,2,3]、[5,6,7]和[13-16], 通过以上算法能够找到最大可用区间为[5,6,7], 那么将把Tj的顶点F放在该区间中, 放置的位置由beg+ (end-beg+1) /2的值来决定。

对F着色后, 着色表如图5所示:

对G着色后, 着色表如图6所示:

对H着色后, 着色表如图7所示:

这样也能够保证团Tj中的顶点均衡分布在整个区间中。

3.4算法改进

以上算法在考试时间安排上还考虑到考场场地的限制问题。如果考场有限, 一个考场只能容纳30人, 而某一场考试时间安排的考试人数有可能会超出了考场限制, 解决的办法是在算法中引入一个阈值, 该阈值就是所有考场最多可容纳人数。构造方法check ( c, u) 为布尔性, 功能是如果u着色为c, 将u的权值加到数组Color[c]中后, 如果Color[c]的值低于阈值就返回true, 表示u可以着色为c;否则返回false, 表示u不可着色为c。

这样就可以防止某一场安排人数超标的情况, 同时, 可将阈值设的小一些, 保证每个时间段的考试人数基本持平, 可见阈值的引入也可做到协调监考人员工作量的作用。

4算法测试

该算法的测试工作是通过一个基于该算法实现的考试时间安排系统完成的。测试需要输入的主要数据包括专业信息、课程信息、学生报考信息、时间段、每场考试最多容纳的人数。下面是对6个专业、116门课程、647个学生数据分类进行测试。

根据前面讲述的算法, 在班级属性中加上一个clash值, 表示此次安排方案产生的冲突系数, 各课之间的时间间隔为0、1、2、3、4、大于4时该项冲突系数分别累加100000、20、5、2、1、0。计算clash值, clash的值越小, 则同一班级的考试课程之间的时间间隔越大, 由此可通过判断比较clash值得到较为合理的时间安排方案。

下面是不同时间段进行考试时间安排的比较, 如表1所示:

可见, 在考场可容纳人数不变的情况下, 时间段越多, 各个年级的考试科目所在的时间段之间的间隔越大。管理人员可通过以上的数据表, 分析找出合理的时间段安排, 既能保证不产生冲突, 也能在集中的时间内完成所有考试。但是当考场可容纳人数较小时, 必须通过增加考试时间段来解决考试时间安排问题。

5结束语

由于算法在设计上考虑到冲突问题, 在安排时间时, 充分利用顶点权值、边权值的判断, 可以使得发生冲突的考试人数降到最低, 同时使得多数学生的考试时间间隔尽量大。而由于报考学生人数庞大、报补考科目种类繁多, 手工安排不可能解决这一问题。

以该算法为核心设计的考试时间管理系统不但能将教务人员从繁重的考务工作中解放出来, 还能自动形成科学、合理的考试安排时间, 对于促进办公自动化的发展具有重要意义。

参考文献

[1]Tim B.Cooper, Jeffrey H.Kingston.The Complexity of Timetable Construction Problems.Proc.ICPTAT95, 1995, 183～295

[2]MW Carter, G Laporte, and Chinneck.A general examination scheduling system.INTERFACES, May-June1994, 24 (3) :109～120

[3]Fred Buckley, Marty Lewinter著.李慧霸, 王凤芹译.图论简明教程.清华大学出版社, 2004.117～119

[4]王晓东编著.算法设计与分析.北京:清华大学出版社, 2003.

[5]陈卫东.求图着色问题的新算法.微计算机应用, 2004, 25 (4) :

[6]程泉, 朱大铭.用图的着色方法求解考试时间安排问题.计算机应用, 2005, 12

着色算法篇3

BWC着色问题主要应用在化学工业试样管理中。化学试剂大多数具有一定的毒性和危险性, 对化学试剂的管理, 不仅是保障分析结果质量的需要, 也是确保人民生命财产安全的需要。化学试剂的管理应根据实际的毒性、易燃性、腐蚀性和潮解性等不同的特点, 以不同的方式归类妥善管理。例如化学物品B有b个试样, 化学物品W有w个试样, 被存放在n≥b+w个可行性位置。根据化学物品的特性不同, 考虑到安全存放, 如何对这些化学物品进行存放, 以保证同一片区域不能包含不同化学性质的物品, 即是否存在如此的保存方案。将此问题用图的着色问题描述, 即构造一个图G, 每一个存放物品的地方代表图的一个顶点, 存放不同化学物品的两个顶点之间不能有边相连即BWC着色问题。该问题的其它应用领域可参考文献[1]。

1 BWC问题研究进展

BWC着色问题最早被Berge[2]提出:给定一个正整数n和b≤n2, 将b个黑皇后和w个白皇后摆放在n×n的棋盘上, 在黑皇后和白皇后不能直接相互攻击的情况下确保白皇后数最大。BWC着色问题被证明是一个NP-完全问题[2], 在该文献中, 作者提出了一个求解树的BWC问题的算法, 其复杂度为O (n3) 。在文献[3]中提出了树的BWC问题复杂度为O (n2lg3n) 的算法, 讨论了几种求解BWC问题的通用启发式算法, 尤其是禁忌搜索算法。Kobler等在文献[4]中给出了一种固定k的k-树多项式算法。Yahalom对Berge[2]提出来的“黑白皇后布局问题”进行改造, 用“军”替代“皇后”, 提出了一个亚线性算法。在文献[1]中研究了一个类似的用“军”替代“皇后”的黑白皇后布局问题, 针对环形图及非环形图提出了一个明确的最优化布局方案。在文献[5]中, 提出了针对平面图的线性时间近似算法。在文献[6]中, 研究了求解BWC问题的禁忌搜索启发式算法, 提出了两个不同的版本, 通过对几种典型图进行测试, 得到了不错的值。同时与线性算法、二次规划算法、模拟退火算法、随机爬山算法以及贪心随机自适应搜索算法等进行了比较。

BWC最优化问题, 即给定无向图G及着黑色顶点数b, 找出一种最优化着色方案, 使得与所有黑色顶点不相连接的着白色顶点数最大。显然最优化问题只依赖黑点个数。举例来说, 图1描述了一个最优化BWC着色方案, B=3, W=4。如果将右边着白色顶点中的任意三个着黑, 就会得到一个B=3, W=3的BWC着色方案, 显然这不是最优的着色方案。

2混合启发式算法BTLSBWC设计

2.1常用智能算法思想

2.1.1启发式算法基本思想

启发式算法步骤如下, 首先随机产生初始解S0, 然后在S0的邻域N (S0) 中以某种带有导向随机方式选择一个解作为下一个解, 通过某种适应度函数决定解的优劣程度, 每一轮循环更新一次问题的解, 经过不断的迭代直到得到满意的解。为了避免迂回搜索, 可以采取禁忌搜索策略, 将最近搜索过的顶点放入队列将其禁忌, 使之不立刻被操作, 当进行了一定步数的迭代之后, 将禁忌的顶点解禁。

2.1.2禁忌搜索算法

禁忌搜索思想是一种模拟人思维的智能搜索算法[7]。它采用一种灵活的“记忆”技术, 即对历史进行记录和选择, 指导下一步的搜索方向。另外, 为了尽可能不错过产生最优解的“移动”, TS还采用“释放准则”的策略[8]。在禁忌搜索过程中, 禁忌表的大小选择、是否固定需要针对不同问题仔细斟酌和考虑。

2.1.3局部搜索算法

局部搜索算法[9,10]是一类可以有效解决优化问题的通用算法。它的基本原理是在邻近解中迭代, 使目标函数逐步优化, 直至不能在优化为止。局部搜索算法用法灵活, 适用面广, 能求解各类的组合优化问题, 并能在有限时间内给出较好的优化解。局部搜索算法步骤:问题的解空间表示为S, 局部搜索算法从一个初始解i∈S开始, 然后根据具体问题定义邻域结构, 在当前解i的邻域Si内按一定规则找到新解, 再用新解取代i成为当前解, 判断是否满足算法结束条件, 如不满足再对当前解继续使用算法, 如满足则算法结束, 当前解就作为算法的最终解。

2.2 BWC最优问题形式化描述

任意给定一个图G, 其最优BWC问题, 就是给定着黑色的顶点数, 在确保所有的白点集合与黑点集合没有任何边相连的情况下, 寻找最大的白点数。图G= (V, E) 包含n个定点m条边, 对于每一个顶点vi, 设置变量wi和bi根据如下定义:

满足如下条件:

(1) bi, wi≥0;bi+wi≤1, 其中1≤i≤n。

(2) bi+wj≤1, 其中i和j两个顶点相连。

BWC最优问题将转换为求解:

2.3算法主体流程设计

BTLSBW (based Tabu list local search black white coloring) 基于禁忌表的设计思想, 以局部搜索算法为主体, 融入启发式策略的一种智能算法。

相关术语包括:G= (V, E) 为无向图, B为黑色顶点集合, 黑点个数为b, 即|B|=b, W白色顶点集合, 灰色顶点集合是指除黑点和白点之外的其它顶点, 也就是与黑点相连的非黑顶点。非黑顶点包括白点和灰点集合。该算法主体流程设计见图2所示。

(1) 产生初始解。

①从图G中随机选择一个点着黑色;

②从剩下的非黑点集合中选择非黑点度最小的顶点着黑色;同时修改所有非黑顶点的黑点度及非黑点度。

③判断着黑色顶点总数是否到达要求, 如果未达到转入 (2) 。

(2) 计算目标函数即|W|。

(3) 局部搜索。

①从黑点集合中取非黑点度最大的且不在禁忌表中的顶点vi;

②从非黑点集合中取黑点度最大的且不在禁忌表中的顶点vj;

③将vi和vj交换。vi由黑变非黑:修改所有非黑点顶点的黑点度和所有黑点的非黑点度;vj由非黑变黑:修改所有非黑点顶点的黑点度和所有黑点的非黑点度。

④将vi和vj加入禁忌表, 且设置为已被处理。

⑤计算目标函数即|W|, 判断是否所有改进并记录。

⑥判断黑点集合中所有顶点是否被处理, 如果未处理完, 转入①。

(4) 迭代。使用禁忌表, 避免小范围内的重复, 重新产生一个可行解, 转入 (2) 。

(5) 满足条件退出。

2.4算法策略

2.4.1启发式策略

主循环流程中, 为找到相对优化的可行解, 需要考虑启发式策略。随机产生一个黑点后, 其余b-1个黑点如何产生呢?通过计算每个非黑点的非黑点度, 始终从剩下非黑点集合中选择一个非黑点度最小的顶点, 作为着黑色的依据, 这样产生的黑点与非黑点连接最少, 可以保证白点数尽可能大一些, 更趋近于解的最优值。

在局部搜索流程中, 从黑点集合中选择一个黑点, 从非黑点集合中也选择一个非黑点, 进行交换, 此时如何选择, 也会考虑到启发式策略。黑点选择策略是:从黑点集合中取非黑点度最大的顶点。非黑点选择策略是:是从非黑点集合中取黑点度最大的顶点。

2.4.2禁忌表策略

在主流程中, 设置一个禁忌表OTL, 禁忌表大小设置小于图顶点总数的三分之一左右, 禁忌表设置形式采用数组。对主循环每次迭代所产生的可行解中的第一个黑点进行禁忌判断。实现方式为:将主循环的迭代次数存入禁忌表中该顶点索引所在項的数组元素中, 在主循环的每次迭代中, 针对可行解的第一个黑点, 首先判断该顶点在禁忌表中的值与迭代当前值进行比较, 如果|迭代次数当前值-禁忌表中对应項之值|>设置的禁忌表大小, 该黑点选择有效, 否则该黑点选择无效。

在局部搜索过程中, 设置两个禁忌表ITLb和ITLw。该禁忌表与OTL的设置形式类似。

2.4.3结束条件

局部搜索中设置结束条件:将可行解中的所有黑点作为局部搜索的起始点, 每产生一个邻域, 就是从黑点集合中通过启发式产生一个黑点, 与非黑点集合中通过启发式产生的一个非黑点进行交换, 得到原可行解的一个邻域。每次选择一个黑点, 对选择的黑点进行标志, 如果该可行解中所有黑点都被设置标志, 意味着本次局部搜索结束。

在主循环流程中设置结束条件:在这里使用简单的方法, 如果产生的BWC最优值与图的实际最优值相等, 主循环即刻结束。

3算法伪代码

3.1核心数据结构设计

G= (V, E) :代表被处理的无向图。

NBdeg G (S) (v) :顶点v在子图G (S) 中的非黑点度 (在子图G (S) 中与非黑点连接的边数) , 其中

Bdeg G (S) (v) :顶点v在子图G (S) 中的黑点度 (在子图G (S) 中与非黑点连接的边数) , 其中

B为代表黑点集合;W代表白点集合;BW代表灰点集合;b为黑点个数, n代表图G的节点数。

CC为存放候选顶点集。

ITLw[i], ITLb[i] (i∈1~n) :局部搜索算法中设置的禁忌表, 用来存放对应顶点i被访问时的迭代计数值, 用以标示该顶点在最近几次 (禁忌表大小) 迭代中是否被访问过。

OTL[i] (i∈1~n) :主循环中设置的禁忌表, 用来存放对应顶点i被访问时的迭代计数值, 用以标示该顶点在最近几次 (禁忌表大小) 迭代中是否被访问过。

以上数据结构将在伪代码中被使用。

3.2算法伪代码

伪代码中的相关参数参见3.1节介绍。主函数

3.2.2 Generate Black Vertexfor Strategy函数

3.2.3目标函数fun (G, B) 算法

3.2.4局部搜索

4试验结果与分析

4.1网格图选取

通过选择不同的网格图, 对算法进行测试, 用以求解BWC问题的最优解。网格图有多种形式, 通常采用路与圈的各种乘积图生成。对于给定的图G= (U, E) 和H= (V, F) , 其Cartesian强乘积图定义为:

当G和H为路 (Path) 时, 即为网格图, 图3为P4与P3做Cartesian强乘积所得到的网格图

4.2网格图算法结果比较

在文献[6]中给出整数线性规划算法 (ILP) , 二次规划算法 (QP) , 模拟退火算法 (SA) , 随机爬山算法 (RRHC) , 贪心随机自适应搜索算法 (GRASP) , 随机禁忌搜索算法 (R-tabu) 以及半贪心禁忌搜索算法 (SG-tabu) 等求解BWC最优问题的算法思想、步骤以及针对部分网格图的求解结果。通过前面BTLS-BW描述的算法思想编写完整的程序, 对测试C15

C11, C21 C20这两个强网格图, 指定不同的黑点数从20, 21, 25, 28, 70, 99, 100, 120, 125, 141等, 通过运行算法程序计算其所产生的最优化BWC问题值, 与前面在文献[6]中相关的实验数据进行比较, 具体实验数据参见表1。

4.3随机图测试结果

选择三个随机图le450_25a, le450_15c, inithx.i.1, 其图的相关属性见表1。

用混合启发式BTLSBWC算法对三个随机图进行了如下测试:BTLSBW算法运算了25次, 每次20min, 表3分别展示了25次中的最好值, 最差值和平均值。

6结论

本文对混合启发式算法BTLSBWC的相关设计思想、工作流程及算法伪代码进行了详细描述, 利用C实现了算法并通过部分网络图和随机图进行了验证。表格1的测试实验数据表明, 本算法达到了目前文献计算出的最好结果。表3展示了该算法对三个随机图进行测试的结果。

参考文献

[1] Berend D, Korach E, Zucker S.Anticoloring of a family of grid graphs.Discret Optimization, 2008;5 (3) :647—662

[2] Hansen P, Hertz A, Quinodoz N.Splitting trees.Discrete Mathematics, 1997;165 (6) :403—419

[3] Berend D, Zucker S.The black-and-white coloring problem on trees.Journal of Graph Algorithms and Applications, 2009;13 (2) :133 —152

[4] Kobler D, Korach E, Hertz A.On black-and-white colorings, Discrete Optimization, 2008;5 (3) :647—662

[5] Berend D, Korach E, Zucker S.Anticoloring and separation of graphs.Discrete Mathematics, 2010;310 (3) :390—399

[6] Berend D, Korach E, Zucker S.Tabu search for the BWC problem.J Glob Optim, 2012;54:649—667

[7] Glover F.Tabu search-part I.ORSA Journal on Computing, 1989;1 (3) :190—206

[8] 徐宁, 李春光.几种现代优化算法的比较研究.系统工程与电子技术, 2002;24 (12) :100—103Xu L, Li C G.A comparative study of several modern optimization algorithm.Journal of Systems Engineering and Electronics, 2002;24 (12) :100—103

[9] 王凌.智能优化算及其应用.北京:清华大学出版社, 2001:143Wang L.Intelligent Optimization Algorithm and Its Application.Beijing:Tsinghua University Press, 2001:143

着色算法篇4

在文献[9]中LEE Changhee等人根据D2D用户提供的干扰列表建立干扰图,并基于图着色进行顺序资源分配,但该算法对终端设备的性能要求较高。文献[10]建立D2D用户和蜂窝用户间加权二分图,并采用最优匹配算法分配无线资源,提高了系统吞吐量,但算法复杂度较高。在文献[11]中HAN Jiang等人允许一个D2D用户复用一个蜂窝用户的无线资源,并利用最优匹配实现了最小化系统中同频干扰。TAB Li等人在文献[12]中对基于图着色理论给出一种认知频谱分配方法,该方法将系统带宽分为多个子信道,再将子信道分配给用户,从而最小化带宽需求,但该方法不能最大化系统吞吐量。此外,现已存在的图着色资源分配算法均是将D2D用户与蜂窝用户作为对等用户建立常规干扰图,再进行无线资源分配。然而D2D通信的引入仅仅是作为蜂窝通信的一种辅助通信方式,这样的无线资源分配不能有效体现出不同通信类型用户的重要性。此外,传统图着色资源分配算法仅根据顶点饱和度来评判着色优先级的策略已远远无法满足实际通信需求。

考虑到上述存在的问题,本文针对D2D用户复用LTE系统中蜂窝用户下行链路进行通信时,尤其在社交网络中对通信质量和传输速度要求较高的场景下,提出了一种基于图着色的加权优先D2D资源分配算法。相比于传统图着色资源分配算法,该算法的优势在于:1)在D2D异构网络中,建立了一张异构干扰图,以体现出网络中两类用户重要程度的差异。2)着色顺序不再是以往的随机着色或者顺序着色,而采用加权优先着色。3)确定了无线资源分配以后,引入简单分组功控,不仅能够进一步减小用户发送功率降低干扰影响,还能够动态调整特定无线资源上的能量消耗。最后,结合算法仿真图,对比分析该算法相对于其他类似算法的优势。

1系统模型

在D2D异构网络中,系统内存在着两类用户:传统蜂窝用户和短距离D2D用户对。建立系统模型如图1所示,系统中共有M个蜂窝用户,记为C={C1,C2,…,CM};N个D2D通信对,记为D={D1,D2,…,DN}。其中,Ci表示第i个蜂窝用户,Txi表示第i个D2D用户对中的发送端用户,Rxi表示接收端用户。同时D2D用户以相同初始发送功率进行数据传输。另外,用LC表示蜂窝链路集合,LD表示所有D2D链路集合,Lk表示使用无线资源k的链路集合。为提高频谱利用率,允许多个D2D用户对复用同一蜂窝用户的无线资源进行数据传输。

由于LTE系统下行采用OFDM(Orthogonal Frequency Division Multiplexing)技术,因此,蜂窝用户之间不存在干扰,而D2D用户以非正交方式复用蜂窝用户下行信道资源,则系统中主要存在两种干扰:D2D用户对之间的干扰和D2D用户对与蜂窝用户之间的干扰。

具体干扰情况如图1所示。图中C1,Tx1,Tx2使用相同信道资源进行数据传输,基站会对Rx1,Rx2造成同频干扰;同时Tx1也会对C1和Rx2造成同频干扰;另外Tx2也会对C1和Rx1造成同频干扰。由此可见,D2D异构网络中的干扰情况比较复杂,为此需要对频谱资源进行合理分配以协调同频干扰,从而保证终端用户通信质量并提高频谱利用率。

此外假设(φi,ri)是用户i的极坐标,则用户i与用户j之间的距离dij在极坐标下表示为

式中:ri表示用户i到基站距离;φi表示用户i方位角。那么系统中的路损模型如下

基站到用户的路径损失为

不同用户之间的路径损失为

其中,d表示通信链路收发端之间的距离。

2基于图着色的加权优先资源分配

根据实际情况,在D2D异构网络中,D2D通信为辅助通信方式,蜂窝用户是主用户而D2D用户仅为从用户,因此在进行干扰分析时应严格对主从用户进行区分。另外,为满足用户的正常通信质量需求,预设蜂窝用户正常通信的SINR阈值为γ1,D2D用户正常通信的SINR阈值为γ2。在基于图着色的加权优先分配资源时,将系统中的通信链路和链路之间的同频干扰分别抽象为图中的“顶点”和“边”,从而建立一张异构干扰图H。特别指出,在建立异构干扰图时,应先将系统中每条通信链路抽象为异构图的“顶点”,然而两个“顶点”之间“边”是否存在,则要结合用户SINR阈值要求和用户间同频干扰程度来决定。

2.1建立异构干扰图

异构干扰图中的“顶点”由蜂窝链路和D2D链路构成。其中,所有蜂窝链路构成顶点集合V1,所有D2D通信链路构成顶点集合V2。V1和V2一起组成图中所有顶点的集合V。根据顶点间干扰以及用户的通信质量要求构成边的集合E,从而可得到异构干扰图H(V(V1,V2),E)。结合D2D异构网络的特性,图H中边主要分为两类:单类干扰边和混合类干扰边。其中,单类干扰边则是针对蜂窝链路仅收到D2D链路的单一干扰所建立的边;混合类干扰边则是针对D2D链路遭受的干扰为来自蜂窝链路和其他D2D链路的混合干扰所建立的边。

当多个D2D用户对以非正交方式与同一蜂窝用户使用相同无线资源k时。蜂窝用户Ci的SINR为

D2D链路接收端Rxj的SINR为

式中:表示Ci的SINR;Pi,k表示基站在信道k上对Ci的发送功率;表示基站到Ci的链路增益;表示Txj在信道k上的发送功率;表示Txj到Ci的链路增益;η表示高斯白噪声功率;B表示信道带宽。

另外定义链路i的发送端对链路j的接收端产生的干扰为Iij,具体表示为

式中:Pi表示链路i发送端的发送功率;Gij表示链路i发送端到顶点j的接收端链路增益。

边建立的详细步骤如下:

1)单类干扰边建立,步骤(伪代码)如下:

2)混合类干扰边建立

混合类干扰边的建立步骤和方法与单类干扰边的建立类似,不同之处在于第4步,SINR的计算采用式(5),以及第11步中的判断条件更改为SINRij>γ2。故此处不再进行赘述。

在单类与混合类干扰边建立完成之后,最终得到一个异构干扰图H。此时,根据图H定义顶点的i饱和度S(i)为

2.2加权优先资源分配

假设基站端有两个缓冲队列,分别存放发起资源请求的蜂窝用户和D2D用户,每个用户对应一个数据队列用来缓存待发送的数据。为不失一般性,定义影响获得资源优先级的因素包括:1)信道质量;2)用户排队等待时延;3)用户待发送数据量;4)用户能忍受的最大时延。一般地,用户获得资源的优先级越高,则要求信道质量好、用户排队时延大、待发送数据多、用户可忍受等待时延小。假设用户i发起资源请求的时刻记为ti,arr_time,获得无线资源的时刻记为ti,leave_time,那么用户i在队列中的排队等待时延Ti为

当等待时延超过能承受的最大时延时,用户则会丢弃待发送的数据包。为了避免信道质量差的用户长时间分配不到资源,降低系统公平性,因此这里将延迟作为影响用户获得获取资源优先级的一个重要因素,定义用户i的延迟权重为

式中:Ti,max用户i允许接受的最大延迟。

假设用户期望发送数据量的大小为Qi',数据队列能缓存的最大数据量为Qi,max,因此对应数据队列中实际待发送数据大小Qi为

同时以信噪比衡量信道质量,信噪比越大说明信道质量越好。链路i接收端的信噪比具体表示为

基于上述分析,将用户i获得无线资源的优先级定义为

式中:D(i)表示用户i获得资源的优先级;对应顶点i和i'属于同类集合的顶点。

对顶点着色时,综合考虑用户优先级和对应顶点饱和度确定着色顺序。根据式(7)和式(12)对图中顶点i着色等级F(i)定义为

当前层着色顶点color*需满足条件为

同时将已着色顶点从对应顶点集合中删除,更新未着色顶点。

考虑到D2D通信只是一种辅助通信模式。因此在基于图着色的异构加权进行着色资源分配时,需要优先对顶点集合V1中的顶点着色,再对集合V2中顶点着色。具体着色步骤(伪代码)描述如下:

为了评判系统中D2D用户间的公平性,采用jains公平性评估标准如

式中:Fair表示系统公平性;n表示请求资源的D2D用户数量;xi表示D2D用户i的传输速率。

将D2D系统用户损失率定义为因超过最大时延而放弃排队等待资源分配的用户数与请求用户总量比值,具体定义为

式中:n表示等待时延超过最大时延的D2D用户数;N表示请求资源的D2D用户数。

2.3分组功率控制

为了减小用户终端功率消耗,以保证用户最低SINR要求为前提,采用简单功率调控最小化对应用户的发送功率。根据图着色无线资源分配结果,将占用相同无线资源的所有用户作为一个分组,对每组中所有用户进行功率调控,从而优化用户的发送功率。

根据资源分配结果,计算蜂窝用户和D2D用户实际SINR。结合Cm的SINR阈值γ1和同组Gm的D2D用户的发送功率,可以得到其最低发送功率为

式中:Pm'表示经过功率调控后;基站对Cm的发送功率。

按式(17)更新基站对Cm的发送功率,同时结合式(5)计算所有D2D用户的SINR,并按此时的SINR从大到小逐个更新D2D用户发送功率。根据阈值要求γ2,更新Gm当前SINR最大的Rxn相应Txn的发送功率表示为

式中:表示经功率控制后Tn的发送功率;若Ti发送功率已更新,则为更新后的发送功率,否则为原始功率。

对未更新功率的D2D用户按照SINR从大到小的顺序,继续采用式(18)更新发送功率,从而减小系统功率消耗。

3仿真与性能分析

为了评估本文提出的D2D无线资源分配算法对系统性能的影响,采用计算机仿真来进行验证和分析。用户在小区内服从均匀分布,蜂窝用户分布在基站中心200 m内,D2D用户复用蜂窝用户下行链路资源。每个用户排队等待时延在仿真时随机生成,其余仿真参数设置如表1所示。由于所有用户在小区中的位置具有一定随机性,仿真次数为500次并取平均值以便得到的数据更具有参考价值。同时,将以随机着色资源分配算法(RCA)、仅考虑时延的着色资源分配算法(DCA)和传统图着色资源分配算法(TGCA)作为参考,对比本文的分配算法(DGCA),重点考察D2D系统公平、系统吞吐量和系统功率消耗等方面的性能。

图2比较了不同算法下,D2D系统资源分配的公平性影响。从图中可以看出,随着D2D请求对数增加,D2D系统公平度开始下降。其中,TGCA以吞吐量最大为目标,而相对牺牲了较多的公平性。在系统中有80对D2D用户的情况下使用DGCA算法,则相比于DCA算法可以提高5%的调度公平性。这是因为DCA算法仅考虑时延而没考虑顶点饱度,而DGCA不仅考虑了顶点饱和度,而且也将时延作为着色的一个因素,能够在一定程度上提高那些因为信道质量差而迟迟得不到资源的D2D用户获得资源的优先级,因此,系统的公平性得到了提高。

图3比较了不同着色资源分配算法下,D2D系统平均时延的影响。由图可看出不同算法的系统平均时延都随着资源请求的D2D对数增加而增加。其中,相比于DCA算法,DGCA算法在D2D用户数达到50对时系统平均时延会稍微偏高0.1 ms,但D2D通信主要用于数据传输而非实时业务,因此0.1 ms的延迟对用户并不感知。另外结合图2和图3分析可知DCA算法优先对时延较大的顶点进行着色资源分配,使系统整体时延最小,但是严重牺牲了资源调度的公平性。相比于其他两种算法,DGCA在降低系统时延上则显示出了明显的优势。

图4比较了不同算法下的系统吞吐量。从图中可以分析随着系统中D2D用户数的增加,系统吞吐量也逐渐增加。由于TGCA算法仅仅根据顶点饱和度进行着色资源分配,而获得了最大的系统吞吐量。DGCA不仅考虑了顶点饱和度还提高了时延较大顶点的着色优先级,使得丢弃的数据包较少,虽然获得的吞吐量相比于TGCA有平均1.5%的降低,但结合图2、图3和图4综合分析,TGCA获取较高吞吐量的前提则是严重牺牲了用户调度的公平性以及很大程度上增加了系统的时延。

图5比较了不同阈值对系统吞吐量的影响。图中显示随着D2D对数增加,系统吞吐量增加,而阈值越大,系统吞吐量越小。这是因为未达到用户SINR阈值时,系统接入D2D对数随着请求D2D对数增加而增加,从而系统吞吐量也增加,而SINR阈值越大,用户能承受的干扰越小,允许接入的D2D对数越少,系统吞吐量就越小。

图6比较了有功率控制和无功率控制时系统总的功率消耗。没有功率控制时,基站和用户均以固定功率发送,而有功率控制时,根据用户SINR最低要求进行功率控制,从而减小了系统功率消耗。

4结语

在TD-LTE系统中为D2D用户选择合适的蜂窝用户下行无线资源进行复用。首先根据用不同通信类型户间干扰程度,建立异构干扰图。进一步结合顶点饱和度、等待时延、信道质量、数据量计算加权优先着色顺序。最后根据图着色算法进行无线资源的分配。理论上,改进了现有图着色资源分配算法的不足,并实现了系统最大吞吐量性能。实际上,又将影响无线资源分配的因素全面考虑,具有很强的实际应用价值。

仿真表明,本文算法在系统平均时延、丢包率以及系统吞吐量方面的综合性能最好,同时还减少了系统总功率消耗。

摘要：针对蜂窝用户与D2D用户所构成的异构网络系统中同频干扰问题,提出一种基于图着色的加权优先D2D资源分配算法。该算法不仅允许多个D2D用户复用一个蜂窝用户资源,而且能够实现简单功控。首先建立异构干扰图,对系统终端用户及干扰类型进行分类异构。然后计算着色优先级,考虑各种影响因子以提升算法的实用性。最后再由分配结果进行组内功率控制,以满足绿色通信的要求。仿真表明,该算法不仅可以降低系统用户接入损失率,提高系统吞吐量,而且还减少了功率消耗。

关键词：资源分配,分类异构,图着色,功率控制,绿色通信

参考文献

[1]DOPPLER K,RINNE M,WIJTING C,et al.Device-to-device communication as an underlay to LTE-advanced networks[J].IEEE communications magazine,2009,47(12):42-49.

[2]SARTORI P,BAGHERI H,DESAI V,et al.Design of a D2D overlay for next generation LTE[C]//Vehicular Technology Conference.[S.l.]:IEEE,2014:1-5.

[3]MOUBAYED A,SHAMI A,LUTFIYYA H.Wireless resource virtualization with device-to-device communication underlaying LTE network[J].IEEE transactions on broadcasting,2015,61(4):734-740.

[4]XIN Q,KANG C G.An effective interference alignment approach for device-to-device communication underlaying multi-cell interference network[C]//2012 International Conference on ICT Convergence(ICTC).[S.l.]:IEEE,2012:219-220.

[5]ZHANG B,WANG Y,JIN Q.Energy-efficient architecture and technologies for device to device(D2D)based proximity service[J].China communication,2015,12(12):32-42.

[6]PHUNCHONGHARN P,HOSSAIN E,KIM D I.Resource allocation for device-to-device communications underlaying LTE-advanced networks[J].IEEE wireless communications,2013,20(4):91-100.

[7]TSOLKAS D,LIOTOU E,PASSAS N,et al.A graph-coloring secondary resource allocation for D2D communications in LTE networks[C]//Proc.International Workshop on Computer Aided Modeling&Design of Communication Links&Networks.Barcelona:IEEE,2012:56-60.

[8]BIN WANG,LI CHEN,XIAOHANG CHEN,et al.Resource allocation optimization for device-to-device communication underlaying cellular networks[C]//Proc.Vehicular Technology Conference(VTC Spring).Budapest:IEEE,2011:1-6.

[9]LEE C,OH S M,PARK A S.Interference avoidance resource allocation for D2D communication based on graphcoloring[J].Journal of Korean institute of communications&information sciences,2014,39A(12):729-738.

[10]ZHANG H,WANG T,SONG L,et al.Radio resource allocation for physical-layer security in D2D underlay communications[C]//Proc.IEEE International Conference on Communications.Sydney:IEEE,2014:2319-2324.

[11]HAN J,CUI Q,YANG C,et al.Bipartite matching approach to optimal resource allocation in device to device underlaying cellular network[J].Electronics letters,2014,50(3):212-214.

着色算法篇5

1 材料与方法

1. 1 主要实验仪器和材料

1.1.1实验仪器

Olympus Crystaleye分光光度比色仪(奥林巴斯公司,美国);恒温箱(上海新苗医疗器械制造有限公司);表面粗糙度轮廓仪(FTSi60,英国泰勒公司);低速手机(广州市超盛医疗器械有限公司)。

1.1.2实验材料

树脂人工牙:ENDURA ANTERIO(日本株式会社松风);贺利氏三色合成树脂牙(贺利氏古莎齿科有限公司);合成树脂牙(上海齿科材料有限公司);EFUCERA-A(山八齿材工业有限公司);凯丰合成树脂牙(沪鸽齿科材料有限公司);热固化树脂基托粉和液(日进公司,日本)。

1.1.3着色介质溶液

雀巢速溶咖啡(广东省东莞市雀巢有限公司);立顿红茶(联合利华食品有限公司);陈醋(恒顺,江苏恒顺集团)。

1. 2 实验方法

1.2.1实验样本制备

(1)每种品牌选用16颗人工牙,均选用右上中切牙,A1色,最大号牙;(2)制作蜡型:常规制作长2 cm、宽2 cm、厚1 cm的蜡型90个,然后将每个蜡型的顶面中心烤软,将准备好的每种品牌的人工牙唇面朝上,嵌入蜡型中,使用不锈钢平板将人工牙中1/3压至水平。人工牙与蜡型结合的边缘用蜡密封好;(3)将制作好的蜡型常规装盒包埋、去蜡、充填树脂、热处理后开盒抛光;(4)样本分组:ENDU-RA ANTERIO为1组,标记贺利氏三色合成树脂牙为2组,标记合成树脂牙为3组,标记EFUCERA-A为4组,标记凯丰合成树脂牙为5组,每组16个样本以1~16编号;(5)每块试件边角打孔,棉线悬挂备用。

着色溶液的准备:咖啡:使用350 ml 100℃蒸馏水溶解3.6 g的速溶咖啡(雀巢);茶:使用350 ml 100℃蒸馏水浸泡一小包立顿红茶。2种溶液均每隔30 min搅拌10 s至温度降至37℃,然后使用滤纸过滤。陈醋:常温,350 ml;蒸馏水:常温,350 ml作为对照。

1.2.2试件粗糙度测量方法

每组试件均在人工牙九分法的中心部位随机选取3个点,用表面粗糙度轮廓仪测量试件表面粗糙度(启动长度0.2 mm,数据长度4 mm,前进速度0.5 mm/s),测量时垂直于测试面,仪器自动记录轮廓算术平均偏差(Ra)。每组试件的3个不同部位测定结果取均值。

1.2.3试件的浸泡与测色

将每组16个人工牙试件随机分成4组,每组4个,分别悬挂于各浸泡液中,避光置放于37℃恒温箱中,每日更换一次溶液,分别在试件浸泡前与浸泡4周后测试其表面色度值。

1.2.4试件测色方法

每次测色均选择下午2点,在同等光线、标准黑背景下,由同一实验者独自完成。将待测试件取出,在蒸馏水下冲洗30 s后,自然干燥。使用分光光度比色仪,选用分析模式,每次测定前预先用自带校准头校准,比色仪测量头使用遮色套,垂直于测试面进行测量,测量部位选取人工牙九分法的中心部位。采用CIE-1976-L*a*b*标准色度系统,记录L*、a*、b*值,每个试件均测定3次,取均值,以浸泡前为基准,计算ΔE值,公式为ΔE=[(ΔL*)2+(Δa*)2+(Δb*)2]1/2。为了将ΔE与临床联系起来,通过公式NBS=ΔE×0.92,计算出NBS值,NBS值对应的临床表现见表1。

1. 3 统计学方法

采用SPSS 19. 0 统计软件进行多样本的色差值和粗糙度值均数比较的方差分析( ANOVA) ,并分别采用Dunnett法和SNK法检验两组间差异,P < 0. 05。

2 结果

2. 1 5 组人工牙试件表面粗糙度的比较

结果经单因素方差分析可知( 表2) ,5 组试件( n= 16) 的主要粗糙度参数Ra值的组间差异有统计学意义( P < 0. 05) ,5 种品牌的人工牙表面粗糙度不完全相同。使用SNK法进行组间两两比较后可知,第1组和第2 组、第3 组和第5 组人工牙主要粗糙度参数Ra值差异无统计学意义( P > 0. 05) ,而第4 组和其它组人工牙主要粗糙度参数Ra值差异有统计学意义( P< 0. 05) 。5 个组试件主要粗糙度参数Ra值的大小顺序为: 4 > 1 = 2 > 3 = 5。即EFUCERA-A人工牙表面粗糙度最大,ENDURA ANTERIO人工牙和贺利氏三色合成树脂牙表面粗糙度次之,合成树脂牙和凯丰合成树脂牙表面粗糙度最小。

2. 2 不同着色介质中试件的着色程度比较

不同着色介质浸泡后,对照组及陈醋组试件颜色无显著性改变; 咖啡组及茶组试件颜色改变明显。将浸泡液种类为影响因素进行方差分析,4 种浸泡液中的试件色差值 ΔE差异具有显著性( P < 0. 05) 。使用Dunnett法对3 个实验组分别与对照组进行两两比较,可知咖啡和茶组 ΔE差异具有统计学意义( P < 0. 05) ,而陈醋组则不具有统计学意义( P > 0. 05) 。使用SNK法两两比较,咖啡的 ΔE大于茶( P < 0. 05) ( 表3) 。

2. 3 同一着色介质中5 组人工牙试件的着色程度比较

浸泡4 周后,咖啡和茶中的5 种品牌人工牙试件的均发生显著性的颜色改变。以人工牙品牌作为影响因素进行方差分析,并使用SNK法进行两两比较,可知不同品牌人工牙试件的色差值 ΔE差异具有统计学意义( P <0. 05) ,其中颜色改变最明显的是EFUCERA-A( 4 组) ,颜色改变最小的是凯丰合成树脂牙( 5 组) ,贺利氏合成树脂牙( 2 组) 、合成树脂牙( 3 组) 和ENDURA ANTERIO( 1 组) 的颜色改变值 ΔE居中( 表3) 。

(± s,μm,n = 16)

注: 以上5 组人工牙组间两两比较除1 组和2 组、3 组和5 组比较时P > 0. 05,其余均P < 0. 05

注: 以上5 组试件组间两两比较除陈醋和水组比较时P > 0. 05,其余均P < 0. 05; 浸泡在咖啡和茶中的5 组试件组件两两比较时均P<0.05

3 讨论

树脂人工牙由有机聚合物基体、无机填充材料和界面偶联剂组成,可以与基托材料形成化学性结合,但是随着义齿戴用时间的延长,人工牙表面会出现各种着色而影响美观[1]。目前国内外关于树脂牙的研究大多集中于硬度、耐磨性等功能性的研究方面[2],而对于其颜色稳定性的研究较少,故本实验选用国内临床常用的5 种品牌的人工牙,研究了3 种着色介质对其颜色稳定性的影响,为临床选择人工牙提供依据。

3. 1 着色介质对人工牙着色的影响

本实验采用分光光度比色仪测量人工牙的色度值,使用国际照明委员会( CIE) 1979 L*a*b*标准色度系统来记录,以 ΔE值作为颜色变化的指标。并引入NBS系统,为临床提供标准化的参考指标[3]。对于临时修复材料和牙科复合树脂,着色情况与材料本身的颜色有关。颜色越亮的物质着色比颜色暗的物质着色更严重[4]。从这个层面上来讲,本研究中选择A1色,因为其更能明显的显示出着色效果。另外实验过程中,试件处理过程相同,各组实验温度、避光情况等均一致,排除了因实验环境差异造成的颜色差异。

本实验中,4 周后浸泡在咖啡和茶中的5 组人工牙试件均发生明显的颜色改变,且浸在咖啡中的试件颜色改变大于茶,而浸在陈醋和水中的5 组人工牙试件未出现明显的颜色变化。颜色改变转变为NBS单位,咖啡和茶均能引起5 组人工牙试件人肉眼可见的颜色改变。这与之前关于丙烯酸树脂材料的研究相符[5],即认为咖啡和茶是着色介质。这是由于树脂牙是PMMA的改性产品,在丙烯酸树脂的基础上加入不同的颜料来调成各种人工牙的色调,通过加入交联剂来改变强度和防止裂纹,它们具有与丙烯酸树脂基本的化学性质,其中也含有亲水基团,可以缓慢吸收和吸附环境中的液体,从而使咖啡和茶中的色素容易吸附到其表面[6,7]。而浸泡在陈醋中的5 组人工牙试件与对照组相比并没有出现显著性差异,这与之前我们所做的关于丙烯酸树脂的研究结果也一致,这大概与陈醋中的酸性成分有关。日本学者Hong等[8]研究了8种义齿清洁剂对义齿颜色稳定性的影响,结果表明酸类清洁剂对义齿颜色稳定性影响最小,从这个层面上来讲醋酸中的酸性成分对人工牙颜色稳定性影响较小。因此,在临床上指导患者佩戴义齿时,应嘱患者尽量避免饮用咖啡,茶等易使义齿着色的饮料。

3. 2 几种品牌人工牙着色的情况

无论是浸泡在咖啡中还是茶中4 周后,5 种品牌的人工牙所表现出的颜色改变情况如下: 最明显的是EFUCERA-A,其次为贺利氏三色合成树脂牙,再次为ENDURA ANTERIO,合成树脂牙再次之,颜色改变最小的是凯丰合成树脂牙。转化为NBS系统5 组人工牙试件的NBS值均处于1. 5 ~ 3. 0 之间,即4 周后浸泡在咖啡和茶中的5 组人工牙试件均出现了人肉眼可见的颜色改变。本实验最大的NBS为2. 74,是浸泡在咖啡中的EFUCERA-A试件,其颜色改变也属于人肉眼可见的范围,但是其 ΔE为2. 976,仍小于3. 3,属于临床可以接受的范围[9]。

由表2 可以看出,这5 种人工牙均为成品牙,表面并未经过磨改,但是其表面粗糙度却不尽相同。从本实验中可以看出这5 种品牌的人工牙的着色情况与其表面粗糙度在一定程度上是相关的。5 种品牌的人工牙中,表面粗糙度顺序为EFUCERA-A人工牙表面粗糙度最大,ENDURA ANTERIO人工牙和贺利氏三色合成树脂牙表面粗糙度次之,合成树脂牙和凯丰合成树脂牙表面粗糙度最小。而颜色改变的情况按由大到小的顺序是: EFUCERA-A、贺利氏三色合成树脂牙、ENDURA ANTERIO、合成树脂牙、凯丰合成树脂牙。这二者顺序基本一致,说明对于人工牙来说,表面粗糙度与其着色程度相关,表面粗糙度越大,着色越明显,即粗糙的表面可以为色素沉着提供条件,在此部位色素颗粒不易得到清洗,同时粗糙的表面可提供较大的表面积使色素易于沉着。

对于ENDURA ANTERIO人工牙和贺利氏三色合成树脂牙其表面粗糙度并不具有统计学差异,但是其着色程度不尽相同。二者相比之下,贺利氏三色合成树脂牙着色更严重。这大概是因为ENDURA ANTERIO人工牙是采用了经硅烷活化处理的超微二氧化硅类填料的复合树脂牙,而贺利氏三色合成树脂牙是未添加任何填料的普通树脂牙。Satoh等[10]认为高强度树脂牙的颜色稳定性比普通树脂牙好,本实验结果中ENDURA ANTERIO人工牙着色程度较贺利氏三色合成树脂轻与之相符。从这个角度来讲,EFUCERA-A人工牙也属于添加填料的硬质复合树脂牙,但是其颜色改变值最大,这可以用其表面粗糙度值最大来解释。另外,Imamura等[11]学者认为在树脂牙中单纯地加入二氧化硅填料,并未经过硅烷化,那么树脂基质吸水膨胀,在填料和树脂基质的连接处容易形成裂隙,使色素容易沉着。而经过硅烷化之后,二氧化硅填料可以与树脂基质良好的结合,形成一个平滑的表面,使树脂材料的吸水性降低,从而其颜色稳定性更好。本实验中加入硅烷化的超微二氧化硅填料的ENDURA ANTERIO人工牙颜色稳定性较好也再次验证了这个观点。而EFUCERA-A人工牙的着色程度最大除了与其表面粗糙度大相关外,另一个原因大概是因为加入其中的二氧化硅填料并未有效地完成硅烷化这一过程。本实验中还发现合成树脂牙与凯丰合成树脂牙表面粗糙度并无统计学差异,但是凯丰合成树脂牙的颜色改变较合成树脂牙小。凯丰合成树脂牙是具有内部交联、网状贯通结构的高分子材料,经高温、高压,多次聚合而成,该原材料材质高度致密,结构上无产生吸水现象的多余空间。而合成树脂牙是上海齿科材料有限公司生产的较早期的丙烯酸树脂牙,它的内部交联程度没有凯丰高,其吸水性较强。综合考虑,表面粗糙度相同的2 种品牌的人工牙,凯丰合成树脂牙是临床上较好的选择。

从本研究可以得出结论,外源性色素如咖啡,茶可以使人工牙着色,不同品牌的人工牙着色程度不尽相同,与其表面粗糙度和填料类型有关,从颜色稳定性方面考虑,本研究中的5 种品牌的人工牙均符合临床使用标准,而且ENDURA ANTERIO和凯丰合成树脂牙是较理想的选择。

摘要：目的:研究4种着色介质对不同品牌树脂人工牙的表面着色状况。方法:选用ENDURA ANTERIO、贺利氏三色合成树脂牙、合成树脂牙、EFUCERA-A、凯丰合成树脂牙各16颗,制作试件,用表面粗糙度轮廓仪测量试件的表面粗糙度参数Ra,然后将每组试件分别浸泡于蒸馏水(对照)、咖啡、茶和陈醋中,用分光光度比色仪测量试件浸泡前及浸泡4周后的颜色,得到L*、a*、b*值,计算浸泡前后的色差ΔE,统计学方法分析树脂人工牙着色与上述因素的关系。结果:咖啡组和茶组试件的色差值ΔE均增大(P<0.05),且咖啡组的ΔE大于茶组(P<0.05),陈醋组的ΔE无明显改变(P>0.05);同一浸泡液中不同品牌人工牙试件的ΔE值差异有显著性(P<0.05),其大小顺序为EFUCERA-A>贺利氏三色合成树脂牙>ENDURA ANTERIO>合成树脂牙>凯丰合成树脂牙。结论:外源性色素能引起树脂人工牙的着色,5种品牌人工牙着色程度不同。

关键词：树脂人工牙,着色,表面粗糙度,着色介质

参考文献

[1]Hipólito AC,Baro VA,Faverani LP,et al.Color degradation of acrylic resin denture teeth as a function of liquid diet:Ultraviolet-visible reflection analysis[J].J Biomed Opt,2013,18(10):105005.

[2]Suwannaroop P,Chaijareenont P,Koottathape N,et al.In vitro wear resistance,hardness and elastic modulus of artificial denture teeth[J].Dent Mater J,2011,30(4):461-468.

[3]Razzoog ME,Lang BR,Russell MM,et al.A comparison of the color stability of conventional and titanium dental porcelain[J].J Prosthet Dent,1994,72(5):453-456.

[4]Chan KC,Fuller JL,Hormati AA.The ability of foods to stain two composite resins[J].J Prosthet Dent,1980,43(5):542-545.

[5]张薇,刘娟,李长福.着色介质及表面粗糙度对热固化基托树脂着色的影响[J].实用口腔医学杂志,2012,28(1):22-25.

[6]Bagheri R,Burrow MF,Tyas M.Influence of food-simulating solutions and surface finish on susceptibility to staining of aesthetic restorative materials[J].J Dent,2005,33(5):389-398.

[7]Omata Y,Uno S,Nakaoki Y,et al.Staining of hybrid composites with coffee,oolong tea,or red wine[J].Dent Mater J,2006,25(1):125-131.

[8]Hong G,Murata H,Li Y,et al.Influence of denture cleansers on the color stability of three types of denture base acrylic resin[J].J Prosthet Dent,2009,101(3):205-213.

[9]Mutlu-Sagesen L,Ergün G,Ozkan Y,et al.Color stability of a dental composite after immersion in various media[J].Dent Mater J,2005,24(3):382-390.

[10]Satoh Y,Nagai E,Azaki M,et al.Study on high-strength plastic teeth.Tooth discoloration[J].J Nihon Univ Sch Dent,1993,35(3):192-199.

着色算法篇6

关键词：化学着色,着色膜,铝合金小零件,耐腐蚀性

0 前言

化学着色可以很好地解决批量铝合金小零件的装饰性和保护性问题。利用KMnO4、HNO3、Cu(NO3)2在常温下对铝合金零件表面着黑色后可以用于仪器仪表、汽车部件,能获得色泽纯正均匀、具有一定耐蚀性能的装饰性色膜[1],满足其使用要求。着色零件使用场合不相同,着色质量标准也不同。而装饰性着色,色泽纯正、抗潮湿空气氧化腐蚀就是其主要指标。为此有必要研发新的化学着色配方,既能获得色泽纯黑的着色膜,又能进一步提高着色膜的耐腐蚀性能。

本工作通过正交试验,优选出了耐蚀性能较佳的工艺配方;所得着色膜耐酸、耐碱和耐盐雾腐蚀能力均有显著提高;该法操作方便,所需设备简单,便于大批量生产,具有较好的应用价值。

1 试验

1.1 着色处理

1.1.1 基材前处理

着色基材为LF2铝合金铆钉,其成分符合GB/T 3190-1996要求,尺寸见图1。其前处理[2,3]如下:

脱脂除油:20 g/L NaOH,45 g/L Na2CO3;温度60～80 ℃,不断搅拌下处理1 min。

酸蚀:质量分数40%的HNO3;室温,处理时间1 min。

活化:质量分数3%的NaOH,室温,时间2 min,其作用是去除表面氧化膜,提高表面的结合强度。

水洗:先用自来水洗,再用蒸馏水洗;每次水洗1～2 min,以去除表面附着的杂质和残留的处理液。

1.1.2 着色工艺

化学着色:将(NH4)2MoO4,NH4Cl,H3BO3和KNO3按一定比例配制成水溶液,并加热至60～90 ℃。将零件按一定的装载量放入着色液中,保持温度下不断缓慢搅动零件20～60 min。

着色后,将工件置入蒸馏水中漂洗,以去除其表面残留的着色液,最后烘干保存。

为了进行对比,按常温置换氧化配方在铆钉表面制备着黑色膜,具体的工艺:15 g/L KMnO4,4 mL HNO3(ρ=1.40 g/cm3),25 g/L Cu(NO3)2,在室温下反应12 h,期间间隔搅拌。

1.2 正交试验设计

选取影响着色膜性能的4个主因素:(NH4)2MoO4浓度、NH4Cl浓度、着色温度、着色时间进行考察,固定H3BO3浓度为8 g/L、KNO3浓度为8 g/L。采用L9(34)正交试验进行优化,其因素水平见表1。

1.3 膜层主要性能评价指标

确定正交检验标准:耐酸腐蚀性、耐碱腐蚀性、耐盐雾腐蚀性分别为S,J,Y指标,采用5 mm×5 mm方格划分,以无腐蚀点方格的比率来评价抗蚀能力的大小:(1)耐酸腐蚀性检验试剂为25 mL 37%HCl,3 g K2CrO7,75 mL 蒸馏水,常温下浸泡;以反应10 min后色膜未被腐蚀方格的百分数评定腐蚀程度;(2)耐碱腐蚀性检验试剂:5%(质量分数)NaOH溶液,温度50～60 ℃,以浸泡3 min后未被腐蚀方格的百分数评定;(3) 耐盐雾腐蚀性:按照GB 6458-86进行中性盐雾(NSS)试验,采用5%(质量分数)NaCl溶液,溶液pH值为中性(6～7);试验温度均取35 ℃,盐雾的沉降率测定为1.7 mL/(80 cm2·h),符合GB 6458-86中沉积率1.0～2.0 mL/(80 cm2·h)的要求,试验时间为8 h,用未被腐蚀方格的百分数评定耐腐蚀性。

2 结果与分析

2.1 4因素对色膜耐蚀性的影响

4因素正交试验的极差分析见图2。由图2可知,(NH4)2MoO4浓度对各耐腐蚀指标影响的显著性最大,最佳值为15 g/L; NH4Cl浓度对耐碱和耐盐腐蚀的影响很不显著,耐酸性在NH4Cl浓度为60 g/L时最佳,但当浓度为30 g/L以上时对性能改善不大;温度和时间的提高对各指标影响较显著,但温度达85 ℃后影响较小;反应时间超过40 min后对抗腐蚀性能的提高作用有限。

由以上得到着色最佳配方及工艺条件:15 g/L (NH4)2MoO4,30 g/L NH4Cl,8 g/L H3BO3,8 g/L KNO3,85 ℃,40 min。

2.2 膜层外观

以最佳工艺条件处理铝合金表面,得到了纯黑、表面平整光滑、附着力强的黑色膜,图3为铝合金铆钉经本工艺化学着色前后的对比。

着色膜表面仅有少量分布的白色针孔,图4是铆钉着色后的圆柱体某区域放大10倍的状态,椭圆内的白点即为针孔,是由成膜过程中铝合金表面不同部位构成电极发生电极反应所产生的。

电极反应式如下[4]:

阳极: Al→Al3++3e

阴极: 2H++2e→H2

undefined

由上式和文献[4]的分析可知,铝的表面形成了由铝的氧化物、氢氧化物和钼的氧化物组成的钼酸盐转化膜。着色膜上的针孔口有析出的白色粉状固体物质,分析发现含有Al,O等元素,是化学反应通道内生成的白色氧化物。着色膜如果经过封闭处理,可获得相当好的保护性能。

2.3 膜层耐腐蚀性

2.3.1 腐蚀宏观形貌

图5是3组铝合金铆钉试样在常温置换氧化配方与本配方下着色后,膜的耐酸性、碱性、盐雾腐蚀结果。

在耐酸试验中:常温置换氧化试样上可见较多的灰白色区域,说明着色膜已经成片脱落;而本工艺试样分布白色的小圆斑,且数量较少,可见本配方着色膜的耐酸性较好。

在耐碱试验中:常规氧化试验上仅小部分区域残存着色膜,大部分已经被腐蚀露出基体;而本工艺着色膜基本完整,但颜色稍淡,也分布有局部的小直径腐蚀点。在相同的试验时间下,通过测定铆钉表面着色膜未腐蚀方格的百分数,得到前者的腐蚀面积是后者的3倍,可见前者耐碱腐蚀能力很差,后者的耐碱性优势十分明显,是前者的3倍。

在耐盐雾试验中:常规氧化试样的耐蚀性也明显差于本工艺试样,在同一试验时间下,常规氧化试样着色膜的腐蚀面积是本工艺试样的1.5倍,后者耐盐雾腐蚀能力明显强于前者。

综上可见,本工艺制备的着色膜具有良好的抗各种腐蚀介质的性能。

2.3.2 耐蚀机理

(1)耐酸试验中,常温置换氧化着色的着色膜主要成分为CuO,与HCl作用而发生溶解腐蚀:

CuO+2HCl=CuCl2+H2O

本配方着色膜主要由钼和铝的氧化物或氢氧化物构成,在膜的形成过程中出现不同的颜色,可见是致密光干涉膜Al2O3,而Al,Mo的氧化物电极电位均高于CuO,与HCl的反应非常微弱。因此,本工艺着色膜的耐酸腐蚀性能优于常温置换氧化着色膜。

(2)耐碱腐蚀试验中,常温置换氧化着色膜中的主要成分CuO在NaOH水溶液中会少量离解出Cu2+,与NaOH发生反应生成疏松的Cu(OH)2而成片脱落:

undefined

而本工艺着色膜以钼的氧化物为主,膜的惰性较高,总体的抗碱腐蚀能力强于氧化铜膜,又由于气密性较好,在碱性腐蚀试验中表现良好的抗蚀能力。

(3)耐盐雾性方面,在5%NaCl溶液中,氧化钼的腐蚀电位高于氧化铜的,更不容易发生点腐蚀。因此,本工艺得到的着色膜更加耐盐腐蚀。

3 结论

(1)优选出的铝合金铆钉着色最佳工艺:15 g/L (NH4)2MoO4,30 g/L NH4Cl,8 g/L H3BO3,8 g/L KNO3,85 ℃,40 min。