篡改定位精度可动态调整的无损图像认证算法*

罗剑高 韩国强 沃焱 梁鹏

(华南理工大学计算机科学与工程学院，广东广州510006)

基于数字水印的图像认证技术［1］是目前图像认证技术研究的一个重要方向，根据因认证信息嵌入而引入的失真是否能被修复，可将其分为有损图像认证技术［2-4］和无损图像认证技术［5-9］.无损图像认证技术以无损水印［10-13］的方式把认证信息嵌入到宿主图像，适用于对失真较为敏感的图像认证应用，如医学图像、法庭证据、电子票据等的图像认证.

现有的无损图像认证算法中认证信息常用密码技术［14］生成，以无损水印的方式嵌入.文献［5-7］中的算法利用宿主图像的散列值生成认证信息，因需嵌入的认证信息量小，水印图像具有较高的保真度，但它们都不能定位篡改.虽然文献［5］中提到可采用分块的方式实现定位篡改，并指出分块的大小取决于采用的无损水印方法和认证要求，但没有具体展开讨论.Celik等［8］基于图像块，采用层次结构的认证水印和广义最低有效位(G-LSB)嵌入算法实现了可定位篡改的图像认证.该认证方案用数字签名算法(DSA)生成认证信息，采用先篡改检测后恢复图像的次序，在某种程度上降低了计算量，通过层次结构的检测过程抗击矢量攻击，但没有给出确定合适图像块大小的方法，水印嵌入算法计算较复杂，性能不高，且不能抗剪裁攻击，因为剪裁攻击可使层次结构遭到破坏，导致算法失效.Weng等［9］通过在宿主图像中引入定位模式，提出了一种抗剪裁攻击的基于图像块的无损认证算法，该算法利用宿主图像散列值生成认证信息，采用图像编号和块编号作为认证信息生成函数的输入来抗矢量攻击，但因定位模式的引入增加了水印图像的失真，图像编号需要额外传输，且在该算法中也没有给出如何选择图像块大小的方法.

由于无损水印算法的有效水印容量依赖于图像特征，对于不同特征的图像或同一图像不同特征的区域，无损水印算法的有效水印量会有较大的差别，这使现有的基于统一规格图像块的无损图像认证算法很难确定图像块的合适大小.为此，文中提出了一种可动态调整图像认证块大小的方案，同时通过多次嵌入的方式实现图像编号的鲁棒传送，解决图像编号分发传送问题，实现了一种安全有效的、具有较高篡改定位能力的无损图像认证算法.

1 问题描述

与有损图像水印算法相比，无损图像水印算法在嵌入水印时不允许丢失宿主图像的任何信息，其水印的嵌入是通过减少宿主图像的编码冗余或像素间冗余来实现的.无损图像水印算法的有效水印嵌入量与宿主图像的特征密切相关，在图像平滑区，因信息冗余量较大，水印嵌入能力强，反之在图像纹理区，信息冗余量较小，水印嵌入能力较弱.文献［11-13］中的实验结果验证了无损水印的这个特点，如在标准测试图Baboon和Lena中嵌入水印，当水印图像的峰值信噪比(PSNR)接近30 dB时，嵌入Lena的有效水印容量大约为嵌入Baboon的两倍.

基于分块和无损水印的图像认证算法采用统一大小认证块时，为保证认证信息能够分别独立、完整地被嵌入，必然要求认证块的大小由水印嵌入能力最弱的图像块来决定，这就不可避免地牺牲了其它水印嵌入能力强的区域的篡改定位能力，从而降低了全图的篡改定位能力，并且对于不同特征的图像，这种合适的认证块大小也是动态变化的.

现有的基于分块的无损图像认证算法［8-9］都没有分析讨论图像认证块大小如何确定的问题，Celik等［8］在实验中用了64×64的图像块，Weng等［9］在实验中用了32×32的图像块.虽然这些图像块大小在作者所选用的测试图像的实验中都有效，但对于一些类似Baboon的高纹理图，则可能出现一些在64×64或32×32的图像块下无法完整嵌入认证信息的情况，从而导致认证算法失效.而对于一些类似Lena的平滑图，可以把图像块取得比64×64或32×32更小些，以提高篡改的定位能力.

