CVS中基于块分类的自适应阈值调整组稀疏重构

杨春玲 郑钊彪 李金昊

(华南理工大学 电子与信息学院，广东 广州 510640)

近几年来，压缩感知(CS)理论[1- 2]在医学图像处理、视频编解码领域受到了广泛的关注。该理论指出，原始信号通过随机矩阵观测后压缩成少量观测数据，经过重构算法可大概率地精确恢复。在一些采集信息比较慢且对成像质量要求不高的实际场景中，应用CS理论可以显著提高采样速度。

关于图像压缩感知，重构算法一直是研究的重点。近几年来，利用图像非局部自相似性的CS重构算法被相继提出，如NLR-CS[3]、GSR[4]等。其中图像组稀疏表示(GSR)将具有相似结构特征的图像块组构成低秩稀疏矩阵，并通过分裂Bregman迭代(SBI)过程求解L0范数约束的目标式。GSR解决了传统字典学习中计算复杂度高的大规模优化问题，在统一的框架内充分利用了图像的局部稀疏性和非局部自相似性，是目前重构性能位于顶尖水平的图像压缩感知重构算法之一。

为了超越GSR的重构性能，不少学者在GSR的基础上做出合理改进，如GSR-TNNM[5]把GSR目标表达式中非凸的L0范数约束修改为松弛的L1范数约束，结合组稀疏表示和截断核范数极小化求解目标式，并且根据当前迭代信号在稀疏域的特征自适应调整稀疏化阈值。近几年来，采用神经网络进行压缩感知的方法[6- 7]逐渐兴起，该类方法不但重构速度快，而且在低采样率下也能够实现高质量重构，但也存在许多不足，如研发的硬件费用昂贵，训练好的单个网络鲁棒性低以及训练集的数据量庞大等。

在视频压缩感知领域，多假设预测-残差重构[8]是经典的重构模型，而MH-wElasticnet[9]、Up-Se-Awen-HHP[10]、PBCR-DCVS[11]、2sMHR[12]都是基于多假设预测模型的改进。其中PBCR-DCVS不仅提出了基于二阶段多假设的关键帧重构方法，还提出了分情况选用wElasticnet或Tikhonov的非关键帧重构方法，并结合了多参考帧选择方案。在时间复杂度上，PBCR-DCVS虽然比MH-wElasticnet降低了不少，但还是比基于Tikhonov正则化的多假设算法要高。而2sMHR通过添加像素域的多假设重构，有效地减少了重构图像中的“块效应”，复杂度低且重构效果好。

不少学者也提出了基于帧间非局部自相似性和局部稀疏性的视频重构模型，如SLM[13]、RRS[14]、MRF-DSR[15]等。文献[16- 17]的重构模型都利用了GSR的思想，文献[17]提出了基于结构相似性的组稀疏表示重构算法(SSIM-InterF-GSR)，将相邻重构帧作为参考帧，根据图像块间的结构相似性(SSIM)选出匹配块组，并随着迭代次数的递增减少匹配块组中图像块的数目，其重构效果不亚于2sMHR，但通过迭代提升重构质量的方式增大了时间复杂度。

SSIM-InterF-GSR虽然重构效果较好，但存在以下不足：非关键帧均采用相邻帧作为参考帧，使得中间帧未能充分利用高质量重构的关键帧信息对平稳区域进行重构；在重构迭代过程中，没有考虑不同采样率下初始重构的噪声含量，也没有考虑不同运动状态的图像块结构信息的保留程度，对所有图像块采用相同的阈值处理方法，限制了重构性能也降低了重构迭代的收敛速度。

基于上述问题，本文提出了基于块分类的自适应阈值调整组稀疏重构算法BC-ATA-GSR。针对关键帧信息利用不充分的情况，文中算法通过帧差法区分运动区域，根据块内物体运动状态将图像块划分为平稳块和运动块，再根据块类别选择合理的参考帧，利用关键帧信息来提高平稳区域的重构质量；针对重构迭代中阈值设置的不合理性，本文根据采样率以及图像块种类自适应设置初始阈值，而且在每次迭代时适当缩减稀疏化处理阈值的数值大小，以便在提高重构质量的同时加快迭代收敛速度；最后通过仿真实验分析了文中算法与现有算法的性能。

1 图像/视频组稀疏表示重构

