一種基于壓縮感知的無損圖像認證算法

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

(1東南大學影像科學與技術實驗室,南京 210096)

(2中法生物醫學信息研究中心,南京 210096)

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

無損圖像認證要求提取水印信息后,能恢復原始圖像,確保經過認證的圖像完全真實可信．無損圖像認證在特殊領域(如醫學、軍事等)的應用使得越來越多的研究者開始關注這項技術．文獻[1]提出了一種圖像自嵌入與自恢復的水印算法,不僅能檢測和定位惡意篡改,而且能恢復被損壞的圖像內容；但該算法并非完全可逆,不能完全恢復原始圖像．文獻[2]提出了一種基于水印的可逆圖像認證方案,能夠檢測篡改且可以實現篡改定位；但該算法將認證水印直接嵌入到像素最不重要位,魯棒性較差．文獻[3]提出了一種基于分塊的可逆認證算法,將圖像分為可逆塊與不可逆塊,不可逆塊用來提取圖像特征,可逆塊則利用差值擴展算法嵌入自身塊的特征和其他分塊的特征信息，該算法不僅能精確恢復原始圖像,還能夠對惡意篡改攻擊進行精確定位；但算法較復雜,且要求可逆塊數目不少于非可逆塊的數目,否則可逆認證不能實現．文獻[4]利用插值擴展和糾錯編碼,實現了一種能夠定位篡改圖像塊的可逆圖像認證方案；但糾錯編碼并不能完全保證水印提取的正確性．文獻[5]將圖像分塊后進行壓縮傳感隨機投影,并將投影值作為零水印注冊保存,不僅不改變圖像像素值,而且能夠檢測定位篡改；但由于注冊所需的零水印數據庫容量有限,該算法具有一定的局限性．

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

1 水印生成

1.1 壓縮感知

壓縮感知理論由Candès等[6-7]提出．只要信號在某個正交空間是可壓縮的或具有稀疏性的,就能以較低的頻率采樣信號,并通過非線性的優化算法從采樣信號中高概率重構出原信號．但一般的自然信號并不是絕對稀疏的,需要在某種稀疏基上進行稀疏表示．

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

y=Φx

(1)

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

y=Φx=ΦΨs=Θs

(2)

式中，Ψ為稀疏矩陣；Θ=ΦΨ,其大小為M×N．

當矩陣Θ滿足有限等距性質準則[8-9]時,壓縮感知理論能夠通過求解式(2)的逆問題,得到稀疏系數s,然后通過公式x=Ψs得到x．

Candès等[6-7]證明，壓縮感知信號重構問題可由l0-范數最小值求解式(2)得到s的估計,數學模型為

(3)

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

(4)

式(4)為凸優化問題,可轉化為線性規劃求解．

1.2 水印生成步驟

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

水印生成具體步驟如下:

1) 將圖像分成若干塊,分塊大小可以根據水印數據量和定位精度調整．

2) 對各個圖像塊進行分塊壓縮感知．

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

HMAC(K,M)t=H(K0?opad,H(K0?ipad,M))

(5)

式中,K為認證密碼;K0為密鑰，其長度為B;t為認證碼的長度,MD5中t=16,SHA-1中t=20;opad為由B個字節0x5a組成的字符串;ipad為由B個字節0x36組成的字符串;M為待加密的輸入數據．其具體流程為

① 在K后添0創建字長為B的字符串K0;

② 將K0和ipad進行異或運算;

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

④ 將H作用于步驟③ 生成的數據流上;

⑤ 將K0和opad進行異或運算;

⑥ 將步驟④的結果填充至步驟⑤生成的數據流中;

⑦ 將H作用于步驟⑥生成的數據流,輸出最終結果．

本文將SHA-1作為加密函數,每一分塊得到160bit的數據,選取其中32bit作為該數據塊的摘要信息．所有分塊比特流記作S,即認證水印為S．

2 水印嵌入

2.1 量化索引調制算法

為了保證正確定位篡改,必須提取出正確的水印信息,否則未經過篡改區域也會被認為已經篡改,即水印算法具有一定的魯棒性．目前,常用的魯棒水印算法是量化索引調制算法．

若圖像系數值為f,待嵌入水印數據為wu,則嵌入算法步驟如下[12]:

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

(6)

② 嵌入水印信息,嵌入后系數值為

(7)

相應的水印提取和圖像恢復算法步驟如下：

① 計算量化步長個數m′和量化間隔r′,即

(8)

② 提取水印數據wu,即

(9)

③ 恢復原始系數f,即

(10)

