均值算法

均值算法（精选9篇）

均值算法 篇1

为了对数字化的图像信息进行某些运算或处理, 使图像的质量达到人们所要求的预期效果, 必须对图像进行增强处理。本文所要浅谈的均值滤波算法是空域增强中的一种很常用的方法, 在此次实验中我们对这种算法进行了相关改进, 使得图像失真度较低。

1 均值滤波简介

邻域均值法是一种线性的算法, 包括非加权邻域平均法和加权邻域平均法。

1.1 非加权邻域平均法

最简单的邻域平均法为非加权邻域平均, 大小为N*N的图像f (i, j) , 用邻域平均法得到的平滑图像为g (x, y) , 则

s为 (x, y) 邻域像素中坐标的集合, 其中不包括 (x, y) , M表示集合中s内像素的总数

常用的邻域为4-邻域, 和8-邻域, 如下图所示:

非加权邻域的平均法, 可以用模板卷积求得, 如下表所示:模板中系数w (0, 0) 应位于图像对应于 (x, y) 的位置, 在图像中的点 (x, y) 的位置, 用该模板得到的响应为:

1.2 加权邻域平均法

加权邻域平均与非加权邻域平均原理基本相同。只不过所有模板系数可以有不同的权值, 如下的3*3模板:

对于一幅M*N的图像, 经过一个m*n (m, n均为奇数) 的加权平均值滤波过程, 可用下式给出:

式中a= (m-1) /2且b= (n-1) /2

1.3 局限性分析

在均值滤波中, 每一像素点都要被窗口均值所代替, 如果对均值分析得不够细致, 再加上窗口所包含的像素点有可能既包含边缘又包含区域, 图像边缘就容易变得模糊, 并不能理想地达到去除噪声同时保鲜边缘的目的。

2 改进的均值滤波算法

普通的均值滤波比较理想化, 没有对边界进行过多考虑, 所以图像处理结果总是不能达到满意的效果。如果对于每一像素点, 能考虑到它与周围邻域像素的关系, 考虑到每个像素点在其周围不同的方向其灰度值以不同的速度发生着变化, 则可以进一步使算法得到增强, 在一定程度上提高处理效果。

改进的算法过程如下所示:

(1) 以目标像素点为中心, 选取一个尺寸为奇数的矩形窗口, 并选择其邻域的8个方向的像素灰度值为Di (i=1, 2, 3, 4, 5, 6, 7, 8) (包括中心像素, 且设中心像素的灰度值为Ic) 。

