光电工程                                        2013 年 6 月 http://www.gdgc.ac.cn 18护和灾害预测及评估等方面发挥着重要的作用。目标识别是 SAR 图像应用中的重要组成部分，相对于光学遥感图像处理[1-3]，针对 SAR 图像的目标识别越来越受到人们的重视[4-7]。字典学习方法是 SAR 图像目标识别中的重要方法，当前的研究难点和热点在于如何构造基于稀疏表示的字典学习算法来进行目标识别。 稀疏表示的模型最早可追溯到1993年，S.Mallat和Z.Zhang首次提出字典的概念并用其代替传统小波变换(Wavelet  Transform)[8]，他们同时设计了一种贪婪追逐(Greedy  Pursuit)算法以近似得到稀疏解[9-10]，此外S.Chen  和D.Donoho  等人分别于1994年和2001年进一步探讨了稀疏解的求解方法[11,12]，并就稀疏解的唯一性、收敛性等问题给出了理论分析。从那以后，基于稀疏表示的字典学习方法在各学科领域得到了广泛而深入的研究。基于稀疏表示的字典学习模型可表示为如下优化问题： (P0):   sii F||||,s.t.||||min£"-2,Yx DXXD                      (1) 其中：YÎRm×n为待处理信号，DÎRm×K为基函数字典，XÎRK×n为稀疏表示向量，xiÎRK为列向量，| .|0表示第0范式，即向量或矩阵中非零元素的个数。 式(1)表示的(P0)问题是 NP-hard 问题，因此寻找字典的方法只能通过逐步逼近的方式。M. Aharon 等人针对该问题于 2006 年提出了 K-SVD 算法[13]。由于将矩阵的 SVD 分解巧妙的应用到字典更新过程中，使得 K-SVD 算法的字典更新速度快且表示精度高，从而引起了学者们的广泛关注和进一步研究[14-17]。 针对海量的雷达遥感图像进行字典学习，在考虑表示精度的同时，需要考虑字典的大小问题。即针对大量的 SAR 图像，如何在保持字典表示精度的同时控制字典的尺寸。包括 K-SVD 在内的字典学习算法在 解决(P0)问题时都专注于如何降低表示误差2||FE -=DXY ，而学习过程中的 K 是人为取定的，这使得 D 的学习效果因 K 而异。K 过小，D 的表示能力不够；K 过大，D 冗余性过高而增加 X 计算时间，并且浪费了存储空间。如何找到合适的 K，既能保证 D 对 Y 的表示精度，又不至于使 D 过于冗余，成为亟待解决的问题。 针对这一问题，本文提出了一种动态 K-SVD 算法(Dynamic K-SVD, DK-SVD)，该算法保持了 K-SVD原算法对信号表示的稀疏性、实现简便等特点，同时最大限度降低了字典 D 的冗余性，提高了信号表示的效率。DK-SVD 算法主要从以下两方面来优化字典：1)  删除 D 中相关度高或利用率低的字典条目，在保证 D 对 Y 的表示精度条件下，尽量降低 D 的冗余性；2)  将误差 包含的主分量添加入 D 中，在保持字典尺寸相对稳定的条件下，尽量降低表示误差。在 MSTAR 数据集上的实验验证了该算法的有效性和稳定性。 1  K-SVD 算法 K-SVD 算法分为系数矩阵更新过程和字典更新过程，下面简单描述其过程。 Step 1  更新系数矩阵 X 控制稀疏度为s的情况下，根据字典D和数据Y采用正交匹配追踪(Orthogonal Matching Pursuit, OMP)[18]算法计算得到 X。 判断误差是否满足精度，即 E≤ε 是否成立，成立则结束训练，否则转 Step 2。 Step 2  逐列更新字典 D 剥离字典条目 di(i=1,2,...,K)的贡献，计算相应的误差 Ei： )('iiiE ´--=xd DY X                                  (2) 式中：di表示 D 的第 i 列，即第 i 个条目，ix¢ 表示 X 的第 i 行。 将 Ei乘以紧缩矩阵 Ωi之后进行 SVD 分解(详见文献[13])，以保证稀疏度： TEΩ =URVii                                     (3) 其中：U 和 V 的列矢量均为正交基，R 为奇异值矩阵且奇异值按照自大到小排列，则此时选取 u1和 v1分别替换 di和ix¢ 。如此保证了局部更新的最优性，总误差不会因为一个条目的更新而增加，也就保证了方法的收敛性。 对整个 D 更新完毕，转 Step 1。 王保云，等：一种基于动态字典学习的 SAR 图像目标识别算法 http://www.gdgc.ac.cn 192  动态 K-SVD 字典学习算法 2.1 K-SVD 算法的不足 在 K-SVD 算法中，由于字典尺寸 K 不变，则会存在以下问题： 1) K 过小。此时由于miiKii 11}{}{==Ì yd ，不符合过完备的要求，不但达不到稀疏表示的要求，甚至表示精度也难以符合要求。这时在Step 2中SVD分解时会出现R的第二个甚至第三个奇异值也很大的情况，用T11vu代替iE 产生的误差较大。此时，即使一直迭代下去，也难以满足 E≤ε。 通常我们要处理的数据量都比较大，即 m 和 n 值都很大。这时虽然可以通过计算 rank(Y)来估计 K，但由于计算复杂度过高而不可取。 2) K 过大。此时字典 D 冗余度过高，由于 K 过大而造成 Step 1 计算量加大，同时过高的冗余度浪费了存储空间。 以上原因促使我们寻找表示精度高而冗余度低的字典 D，即在字典学习过程中自动寻找合适的 K。 2.2 动态 K-SVD 字典学习算法 DK-SVD 与 K-SVD 不同之处在于通过实时调节 K 来调整字典的大小，同时保证表示误差处于可接受范围。这时(P0)问题转变为 sii FKi ii Kå£"-== 021',,DKxxd YX||||,s.t.||||minarg},,{XD                       (4) 式(4)所述(Pk)问题不是凸问题，无法直接求解其最优解。这里结合 K-SVD 的字典更新方法和交替投影迭代的思想[19]，将问题分为两步交替进行：首先固定K，运用 K-SVD 算法对 D 和 X 更新；然后优化 D，求出当前最优字典 Dopt。(Pk)问题可分解为(Pk0)和(Pk1)： (Pk0):  Kisi FKi ii,,2,1,||||s.t.||||minarg},{021',Kå=£-==Xxxd YDXD              (5) (Pk1):  fs KKi£=0optoptx XD||||s.t.),,(},{ D                          (6) (Pk0)问题即为 K-SVD 要解决的问题，对应于图 1 流程中的“稀疏编码(Sparse  coding)”和“字典更新(Dictionary  update)”两步；(Pk1)问题为 DK-SVD 中的字典动态调整部分，对应于图 1 中的“字典优化(Dictionary optimization)”步骤。DK-SVD 的关键就在于如何优化字典 D 得到 Dopt。 2.3 字典优化步骤 针对字典尺寸的优化无外乎以下两种情况：1)  由于 K 过大而致使字典条目过多，需要删除相关度过高条目或利用率过低条目；2)  由于 K 过小而致使字典表示能力欠佳，需要增加字典条目以增强字典表示能力。 2.3.1 删除字典条目 对于删除字典条目的情况，首先考虑条目重复或条目表示能力等同的情况。先定义字典的协方差矩阵C=[cij]=DTD，cij=<di，dj>，其中<·，·>表示向量之间的内积。当 cij≥Tcorrelation时，表明id 和 dj具有很高的相关度，二者对信号的表示能力相等，可以删除其中一条而几乎不影响 D 对 Y 的表示能力。另外，虽然与其他条目不重复，但在表示 Y 的过程中贡献小于 Tcorrelation，则认为该条目应该删除，为此定义贡献度向量 图 1   动态字典训练过程 Fig.1   Flowchart of the dynamic K-SVD Training data Dictionary initialization  Sparse coding Dictionary update Dictionary optimization Stop condition satisfied? NY D Pk0 Pk1                       光电工程                                        2013 年 6 月 http://www.gdgc.ac.cn 201'||||iif =x 。综合以上，得到删除字典条目序号集合为 },,|{},|{oDELncorrelatio DELncontributifi MEci TTEji TTiijii>£³££=U                   (7) 其中：2'||)(||FiiiE Y --=xd DX 表示剔除条目di后字典的表示误差，TDEL为误差控制阈值，Ei≤TDEL保证删除 后误差不会大幅度增加。 由于阈值 Tcontribution与 Tcorrelation和实验的数据集有关，较难控制。为简单起见，可使用式(8)替代式(7)： },,max|{},min|{DEL,DELi MEi TfEji Tciijjiiii>££=U                      (8) 即每次搜寻贡献度最小的条目和相关度最大的条目，并计算其删除代价Ei，如果满足DELTEi£ ，则进行删除操作。图 2(a)给出了删除操作的示意图，其中id 和ix¢ 的对应图中 D 矩阵和 X 矩阵中白色标示的列和行。 由于删除了ix¢ ，X 中部分列向量稀疏度降低。在(Pk)问题中，稀疏度 s 是一个上限值，所以我们对 X中稀疏度降低的向量不做处理。 删除字典条目算法 1 如下： 输入：字典0KmR´DÎ 和系数矩阵n KR´Î0X ； 输出：优化后字典1opt KmR´DÎ 和系数矩阵n KR´Î1X ，01KK < ； 删除步骤： 1)  计算删除字典条目：根据式(8)计算 M； 2)  删除操作：删除 iÎM 对应的字典条目id 以及 X 中对应的行ix¢  3)  调整字典：调整字典列数为 ||01-=MKK 。 2.3.2 增加字典条目 对于确定的 D，当表示误差ADD2||| TEFDXY³-= 时，则认为误差中包含 D 所不能表示的成分，将误差进行 SVD 分解，所得到的 u1可作为新增加的字典条目，即： ),,,,(1210uddd DKK=  而系数矩阵需要添加一行 )(1sparsenew¢=vx f ，其中 )(1sparsefv 函数保留向量中绝对值最大的 s 项，其余置零。1u 和newx¢ 分别如图 2(b)中 D 和 X 的最后一列和一行所示。 至此为止，我们增加了一个字典条目，同时在系数矩阵 X 中添加了一行。此时 X 中最多有 s 列的非零元为 s+1，这里直接将非零元个数为 s+1 的列中最小的元素置零，使之满足稀疏度要求。 字典条目增加算法 2 如下： 输入：字典0KmR´DÎ 和系数矩阵n KR´Î0X ； 输出：优化后字典1opt KmR´DÎ 和系数矩阵n KR´Î1X ， 101KK+= ； 增加步骤： 1)  条件判断：判断误差是否满足ADDTE ³ ，满足则继续，否则返回； 2) SVD 分解：将误差矩阵 E 进行 SVD 分解， URVE = ； 3)  提取字典元：将 U 的第一列1u 作为新增字典条目； 4)  修改系数矩阵：添加 )(1sparsenew¢=vx f 为 X 最后一行； 图 2   字典条目增删示意图 Fig.2   Adjustment of dictionary in DK-SVD(a) Delete one atom from D (b) Add one atom to D  D  XY YD X http://www.gdgc.ac.cn 王保云，等：一种基于动态字典学习的 SAR 图像目标识别算法 http://www.gdgc.ac.cn 215)  调整稀疏度：对于 X 中newx¢ 非零元对应的列，将其列元素中最小一个值置零。 2.3.3 两个阈值之间的关系 阈值DELT 和ADDT 的取值会影响算法的收敛性，这里简单讨论二者之间的关系。 1) DELADDTT £  当执行算法 1 删除字典条目后，表示误差将会增加，设单次删除(删除一条)后表示误差为DELTEi£ 。因为DELADDTT £ ，则ADDTEi³ 成立，将必然执行算法 2。此时存在两种情况： (a) Ei主要是由删除id 造成的，此时对 E 进行 SVD 分解，主方向与id 一致，算法 2 将再次将id 加入 D中。这时对同一字典条目造成“删除-添加-删除”循环，即算法 1 和算法 2 被交替执行，使算法无法收敛。 (b)  删除id 对iE 影响较小，即id 项对整个数据表示的贡献很小，此时执行算法 2 将得到有效执行。 所以DELADDTT £ 时不能保证算法的收敛性，会造成振荡现象。 2) DELADDTT >  当执行算法 1 删除字典条目后，误差需要累积到ADDTEi³ 时才执行算法 2。如果iE 主要是由于删除id造成的，则ADDDEL2'|||| TTEFiiixd<£» ，不满足误差分解条件，算法 2 不会被执行；如果id 分量在iE 总所占比重较小且误差满足ADDTEi³ ，此时进行 SVD 分解得到1u 比id 更利于减小表示误差。 所以DELADDTT > 时，可以保证算法的收敛性。同时也注意到ADDT 不宜比DELT 大太多，否则算法 2 总是得不到有效执行，就会出现字典条目只减不增的现象。 综合以上分析，为了保证算法的收敛性，要求DELADDTT > ，一般可取 22TTTDELADD== 。在算法中，T取前后两次的相对误差而不是固定的数值，这样可以避免由于对绝对误差估计不准而带来的算法性能下降，即取ii/)(EEEprior- ，其中priorE 为当前操作之前的误差。 3  DK-SVD 应用于 SAR 图像目标识别 3.1 数据库介绍 本文实验数据采用美国 DARPA/AFRL 提供的 MSTAR 图像，该数据中目标图像分辨力为 0.3 m×0.3 m，像素尺寸 128×128。数据库里包含 3 类(BMP2,BTR70,T72)共 7 种型号的地物目标，同一大类里面不同型号的实际差异为目标的配置不同，称为变形目标，目的是检验算法的有效性和推广性。由于 SAR 对目标成像方位的敏感性，每类目标需有很多不同方位图像对应，以确保目标识别的准确性。MSTAR 数据中每类目标像的方位覆盖范围均为 0~360°间隔为 1°，数据如表 1 所示。 论文中使用的训练测试集样图如图 3 所示。 3.2 实验结果 在 实 验 中 ， 我 们 取 稀 疏 度 s=3 ， 收 敛 控 制 最 小 误 差6106-E´=D ， 动 态 学 习 阈 值033.02/ADDDELTTT=== ，更新次数最大为 300，初始字典条目为 700K= 。 图 4 给出了训练后字典，图 4(a)、4(b)和 4(c)分别对应三类字典。从图中可看出，三类字典都包含了类似低频到高频的分量，并且字典的大部分条目都只包含图像中心的目标部分信息，这也符合一般的认知原理：图像的低频能量较高但成分简单，目标边缘部分则包含了较多高频信息。 表1   MSTAR数据统计 Table 1   Description of the MSTAR dataset Category  Training set  Number Test set  Number 1.1 BMP2(S-C21)  233 BMP2(S-C9563)  195 1.2  BMP2(S-C9566)  196 1.3  BMP2(S-C21)  196 2.0  BTR70(Sn-C71)  233  BTR70(Sn-C71)  196 3.1 T72(Sn-132)  232 T72(Sn-132)  196 3.2  T72(Sn-812)  195 3.3  T72(Sn-S7)  191                       光电工程                                        2013 年 6 月 http://www.gdgc.ac.cn 22实验结果如表 2 和表 3 所示，其中识别率计算公式为 100%tolrightrate´=NNR                                     (9) 其中：rightN 为正确识别数，tolN 为总的识别数。 (b)(c) 图 4   训练后字典示意图 Fig.4   Dictionary atoms in DK-SVD (a) 图 3   MSTAR 数据库样图 Fig.3   Samples of MSTAR dataset (a) S-C9563  (b) S-C9566 (c) S-C21 (d) Sn-C71  (e) Sn-132 (f) Sn-812 (g) Sn-812 表 2   本文算法与其他算法性能对比 Table 2   Performance comparison of different methods on MSTAR dataset Algorithm  MT[20]  KLDA+SVM[21]  KPCA+SVM[22]  KPCA+Lap RLSC[23]KPCA+RLSC[23]PCA+SVM[22]  DK-SVD Recognition rate 68.0%  90.5%  91.5%  98.6%  95.5%  95.4%  99.7% 表 3   DK-SVD 在 MSTAR 数据集上实验结果 Table 3   Results of DK-SVD on MSTAR dataset Category  1.1  1.2  1.3  2  3.1  3.2  3.3  Ave Items  18  20  19  19 Recognition rate %  99.5  100  100  100  99.5  99.5  99.5  99.7 王保云，等：一种基于动态字典学习的 SAR 图像目标识别算法 http://www.gdgc.ac.cn 23表 2 为本文算法 DK-SVD 与其他算法的识别性能对比，表 3 中给出了每一类的识别率和最终字典条目数。 从表 2 可以看出 DK-SVD 识别率为 99.7%，优于其他传统算法；表 3 给出了 DK-SVD 对字典动态调整的结果，可以看出在 MSTAR 数据库上，字典最终页数为 K=19 左右，远低于初始值 700K= ，即可保证较高的识别率。 3.3 分析与讨论 3.3.1  阈值 T 对算法的影响 阈值T 对字典的性能影响较大，无论是字典条目数、表示误差，还是最终的识别率都有明显的影响。 图 5(a)为 s=3， 700K= 时阈值 T 对表示误差的影响，图中的点划线为表示误差曲线，实线为识别率曲线。可以看到随着T从 0 增大到 0.1，当 TÎ]035.0,0[ 时，信号的表示误差值很低且变化缓慢；而在TÎ)042.0,035.0( 左右发生了大幅的增加， T 在[0.042，0.1]区间时，误差较大且区域变化平缓；同样地，识别率曲线也表现出类似的效果，在TÎ)042.0,035.0( 区间内，识别率从 99.0%下降到 86.7%，而在该区间之外则变化缓慢。 图 5(b)为 s=3， 700K= 时字典条目数随T 值变化图。与图 5(a)对应，字典条目数在TÎ)043.0,02.0( 之间发生剧烈的变化，而在[0，0.02]和[0.043，0.1]两个区间内变化较为缓慢。 上图表明，当阈值 T 较小时，算法 1 和算法 2 中满足删除的条目较少，字典条目数变化不大；随着阈值增大到 0.02，冗余的条目被删除，字典条目数被调整到合理的数目。图中表示误差 E 急剧增加时的 T 值即我们要求的DELT ，其对应的字典条目数也为最佳大小。在本实验中， s=3 ， 700K= 时，T<035.0 ，字典条目数可控制在 20 左右。 对比图 5(a)和 5(b)，可用下式近似计算T 的最佳值*T ： TET)}({maxargT=¢* 其中： TE)( 表示以T 为变量的误差函数，即图 5(a)中的点划线， TE¢)( 表示对自变量T 求导。本实验在 s=3，700K= 条件下求得 =035.0*T 。 3.3.2 字典条目数动态调整过程 由于算法 1 和算法 2 的同时进行，这在加快收敛速度的同时，也会带来 K 和 E 的波动。 图 6 描述了误差 E (点划线)和字典条目数 K (实线)随迭代次数的变化趋势。刚开始由于 K 较大，所以表示精度也较高，而随着迭代次数增加，不断的调用算法 1 和算法 2 导致K下降，同时带来表示误差的增加，当 K 减小到 20，则达到平衡状态， K 和 E 都不再变化。 图 6 中 E 和 K 的曲线都有不同程度的抖动，这是因为：当字典冗余度较大时，算法 1 被不断的执行，表现为表示字典条目数的 K 值不断下降，但当误差增加到一定程度，算法 2 将会被执行，其效果表现为 K值局部上升且 E 值局部下降。二者交替执行最终达到字典条目数和误差的平衡值。 0  0.02  0.04  0.06  0.08 0.10E 0.2 0.3 0.4 0.5 0.850.900.951.00K Reconstruction error Recognition rate 020 40 60 0 0.02 0.04 0.06  0.08  0.10 (a)  (b)图 5   阈值 T 的选择及其对算法的影响(s=3, K0=70) Fig. 5   Choice of T and its influence of DK-SVD(s=3, K0=70) T  T                                              光电工程                                        2013 年 6 月 http://www.gdgc.ac.cn 244  结  论  本文针对字典学习在 SAR 图像目标识别中的应用场景提出了一种动态调整字典大小的算法。该算法试图在提高表示精度和降低字典条目冗余度之间找到最佳平衡点，即自动找到满足一定表示精度的最小字典，以避免事先人为设定字典尺寸所带来的过大或过小的弊端。通过在 MSTAR 数据集上的三类目标识别试验表明，DK-SVD 在获得较为紧凑的字典结构的同时，对三类 7 种目标都保持了较高的识别率。该算法对 SAR图像目标成像方位不敏感，算法稳定性好。 参考文献： [1]   WANG  Bao-yun，ZHANG  Rong，YUAN  Yuan，et  al.  An  auto-adapt  multi-Level  threshold  segmentation  method  of  ships detection  in  remote  sensing  images  with  complex  sea  surface  background  [C]//  2011  International  Workshop  on Multi-Platform/Multi-Sensor Remote Sensing and Mapping (M2RSM)，2011：1-5. [2]   王彦情，马雷，田原.  光学遥感图像舰船目标检测与识别综述[J].  自动化学报，2011，37(9)：1029-1039. WANG Yan-qing，MA Lei，TIAN Yuan. State-of-the-art of ship detection and recognition in optical remotely sensed imagery [J]. Acta Automatica Sinica，2011，37(9)：1029-1039. [3]   王保云，张荣，袁圆，等.  可见光遥感图像中舰船目标检测的多阶阈值分割方法[J].  中国科学技术大学学报，2011，41(4)：293-298. WANG  Baoyun，ZHANG  Rong，YUAN  Yuan，et  al.  A  new  multi-level  threshold  segmentation  method  for  ship  targets detection in optical remote sensing images [J]. Journal of University of Science and Technology of China，2011，41(4)：293-298. [4]   张新征，黄培康.  基于贝叶斯压缩感知的 SAR 目标识别  [J].  系统工程与电子技术，2013，35(1)：40-44. ZHANG  Xinzheng，HUANG  Peikang.  SAR  ATR  based  on  Bayesian  compressive  sensing  [J].  Systems  Engineering  and Electronics，2013，35(1)：40-44. [5]   WEI  Z，JIE  W，JIAN  G. An  efficient  SAR  target  recognition  algorithm  based  on  contour and  shape context  [C]// Synthetic Aperture Radar (APSAR)，2011 3rd International Asia-Pacific Conference on，2011：1-4. [6]   WU Tao，CHEN Xi，RUANG Xiangwei，et al. Study on SAR target recognition based on support vector machine [C]// 2nd Asian-Pacific Conference on Synthetic Aperture Radar，Xian，Shanxi，Oct 26-30，2009：856-859. [7]   LIN  C，SUN  X，WANG  B，et  al.  Adaptive  Quasiconformal  Kernel  Principle  Component  Analysis  for  MSTAR  SAR Recognition [J]. Information Technology Journal(S1812-5646)，2012，11：1751-1757. [8]   Mallat  S  G，Zhang  Z.  Matching  pursuits  with  time-frequency  dictionaries  [J]. Signal Processing，IEEE Transactions on(S 1053-587X)，1993，41(12)：3397-3415. 图 6   优化过程中 E 和 K 随迭代次数变化情况(s=3, K0=70, T=0.033) Fig.6   E and K vary with the times of iteration (s=3, K0=70, T=0.033) 0  20 40 60 80 100Times of iterationReconstruction error K(No. of atoms in D) 80604020K E 0.2 0.3 0.4 0.5