一種基于壓縮感知的無損圖像認(rèn)證算法

艾 鴿 伍家松，2 段宇平，2 舒華忠，2

(1 東南大學(xué)影像科學(xué)與技術(shù)實驗室，南京210096)

(2 中法生物醫(yī)學(xué)信息研究中心，南京210096)

隨著網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，信息交流和共享變得越來越容易，在這個過程中，信息的完整性和可靠性受到越來越嚴(yán)重的威脅.計算機(jī)軟件功能的日益強(qiáng)大，使得多媒體數(shù)據(jù)的篡改更容易被普通人所掌握.諸如“正龍拍虎”、“藏羚羊穿越青藏鐵路”等被廣泛報道的虛假新聞圖片造成了惡劣的社會影響.因此，對信息進(jìn)行安全認(rèn)證十分必要.多媒體數(shù)據(jù)認(rèn)證的目的是確認(rèn)數(shù)據(jù)是否完整、真實，是否經(jīng)過任何處理過程，并對其來源進(jìn)行判定.多媒體數(shù)據(jù)認(rèn)證在電子商務(wù)和政務(wù)、法庭證據(jù)、新聞傳媒、金融、保險、公安和醫(yī)療等領(lǐng)域均有著廣泛的應(yīng)用.

無損圖像認(rèn)證要求提取水印信息后，能恢復(fù)原始圖像，確保經(jīng)過認(rèn)證的圖像完全真實可信.無損圖像認(rèn)證在特殊領(lǐng)域(如醫(yī)學(xué)、軍事等)的應(yīng)用使得越來越多的研究者開始關(guān)注這項技術(shù).文獻(xiàn)［1］提出了一種圖像自嵌入與自恢復(fù)的水印算法，不僅能檢測和定位惡意篡改，而且能恢復(fù)被損壞的圖像內(nèi)容;但該算法并非完全可逆，不能完全恢復(fù)原始圖像.文獻(xiàn)［2］提出了一種基于水印的可逆圖像認(rèn)證方案，能夠檢測篡改且可以實現(xiàn)篡改定位;但該算法將認(rèn)證水印直接嵌入到像素最不重要位，魯棒性較差.文獻(xiàn)［3］提出了一種基于分塊的可逆認(rèn)證算法，將圖像分為可逆塊與不可逆塊，不可逆塊用來提取圖像特征，可逆塊則利用差值擴(kuò)展算法嵌入自身塊的特征和其他分塊的特征信息，該算法不僅能精確恢復(fù)原始圖像，還能夠?qū)阂獯鄹墓暨M(jìn)行精確定位;但算法較復(fù)雜，且要求可逆塊數(shù)目不少于非可逆塊的數(shù)目，否則可逆認(rèn)證不能實現(xiàn).文獻(xiàn)［4］利用插值擴(kuò)展和糾錯編碼，實現(xiàn)了一種能夠定位篡改圖像塊的可逆圖像認(rèn)證方案;但糾錯編碼并不能完全保證水印提取的正確性.文獻(xiàn)［5］將圖像分塊后進(jìn)行壓縮傳感隨機(jī)投影，并將投影值作為零水印注冊保存，不僅不改變圖像像素值，而且能夠檢測定位篡改;但由于注冊所需的零水印數(shù)據(jù)庫容量有限，該算法具有一定的局限性.

本文提出的水印算法屬于完全認(rèn)證.首先，對原始圖像進(jìn)行壓縮感知隨機(jī)投影，得到測量值.然后，利用基于哈希的消息認(rèn)證碼(HMAC)生成水印信息，并通過量化索引調(diào)制(QIM)算法將其嵌入到圖像小波變換后的低高頻系數(shù)中.最后，利用整數(shù)小波逆變換得到含水印圖像.量化索引調(diào)制過程是不可逆的，恢復(fù)時需要額外的誤差信息，因此將量化索引調(diào)制產(chǎn)生的誤差信息作為恢復(fù)密鑰保存.

1 水印生成

1.1 壓縮感知

壓縮感知理論由Candès 等［6－7］提出.只要信號在某個正交空間是可壓縮的或具有稀疏性的，就能以較低的頻率采樣信號，并通過非線性的優(yōu)化算法從采樣信號中高概率重構(gòu)出原信號.但一般的自然信號并不是絕對稀疏的，需要在某種稀疏基上進(jìn)行稀疏表示.

假設(shè)一個長度為N 的實值時間離散信號x，經(jīng)過一個大小為M ×N 測量矩陣線性投影，得到長度為M(M?N)的測量值y，即

式中，Φ 為測量矩陣，其大小為M ×N.若信號s 在Ψ 上是稀疏的，則式(1)可描述為

