图像通信按光栅扫描顺序执行分块编解码，在传输过程中存在块丢失现象.信宿端的错误隐藏不需要对信源端进行任何改变，在恢复丢失像素的过程中完全不需要信源端的参与，属于图像通信的一类后处理技术，由于不需要增加编码冗余或改变码流结构而受到广泛关注^[1-2].大多数自然图像具有较强的空域相关性，空域错误隐藏算法需要通过可用信息来高效地预测丢失像素，提高可视质量^[3].

快速的空域错误隐藏算法均采用了低复杂度的线性插值机制，基本原理是利用已正确接收的邻域像素来进行加权预测.作为图像通信广泛使用的空域错误隐藏算法，高级视频编码(Advanced Video Coding, AVC)插值算法^[4]利用受损块的邻近像素进行双线性插值，通过计算上、下、左、右4个邻近像素的加权平均值来估计丢失像素，其权重与像素间的距离成反比.AVC算法难以恢复边缘较多或纹理较丰富的图像区域.内容自适应划分(Content Adaptive Division, CAD)插值算法^[5]利用边缘检测算子来评估受损块的边缘强度，根据强度大小将受损块分成三种类型：平滑块、纹理块和边缘块，分别选取相应的插值方式进行恢复，其计算复杂度较低.作为对象移除应用的典型技术，耗时的图像补全机制主要关注视觉主观效果，但在松散的时间约束下也有学者将其用于解决错误隐藏问题，Chung等^[6]提出了一种联合图像补全和线性插值(Hybird Inpainting Interpolation, HII)算法，并为两种机制的切换提供了判决门限.由于边缘结构比单一纹理在视觉上更为重要，边缘导向插值(Edge Guided Interpolation, EGI)算法^[7]首先通过自适应阈值Sobel算子估计显著的边缘信息，然后选择边缘效应最强的候选边缘进行多方向插值.对于存在强边缘的受损块，EGI算法有助于增强其边缘信息，然而要找到所有边缘的准确位置是非常困难的.多方向插值算法具有运行速度快与通用性好的优点，但当块间内容变化较大时，候选像素与权重具有不稳定性，影响恢复质量.

大多数自然图像具有低通特性，图像块可以被建模为基函数的线性组合.基于块的双边滤波(Block-based Bilateral Filtering, BBF)算法^[8]利用一对高斯函数来估计受损块的边缘信息：一个基函数用于测量受损块和可用邻域的相似度，另一个基函数用于测量两者的空域差异性，BBF算法的复杂度较低.基于最小均方误差估计器，Koloda等^[9]提出了一种多模式基函数(Multi-Mode Kernel, MMK)算法，通过计算受损块的概率密度函数，利用邻域信息来确定支撑模型阶数，通过耗时的迭代逼近机制来预测丢失像素.

近年来，信号稀疏表达广泛用于图像处理.稀疏线性预测(Sparse Linear Prediction, SLP)算法^[10]根据当前受损块的邻域情况调整扫描顺序和候选像素集合的形状，并用贝叶斯信息准则来确定预测器的阶数，预测器阶数的增加会导致复杂度呈指数级增长.随着机器学习的兴起，双稀疏表达(Dual Sparsity Regularization, DSR)算法^[11]通过主成分分析进行字典构建，解决了因图像数据不足造成字典训练无法完成的难题.DSR算法利用欧式距离小于某一阈值来确定用于字典构建的候选像素集合和模板像素集合，但固定阈值导致的候选块选取不准问题会降低预测模型的通用性.进一步地，联合稀疏学习(Joint Sparse Learning, JSL)算法^[12]改进了稀疏表达的字典构建与系数求解，利用自适应阈值来提高搜索候选像素集合和模板像素集合的准确性.目前，基于稀疏表达的错误隐藏算法均采用线下训练的字典构建，在实际应用中需要大量图像作为训练数据，难以适用于各种丢失模式.即使不考虑模型训练的耗时与泛化性问题，当前稀疏模型类错误隐藏算法的计算复杂度仍然过高.