事实上，人们总是希望篡改定位能力尽可能强，图像块尺寸尽可能小，但现实生活中的图像千差万别，而图像块之间的差别更是如此，要确定一个相对固定的、规格统一的图像块尺寸是不现实的.因此，在保留现有的基于分块的无损图像认证算法优点的前提下，如何划分图像认证块是无损图像认证算法亟待解决的问题.

2 无损图像认证算法

文中提出的篡改定位精度可动态调整的无损图像认证算法(LIAA)，解决了现有的基于分块的无损图像认证算法中的认证块划分问题.其认证块划分的基本思想是:选择或设计某种适合小尺寸图像块的无损水印算法;把宿主图像I划分为m个能够被识别的规则基本块(BBi;i=1，2，…，m)，BBi的大小由所采用的无损水印算法和认证块中需嵌入的认证信息量等综合确定;m个BBi根据某种相邻合并规则动态生成n个图像认证块(ABj;j=1，2，…，n).在划分基本块和认证块过程中必须满足以下基本要求:

(4)为提高篡改定位能力，一般要求图像认证块具有尽可能小的平均面积.实际设计认证块划分算法时应权衡篡改定位能力和算法的复杂度.

(5)图像中的BBi、ABj能以某种方式在认证端被准确地识别.

图1给出了LIAA算法处理的过程，分为两个阶段:

1)认证水印嵌入阶段

(1)计算全图摘要D，把D作为图像编号;

(2)把宿主图像I划分为若干个基本块BBi，并按确定的相邻合并规则动态生成认证块ABj;

(3)将D、认证块编号和认证块像素矩阵作为散列函数的输入计算散列值，然后对散列值进行数字签名，生成认证信息，进而与D等比特串接生成各认证块的水印载荷;

图1 LIAA算法的处理过程Fig.1 Process of LIAA algorithm

(4)各认证块以无损水印方式嵌入水印载荷，形成含认证水印的输出图.

2)图像认证、恢复及篡改定位阶段

(1)识别出有效基本块组合作为待认证块;

(2)以待认证块为单位提取水印，恢复图像;

(3)在待认证块提取的水印中筛选出D，如果D提取失败，说明认证不通过，输出图像遭受严重篡改的提示，结束程序;

(4)对待认证块进行逐块认证，标识通过认证的图像块，输出含篡改块标识和通过认证的图像块的恢复图像，结束程序.

2.1 认证块动态生成及标识

文中采用递归算法来实现认证块的动态生成，该认证块的生成算法虽然简单，但生成的认证块大小仅是次优解，此时的认证块通常还有进一步缩小的空间.文中认证块的动态生成过程可借助图像二叉树结构来描述，如图2所示，动态生成的认证块与二叉树的节点对应.

图2 认证块的二叉树表示Fig.2 Binary tree representation of authentication blocks

图2中，I为由u×v个大小为x×y的基本块组成的父区域，根据u、v的大小，把I分成I1和I2两个子区域:

依此类推，直至子区域为单个基本块为止.然后以基本块作为当前候选认证块尝试嵌入含认证信息的水印载荷(水印载荷的生成和结构见2.3节)，如果嵌入失败，则与兄弟子区域合并组成新的候选认证块，进入新一轮的尝试;否则嵌入该认证块的水印载荷，并同时对该认证块做标识处理，然后返回继续处理剩下的基本块，直至处理完所有的图像基本块.

为了在认证时能正确地提取认证块，文中采用如下的认证块标识方法:如图3所示，以倒S顺序链接认证块的所有BBi，每个BBi用3比特来表示这种链接结构关系，其中，第一比特表示是否是首BBi，后两比特表示后续BBi的位置(01表示右邻块，10表示下邻块，11表示左邻块，00表示末尾块).具体实现时，把3比特的结构表示符保存在相应BBi头3个像素的最低有效位(LSB)上，原LSB上的值作为载荷的一部分予以保存，用于认证端的图像恢复.根据这些表示比特，在认证端就能正确识别所有的有效认证块(详见2.4节).

图3 认证块的链表结构示意图Fig.3 Schematic diagram of a chain structure of authentication block

2.2 无损水印嵌入

文中采用文献［13］中的算法来嵌入水印载荷.该算法采用一个二叉树结构来表示用于嵌入水印的多个峰值点信息，二叉树结构只需用一个表示二叉树层数的数据来表示，因而有效地减少了辅助信息数据量，适用于小尺度的图像块.

