篡改定位精度可動態(tài)調整的無損圖像認證算法*

羅劍高 韓國強 沃焱 梁鵬

(華南理工大學計算機科學與工程學院，廣東廣州510006)

基于數字水印的圖像認證技術［1］是目前圖像認證技術研究的一個重要方向，根據因認證信息嵌入而引入的失真是否能被修復，可將其分為有損圖像認證技術［2-4］和無損圖像認證技術［5-9］.無損圖像認證技術以無損水?。?0-13］的方式把認證信息嵌入到宿主圖像，適用于對失真較為敏感的圖像認證應用，如醫(yī)學圖像、法庭證據、電子票據等的圖像認證.

現(xiàn)有的無損圖像認證算法中認證信息常用密碼技術［14］生成，以無損水印的方式嵌入.文獻［5-7］中的算法利用宿主圖像的散列值生成認證信息，因需嵌入的認證信息量小，水印圖像具有較高的保真度，但它們都不能定位篡改.雖然文獻［5］中提到可采用分塊的方式實現(xiàn)定位篡改，并指出分塊的大小取決于采用的無損水印方法和認證要求，但沒有具體展開討論.Celik等［8］基于圖像塊，采用層次結構的認證水印和廣義最低有效位(G-LSB)嵌入算法實現(xiàn)了可定位篡改的圖像認證.該認證方案用數字簽名算法(DSA)生成認證信息，采用先篡改檢測后恢復圖像的次序，在某種程度上降低了計算量，通過層次結構的檢測過程抗擊矢量攻擊，但沒有給出確定合適圖像塊大小的方法，水印嵌入算法計算較復雜，性能不高，且不能抗剪裁攻擊，因為剪裁攻擊可使層次結構遭到破壞，導致算法失效.Weng等［9］通過在宿主圖像中引入定位模式，提出了一種抗剪裁攻擊的基于圖像塊的無損認證算法，該算法利用宿主圖像散列值生成認證信息，采用圖像編號和塊編號作為認證信息生成函數的輸入來抗矢量攻擊，但因定位模式的引入增加了水印圖像的失真，圖像編號需要額外傳輸，且在該算法中也沒有給出如何選擇圖像塊大小的方法.

由于無損水印算法的有效水印容量依賴于圖像特征，對于不同特征的圖像或同一圖像不同特征的區(qū)域，無損水印算法的有效水印量會有較大的差別，這使現(xiàn)有的基于統(tǒng)一規(guī)格圖像塊的無損圖像認證算法很難確定圖像塊的合適大小.為此，文中提出了一種可動態(tài)調整圖像認證塊大小的方案，同時通過多次嵌入的方式實現(xiàn)圖像編號的魯棒傳送，解決圖像編號分發(fā)傳送問題，實現(xiàn)了一種安全有效的、具有較高篡改定位能力的無損圖像認證算法.

1 問題描述

與有損圖像水印算法相比，無損圖像水印算法在嵌入水印時不允許丟失宿主圖像的任何信息，其水印的嵌入是通過減少宿主圖像的編碼冗余或像素間冗余來實現(xiàn)的.無損圖像水印算法的有效水印嵌入量與宿主圖像的特征密切相關，在圖像平滑區(qū)，因信息冗余量較大，水印嵌入能力強，反之在圖像紋理區(qū)，信息冗余量較小，水印嵌入能力較弱.文獻［11-13］中的實驗結果驗證了無損水印的這個特點，如在標準測試圖Baboon和Lena中嵌入水印，當水印圖像的峰值信噪比(PSNR)接近30 dB時，嵌入Lena的有效水印容量大約為嵌入Baboon的兩倍.

基于分塊和無損水印的圖像認證算法采用統(tǒng)一大小認證塊時，為保證認證信息能夠分別獨立、完整地被嵌入，必然要求認證塊的大小由水印嵌入能力最弱的圖像塊來決定，這就不可避免地犧牲了其它水印嵌入能力強的區(qū)域的篡改定位能力，從而降低了全圖的篡改定位能力，并且對于不同特征的圖像，這種合適的認證塊大小也是動態(tài)變化的.

現(xiàn)有的基于分塊的無損圖像認證算法［8-9］都沒有分析討論圖像認證塊大小如何確定的問題，Celik等［8］在實驗中用了64×64的圖像塊，Weng等［9］在實驗中用了32×32的圖像塊.雖然這些圖像塊大小在作者所選用的測試圖像的實驗中都有效，但對于一些類似Baboon的高紋理圖，則可能出現(xiàn)一些在64×64或32×32的圖像塊下無法完整嵌入認證信息的情況，從而導致認證算法失效.而對于一些類似Lena的平滑圖，可以把圖像塊取得比64×64或32×32更小些，以提高篡改的定位能力.