式中，Ψ 為稀疏矩陣;Θ=ΦΨ，其大小為M ×N.

當(dāng)矩陣Θ 滿足有限等距性質(zhì)準(zhǔn)則［8－9］時，壓縮感知理論能夠通過求解式(2)的逆問題，得到稀疏系數(shù)s，然后通過公式x=Ψs 得到x.

Candès 等［6－7］證明，壓縮感知信號重構(gòu)問題可由l0－范數(shù)最小值求解式(2)得到s 的估計，數(shù)學(xué)模型為

但是對l0－范數(shù)的求解是一個NP 問題，即難以求解或者無法驗證解的可靠性，因此需要尋求一種更有效的等價求解方法.l1－范數(shù)最小問題在一定條件下和l0－范數(shù)最小化問題具有等價性，可以得到相同的解.因此，式(3)可以轉(zhuǎn)化為l1－范數(shù)最優(yōu)化問題，即

式(4)為凸優(yōu)化問題，可轉(zhuǎn)化為線性規(guī)劃求解.

1.2 水印生成步驟

壓縮感知測量值作為圖像的內(nèi)容特征，不僅完整表征了圖像，且數(shù)據(jù)量遠(yuǎn)小于原圖像.而觀測矩陣元素可對圖像間的細(xì)微差別進(jìn)行加權(quán)累加使之放大，繼而保證相近圖像不會生成相似的觀測值.另外，測量矩陣所具有的加密作用保證了攻擊者在不知道密鑰的情況下無法通過測量值恢復(fù)原始圖像的內(nèi)容，滿足了水印的保密要求［10］.與其他自嵌入水印算法相比，基于壓縮感知的水印對原始圖像的信息提取更加全面，安全性更好［5］.

水印生成具體步驟如下:

1)將圖像分成若干塊，分塊大小可以根據(jù)水印數(shù)據(jù)量和定位精度調(diào)整.

2)對各個圖像塊進(jìn)行分塊壓縮感知.

3)將各塊壓縮感知隨機(jī)投影得到的壓縮測量值作為HMAC 的輸入，得到消息認(rèn)證碼.HMAC需要1 個加密哈希函數(shù)H(MD5 或SHA－1)和1 個密鑰，可以理解為在原有的哈希函數(shù)中添加了密鑰，故其安全性不完全依賴于所采用的哈希函數(shù).HMAC 的計算公式為［11］

式中，K 為認(rèn)證密碼;K0為密鑰，其長度為B;t 為認(rèn)證碼的長度，MD5 中t =16，SHA－1 中t =20;opad 為由B 個字節(jié)0x5a 組成的字符串;ipad 為由B 個字節(jié)0x36 組成的字符串;M 為待加密的輸入數(shù)據(jù).其具體流程為

①在K 后添0 創(chuàng)建字長為B 的字符串K0;

②將K0和ipad 進(jìn)行異或運算;

③將M 添至步驟②生成的字符串上;

④將H 作用于步驟③生成的數(shù)據(jù)流上;

⑤將K0和opad 進(jìn)行異或運算;

⑥將步驟④的結(jié)果填充至步驟⑤生成的數(shù)據(jù)流中;

⑦將H 作用于步驟⑥生成的數(shù)據(jù)流，輸出最終結(jié)果.

本文將SHA－1 作為加密函數(shù)，每一分塊得到160 bit 的數(shù)據(jù)，選取其中32 bit 作為該數(shù)據(jù)塊的摘要信息.所有分塊比特流記作S，即認(rèn)證水印為S.

2 水印嵌入

2.1 量化索引調(diào)制算法

為了保證正確定位篡改，必須提取出正確的水印信息，否則未經(jīng)過篡改區(qū)域也會被認(rèn)為已經(jīng)篡改，即水印算法具有一定的魯棒性.目前，常用的魯棒水印算法是量化索引調(diào)制算法.

若圖像系數(shù)值為f，待嵌入水印數(shù)據(jù)為wu，則嵌入算法步驟如下［12］:

①計算量化步長個數(shù)m(m≥0)以及f 到第m個量化步長的距離r(r ∈［0，2bΔ)，Δ 為量化步長)，即

②嵌入水印信息，嵌入后系數(shù)值為

相應(yīng)的水印提取和圖像恢復(fù)算法步驟如下:

①計算量化步長個數(shù)m′和量化間隔r′，即

②提取水印數(shù)據(jù)wu，即

③恢復(fù)原始系數(shù)f，即

由式(6)和(7)可知，若系數(shù)f 的存儲精度為n位，則f′的存儲精度為n+b 位.精度的不一致導(dǎo)致QIM 算法不可逆，因此需要對f′精度進(jìn)行修改，即

