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

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

(1東南大學(xué)影像科學(xué)與技術(shù)實(shí)驗(yàn)室,南京 210096)

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

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

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

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

1 水印生成

1.1 壓縮感知

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

假設(shè)一個(gè)長(zhǎng)度為N的實(shí)值時(shí)間離散信號(hào)x,經(jīng)過(guò)一個(gè)大小為M×N測(cè)量矩陣線性投影,得到長(zhǎng)度為M(M?N)的測(cè)量值y,即

y=Φx

(1)

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

y=Φx=ΦΨs=Θs

(2)

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

當(dāng)矩陣Θ滿足有限等距性質(zhì)準(zhǔn)則[8-9]時(shí),壓縮感知理論能夠通過(guò)求解式(2)的逆問(wèn)題,得到稀疏系數(shù)s,然后通過(guò)公式x=Ψs得到x．

Candès等[6-7]證明，壓縮感知信號(hào)重構(gòu)問(wèn)題可由l0-范數(shù)最小值求解式(2)得到s的估計(jì),數(shù)學(xué)模型為

(3)

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

(4)

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

1.2 水印生成步驟

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

水印生成具體步驟如下:

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

2) 對(duì)各個(gè)圖像塊進(jìn)行分塊壓縮感知．

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

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

(5)

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

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

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

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

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

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

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

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

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

2 水印嵌入

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

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

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

① 計(jì)算量化步長(zhǎng)個(gè)數(shù)m(m≥0)以及f到第m個(gè)量化步長(zhǎng)的距離r(r∈[0,2bΔ),Δ為量化步長(zhǎng)),即

(6)

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

(7)

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

① 計(jì)算量化步長(zhǎng)個(gè)數(shù)m′和量化間隔r′,即

(8)

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

(9)

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

(10)

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

(11)

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

2.2 水印嵌入步驟

本文實(shí)驗(yàn)中水印嵌入步驟如下:

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

(12)

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

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

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

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

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

3 水印提取與篡改檢測(cè)

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 不可感知性

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

(13)

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

選擇如圖1所示的圖像進(jìn)行實(shí)驗(yàn),并與文獻(xiàn)[3-4]的算法進(jìn)行比較,結(jié)果見(jiàn)表 1．由表可知,本文算法對(duì)不同紋理的圖像均具有較好的不可感知性,滿足視覺(jué)上不可覺(jué)察的要求．

表1 PSNR比較

4.2 篡改認(rèn)證性

將壓縮感知隨機(jī)投影測(cè)量值作為圖像內(nèi)容特征,不僅能較好地表征圖像,減小數(shù)據(jù)量,而且對(duì)篡改具有強(qiáng)敏感性．壓縮傳感測(cè)量值之所以能檢測(cè)篡改是因?yàn)榫哂胁町惙糯蟮墓δ?即圖像間的細(xì)微差別都會(huì)被放大．這個(gè)差異放大的能力實(shí)際是通過(guò)測(cè)量矩陣對(duì)差異進(jìn)行加權(quán)累加實(shí)現(xiàn)的[5]．即使是差異很小的測(cè)量值,通過(guò)哈希函數(shù)后也會(huì)有很大的差異．因而即使圖像只有1bit的改變也會(huì)被檢測(cè)出來(lái)．

圖1 測(cè)試圖像

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

圖3 Fruits認(rèn)證

圖4 Truck認(rèn)證

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

5 結(jié)語(yǔ)

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

)

[1]張鴻賓,楊成.圖像的自嵌入及竄改的檢測(cè)和恢復(fù)算法[J].電子學(xué)報(bào),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]文家福,王嘉禎,劉愛(ài)珍,等.基于差值擴(kuò)展和糾錯(cuò)編碼的可逆圖像認(rèn)證[J].計(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].ComputerEngineering,2009,35(22): 125-127.(in Chinese)

[5]趙春暉,劉巍.基于分塊壓縮感知的圖像半脆弱零水印算法[J].自動(dòng)化學(xué)報(bào),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].中山大學(xué)學(xué)報(bào):自然科學(xué)版,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.