1.1 图像组稀疏表示重构算法

图像GSR将相似图像块组的列向量构成相似矩阵，若图像块之间越相似，则矩阵的低秩特性越强。将低秩矩阵投影到更低维的线性子空间，就可以用几个稀疏表示系数来表示这一组相似块的结构信息。将该子空间稀疏系数的个数作为约束项，则GSR的目标表达式为

(1)

s.t.u=R(DG○αG)。

1.2 视频CS重构中基于结构相似性的帧间组稀疏表示重构算法

SSIM-InterF-GSR利用帧间图像块的非局部相似性，通过比较SSIM找到相似块。SSIM-InterF-GSR的整体框架描述如下：编码端采用高斯随机矩阵对视频帧进行分块观测，关键帧采用高采样率矩阵观测，经过多假设预测单帧重构后，在帧内寻找相似块，进行帧内组稀疏表示重构；非关键帧采用低采样率矩阵观测，单假设预测[18]初始重构后，在相邻帧以及当前帧初始重构图像中寻找相似块，采用帧间组稀疏表示算法重构。

以重构非关键帧为例，为了求解带有等式约束的式(1)，加入权值参数μ，将式(1)修改为无等式约束的增广拉格朗日形式：

(2)

使用SBI迭代求解式(2)，其过程可分为下列3个子问题：

(3)

式中，u子问题本质上是一个关于严格凸二次函数的极小化问题，可以用共轭梯度下降法去接近最优解：

(4)

η是u子问题公式的梯度方向，d是最佳下降步长，两个变量的表达式可以在文献[4]中找到，这里不再赘述。

求解α子问题前需要找出相似块。SSIM-InterF-GSR在当前帧和相邻帧中进行相似块搜索。块搜索过程为：首先依据均方误差(MSE)挑选出一定数量的图像块，再根据SSIM大小进一步筛选。另外，SSIM-InterF-GSR提出了搜索相似块数目随着迭代次数阶梯递减的调整方案。式(3)中的α子问题经过证明可大概率等价为[4]

(5)

式中：αGk和γGk分别是相似矩阵Gk的稀疏系数矩阵目标值和当前值；是L0范数约束项的权重因子，

(6)

Bs是图像块边长B的平方，c是当前块找到的相似块数量，n是当前图像中重叠分块数目的总和，N是当前图像的像素点总数。

(7)

解决α子问题后，把相似块组中的图像块加权平均放回原位置，即可得到当前迭代的重构图像。满足退出条件时则结束迭代并输出最终重构图像。

SSIM-InterF-GSR在重构视频序列时取得了良好的视觉效果，但仍然存在以下不足：①平稳区域的重构过程未充分利用关键帧信息。平稳区域指当前帧的像素点数值与参考帧相比未发生较大变化的区域。理论分析表明，视频序列中的平稳区域很容易在重构质量高的关键帧中找到相似甚至相同结构特征的图像块，但SSIM-InterF-GSR只是将相邻帧作为参考帧，画面组(GOP)中间位置的非关键帧没有利用关键帧进一步提升平稳区域的重构质量。②稀疏系数阈值处理的数值设置不平衡。SSIM-InterF-GSR对所有相似块组设置相同数值的硬阈值函数，并没有考虑到视频序列中物体的运动状态所带来的重构难度差异，导致重构出的运动区域物体轮廓结构比较模糊，而平稳区域物体的细节纹理大部分被平滑处理；另外，重构过程中硬阈值函数的阈值一直不变，导致迭代后期重构出的纹理信息仍被当作噪声滤除，限制了重构质量的提升。

2 基于块分类的自适应阈值调整组稀疏重构

在SSIM-InterF-GSR的基础上，本文提出了基于块分类的自适应阈值调整组稀疏重构(BC-ATA-GSR)算法。该算法包含以下改进：块分类及参考帧的合理选择、组稀疏重构过程中初始阈值的自适应设置、迭代阈值梯度递减。BC-ATA-GSR算法整体框架如图1所示。

2.1 块分类及参考帧选择方案

三帧差分法是检测视频序列中运动物体的常用方法之一，该方法实现简单、计算复杂度低且对光线变化不敏感。本文采用三帧差分法判断视频序列中的运动区域，从而实现图像块的分类，然后分别对不同类别的图像块选择合适的参考帧。具体实现步骤如下：