在空域错误隐藏应用中，每个受损块相对较小但序号明确，恢复目标是在较低复杂度的约束下使重构误差达到可接受的程度.迭代类隐藏算法以高复杂度换取了恢复质量的轻微提升；一些隐藏算法专门针对特定的丢失模式进行模型训练或算法优化，难以适用于各种各样的丢失模式.因此，有必要提出一种新的空域错误隐藏算法，以更好地平衡通用性、计算复杂度和恢复质量等性能指标.

1 问题描述 1.1 块的丢失模式

在图像通信中，为了便于码流传输，多个块封装成一个包，一幅图像通常编码成若干独立的包，每个包可以单独恢复，当一幅图像出现了包丢失，信宿端根据受损块的位置，利用邻域的无错块或已隐藏块进行恢复.空域错误隐藏不同于图像去噪或对象移除等应用，图像通信的信宿端能够获取受损块在图像中的具体位置.在光栅扫描顺序下，一个丢失像素的重构不仅依赖于正确接收的像素，也依赖于已经隐藏处理过的像素.为了便于描述，“可用像素”表示正确接收的像素或者已经隐藏过的像素；如果某种块丢失情形在接收图像中重复出现，本文称之为“规则”丢失.现有的错误隐藏算法均能很好地应对低丢失率的情形.根据受损块在图像中的整体分布情况，可归为4种丢失模式：规则间隔丢失模式、规则连续丢失模式、随机突发丢失模式、随机行丢失模式.

对于图像块的丢失，图 1展示了4种具有代表性的丢失模式，图中每个方块代表一个8×8或16×16或其他像素大小的图像块，正确接收的块用白色标记，受损块用黑色标记.如图 1(a)所示，规则间隔丢失模式是一种广为运用的丢失模式，受损块在图像中的分布比较离散，其8个相邻块都已经被正确接收，由于可用的邻域信息比较充分，许多错误隐藏算法都能对此种丢失模式进行有效的恢复.图 1(b)给出了规则连续丢失模式的块分布情形，其中，当前受损块的4个相邻块被正确接收.图 1(c)给出了随机突发丢失模式的示意图.图 1(d)展示了随机行丢失模式的一个示例，受损块集中出现在图像中的某些整行，由于受损块水平方向的邻域信息已经损失，可资利用的相关信息较少，许多隐藏算法针对此丢失模式都达不到满意的效果.

空域错误隐藏的主要应用场合是图像通信的实时后处理.对于现有的空域错误隐藏机制，一方面，插值机制的计算复杂度较低，但图像细节恢复的效果一般；而稀疏表达机制的计算复杂度较高，不太适合实时性要求严格的场合.另一方面，许多空域错误隐藏算法只针对特定的丢失模式进行优化，难以适应不同的丢失模式.因此，有必要在通用性、计算复杂度和恢复质量之间寻求更具竞争力的算法.

1.2 最大后验预测

延拓区域的像素相关性通常被建模为一个条件随机过程，空域错误隐藏可以采用最大后验准则来估计当前受损块的像素^{[4, 12]}.从统计学的观点来看，错误隐藏问题可以等价为在一个延拓区域内，通过一个可用像素子集{q_m} (1≤m≤M)的信息来预测当前丢失像素子集{p_k} (1≤k≤K).K和M的大小关系取决于不同的隐藏策略.{p_k}的最大后验估计能表示为最大化联合条件概率ρ(p₁, …, p_K|q₁, …, q_M)，但是K或M的取值范围通常是比较大的，难以进行准确地建模，在实际应用中获得这一联合条件概率几乎是不可能的.由于一个延拓区域通常是一幅图像的小块区域，往往能够近似成为一个准平稳过程，上述最大后验估计的简化策略是基于线性加权的方式来预测每个丢失像素.