水印载荷的嵌入以认证块为单位，嵌入的载荷量为相对确定值Cp(参见2.3节)，水印嵌入参数δ(二叉树层数)的范围设为［0，15］，如果认证块不能有效嵌入认证信息(即在水印图像峰值信噪比PSNR大于保真门限τ的条件下无法完整嵌入认证信息)，则返回重新尝试生成新的认证块，否则由式(2)确定δ，并把δ保存在认证块固定像素的LSB上，这些LSB上的比特串Lsb作为水印载荷的一部分用于水印提取后的图像恢复.

式中:Cv为参数δ下认证块的有效水印容量;Cp为待嵌入的含认证信息的水印载荷量;PSNR(δ)为参数δ下的峰值信噪比;EF为认证信息嵌入成功与否的标志，EF=0表示失败，EF=1表示成功.

LIAA的图像基本块选定为16×16，水印嵌入具体过程可参阅文献［13］，需要指出的是，文中认证块水印嵌入算法中用于保存认证块结构表示比特和水印嵌入参数L的像素不参与水印的嵌入.

2.3 认证信息及认证块水印载荷的生成

LIAA属于基于独立分块的认证算法，因而也需要解决易受矢量攻击的安全问题.现有的基于分块相关［3］和基于等级结构［4］的抗矢量攻击方法要求认证块结构稳定，不适用于LIAA.LIAA采用基于块编号和图像编号的方法［2，9］，但对其存在的图像编号D存储、管理与传送等问题进行了如下改进:

式中，HMD5为散列函数，D为128 b的散列值.由式(5)生成的图像编号D可实现图像标识的唯一性.

为了实现盲认证，LIAA把D作为水印载荷的一部分嵌入图像，并采用在各认证块中重复嵌入D的方式来保证传送的可靠性.在认证端对从各认证块中分别提取的候选D采用最大判决的方式就可以鲁棒地获得正确的D.

LIAA以认证块为单位生成水印载荷Wp，Wp是由D、认证签名S和认证块固定像素LSB的比特合并串Lsb组成的长为Cp的比特串:

式中“+”表示比特流串接合并.

LIAA中认证块的认证签名S采用密码学中的数字签名算法DSA［14］生成:

式中:S表示长为320 b的签名串;SDSA为DSA签名函数;HSHA为SHA散列函数;Ψ为当前认证块像素矩阵;(x，y)为认证块的左上角坐标(作为区别认证块的块编号，用于克服同一图像中不同认证块之间的替换攻击);k为数字签名的私钥.

LIAA用认证块中第一个基本块的第4至第7个像素的LSB上的比特来表示水印嵌入参数δ，这些像素和各BBi头3个像素(用于表示认证块结构的像素，参见2.1)的LSB上的原有比特串接形成式(6)中的Lsb.

2.4 认证端对有效认证块的识别

认证块能在认证端被鲁棒地识别是LIAA的关键，也是进一步对认证块进行认证操作的前提.LIAA识别有效认证块的过程如下:

1)依次扫描图中各基本块头3个像素LSB上的比特(记为Lsb1、Lsb2、Lsb3)，若Lsb1为1，则转步骤2);否则，若当前基本块不是图像基本块的末尾块(BBend)则跳过该块，继续查看下一基本块;若当前基本块为BBend则结束程序.

2)若Lsb2Lsb3为00，表示当前基本块为候选认证块的末尾分块，则转步骤4);否则，若当前基本块不是BBend，则根据Lsb2Lsb3转到候选认证块中相应的下一分块(01表示下一分块为当前基本块的右邻块，10表示下一分块为当前基本块的下邻块，11表示下一分块为当前基本块的左邻块);若当前基本块为BBend则结束程序.

3)如果当前基本块的Lsb1为1，表示该候选认证块识别失败，则返回到该候选认证块首块的下一基本块，转到步骤1)，否则转到步骤2).

4)判断候选认证块是否为一含2t(t=0，1，…)个基本块的合法矩形图像块，如果不是，表明候选认证块识别失败;否则，对该候选认证块执行无损水印提取和像素恢复.如果水印提取和图像恢复过程出错，表明候选认证块认证失败;否则，把该认证块的结构及提取的图像编号、认证信息、图像恢复结果保存在候选认证块数组中，用于下一步以认证块为单位的认证信息签名的验证.分析处理候选认证块后，若当前基本块不是BBend则返回到该候选认证块首块的下一基本块，转步骤1)，否则结束程序.