图1 BC-ATA-GSR算法框架Fig.1 Frame of BC-ATA-GSR algorithm

图2 三帧差分法判断运动物体轮廓示例

(4)对于平稳图像块，选择最近邻的两个关键帧作为参考帧；对于运动图像块，选择最近邻的一帧或两帧作为参考帧。

这样选择参考帧的原因如下：若当前块为平稳块，在关键帧中搜索到的图像块相似程度高，且关键帧因采样率高而重构效果好，则将关键帧作为平稳块的参考帧能够获得更好的重构效果；若当前块为运动块，由于当前帧与关键帧在时间维度上相距较远，关键帧的时间相关性比相邻帧小，在关键帧的相同位置找到的图像块相似程度低，因此像素点变化较多的运动块以相邻帧作为参考帧，能够获得更契合当前块的运动估计信息。图3给出了GOP=8时不同类别图像块的参考帧具体选择方案。

图3 非关键帧中不同类别图像块的参考帧选择方案

2.2 自适应初始阈值设置

除了SSIM-InterF-GSR中统一数值的硬阈值处理外，也有不少文献提出了不同的稀疏表示后阈值处理方案，如GSR-WNNM对奇异值进行软阈值处理[19]和GSR-TNNM对较大奇异值不作阈值处理以保留相似图像块的主要轮廓[5]。

本文在SSIM-InterF-GSR的统一数值硬阈值处理的基础上，提出了自适应初始阈值设置方案。经过图像块分类及参考帧选择之后，每个图像块通过块匹配得到一组相似块，然后进入组稀疏迭代重构过程。组稀疏处理是通过阈值处理实现的，初始阈值影响着初始重构图像进入迭代过程后的细节保留程度，而初始重构图像的质量和采样率之间的相关性非常大。在高采样率时，初始图像的重构质量较高，变换域中小系数对应的细节纹理信息需要尽量保留，此时初始阈值设置应相对较小；在低采样率时，经过初始重构引入的噪声较多，初始重构图像比较模糊，仅保留图像块中对应轮廓结构的变换域大系数，此时初始阈值设置应相对较大。于是结合式(6)，在非关键帧重构的初始阈值设置中考虑采样率的影响，阈值的初步设置方案如下：

(8)

式中，S是非关键帧的采样率。

另外，在初始重构图像中，运动图像块一般比较模糊，重构时以保留物体主要轮廓为主，此时变换域中小系数代表的结构信息大部分是与轮廓结构无关的干扰信息，故运动块的初始阈值较大；平稳图像块初始重构效果较好，此时变换域中小系数代表的纹理细节信息较多，应尽量保留，故平稳块的初始阈值较小。经过大量实验发现，平稳块初始阈值接近运动块初始阈值数值的一半时重构效果最优，结合式(8)的阈值初步设置公式，不同类别图像块初始阈值T(0)设置如下：

(9)

图4 Football序列对不同阈值选择方案的平均PSNR

2.3 迭代过程中阈值梯度递减方案

在SBI迭代重构过程中，随着迭代次数的增加，重构图像中更多细节纹理被恢复，此时应该适当减小硬阈值函数的阈值，以尽可能地保留纹理信息对应的小稀疏系数。因此，迭代过程中的硬阈值调整方案应该与当前迭代次数有关，迭代开始时阈值大小等于初始阈值，次数越大，阈值应该越小。结合式(9)设置的初始阈值T(0)，第i次迭代的硬阈值表达式为

T(i)=(1-βi)T(0)

(10)

式中，β为梯度递减斜率，取值范围为[0.02，0.05]，斜率越大，阈值递减速度越快。

为了取得各采样率下重构效果最好对应的β值，对Coastguard、Football、Soccer、Suzie、Foreman、Hall、Mother-daughter这7个标准QCIF序列的前88帧进行实验，GOP=8，分块大小为16×16像素。在采样端，采用高斯随机观测矩阵，关键帧采样率为0.7，非关键帧采样率为0.1～0.5。实验记录重构序列的PSNR作比较分析。求出各视频序列的平均每帧PSNR后，再求7个视频序列的PSNR均值，各采样率下的平均PSNR比较如图5所示，图中Org曲线为SSIM-InterF-GSR的PSNR。

图5 β取不同值时在各采样率下视频序列的平均PSNR比较