$ {p_k} = \left\{ \begin{array}{l} \sum\limits_{m = 1}^M {{\beta _m} \cdot {q_m},k = 1} ;\\ \sum\limits_{n = 1}^{k - 1} {{\alpha _n}{p_n} + \sum\limits_{m = 1}^M {{\beta _m} \cdot {q_m},} 2 \le k \le K.} \end{array} \right. $

(1)

对于公式(1)中的加权系数α_n和β_m，自适应系数相比于固定系数能更好地表达图像的局部相关性.作为错误隐藏问题的一个一般性假设，空域错误隐藏算法大都假设合成的边缘在穿越受损块时是准直线的，因此可利用多方向插值来恢复受损边缘.在光栅扫描顺序下，多方向插值逐一地估计受损块在不同方向上的像素相关性，然后对邻域像素值与相关系数进行加权叠加.每个当前受损块对应着一个延拓区域.如图 2所示，一个延拓区域A含有3×3个块：当前受损块C位于中心，其它8个块分别属于以下3种类型之一：正确接收的无错块E、已经执行错误隐藏的已隐藏块R、还未进行错误隐藏的后续受损块S.

2 所提算法

本文提出了一种非迭代收缩多方向预测(Non-iterative Shrinkage Multi-directional, NSM)算法，所提算法吸收了现有多方向插值与稀疏模型学习的优点，通过引入自适应的邻域梯度特征学习机制，高效地获取受损块的邻域信息，随后通过精细设计的收缩填充次序进行逐像素的多方向插值.

2.1 基于梯度特征的自适应学习

现有的空域错误隐藏算法表明，根据梯度特征对受损块进行自适应插值，可以较好地保持图像的结构和边缘信息.所提NSM算法通过在当前延拓区域的无错块E和已隐藏块R中执行梯度特征统计过程，累计当前延拓区域的梯度分布；基于无错块E和已隐藏块R，分别累计8个方向中各方向上的梯度幅值.p_{i, j}表示位于坐标(i, j)的像素，梯度检测可以表示如下：

$ {\nabla _{i,j}} = \left[ \begin{array}{l} {\mathit{\boldsymbol{g}}_x}\left( {i,j} \right)\\ {\mathit{\boldsymbol{g}}_y}\left( {i,j} \right) \end{array} \right] = \left[ \begin{array}{l} \partial {p_{i,j}}/\partial x\\ \partial {p_{i,j}}/\partial y \end{array} \right]. $

(2)

式中，g_x(i, j)和g_y(i, j)分别表示在x水平方向和y垂直方向的像素强度变化率.现有空域错误隐藏算法的梯度检测采用了各向异性的Sobel或Canny算子，以利于检出较为准确的边缘信息.而本文算法仅需统计受损块邻域的总体梯度特征，各个方向的像素之间距离越远、相关性越小，掩模位置的加权系数应与到中心像素的距离成反比，而与方向无关，各向同性梯度检测器更有利于实现这一目标.因此，本文采用的各向同性梯度检测器含有两个3×3像素的梯度掩模算子，中心像素p_{i, j}的梯度分量g_x(i, j)和g_y(i, j)对其邻域执行如下两个3×3像素的梯度掩模算子.

$ {\mathit{\boldsymbol{g}}_x}\left( {i,j} \right) = \left[ {\begin{array}{*{20}{c}} { - 1}&0&1\\ { - \sqrt 2 }&0&{\sqrt 2 }\\ { - 1}&0&1 \end{array}} \right], $

(3)

$ {\mathit{\boldsymbol{g}}_y}\left( {i,j} \right) = \left[ {\begin{array}{*{20}{c}} { - 1}&{ - \sqrt 2 }&{ - 1}\\ 0&0&0\\ 1&{\sqrt 2 }&1 \end{array}} \right]. $

(4)

基于NSM算法，图 3所示的例子说明了如何利用各向同性梯度检测器来计算像素p_{i, j}的水平梯度g_x(i, j)和垂直梯度g_y(i, j)，其中，各向同性的梯度掩模算子用于计算各个延拓区域的水平或垂直梯度分布.各个邻域像素对中心像素的影响效应并不相同，所以不同的掩模位置有着不同的加权系数.

在获取中心像素p_{i, j}的梯度分量g_x(i, j)和g_y(i, j)之后，坐标(i, j)处的梯度幅值可通过如下公式推导：

$ \left| {{\nabla _{i,j}}} \right| = \sqrt {{{\left[ {{\mathit{\boldsymbol{g}}_x}\left( {i,j} \right)} \right]}^2} + {{\left[ {{\mathit{\boldsymbol{g}}_y}\left( {i,j} \right)} \right]}^2}} . $

(5)

|▽_{i, j}|表示在像素坐标(i, j)处的梯度幅值，对应的梯度角度表示为

$ {\theta _{i,j}} = {\rm{arctan}}\left[ {{\mathit{\boldsymbol{g}}_y}\left( {i,j} \right)/{\mathit{\boldsymbol{g}}_x}\left( {i,j} \right)} \right]. $

(6)

研究表明，超过8个预测方向已难以提升错误隐藏的恢复质量^[7].因此，每个梯度角度被归入到8个方向中的某一角度，每个方向的角度范围是成对的22.5°.在当前延拓区域的无错块E和已隐藏块R中，每个像素对应的梯度幅值和梯度角度分别通过式(5)和式(6)进行计算，由此为8预测方向累计梯度幅值.在获得延拓区域的梯度分布信息之后，非迭代收缩填充过程将对当前受损块的所有像素逐一执行多方向预测.

2.2 非迭代收缩填充

对于当前受损块中的不同像素，它们的填充先后次序会影响最终的恢复质量，因为已经隐藏过的像素可能导致错误扩散.对于由外至内的受损块像素填充，现有的空域错误隐藏算法预设了与受损块无关的像素填充次序，并没有考虑不同的丢失模式应具有差异化的像素填充次序.因此，本文算法在像素级可用度的基础上，新增了邻域级可用度的定义，从而设计出模式自适应的“收缩填充次序”.在大多数情况下，正确接收的像素和已经完成错误隐藏的像素有着相似的利用价值.对于任一像素p_l，它的像素级可用度α(p_l)被定义为

$ \alpha \left( {{p_l}} \right) = \left\{ \begin{array}{l} 1,若{p_l}被正确接收或已隐藏;\\ 0,若{p_l}是丢失或未知. \end{array} \right. $

(7)

如果某个像素已经被正确接收到，它的像素级可用度被设置为1.对于一个丢失像素，它的像素级可用度被初始化为0；在进行错误隐藏之后，它的像素级可用度被设置为1.一般而言，一个丢失像素的恢复质量会随着它的16邻域像素中可用像素的数量增加而提高.对于一个丢失像素X_k，它的邻域级可用度β(L_k)被定义为在它的16邻域像素L_k中所有像素级可用度之和

$ \beta ({\mathit{\boldsymbol{L}}_k}) = \sum\limits_{{p_l} \in {\mathit{\boldsymbol{L}}_k}} {\alpha ({p_l})} . $

(8)

有着更高邻域级可用度的像素应该被赋予更高的优先权.在当前受损块里，有着相等邻域级可用度β(L_k)的所有像素形成一个像素组，不同的像素组按照一组接一组的顺序进行隐藏.根据当前受损块内像素组的邻域级可用度，非迭代收缩填充首先恢复第1个像素组，它的像素有着最高的邻域级可用度.当第1个像素组内的所有像素按照先验填充准则进行错误隐藏之后，非迭代收缩填充将恢复第2个像素组，它的像素在受损块的所有像素中有着第二高的邻域级可用度，第2个像素组的所有像素同样按照先验填充准则进行错误隐藏，以此类推.光栅扫描顺序可能导致图像中的错误大致地从左上块向右下块进行扩散.一个像素组内的所有像素具有相等的邻域级可用度，各像素的填充顺序需要预先设定，图 4给出了本文所提的先验填充准则示意图，图中每个方框内的数字表示相应像素的填充次序.

在当前受损块内，位于外层的像素组由于有着较高的邻域级可用度, 通常具有更高的优先级，因此收缩填充次序呈现出从外层像素组到内层像素组的大致趋势.图 5(a)给出了对尺寸为8×8像素的当前受损块进行非迭代收缩填充的一个例子，当前受损块的相邻块都被正确接收，图中颜色越深的像素越晚进行错误隐藏，各像素上对应的数字表示该像素的填充次序.图 5(b)给出了当前受损块在非迭代重构过程中的次序幅度图，有着更高幅度的像素将越晚进行错误隐藏.一组接一组的像素组重构将大致从受损块的外层向内层进行，同时，丢失像素按照先验填充准则逐个进行恢复，这种像素级的恢复顺序被称为“收缩填充次序”.

梯度检测是为了获取延拓区域的梯度分布，丢失像素与邻域像素之间存在8个主要的预测方向.对于每个延拓区域，NSM算法利用无错块E和已隐藏块R的梯度特征统计，对多方向预测器的加权系数进行局部自适应调整.在恢复当前丢失像素时，可用像素的加权系数正比于当前丢失像素与该可用像素所在方向上的梯度幅值，当存在多个预测方向时，多方向预测器按照各方向上的梯度比例进行联合加权，使恢复的图像块具有与延拓区域类似的几何结构特征.NSM算法为每个丢失像素提供了一个基本隐藏单元，该单元由一个丢失像素周围的16邻域像素组成，存在8个等间隔的预测方向.基于一个基本隐藏单元，每一丢失像素利用在8个方向的可用像素及其权重进行最大后验预测.c_l^k表示在当前丢失像素X_k和它的基本隐藏单元可用像素p_l之间方向上的梯度幅值，NSM算法通过多方向邻域像素的加权叠加来恢复每个丢失像素：

$ {X_k} = \sum\limits_{{p_l} \in {\mathit{\boldsymbol{L}}_k}} {{\delta _l} \cdot {p_l}} = \sum\limits_{{p_l} \in {\mathit{\boldsymbol{L}}_k}} {\left( {\frac{{c_l^k}}{{\sum {c_l^k} }}} \right)} {p_l}. $

(9)

式中，L_k代表在丢失像素X_k的基本隐藏单元中可用像素集合，δ_l是一个正比于梯度幅值c_l^k的加权系数，NSM算法通过基本隐藏单元的可用像素来预测丢失像素.在执行多方向预测器时，非迭代收缩填充偶尔会面临一种极端的情况：对于某一像素的多方向预测，式(9)的所有δ_lp_l项都等于0.为了解决这一特殊问题，该像素将采用相邻块中与之最近的可用像素直接进行估计.填充次序与丢失像素的估计值无关，收缩填充的次序能够在当前块恢复之前确定下来.低复杂度的NSM算法能够避免严重的块效应，在受损边缘之间生成较为平滑的过渡效果.

2.3 复杂度分析

下面分析NSM算法的计算复杂度.在当前延拓区域A中，无错块E和已隐藏块R的可用像素被用于估计当前受损块C的梯度分布，计算开销主要是在每个可用像素处进行梯度检测，各向同性梯度检测器的计算复杂度取决于参与梯度掩模算子的像素数量a.假设块大小是s²个像素，E和R的块数量是b，则一个延拓区域包含b×s²个可用像素.因此，梯度特征学习的计算复杂度为O(a×b×s²)，各像素的梯度可供多个相邻块使用.为了恢复当前受损块C，每一丢失像素执行多方向插值，相应的计算复杂度取决于该像素的16邻域像素L_k中可用像素的数量d.对于一个受损块，非迭代收缩填充的计算复杂度为O(d×s²).令g=a×b+d，NSM算法的计算复杂度为O(g×s²).

类似的，非迭代类AVC、CAD、BBF或EGI算法的计算复杂度均可表示为O(q×s²)，通常g 或q都是较小的整数值.AVC算法的计算复杂度为O(s²)，其实时性最好；BBF算法的q值与NSM算法的g值基本相当.CAD算法采用了三种不同的隐藏算法进行错误掩盖，需要预判受损块的类型，内容自适应的预判流程增加了实现难度.EGI算法需要执行自适应的边缘提取，然而寻找所有边缘的准确位置是比较耗时的.因此，CAD与EGI算法的q值相对较高.当前恢复质量最好的空域错误隐藏算法采用了迭代逼近机制，然而每个像素的迭代重构过程是非常耗时的，迭代循环的次数往往超过100次^[10-12]，虽然迭代过程可以通过穷举法搜索出最匹配的候选者，但这一过程往往导致大量无效的重复操作，计算复杂度由此至少增长了一个数量级.

3 实验结果

为了评估NSM算法，本文在标准测试图像上进行了大量实验，块尺寸采用现有错误隐藏算法常用的8×8和16×16像素，并采用图 1所示的4种典型丢失模式：规则间隔丢失模式(丢失率≈25%)、规则连续丢失模式(丢失率≈50%)、随机突发丢失模式(丢失率≈20%)、随机行丢失模式(丢失率≈15%), 这些模式也为其他错误隐藏算法所采用.随机数生成器采用同一缺省种子，以便针对不同图像产生重复的随机突发或随机行丢失.下列测试图像均来自USC-SIPI图像数据库^[13]：Aerial、Boat、Couple、Elaine、House、Lena、Mandrill、Peppers、Barbara、Lighthouse、Crowd、Bridge，包含人脸、动物、植物、房屋等多种类型，格式被统一为8位深度的512×512灰度图像.NSM算法与绪论所述的空域错误隐藏算法进行了比较，包括AVC^[4]、CAD^[5]、HII^[6]、EGI^[7]、BBF^[8]、MMK^[9]、SLP^[10]、DSR^[11]和JSL^[12].为了比较不同算法的计算复杂度，本文在同一实验平台上测试了每种算法的运行时间，该平台包括Intel i5-4210M CPU (2.60 GHz)、8 GB内存、Windows10的64位操作系统、MATLAB R2018b.由于这些错误隐藏算法采用了相似的基本指令集，它们的MATLAB程序能够为算法复杂度的评估提供一定的参考.

两种最常用的重构误差测度：峰值信噪比(PSNR)和多尺度结构相似度(SSIM)用于评价受损图像的恢复质量^[14].PSNR或SSIM的评分越高，则图像的恢复质量越好.通过在每种丢失模式下分别测试所有图像的平均性能，表 1和表 2比较了不同算法的恢复质量.从表中可以看出，NSM与最好质量算法之间的平均值差距分别为0.85 dB的PSNR、0.022 1的SSIM.相比于较低复杂度的AVC、CAD、BBF和EGI算法，NSM算法分别取得了0.625 dB、3.461 dB、1.952 dB和0.506 dB的平均PSNR增益，同时取得了0.027 6、0.051、0.035 3和0.013 6的平均SSIM增益.

就计算复杂度而言，表 3显示了不同算法的运行时间比较.对于每种丢失模式，各算法的运行时间是恢复每一图像后的平均值.从表中可以看出，AVC、CAD、BBF、EGI和NSM可以被归为低复杂度的错误隐藏算法，而其它迭代类算法的运行时间至少增长了一个数量级.AVC算法的实时性最好，但其平均PSNR和平均SSIM仅高于CAD算法，恢复质量相较于其他低复杂度算法处于劣势.BBF算法比NSM算法稍快，但由于没有引入局部自适应的梯度特征学习机制，导致恢复质量较差.除了AVC和BBF算法，所提NSM算法相比于其他错误隐藏算法始终需要更少的运行时间，计算复杂度比迭代类算法低了一个数量级以上.NSM算法无需实测数据进行模型训练，对不同的丢失模式具有良好的通用性，其平均PSNR和平均SSIM在低复杂度算法中表现最好.

4 结论

在现有的空域错误隐藏算法中，运行快速的多方向插值算法在处理多种丢失模式时效果不甚理想，而恢复质量高的迭代类算法又难以满足实时性需求.为了改进当前空域错误隐藏的综合性能，本文提出了一种高效的非迭代收缩多方向预测算法，通过各向同性梯度检测器学习每个受损块邻域的梯度特征，随后根据精细的收缩填充次序逐一对丢失像素进行非迭代重构.所提算法在各种丢失模式下均能够获得良好的综合性能，在通用性、计算复杂度和恢复质量之间取得了一种具有竞争力的性能折衷.