基于压缩感知的数字图像认证算法研究

邓桂兵， 周 爽， 李珊珊， 蒋天发*

(1.长江职业学院 信息化建设办公室， 武汉 430073;2.中南财经政法大学 统计与数学学院， 武汉 430073;3.中南民族大学 计算机科学学院， 武汉 430073)



基于压缩感知的数字图像认证算法研究

邓桂兵1， 周 爽2， 李珊珊3， 蒋天发3*

(1.长江职业学院 信息化建设办公室， 武汉 430073;2.中南财经政法大学 统计与数学学院， 武汉 430073;3.中南民族大学 计算机科学学院， 武汉 430073)

基于压缩感知相关理论，提出一种新的算法.将图像分成许多小块，观测这些小块图像得到压缩感知观测值，然后引入消息认证码算法，利用观测值得到图像摘要，把图像摘要通过量化索引调制法作为水印进行图像小波区域的嵌入，之后对于水印进行提取，将图片恢复.利用压缩感知理论将图像进行随机投影，再把水印和图像摘要进行比较，这样就实现了图像的篡改检测与图像认证.根据实验研究证实，此算法对局部篡改的检测功能较强，算法的隐蔽性很好，图像在经过图像认证后，能够进行无损恢复.

压缩感知； 图像认证； 篡改检测

随着我国社会经济的迅猛发展，我国的计算机网络技术的普及使得人们进入信息爆炸式传播的时代，图片更是传递信息的一种不可缺少的方式，但是图片在网络传播的过程当中，被篡改失真的现象十分严重，尤其在计算机图片修改软件的日益强大之后，对图片的篡改更加疯狂，因此图像的真实性有待加强，对于图像的认证变得十分重要.压缩感知自提出以来，已经在很多领域得到了很好的应用和实践，如统计学、信息学、编码、数据隐藏等[1-2].压缩感知应用到数字水印中的两个方面:一是水印的预处理，即将水印经过压缩感知处理后再嵌入到载体图像中，处理之后水印的信息量将得到减少，这对于水印的隐蔽是十分有利的；二是水印的嵌入提取，也就是对载体图像进行压缩感知处理之后，再对它的压缩感知域中的系数进行修改从而来达到添加水印的目的，通过这些处理之后水印在载体图像中就具有了更好的隐蔽性.

本文先对压缩感知理论基本理论进行阐述，利用观测值得到图像摘要，把图像摘要通过量化索引调制法作为水印进行图像小波区域的嵌入，之后对水印进行提取，将图片恢复.利用压缩感知理论将图像进行随机投影，再把水印和图像摘要进行比较，这样就实现了图像的篡改检测与图像认证，并得出实验结果.

1数字图像认证算法

数字图像认证是一种无损图像认证，在对于水印信息进行提取之后，要将原始图像进行复原，这样图像的相关信息才具有真实性.随着无损图像认证技术在许多领域的应用越来越广泛，很多学者开始对于无损图像认证技术进行研究.文献[2]当中研究的是在水印基础上的认证可逆图像的方法，能够对于篡改进行检测，并且能够进行篡改的定位，然而，这种算法会将认证水印嵌入在像素的最不重要位置，这样图像具有比较差的鲁棒性.文献[3]当中的水印算法是图像能够自恢复和自嵌入的，不仅对于图像能够进行恶意篡改的检测与定位，还能够对于损坏图像部分进行恢复，然而这种恢复是部分恢复，不能完全恢复.文献[4]当中是以分块为基础的可逆认证算法，把图像进行可逆块和不可逆块的划分，不可逆块进行图像特征的提取，可逆块通过差值扩展算法进行自身块的嵌入，对于其他特征信息进行采集，这种算法不但能够将原始图像精确恢复，还可以精准定位图像恶意篡改攻击，然而算法十分复杂，要求可逆块属于大于等于非可逆块的数量，不然可逆认证不能成为现实.文献[5]通过插值扩展与纠错编码，得到了可以进行篡改图像块定位的可逆图像认证方案，然而纠错编码不可以完全保证水印提取正确性.文献[6]把图像进行分块后开展压缩传感随机投影，并把投影值作为零水印进行注册保存，不仅不能改变图像像素值，而且能够进行定位篡改检测， 但因为注册所需的零水印数据库容量有限，该算法具有一定的局限性.