要想無損地恢復(fù)原始圖像，需要額外存儲f′的精度信息.水印提取時，在原有系數(shù)的基礎(chǔ)上加上額外的精度信息作為f′，利用式(8)～(10)即可無損恢復(fù)圖像.

2.2 水印嵌入步驟

本文實驗中水印嵌入步驟如下:

①為防止嵌入水印后逆運算時溢出，需要對圖像進(jìn)行預(yù)處理.若圖像像素值為p(p∈［0，2b－1］)，則預(yù)處理公式為

式中，δ 為預(yù)處理閾值，可根據(jù)圖像亮度進(jìn)行調(diào)整.為了在水印提取端恢復(fù)原始圖像，需要存儲預(yù)處理信息.假設(shè)生成一個位置圖Lm，大小與圖像相同.若像素值利用式(12)移位，則該位置圖處標(biāo)為1;否則，標(biāo)為0.然后，將位置圖信息壓縮，壓縮后的位置圖記作Lf，則所有待嵌入水印信息為D =S∪Lf=b1b2…bm，其中b1，b2，…，bm∈{0，1}.

②對圖像進(jìn)行整數(shù)小波變換，得到低高頻子帶系數(shù)值C.

③保存C 的奇偶信息，生成位置圖Lp.此奇偶信息即作為量化索引調(diào)制逆變換時的精度信息.保存該位置圖Lp，作為圖像恢復(fù)密鑰.

④利用式(6)～(11)，將水印信息D 嵌入到系數(shù)C 中.此處，式(6)～(11)中b =1，即水印信息是二值的.

⑤經(jīng)過小波逆變換即可得到加水印圖像.

3 水印提取與篡改檢測

水印提取是水印嵌入的逆過程，步驟如下:

①對圖像進(jìn)行整數(shù)小波變換，得到低高頻小波系數(shù)值.

②利用圖像恢復(fù)密鑰Lp及QIM 逆算法提取出水印信息D 并恢復(fù)系數(shù)C，然后進(jìn)行小波逆變換.

③若圖像分塊總數(shù)為T，則認(rèn)證水印為D 中前32T 個信息流.S 以后的信息流設(shè)為D1.

④根據(jù)D1以及EOS 標(biāo)志得到預(yù)處理位置圖信息流Lf，解碼后得到Lm.

⑤利用Lm恢復(fù)圖像.

⑥將恢復(fù)后的圖像按相同的生成算法得到比特流R，然后將R 劃分為多個等長的比特流rl(l =0，1，…，T)，每個等長比特流為32 bit.同時對S 進(jìn)行同樣的操作，得到sl(l=0，1，…，T).分別將其進(jìn)行比較，若相等，則認(rèn)為相應(yīng)的圖像塊是可認(rèn)證的;否則，認(rèn)為該算法已被篡改.

4 實驗結(jié)果與分析

下面從不可感知性和篡改認(rèn)證性來分析本文算法的性能.實驗環(huán)境為Windows XP，Matlab 2010b，位置圖壓縮采用游程編碼和哈夫曼編碼.

4.1 不可感知性

水印的不可感知性一般使用峰值信噪比(PSNR)來衡量，其計算公式為

式中，X(i，j)，Xw(i，j)分別為嵌入水印前、后的像素值;L，W 分別為圖像的長和寬.PSNR 值越大，表明水印的不可感知性越好.

選擇如圖1所示的圖像進(jìn)行實驗，并與文獻(xiàn)［3－4］的算法進(jìn)行比較，結(jié)果見表1.由表可知，本文算法對不同紋理的圖像均具有較好的不可感知性，滿足視覺上不可覺察的要求.

表1 PSNR 比較

4.2 篡改認(rèn)證性

圖1 測試圖像

將壓縮感知隨機(jī)投影測量值作為圖像內(nèi)容特征，不僅能較好地表征圖像，減小數(shù)據(jù)量，而且對篡改具有強(qiáng)敏感性.壓縮傳感測量值之所以能檢測篡改是因為具有差異放大的功能，即圖像間的細(xì)微差別都會被放大.這個差異放大的能力實際是通過測量矩陣對差異進(jìn)行加權(quán)累加實現(xiàn)的［5］.即使是差異很小的測量值，通過哈希函數(shù)后也會有很大的差異.因而即使圖像只有1 bit 的改變也會被檢測出來.

對Lena，F(xiàn)ruits，Truck 圖像加水印后，分別進(jìn)行偽版權(quán)標(biāo)記、復(fù)制－篡改偽造以及圖像修復(fù)攻擊，利用本文算法進(jìn)行篡改檢測與定位，結(jié)果見圖2～圖4.

