基于马尔可夫随机场的加密二值图像有损压缩算法

李添正，王春桃

（华南农业大学数学与信息学院，广州510642）

（∗通信作者电子邮箱wangct@scau.edu.cn）

0 引言

实际应用中，为了节省带宽并保证图像在传输过程的安全，发送方在传输图像至公共信道前通常会先对图像进行压缩，然后再进行加密，但在云计算、分布式计算等环境中，由于计算资源有限（如传感器）或无利益驱动进行压缩，发送方通常不会在加密前先进行压缩，仅将图像进行加密后发送至云端。而云端为了节省存储空间或传输带宽，往往需要在无法获取加密密钥的情况下对加密图像进行压缩。接收方则在获得加密密钥及加密压缩图像的情况下，通过联合解压缩解密来重构原始图像。这种应用场景发展的系统通常称为先加密后压缩（Encryption-Then-Compression，ETC）系统。

尽管直觉上加密信号是无法压缩的，但Johnson等［1］通过把加密信号的压缩问题表征为带边信息的分布式信源编码问题，用信息论证明了加密图像压缩的可行性，且其理论压缩效率及安全性与先压缩后加密的系统性能一致；Schonberg等［2］通过引入马尔可夫信源模型，进一步提高了加密图像的压缩性能；Lazzeretti等［3］通过在加密前利用灰度或彩色图像空域、位平面间及不同色彩通道间的相关性，进一步提高了加密图像的压缩效率。通过先产生预测误差然后再进行加密及压缩的方式，Kumar等［4］较为显著地提升了无损压缩的性能；Liu等［5］借助截断Turbo码以及在接收方以分辨率演进的方式来提升加密图像压缩的性能；Zhou等［6］对预测误差进行聚类及随机置乱加密，获得接近以原始未加密图像作为输入的最优压缩算法的性能；Wang等［7］利用二维马尔可夫随机场（Markov Random Field，MRF）表征二值图像空域特征，并构建重构因子图来进行联合解压缩和解密，较大幅度地提高了二值图像的压缩效率。随后，他们将此思想推广到加密灰度图像的压缩［8］。

为了在一定质量损失的情况下获得更大的压缩率，研究人员也开展了加密图像的有损压缩算法研究。根据所采用的压缩技术，这些算法大致可以分为三类：第一类采用压缩传感技术［9-11］，即利用传统的压缩传感测量矩阵［9］、梯度投影矩阵［10］或者学习得到的词典［11］作为测量矩阵利用压缩传感技术来实施压缩，并用改进的基追踪（Basis Pursuit，BP）算法进行重构；第二类采用量化技术［12-18］进行压缩，即利用标量量化器对加密信号进行量化来进行压缩，其中量化步长通过多种策略进行优化，接收方通过解密和反量化方式来重构原图像；第三类利用均匀下抽样技术［5，19-21］来进行压缩，并在接收方利用内容自适应插值算法重构图像。

当前加密图像压缩算法可分有损压缩及无损压缩两类。由上述的文献分析可知，当前已有针对加密二值［1-2，7］、灰图［2-6，8］及彩色像［4］的无损压缩与重构算法，但所有相关的加密图像有损压缩算法都是针对灰度或彩色图像的，并没有针对加密二值图像的压缩与重构算法。而诸如签名、合同、指纹图像、黑白图像等二值图像在日常生活中仍旧有大量的应用，尽管当前有众多二值图像的压缩算法，但这些算法并不能直接用于加密二值图像的压缩。因此，开展针对加密二值图像的压缩与重构仍然具有重要的理论和实践意义，当前仍鲜有这方面的研究。针对此情况，并考虑MRF在表征二值图像空域统计特性方面的优势［7］，本文提出针一种基于MRF的加密二值图像的有损压缩算法。具体而言，发送端利用流密码对二值图像进行加密；云端对加密图像分块后用随机抽样方式进行下抽样，对下抽样后留下的像素进一步用低密度奇偶校验（Low-Density Parity-Check，LDPC）码进行压缩；最后在接收端联合MRF因子图、加解密复用因子图和LDPC解码因子图形成联合的重构因子图，以有损重构二值图像。实验仿真时，本文算法与针对原始未加密二值图像的、具有优秀压缩性能的国际通用标准JBIG2方法进行性能比较。这是因为根据对文献尽可能的掌握，当前并未发现针对加密二值图像的有损压缩算法；且根据Johnson等［1］的研究，先加密后压缩系统的压缩及安全性能与先压缩后加密系统的一致，因此可以通过与传统压缩方法性能的比较来等价地评估加密图像压缩算法的性能。实验结果表明，本文算法获得了较高的加密二值图像压缩效率，并与JBIG2算法压缩性能相当。考虑到JBIG2是针对原始未加密二值图像进行压缩的，而本算法则是针对加密二值图像的压缩算法，上述实验结果印证了Johnson等［1］的理论证明，与JBIG2压缩性能相当也充分表明了本文算法的可行性和有效性。