(2) 对目标像素, 进行加权处理。设中心像素的权值为w, 其余8个方向的像素的权值为wi (i=1, 2, 3, 4, 5, 6, 7, 8) (。

(3) 处理后中心像素灰度值为Ic= (∑Di*wi+w*Ic) / (w+num (wi) ) (num (wi) 表示8个方向的像素的权值总和)

(4) 对于目标图像的每个像素点不断重复以上过程。

实验处理了一幅添加高斯噪声的lena图像, 并以改进算法的3*3和5*5模板为例, 其模板如下:

3 实验结果分析

利用普通均值滤波及其改进算法进行相关实验, 结果如下:

由结果图得知:添加高斯噪声的图像经过非加权邻域平均算法的5*5窗口处理后, 已经可以看出明显模糊;而经加权邻域平均算法的3*3模板和5*5模板处理后, 图像都有些偏白。综合可知, 改进后均值滤波算法处理的图像与普通均值滤波算法所处理的图像相比, 模糊度较低, 与原图像相比失真程度较小。

4 结论

经验证, 本实验提出的改进算法对图像边缘保护性较好, 使图像失真度大大降低, 比普通均值滤波算法有着明显的优势。特别是新算法考虑了每个像素点在八个不同的方向, 以目标像素点为中心像波一样发生着微小变化, 考虑更加细致严谨, 有相当大的实际意义, 可以在以后的数字图像处理过程中进行推广。

参考文献

[1]周品, 李晓东.MATLAB数字图像处理.北京:清华大学出版社[M], 2012, 8.228-231

[2]牛秀琴.改进的邻域均值滤波去噪算法研究.长治学院学报[J], 2012, 4: (3) .

[3]张旭, 陈树越.一种基于统计特性的邻域均值滤波算法.科技情报开发与经济[J], 2005.

[4]双娜.数字图像中平滑去噪技术研究及实现[J].现代计算机.2010, 6.

均值算法 篇2

xy+1/xy≥17/

41=x+y≥2√(xy)

得xy≤1/4

而xy+1/xy≥

2当且仅当xy=1/xy时取等

也就是xy=1时

画出xy+1/xy图像得

01时，单调增

而xy≤1/4

∴xy+1/xy≥(1/4)+1/(1/4)=4+1/4=17/4

得证

继续追问：

拜托，用单调性谁不会，让你用均值定理来证

补充回答：

我真不明白我上面的方法为什么不是用均值不等式证的法二：

证xy+1/xy≥17/4

即证4(xy)²-17xy+4≥0

即证(4xy-1)(xy-4)≥0

即证xy≥4，xy≤1/4

而x,y∈R+，x+y=

1显然xy≥4不可能成立

∵1=x+y≥2√(xy)

∴xy≤1/4，得证

法三：

∵同理0

xy+1/xy-17/4

=(4x²y²-4-17xy)/4xy

=(1-4xy)(4-xy)/4xy

≥0

∴xy+1/xy≥17/4

试问怎样叫“利用均值不等式证明”，是说只能用均值不等式不能穿插别的途径?!

二、已知a>b>c，求证：1/(a-b)+1/(b-c)+1/(c-a)>0

a-c=(a-b)+(b-c)≥2√(a-b)*(b-c)

于是c-a≤-2√(a-b)*(b-c)<0

即：1/(c-a)≥-1/【2√(a-b)*(b-c)】

那么

1/(a-b)+1/(b-c)+1/(c-a)

≥1/(a-b)+1/(b-c)-1/【2√(a-b)*(b-c)】

≥2/【√(a-b)*(b-c)】-1/【2√(a-b)*(b-c)】=(3/2)/【2√(a-b)*(b-c)】>0

三、1、调和平均数：Hn=n/(1/a1+1/a2+...+1/an)

2、几何平均数：Gn=(a1a2...an)^(1/n)

3、算术平均数：An=(a1+a2+...+an)/n4、平方平均数：Qn=√(a1^2+a2^2+...+an^2)/n这四种平均数满足Hn≤Gn≤An≤Qn的式子即为均值不等式。

概念：

1、调和平均数：Hn=n/(1/a1+1/a2+...+1/an)

2、几何平均数：Gn=(a1a2...an)^(1/n)

3、算术平均数：An=(a1+a2+...+an)/n4、平方平均数：Qn=√

这四种平均数满足Hn≤Gn≤An≤Qn

a1、a2、…、an∈R+，当且仅当a1=a2=…=an时劝=”号

均值不等式的一般形式：设函数D(r)=^(1/r)(当r不等于0时);

(a1a2...an)^(1/n)(当r=0时)(即D(0)=(a1a2...an)^(1/n))

则有：当r注意到Hn≤Gn≤An≤Qn仅是上述不等式的特殊情形，即D(-1)≤D(0)≤D(1)≤D(2)

由以上简化，有一个简单结论，中学常用2/(1/a+1/b)≤√ab≤(a+b)/2≤√

方法很多，数学归纳法(第一或反向归纳)、拉格朗日乘数法、琴生不等式法、排序不等式法、柯西不等式法等等

用数学归纳法证明，需要一个辅助结论。

引理：设A≥0，B≥0，则(A+B)^n≥A^n+nA^(n-1)B。

注：引理的正确性较明显，条件A≥0，B≥0可以弱化为A≥0，A+B≥0,有兴趣的同学可以想想如何证明(用数学归纳法)。

原题等价于：((a1+a2+…+an)/n)^n≥a1a2…an。

当n=2时易证;

假设当n=k时命题成立，即

((a1+a2+…+ak)/k)^k≥a1a2…ak。那么当n=k+1时，不妨设a(k+1)是a1，a2，…，a(k+1)中最大者，则

ka(k+1)≥a1+a2+…+ak。

设s=a1+a2+…+ak，{/(k+1)}^(k+1)

={s/k+/}^(k+1)

≥(s/k)^(k+1)+(k+1)(s/k)^k/k(k+1)用引理

=(s/k)^k*a(k+1)

≥a1a2…a(k+1)。用归纳假设

下面介绍个好理解的方法

琴生不等式法

琴生不等式：上凸函数f(x)，x1,x2,...xn是函数f(x)在区间(a,b)内的任意n个点，则有：f≥1/n*

设f(x)=lnx，f(x)为上凸增函数

所以，ln≥1/n*=ln

即(x1+x2+...+xn)/n≥(x1*x2*...*xn)^(1/n)

均值不等式的应用 篇3

关键词：均值不等式；n次多项式；基本元素

设a1，a2，…，an∈R+，n∈N且n＞1，则■≥■（*）

（当且仅当a1=a2=…=an，时，“=”成立）

利用（*）式，能解决数学中许多诸如不等式、函数最值等问题。本文重在探究如何应用（*）式去解决一类关于n次多项式的不等式的证明问题.

为研究问题方便，不妨称满足（*）式中的a1，a2，…，an为基本元素，由这些元素构成的和式a1+a2+…+an与积式a1a2…an称为基本式.

一、所涉及的命题中，明显含有a1+a2+…+an和a1a2…an等基本式，可选用a1，a2，…，an为基本元素，直接利用（*）式证明

例1：设a1，a2，…，an∈R+求证（a1+a2+…+an）（■+■+…+■）≥n2

分析：由于题目中明显含有和式（a1+a2+…+an）与 （■+■+…+■），故可选ai和■（i=1，2，3，…，n）为基本元素，由（*）式着手解决。

简证：选ai和■（i=1，2，3，…，n）为基本元素，由均值不等式可得，a1+a2+∧+an≥n■（1）

■+■+∧+■≥n■（2）

（1）×（2）：（a1+a2+…+an）（■+■+…+■）≥n2 证毕.

例2：设a1，a2，…，an为不相等的正数，且S=a1+a2+…+an，

试证：■+■+…+■＞■

分析：题目中，明显含有和式■+■+…+■，故可选■（i=1，2，…，n）为基本元素，再利用均值不等式解决。

简证：选■（i=1，2，…，n）为基本元素，由均值不等式得：

■（■+■+…+■）＞■（1）

考虑（1）式根号内的分母，选s-ai（i=1，2，…，n）为基本元素，再由均值不等式得：

■＞

■，

又由已知S=a1+a2+…+an，所以■＞■，（2）

（1）×（2）：■（■+■+…+■）＞■=s

所以■+■+…+■＞■

由以上证明发现，巧妙选定基本元素■和s-ai是证明这个命题的关键。

二、所涉及的命题形式中，不能明确体现基本元素 a1，a2，…，an，此类题目较难.解决这类问题的关键是根据命题的形式与特点，利用以前所学过的数学知识，设法分离出满足（*）式基本元素a1，a2，…，an，再利用均值不等式解决

例3.设n∈N且n＞1，求证n！＜■n

分析：考虑到，n！=1·2·3…n，我们选1，2，3，…，n为基本元素，利用均值不等式着手解决。

简证：因为n！=1·2·3…·n，所以可选1、2、3、…n为基本元素

由（*）式■＞■，即：■＞■ ∴n！＜■n

通过拆分n！，继而发现基本元素1，2，3，…，n，再利用均值不等式入手解决，这样使看来无法下手的問题，变得有章可循，有法可依，证明起来轻松异常。

例4.设n是大于1的自然数，求证：2n-1＞n■

分析：据等比数列求和公式知，2n-1=1+2+22+…+2n-1，所以可选1，2，22，…，2n为基本元素，由均值不等式着手解决。

简证：由（*）式：1+2+22+…+2n-1＞n■ 可得：2n-1＞n■

所以2n-1＞n■.证毕。

由证明发现，通过把2n-1拆分为1+2+22+…+2n-1 使毫无思路，难于下手的不等式问题通过均值不等式迎刃而解。

三、所涉及的命题中明显含有“式子的n次方”，我们可将它转化为“ｎ个式子的乘积”，使之出现基本式a1a2…an，进而确定基本元素a1，a2，…，an，再利用均值不等式解决

例5．设n为大于1的自然数，且０＜x＜1，证明：1+■n+1≥1+■n

分析：考虑到，1+■n＝1×1+■×1+■×…×1+■，可选1和n个1+■作为基本元素，再利用均值不等式解决。

简证：由于1+■n＝１×■，所以，利用均值不等式，■≥■，即■≥■也即1+■≥■，两边开n次方得：1+■n+1≥1+■n，命题得证。

此例的证明方法很多，比如常见的构造函数法，都比较麻烦。采用均值不等式证明，思路清晰，简明易懂，令人耳目一新！证明的关键是，由拆分“式子的n次方”进而去发现“基本元素”，再由均值不等式着手完成。

例6.设m、n、r为正整数且两两不等，求证：■m+n+r＞mmnnrr

分析：拆分■，■，■，可选m个m，n个n，r个r （总共有（m+n+r）项）为基本元素，再利用均值不等式解决.

证明：由（*）式：＞■＞

■

（上式中m个m，n个n，r个r相加）

即■＞■，两边式子都进行（m+n+r）次方，

所以■m+n+r＞mmnnrr.命题得证。

均值算法 篇4

FCM算法是1974年由Dunn提出并由Bezdek加以推广的模糊C-均值 (fuzzy c-means 简称FCM) 算法[1]。模糊C 均值算法 (FCM) 是基于模糊集理论的一种聚类方法, 有着广泛的应用。近年来, 将遗传算法引入聚类分析是一个新的方向, 文献[2,3]对基于遗传算法的聚类分析进行了介绍。

1 遗传算法描述

遗传算法模拟自然界的演化进程, 采用优胜劣汰的原则, 利用选择、交叉、变异等遗传操作寻找最优个体, 具有很强的搜索能力, 在许多方面都获得了成功的应用。目前对将遗传算法应用到聚类中已经做过很多研究[4], 但遗传算法仍然存在一些缺陷, 如局部搜索能力差, 容易陷入早熟, 效率不高, 还面临着与计算复杂度相关的一些问题。选择和交叉操作都与个体的编码设计相关, 有的个体设计得比较容易进行交叉操作, 然而其适应度函数的计算就会比较复杂, 使选择操作进行起来不太容易;因此, 选择和交叉操作在计算复杂程度上是互补的, 现将模糊C-均值算法引入到遗传算法的进化中, 代替遗传算法的交叉操作。虽然模糊C-均值算法对初始条件敏感, 容易陷入局部最优解, 但将FCM操作代替标准遗传算法中的交叉操作, 弥补了FCM算法和遗传算法各自的缺点。

1.1 目标函数

对有n个对象的集合进行划分成为C个类, 每个对象都是d维向量, 最终使目标函数——总类内差异TWCV最小化, 给出定义如下:n个对象组成的集合{xi, i=1, 2, …, n}, xij表示对象xi的第j个属性。对于i=1, 2, …, n;c=1, 2, …, C。

若第i个对象属于第c个类

$W{}_{ic}=\{\begin{array}{l}1‚\text{若}\text{对}\text{第}i\text{个}\text{对}\text{象}\text{属}\text{于}\text{第}c\text{个}\text{类}\\ 0‚\text{其}\text{他}\end{array}(1)$

对于矩阵W=[wij], wij={0, 1}且${\displaystyle \sum _{j=1}^C}$wji=1 (2)

第c个类的质心Vc={Vc1, Vc2, …, Vcd}。

其中Vcj=$\frac{{\displaystyle \sum _{i=1}^{n}w}{}_{ic}x{}_{ij}}{{\displaystyle \sum _{i=1}^{n}w}{}_{ic}}(3)$

第c个类的类内差异定义为:

S (c) (W) =${\displaystyle \sum _{i=1}^{n}w}{}_{ic}{\displaystyle \sum _{j=1}^d(}x{}_{ij}-v{}_{cj}){}^2(4)$

总类内差异定义为:

S (W) =${\displaystyle \sum _{c=1}^C}$S (c) =${\displaystyle \sum _{c=1}^C}{\displaystyle \sum _{i=1}^n}$wic${\displaystyle \sum _{j=1}^d}$ (xij-vcj) 2 (5)

1.2 遗传PCM算法流程图与算法步骤

遗传快速FCM算法的处理流程是从初始化包含M个个体的种群P0对于每一代种群Pi, 经过选择、变异和快速FCM操作后, 得到新一代的种群, 这一过程重复进行G次。在执行选择操作之前, 找出目前的最佳个体并将其存入S0中, 最后S0作为最终的迭代结果输出 (图1) 。

遗传FCM的算法步骤:

(1) 编码

设n个d维对象要分为c个类, 用S={S1, S2, …, Sn}表示解个体的结构, S为1×n维的行向量, 这里Si{1, 2, …, k}表示第i位的等位基因, 当Si=c时表示第i个样本属于第c个类;编码形成的个体长度为n, 个体上每个基因位的值是{1, 2, …, C}中的一个数值, 每个基因对应一个对象, 它的值表示该对象所属类的类编号, 因为对于所有i, 只有唯一的c, 使wic=1 (由式 (1) 可见) , 所以这个值也是唯一的。遗传快速FCM算法的种群由M (种群规模) 个编码后的个体所组成。

(2) 初始化

随机选择初始群p (0) , 将个体的每个基因随机确定一个值, 该值是从集合{1, 2, …, C}中随机选取的一个数, 即将每个对象随机赋给一个类。由此可能得到一些“非法串” (非法串表示个体中的某些类中没有包含任何对象) , 因为当类的个数越少时, TWVC的值就会越大, 所以出现空类不是所期望的, 应该避免非法串的出现。

(3) 适应度函数的确定

每个个体Sw的适应度值取决于该个体总的类内差异TWCV。因为实行聚类的目的是要使TWCV最小化, TWCV值较小的个体有较大的适应度值。关于适应度函数的定义有多种[5], 这里将适应度函数f (Sw) 定义如下

令f (SW) =TWCV (SW) (6)

$g(S{}_W)=F(S{}_W)-(\overline{F}-k\sigma )(7)$

这里$\overline{F}$和σ分别表示当前群所有个体的f (Sw) 的平均值和标准偏差;k表示在1到3之间的常量。于是个体串Sw的适应度值F (Sw) 为

$F(S{}_w)=\{\begin{array}{cc}g(S{}_W)‚& \text{若}g(S{}_W)\ge 0\\ 0‚& \text{其}\text{他}\end{array}$

(8)

(4) 选择

个体是否被选择依据其适应度值的大小, 适应度小的个体被选择的概率也小, 并可能被淘汰, 而适应度大的个体被选择的概率也大。选择操作采用了 J.Holland教授提出的轮盘赌方式进行, 按照以下给定分布概率从先前的种群中随机选择个体, 重复进行了多次, 直到个体数目满足了预定的种群规模。

P (Si) =$\frac{F(S{}_i)}{{\displaystyle \sum _{j=1}^{{\rm N}}F}(S{}_j)}$ (9)

F (Si) 表示在种群中Si的适应度值

(5) 变异

变异操作是根据每个对象与各聚类中心的距离对个体中相应基因位的值进行改变, 使种群朝着更优的方向进化。对于解空间中的个体, 每个基因位都对应于一个对象, 其值对应该对象所属类的类编号。如果一个对象离某个类中心的距离更近, 那么个体中对应此对象的基因位变异为这个类编号的概率就大。令Sw (i) 表示个体Sw对象xi所对应的基因位;dj=d (xi, vj) 为对象xi与类中心vj之间的Euclidean距离。每个基因位Sw (i) 在用户所定义的变异概率Pm的作用下 (0<Pm<1) 根据下式计算所得的概率使基因位的值发生变异

Pj=Pr{SW (i) =j}=$\frac{k{}_{m}d{}_{\max }-d{}_j}{{\displaystyle \sum _{i=1}^{C}k}{}_{m}d{}_{\max }-d{}_i}$ (10)

km是一个不小于1的常量;dj=max (dj) 是对象xi与各个类中心的最大距离。

(6) FCM操作

由于选择和变异操作是基于概率的, 因此选择与变异操作可能要以花费较多的时间为代价, 收敛到全局最优解。而且, 变异概率只能是一个较小的值, 因为变异概率Pm较大, 容易造成算法的振荡而退化为随机搜索。为了改善这种情况, 同时提高收敛速度, 引入了快速FCM算法中的一个操作步骤, 替换遗传算法中复杂的交叉操作, 最终得到TWVC最小的最优解。

2 实验与结论

为了测试本文算法的优越性, 实验选用Iris (尾属植物) 作为测试样本集。Iris数据集包含了150个样本, 分为三类不同的花: setosa、versicolor、virginica;每类花包含50个样本。对于遗传FCM算法, 实验设初始群大小M=150, 变异概率Pm=0.01, 终止代数T=100, 聚类个数c=4, 进化代数T=100。将基于模糊C-均值与遗传FCM进行比较, 结果表1所示。

遗传算法和模糊C-均值各具特点, 本文提出的将两种算法结合在一起, 模糊C-均值操作提升了遗传FCM算法的收敛速度, 变异操作保证了算法的全局搜索特性, 使算法得到最优解。

参考文献

[1]Bezdek J C.Pattern Recognition with Fuzzy Objective Function Algo-rithms.New york:Plenum Press, 1981

[2]孙志胜, 曹爱增, 梁永涛.基于遗传算法的聚类分析及其应用.济南大学学报, 2004;18 (2) :127—129

[3]戴晓晖, 李敏强, 寇纪凇.基于遗传算法的动态聚类方法.系统工程理论与实践, 1999; (10) :108—110

[4]陈金, 书岗.遗传+模糊C-均值混合聚类算法.电子与信息学报, 24;210—215

[5]Goldberg D.Genetic Algorithm in Search, Optimization and Machine Learning Wesley, Readizlg, MA, 1989

均值算法 篇5

聚类分析[1]是模式识别和数据压缩领域中一种重要的非监督学习过程,其目的是将若干特征相似的特征模式划分到一个集合,每个集合的特征模式之间按照某种度量来衡量相似程度,使得同一个集合内的数据对象具有较高的相似度,而不同集合中的数据对象间的相似度尽可能小,数据对象间特性差异的大小通常是借助于某一距离空间中的距离概念来刻划的。在现有的聚类算法中,K-均值算法以其简单和高效占有重要地位[2]。但因K-均值算法在寻找聚类中心的过程中采用了启发式方法,使得该算法对初始聚类中心的选择较为敏感,易于陷入局部最优解。尤其在大矢量空间中,这种算法的性能会变得更差[3,4]。美国Holland教授于1975年提出了一种全局优化自适应概率搜索算法—遗传算法(GA)[5,6]。该算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化搜索算法,具有较强的鲁棒性和全局寻优的能力,但基于遗传的K均值算法(GA-K均值算法)存在前期过早收敛而后期收敛慢的缺点[7]。本文借助免疫机制的优点[8],将免疫原理的选择操作机制引入遗传算法中,提出基于改进遗传算法的K-均值聚类算法。该算法结合K-均值算法的高效性和局部搜索能力,以及改进遗传算法的全局优化能力,达到了较好的聚类效果。

1 基于改进遗传算法的K-均值聚类算法

遗传算法在解决实际问题时,目标函数和约束条件作为抗原输入,随机产生初始抗体群,并通过一系列遗传操作及个体浓度的计算,在保持抗体多样性的情况下找出针对该抗原的抗体。本研究借助免疫机制来调整选择概率,以优化初始聚类中心,同时,在种群进化过程中,自适应动态调节交叉概率和变异概率,避免了早熟现象的发生。具体步骤如下:

1.1 染色体编码及种群初始化

染色体编码有很多方式,聚类分析中常用的是基于聚类中心的浮点数编码和基于聚类划分的整数编码。根据聚类样本的高维性和数量大的特点,本文采用浮点数编码。初始种群的产生采用随机生成,方法为:假设随机从样本空间中选K个样本作为聚类中心,其它样本随机分到这K个聚类中,并计算各个聚类的聚类中心作为初始个体的染色体编码,最后增加一位该个体所对应的适应度,即1条染色体可以用长度为(K+1)个基因位组成的浮点码串S=Z1Z2…Zkf表示,重复进行psize次(psize为种群大小),得到初始种群。

1.2 染色体适应度的选取

根据染色体的构成,采用的适应度函数为

$f=\frac{1}{k}\times \frac{E{}_1}{E{}_k}\times D{}_k$

上式中:k为聚类类别数;是簇内距离;是簇间距离。,计算公式分别为

$E{}_k={\displaystyle \sum _{j=1}^k{\displaystyle \sum _{x{}_i\in {\rm I}{}_j}\parallel x{}_i-c{}_j\parallel }}{}^2$

上式中:xi表示类簇Ij中的样本;cj表示类簇j的中心。这样定义考虑了簇内聚类最小的原则。

$D{}_k=\underset{i‚j=1}{\overset{k}{{\displaystyle max}}}\parallel c{}_i-c{}_j\parallel$

上式中:ci,cj分别为簇i,j的中心。这样定义考虑了簇间距离最大的原则。

适应度函数受3个因素影响,即1/k,E1/Ek及。第一个因素减少的时候,另外两个因素随着k的增加而增加,所以这个适应度函数表达的内涵是在所分类别数尽可能小的情况下提高聚类的紧凑度和分离程度。

1.3 选择操作

针对基于遗传算法的聚类算法在算法开始前期收敛速度快,而后期由于各条染色体的个体差异变小使收敛速度变得很慢,本研究采用一种基于免疫原理[6]的选择操作和比例适应度分配方法相结合的混合选择算子计算个体被选中的概率以克服上述缺点。

定义1 个体浓度:

$d=\frac{\text{群}\text{体}\text{中}\text{相}\text{同}\text{个}\text{体}\text{的}\text{数}\text{目}(m)}{\text{群}\text{体}\text{大}\text{小}(p{}_{size})}$

找出群体中个体浓度最大的m个个体,设为1,2,…,m,则这m个个体的个体浓度概率为$p{}_d=\frac{\left(1-d\right)}{p{}_{size}}$,其余的个体浓度概率为,所有个体的浓度概率之和为1。

设某一个个体的适应度为fi,该个体被选中的概率为pfi,则

$p{}_{f{}_i}=\frac{f{}_i}{p{}_d\times {\displaystyle \sum _{j=1}^{p{}_{size}}f}{}_i}$

式中:i=1,2,…,psize。

此种选择策略有两个优点:一是个体适应度越大,则选中的概率越大,加速了算法的收敛;二是个体浓度越大则被选择的概率越小,起到抑制作用,保证了进化群体中个体的多样性,避免过早收敛。

1.4 交叉操作

标准遗传算法由于在进化过程中采用固定的交叉概率和变异概率,已经被证明无法收敛到问题的全局最优解,容易出现早熟现象,后期还会因为个体差异的减小出现收敛速度缓慢的现象。鉴于此,本研究按照一定的交叉概率采用最邻近法则进行交叉操作。首先对交叉概率和变异概率做出如下约定:当群体适应度比较集中时,使得交叉概率Pc和变异概率Pm增大;当群体适应度比较分散时,使得交叉概率Pc和变异概率Pm适当减小。这样约定能使算法在迭代过程中根据个体的适应度来改变其交叉概率Pc和变异概率Pm,从而在能保护最优个体的同时加速较差个体的淘汰速度,增强了算法的全局搜索能力。其数学模型为:

${\rm P}{}_c=\{\begin{array}{l}{\rm K}{}_1\times \frac{f{}_{max}-f^{\prime }}{f{}_{max}-f{}_{avg}}{f}^{\prime }\ge f{}_{avg}\\ {\rm P}{}_c={\rm K}{}_2{f}^{\prime }＜f{}_{avg}\end{array}$

${\rm P}{}_m=\{\begin{array}{l}{\rm K}{}_3\times \frac{f{}_{max}-f}{f{}_{max}-f{}_{avg}}f\ge f{}_{avg}\\ {\rm P}{}_m={\rm K}{}_{4}f＜f{}_{avg}\end{array}$

式中:K1,K2,K3,K4是小于0的常数;fmax为群体的最大适应度;favg为群体的平均适应度;f′为交叉产生的2个新个体中适应度较大的那个个体的适应度;f为变异个体的适应度值。

采用最邻近法则的基因匹配交叉操作:设待交叉的2条染色体为S1=Z${}_1^{(1)}$Z${}_2^{(1)}$…Z${}_k^{(1)}$和S2=Z${}_1^{(2)}$Z${}_2^{(2)}$…Z${}_k^{(2)}$。对染色体S1的每个基因Z${}_i^{(1)}$

,选择S2中与Z${}_i^{(1)}$距离最近的基因Z${}_j^{(1)}$配对,已经配对的基因不再参加后续的基因配对。再将S2按基因配对的顺序重新排列,得到S*2。最后随机选择交叉点进行单点交叉得到下一代个体S′1和S′2。

1.5 变异操作

变异操作是一种局部随机搜索,与选择、交叉算子结合可以保证算法的有效性。本研究中采用按基因位(一个基因即为一个聚类中心)的维向量来进行,每个基因位的每维向量(一个浮点数)按变异概率Pm来发生随机变异。在整个算法开始之前,先求出每维向量的最大值和最小值,分别保存在向量$vec{\rm M}ax\left[p\right]$与$vec{\rm M}in\left[p\right]$(p为样本数据维数)中,可知所有最优聚类中心的第i(0〈i≤P)维向量的值一定介于$vec{\rm M}in\left[i\right]$与$vec{\rm M}ax\left[i\right]$之间。同时约定随机变异的值应在$vec{\rm M}in\left[i\right]$与$vec{\rm M}ax\left[i\right]$之间。这样既保证了群体的多样性,又可以避免盲目搜索,大大提高了搜索的速度和效率。

1.6 算法终止条件

只要满足以下2个条件中的任意一个条件则算法终止:

(1)算法迭代次数超过设定一个最大的迭代次数maxGen;

(2)运行过程中得到相同的最优结果次数连续超过某一阀值。

本文采用第2个条件作为结束条件。

2 算法描述

给定样本数据集合$D=\left\{d{}_1‚d{}_2‚\cdots ‚d{}_i‚\cdots ‚d{}_n\right\}$,基于改进遗传算法的K-均值聚类算法具体过程描述为

(1)确定要生成的类簇数目k、种群规模为psize个个体及算法结束条件。

(2)先随机选择k个初始聚类中心组成一个个体$C=\left\{c{}_1‚c{}_2‚\cdots ‚c{}_i‚\cdots ‚c{}_k\right\}$,对个体进行染色体编码,总共进行psize次,得到群体为psize个个体,设置初始迭代次数t=0。

(3)对数据集中的每一个样本数据di,依次计算它与各个聚类中心的相似度;将样本数据di合并到与其具有最大相似度的类簇中。

(4)按照相似度公式计算新的类簇的中心,组成一个个体,并计算新个体的适应度;

(5)对所有的个体实施遗传算子,得到下一代的群体;

(6)得到优化后的个体。如果所有聚类中心均达到稳定,则结束;否则,t=t+1,转(3)。

3 试验结果及分析

分别采用 k-均值算法、遗传K-均值算法(GA-K均值算法)和本文算法在VC++和MatlAB环境下进行仿真实验。遗传算法的交叉概率和变异概率初始值分别取为0.75,0.09,群体规模为100,迭代次数为100次,当运行过程中得到最优结果次数连续10次以上时算法结束。实验采用数据是Fisher的Iris 3种植物150样本个数据[9]进行10次试验,每个样本均为四维向量,代表植物的4种属性。三种算法分别单独运行10次,计算出簇内距离Ek与簇间距离Dk的最大值,最小值及平均值。实验结果见表1。

注:以上数据为单个算法运行10次的平均值。

聚类算法的理想结果是同时获得最小的簇内距离和最大的簇间距离。从表1中的数据可以看出,标准的K-均值算法由于对初始中心选取敏感性很大,在初始中心选择不当的情况下易陷入局部最优,出现过早收敛;GA-K均值算法由于个体的多样性不足而常出现早熟现象;本研究提出的算法在全局搜索能力方面优于K-均值和GA-K均值算法,所获得的聚类结果具有更强的稳定性,对于随机分布的数据聚类有明显的优越性;同时从达到最优解迭代次数看,本文提出的算法达到最优解的平均迭代次数要远少于K-均值和GA-K均值算法,所以本文提出的算法收敛速度更快。

4 结束语

本文对遗传算法和K-均值聚类算法进行了研究,针对K-均值聚类效果易受初始聚类中心影响的不足,为克服遗传算法引入K-均值算法所带来的易出现局部早熟的缺点,将免疫机制的选择操作引入遗传算法,使个体浓度和适应度同时对个体的选择操作产生作用,改变以往单纯以适应度来作为个体选择的依据,对算法进行改进,然后将改进的遗传算法引入K-均值算法中以优化聚类中心,提出一种基于改进遗传算法的K-均值聚类算法。试验结果表明,本研究的算法与传统的K-均值算法和GA-K均值算法比较,在全局搜索能力方面优于K-均值和GA-K均值算法,所获得的聚类结果具有更强的稳定性,能够有效改善聚类质量。

参考文献

[1]Jiawei Han,Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社,2005:185-218

[2]Bandyopadhyay S,Maulik U.An evolutionary technique based on k-means algorithm for optional clustering in rn[J].Information Sciences,2002,(146):221-237

[3]Ahmadyfard Alireza,Modares Hamidreza.Combining PSO and k-means to enhance data clustering[A].IST2008International Symposium[C].Tehran:IEEE Press,2008.

[4]Hai-xiang Guo,Ke-jun Zhu,Si-wei Gao,et al.Animproved genetic k-means algorithm for optimal clustering[A].Sixth IEEE International Conference[C].Leipzig:IEEE Press,2006.

[5]李茂军,罗安.单亲遗传算法的机理分析[J].长沙理工大学学报(自然科学版),2004,1(1):76-79

[6]贺志民,方美娥.基于遗传算法的特征值问题求解[J].长沙电力学院学报(自然科学版),2003,18(1)12-14

[7]赖玉霞,刘建平,杨国兴.基于遗传算法的K-均值聚类分析[J].计算机工程2008,34(20):200-202

[8]王磊,潘进,焦李成.免疫算法[J].电子学报2000,28(7):74-78

均值算法 篇6

关键词：Mean Shift,灰色马尔可夫预测模型,几何特征,目标跟踪

Comaniciu等[1]提出的基于Mean Shift的跟踪算法取得了很大成功,并且吸引了越来越多学者的研究兴趣。Mean Shift算法是一种非参数密度估算法,它具有良好的实时性,且对形变、目标遮掩的稳健性良好,易于与其他算法集成,广泛地应用于目标跟踪中。但该算法也存在一定的缺陷,为了解决传统均值偏移算法不能自适应改变核函数带宽的缺陷,Collins等将Lindeberg尺度的空间理论和Mean Shift算法相结合[2],并在某种程度上改善了此缺陷;Li Jinping等提出了采用Level Set描述目标轮廓方法与Mean Shift算法组合进行跟踪,使得在光线变化、目标颜色发生改变时取得好的效果[3],改善了相似颜色干扰问题;为了解决遮挡情况下均值偏移算法的跟踪缺陷,许多学者采用了目标预测结合Mean Shift的跟踪方法,Maggio E等提出了采用粒子滤波结合Mean Shift算法的跟踪[4],取得了好的跟踪效果,但计算量大。

本文在灰色GM(1,1)模型的基础上引入马尔可夫链预测理论,建立运动目标的灰色马尔可夫GM(1,1)预测模型,利用少量的数据来预测目标的运动轨迹,并以当前时刻的目标预测位置作为Mean Shift算法进行迭代搜索的起始位置;利用提取的几何特征表示相似度函数来自适应性地更新搜索窗口,以此减少迭代次数,最后根据模型更新策略来更新目标模拟。

1 Mean Shift算法

Mean Shift算法是一个自适应地寻找概率密度局部最大值的迭代方法。在目标跟踪中,采用归一化的加权颜色直方图来描述目标模型。假定跟踪目标的中心位于x0,xi是d维Euclidean空间Rd中的一组点,用向量表示xi(i=1,2,…,n),使用带宽为h的核函数K(x)作为多变量核密度估计,则目标模型可以表示为

$p{}_u=C{}_h{\displaystyle \sum _{i=1}^{n}k}\left(\left|\left|\frac{\mathit{x}{}_i-\mathit{x}{}_0}{h}\right|\right|{}^2\right)\delta \left[b\left(\mathit{x}{}_i\right)-u\right](1)$

式中:u=1,2,…,m,为目标区域的所有特征值;Ch为归一化常数;${\displaystyle \sum _{u=1}^{m}p}{}_u=1$;δ是Kronecker函数,如果像素属于第u个直方图,该函数值为1,否则为0。

令候选模型的中心坐标为y,则可以描述为

$q{}_u(\mathit{y})=C{}_h{\displaystyle \sum _{i=1}^{n{}_h}k}\left(\left|\left|\frac{\mathit{x}{}_i-\mathit{y}}{h}\right|\right|{}^2\right)\delta \left[b\left(\mathit{x}{}_i\right)-u\right](2)$

pu与qu(y)的相似性用Bhattacharyya系数$\widehat{\rho }$(y)来度量,即

$\widehat{\rho }(\mathit{y})\equiv \rho [p{}_u,q{}_u(\mathit{y})]={\displaystyle \sum _{u=1}^m\sqrt{p{}_{u}q{}_u(\mathit{y})}}(3)$

从式(3)可以看出,两个模型越相似,则$\widehat{\rho }$(y)的值越大,为使其值最大,令yk表示目标的初始位置,将$\widehat{\rho }$(y)在该点进行一阶泰勒展开求导为零,可以得到Mean Shift向量

$\begin{array}{l}\mathit{{\rm M}}{}_h(x)=\mathit{y}{}_{k+1}-\mathit{y}{}_k=\\ \frac{{\displaystyle \sum _{i=1}^{n{}_h}w}(\mathit{x}{}_i)\left(\mathit{x}{}_i-\mathit{y}{}_k\right)g^{\prime }\left(\parallel \frac{\mathit{x}{}_i-\mathit{y}{}_k}{h}\parallel {}^2\right)}{{\displaystyle \sum _{i=1}^{n{}_h}w}(\mathit{x}{}_i)g^{\prime }\left(\parallel \frac{\mathit{x}{}_i-\mathit{y}{}_k}{h}\parallel {}^2\right)}(4)\end{array}$

式中:$w(\mathit{x}{}_i)={\displaystyle \sum _{u=1}^m\sqrt{\frac{p{}_u}{q{}_u(y)}}}\delta [b(\mathit{x}{}_i)-u]$是图像中采样点的权重。在计算(4)式的迭代过程中,若$\parallel \mathit{{\rm M}}{}_h\left(x\right)\parallel \le \epsilon$,则$\widehat{\rho }$(y)的值达到最大,迭代停止;否则总是往$\mathit{{\rm M}}{}_h\left(x\right)$向量的方向移动,搜索满足条件的目标中心坐标来使$\widehat{\rho }$(y)达到最大值,即两模型最相似;最后,目标就从初始位置移动到了真实的目标位置。

2 灰色马尔可夫预测模型

灰色系统预测的概念是由邓聚龙教授首先在国内提出,之后灰色系统理论的研究得到了迅速发展。灰色预测方法的优点在于对缺少基础资料的预测能够得到较好的预测效果,与别的预测方法相比较而言它用到的样本数据较小,而预测的精度相对较高。马尔可夫概率矩阵是对随机过程每个时刻状态的描述,它是根据状态之间的转移概率来预测系统的发展,把在不相同状态范围的内在波动规律展现出来,使随机作用造成的波动得以修正。灰色马尔可夫预测模型就是将两者的优势相结合进行预测。

2.1 建立GM(1,1)模型

假设有原始序列为

x(0)={x(0)(1),x(0)(2),…,x(0)(n)} (5)

将该序列x(0)进行一次累加生成处理,得到x(1)(记作1-AGO)

x(1)={x(1)(1),x(1)(2),…,x(1)(n)} (6)

式中:$x{}^{(1)}(k)={\displaystyle \sum _{i=1}^{k}x}{}^{(0)}(i),k=1,2,\cdots ,n$。

建立GM(1,1)灰微分方程

$\frac{\text{d}x{}^{(1)}}{\text{d}t}+ax{}^{(1)}=b(7)$

式中:a为发展系数;b为灰作用量,是待估参数。

把式(7)转化为矩阵方程

$\mathit{y}{}_n=\mathit{B}\widehat{\mathit{a}}(8)$

$\widehat{\mathit{a}}=[a,b]{}^{\text{Τ}},\mathit{y}{}_n=[x{}^{(0)}(2),x{}^{(0)}(3),\cdots ,x{}^{(0)}(n)]{}^{\text{Τ}}(9)$

$\mathit{B}=[\begin{array}{l}-z{}^{(1)}(2)\\ -z{}^{(1)}(3)\\ ⋮\\ -z{}^{(1)}(n)\end{array}\begin{array}{l}1\\ 1\\ ⋮\\ 1\end{array}](10)$

z(1)(k)=[x(1)(k)+x(1)(k-1)]/2,k=2,3,…,n (11)

由式(8)可得:$\widehat{\mathit{a}}=[a,b]{}^{\text{Τ}}=(\mathit{B}{}^{\text{Τ}}\mathit{B}){}^{-1}\mathit{B}{}^{\text{Τ}}\mathit{y}{}_n$

GM(1,1)模型的离散响应方程为

$\widehat{x}{}^{(1)}(k+1)=[x{}^{(0)}(1)-\frac{b}{a}]\text{e}{}^{-ak}+\frac{b}{a}(12)$

将$\widehat{x}{}^{(1)}(k+1)$计算值作累减还原计算得到原始数据的估计值

$\widehat{x}{}^{(0)}(k+1)=\widehat{x}{}^{(1)}(k+1)-\widehat{x}{}^{(1)}(k)(13)$

以上就是建立运动目标轨迹的灰色GM(1,1)预测模型的基础[5]。

2.2 建立转移概率矩阵

假设将目标的轨迹状态分为m个,即状态空间I={1,2,…,m},fij作为i到j状态经一步转移的数据样本数,与${\displaystyle \sum _{j=1}^{m}f}{}_{ij}$(状态i的所有数据样本数)相除的值定义为“转移概率”,用pij,i,j∈I表示,即有

$p{}_{ij}=\frac{f{}_{ij}}{{\displaystyle \sum _{j=1}^{m}f}{}_{ij}}(14)$

由状态i经k步转到状态j的频率也可以用式(14)来表示,将状态转移概率依次排序,可得到矩阵

$\mathit{p}{}^{(k)}=\left[\begin{array}{cccc}p{}_{11}^{(k)}& \cdots & p{}_{1n}^{(k)}& \\ ⋮& & ⋮& \\ p{}_{1n}^{(k)}& \cdots & p{}_{nn}^{(k)}& \end{array}\right](15)$

式中:${\displaystyle \sum _{j=1}^{n}p}{}_{ij}^{(k)}=1$。

从以上分析可知,灰色GM(1,1)模型用来预测目标轨迹变化的总趋势,对其轨迹状态的修正则是通过马尔可夫转移概率矩阵来完成的,最终精确地预测出目标的位置,为均值偏移算法提供搜索初始位置,避免了由于遮挡造成的目标丢失。

3 Mean Shift算法和灰色马尔可夫模型的结合

跟踪的过程中,会产生一系列的时间序列{yi},i=1,2,…,表示迭代的次数,这种时间序列有平稳收敛(呈递增和递减两种形式分布)和波动收敛(呈交替状分布)两种形式。针对这两种形式,可以采用灰色马尔可夫模型进行目标中心位置的预测。在Mean Shift搜索之前先进行目标在下一帧中位置的初步预测,并用预测中心位置作为目标搜索的起始位置,之后再进行迭代搜索,不仅可以提高搜索准确性,还能够减少迭代搜索次数。灰色马尔可夫模型采用“新陈代谢”更新策略,保证用于预测的数据是最新的,一般用当前帧的前4帧数据作为基本数据,既保证了预测的准确性,也减少计算量。

如图1所示,提取的颜色特征用于传统的Mean Shift算法进行迭代计算,找出最匹配的目标位置,具体过程见本文第2节;利用文献[6]中的迭代投影算法来近视计算目标的面积,通过前后两帧面积的差值来判断是否更新跟踪窗口的大小;再设置一个阀值,根据相邻两帧的目标面积的比值是否小于阀值来判断是否更新目标模型,避免了目标模型过更新。

4 实验结果与分析

本文实验使用的硬件平台为2.53 GHz的CPU、2 Gbyte内存,在Windows7操作系统下的计算机,软件平台为MATLAB 2010a编程环境。测试视频选取一段橄榄球的运动视频序列,视频图像大小为352×288,共88帧。根据反复的实验,选取模板更新阈值为0.2。在整个视频序列中,橄榄球的运动都是随机波动的,前42帧被跟踪的橄榄球从大到小,再从小到大,其大小一直在不断变化;后40多帧发生遮挡情况。

图2为传统的均值偏移算法跟踪的仿真图,当球的大小不断变化时,跟踪窗口不能自适应地调整大小,当球快速运动时,目标窗口的中心位置严重偏移,在42帧发生遮挡时,跟踪失败,跟踪窗口停留在第42帧时的位置。本文算法的仿真图如图3所示,根据灰色马尔可夫模型和均值偏移算法相结合,在球快速运动时能准确地确定目标的中心位置,再根据提取目标的几何特征的变化来改善跟踪窗口的大小,能很好地进行实施跟踪,效果也比传统的均值偏移算法要好;在发生遮挡时,以灰色马尔可夫GM(1,1)的预测值为中心来开窗,避免丢失跟踪目标。从两个仿真图来看,本文提出的算法要优于传统的均值偏移算法,可以取得良好的实时性和稳健性。

5 结论

当在运动目标跟踪的过程中,发生遮挡、多种运动方式存在的情况下,本文提出通过灰色GM(1,1)模型对目标的运动轨迹进行总趋势预测,再用马尔可夫概率转移矩阵来对轨迹进行修正,这样能准确预测出目标在每一帧中的中心位置,并比一般的预测方法计算量小、精度高;再结合Mean Shift算法进行匹配跟踪,最终确定目标。其中通过提取的几何特征的变化来更新跟踪窗口和目标模型,这样可以适应目标的尺度变化和避免了目标模型的过更新。实验表明,该方法能够对目标进行实时有效的跟踪。

参考文献

[1]COMANICIU D,RAMESH V,MEER P.Real-time tracking of non-rigidobjects using mean Shift[C]//Proc.IEEE Conference on Computer Vi-sion and Pattern Recognition 2000.[S.l.]:IEEE Press,2000:142-149.

[2]COLLINS R T.Mean Shift blob tracking through scale space[C]//Proc.IEEE Conference on Computer Vision and Pattern Recognition 2003.[S.l.]:IEEE Press,2003:234-240.

[3]LI J P,LI Q J.Real-time tracking by combining level set and Mean Shift[J].Journal of Information&Computational Science,2008,5(2):829-836.

[4]MAGGIO E,CAVALLARO A.Hybrid particle filter and mean shifttracker with adaptive transition model[C]//Proc.ICASSP 2005.[S.l.]:IEEE Press,2005:221-224.

[5]邓聚龙.灰色系统理论教程[M].武汉:华中理工大学出版社,1992.

均值算法 篇7

数字水印是近几年新兴的技术。而数字水印的研究着重在于健壮性, 真伪辨别, 版权证明, 网络认证, 音频和视频等方面, 最广泛的研究是在于健壮性和可验证性。

目前数字水印的嵌入方法也有很多种, 根据嵌入的算法可以分为两大类:空间域和变换域算法。在空间域算法中, 最典型就是最低有效位 (LSB) 算法, Pathwork算法。最低有效位算法是L.F.Turner和R.G.van Schyndel等人提出的第一个数字水印算法, 是一种典型的空间域信息隐藏的一种算法。直接将水印信息嵌入载体图像的最低有效位, 虽然这种方法实现简单, 但是极易受到攻击而使水印失效。无法满足数字水印信息鲁棒性的要求。Patchwork算法嵌入载体图像的水印信息具有高斯分布特性, 首先随即的选取N对像素点, 然后通过增加像素对中一个点的亮度值, 而相应地降低另一点的亮度值, 从而使得整个图像的平均亮度值保持不变。嵌入的信息量较小, 能见度很低, 鲁棒性很强的数字水印。本文研究的数字水印算法融合这两种算法的优点。

2. 空间域数字水印算法的嵌入

Step1:将载体图像读到对应的矩阵ww中。

Step2:本文采用 (512*512大小的图像) , 把载体图像分为4096个小块, 每块的大小为8*8。

Step3:计算每个小块的平均值NN保存在ME中, 方差保MM保存在CO中。把所有计算出的每块的方差使用sort () 函数进行排序, 结果保存到[CO1, idx1]中 (把方差从大到小排序, 对应的块保存在向量idx1中) 。

Step4:计算水印信息的大小, [p0, q0]=size (water) 。

Step5:通过while语句进行优良载体小块的选取, 循环p0*q0次。

Step6:选取载体中的块保存在b_w=ww_I (8*i3-78*i3, 8*j3-7:8*j3) 中。

Step7:xb_w=bitget (b_w, 4) 选取每个小块中的每位数值的二进制位的第四位进行水印信息的嵌入xb_w保存小块的第四位数值。

如果水印信息和小块的第四位数值相等, 就直接嵌入。

嵌入算法的运行效果如图1所示:

3. 水印信息的提取算法

提取的过程是嵌入过程的逆过程。嵌入的过程是将每个水印信息的嵌入到每个载体块的每一位中, 所以提取算法就是首先选出嵌入水印信息的小块, 进行水印的提取。

Step1:根据嵌入方法选择块的方法进行选择提取的块。

Step2:同样的把的块保存在b_w2, 即b_w2=ww_I (8*i4-7:8*i4, 8*j4-7:8*j4) 。

Step3:把提取的水印信息暂时保存在bk中, 即

www保存了提取的水印信息。

提取算法的运行效果图, 如图2所示:

4. 水印攻击与检测

5. 小结

该方法的主要思想是:在较小改变量的前提下实现最大信息量的嵌入。具体的实现是在载体图像纹理较复杂块的第四位进行水印的嵌入, 通过改变最低的三位的值使其根据水印的数据进行有效调整, 使得载体图像的改变不会引起视觉上的差异。实验结果证明了该算法的简单性和可行性。但是鲁棒性很信息嵌入的强度还有待于进一步的提高。

摘要：数字水印技术是保护多媒体版权的有效手段之一。本文研究的是将载体图像划分成若干小块, 然后按照方差, 均值的标准进行选择优良的块进行数字水印信息的嵌入。反复的实验结果证明了该算法具有很好的隐蔽性, 又具有很理想的鲁棒性。

关键词：空域,均值,方差,数字水印,嵌入,提取

参考文献

[1]金聪, “基于图像投影序列的盲目数字水印鲁棒性检测技术”, 《数字水印理论与技术》, 2008

均值算法 篇8

图像去噪是图像预处理的一个基本内容,与图像处理相关的许多应用如分割、配准、边缘提取等,通常均需要使用有效的去噪算法进行预处理来获得更可靠的效果。因此,图像去噪吸引了大量研究者的关注,其中图像中高斯白噪声的去除一直是图像处理中的一个重要研究方向。

Buades A,Coll B和Morel J M在对许多典型的去噪算法进行比较研究的基础上,提出了非局部均值(non-local means,NLM)去噪算法[1],并将其应用到图像和视频的去噪处理中。NLM算法无论从理论上还是实验上均优于其他经典的去噪方法,如双边滤波[2]、各向异性扩散方程算法[3]和小波的方法[4]。NLM算法是利用图像中的冗余信息,结构相似的像素上叠加的噪声是随机的,所以通过加权平均就可以有效地去除噪声,同时也可以消除传统邻域滤波算法中出现的伪影;但其自身也存在一些不足。NLM算法是利用图像块来表示像素点的特征,并通过图像块之间的相似度来度量像素点之间的相似度;图像块之间的相似度可根据块内灰度值向量空间之间的高斯加权欧氏距离来衡量,然而噪声的存在、特别是当噪声水平较高时,基于块内灰度值向量空间的高斯加权欧氏距离将不能很好地反映原始图像块之间的相似度,因而NLM算法去噪后的图像仍残留了大量的噪声,特别是边缘部分。此外,在NLM 算法去噪时,以参考像素点为中心的图像块要与以图像中所有像素点为中心的图像块或者局部区域中所有像素点为中心的图像块进行比较,计算量非常大。因此,有效改进NLM算法的去噪效果和加快计算速度是对该算法研究的两个重要方面。

为了得到更精确的高斯加权欧氏距离去除图像残留噪声,本文提出基于离散余弦变换(discrete cosine transform,DCT)的非局部均值滤波算法。对测试图像的实验结果表明,相对于NLM算法,该算法能够更为有效地去除噪声,具有更高的峰值信噪比(peak signal to noise ratio,PSNR),去噪图像内容更加清晰。

1 非局部均值去噪算法

设噪声图像为z=x+n,x为未受高斯白噪声污染的原始图像,n为高斯白噪声。对于噪声图像中的任何一个像素,非局部均值利用整幅图像中所有像素值的加权平均来得到该点的估计值,即:

${\rm N}L[z](i)={\displaystyle \sum _{j\in R{}_i}\omega }(i,j)z(j)(1)$

式(1)中,权值ω(i,j)依赖于像素i与j之间的相似度,并满足0≤ω((i,j)≤1且${\displaystyle \sum _j\omega }(i,j)=1$。像素i和j之间的相似度由灰度值矩阵Ni与Nj之间的相似度决定,其中Ni表示以像素i为中心的大小为M×M的方形邻域,虽然理论上参与加权的像素是图像中所有的像素,但为了提高计算效率,往往限定为局部区域的像素。各邻域灰度矩阵之间的权值ω(i,j)通过高斯加权欧式距离来度量,即:

$\omega ((i,j)=\frac{1}{C}\exp \left(-\frac{\parallel z({\rm N}{}_i)-z({\rm N}{}_j)\parallel {}_{2,\alpha }^2}{h{}^2}\right)(2)$

$C{}_i={\displaystyle \sum _j\exp }\left(-\frac{\parallel z({\rm N}{}_i)-z({\rm N}{}_j)\parallel {}_{2,\alpha }^2}{h{}^2}\right)(3)$

其中,Ci是归一化因子,‖·‖2,α是高斯加权的欧氏距离函数,α是高斯核的标准差,h控制着指数函数的衰减速度,决定滤波的程度。

2 离散余弦变换

DCT是一种正交变换,其变换核为实数余弦函数。对一幅图像进行离散余弦变换后,有关图像的许多重要可视信息都集中在DCT变换的小部分低频系数中。因此,其经常在信号处理和图像处理中使用,用于图像压缩、数字水印和信号检测等。

假设给定大小为N×N的二维信号f,其DCT定义为:

$\begin{array}{l}F(u,v)=\frac{2}{{\rm N}}c(u)c(v){\displaystyle \sum _{i=0}^{{\rm N}-1}{\displaystyle \sum _{j=0}^{{\rm N}-1}f}}(i,j)\times \\ \cos \left[\frac{(2i+1)u\text{π}}{2{\rm N}}\right]\cos \left[\frac{(2j+1)v\text{π}}{2{\rm N}}\right](4)\end{array}$

反离散余弦变换IDCT定义为:

$f(i,j)={\displaystyle \sum _{u=0}^{{\rm N}-1}{\displaystyle \sum _{v=0}^{{\rm N}-1}c}}(u)c(v)F(u,v)\cos \left[\frac{(2i+1)u\text{π}}{2{\rm N}}\right]\times$

cos$\frac{(2j+1)v\text{π}}{2{\rm N}}](5)$

式(5)中

正是由于离散余弦变换具有很强的“能量集中”特性,可以由通过少量低频DCT系数进行重构得到的重构图像代替噪声图像计算图像块之间的相似度权重值。如图1所示,(a)为加入10%高斯白噪声的噪声图像,(b)为由28%的低频DCT系数重构的重构图像。由图1可知,通过少量低频DCT系数进行重构得到的重构图像能够保护图像的主要内容,并且能够滤除部分噪声。

3 基于离散余弦变换的非局部均值算法

对大小为N×N的二维噪声图像f,其基于散余弦变换的非局部均值算法的具体流程如下:

(1)DCT变换:对噪声图像f进行DCT变换,F=DCT(f),F为经DCT变换后的频域信息。

(2)低频系数:定义大小N×N、值为0的矩阵F1,从F中通过Zigzag扫描选取28%低频DCT系数,赋给F1。

(3)IDCT变换:对低频系数矩阵F1进行IDCT变换得到重构图像,f1=IDCT(F1),f1为经IDCT变换后得到的重构图像。

(4)NLM算法:通过f1计算图像块之间的相似度权值ω(i,j),将NLM算法用于噪声图像f进行去噪处理,f2=NLM(f),f2为最终的滤波结果图像。

4 实验结果与分析

为了验证算法的有效性和可行性,现在Matlab7.0环境下以大小为128×128的Lena、Peppers图像作为测试图像对本文算法进行仿真实验,为了使不同算法具有可比性,根据文献[5,6,7,8,9,10]的大量研究和测试,搜索窗口范围为11×11,像素邻域大小为7×7,滤波参数h=12σ( σ为所加噪声的标准差)。

本文采用峰值信噪比PSNR作为评价的客观准则对不同算法进行比较,峰值信噪比定义为:

PSNR=10lg(2552/MSE) (6)

式(6)中,MSE为均方差。图2所示为被标准差分别为25和50的高斯噪声污染的Lena、Peppers图像,图3所示为不同算法对被标准差为25的高斯噪声污染的图像的去噪效果,图4所示为不同算法对被标准差为50的高斯噪声污染的图像的去噪效果。从整体上来看,本文算法去噪图像的主观视觉效果好于NLM算法和文献[5]的算法,有更少的模糊现象,保留了更多的边缘与细节信息。

表1给出了采用NLM算法、文献[5]算法及本文算法对被标准差为5、10、15、20、25、30、40、50的高斯白噪声污染的图像去噪后的PSNR。当噪声的标准差σ=5时,本文算法去噪图像的PSNR高于NLM算法,但略低于文献[5]算法;当噪声的标准差σ>5时,本文算法去噪图像的PSNR均不同程度的超过文献[5]算法及NLM算法。

5 结论

在分析传统滤波算法和一些改进算法的基础上,提出了一种基于离散余弦变换的非局部均值滤波算法。首先,利用DCT的低频系数重构图像,以达到滤除部分噪声的同时保护图像的主要内容。其次,利用重构图像较准确块计算图像块之间的欧氏距离,将NLM去噪算法用于噪声图像。仿真结果表明,较NLM算法,本文算法去噪后的图像视觉效果得到了较好的改善,并能够保留大量的细节信息;当噪声标准差σ大于5时,本文算法去噪效果提高更加明显。

摘要：要非局部均值(non-local means,NLM)去噪算法已成为较有效去除图像噪声的算法之一。然而,当噪声水平较高时,NLM不能准确地计算图像块之间的相似度权重值,影响图像的去噪效果。针对上述问题,结合离散余弦变换(discrete cosinetransform,DCT)提出了基于DCT的非局部均值滤波算法。首先,利用DCT的低频系数重构图像,以达到滤除部分噪声的同时保护图像的主要内容。其次,利用重构图像较准确地计算图像块之间的相似度权重值,将NLM去噪算法用于噪声图像。实验结果表明,该算法能够得到较高的峰值信噪比(peak signal to noise ratio,PSNR)和更好的视觉效果。

关键词：图像去噪,非局部均值(NLM),离散余弦变换(DCT)

参考文献

[1]Buades A,Coil B,Morel J M.A review of image denoising algo-rithms,with a new one.Multiscale Modeling and Simulation,2005;4(2):490-530

[2]蔡超,丁明跃,周成平,等.小波域中的双边滤波.电子学报,2004;32(1):128-131

[3]Perona P,Malik J.Scale-space and edge detection using anisotropicdiffusion.IEEE Transactions on Pattern Analysis and Machine Intelli-gence,1990;12(7):629-639

[4]Coifman R R,Donoho D L.Translation-invariant de-noising.Proceed-ings of Wavelets and Statistics Springer Lecture Notes in Statistics,New York:Springer,1995;103:125-150

[5]胡金蓉,蒲亦非,张意.DCT子空间的非局部均值去噪算法.计算机辅助设计与图形学学报,2012;24(1):89-96

[6]张权,罗立民,桂志国,等.一种基于优化参数的非局部均值滤波算法.计算机应用与软件,2012;29(3):78-138

[7]孙伟峰,彭玉华.一种改进的非局部平均去噪算法.电子学报,2010;38(4):923-928

[8]Brox T,Cremers D.Iterated nonlocal means for texture restoration.In:Proc International Conference on Scale Space and Variational Methodsin Computer Vision.F Sgallari,A Murli,N Paragios,et a1.New York:Springer,2007;4485:13-24

[9]Buades A,Con B,More1J M.Nonlocal image and movie denoising.International Journal of Computer Vi～on,2008;76(2):123-139

一种基于密度均值的谱聚类算法 篇9

关键词：谱聚类,平均密度,相似矩阵,多尺度

谱聚类是一种多尺度算法。近年来该算法在语音识别、图像分割[1]和文本检索中应用广泛,尤其是在大数据的分类上越发引起人们的重视。建立在谱图理论上的谱聚类算法具有将非线性不可分的样本点空间转化为凸样本分布的能力,相比于传统的聚类算法(如K-means),其能在任意形状的样本空间上聚类且收敛于全局最优解[2]。

谱聚类算法具有比其他聚类算法更优越的数据聚类性能,但由于其本身在构造相似度矩阵时对尺度参数(核函数的宽度参数,控制了函数的径向作用范围)比较敏感,在处理多重尺度数据集时也存在结果不理想等问题。针对这一突出缺点,Zelnik-Manor和Perona提出的自调整谱聚类算法[3],利用局部密度信息来给推导出局部尺度参数,从而形成了基于多尺度参数的相似度矩阵,相比统一尺度参数更能反映真实数据点之间的关系。实验表明,该算法可准确分离出稀疏簇内部包含的紧密簇,更加准确地反映了数据点间的内在联系。但算法对数据点的位置分布没有做全面的考虑,仍存在不足之处。王玲[4]等人为了实现数据的全局一致性,提出了一种密度可调节的相似性度量矩阵,通过最短路径算法对较高密度区域上的相似性进行改进,形成了完全不同于高斯核的另一种相似性度量方式。

本文在文献[5]的基础上进行了改进,提出一种基于密度均值的具有自适应性的谱聚类算法。算法将样本点与相邻K个样本点的距离平均值视为核函数尺度参数σ,自适应地调整各个样本之间的相似度,并引入邻域密度信息,充分挖掘出了各样本点内在联系,同时也避免了聚类结果对人为给定参数的影响。仿真结果表明,本文所提算法在处理簇密度相差较大的多重尺度数据集时具有良好的簇类效果,提高了聚类性能和质量,且有一定的自适应性和鲁棒性。

1 谱聚类

1.1 谱聚类原理

谱聚类算法来源于谱图的划分。其的核心思想是将样本点聚类的问题转化为一个无向图的多路划分的问题。样本数据点被看成是无向G(V,E),将其顶点视为集合V,带权值的加权边集合E={Sij}表示基于某一相似性度量,基于此计算的两点间的相似度,用W表示待聚类数据点之间的相似度矩阵。在图G中就把聚类问题转化为在图G上最优图划分的问题,即将图G(V,E)划分为k个互不相交的子图V1,V2,…,Vk,划分后保证每个子集Vi内的相似度程度较高,不同集合Vi和Vj之间的相似度程度较低[6]。

在谱聚类算法中,常用3种反映相似度的连接图:ε邻近连接图、k最近临阶连接图和全连接图。多数文献中均采用全连接图。令sij表示xi和xj两点之间的连接权值,以高斯核函数来定义两个顶点之间的权值,其中参数σ称为尺度参数。sij定义为

对于最优图谱的划分,一个切实有效的求解方法就是将原有问题转化为求解拉普拉斯矩阵的特征值和对应的特征向量的问题。利用这些特征向量构造出一个简化的数据空间,在该空间中的数据分布结构会更加明显,并与原数据空间分部信息保持一致[7]。

1.2 传统谱聚类算法

传统的谱聚类算法有众多,其中最具代表性算法是Ng等人提出的NJW算法。NJW算法本质是是利用相似矩阵的特征向量进行聚类。选取全的谱图划分构造相似矩阵,并求取其对应的拉普拉斯矩阵,然后求出拉普拉斯前K个最大特征值对应的特征向量,这样在K维空间中形成与源数据一一对应的映射,最后利用传统的K-means或其他算法聚类,从而得到聚类结果。NJW算法步骤如下。

输入数据集经X={x1,x2,…,xn}和聚类数目k。

输出k个聚类结果Y1,Y2,…,Yk。

(1)根据高斯核函数构造相似矩阵W;

(2)计算Laplacian矩阵L=D-1/2WD1/2,其中D为W的度矩阵,对角线上元素为W每行元素的和,表达式为

(3)计算L的前k个最大特征向量u1,u2,…,uk,单位化得到矩阵V;

(4)通过K-means或其他经典聚类算法对V向量进行聚类,得到聚类结果{Y1,Y2,…,Yk}。

尽管NJW算法能将非凸数据空间转化为线性可分的凸数据空间,但在使用高斯核函数构造相似矩阵W时,聚类结果由于受尺度参数σ的影响,使得其结果具有不确定性。当处理多重尺度数据集时,这种不确定性变得更加严重。一个有效的解决方法就是取多组尺度参数,重复多次聚类,最后得到最优解,但这将导致计算机的开销过大。图1显示了同一数据集在选取不同尺度参数时的聚类效果,可看出尺度参数的不同对聚类结果产生的影响。因此,只有选取特定的参数时(在本实验中取0.6或者0.8),才能得到满意的聚类结果。

2 基于密度平均值的谱聚类算法

2.1 算法提出

由于标准的谱聚类算法使用的是全局尺度参数,并未考虑到样本点邻域数据分布对聚类结果产生的影响,当数据集具有多重尺度,密集簇和稀疏簇相互交错时,传统的谱聚类算法就无法得到较好的结果。

图2显示的是一个多重尺度数据集,其是由两个半圆月亮形组成的密集簇和夹在之间的稀疏簇组成,其中样本点A和B是位于上半弧形数据簇中,C是位于下半弧形数据簇中。在此假设AB和AC的距离相等即d(AB)=d(AC),由于传统谱聚类算法是利用空间欧式距离来表征样本点之间的相似度,由假设即可得出W(A,B)=W(A,C),即AB之间的相似度和AC之间的相似度相等,但客观情况是由于AB位于同一个密集数据簇,其间的相似度应该大于位于不同密度的AC之间的相似度。显然传统谱聚类算法不能较好地处理这类数据集的聚类。

为解决这种由于使用全局参数带来的无法将密集和稀疏数据集带来的问题,学者提出了Self-Tuning(STSC)算法。该算法将每个样本点邻域信息引入到相似矩阵的计算中,由此定义了可随样本点改变的自适应参数,得到了这种情况下的相似度函数

其中,σi=d(si,sk),表示样本点si到其第k个最近样本点的欧氏距离。同样对于图2,由于引入了邻域的信息值,有σB>σC,使得σAσB>σAσC,继而有W(A,B)>W(A,C),这样在同一密集区的样本点更容易被聚集在一起,稀疏区的样本点划分为另一类。

虽然STSC能自动的对位于不同区域的样本点间的相似度进行微调,但其仍有不足之处。

如图3所示,样本点A位于稀疏区,样本点B,C位于密集区,由STSC的理论却依旧只能得到σB=σC,σAσB=σAσC,A,B和A,C之间的相似度W(A,B)=W(A,C),这样还是无法获得正确的聚类结果。原因是样本点所在邻域的密度对数据之间的相似性有着严重的影响,两个样本点所在区域的密度相近时,其被划分在一个类的概率越大,密度相差越远时,其被划分在不同类的概率也就越大。

尺度针对这两种算法的不足,在尺度自调整的思想上,提出基于密度均值的谱聚类算法(ADSC)。其基本思想是:在对具有多重尺度的数据聚类问题上,单一用欧氏距离来表征样本点间的相似性无法全面的反映实际样本点的相互联系。在对STSC算法改进的基础上,将待聚类眼样本点的密度值也引入相似度的计算过程中,用密度权值和距离权值综合在一个相似矩阵中。通过数据点的欧式距离大小和密度信息来不断调整相似度的值,这样更加符合实际数据的相互关系。

2.2 ADSC算法实现

基于上述分析,本文在文献[3]和文献[5]的基础上重新定义了相似度函数表达式

其中,σi,σj表示样本点si,sj到距离其最近的k个点距离的平均值,σmax和σmin表示|σi-σj|的最大值和最小值。这样定义的优点在于不仅改进了传统的相似度矩阵表达式,且还引入基于平均距离的密度权值。当样本位于不同密度的簇时,可通过密度均值的权值自动调整相似度,密度和距离相差大,就会被划分在不同的类;反之,密度与距离相差较小,数据点就会被划分在同一个簇中。将新定义的相似度计算公式和传统谱聚类算法结合,可得到基于密度均值(ADSC)谱聚类算法步骤。

输入数据集X={x1,x2,…,xn}和聚类目k。

输出k个聚类结果{Y1,Y2,…,Yk}。

(1)根据新定义的核参数构造相似矩阵样本数据的^W;

(2)计算Laplacian矩阵L=D-1/2WD1/2,其中D为W的度矩阵,对角线上元素为W每行元素的和,表达式为

(3)计算L的前k个最大特征向量u1,u2,…,uk单位化得到矩阵

(4)通过K-means或其他经典聚类算法对V向量进行聚类,得到聚类结果{Y1,Y2,…,Yk}。

选取L前k个最大的特征值和其所对应的特征向量的原因在于:可证明若空间上存在k个严格彼此分离的有限数据簇,矩阵L的前k个最大特征值全为1,第k+1个最大特征值严格小于1,且这两个特征值之间的差值越大,反映出相同类间样本分布越密集,不同类间分布越稀疏[8]。图4显示的是对于文章前面提到的STSC算法不能很好地产生聚类结果,但用ADSC算法就可以准确地被聚合成两个密集类和一个稀疏类,显然更加符合实际。

图5显示了在3维空间内运用ADSC算法的实现过程,图5(a)表示原始数据集,在空间中程花瓣状[9],各坐标值表示实际属性值(下同);图5(b)表示带有邻域距离和密度信息的相似图;图5(c)表示该数据集在ADSC聚类结果;图5(d)表示Silhoutette聚类性能评价指标[10](幅值越接近1表示与聚类结果原数据集接近近程程度度更更高高))。。

3 实验结果

为验证本文所提出算法的有效性和优越性,本文分别在人工数据集和真实数据集上对传统NJW谱聚类算法、共享邻域自适应谱聚类算法(STSC)和基于密度均值的谱聚类算法(ADSC)的聚类结果进行对比实验。

3.1 人工数据集

图6给出了一个由两条螺旋线构成的数据集。图6(a)为原始数据集,是由1 000个样本点,2个属性值构成;图6(b)是传统NJW聚类方法聚类出来的结果,算法中高斯核参数σ取0.8,由于参数选取的不确定性导致了结果的不唯一;图6(c)是在具有自动尺度调整的STSC聚类方法下的结果(邻域样本数k=7),虽然大部分样本点均有效地划分在同一属性的区域,但由于相似矩阵中没有邻域的密度信息,仍有部分的样本点被错误的划分在其他类中。

3.2 真实数据集

为近一步验证本文所提出算法的聚类性能,选取UCI数据集上的Cancer、Diabetes、Ionospher、Iris数据集作为测试样本数据。表1给出了真实数据集的样本个数、类的个数和属性的个数。

表4给出了表列出的4种真实数据集在3种算法(NJW,STSC,ADSC)下的性能指标。聚类性能采用误差率来表示,误差率越小,表示聚类的效果越好。可看出本文提出的基于密度均值的聚类算法有着更好的聚类效果。

4 结束语

本文在文献的基础上,结合STSC聚类算法,提出了一种基于平均密度的聚类算法ADSC。将数据集邻域密度的信息融合到了相似度矩阵的计算中,通过欧氏空间距离和平均密度来调整每个样本点同其他样本点之间的相似度。在人工数据集和UCI真实数据集上同其他算法作了比较,结果表明该算法在聚类效果上有着明显的提高。但算法在高维数据聚类的过程中,占用计算机资源较大,运算时间较长,下一步将就这一缺陷做进一步的研究。

参考文献

[1]Agrawal D P,Zeng Q A.Introduction to wireless and mobile systems[M].Canada:Thomson Learning,2002.

[2]Von Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing,2007,17(4):395-416.

[3]Zelnik Manor L,Perona P.Self-tuning spectral clustering[J].Advances in Neural Information Processing Systems,2004,17(6):1601-1608.

[4]王玲,薄列峰,焦李成.密度敏感的半监督谱聚类[J].软件学报,2007,18(10):2412-2422.

[5]王雅琳,陈斌,王晓丽,等.基于密度调整的改进自适应谱聚类算法[J].控制与决策,2014,29(9):1681-1687.

[6]Malik J,Belongie S,Leung T,et al.Contour and texture analysis for image segmentation[J].International Journal of Computer Vision,2001,43(1):7-27.

[7]Ng A Y,Jordan M L,Weiss Y.On spectral clustering:analysis and an algorithm[C].Cambridge:Advances in Neural Information Processing Systems,MIT Press,2002.

[8]田铮,李小斌,句彦伟.谱聚类的扰动分析[J].中国科学E辑:信息科学,2007,37(4):527-543.

[9]Hamidian A,Nilsson A.Performance of internet access solutions in mobile ad networks[J].Lecture Notes in Computer Science(LNCS),2004(3427):189-201.