由式(6)和(7)可知,若系數f的存儲精度為n位,則f′的存儲精度為n+b位．精度的不一致導致QIM算法不可逆,因此需要對f′精度進行修改,即

(11)

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

2.2 水印嵌入步驟

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

① 為防止嵌入水印后逆運算時溢出,需要對圖像進行預處理．若圖像像素值為p(p∈[0,2b-1]),則預處理公式為

(12)

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

② 對圖像進行整數小波變換,得到低高頻子帶系數值C．

③ 保存C的奇偶信息,生成位置圖Lp．此奇偶信息即作為量化索引調制逆變換時的精度信息．保存該位置圖Lp,作為圖像恢復密鑰．

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

⑤ 經過小波逆變換即可得到加水印圖像．

3 水印提取與篡改檢測

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

① 對圖像進行整數小波變換,得到低高頻小波系數值．

② 利用圖像恢復密鑰Lp及QIM逆算法提取出水印信息D并恢復系數C,然后進行小波逆變換．

③ 若圖像分塊總數為T,則認證水印為D中前32T個信息流．S以后的信息流設為D1．

④ 根據D1以及EOS標志得到預處理位置圖信息流Lf,解碼后得到Lm．

⑤ 利用Lm恢復圖像．

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

4 實驗結果與分析

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

4.1 不可感知性

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

(13)

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

選擇如圖1所示的圖像進行實驗,并與文獻[3-4]的算法進行比較,結果見表 1．由表可知,本文算法對不同紋理的圖像均具有較好的不可感知性,滿足視覺上不可覺察的要求．

表1 PSNR比較

4.2 篡改認證性

將壓縮感知隨機投影測量值作為圖像內容特征,不僅能較好地表征圖像,減小數據量,而且對篡改具有強敏感性．壓縮傳感測量值之所以能檢測篡改是因為具有差異放大的功能,即圖像間的細微差別都會被放大．這個差異放大的能力實際是通過測量矩陣對差異進行加權累加實現的[5]．即使是差異很小的測量值,通過哈希函數后也會有很大的差異．因而即使圖像只有1bit的改變也會被檢測出來．

圖1 測試圖像

對Lena,Fruits,Truck圖像加水印后,分別進行偽版權標記、復制-篡改偽造以及圖像修復攻擊,利用本文算法進行篡改檢測與定位，結果見圖2～圖4．

圖3 Fruits認證

圖4 Truck認證

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

5 結語

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

)

[1]張鴻賓,楊成.圖像的自嵌入及竄改的檢測和恢復算法[J].電子學報,2004,32(2):196-199.

Zhang Hongbin,Yang Cheng.Temper detection and self recovery of images using self-embedding[J].ActaElectronicaSinica,2004,32(2): 196-199.(in Chinese)

[2]Gao T,Gu Q.Reversible image authentication based on combination of reversible and LSB algorithm [C]//Proceedingsof2007InternationalConferenceonComputationalIntelligenceandSecurityWorkshops.Harbin,China,2007: 636-639.

[3]Gu Q,Gao T.A new image authentication based on reversible watermarking algorithm[C]//Proceedingsofthe7thWorldCongressonIntelligentControlandAutomation.Chongqing,China,2008: 2727-2731.

[4]文家福,王嘉禎,劉愛珍,等.基于差值擴展和糾錯編碼的可逆圖像認證[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].ComputerEngineering,2009,35(22): 125-127.(in Chinese)

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

Zhao Chunhui,Liu Wei.Block compressive sensing based image semi-fragile zero-watermarking algorithm[J].ActaAutomaticaSinica,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].IEEETransactionsonInformationTheory,2006,52(2): 489-509.

[7]Donoho D.Compressed sensing [J].IEEETransactionsonInformationTheory,2006,52(4): 1289-1306.

[8]Candès E,Romberg J.The restricted isometry property and its implications for compressed sensing [J].ComptesRendusMathematique,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].ConstructiveApproximation,2008,28(3): 253-263.

[10]Rachlin Y,Baron D.The secrecy of compressed sensing measurements[C]//Proceedingsofthe46thAnnualAllertonConferenceonCommunication,ControlandComputing.Urbana-Champaign,IL,USA,2008: 813-817.

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

Zhou Yan,Zhang Defeng,Ma Zilong.The research of image hash watermarking algorithm based on compressed sensing[J].ActaScientiarumNaturaliumUniversitatisSunyatseni,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]//Proceedingsofthe3rdInternationalConferenceonCrimeDetectionandPrevention.London,UK,2009: 1-6.