通过观察并比较图5的PSNR值，为了取得最好的重构效果，β在各采样率S下的取值如下：

(11)

3 仿真实验与结果分析

为了验证本文改进算法的有效性，对BC-ATA-GSR与2sMHR[12]、SSIM-InterF-GSR[17]以及PBCR-DCVS[11]进行重构性能对比，因为2sMHR是重构速度最快且效果不错的多假设重构算法，SSIM-InterF-GSR为本文BC-ATA-GSR提供了基础框架，PBCR-DCVS是最新且效果最好的多假设重构算法。仿真平台为Core i5(3.2 Hz)处理器、内存8 GB的台式计算机，操作系统为Windows10旗舰版，仿真软件为Matlab R2016b。

3.1 重构质量结果对比分析

3.1.1 重构QCIF格式视频序列的性能对比分析

比较QCIF格式视频序列的重构结果可以看出：①对于几乎静止的视频序列Mother-daughter和Suzie，BC-ATA-GSR的平均PSNR比2sMHR最高提升了1.86、1.40 dB，比GSR-SSM-InterF最高提升了2.21、1.30 dB。这类视频序列大部分由平稳块构成，在重构质量高的关键帧中能搜索到相似程度高的图像块，利用关键帧中的相似块可以更精确地重构平稳区域。②对于物体运动快且无规律的视频序列Soccer和Football，BC-ATA-GSR的平均PSNR比2sMHR最高提升了3.77、2.82 dB，比SSIM-InterF-GSR最高提升了1.80、0.68 dB。这类视频序列中的图像块以运动块居多，而运动块经过大初始阈值的硬阈值处理后，只保留了初始重构图像中物体的主要轮廓，再经过SBI迭代重构得到更准确的物体细节信息。③对于物体运动轨迹规律的视频序列Coastguard，BC-ATA-GSR的平均PSNR比2sMHR和SSIM-InterF-GSR最高分别提升了0.64、0.78 dB。

Mother-daughter序列在采样率等于0.1时，BC-ATA-GSR的重构质量比2sMHR略低，因为慢速序列参考帧中相似块数目多，在初始重构图像质量低时利用多假设更能准确预测当前块。而Coastguard序列在采样率为0.1时，BC-ATA-GSR的重构质量也不及其他两种算法，因为Coastguard序列中的运动块含有水纹、石头这些纹理较多的物体，BC-ATA-GSR设置的大初始阈值不可逆地滤去了一部分初始重构中的纹理。

表1 3种算法重构QCIF序列的PSNR对比

图6是3种算法对Soccer序列第13帧在0.1采样率下的重构视觉效果对比。从图中可知：2sMHR的重构图“块效应”较明显，运动员与背景的边界模糊，手和脚等运动部位不清晰；SSIM-InterF-GSR的重构图几乎观测不到块效应，但存在震荡波纹，方框区域比2sMHR图像更模糊；BC-ATA-GSR的重构图中运动员与背景交界的震荡波纹减少了许多，方框部分人物的四肢轮廓视觉效果更好。

图7是3种算法对Hall序列第27帧在0.1采样率下的重构视觉效果对比。从图中可知：2sMHR的重构图整体视觉效果较好，但人物运动的方框区域块效应明显；SSIM-InterF-GSR的重构图方框中也出现了模糊的重影；BC-ATA-GSR的重构图像既保留了清晰的背景信息，人物轮廓也更清晰可见。

图6 Soccer帧在0.1采样率下的重构视觉效果对比Fig.6 Reconstruction and visual effect comparison of Soccer frame at 0.1 sampling rate

3.1.2 重构CIF格式视频序列的性能对比分析

对BC-ATA-GSR与当前最新的视频压缩感知算法PBCR-DCVS[11]进行重构效果上的对比，同时加入2sMHR和SSIM-InterF-GSR的实验结果进行比较。取CIF格式的4个视频序列(Coastguard、Soccer、Foreman、Mother-daughter)前88帧进行观测重构，GOP=8。在编码端，观测矩阵为高斯随机矩阵，观测块大小为16×16像素，关键帧采样率为0.7，非关键帧采样率为0.1～0.5。PBCR-DCVS的重构结果取与文献[11]相同，其他算法的重构结果均通过仿真获得，比较分析了4种算法重构视频序列的PSNR，结果如表2所示。