2.5 无损水印提取和图像恢复

无损水印提取和图像恢复以认证块为单位进行，在认证块固定像素的LSB上提取水印初始参数δ，执行水印提取和图像恢复(具体过程可参阅文献［13］).需要注意的是，不参与水印嵌入的固定像素也不参与水印提取，这些像素的原始LSB用从水印中截取的Lsb(参见2.3)恢复.如果水印提取和图像恢复过程出现错误，则输出出错标记，否则输出水印提取结果和图像恢复结果.

2.6 认证块签名验证

(1)依次扫描候选认证块数组中各记录的图像编号字段，选择最大重现率的项作为最终图像编号D，如果该项在数组的重现率低于50%，则认为发生了严重篡改，给出提示，结束认证.

(2)重新依次扫描候选认证块数组，若当前候选认证块的图像编号字段的值不等于D，则该认证块认证失败;否则，用公钥对当前候选认证块执行式(8)的DSA签名验证，并标记通过验证的认证块:

式中，VDSA为DSA签名的验证算法，S'为从当前认证块中提取的认证信息为当前认证块的像素恢复矩阵，k'为DSA签名算法的公钥.

(3)输出含篡改块标记和通过认证的区域的恢复图像.

3 算法性能分析

LIAA结合了数字签名的安全性和数字水印的篡改定位能力、盲认证能力，具有安全性高、篡改定位精度可动态调整、易于扩展等优点.

3.1 安全性

由于解决了矢量攻击问题，LIAA的安全性主要取决于所用的密码系统，到目前为止320 b的DSA被证明还是安全的.LIAA在图像没有被篡改时，由恢复图像计算所得的认证信息将与提取的认证信息完全相同，故虚警概率为0.当图像出现被篡改时，即使是微小的变化，在认证端由密码算法计算出的认证信息与提取的认证水印也截然不同，如假设认证信息服从随机均匀分布，此时认证块漏警的概率为2-320，这里还没有考虑无损水印能否有效提取等因素，故漏警概率可近似为0.

3.2 篡改定位能力

LIAA的每一认证块对应着图2中图像二叉树上的某个节点，由二叉树生成过程可知每一节点对应的图像区域都是一个趋近正方形的区域.在保证认证信息完整嵌入的前提下，LIAA使认证块的大小动态地趋于最小.由认证块的划分规则可知，LIAA认证块的平均面积小于采用固定大小认证块方式时的认证块面积，相应地，篡改定位能力得到了提高.

3.3 扩展性

LIAA不仅适用于各种类型的图像，而且易于根据具体的应用要求做相应的扩展，如通过设定保真度门限τ可实现对水印图像失真的控制，用不同的保真度门限可分别调整图像的感兴趣区(ROI)和非ROI的篡改定位能力，从而在全图保真度稳定的情况下提高ROI的篡改定位能力.

4 实验及结果分析

为验证LIAA的有效性，在Matlab平台上实现了LIAA，并用USC-SIPI图像数据库［15］中各种不同性质的图像进行实验.

为了方便分析，文中将无损图像认证算法的篡改定位精度定义为

式中，M×N为宿主图像I的分辨率，λ为认证块总数.

图4给出了图像Lena、Baboon和Plane的篡改定位精度-认证块保真门限曲线，篡改定位精度Γ随着认证块保真度门限τ的增加而增加，篡改定位能力下降.通过调整τ，可以在从基本块大小到全图大小的范围内动态地获得合适大小的认证块.由于单个LIAA认证块的水印载荷只有几百比特，现实中有意义的图像I采用LIAA中的无损水印算法时，有效认证块在全图大小范围内总能找到合适大小的图像块嵌入认证信息，不会出现因认证水印无法有效嵌入而导致LIAA失效的问题.

图4 几种图像认证块的篡改定位精度-保真度门限曲线Fig.4 Curves of tamper localization accuracy versus fidelity threshold of authentication block for several images

图5给出了在不同门限τ下使用LIAA处理图像Plane时的认证块结构，其中PSNR表示嵌入认证信息后全图I的峰值信噪比，Γ为式(9)定义的定位精度.图5显示，LIAA能根据图像的局部特征动态地调整定位精度，一般平滑区的定位能力要比纹理区的定位能力高，实际水印图像的PSNR要高于无损认证设定的τ参数.