圖2 Lena 認(rèn)證

圖3 Fruits 認(rèn)證

圖4 Truck 認(rèn)證

由圖2～圖4可知，本文算法對這種局部篡改具有較好的認(rèn)證效果.目前，圖像認(rèn)證算法多采用魯棒性(即抗攻擊能力)來比較其篡改認(rèn)證性能，且大多針對有損圖像認(rèn)證算法，無損圖像認(rèn)證算法很大程度上屬于完全脆弱水印，魯棒性相對較弱，不具有可比較性，故此處未與其他算法進(jìn)行比較.

5 結(jié)語

本文提出了一種基于壓縮感知的無損圖像認(rèn)證算法.該算法首先對圖像進(jìn)行壓縮感知隨機(jī)投影，將得到的測量值作為HMAC 輸入值，生成圖像的摘要.然后，利用量化索引調(diào)制算法，將生成的水印信息嵌入到圖像小波域中.實驗結(jié)果表明，該算法具有較好的不可感知性，且能夠?qū)D像進(jìn)行認(rèn)證，定位篡改區(qū)域.若圖像經(jīng)過認(rèn)證，則可無損恢復(fù)原始圖像.由此可見，該算法可應(yīng)用于醫(yī)學(xué)圖像處理.可將醫(yī)學(xué)圖像分為ROI 區(qū)域和RONI 區(qū)域，將病患信息和ROI 認(rèn)證信息嵌入到RONI 區(qū)域，不僅可對ROI 區(qū)域進(jìn)行認(rèn)證，還保證了水印的魯棒性以及可逆性.本文算法的不足之處在于，水印生成的嚴(yán)謹(jǐn)性使得提取端無法區(qū)分惡意篡改與無意篡改，這需要在后續(xù)工作中進(jìn)一步改進(jìn).

References)

［1］張鴻賓，楊成.圖像的自嵌入及竄改的檢測和恢復(fù)算法［J］.電子學(xué)報，2004，32(2):196－199.Zhang Hongbin，Yang Cheng.Temper detection and self recovery of images using self－embedding［J］.Acta Electronica Sinica，2004，32(2):196－199.(in Chinese)

［2］Gao T，Gu Q.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.

［3］Gu Q，Gao T.A new image authentication based on reversible watermarking algorithm［C］//Proceedings of the 7th World Congress on Intelligent Control and Automation.Chongqing，China，2008:2727－2731.

［4］文家福，王嘉禎，劉愛珍，等.基于差值擴(kuò)展和糾錯編碼的可逆圖像認(rèn)證［J］.計算機(jī)工程，2009，35(22):125－127.

Wen Jiafu，Wang Jiazhen，Liu Aizhen，et al.Reversible image authentication based on difference expansion and error correction code［J］.Computer Engineering，2009，35(22):125－127.(in Chinese)

［5］趙春暉，劉巍.基于分塊壓縮感知的圖像半脆弱零水印算法［J］.自動化學(xué)報，2012，38(4):609－617.

Zhao Chunhui，Liu Wei.Block compressive sensing based image semi－fragile zero－watermarking algorithm［J］.Acta Automatica Sinica，2012，38(4):609－617.(in Chinese)

［6］Candès E，Romberg J，Tao T.Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information［J］.IEEE Transactions on Information Theory，2006，52(2):489－509.

［7］Donoho D.Compressed sensing ［J］.IEEE Transactions on Information Theory，2006，52(4):1289－1306.

［8］Candès E，Romberg J.The restricted isometry property and its implications for compressed sensing ［J］.Comptes Rendus Mathematique，2008，346(9):589－592.

［9］Baraniuk R，Davenport M，Devore R，et al.A simple proof of the restricted isometry property for random matrices［J］.Constructive Approximation，2008，28(3):253－263.

［10］Rachlin Y，Baron D.The secrecy of compressed sensing measurements［C］//Proceedings of the 46th Annual Allerton Conference on Communication，Control and Computing.Urbana－Champaign，IL，USA，2008:813－817.

［11］周燕，張德豐，馬子龍.基于壓縮傳感的圖像哈希水印算法研究［J］.中山大學(xué)學(xué)報:自然科學(xué)版，2010，49(6):58－63.

Zhou Yan，Zhang Defeng，Ma Zilong.The research of image hash watermarking algorithm based on compressed sensing［J］.Acta Scientiarum Naturalium Universitatis Sunyatseni，2010，49(6):58－63.(in Chinese)

［12］Peng F，Lei Y，Li C，et al.A reversible watermarking scheme for 2D engineering graphics based on improved quantization index modulation［C］//Proceedings of the 3rd International Conference on Crime Detection and Prevention.London，UK，2009:1－6.