基于压缩感知的彩色图像可逆水印认证算法∗

左航洲

（中国电子科技集团公司第二十研究所西安710068）

基于压缩感知的彩色图像可逆水印认证算法∗

左航洲

（中国电子科技集团公司第二十研究所西安710068）

针对现有可逆水印的图像认证技术存在篡改检测、定位能力不足，篡改重构没有被重视等问题，提出了一种基于压缩感知的彩色图像可逆水印认证算法。该算法在发送端将原始图像分块压缩感知生成图像哈希作为水印，并利用差值直方图调整的可逆水印算法进行嵌入；在接收端提取水印信息对水印图像进行认证，并针对认证失败的篡改块，利用压缩感知进行重构来恢复原始图像。实验结果表明，该算法将可逆水印和压缩感知相结合提高了图像认证检测率，并增强了水印算法抗稀疏噪声、抗剪裁的鲁棒性，同时可重建原始图像。

图像认证；可逆水印；压缩感知；差值直方图；图像重构

ClassNumber TP309

1 引言

数字多媒体已广泛渗透进人类生活，证明其完整性和真实性是一大挑战。创建一个数字信号的副本实际上是重构相同的信号，这使得在多媒体数字域提供简单的复制方法的同时使其保持完整性和真实性带来了困难问题。目前，现有三种方法可解决图像篡改检测问题［1~2］：盲检测、图像哈希和数字水印。

其中，盲检测是寻找存在一种特定的攻击类型，其优点是不需要任何辅助信息来检测篡改［3~4］。当检测篡改原始信号不可再用时，该方案是有利的，但该方案不得不模拟每种类型的篡改，以至于取得低于标准的算法性能。图像哈希是一个基于数字信号特征的数字内容紧凑表示。图像哈希必须满足如下性质［5~6］：感知保真度、单通道的、对输入非常敏感、用于图像质量评价，以及使用数据库检索。此外，图像哈希可结合压缩感知（com⁃pressed sensing，CS）［7~8］解决图像认证问题。压缩感知可从稀疏采样中的重构样本信号，且速度远远低于奈奎斯特采样速率，其精髓是一种利用稀疏的或可压缩的信号进行信号重构的技术，信号可以通过求解一个凸优化问题重构；数字水印可直接嵌入到数字内容用于图像认证和完整性检查，其中易碎水印可表示图像完整性的损失［9~10］。文献［9］使用小波域嵌入水印，这些操作可被定位在频率和空间域。文献［10］中水印信号以分级的方式嵌入在最低有效位，有效地抗击矢量量化攻击，另外将半脆弱水印结合压缩感知原理可有效地解决图像认证［11~13］。文献［11］对图像采样并创建投影，随机投影采用统一量化器，低密度奇偶校验（LDPC）码是用来形成哈希作为鲁棒水印嵌入，恢复水印导致恢复的投影可用于对所接收图像的失真估计，如果篡改是足够稀疏，则可定位篡改。文献［12］提出了一种图像篡改检测、定位和原始图像恢复（如果篡改是稀疏的）的算法。文献［13］提出在变换域（DCT）中基于压缩感知的水印检测方法，该方法依赖于自然图像在变换域系数是稀疏的事实，并且可以进一步通过应用阈值对系数深层次稀疏化，加性水印方案嵌入中频系数，在稀疏和码字长度比水印长度一定的条件下，水印可采用压缩感知恢复，水印的抗泊松噪声攻击鲁棒性已被作者证明。以上文献研究的大多数水印认证算法存在以下一个或多个缺点：1）不是可逆水印，从而不能应用于敏感图像；2）认证结果只是得出篡改检测或篡改定位；3）没有对篡改信号评估或重建；4）研究的大多数是灰度图像，实用性不强。

本文提出一种基于压缩感知的彩色图像可逆水印认证算法（compressivesensingbased color-image reversible authentication watermarking，CS-CRAW）。该算法在发送端对图像进行离散小波变换，计算（LL）子带的图像哈希，通过压缩感知结合密钥生成可逆水印，并利用差值直方图调整的可逆水印算法把图像哈希作为水印嵌入载体彩色图像；在接收端提取水印，通过密钥重构哈希水印，用提取的哈希和重构的哈希比较认证。该算法结合压缩感知理论及图像可逆水印技术，充分利用压缩感知高效压缩图像及可精确重构图像等性质，实现篡改检测、定位，从而增强秘密信息传送的安全性，提高了水印算法抗稀疏噪声、抗剪裁的鲁棒性，降低水印技术的复杂度，进而实现基于压缩感知的彩色图像可逆水印认证技术。

2 压缩感知的信号重构