由表2可以看出，整体上BC-ATA-GSR的重构效果最好。特别是Soccer和Foreman序列，BC-ATA-GSR比PBCR-DCVS最高分别提升了2.16 及1.68 dB，且随着采样率的升高，两者的PSNR差值越来越大。Foreman序列运动缓慢且背景纹理规律，平稳图像块的数量居多，可以利用高质量重构的关键帧提升重构质量；BC-ATA-GSR中的自适应字典学习方法使得图像块的稀疏表示系数更少，可以保留大部分纹理信息，故其重构效果比基于多假设预测的PBCR-DCVS要好。Soccer序列运动轨迹复杂，非重叠块重构的PBCR-DCVS很容易产生块效应，导致运动区域的图像块无法清晰显现物体的边缘;BC-ATA-GSR不仅通过重叠分块消除了块效应的影响，还根据图像块种类分类讨论了阈值选择，利用合理的阈值大小有效地保留了运动物体的主要轮廓。但是对于纹理结构复杂的视频序列如Coastguard和Mother-daughter序列，SSIM-InterF-GSR、BC-ATA-GSR的重构效果都与PBCR-DCVS相近，因为多假设预测通过利用当前块位置附近像素的局部相似性，能更好地保留分布较为随机的纹理结构。

表2 3种算法重构CIF序列的PSNR对比

在0.1采样率时，2sMHR和PBCR-DCVS的重构质量大部分比BC-ATA-GSR好。这是因为BC-ATA-GSR在低采样率下的阈值数值较大，删除了初始重构图像得到的许多纹理信息；另外，重构慢速序列时，多假设算法能通过周围块加权得到较为准确的预测块，提高了重构质量。

3.2 算法时间复杂度对比分析

将BC-ATA-GSR与2sMHR、SSIM-InterF-GSR进行时间复杂度的对比分析。选取4组格式为QCIF的视频序列(Soccer、Football、Mother-daughter、Foreman)的前88帧进行重构，GOP=8，关键帧采样率为0.7，非关键帧采样率为0.1～0.5。首先，定义两种算法的相对时间减少比例Pt：

(12)

式中，tS1和tS2分别为SSIM-InterF-GSR和BC-ATA-GSR的平均每帧重构时间。3种算法重构各个序列的平均时间复杂度以及相对时间减少比例如表3所示。从表中可以看出，在各采样率下BC-ATA-GSR的时间复杂度均比SSIM-InterF-GSR低，相对时间减少比例大致在25%～40%，最高可达到42.08%，这是因为BC-ATA-GSR采用了迭代阈值梯度下降的方案，使得在迭代后期重构图像的PSNR达到较高的稳定值，可以更快地满足退出迭代条件，有效地降低计算复杂度。另外，在相同采样率下，重构慢速序列(Mother-daughter，Foreman)比重构快速序列(Soccer，Football)要快很多，因为慢速序列中平稳块数量居多，其参考帧数量比运动块少；而且图像初始重构质量较高，迭代步数一般较少。2sMHR重构不需要迭代，故其时间复杂度远低于SSIM-InterF-GSR和BC-ATA-GSR。

4 结论

在基于结构相似性的组稀疏表示重构算法(SSIM-InterF-GSR)的基础上，本文提出了基于块分类的自适应阈值调整组稀疏重构算法(BC-ATA-GSR)。BC-ATA-GSR首先采用帧差法检测和分类图像块，并选择不同的参考帧，以有效利用关键帧来提升平稳区域的重构效果；其次，根据采样率以及图像块种类自适应地设定迭代初始化时硬阈值的初始阈值，且随着迭代次数进行阈值梯度递减，以保留更多的有效细节，更快地退出迭代。实验结果表明：BC-ATA-GSR的重构质量整体上比大部分传统的视频压缩感知算法高，且视觉效果更好；BC-ATA-GSR的PSNR比2sMHR、SSIM-InterF-GSR最高分别提升了3.77、2.21 dB，比当前最新的PBCR-DCVS最高提升了2.16 dB；相对于SSIM-InterF-GSR，BC-ATA-GSR的时间复杂度最多降低了42.08%。

表3 BC-ATA-GSR和2sMHR、SSIM-InterF-GSR的时间复杂度对比Table 3 Comparison of time complexity among BC-ATA-GSR,2sMHR and SSIM-InterF-GSR