事實上，人們總是希望篡改定位能力盡可能強，圖像塊尺寸盡可能小，但現(xiàn)實生活中的圖像千差萬別，而圖像塊之間的差別更是如此，要確定一個相對固定的、規(guī)格統(tǒng)一的圖像塊尺寸是不現(xiàn)實的.因此，在保留現(xiàn)有的基于分塊的無損圖像認證算法優(yōu)點的前提下，如何劃分圖像認證塊是無損圖像認證算法亟待解決的問題.

2 無損圖像認證算法

文中提出的篡改定位精度可動態(tài)調整的無損圖像認證算法(LIAA)，解決了現(xiàn)有的基于分塊的無損圖像認證算法中的認證塊劃分問題.其認證塊劃分的基本思想是:選擇或設計某種適合小尺寸圖像塊的無損水印算法;把宿主圖像I劃分為m個能夠被識別的規(guī)則基本塊(BBi;i=1，2，…，m)，BBi的大小由所采用的無損水印算法和認證塊中需嵌入的認證信息量等綜合確定;m個BBi根據某種相鄰合并規(guī)則動態(tài)生成n個圖像認證塊(ABj;j=1，2，…，n).在劃分基本塊和認證塊過程中必須滿足以下基本要求:

(4)為提高篡改定位能力，一般要求圖像認證塊具有盡可能小的平均面積.實際設計認證塊劃分算法時應權衡篡改定位能力和算法的復雜度.

(5)圖像中的BBi、ABj能以某種方式在認證端被準確地識別.

圖1給出了LIAA算法處理的過程，分為兩個階段:

1)認證水印嵌入階段

(1)計算全圖摘要D，把D作為圖像編號;

(2)把宿主圖像I劃分為若干個基本塊BBi，并按確定的相鄰合并規(guī)則動態(tài)生成認證塊ABj;

(3)將D、認證塊編號和認證塊像素矩陣作為散列函數的輸入計算散列值，然后對散列值進行數字簽名，生成認證信息，進而與D等比特串接生成各認證塊的水印載荷;

圖1 LIAA算法的處理過程Fig.1 Process of LIAA algorithm

(4)各認證塊以無損水印方式嵌入水印載荷，形成含認證水印的輸出圖.

2)圖像認證、恢復及篡改定位階段

(1)識別出有效基本塊組合作為待認證塊;

(2)以待認證塊為單位提取水印，恢復圖像;

(3)在待認證塊提取的水印中篩選出D，如果D提取失敗，說明認證不通過，輸出圖像遭受嚴重篡改的提示，結束程序;

(4)對待認證塊進行逐塊認證，標識通過認證的圖像塊，輸出含篡改塊標識和通過認證的圖像塊的恢復圖像，結束程序.

2.1 認證塊動態(tài)生成及標識

文中采用遞歸算法來實現(xiàn)認證塊的動態(tài)生成，該認證塊的生成算法雖然簡單，但生成的認證塊大小僅是次優(yōu)解，此時的認證塊通常還有進一步縮小的空間.文中認證塊的動態(tài)生成過程可借助圖像二叉樹結構來描述，如圖2所示，動態(tài)生成的認證塊與二叉樹的節(jié)點對應.

圖2 認證塊的二叉樹表示Fig.2 Binary tree representation of authentication blocks

圖2中，I為由u×v個大小為x×y的基本塊組成的父區(qū)域，根據u、v的大小，把I分成I1和I2兩個子區(qū)域:

依此類推，直至子區(qū)域為單個基本塊為止.然后以基本塊作為當前候選認證塊嘗試嵌入含認證信息的水印載荷(水印載荷的生成和結構見2.3節(jié))，如果嵌入失敗，則與兄弟子區(qū)域合并組成新的候選認證塊，進入新一輪的嘗試;否則嵌入該認證塊的水印載荷，并同時對該認證塊做標識處理，然后返回繼續(xù)處理剩下的基本塊，直至處理完所有的圖像基本塊.

為了在認證時能正確地提取認證塊，文中采用如下的認證塊標識方法:如圖3所示，以倒S順序鏈接認證塊的所有BBi，每個BBi用3比特來表示這種鏈接結構關系，其中，第一比特表示是否是首BBi，后兩比特表示后續(xù)BBi的位置(01表示右鄰塊，10表示下鄰塊，11表示左鄰塊，00表示末尾塊).具體實現(xiàn)時，把3比特的結構表示符保存在相應BBi頭3個像素的最低有效位(LSB)上，原LSB上的值作為載荷的一部分予以保存，用于認證端的圖像恢復.根據這些表示比特，在認證端就能正確識別所有的有效認證塊(詳見2.4節(jié)).