本文对于图像能够通过水印算法进行完全认证.第一，先将原始图像利用压缩感知技术进行随机投影，图像会出现一个测量值.之后，利用哈希的消息认证码( HMAC)得到水印信息，之后利用量化索引调制算法(QIM)把嵌入在图像小波进行变换之后的低高频系数当中.进而进行整数小波的逆变换，得出含水印的图像.量化索引调制的过程是一个不可逆过程，在进行恢复的过程当中要考虑额外的相关误差信息，所以把量化索引调制出现的相关误差信息当中恢复密钥进行储存.

2水印图像预处理

2.1压缩感知的应用

压缩感知是指如果在一个正交的空间存在稀疏性信号或是信号能够被压缩，就可以用较低的频率进行信号采集，利用优化算法将采集信号进行高概率重构.然而普通的自然信号不能实现完全稀疏，要将信号进行稀疏表示[7].压缩感知理论框架如图1所示.

图1 压缩感知理论框架图
Fig.1 The compressed sensing theory framework

如果设定一个实值时间离散信号的长度为M，通过测量矩阵进行线性投影，矩阵的大小是N×M，那么能够测得长度为y，那么可以知道：

y=Φx,

(1)其中，测量矩阵用Φ表示，测量矩阵大小是N×M.用Ψ表示稀疏矩阵，大小同测量矩阵，如果信号基于Ψ具有稀疏性，那么可以进一步推导公式

y=Φx=ΦΨs=θs.

(2)

如果矩阵θ符合有限等距性质准则，那么就可以利用压缩感知理论逆解以上公式，这样就能够将稀疏系数s算出，之后利用x=Ψs解出x.很多压缩感知理论的研究都指出，压缩感知信号重构问题能够利用以上公式估计s的值[8]，数学模型为

(3)

然而由于(2)式是NP问题，对解的可靠性十分难验证或是根本无法求解，所以可以研究出转化问题的等价求解方式.可以将(3)变为对l1-范数的最优化，即

(4)

公式(4)的范数优化进一步可以转化利用线性规划解决.

2.2生成提取水印的过程

在得到压缩感知的测量值之后，这个值可以成为图像的内容特征，测量值不但能够将图像进行完整表示，还能够将原图像的数据量大大降低.将矩阵元素进行观测，加权累加图像的细小差距，将这些差距放大数倍，这样有效避免了相似图形产生同样的观测值，大大提高了图像观测的精确度.而且，测量矩阵能够对图像进行加密，这样如果出现攻击者，即使掌握了图形观测值，没有密钥也无法恢复原始图像，提高了图像的保密性[9-11].比较于某些自嵌入水印算法，利用压缩感知理论的水印算法能够更完善地提取图形信息，并且具有更高的保密性.其图像分为B×B小块[6-7]，然后将各图像子块经过压缩处理得到观测值，最后将观测值组合在一起生成水印，分块水印算法的构造流程如图2所示.

图2 基于压缩处理的分块水印构造流程图 Fig.2 Block based watermarking construction flow chart of compression

利用压缩感知理论分块水印算法的水印生成过程如下：

①把图像进行分块，小块图像的大小参考定位精度和水印数据量确定.

②利用压缩感知理论对小块图像进行处理.

③对小块图像进行压缩感知随机投影，将各块压缩感知随机投影得到的压缩测量值，再引入消息认证码算法，将测量值作为密钥相关的哈希运算消息认证码输入.密钥相关的哈希运算消息认证码要利用一个密钥和一个加密的哈希函数，这样就是在哈希函数的基础上增加了密钥，这样在哈希函数保密性的基础上又增加了更强的保密性.密钥相关的哈希运算消息认证码的相关计算公式是

HMAC(k，M)t=

H(k0⊕opad，H(k0⊕ipad，M))

(5)

其中，k0是B长度的密钥，k是认证密码，认证码长度是t，在MD5当中的t值为16，SHA-1当中的t值为20，ipad和opad都是B个字节构成的字符串，字节长度分别为0x36和0x5a；M是输入数据.

3水印算法

3.1嵌入水印算法方法

在进行水印提取的过程当中，篡改定位一定要保证其准确性，不然一些没有出现篡改的部分会被误确定为遭到篡改，引起篡改定位的不准确性，这被称作水印算法的鲁棒性.为了解决这个问题，一般会引入量化索引调制算法.设图像系数值是f，wu表示待嵌入水印数据，具体算法过程如下：

① 首先计算出n个量化步长，之后计算f与第n个量化步长的间距a(a∈[0，2bΔ])，其中量化步长是Δ，公式为：

n=f2bΔ；a=f-2bnΔ.

(6)

② 将水印数据嵌入，计算系数值：

(7)

提取水印和图像恢复算法:

① 量化步长个数n＇与量化间隔a＇的计算，公式为

(8)

② 将水印数据wu提取出来，公式为

(9)

③ 将原始系数f进行恢复，公式为

(10)

根据以上公式得到，假如系数f有n位存储精度，那么f'有n+b位存储精度.两数据精度不同，导致算法不可逆，所以要修改f＇的精度，公式为

wu∈{ 0，1，…，2b-1}.

(11)

如果需要将原始图像进行无损恢复，要将f＇的精度值额外储存.

3.2进行水印嵌入的过程

在引入算法之后，将水印进行嵌入，过程为：

①为了避免在水印嵌入之后进行逆运算的过程中溢出，要预处理图像.如果需要在水印提取端将原始图像恢复，就要将预处理信息进行存储[12-14].

②整数小波变换图像，取得低高频子带系数值.

③将低高频子带系数值的相关奇偶信息进行储存，之后得出位置图.在利用量化索引调制算法进行逆变换的过程当中精度信息就是低高频子带系数值的相关奇偶信息.将位置图进行储存，设为图像恢复使用的密钥.

④ 使用以上公式嵌入水印信息到系数当中.在公式当中b值为1，那么认为水印信息为二值信息.

⑤ 进行小波逆变换.

3.3水印提取算法与篡改检测

可以这样说，水印提取是水印嵌入的一个逆过程，其步骤如下:

① 将图像进行整数的小波变换，这样能够取得低高频小波系数值；

② 采取图像恢复密钥Lp与QIM逆算法将水印信息D提取出来并将系数C恢复，之后开展小波逆变换；

③ 如果图像分块的总数是T，那么认证水印为D里面前32T个信息流，S之后的信息流设为D1；

④ 参考D1和EOS标志对预处理位置图信息流Li计算，解码后得到Lm；

⑤ 在图像恢复之后，利用同样的生成算法进行比特流R的计算，之后把R划分成多个等长的比特流rl(l=0，1，…，T) ，其中，每个等长比特流为32 bit.还要对S进行相同操作，得到sl(l=0，1，…，T) .之后对这些值进行比较，如果相等，那么可以认为对应的图像块是能够认证的；不然，可以认为该算法已经被篡改.

4实验结果分析研究

对算法的水平利用篡改认证性与不可感知性进行评估.计算机实验分析软件为Matlab2013，利用哈夫曼编码与游程编码进行位置图的压缩.

4.1水印可提取性评估

在现实生活中，相关重要场合保密性比较高，不允许提供原始图像，这就要求对水印的可提取性进行评估以方便提取水印信息[15].该文利用观测矩阵和分块水印信息流进行提取，同时，测量矩阵能够对图像进行加密，这样如果出现攻击者，即使掌握了图形观测值，没有密钥也无法恢复原始图像，提高了图像的保密性.使提取者在没有密钥的情况下，无法通过随机构造观测矩阵与定位隐藏水印的分块来提取水印，因此在水印可提取性方面具有更好的灵活性与安全性.

表1 水印可提取性标准Tab.1 The watermark can be extracted from the standard

4.2算法的不可感知性评估

对于水印算法的不可感知性的定量测量通常会利用峰值信噪比，相关计算公式如下：

图3 几幅测试图像Fig.3 Sereral images of test

峰值信噪比结果见表2(数据取30次测试平均值).

表2 图片的峰值信噪比结果Tab.2 Pictures of the peak signal to noise ratio results

经过相关比较可以得知，本实验的算法对图像的不可感知性十分优秀，能够达到视觉不可查标准.图4、图5为分解后的低频到高频的信息.

图4 原始图像Fig.4 Original image

图5 分解后的图像Fig.5 Image after decomposition

4.3算法的篡改认证性评估

在得到压缩感知随机投影测量值之后，将测量值设定成图像内容特征，不但能够将图像更好地表示，还能够有效降低数据量，此外，最大的优势就是能够加强对篡改的敏感度.压缩感知测量值对图像的差异能够进行数倍放大，这样就能够检测图像的篡改，而具体方法是利用测量矩阵加权累计图像差异，就算测量值的差异十分细微，但是在哈希函数检验之后就会将差异放大无数倍，所以图像篡改认证的精确度为1 bit，精确度很高.图6～图8为篡改图像的检测.

图6 被篡改的图像Fig.6 Image tampering

图7 篡改位置Fig.7 Tampered position

图8 篡改图像检测结果Fig.8 Image forgery detection results

5结束语