本文主要贡献：1）针对基于MRF的重构方法特点，提出了一种基于分块随机抽样的下抽样方法，既能使下抽样后的序列尽可能均匀分布，又能方便实现任意的下抽样率；2）构造了包含LDPC解码、解密及MRF重构因子图的联合重构因子图及相应的和-积算法，以实现加密压缩二值图像的有损重构；3）提出一种新的加密二值图像压缩算法，获得较高的压缩效率，且跟以原始未加密二值图为输入的JBIG2算法压缩性能相当甚至更好。

1 背景知识

1.1 因子图及和-积算法

因子图［22］是用来表示全局函数f(x1，x2，…，xn)和局部函数fj(X j)的图模型，其中，X j是集合｛x1，x2，…，xn｝的真子集，索引j用于区分不同子集。

设全局函数可分解为若干局部函数的积，即有：

对于式（1），若用圆圈表示变量节点xi，用小正方形表示因子节点fj，且每个fj都与其对应的自变量集合Xj内的变量节点xi有连接边，就构成了因子图，如图1所示。

图1 消息更新示意图Fig.1 Schematic diagramof messageupdate

因子图中，对于每一个变量节点xi，都有与之对应的边缘函数f i(xi)，定义为：

其中～{xi}表示除变量xi以外的所有变量集合。对于边缘函数，可以用和-积算法进行高效计算。该算法可高效同时地计算从变量节点到因子节点的消息（记作vx→f(x)），并更新从因子节点到变量节点的消息（记作μf→x(x)）。其中，vx→f(x)用“积”方式计算，即有：

其中，h∈N（x）f代表x除f外的所有相邻节点。μf→x(x)用“和”方式计算，即有：

然后，将所有传给变量节点x的消息进行累乘，即可得到该节点的边缘函数，即：

1.2 MRF及其因子图

马尔可夫随机场（MRF）具有良好的图像空间统计特性表征能力，并获得了广泛应用［23-24］。首先介绍随机场的概念。设I(x，y)是像素深度为Q、大小为W×H的图像，其每一个位于s∈L(L={(x，y)|x∈ [1，W]，y∈ [1，H]})的像素都对应一个随机变量Fs，取值空间为Φ(Φ={0，1，…，2Q-1})，则这些随机变量的集合就是随机场ℱ，即有：

设I(x，y)在坐标集合L上的邻域为δ(s)={s'|‖ ‖ss'≤d，s≠s'，{s，s'}⊆L}，则邻域系统表示满足图像I(x，y)上任一点到坐标s的距离小于或等于d的点的集合，但不包括点s。图2示例了二维空间中到参考点(a，b)距离小于等于5的所有集合，方格数字代表到参考点的距离。

图2 邻域系统Fig.2 Neighborhood system

如果随机场ℱ满足下面两个条件：

1）非负性：

2）马尔可夫性：

则该随机场称为马尔可夫随机场。文献［25-27］发现马尔可夫随机场与吉布斯（Gibbs）随机场等价，因此可得到MRF的具体计算公式，即有：

