《智能目标识别分类技术》由会员分享，可在线阅读，更多相关《智能目标识别分类技术（10页珍藏版）》请在金锄头文库上搜索。
1、一、K-均值算法因为K-SVD算法是由K-均值扩展而来，有必要先简单介绍K-均值算法。K- 均值算法要解决的问题是：求解一个包括K个代码的码本，使得在此码本上，根 据最近邻分配法则，对包括N个信号的信号集合Y = yh ,N K进行分类，得i i=1到最佳分类问题。此时，Y中各向量被归类于与之距离最小的代码所代表的类中，C = c，c，,c 为码本，C中的列c为码本中的大妈。当码本C给定时，每个12Ki信号用最近（12-范数意义下）的一个代码表示。也就是说，y沁Cx，其中x=e ii j是自然基中的一个向量（除第j个值为1外，其他值都为0）。满足vk 丰 j| y. - Ce.| |2 勻 |
2、y. - Cek II2iJ 2ik 2这相当于稀疏编码的一个特例：只用一个原子表示信号y，同时强制系数等 i于1。这种表示方法中，yi的方差为e2 = |y - Cx |2，则Y的量化误差由下式确定 1iii 2E2 =f e2 = |Y-CX|2iFi=1K-均值算法的目标函数如下式Vi, x = eikmin Y 一 CX|2 stC XFK-均值算法的实现是一个迭代过程，包括两步：（1）求X,本质上就是稀疏编码；（2） 更新码本。 O图 4 K 均值算法步骤示意图从上图中，我们可以看到， A， B， C， D， E 是五个在图中点。而灰色的点是我们的种子点，也就是我们用来找点群的点。有
3、两个种子点，所以 K=2。然后， K-Means 的算法如下：1。随机在图中取K （这里K=2）个种子点。2。然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si 最近，那么Pi属于Si点群。（上图中，我们可以看到A，B属于上面的种子点， C，D，E属于下面中部的种子点）3。接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三 步）4。然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中 的第四步上面的种子点聚合了 A，B，C,下面的种子点聚合了 D，E）。二、K-SVD 算法K-SVD算法和K-均值聚类算法有着很深的联系，当K-SVD算法中要求的每个 信号
4、只用一个原子来近似时，K-SVD算法就退化为K均值聚类算法。同样，稀疏 表示也可看作广义的矢量量化（VQ），其中的每个信号用多个代码的线性组合表示。 令D e nxK, y e n,x e k分别代表字典、训练信号、训练信号的稀疏表示系数向量，Y = yh为N个训练信号的集合，X = x n为Y的解向量的集合。从线i i=1i i=1性组合角度看， K-SVD 训练算法的目标方程可表示为min Y - DX |2 s.tViJ|x | T(9)D, XFi 00其中，T为稀疏表示系数中非零分量的数目的上限，即系数向量中最大差异0度。从误差逼近角度来看，K-SVD训练算法的目标方程还可以表示为m
5、in |x| ,s.t|Y - DX |2 (10)D, Xi 0F本质上，式(9)和式(10)是相同的，只是考虑问题的角度不同，K-SVD作者在 论文中的目标函数式子采用(9)。式(9)求解是一个迭代过程。首先，假设字典D是固定的，用MP、OMP、或BP等算法可以得到字典D上Y的稀疏表示的系数矩阵X；然后根据系数矩阵X， 找到更好的字典D。字典的更新是逐列进行的。首先假设系数矩阵X和字典D都是固定的，将要 更新字典的第k列d，令系数矩阵X中d相应的k行为xk (不同于X的第k列xk k T k的转置)，则目标函数式(6。 21)中的惩罚项可以重写为IY - DXII2FXj d xk j T
6、丿 j*k丿kT2=IIe d xk11 k k T FF(11)上式中，乘积DX被分解成K个秩为1的矩阵和。按照假设其中K-1项是固定的。所剩的一个，也就是要处理的第k个。矩阵E代表的是去掉原子d的成分在所 kk有N个样本中造成的误差。如果此时就用奇异值分解(SVD)更新d和xk，SVD能找到距离E最近的秩为 k T k1的矩阵，这能有效地减少式(10)代表的误差。但是，如此得到的xk将是满向量 T(相对于稀疏向量而言，满向量表示向量大多数元素都是非零元的向量)，所以更新的d也不能被强制的满足稀疏条件。换句话说，因为xk中的0的影响，用SVD kT得到的xk更新向量中的非零值的位置和数量会和
7、原xk中非零位置和数量不同，TT出现“发散”。为解决此问题，直观的可以看出，去掉xk中所有的0仅保留非零值，再用SVD更新d和xk时，就不会出现“发散”现象了。kT定义集合 II i N,xk (i)H 0为用到d所有信号集合y 的索引所构kTki成的集合，即xk (i)z 0的点的索引值。定义。为Nx|o |矩阵，他在(o (i),i)处Tkkk的值都为1,其他点为0。定义xk二xkG、Yk二YkQ、Ek二EkQ，则三者分别R T k R T k R T k为xk、Y、E中去掉零输入后的收缩结果，Yk为当前用到原子d的样本集合，EkTkRkT为去掉不受原子d影响的样本后，如果不考虑d在其受影
8、响的样本中成分时，kk带来的误差。xk的长度为|w ， Yk、Ek是n x |w I矩阵。R1 kR R1 k 1此时，最小化式(11)得到的解xk和原xk就会有相同的支撑，不会出现“发TT 散”。相当于式(11)经过一次转化，转化为IIe Q - d xkQ 2 =|Ek - d xklI2(12)k k k T kl R k R“f对Ek做SVD分解，则Ek二UAVt，令d为U的第一列，则d为d的更新结果。RRkkk同时，用V的第一列和A(l,l)的乘积更新xk。在逐列更新完成后用字典D做稀 R疏分解，并判断是否达到停止条件(停止条件可以是既定的迭代次数或者重构信 号和原信号之间的误差率)
9、，以决定迭代是否继续。K-SVD 算法非常灵活，可以和常见的稀疏分解的最优原子搜索算法(如匹配追 踪(MP)、正交匹配追踪(OMP)、基追踪(BP)、FOCUSS等)结合使用。文中所选的 是正交匹配追踪算法。三、K-SVD 算法仿真实验结果 在以上知识的指导下，我们给出了在高斯白噪声下使用 KSVD 方法进行去噪 的仿真结果。实验设置：实验用图为标准测试图Barbara、House、Lena和Peppers。所加高斯白噪声 分别方差分别为15、25和35。而去噪过程中所采用的字典分别为固定的DCT字 典和文档中所阐述的使用噪声块学习出的字典。实验用图如下：图5实验用原图和加标准差为15、5、5
10、的噪声图像，从左至右分别为Barbara、ouse、Lena 和 Peppers分别采用了两种字典学习方式一一固定的DCT字典和由噪声图像学习的字典,去噪结果图由下图所示：图 6 固定 DCT 字典的 K-SVD 算法去噪结果图，从上到下噪声标准差为 15、25、35图7基于噪声图像块学习的字典的KSVD去噪结果盘E US9K H闱DM阳羽 .电懸範龍團应曲Hi切用加心然: 1 i視辑猷胡自召去il閒詈tie亠 rH, i1 浴肯I IK K 占暫耳U.：x 滅耆砌殘IW嚴辯輕H :T痢 CL fXSMTOfflQCKK 落职鼻鼻2比左悬谀F S3FKW m.Jli YiM 工宣Ki XZVJ
11、 皿 曲先妗Jill I If髓鳴斟薄用那的帀 楸阈1、删惱WZKWfflASJ XI |怫询轡帰妙J 城沏训 :l3IIIIIIWS7/Wfllll!W Z曲辭 MN M-57J1丄公 左叶眾站慰骰菩I -(a) (b)图 8 K-SVD 算法所用字典结果 (a)DCT 字典 (b) 自适应学习的字典表 1 定量分析不同噪声标准差下应用不同字典的去噪结果o =15o =25o =35噪声图DCTAdaptive噪声图DCTAdaptive噪声图DCTAdaptiveBarbara24.6131.6532.3820.1628.6929.6317.2426.7127.81House24.5933
12、.4534.2720.1630.9932.0717.2829.2930.31Lena24.5833.3533.6720.1530.9231.3417.2229.1729.65Peppers24.6131.6732.1420.1828.9129.6317.2627.1828.09由图6、图7和表1所示，我们可以看到K-SVD算法在去噪性能确实有很明 显的效果。属于目前流行的几种去噪算法之一。细节上看，固定的DCT字典不能 很好的适应各类图像，而去噪的结果也没有自适应学习的字典效果好。宏观上看， K-SVD 算法在低标准差的高斯噪声下有着很好的去噪效果，但随着噪声的增大， 此去噪算法的效果下降也较为明显。四、小结本文着重介绍了 K-SVD算法，首先由K-均值算法入手，得到广义K-均值算 法，也就是我们所用的 K-SVD 算法。 K-SVD 算法属于字典学习的经典算法之一， 将稀疏表示的思想用于图像去噪，并取得了较好的效果。本文通过学习这种算法 并进行仿真实验，重现了文献中的部分结果。使得我更好的体会了这个算法的精 髓。