圖3 認證塊的鏈表結構示意圖Fig.3 Schematic diagram of a chain structure of authentication block

2.2 無損水印嵌入

文中采用文獻［13］中的算法來嵌入水印載荷.該算法采用一個二叉樹結構來表示用于嵌入水印的多個峰值點信息，二叉樹結構只需用一個表示二叉樹層數的數據來表示，因而有效地減少了輔助信息數據量，適用于小尺度的圖像塊.

水印載荷的嵌入以認證塊為單位，嵌入的載荷量為相對確定值Cp(參見2.3節(jié))，水印嵌入參數δ(二叉樹層數)的范圍設為［0，15］，如果認證塊不能有效嵌入認證信息(即在水印圖像峰值信噪比PSNR大于保真門限τ的條件下無法完整嵌入認證信息)，則返回重新嘗試生成新的認證塊，否則由式(2)確定δ，并把δ保存在認證塊固定像素的LSB上，這些LSB上的比特串Lsb作為水印載荷的一部分用于水印提取后的圖像恢復.

式中:Cv為參數δ下認證塊的有效水印容量;Cp為待嵌入的含認證信息的水印載荷量;PSNR(δ)為參數δ下的峰值信噪比;EF為認證信息嵌入成功與否的標志，EF=0表示失敗，EF=1表示成功.

LIAA的圖像基本塊選定為16×16，水印嵌入具體過程可參閱文獻［13］，需要指出的是，文中認證塊水印嵌入算法中用于保存認證塊結構表示比特和水印嵌入參數L的像素不參與水印的嵌入.

2.3 認證信息及認證塊水印載荷的生成

LIAA屬于基于獨立分塊的認證算法，因而也需要解決易受矢量攻擊的安全問題.現(xiàn)有的基于分塊相關［3］和基于等級結構［4］的抗矢量攻擊方法要求認證塊結構穩(wěn)定，不適用于LIAA.LIAA采用基于塊編號和圖像編號的方法［2，9］，但對其存在的圖像編號D存儲、管理與傳送等問題進行了如下改進:

式中，HMD5為散列函數，D為128 b的散列值.由式(5)生成的圖像編號D可實現(xiàn)圖像標識的唯一性.

為了實現(xiàn)盲認證，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)為認證塊的左上角坐標(作為區(qū)別認證塊的塊編號，用于克服同一圖像中不同認證塊之間的替換攻擊);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)則跳過該塊，繼續(xù)查看下一基本塊;若當前基本塊為BBend則結束程序.

2)若Lsb2Lsb3為00，表示當前基本塊為候選認證塊的末尾分塊，則轉步驟4);否則，若當前基本塊不是BBend，則根據Lsb2Lsb3轉到候選認證塊中相應的下一分塊(01表示下一分塊為當前基本塊的右鄰塊，10表示下一分塊為當前基本塊的下鄰塊，11表示下一分塊為當前基本塊的左鄰塊);若當前基本塊為BBend則結束程序.

3)如果當前基本塊的Lsb1為1，表示該候選認證塊識別失敗，則返回到該候選認證塊首塊的下一基本塊，轉到步驟1)，否則轉到步驟2).

4)判斷候選認證塊是否為一含2t(t=0，1，…)個基本塊的合法矩形圖像塊，如果不是，表明候選認證塊識別失敗;否則，對該候選認證塊執(zhí)行無損水印提取和像素恢復.如果水印提取和圖像恢復過程出錯，表明候選認證塊認證失敗;否則，把該認證塊的結構及提取的圖像編號、認證信息、圖像恢復結果保存在候選認證塊數組中，用于下一步以認證塊為單位的認證信息簽名的驗證.分析處理候選認證塊后，若當前基本塊不是BBend則返回到該候選認證塊首塊的下一基本塊，轉步驟1)，否則結束程序.

2.5 無損水印提取和圖像恢復

無損水印提取和圖像恢復以認證塊為單位進行，在認證塊固定像素的LSB上提取水印初始參數δ，執(zhí)行水印提取和圖像恢復(具體過程可參閱文獻［13］).需要注意的是，不參與水印嵌入的固定像素也不參與水印提取，這些像素的原始LSB用從水印中截取的Lsb(參見2.3)恢復.如果水印提取和圖像恢復過程出現(xiàn)錯誤，則輸出出錯標記，否則輸出水印提取結果和圖像恢復結果.

2.6 認證塊簽名驗證

(1)依次掃描候選認證塊數組中各記錄的圖像編號字段，選擇最大重現(xiàn)率的項作為最終圖像編號D，如果該項在數組的重現(xiàn)率低于50%，則認為發(fā)生了嚴重篡改，給出提示，結束認證.