其中：E(X)为能量函数，U是邻域内所有基团的集合，Vu(⋅)是通过给定基团的簇势函数，Ω={F=(F1=f1，F2=f2，…，FWH=f WH|fs∈Φ}。势函数的阶为n时，则MRF的阶为n-1。

根据式（10）可得出MRF条件转移概率：

因此，势函数对MRF的构建起到了决定性作用。换言之，可以通过对势函数研究来代替对MRF的研究。

2 本文算法

为在保证一定图像质量的前提下进一步提高压缩率，本文设计一种针对加密二值图像的有损压缩算法。鉴于云端实际上无法获取加密密钥，因此本文采用了下抽样方式来对加密二值图像进行压缩。为了充分利用载体信号间的统计依赖关系，抽样后留下来的像素要尽可能在空间上呈现均匀分布；为了方便实现任意的下抽样率，每一块内采用随机抽样。为此，本文设计了一种适应各种压缩率的分块随机下抽样方法。对于下抽样后的序列，利用LDPC进一步进行压缩。接收方收到加密压缩序列后，构造包含LDPC解码、解密及MRF重构部分的重构因子图，实现原始图像的有损重构，其中，下抽样后的序列可以无误地进行重构，但下抽样过程中被丢弃的像素则需要通过其他辅助手段来进行有损重构。最直接的方式是利用插值法来重构下抽样过程中被丢弃的像素，但此法重构性能较差。考虑到MRF能很好地表征图像的空域统计分布，因此若能在无误重构的下抽样序列基础上进一步借助MRF，则将能更好地实现其他像素的有损重构。鉴于MRF能良好地表征图像的空域统计特性，上述方法将能在一定的压缩率下获得较好的重构质量。

图3给出了本文提出的基于MRF的加密二值图像有损重构算法。本文算法包含3个部分，即发送方的加密操作，云端的分块随机下抽样，以及接收方的联合解压、解密和有损重构操作。各部分的具体细节分别描述如下。

图3 本文算法流程Fig.3 Flowchart of the proposed algorithm

2.1 载体图像加密

设二值图像I(x，y)的大小为W×H，按逐行扫描的方式得到一维二值序列I={I i|i=1，2，…，WH}，然后用流密码对I进行加密，具体如下。

伪随机数发生器通过密钥种子KEY1生成长度为WH的一串随机密钥K={K i|i=1，2，…，WH}。为了保证加密的安全，每次加密一幅二值图像时，都生成不同的密钥K，以实现“一次一密”。根据香农的理论证明，“一次一密”的加密方法具有可保障的安全性。产生密钥后，采用异或运算对二值图像进行加密，即有：

加密后，得到加密二值图像序列C={C i|i=1，2，…，WH}。该加密二值图像看上去是一幅随机二值图像，随后，加密图像序列C通过公共信道传给云端，密钥种子KEY1则通过安全信道传给接收方。

2.2 基于分块随机下抽样的压缩

为了节省存储空间或者传输带宽，云端需要在无法获得加密密钥的情况下对接收到的加密图像进行压缩。如前所述，为了便于尽可能高质量重构，云端采用下抽样的方式进行压缩，且下抽样后的像素尽可能在空间上进行均匀分布。为此，本文采用基于分块的随机下抽样方法，具体介绍如下。

云端把加密二值图像序列C重新构成W×H的加密二值图像I'(x，y)。为了能在尽可能均匀的情况还易于操作，本算法采用基于分块的随机下抽样。即把I'(x，y)划分成互不重叠的块，每块的大小为B×B。对于每一块，按下抽样率P(P∈[0，1])进行随机抽取，抽取位置由种子密钥KEY2控制下生成的随机数来确定。因此每块下抽样后得到长度为B2P长的序列，其中⋅代表向上取整函数。这样I'(x，y)下抽样后得到长度为N=WHP的序列，2，…，N}。

为了进一步提高压缩率，本文基于Johnson的ETC框架［1］，对下抽样序列Cˉ利用LDPC进行压缩。设LDPC的码率为R(R∈[0，1])，码长为N，对应的校验矩阵为N(1-R)×N大小的A，则基于LDPC的压缩［28］为：

根据式（12），密钥K与加密序列C是相关的，因此可以把密钥K作为C的边信息；类似地，下抽样密钥Kˉ与Cˉ也是相关的。如果原始二值图像中非零比特较多，则Kˉ与Cˉ的相关性变小，有可能会导致LDPC解码失败。此时，需利用位掺杂技术来应对。

所谓掺杂技术，即是云端向接收方提供未压缩的加密比特消息。这样接收方利用该掺杂比特直接重构相应的像素，从而可以提高边信息的质量而提高解码成功率。由于发送1个未压缩的加密比特，就等价于校验矩阵A中增加一个度为1的行，这样就可以把比特掺杂与校验矩阵进行等效处理。即设掺杂率为dp_rate，则重新构造校验矩阵如下：

其中，矩阵D的大小为(dp_rate⋅N⋅(1-R))⋅N，且每行有且只有一个1。

当采用掺杂技术时，云端用新构造的Aˉ压缩Cˉ，即：

S=Aˉ⋅Cˉ （15）

采用上述方法压缩后，得到加密压缩序列S={S i|i=1，2，…，M'}，其中M'=(1+dp_rate)⋅N⋅(1-R)。基于此，压缩率可以计算为：

云端完成分块抽样和编码后，将联合压缩后的加密序列S及密钥种子KEY2发送到接收方。

2.3 构造联合二值图像解密解码因子图

当接收方收到压缩加密序列S、加密种子密钥KEY1、随机下抽样种子密钥KEY2后，进行联合解压缩、解密及基于MRF的重构。为了能充分地利用边信息以提升重构质量，本文利用因子图理论［22］把基于LDPC解码的解压缩、解密及基于MRF的重构操作都表征成因子图，并将这些因子图无缝整合在一起形成一个在联合解压缩、解密及MRF的重构用因子图（Joint Factor Graph for Decompression，Decryption，and MRF-based reconstruction，JFG-DDM）。设计好JFG-DDM后，通过在该重构因子图上运行和-积算法而实现有损重构。

图4给出了JFG-DDM的示意图，包含LDPC解码因子图、加解密复用因子图及MRF因子图，其中，LDPC解码因子图实现LDPC解码，即根据校正子S还原下抽样后的加密序列Cˉ；加解密复用因子图用于在迭代解码过程中，对传递的LLR（Log-Likelihood Ratio）消息进行明文状态和密文状态的转换，其中在MRF因子图下传递的是明文状态下的消息，在LDPC解码因子图中传递的是密文状态下的消息；MRF因子图用于为LDPC的迭代解码过程中，间接地、动态地提供额外的边信息，且用于重构那些因下抽样而丢失的像素。下面分别给出这3个因子图的具体设计及针对JFG-DDM的和-积算法。

1）LDPC解码因子图。

设S j(j=1，2，…，M，…，M')为接收到的校正子元素，其中S k(k=M+1，M+2，…，M')为掺杂比特（即只加密未压缩的比特），可根据加密特点直接确定该比特的原始未加密未压缩时的值，故可以在迭代译码开始时提供高质量的边信息；Ŷi(i=1，2，…，N)为LDPC解码过程中得到的加密下抽样序列；A j为校验矩阵A的第j行。那么，基于LDPC的压缩可以表示为：

为 经 LDPC 解 码 但 未 解 密 的序列。

图4 JFG-DDM示意图Fig.4 Schematic diagram of JFG-DDM

根据因子图理论，若用圆圈代表S j和Ŷi，用方框代表式（17）的函数约束关系，则可构造图5所示的LDPC解码因子图。其中，只要A j的第i列为1，就与因子节点gj连线。对于掺杂比特，根据其特点可知，S j和Ŷi都只有一条线连接至对应的因子节点gj，即有Ŷi=S j，这样就能在解码初始化时提供高质量的边信息，促进解码的收敛。掺杂比特对应的变量节点与常规变量/因子节点一样，无需区别对待。

图5 LDPC解码因子图Fig.5 Factor graph of LDPCdecoding

根据LDPC解码原理，对于此LDPC解码因子图，和-积算的消息更新方式如下：

其中，消息μ•→Ŷi表示其他因子图中因子节点向LDPC因子图中传递的消息。

2）加解密复用因子图。

加解密复用因子图用于迭代解码过程中，转换LLR消息在明文域与密文域之间的状态。

发送端采用流密码的方式对二值图像进行加密，因此流密码加/解密复用的全局函数可构造如下：

图6 本算法加解密复用因子图Fig.6 Multiplexingfactor graph of encryption and decryption

针对此因子图，加密过程消息更新为：

解密过程消息更新为：

此外，由于接收端已知密钥Kˉi，因此无需向Kˉi节点更新消息。

3）MRF因子图。

为了在复杂性和便利性间取得折中，本文采用一阶的MRF来表征二值图像的空域统计特性。后续的实验结果表明，采用一阶MRF是可行的。

具体来说，由于加密操作掩盖了二值图像原有的相关性，在不知道密钥的情况下，加密序列可以看成是离散无记忆信源。但是由于接收方已知密钥，而实际上图像像素间是存在统计依赖关系的，因此可以借助于加解密复用因子图的消息转换作用，构建MRF因子图来表达加密序列隐含的内在关系。MRF因子图有助于在LDPC迭代解码过程起到正反馈作用，加速解码收敛。即利用MRF表征的图像的统计依赖关系，来修正LDPC解码因子图中每次迭代解码结束时的消息，间接地、动态地为下一次迭代解码提供高质量的边信息。

由于本算法引入随机下抽样方法对图像进行有损压缩，因此存在两类像素，第一类对应加密下抽样序列经过LDPC解压及解密后得到的像素，第二类对应下抽样过程中被丢弃掉的像素。由此构造两种MRF因子图，分别如图7和图8所示，其中，图7表示MRF因子图会与相邻的加解密复用因子图进行连接，但图8表示MRF因子图不会与加解密复用因子图进行连接，以此对应下抽样后的二类像素的重构特点。

图7所示为第一类像素对应的因子图，此MRF因子图模型中的变量节点与文献［7］中的类似。以中间变量节点F̂x，y为例，其他第一类像素类似于此情况。在图7所示的MRF因子图中，方框Px，y代表像素的先验概率约束，ti代表相邻加解密复用因子图中的因子节点，Mx，y和Nx，y分别代表水平及垂直方向相邻像素之间的势函数约束。

图8为第二类像素对应的因子图，以中心变量节点F̂x，y为例，其他第二类像素类似于此情况。由于不与加解密复用因子图进行连接，因此与图7的最大不同之处是不与因子节点ti相连。图8是针对本文算法特有的MRF因子图。

图7 一般二值图像的MRF因子图Fig.7 Conventional factor graph for MRFof abinary image

图8 本文算法MRF因子图Fig.8 Factor graph for MRFof the proposed algorithm

对于本文MRF因子图中的第二类变量节点，因其未与相邻加解密复用因子图相连，因此只要把式（23）中的、来自于加解密复用因子图的消息μt(i)→F̂x，y去掉即可，得到下列的消息更新规则：

此外，v F̂x，y→Mx，y、v F̂x，y→Nx，y+1及v F̂x，y→Nx，y可类似处理。

对于消息μMx，y+1→F̂x，y、μMx，y→F̂x，y、μNx，y+1→F̂x，y及μNx，y→F̂x，y，则无需改变。

2.4 适用于因子图JFG-DDM的和-积算法

将2.3节中的LDPC解码因子图、加解密复用因子图及MRF因子图中相同的变量节点进行合并，即可得到本文算法用于加密二值图像有损重构的因子图JFG-DDM。在此因子图上运行和-积算法即可实现二值图像的有损重构。

基于和-积算法思想，针对本文算法重构因子图JFGDDM的和-积算法流程如图9所示。

图9 针对JFG-DDM的和-积算法流程Fig.9 Flowchart of sum-product algorithmfor JFG-DDM

具体描述如下。

1）初始化变量节点发出的消息。

结合分布式信源编码理论，利用加密密钥以及云端提供的掺杂比特信息，为解码初始化提供高质量的边信息，并初始化JFG-DDM中变量节点发出的消息。

当不采用掺杂比特时，用对应下抽样序列的加密密钥Kˉi直接生成边信息。此时在LDPC解码因子图中，变量节点Ŷi(i=1，2，…，N)向因子节点gj(j=1，2，…，M)发出的消息初始化方式如下：

若采用掺杂比特，因子图中的Ŷi与掺杂比特S k对应，其对应关系由前面KEY2决定，可得Ŷi=S k。掺杂比特S k作用在于，用于为解码开始时，进一步提高边信息质量。对于此部分由KEY2决定的关系，进而可知v Ŷi→gj的值为：

LDPC解码因子图中，变量节点Ŷi向加解密复用因子图发出的消息v Ŷi→ti可类似于v Ŷi→gj的初始化方式进行初始化。

若能确定S j为掺杂比特，可以确定=S j，进一步可以确定 像 素的 值 为在 这 种 情 况 下 ，消 息νF̂x，y→Mx，y可初始化为：

νF̂x，y→Mx，y+1、νF̂x，y→Nx+1，y、νF̂x，y→Nx，y和νF̂x，y→ti亦可类似地初始化。若Ŷi的值无法确定，则根据先验概率经验值Px，y进行初始化。例如，νF̂x，y→Mx，y可初始化为：

其他消息νF̂x，y→Mx，y+1、νF̂x，y→Nx+1，y、νF̂x，y→Nx，y和νF̂x，y→ti也可以类似地初始化。

2）更新因子节点向变量节点发出的消息。

前面已经计算出变量节点发出的消息，此步利用和-积算法中的“和”操作更新因子节点（Factor Node，FN）到变量节点（Variable Node，VN）的消息。

MRF因子图中，FN向VN的更新公式参考2.3节的式（24）。加解密复用因子图中，FN向VN的更新公式参考2.3节的式（21）和（22）。对于LDPC解码因子图，FN向VN的更新公式参考2.3节的式（19）。

3）更新变量节点向因子节点发出的消息。

接下来应用和-积算法更新变量节点VN到因子节点FN的消息。对于MRF因子图，因子图内部的VN向FN的更新消息参考式（23）和（25）。对于LDPC解码因子图，因子图内部的VN向FN的更新消息参考式（18）。

在加解密复用因子图中，当消息由LDPC解码因子图中的变量节点流向加解密因子节点ti时，ν̂更新方法为：

Y i→ti

当消息由MRF因子图中的变量节点F̂x，y流向加解密复用因子节点ti时，更新方法如下：

4）Ŷ的最佳估计。

经过新一轮的迭代（即FN向VN更新以及VN向FN更新）后，为了判断LDPC解码是否收敛，需要对LDPC解码因子图中变量节点Ŷi的边缘概率进行软判决。即首先累加各个变量节点Ŷi的所有消息，即：

考虑到消息传递采用了对数似然率（Log Likelihood Ratio，LLR），然后再进行如下的软判决，即：

5）判断迭代是否继续。

获得软判决的重构序列̂后，计算校正子S完全等于云端发送到接收方的校正子序列S，则表明LDPC解码成功，因此迭代重构算法结束。否则，继续进行前述的步骤2）～步骤4），直到LDPC解码成功或者达到最大的预设迭代次数为止。

6）重构估计图像。

若LDPC解码成功，则MRF因子图的第一类变量节点（即下抽样后被保留下来的像素节点）重构值为：

对于第二类变量节点（即下抽样过程中被丢弃的像素节点），首先类似于式（32）计算传到该变量节点的所有消息之和，然后再按照式（33）进行软判决。值得指出的是，尽管第一类节点也可以按照第二类节点进行重构，但可能存在因MRF因子图中更新的消息不甚准确而导致软判决错误的可能性。

3 实验仿真与分析

3.1 实验参数设置

实验仿真中采用了6幅大小为100×100、具有不同纹理特性的二值图像Baboon、Barb、Boat、F16、Lena和Tree作为测试图像，如图10所示。

图10 实验测试图像Fig.10 Test imagesfor experiments

考虑到本文算法为加密二值图像的有损重构算法，因此实验中采用bpp（bit per pixel）和BER（Bit Error Rate）作为算法性能的评估指标，其中，bpp表示每个像素压缩后的比特数，用压缩后的总比特数除以总像素来计算；BER为重构的二值图像与原始二值图像间的比特误差率，用两图像不相同比特的数量除于总像素数量来进行计算。在同等bpp情况下，BER越小表明重构质量越好；反之亦然。值得指出的是，根据BER可以计算得到相应的峰值信噪比（Peak Signal-to-Noise Ratio，PSNR），但BER的数值能更具体地反映重构图像的误差情况，故本文采用BER。

本文算法是在前期加密二值图像无损压缩研究［7］的基础上，进一步提出的针对加密二值图像的有损压缩方法。根据对文献尽可能全面的掌握，当前有为数众多的二值图像无损及有损压缩方法，但尚未发现加密二值图像的有损压缩方法。因此为了评估本文算法的bpp-BER性能，根据Johnson等［1］的先加密后压缩系统压缩及安全性能与先压缩后加密系统的压缩及安全性能一致的理论研究，本文主要与前期的加密二值图像无损压缩算法以及加密原始二值图像作为输入的JBIG2（Joint Bi-level Image Experts Group version 2）有损压缩算法进行性能比较，以此等价地评估本文算法的性能。下面分别给出本文算法及JBIG2算法的参数设置。

1）本文参数设置。

为了进一步探究均匀性与随机性间之间的关系，本节采用分块随机抽样（参考2.2节）、整幅加密二值图像随机抽样及均匀抽样三种抽样方式，然后在相同实验参数设置下比较它们的压缩性能。对于分块随机下抽样，为了尽可能保留二值图像在空域上的局部特征，分块的大小不应设置过大；本文根据实验情况折中设置分块大小为B=10。对于整幅图像随机抽样，利用伪随机序列确定抽取位置；对于整幅图像的均匀抽样，则根据抽样率确定抽样步长，然后根据步长均匀地抽取像素。

不论采用哪种抽样方式，当不采用比特掺杂方法（即dp_rate=0）时 ，MRF的 参 数 设 置 为δ=45、P=0.35和T=0.000 49；当采用比特掺杂方法时，MRF的参数设置为δ=45、P=0.5和T=0.000 49。根据前期的研究工作［7］，这些是较优的参数。另最优掺杂率dp_rate通过折半搜索获得。

实验仿真时，通过Matlab与C结合的方式实现本文算法。bpp用式（16）进行计算。

2）JBIG2参数设置。

JBIG2是一种针对未加密二值图像的、支持无损及有损压缩的国际标准［29-30］。虽然JBIG2允许进行有损压缩，但并未规定有损压缩的具体方法，而是通过在无损压缩前额外增加有损压缩预处理模块来实现。为了与本文的加密二值图像有损压缩算法进行比较，实验仿真中采用了JPEG作为有损压缩预处理模块。具体而言，实验仿真中先对二值图像进行灰度化预处理，即首先把二值图像的0和1分别映射成取值为0和255的灰度图像；然后对此灰度化图像实施量化因子为QF的有损压缩，得到相应的JPG图像；最后再以此有损压缩后的灰度图像作为JBIG2编码器（内置图像二值化功能）的真正输入。当该JPG图像输入JBIG2后，首先进行阈值为128的二值化，然后获得JBIG2压缩后的JB2文件数据流，以此实现有损压缩。

对于JBIG2算法，bpp计算方式如下：

其中：FileSize表示使用JBIG2算法得到的压缩文件的大小；W和H表示图像的宽度和高度。

3.2 重构过程演示

为了演示本文算法的重构过程，本节以二值Lena图为例，该图大小为100×100，像素值为1的百分比为50.6%。实验仿真时，采用码率R=0.525的LDPC码，并经折半搜索得到最优掺杂比特率。根据实验结果，采用最优掺杂比特率时对应的压缩率为0.507。图11（a）～（f）展示了二值Lena原图、流密码加密图以及迭代11、21、41和51次时的重构二值图。其中，迭代到51次时LDPC能无误解码，获得有损重构后的Lena，相应的BER为0.006。由图11可知，在近一半压缩率的情况下，无论是BER还是视觉效果，有损重构图像11（f）几乎逼近原始二值图像11（a）。

图11 Lena重构过程演示图Fig.11 Schematic diagramof reconstruction processof Lena

3.3 算法性能评估

3.3.1 抽样方式对压缩性能的影响

为评估本文算法性能，本节比较3.1节中设置的3种不同抽样方式时本文算法的性能，其中，采用分块随机抽样的本文算法记作MRF_BlkRnd，采用整幅图像随机抽样和均匀抽样的本文算法分别记作RANDOM和EVEN。

实验仿真时，采用具有不同纹理特征的二值图像Tree、Lena、Baboon和F16作为测试图像。对于步长为10%的每一个 下 抽 样 率P∈[30%，100%]，分 别 采 用 分 块 随 机（MRF_BlkRnd）、整幅图像随机（RANDOM）、整幅图像均匀抽样（EVEN）方式进行抽样；接收方在接收到加密压缩序列后，利用JF-DDM进行重构。对于每一个下抽样率P，都遍历LDPC的码率范围R∈[0.425，0.725]以找到最小的压缩率，遍历时的码率步长为0.025。对于所获得的三组实验数据，为便于比较，将压缩率bpp以0.025为间隔进行划分，并挑选每一区间内最小的BER值。基于此，得到图12所示的针对三种抽样方式的bpp-BER性能曲线。值得指出的是，当P=100%时，本文算法就等价于针对加密二值图像的无损压缩算法［7］，此时可以获得BER=0的结果。

图12 三种算法在不同图像间的bpp-BER性能比较Fig.12 Comparison of bpp-BER performance of three algorithms between different images

图12所示的实验仿真结果表明，MRF_BlkRnd总体上优于EVEN和RANDOM。这是因为MRF_BlkRnd采用了均匀分块而块内随机的下抽样方法，能较好地在均匀性和随机性间保持较好的折中，从而有利于借助解压解密重构的像素及MRF推断其他在下抽样过程中被丢弃的像素，重构性能较为稳定。然而，RANDOM的随机性较强，解压解密重构的像素有可能堆在一个局部而不利于借助MRF推断其他下抽样时被丢弃的像素；EVEN的均匀性虽然非常好，但有可能会因边缘纹理区域下抽样的像素数量少而影响重构质量。因此，采用分块随机进行下抽样是一种较好的选择。

3.3.2 与相关算法的性能比较

为进一步评估本文算法性能，本节比较本文算法（即MRF_BlkRnd）与有损JBIG2算法，其中，有损JBIG2算法借助于JPEG压缩方法来实现有损压缩，具体见3.1节描述。实验仿真中，JPEG压缩的QF设置为［1：100］，步长为1。若相邻QF导致相同的bpp，则取BER较小的那个结果。

考虑到本文算法是针对加密二值图像的压缩，而JBIG2是针对原始未加密二值图像的压缩，本节还分别以原始未加密二值图像以及对应的加密二值图像作为有损JBIG2算法的输入，以便更好地评估各算法的bpp-BER性能。为简便起见，这两种情形分别记作ORI_JBIG2和ENC_JBIG2。

利用3.1节及上述的实验参数设置，对6幅测试图像开展实验。首先评估不同方法的重构质量，图13中给出了MRF_BlkRnd和ORI_JBIG2在近似压缩率情况时的有损重构图像；但因ENC_JBIG2的压缩率大于1，难于进行比较，故图13中并未给出该方法的重构图像。鉴于篇幅限制，图13中以Barb和F16为例，除Baboon外的其他图像有类似情况；对Baboon而言，MRF_BlkRnd的压缩率都比ORI_JBIG2的低，因此难于进行同等压缩率下的重构质量比较。由图13可知，MRF_BlkRnd和ORI_JBIG2的重构图像都具有较好的视觉效果，且与原始图像相近；MRF_BlkRnd与ORI_JBIG2间的重构图像质量近似一致，差别不明显。考虑到ORI_JBIG2是针对原始未加密二值图像的压缩方法，而本文是针对加密二值图像的压缩算法，这就表明了本文算法的可行性。

图13 重构图像质量评估Fig.13 Evaluation of reconstructed images

其次评估算法MRF_BlkRnd、ORI_JBIG2和ENC_JBIG2针对6幅二值图像的bpp-BER性能，如图14所示。由图可知，MRF_BlkRnd算法的BER随着bpp的增加而逐渐减小，这是因为bpp的增大意味着压缩率的减小，从而使得重构误差也相应地减小。不过，MRF_BlkRnd的变化趋势并不是非常平滑，主要是因为分块内进行不同的随机抽样时，会呈现波动，如图14中Boat和F16的情况。此外，图14也表明，测试图像的压缩率落在0.2～0.4 bpp范围内，BER最多不超过0.05，这表明本文算法具有良好的率失真性能。

由图14可知，在相同BER情况下，MRF_BlkRnd相比ORI_JBIG2和ENC_JBIG2普遍具有更低的bpp。这主要是因为本文算法借助于MRF更好地利用了像素间的统计依赖关系，能更好地重构因压缩而丢失的像素，进而获得更高的压缩效率。

图14 MRF_BlkRnd、ENC_JBIG2和ORI_JBIG2的bpp-BER性能比较Fig.14 Performance comparison in bpp-BERbetween MRF_BlkRnd，ENC_JBIG2 and ORI_JBIG2

根据图14，ENC_JBIG2算法的性能远差于ORI_JBIG2和MRF_BlkRnd。这是因为ENC_JBIG2的输入图像是加密后的二值图像，JBIG2算法无法利用图像的统计特性进行压缩，自然没有办法获得好的压缩性能，从而比ORI_JBIG2和MRF_BlkRnd的性能差。

此外，对于ORI_JBIG2，在不同JPEGQF时的压缩率差别不大，BER通常随着QF的增加而减小。这是因为将原始二值图映射成取值为0和255的灰度图并经过JPEGQF有损压缩预处理后，无论采用什么样的QF，经过这些操作后的像素值大多数仍然分布在0或255的附近。这样当把JPEG压缩后的图输入到JBIG2压缩算法中，并以128作为阈值处理得到的二值图IJPEG(x，y)，与原始二值图I(x，y)差别较小，从而使得经过JBIG2压缩后的bpp相差不大。但当QF变小时，IJPEG(x，y)与I(x，y)的差别相对增大，导致解码后的BER也相应地增大。

再者，对于ENC_JBIG2中的加密二值图像，采用与ORI_JBIG2相同的处理流程。由于加密操作掩盖了载体图像的统计特性，因此JBIG2算法根本无法发挥其压缩优势，从而基本上无法进行压缩。再加上在JBIG2编码前进行了JPEG压缩，在编码后生成的jb2文件尚需要保存一部分辅助信息，导致压缩率略大于1.0 bpp。综合上述分析可知，相较于ORI_JBIG2，本文算法在不同bpp时的性能有好有差，但总体上性能相当甚至略好，即本算法压缩加密二值图像的压缩效率，能够达到JBIG2算法压缩常规二值图像的压缩效率。

由于ORI_JBIG2是以未加密图像作为输入进行压缩的，而本文算法是针对加密二值图像进行压缩的，因此本文算法是可行的和有效的。

4 结语

本文提出了一种基于MRF的加密二值图像有损压缩算法。其中，发送方用流密码进行加密；云端采用基于分块随机下抽样方法进行压缩，分块的目的在于令下抽样后的序列在空域中尽可能均匀分布，随机的目的在于方便实现任意的下抽样率；下抽样后的序列进一步利用LDPC校正子编码进行压缩；接收方构造包含LDPC解码、解密及MRF重构的重构因子图，以便在运行经适配的和-积算法时能实现加密二值图像的有损重构。实验仿真结果表明，本文算法具有较好的加密二值图像压缩效率，且bpp-BER性能总体上与以未加密原始二值图作为输入的JBIG2算法性能相当甚至更好。这就充分表明了本文算法的有效性和可行性。

本文算法设计的分块随机下抽样方法，虽然基本上是可行的，但在不同随机抽样情形下，bpp-BER性能却会有一定的波动，因此，后续研究中需进一步设计更好的下抽样方式。