根据本文的实验结果可以得到，利用基于压缩感知的数字图像认证算法的不可感知性和篡改认证性都十分良好，对篡改区域的定位十分准确，精确度高，能够将原始图像进行无损恢复.但是基于压缩感知的数字图像认证算法存在一些不完善的地方，那就是水印算法的严谨性过高，使得无意篡改和恶意篡改没办法区别，这一点还需要进行完善提高.本文对基于压缩感知的数字图像认证算法的实施过程进行具体研究，对我国的数字图像认证方面的发展具有积极的意义.

[1] 石永福， 杨得国， 李 智.一种基于小波变换的数字图像水印新算法[J]. 华中师范大学学报：自然科学版， 2013， 47(4)：479-482．

[2] 曹守斌. 基于图像认证的脆弱水印技术研究[D]. 杭州：杭州电子科技大学， 2011:33-37．

[3] Tiegang Gao， Qiaolun Gu. Reversible image authentication based on combination of reversible and LSB algorithm [C]//Proceedings of 2007 International Conference on Computational Intelligence and Security Workshops.Harbin，China，2007: 636-639．

[4] 黄晓晴. 分形编码的数字水印及图像检索中的应用技术研究[D].南京：南京航空航天大学， 2010:23-90．

[5] 杨恒伏. 结合视觉感知的图像认证与数据隐藏算法研究[D].长沙：湖南大学， 2009:48-81．

[6] Valenzise G， Tagliasacchi M， Tubaro S， et a1. A compressive-sensing based watermarking scheme for sparse image tampering identification[J]. IEEE Cairo Egypt， 2009: 1265-1268．

[7] Candès E J. Compressive sampling[J]. Proceedings of the International Congress of Mathematicians， 2006(3):1-20．

[8] 张 斌. 基于感知哈希与数字水印图像内容认证技术研究[D]. 北京： 北京邮电大学， 2011: 29-38．

[9] Tiwari A， Sharma M. Comparative evaluation of semi fragile watermarking algorithms for image authentication [J]. Journal of Information Security， 2012， 3(3):189-195．

[10] Tiwari A， Sharma M. A survey of transform Domain based Semifragile watermarking schemes for image authentication [J]. Journal of The Institution of Engineers (India): Series B， 2013， 93(3):185-191．

[11] Athira V， George S N， Deepthi P P. A novel encryption method based on compressive sensing[C]//Automation， Computing， Communication， Control and Compressed Sensing (iMac4s)， 2013 International Multi-Conference on Delhi India IEEE， 2013: 271-275．

[12] Wang Zhewei， Huang Mingwei， Ying Zilu. The performance study of facial expression recognition via sparse representation[J]. IEEE Machine Learning and Cybernetics (ICMLC)， 2010， 2(6): 824-827．

[13] Tiegang Gao， Qiaolun Gu， Emmanuel S. A novel image authentication scheme based on hyper-chaotic cell neural network[J]. Chaos， Solitons and Fractals， 2009， 42(1) : 548-553．

[14] Chamlawi R， Khan A. Digital image authentication and recovery: Employing integer transform based information embedding and extraction[J]. Information Sciences， 2010， 180(24): 4909-4928．

[15] 熊祥光， 蒋天发， 蒋 巍. 基于整数小波变换和的视频水印算法[J].计算机工程与应用， 2014， 50(1):78-82,194.

Research of image authentication algorithm based on compressive sensing

DENG Guibing1， ZHOU Shuang2， LI Shanshan3， JIANG Tianfa3

(1.Office of Informatization， Chang Professional College， Wuhan 430073;2.Department of Statistics and Mathematics， Zhongnan University of Economics and Law School， Wuhan 430073;3.School of Computer Science， South-Central University for Nationalities， Wuhan 430073)

Based on the theory of compressed sensing， a new algorithm is proposed. The image is divided into many small pieces， observing these small images we can get compressed sensing observations， then introduce the message authentication code algorithm. Uses the observed to get image summary as watermark embedding wavelet region by quantization index modulation，and then extraction the watermark， recovery the picture.Compressed sensing theory will be used random projection image， and then comparing the watermark and image summaries， so that to achieve the image tamper detection and image authentication. According to the experimental result，the algorithm has the local tamper detection function， good concealment algorithm， and after image authentication， it can able to perform nondestructive recovery．

compressive sensing; image authentication; tamper detection

2014-04-19.

国家自然科学基金项目(4057128);湖北省教育厅科研项目(B2014121).

1000-1190(2014)04-0487-05

TP309.7

A

*通讯联系人. E-mail: jiangtianfa@163.com.