(2)重新依次掃描候選認證塊數組，若當前候選認證塊的圖像編號字段的值不等于D，則該認證塊認證失敗;否則，用公鑰對當前候選認證塊執(zhí)行式(8)的DSA簽名驗證，并標記通過驗證的認證塊:

式中，VDSA為DSA簽名的驗證算法，S'為從當前認證塊中提取的認證信息為當前認證塊的像素恢復矩陣，k'為DSA簽名算法的公鑰.

(3)輸出含篡改塊標記和通過認證的區(qū)域的恢復圖像.

3 算法性能分析

LIAA結合了數字簽名的安全性和數字水印的篡改定位能力、盲認證能力，具有安全性高、篡改定位精度可動態(tài)調整、易于擴展等優(yōu)點.

3.1 安全性

由于解決了矢量攻擊問題，LIAA的安全性主要取決于所用的密碼系統(tǒng)，到目前為止320 b的DSA被證明還是安全的.LIAA在圖像沒有被篡改時，由恢復圖像計算所得的認證信息將與提取的認證信息完全相同，故虛警概率為0.當圖像出現(xiàn)被篡改時，即使是微小的變化，在認證端由密碼算法計算出的認證信息與提取的認證水印也截然不同，如假設認證信息服從隨機均勻分布，此時認證塊漏警的概率為2-320，這里還沒有考慮無損水印能否有效提取等因素，故漏警概率可近似為0.

3.2 篡改定位能力

LIAA的每一認證塊對應著圖2中圖像二叉樹上的某個節(jié)點，由二叉樹生成過程可知每一節(jié)點對應的圖像區(qū)域都是一個趨近正方形的區(qū)域.在保證認證信息完整嵌入的前提下，LIAA使認證塊的大小動態(tài)地趨于最小.由認證塊的劃分規(guī)則可知，LIAA認證塊的平均面積小于采用固定大小認證塊方式時的認證塊面積，相應地，篡改定位能力得到了提高.

3.3 擴展性

LIAA不僅適用于各種類型的圖像，而且易于根據具體的應用要求做相應的擴展，如通過設定保真度門限τ可實現(xiàn)對水印圖像失真的控制，用不同的保真度門限可分別調整圖像的感興趣區(qū)(ROI)和非ROI的篡改定位能力，從而在全圖保真度穩(wěn)定的情況下提高ROI的篡改定位能力.

4 實驗及結果分析

為驗證LIAA的有效性，在Matlab平臺上實現(xiàn)了LIAA，并用USC-SIPI圖像數據庫［15］中各種不同性質的圖像進行實驗.

為了方便分析，文中將無損圖像認證算法的篡改定位精度定義為

式中，M×N為宿主圖像I的分辨率，λ為認證塊總數.

圖4給出了圖像Lena、Baboon和Plane的篡改定位精度-認證塊保真門限曲線，篡改定位精度Γ隨著認證塊保真度門限τ的增加而增加，篡改定位能力下降.通過調整τ，可以在從基本塊大小到全圖大小的范圍內動態(tài)地獲得合適大小的認證塊.由于單個LIAA認證塊的水印載荷只有幾百比特，現(xiàn)實中有意義的圖像I采用LIAA中的無損水印算法時，有效認證塊在全圖大小范圍內總能找到合適大小的圖像塊嵌入認證信息，不會出現(xiàn)因認證水印無法有效嵌入而導致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能根據圖像的局部特征動態(tài)地調整定位精度，一般平滑區(qū)的定位能力要比紋理區(qū)的定位能力高，實際水印圖像的PSNR要高于無損認證設定的τ參數.

圖6給出了LIAA的篡改檢測、定位實例局部圖.實驗中對含認證水印的圖像Plane做了一處視覺難以識別的內容修改，如圖6(a)、6(b)所示，使用LIAA對圖6(b)進行認證，認證結果不僅能檢測出圖像被篡改，而且能準確地定位出篡改內容所在的認證塊區(qū)域，如圖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采用認證塊動態(tài)生成的策略解決了現(xiàn)有基于獨立分塊的無損圖像認證算法中的認證塊劃分問題，提高了篡改定位能力;通過多次嵌入的方式實現(xiàn)圖像編號的魯棒傳送，解決了基于圖像編號抗矢量攻擊方法的圖像編號管理、傳送問題，可有效地抗擊矢量攻擊.理論分析和實驗結果表明，LIAA綜合了數字簽名和數字水印在圖像認證應用中的優(yōu)點，安全性高，盲認證，篡改定位能力強于現(xiàn)有的無損圖像認證算法，且適應性強，適用于對安全性、保真度、篡改定位精度等要求高的圖像的精確認證.

［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/.