文献［7~8］中展示了压缩感知的稀疏信号重构，任何信号X(XÎRN)可被表示成：

其中Ψ为N´N正交基矩阵，S为是K-稀疏的，S是离散信号X在正交基矩阵Ψ上的稀疏表示系数。

M´1维的观测值Y由下式产生：

其中Φ为M´N的观测矩阵(M

其中压缩感知矩阵Θ=ΦΨ满足受限等距特性时可以由M观测值中准确重建K-稀疏信号S：

其中l0范数表示S′中非零系数的个数，然而这是一个NP问题，在实际应用中难以解决。

准确地重建K-稀疏的信号可以用求解一个更加简单的l1优化问题会产生同等的解（要求Φ和Ψ不相关），稍微的差别使得问题变成了一个凸优化问题，因此可以方便地化简为线性规划问题。典型算法代表：BP算法。尽管BP算法可行，但在实际应用中存在两个问题：即使是常见的图像尺寸，算法的计算复杂度也难以忍受；在采样点个数满足M³cK，c»log2(N/K+1)时，重构计算复杂度的量级在O（N3）。

3 CS-CRAW算法实现过程

CS-CRAW算法认证实现过程如图1所示，原始图像生产者在发送给接收者之前，先给原始图像嵌入水印。当接收者收到含水印图像后，可以从本认证系统得到两个信息，一个是原始图像与篡改图像的失真评估，另一个是认证结果。

3.1 图像哈希构造

通过对图像分块，对分块进行离散小波变换，得到近似图像子段（LL）的小波系数x，接下来对x随机投影得到观测值y：

其中Φ是从种子s中产生的正交高斯矩阵，随机密钥S只有嵌入者和解码器拥有。这将使得解码器需要相同的种子s产生Φ，在解码端CS中是不可或缺的。观测值y使用一个统一的量化、编码生成图像哈希H∈｛0，1｝。

3.2 水印嵌入

CS-CRAW算法采用分量间差值直方图相差的绝对值调整嵌入水印，首先计算彩色图像色彩分量的差值直方图，然后对差值直方图做差的绝对值，最后对差的绝对值调整以嵌入水印。

图2以Lena彩色图像（512×512）为例展示相应直方图。其中R、G、B分量分别表示彩色图像红色、绿色、蓝色三个色彩通道，分量R的行向量像素差值用d1表示，分量G的行向量像素差值用d2表示，d1与d2差的绝对值用d表示。

从图2可以看出，分量R的差值直方图（d1）比分量R的直方图聚集，而且分布在0附近；同时可以看出d1与d2差的绝对值d直方图更加聚集，基本在20以内。因此，CS-CRAW算法可以实现在取得较大嵌入容量的同时保证高的图像质量。

3.3 水印检测认证

完整性验证首先对接收的图像使用DWT变换，接收端从水印图像中提取水印信息的同时恢复载体图像，对水印信息解密得到y的同时对载体图像进行使用相同的种子s进行观测投影得到，如果提取的观测值与重新计算的观测值匹配（= y），则图像完整性被认为是完整的。

3.4 图像块篡改重构

通过嵌入的水印信息对载体图像认证后，如果图像块受到篡改攻击，则利用压缩感知重建篡改块。如图3给出图像块篡改重构的流程：

假设图像受到稀疏脉冲篡改后的模型为

其中eÎRN为K-稀疏噪声（K<

由于原始信号y无法获得，故用恢复的信号y近似代替得到下式：

其中Q(×)表示量化操作，z为量化操作带来的误差，本文算法使用§1的l1-范数重构图像，为了重建篡改需要解决下式：

最后为了评估K稀疏篡改e解决式（11），压缩感知理论要求投影观测值M必须满足下式条件：

其中常量c通常依赖式（11）的实际算法。

4 实验结果及分析

所有实验均在Intel（R）Core（TM）2Duo CPU，1G内存，Win7操作系统，以Matlab 2012b为实验平台得到。从哥伦比亚大学的UCID图像库［14］中选择两幅经典的具有不同纹理特征的24 bit彩色图像（512×512）作为测试图像，如图4所示，以真阳检测率和峰值信噪比为评价标准衡量图像的认证精确度。

4.1 算法检测率性能

CS-CRAW算法在不同稀疏篡改程度条件下对测试图像（512×512）仿真篡改定位系统，首先把图像分成（32×32）像素不重叠块，计算块的小波变换低频（LL）系数按行优先排列，记为x且拥有N= 256个元素。该算法利用方差σs2=1000在x的K个随机位置的高斯噪声来模拟篡改，假定随机测量值y在哈希值H的辅助条件下可以正确地解码，即解码的y与随机投影得到y的均方误差相等。

CS-CRAW算法通过重建篡改e并比较估计篡改与实际篡改的位置来评价篡改定位性能。通过改变阈值T，可以建立一个给定观测值M数量和总率的平均每像素比率为RT=MR（D）/N的真阳性率ROC曲线。定义零误检率——检测率（PD）为真阳性率ROC曲线的最高值，假阳性率ROC曲线的零值，这使得该系统可检测到任何篡改信息情况。不同哈希比率RT的真阳性检测率如图5所示。

图5 （a）表示对于图像哈希的不同比率RT所对应的检测率PD，即随着观测值M数量增加时，K/ N=0.01。图像哈希所占图像的不同比率RT导致不同的检测率，对于给定的检测率，观测值数量越多，每个观测值平均比率越低，增加比特数量每观测值可提高检测率PD，最终使检测率达到1。当观测值数量小于约束条件式（12），用l1-范数重建将导致较大的假阳率，即只能是较小部分的篡改定位和真实情况相符，这是因为重建的篡改e有较多的非零系数与实际篡改不符。当与式（12）等式接近时，检测率PD获得峰值。图5（a）所示，检测率PD峰值获得在M为80附近，由此可验证常数c大约等于1.72的1%的稀疏篡改。在低比特率曲线（如图5（a），RT=0.002bpp）中，观测值数量较大时检测率反而降低了，这是因为在分配给每观测值的比特数量太少时，导致重建的噪声e严重失真，因此量化噪声对重建随机观测值的影响便不可忽略。图5（b）所示类似的实验为5%的稀疏篡改，更好地证明以上现象。检测率PD在M³250（c=1.63）时逼近峰值，由式（12）可知稀疏性增加时，需更多的观测值来解决式（11）。因此用和图5（a）同样的比率时，分配给每观测值的比特数量要少于1%稀疏篡改的情况，检测率PD达到最高值1时需更多的比特数量构成图像哈希。

4.2 篡改检测定位与图像重建

CS-CRAW算法对原始图像进行小波变换，把图像细节特征系数进行压缩感知并嵌入载体图像，在图像受到稀疏噪声篡改时，利用提取的水印可检测到篡改的同时利用图像细节特征系数重建原始图像，取得了很好效果。图像的噪声篡改检测与重建结果如图6所示。

图6 （a）-（b）分别展示了Lena、Airplane图像在受到稀疏噪声篡改后，通过提取的水印信息进行认证，准确地检测定位到篡改区域，利用压缩感知对图像特征系数重建，成功地重建了图像。如图6（a）Lena图像实验结果比对图，通过压缩感知重建的图像与原始图像峰值信噪比为39.66dB；图6（b）Air⁃plane原始图像与重建图像的峰值信噪比为39.11dB。

CS-CRAW算法将原始图像分成（32×32）像素不重叠块，分别对块进行小波变换并将块的图像小波（LL）特征系数嵌入到别的块。在图像块受到篡改时，可通过嵌入到其他块的篡改块系数利用压缩感知重建篡改块。图7（a）-（b）分别展示了Lena、Airplane图像在受到单处块裁剪后，通过提取的水印信息进行认证，准确地检测定位到裁剪区域，并利用被裁剪区域的特征系数重建裁剪区域，最终成功地重建图像。如图7（a）Lena图像实验结果比对图，通过特征系数重建的图像与原始图像峰值信噪比为42.57dB；图7（b）Airplane图像通过特征系数重建的图像与原始图像峰值信噪比为41.34dB。

图8 （a）、（b）分别展示了Lena、Airplane图像在受到多处块裁剪后，通过提取的水印信息进行认证，准确地检测定位到裁剪区域，并利用被裁剪区域的特征系数重建裁剪区域，最终成功地重建图像。如图8（a）Lena图像实验结果比对图，通过特征系数重建的图像与原始图像峰值信噪比为40.63dB；图8（b）Airplane图像通过特征系数重建的图像与原始图像峰值信噪比为39.74dB。

5 结语

本文提出一种基于压缩感知的彩色图像可逆水印认证算法。该算法首先将载体彩色图像自身灰度图像的低频系数进行压缩感知随机投影并生成水印，水印信息完整的表征了图像的细节特征；然后采用分量间差值直方图相差的绝对值进行调整嵌入水印。为了保证较高的图像质量，CS-CRAW算法只考虑对2个分量（R、B）进行嵌入，而忽略对人类视觉系统（HVS）最敏感的绿色（G）色彩分量嵌入。实验结果表明，该算法在完整性认证时不需要原始图像，即盲检测在接收端可以通过提取水印对图像进行认证，在认证图像没有遭受篡改的同时无损地恢复原始图像；若图像遭受稀疏噪声脉冲时，则可通过水印定位篡改并利用压缩感知重建原始图像，CS-CRAW算法对载体图像的篡改定位和稀疏噪声篡改重建取得较好效果，提高了水印算法抗稀疏噪声、抗剪裁的鲁棒性。

［1］WANG X，PANG K，ZHOU X，et al.A visualmodel based perceptual image hash for content authentication［J］. IEEE Transactions on Information Forensics and Security，2015，10（7）：1336-1349.

［2］LO CC，HU Y C.A novel reversible image authentication scheme for digital images［J］.Signal Processing，2014，98：174-185.

［3］FARID H.Exposing digital forgeries in scientific images［C］//Proceedings of the 8th workshop on Multimedia and security.Geneva，Switzerland，ACM，2006：29-36.

［4］JOHNSON M K，FARID H.Detecting photographic com⁃posites of people［C］//Proceedings of the 6th Internation⁃al Workshop on Digital Watermarking，IWDW 2007. Guangzhou，China，Springer Berlin Heidelberg，2008，5041 LNCS：19-33.

［5］SWAMINATHAN A，MAO Y，WU M.Robust and secure image hashing［J］.IEEE Transactions on Information Fo⁃rensicsand Security，2006，1（2）：215-230.

［6］MONGA V，EVANS B L.Perceptual image hashing via feature points：performance evaluation and tradeoffs［J］. IEEE Transactions on Image Processing，2006，15（11）：3452-3465.

［7］DONOHO D L.Compressed sensing［J］.IEEE Transac⁃tionson Information Theory，2006，52（4）：1289-1306.

［8］CANDÈSE J，ROMBERG J，TAO T.Robust uncertainty principles：Exact signal reconstruction from highly incom⁃plete frequency information［J］.IEEE Transactions on In⁃formation Theory，2006，52（2）：489-509.

［9］KUNDUR D，HATZINAKOSD.Digitalwatermarking for telltale tamper proofing and authentication［J］.Proceed⁃ingsof the IEEE，1999，87（7）：1167-1180.

［10］CELIK M U，SHARMA G，SABER E，et al.Hierarchical watermarking for secure image authentication with local⁃ization［J］.IEEE Transactions on Image Processing，2002，11（6）：585-595.

［11］VALENZISE G，TAGLIASACCHIM，TUBARO S，et al. A compressive-sensing based watermarking scheme for sparse image tampering identification［C］//Proceedings of the 2009 IEEE International Conference on Image Pro⁃cessing，ICIP 2009，Cairo，Egypt，IEEE，2009：1265-1268.

［12］ZHANG X，QIAN Z，REN Y，et al.Watermarking with flexible self-recovery quality based on compressive sens⁃ing and compositive reconstruction［J］.IEEE Transac⁃tions on Information Forensics and Security，2011，6（4）：1223-1232.

［13］SHEIKH M，BARANIUK RG.Blind error-free detection of transform-domain watermarks［C］//Proceedings of the 2007 IEEE International Conference on Image Process⁃ing，ICIP 2007，San Antonio，TX，United states，IEEE，2007，5：453-456.

［14］SCHAEFER G，STICH M.UCID-an uncompressed co⁃lour image database［C］//Proceedings of SPIE，Storage and Retrieval Methods and Applications for Multi-me⁃dia，San Jose，CA，United states，The International So⁃ciety for Optical Engineering，2004，5307：472-480.

Reversib leW atermarking Authentication A lgorithm for Color Im ages Based on Com p ressed Sensing

ZUO Hangzhou
（20th Research InstituteofChina Electronics Technology Group，XiƳan 710068）

Aim ing at the shortcom ingsofexisting reversiblewatermarking for image authentication，such as poor ability of tam⁃per detection and localization，and low attention of reconstruction after tampering，a reversible watermarking algorithm based on compressive sensing for color image authentication was proposed.On the side of the sender，the original image has been divided into blocksand carried out compressed sensing to generate image hash which works as the watermark information，and was embedded by the reversiblewatermarking of difference histogram algorithm.On the side of the receiver，watermark was extracted for authentica⁃tion.For the tampered block which was failed in authentication，original imagewillbe restored by reconstruction of compressed sens⁃ing.Experimental results show that the algorithm combinesof reversiblewatermarking and compressed sensing，so that the detection rate of image authentication hasbeen improved，aswell as the robustness to resist sparse noise and cuttingand theability to recon⁃struct the original image.

image authentication，reversiblewatermarking，compressed sensing，difference histogram，image reconstruction

TP309 DO I：10.3969/j.issn.1672-9730.2017.05.021

2016年11月19日，

2016年12月31日

左航洲，男，硕士，助理工程师，研究方向：数字图像可逆水印。