基于压缩感知算法的图像压缩保密方法

宫丽美，张 旻，王方超

(1.解放军电子工程学院，安徽 合肥 230037; 2.安徽省电子制约技术重点实验室，安徽 合肥 230037)

基于压缩感知算法的图像压缩保密方法

宫丽美1,2，张 旻1,2，王方超1,2

(1.解放军电子工程学院，安徽 合肥 230037; 2.安徽省电子制约技术重点实验室，安徽 合肥 230037)

针对目前加密方法经压缩后对图像进行加密处理，存在处理效率低、安全性低、算法复杂度高等缺点，提出基于压缩感知算法的图像压缩保密方法。该方法首先对图像进行分块，并分析了分块后的像素置乱加密效果，其次构造了压缩感知观测过程的加密模型，并论证了该模型具有计算保密性，最后通过图像分块的保密性分析和观测矩阵的保密性分析，证实压缩感知算法在压缩时也具有良好加密效果。实验结果表明，该方法鲁棒性强，易于实现，具有一定的工程应用价值。

压缩感知；图像加密；分块处理；观测矩阵

0 引言

随着卫星、无人机等升空平台的大量涌现，如今获取图像信息的能力有了极大提高，尤其在军事领域， 图像侦察发挥着越来越重要的作用[1]。但因图像数据量巨大，为减少存储空间、提高传输效率，需对传输图像进行压缩处理。压缩感知理论(Compressive Sensing, CS)突破了传统的奈奎斯特采样定理的限制，只需少量观测数据，即可高精度重构原始信号，大大降低了对采样编码端硬件的要求，在图像压缩领域表现出巨大的研究价值。但由于所获图像在回传中易被截获、篡改。因此，对原图像压缩的同时，采取一定方式对图像进行加密处理也很有必要。

目前，有学者提出基于图像像素的置乱算法[2]、基于混沌的图像加密技术[3-4]等加密方法对图像进行加密处理，但存在保密性不强等缺点；也有学者将压缩感知算法和传统的图像加密方法结合起来，形成新的图像加密方法，如文献[5]等提出了一种基于压缩感知的光学数字图像加密方案,借助双随机相位编码技术,实现了对数字图像的多重加密，但存在处理效率低、鲁棒性不强等缺点；文献[6]提出基于压缩感知和变参数控制混沌映射的图像加密算法，将CS理论运用到数字图像加密中，通过采用混沌控制变参数混沌序列来产生测量矩阵，增大了密钥空间，提高了加密系统安全性，但算法复杂度较高。本文针对上述问题，提出了基于压缩感知算法的图像保密方法。

1 压缩感知基本理论

压缩感知理论于2006年由Candès和Donoho正式提出[7-8]。压缩感知的核心思想是用一个与变换基不相关的观测矩阵将变换所得的高维信号，投影到一个低维空间上，然后从这些少量的投影中以高概率重构出原始信号，其理论框图如图1所示。

假设x=[x(1),x(2),…,x(N)]T，用一组标准正交基的线性组合可将其表示为：

(1)

式(1)中，ψ为基矩阵，ψ=[ψ1,ψ2,…,ψN],ψi为列向量，S为N×1维的列向量，是x在ψ的稀疏表示系数。如果S中只有K个非零(或绝对值较大)的系数，其余N-K个系数都为0(或绝对值很小)，则称x具有稀疏性。

压缩感知的观测过程即利用观测矩阵Φ∈RM×N对具有稀疏性的信号x进行线性测量，得到观测值y的过程[9]，如式(2)所示，

y=Φx=ΦΨS=ΘS

(2)

式(2)中，Θ=ΦΨ是一个大小为M×N的矩阵。

压缩感知的信号重构过程是一个求解线性方程的问题[10]，式(2)未知数的个数远大于方程的个数，是一个不定方程，有无穷多解。但由于系数S是稀疏的，可以通过求解最小l0范数来重构信号，如果观测矩阵Φ和稀疏变换矩阵Ψ满足约束等距性(Restricted Isometry Property, RIP)条件，即若对于所有的x∈∑k，存在一个δk∈(0,1)，使得：

(3)

式(3)中，x是一个k阶稀疏信号，δk称为RIP常数，此时称矩阵A∈RM×N满足k阶RIP条件。

可通过求解式(4)来精确重构信号。