图6给出了LIAA的篡改检测、定位实例局部图.实验中对含认证水印的图像Plane做了一处视觉难以识别的内容修改，如图6(a)、6(b)所示，使用LIAA对图6(b)进行认证，认证结果不仅能检测出图像被篡改，而且能准确地定位出篡改内容所在的认证块区域，如图6(c)所示(图中分格线实际输出时可去除).

图5 LIAA的篡改定位精度实验结果Fig.5 Experimental results of tamper localization accuracy of LIAA

图6 LIAA的篡改检测、定位实例Fig.6 Example of tamper detection and localization by LIAA

5 结语

文中提出一种新的基于分块的无损图像认证算法LIAA.LIAA采用认证块动态生成的策略解决了现有基于独立分块的无损图像认证算法中的认证块划分问题，提高了篡改定位能力;通过多次嵌入的方式实现图像编号的鲁棒传送，解决了基于图像编号抗矢量攻击方法的图像编号管理、传送问题，可有效地抗击矢量攻击.理论分析和实验结果表明，LIAA综合了数字签名和数字水印在图像认证应用中的优点，安全性高，盲认证，篡改定位能力强于现有的无损图像认证算法，且适应性强，适用于对安全性、保真度、篡改定位精度等要求高的图像的精确认证.

［1］Cox IJ，MillerM L，Bloom JA，etal.Digitalwatermarking and steganography［M］.2nd ed.Burlington:Morgan Kauffman，2008:375-422.

［2］Wong PW，Memon N.Secretand public key image watermarking schemes for image authentication and ownership verification［J］.IEEE Transactions on Image Processing，2001，10(10):1593-1601.

［3］张鸿宾，杨成.基于公钥和脆弱水印的图像认证算法［J］.计算机科学，2004，31(11):218-221.Zhang Hong-bin，Yang Cheng.An image authentication scheme based on public key and fragile watermar king［J］.Computer Science，2004，31(11):218-221.

［4］Celik M U，Sharma G，Saber E，et al.Hierarchical watermarking for secure image authentication with localization［J］.IEEE Transactions on Image Processing，2002，11(6):585-595.

［5］Fridrich J，Goljan M，Du R.Invertible authentication［C］∥Proceedings of Security and Watermarking of Multimedia Contents III.San Jose:SPIE，2001:197-208.

［6］Tian J.Wavelet-based reversible watermarking for authentication［C］∥Proceedings of Security and Watermarking of Multimedia Contents IV.San Jose:SPIE，2002:679-690.

［7］Lee Sang-kwang，Suh Young-ho，Ho Yo-sung.Reversible image authentication based on watermarking［C］∥Proceedings of IEEE International Conference on Multimedia and Expo.Toronto:IEEE，2006:1321-1324.

［8］Celik M U，Sharma G，Tekalp A M.Losslesswatermarking for image authentication:a new framework and an implementation［J］.IEEE Transactions on Image Processing，2006，15(4):1042-1049.

［9］Weng SW，Zhao Y，Pan JS.Reversible watermarking resistant to cropping attack［J］.IET Information Security，2007，1(2):91-95.

［10］Ni Z，Shi Y Q，Ansari N.Reversible data hiding［J］.IEEE Transactions on Circuits and Systems for Video Technology，2006，16(3):354-362.

［11］Tian J.Reversible data embedding using a difference expansion［J］.IEEE Transactions on Circuits and Systems for Video Technology，2003，13(8):890-896.

［12］Thodi D M，Rodriguez J J.Expansion embedding techniques for reversible watermarking［J］.IEEE Transactions on Image Processing，2007，16(3):721-730.

［13］TaiW L，Yeh C M，Chang C C.Reversible data hiding based on histogram modification of pixel differences［J］.IEEE Transactions on Circuits and Systems for Video Technology，2009，19(6):906-910.

［14］Atul Kahate.密码学与网络安全［M］.邱仲潘，译.北京:清华大学出版社，2005:105-130.

［15］Signal and Image Processing Institute，University Southern California，Los Angeles.Image database［DB/OL］.［2011-05-16］.http:∥sipi.usc.edu/database/.