(4)

式(4)中，‖•‖0为向量的l0范数，代表向量x中非零元素的个数。

2 图像压缩保密方法

2.1 图像分块

2.1.1 图像分块处理方法

由于无人机图像维度较高，为了降低测量矩阵的存储空间和解码重构的复杂度，利用基于压缩感知的图像压缩压缩算法处理图像时，首先对图像进行分块处理。

将大小为M×N的图像分成n个大小为B×B的小图像块，并将每一个图像块转换成列向量的形式进行表示，记xi(i=1,2,…,n)是第i块的列向量表示，则相应的观测值yi，可以表示成

yi=ΦBxi

(5)

式中，ΦB是一个大小为m×B2(0

(6)

2.1.2 像素置乱加密效果

图像分块的大小决定了观测矩阵的维度，同时会影响重构速度和重构质量，因此在对图像进行分块处理时会结合图像本身的大小和实际需求选择图像分块大小，图像分块大小具有不确定性。

分块处理获得的图像小块需转换成向量的形式进行测量，该步骤会打乱图像原有的像素排列，实现像素置乱(像素置乱是一种重要的传统图像加密手段)。分块大小的不同，会导致像素排列的完全不同，在分块大小未知的情况下，即使获得图像全部的像素信息，也很难正确排列组合，恢复出原图像。但由于分块的情况相对有限，在其它条件均已知的情况下可以通过穷举法获得图像分块信息。因而图像分块处理具有一定的保密性。

为了进一步说明图像分块处理对保密性的影响，本文对图像分块过程进行演示，如图2所示。图2(a)为4×4的图像示意图，每一个小方框代表一个像素，小方框内的数值标记不同像素的位置。图2(b)为2×2大小的图像分块示意图，图2(c)为分块后的小块图像转换成列向量的示意图。

根据图2(a)可得原始图像矩阵X如式(7)所示，矩阵中的元素代表的是原始图像中像素的位置；采用2×2的分块获得的待观测矩阵X1如式(8)所示，采用3×3的分块获得的待观测矩阵X2如式(9)所示。

(7)

(8)

(9)

经过对X,X1,X2中元素进行观察，可以看到X1,X2与X的像素排列完全不同，这就是图像分块达到的像素置乱效果，也验证了分块处理具有一定的保密性。

2.2 观测矩阵

2.2.1 观测过程加密模型的构造

利用文献[11]的对称加密算法构造了压缩感知观测过程的加密模型，具体构造过程如下：

待加密明文：待观测信号x∈X(X为明文文本);

加密函数：y=ΦKx；

加密后所得的密文：y∈Y(Y为密文文本)。

解密过程：由y求解x的过程。

以上即为压缩感知观测过程的加密模型，下面将进行观测过程加密模型的保密性证明。

2.2.2 保密性证明

为了证明该模型的加密性能，在此之前，先说明下加密算法的加密过程和解密过程，分别如式(10)和式(11)所示。

eK:p→c

(10)

dK:c→p

(11)

p为待加密内容称之为明文，且p∈P(P为明文文本)，c为加密后获得的密文，且c∈C(C为密文文本)，K为加密密钥，e和d分别为加密函数和解密函数。下面将引入完全保密性和计算保密性的概念。

定义1：完全保密性

若密文发生的概率独立于明文发生的概率，即满足式(12)，则称该系统具有完全保密性。

P(C=c/P=p)=P(C=c)

(12)

定义2：计算保密性

若系统解密过程是一个N-hard问题，也就是说在一个多项式时间内无法推测出所有密钥，则称该系统具有计算保密性。

压缩感知观测过程加密模型是否可实现有效加密，下面详细证明了压缩感知不具有完全保密性，但具有计算保密性。

推论1：压缩感知观测过程加密模型不具有完全保密性。

证明：

X是明文文本，PX(x)>0,∀x∈Rn,Φ为M×N维的矩阵，Y=ΦX。

根据式(12)可知要证明压缩感知观测模型作为加密系统是否具有完全保密性，只需证X与Y相互独立，此时加密系统具有完全保密性。

情况1：当X=0时

∵Φ是线性的，

∴ 当x=0时，y=0，

即PY/X(Y=0/X=0)=1。

又∵y=Φx，

∴ 当y=0 时，x必在Φ的零空间上，

又∵PX(x)>0,∀x∈Rn,

∴PY(Y=0)<1 ，

∴PY/X(Y=0/X=0)≠PY(Y=0)

∴ 即X和Y是非统计独立的，

∴ 当X=0时，压缩感知观测过程加密模型不具有完全保密性。

情况2：当X≠0时

∵Φ满足RIP准则，

∴

(13)

则由公式(13)可得,

PX/Y(x,/y)=0

又∵PX(x′)>0

∴PX/Y(x′/y)≠PX(x′)

∴ 即X和Y是非统计独立的，

∴ 当X≠0时，压缩感知观测过程加密模型不具有完全保密性。

综上所述，压缩感知观测过程加密模型不具有完全保密性。

推论2：

压缩感知观测过程加密模型具有计算保密性。

证明：

压缩感知的重构问题是一个求解0范数最优化的问题，如式(14)所示。然而Candès证明这是一个NP难的问题，因而通常将该问题转化成求解1范数最优化问题如式(14)所示。

(14)

引理：

Φ和Φ′是两个M×N维的独立同分布的高斯随机矩阵，若对于K稀疏的向量x=ΨS有y=Φx；对于Φ′利用0范数或者1范数重构时y=Φ′x′，则所得x′=ΨS′必为M稀疏的向量，且M≥K+1。

根据上述引理可知若想重构原图像必须保证使用相同的观测矩阵即Φ′=Φ。若能根据观测矩阵的维度推测出正确的观测矩阵，则说明式(14)有解。然而，Candès证明了式(14)的求解是一个NP难问题，因而无法在多项式时间内恢复出正确的明文。即压缩感知观测过程加密模型具有计算保密性。

3 实验结果与分析

为了验证本文对保密性的分析，利用Matlab实验仿真进行说明。实验所用软件为Matlab8.0，硬件条件为i7CPU，内存8 GB的计算机。实验图像为512×512的实测无人机图像。用于压缩感知观测过程的观测矩阵1、矩阵2、矩阵3均为随机产生的高斯随机矩阵，稀疏表示字典采用离散余弦字典，重构算法选取OMP重构算法[12]。

共设计了三组实验，实验1为对比实验，用于仿真合作方重构图像，为实验2和实验3的加密效果验证提供对照；实验2为图像分块处理加密效果验证实验；实验3为压缩感知观测模型加密效果验证实验。三组实验的采样编码端均采用32×32图像分块大小，并利用观测矩阵1对分块处理后的图像数据进行观测。

3.1 实验1：对比实验

重构端参数选择：图像分块大小32×32，采用观测矩阵1进行重构，实验结果如图3所示。

图3(a)为原始无人机图像，图3(b)为模拟合作方在各参数已知的情况下获得的重构图像。由图3(b)可以看出，根据正确的图像分块大小，利用和观测过程相同的观测矩阵进行重构时，获得的重构图像较原图像失真较小，重构效果较好。

3.2 实验2： 图像分块处理加密效果验证实验

重构端参数选择：图像分块大小分别为16×16和64×64，采用观测矩阵1进行重构，实验结果如图4所示。

图4(a)为模拟非合作方在观测矩阵已知，图像分块大小未知的情况下，利用小于编码端分块大小的16×16图像分块处理方法获得的重构图像。图4(b)利用大于编码端分块大小的64×64图像分块处理方法获得的重构图像。明显在图像分块大小未知的情况下获得的重构图像(图4(a)、(b))与合作方重构图像(图3(b))效果存在较大差距，验证了图像分块可以起到保密的效果。

3.3 实验3：压缩感知观测模型加密效果验证实验

重构端参数选择：图像分块大小32×32，采用观测矩阵2和观测矩阵3进行重构，实验结果如图5所示。

图5(a)为模拟非合作方在图像分块大小已知，观测矩阵未知的情况下，利用随机产生的不同于编码端观测矩阵的观测矩阵2进行图像重构，获得的重构图像。图5(b)为利用随机产生的不同于编码端观测矩阵的观测矩阵3进行图像重构，获得的重构图像。明显图5(a)、(b)两幅重构图像与图3(b)合作方重构图像效果存在更大差距，验证了压缩感知观测模型也可以起到保密的效果。

为了对本文各组实验重构图像质量进行定量分析，利用峰值信噪(PSNR)比对重构图像效果进行比较，结果如表1所示。其中，PSNR计算表达式如式(14)所示。

(15)

式中，I0(i,j)为原图像，IG(i,j)为重构后图像。

表1 重构图像峰值信噪比比较

从表1可以看出，实验2、实验3重构图像的峰值信噪比要远低于实验1重构图像的峰值信噪比，从三组实验仿真结果可以得出，基于压缩感知的图像压缩处理方法的图像分块处理过程和观测过程确实可以达到加密的效果。

4 结论

本文提出了基于压缩感知算法的图像保密方法。该方法通过分析图像分块处理的像素置乱加密效果，然后针对算法本身保密性进行分析，构造了压缩感知观测过程加密模型，并论证了该模型虽然不具有完全保密性，但具有计算保密性，最后对图像分块处理、观测模型的保密性进行了验证。实验结果表明，该方法鲁棒性强，易于实现，具有一定的工程应用价值。

[1]李德仁,李明. 无人机遥感系统的研究进展与应用前景[J]. 武汉大学学报(信息科学版), 2014, 39(5):505-513.

[2]吴成茂. 离散Arnold变换改进及其在图像置乱加密中的应用[J]. 物理学报, 2014(9):1-20.

[3]胡志高. 一种基于混合混沌序列的图像加密方法[J]. 软件工程师, 2013(3):34-37.

[4]邓晓衡, 廖春龙, 朱从旭,等. 像素位置与比特双重置乱的图像混沌加密算法[J]. 通信学报, 2014(3):216-223.

[5]刘效勇, 曹益平, 卢佩. 基于压缩感知的光学图像加密技术研究[J]. 光学学报, 2014(3):91-99.

[6]梁亚茹, 吴建华. 基于压缩感知和变参数混沌映射的图像加密[J]. 光电子·激光, 2015(3):75-80.

[7]CandèsEJ.Compressivesampling[C]//ProceedingsoftheInternationalCongressofMathematicians.Madrid,Spain, 2006:1433-1452．

[8]DonohoDL.Compressedsensing[J].IEEETransactionsonInformationTheory,2006,52 (4):1289-1306.

[9]王强，李佳，沈毅.压缩感知中确定性测量矩阵构造算法综述[J]. 电子学报,2013,41(10):2041-2050.

[10]BianchiT,BioglioV,MagliE.AnalysisofOne-TimeRandomProjectionsforPrivacyPreservingCompressedSensing[J].IEEETransactionsonInformationForensics&Security, 2015, 11(2):1-1.

[11]KazunoriHAYASHI,MasaakiNAGAHARA.AUser’sGuidetoCompressedSensingforCommunications[J].IEEETrans.InfTheory, 2013, 96(3): 685-712.

[12]HuangWeiqiang,ZhaoJianlin,LvZhiqiang,etal.SparsityandStep-sizeAdaptiveRegularizedMatchingPursuitAlgorithmforCompressedSensing[C]//2014IEEE7thJointInternationalInformationTechnologyandArtificialIntelligenceConference(ITAIC), 2014: 536-540.

Image Compression Confidentiality Based on Compression Sensing Algorithm

GONG Limei1,2, ZHANG Min1,2, WANG Fangchao1,2

(1.Electronic Engineering Institute, Hefei 230037,China; 2.Key Laboratory Electronic Restricting Technique, Hefei 230037, China;3.State Key Laboratory of Pulsed Power Laser Technology,Hefei 230037,China)

This paper studied several factors influencing the secrecy perception of the image compression based on compression sensing algorithm. Aiming at these problems, the confidentiality of image compression method based on compression sensing algorithm was proposed. First of all, the paper analyzed the image block processing could achieve pixel scrambling, and then build a encryption model about the compressed sensing observation process, at the same time, it was proved that the model although could not achieve perfect secrecy, but the calculating secrecy could not be achieved. The experiment results showed that this method had strong robustness and easy to implement for the further engineering application.

compressed sensing; image encryption; block processing; the observation matrix

2016-09-02

国家自然科学基金项目资助(61171170)；安徽省自然科学基金项目资助(1408085QF115)

宫丽美(1991—)，女，山东威海人，硕士研究生，研究方向：图像处理与信息融合技术。E-mail:gong_li_mei@126.com。

TP751

A

1008-1194(2017)01-0106-05