曲長波　李棟棟

(遼寧工程技術(shù)大學(xué)軟件學(xué)院　遼寧 葫蘆島 125105)

?

基于視覺密碼和邊緣檢測的零水印算法

曲長波李棟棟

(遼寧工程技術(shù)大學(xué)軟件學(xué)院遼寧 葫蘆島 125105)

在版權(quán)認(rèn)證領(lǐng)域，傳統(tǒng)的水印算法往往是在載體圖像中嵌入二值圖像。這種算法有兩個缺點：一是水印的嵌入改變了載體圖像，而在醫(yī)學(xué)和偵查等領(lǐng)域需要保留原始數(shù)據(jù)；二是圖像受到篡改攻擊后，很難判斷攻擊的類型和位置。針對以上兩個問題，提出一種基于視覺密碼和邊緣檢測的零水印算法。首先，對載體圖像進(jìn)行置亂和奇異值分解等操作提取特征矩陣；然后，將特征矩陣按照算法生成公有圖和私有圖；最后，將私有圖和零水印存至認(rèn)證中心。另外，應(yīng)用游程編碼對圖像邊緣進(jìn)行無損壓縮生成密鑰，用來進(jìn)行篡改檢測。實驗表明，該算法具有非常好的魯棒性和安全性，尤其是抵御噪聲攻擊；在篡改檢測方面也具有很好的效果。

版權(quán)認(rèn)證視覺密碼特征矩陣邊緣檢測

0　引　言

信息隱藏技術(shù)是一門新興學(xué)科，即將秘密信息隱藏到普通文件中，保證秘密信息不被盜密者發(fā)現(xiàn)并在網(wǎng)絡(luò)中安全傳輸?shù)募夹g(shù)[14]。在版權(quán)保護(hù)方面，文獻(xiàn)[6,12]提出的數(shù)字水印技術(shù)多將水印嵌入載體圖像，這種嵌入方式影響了載體圖像的完整性，在對數(shù)據(jù)完整性要求較高的醫(yī)學(xué)和偵查領(lǐng)域，這顯然是不合理的[4]。在偵查等領(lǐng)域，我們還需要對圖像進(jìn)行篡改檢測，以便于對圖像所受攻擊進(jìn)行鑒別和定位，而近年來的水印技術(shù)很少將兩者進(jìn)行結(jié)合。另外，在算法保護(hù)方面，算法的加密也是很重要的一部分，因為算法一旦泄露，不但起不到保護(hù)版權(quán)的作用，甚至為侵權(quán)和盜版提供了更便利和以假亂真的渠道。

基于以上問題，本文提出基于視覺密碼和邊緣檢測的零水印算法。在水印嵌入上，零水印算法通過提取載體圖像的固有特征生成零水印的兩部分，從而保護(hù)載體圖像的完整性。在篡改檢測上，應(yīng)用游程編碼對提取載體圖像邊緣后所得圖像進(jìn)行無損壓縮生成密鑰，用于后期篡改檢測和定位。在算法保護(hù)方面，利用視覺密碼技術(shù)將版權(quán)水印根據(jù)載體圖像固有特征和固定的匹配算法生成水印的兩個分圖：一個分圖標(biāo)志圖像信息，并在生成后進(jìn)行銷毀；一個分圖注冊到認(rèn)證中心1。同時，將兩個分圖疊加后生成的零水印注冊到認(rèn)證中心2，這種版權(quán)認(rèn)證方式采用了“三方分離”的方法。分圖可以一個嵌入，一個進(jìn)行版權(quán)保護(hù)[9]。除了擁有兩個分圖并進(jìn)行疊加獲得零水印以外，還需要到認(rèn)證中心檢測才能確定版權(quán)歸屬。任何一方單方持有水印的一個分圖甚至是版權(quán)水印都無法解密圖像，從而保證了算法的安全性。Hsu等[7]提出了一種視覺密碼的數(shù)字水印方案，該方案采用傳統(tǒng)嵌入方式，使原始數(shù)據(jù)遭到破壞；曲長波等[10]提出了一種小波域視覺密碼零水印算法，該算法在提取特征矩陣時采用均值和指定方法生成零水印，對于噪聲攻擊等影響均值的方法沒有好的魯棒性；曲長波等[3]提出平衡多小波的視覺密碼技術(shù)，該算法的特征信息不夠全面，導(dǎo)致魯棒性不夠好。本文在考慮到以上各問題的基礎(chǔ)上，平衡了文獻(xiàn)[7，10]的缺點，在此基礎(chǔ)上又增加了篡改檢測。實驗表明該算法具有較高的魯棒性和安全性，其中篡改檢測對多種常見攻擊具有十分好的檢測效果。

1　算法理論基礎(chǔ)

1.1奇異值分解

數(shù)值分析中的奇異值分解是一種矩陣對角化的數(shù)值算法[11]，可以將指定矩陣分解為3個矩陣的乘積，即：

(1)

奇異值分解可以快速將大量的信號能量壓縮到很少的系數(shù)中。奇異值所表現(xiàn)的是圖像的固有特征而非視覺特性，為水印的不可見性提供了保障[6]。根據(jù)奇異值分解的這種特性，可以將其應(yīng)用到圖像的分解中，用少量數(shù)據(jù)描述圖像主要特征并生成零水印，從而獲得魯棒性較好的零水印算法。

1.2視覺密碼技術(shù)

視覺密碼是一種只需人眼解密圖像而不需要其余處理過程參與的加密方式[15]?？梢酝ㄟ^將一幅保密圖像分解為公有圖和私有圖兩部分進(jìn)行圖像加密，并把兩部分圖像疊加后進(jìn)行解密[16]?？梢暶艽a方案消除了復(fù)雜的解密過程,加密圖像可以通過疊加操作恢復(fù)[2]。

算法[17〗：設(shè)加密圖像尺寸為N×N，加密圖像按照算法生成兩個2N×2N的部分。加密圖像的1個像素分解成4個像素，其中白色像素分解為2×2的僅有2個黑像素的灰色矩陣，而黑色像素分解為2×2的有4個黑像素的全黑矩陣。圖1是加密圖像分解和加密產(chǎn)生的效果圖，(a)“版權(quán)保護(hù)”經(jīng)過分解成為兩部分：(b)和(c)。(d)是將兩部分疊加后得到的解密圖像。

圖1　視覺密碼效果圖

2　零水印及密鑰生成算法

2.1特征矩陣提取算法

特征矩陣提取過程分為小波變換、分塊操作、奇異值分解、取最大奇異值操作和取最高位操作。設(shè)載體圖像I大小為M×M，水印圖像W大小為m×m，則具體步驟如下：

(1) 采用置亂變換技術(shù)對圖像進(jìn)行預(yù)處理[8]，把載體圖像I進(jìn)行置亂，像素重新分布后得到置亂后的圖像S。

(2) 對載體圖像進(jìn)行L級小波變換，得低頻域cAL。把cAL均分為m×m塊，得到Bij(i,j∈{1,2,…,M/(2L×m)})矩陣分塊。

(3) 將Bij進(jìn)行奇異值分解，把每塊的最大奇異值經(jīng)過四舍五入和取最高位操作得到過渡矩陣Xij(i,j∈{1,2,…,M/(2L×m)})。

(4) 最后根據(jù)過渡矩陣X的奇偶性生成特征矩陣Y。即:

(2)

2.2零水印生成算法及算法銷毀方式

在得到特征矩陣Y之后，結(jié)合特征矩陣和版權(quán)水印圖像，用視覺密碼技術(shù)形成版權(quán)保護(hù)圖像的兩個部分，具體算法如表1所示。

表1　零水印算法生成圖示

即：

(3)

(4)

從式(4)可以看出，公有圖的每個像素M(i,j)的生成方式僅僅依賴于特征矩陣的每個像素Y(i,j)，與二值版權(quán)水印W(i,j)無關(guān)。為了預(yù)防算法的泄露，在兩分圖生成后，先將零水印MO和私有圖O保存至不同認(rèn)證中心2和認(rèn)證中心1，實現(xiàn)認(rèn)證分離。然后，立即將水印生成式(3)中私有圖O(i,j)的生成方式和二值版權(quán)水印W進(jìn)行銷毀，僅留下公有圖M(i,j)的生成算法以用來后期提取。

2.3密鑰生成算法

密鑰生成算法分為載體圖像邊緣檢測和游程編碼無損壓縮兩部分。游程編碼主要思想是指將連續(xù)相同的信號用信號值和長度所組成的二元數(shù)組來替代[5]。方法如下：

(1) 首先對載體圖像應(yīng)用合適微分算子和閾值進(jìn)行邊緣檢測得到二值圖像E。根據(jù)文獻(xiàn)[18]中各類算子邊緣檢測的特點，選用檢測輪廓清晰、細(xì)節(jié)完整度較高的算子。不同閾值與壓縮率和漏警率[19]的關(guān)系如圖2所示。

(2) 然后對E應(yīng)用游程編碼RLC(Run Length Coding)進(jìn)行無損壓縮得到一維數(shù)值序列K。

(3) 最后，將一維數(shù)值序列K作為密鑰K進(jìn)行保存，用于后期檢測。

圖2　不同閾值壓縮率及漏警率折線圖

根據(jù)圖2可以看出，隨著選定的算子(canny)在提取邊緣時閾值的不斷增大，游程編碼的壓縮率逐步提高，并在0.1時達(dá)到頂峰；同時，后期篡改檢測(選用50個隨機(jī)3×3篡改區(qū)域進(jìn)行漏警率計算)的漏警率也在逐步增大，而在0.1時有較小回落。本著使密鑰數(shù)據(jù)量最小和定位精準(zhǔn)度高的原則，應(yīng)該選擇壓縮率最高和漏警率最低的閾值作為本文設(shè)定的閾值，而對于其他圖像，應(yīng)具體問題具體分析。

3　零水印認(rèn)證及篡改檢測算法

3.1水印認(rèn)證算法

零水印認(rèn)證主要是公有圖的提取。載體圖像在經(jīng)過攻擊后得到圖像I’，對圖像I’進(jìn)行同2.1節(jié)的特征矩陣提取，在提取到特征矩陣之后，結(jié)合2.2節(jié)中M(i,j)的算法生成零水印的公有圖M。最后，公有圖M和認(rèn)證中心1保存的零水印私有圖O進(jìn)行疊加，得到攻擊后的零水印圖像，將攻擊后的零水印圖像與認(rèn)證中心2得到的零水印圖像進(jìn)行比較，即可完成圖像的版權(quán)認(rèn)證。具體認(rèn)證過程如下：

(1) 應(yīng)用置亂算法，把載體圖像I’進(jìn)行置亂，像素重新分布后得到置亂后的圖像S’。

(2) 對載體圖像S’進(jìn)行L級小波變換，獲得低頻域cA。把cA均分為m×m塊，得到Bij(i,j∈{1,2,…,M/(2L×m)})矩陣分塊。

(3) 將Bij進(jìn)行奇異值分解，把每一塊的最大奇異值經(jīng)過四舍五入和取最高位操作得到過渡矩陣Xij(i,j∈{1,2,…,M/(2L×m)})。

(4) 最后根據(jù)過渡矩陣X的奇偶性生成特征矩陣Y。即:

(5)

(5)應(yīng)用2.2節(jié)中銷毀后所剩算法生成零水印的公有圖M。即：

(6)

(6) 將公有圖M與認(rèn)證中心1提取的私有圖O進(jìn)行疊加，并與認(rèn)證中心2提取的零水印MO進(jìn)行比對，確定版權(quán)所有。

3.2篡改檢測算法

篡改定位是基于數(shù)字水印圖像認(rèn)證技術(shù)的一個突出優(yōu)點, 也是衡量脆弱水印算法性能的重要指標(biāo)之一[1]。篡改檢測應(yīng)用的是邊緣檢測和游程編碼的方式。游程編碼對于二值圖像非常有效[13]，因為游程編碼是連續(xù)精確的編碼，對任何一位的改變都十分敏感，任何對圖像邊緣的破壞都會使得密鑰K改變，所以篡改判斷比較精確。方法如下：

(1) 對攻擊后的圖像I’應(yīng)用2.3節(jié)中相同閾值和微分算子提取邊緣得到二值圖像E’。

(2) 按照2.3節(jié)中保存的密鑰K和游程編碼程序解壓得到二值圖像E。

(3) 然后對E’應(yīng)用游程編碼RLC進(jìn)行無損壓縮得到一維數(shù)值序列K’。

(4) 判斷K與K’是否相等，若不等，則圖像受到篡改。

(5) 將E與E’進(jìn)行比對，判斷圖像所受篡改的類型及位置。

4　實驗結(jié)果

4.1實驗參數(shù)

實驗環(huán)境為Matlab R2010b,實驗選取512×512的灰度圖像Lena為載體圖像。版權(quán)水印為32×32的“版權(quán)保護(hù)”圖像，小波選擇Haar小波基進(jìn)行二級小波變換，置亂方式為Arnold置亂算法，邊緣檢測采用canny算子，閾值為0.1。版權(quán)水印如圖3(a)所示，載體圖像如圖3(b)所示。

圖3　版權(quán)水印和載體圖像

4.2評價標(biāo)準(zhǔn)

數(shù)字水印魯棒性的衡量標(biāo)準(zhǔn)本文選擇歸一化相關(guān)系數(shù)(NC)來衡量：

(7)

篡改檢測實驗效果如圖4-圖6所示。

圖4　噪聲攻擊對比圖像

圖5　剪切攻擊對比圖像

圖6　涂改攻擊對比圖像

篡改檢測實驗效果圖展示了該算法對常見攻擊的檢測效果，從圖中可以看出，載體邊緣圖(圖4(a))在和經(jīng)受攻擊后的各個邊緣圖像對比后能清楚地判斷圖像遭受攻擊的類型和位置。噪聲攻擊(圖4(b-d))、剪切攻擊(圖5)和涂改攻擊(圖6)清楚地顯示了載體圖像(圖3(b))在遭受攻擊的類型和程度不同時呈現(xiàn)的檢測圖。根據(jù)篡改檢測實驗圖，可以判斷載體圖像在傳輸過程中所遭受的攻擊類型和位置，有利于后期對圖像完整性及其來源的判斷。實驗對照如表2、表3所示。

表2　篡改檢測實驗Lena密鑰(K)對照表

表3　Lena魯棒性實驗性能(NC) 對照表

續(xù)表3

注：-表示無此項

5　實驗結(jié)果分析

5.1篡改檢測分析

從圖4-圖6和表2可以很清楚地看出篡改檢測算法實現(xiàn)了比較精確的篡改鑒別及定位。圖4-圖6非常直觀地反映了載體圖像在接受各類攻擊后呈現(xiàn)的邊緣檢測圖，與原始邊緣檢測圖(圖4(a))進(jìn)行精確比對，可以很容易判斷載體圖像所受的攻擊類型及其位置，尤其是對旋轉(zhuǎn)攻擊、噪聲攻擊、剪切攻擊、區(qū)域攻擊、涂改攻擊的定位和判斷十分準(zhǔn)確。表2用密鑰K反映了載體圖像是否受到篡改，對于以上各類攻擊都具有精確的判斷。這利用了游程編碼是精確編碼的優(yōu)勢，邊緣圖像任意像素的修改都會影響游程編碼的密鑰K。表2在數(shù)據(jù)上應(yīng)用K的長度來進(jìn)行比對，這是由于K序列一般較長，一般通過長度就可以判斷，對于精確度要求很高的領(lǐng)域，可以直接進(jìn)行K的比對。

5.2魯棒性實驗分析

由表3可知，本文算法在噪聲攻擊、濾波攻擊、壓縮攻擊、左上角剪切攻擊方面具有十分強的魯棒性。這是因為奇異值分解和取最高位操作使得圖像能量更加集中，特征信息更具代表性。該算法應(yīng)用文獻(xiàn)[3，10]視覺密碼的優(yōu)點，采納文獻(xiàn)[7]零水印算法分圖組合方式，同時提出了不同于二者的特征矩陣和零水印生成方式，又采取了“三方分離”加密方式，這樣算法在魯棒性和安全性上都有較大提升。

在旋轉(zhuǎn)攻擊和中心剪切方面，本文算法綜合考慮文獻(xiàn)[3，7，10]的優(yōu)缺點，在旋轉(zhuǎn)攻擊較文獻(xiàn)[3，7]有較大提升，在中心剪切較文獻(xiàn)[3，10]有較大提升。綜合以上各類攻擊來看，本文算法在以上各類攻擊的綜合性能方面較文獻(xiàn)[3，7，10]都有較大提高。

5.3安全性分析

在版權(quán)保護(hù)領(lǐng)域，除了對版權(quán)進(jìn)行精確認(rèn)證外，還需要考慮到整個保護(hù)過程的安全性。在閱讀各類數(shù)字水印文獻(xiàn)的基礎(chǔ)上，針對各類文獻(xiàn)缺乏算法保護(hù)的問題，本文提出了將視覺密碼應(yīng)用于數(shù)字水印的方法。同時提出了實現(xiàn)水印認(rèn)證“三方分離”和零水印生成“版權(quán)水印銷毀”、“算法銷毀”的策略?！叭椒蛛x”充分利用視覺密碼可以將載體圖像分解的特點，分解后的私有圖和公有圖互不關(guān)聯(lián)，疊加后的零水印也與任何一個分圖不關(guān)聯(lián)，僅有在同時持有三者的情況下才可以完成版權(quán)認(rèn)證，這樣提高了認(rèn)證的安全性。“版權(quán)水印銷毀”和“算法銷毀”針對解決版權(quán)擁有者內(nèi)部或其他原因引起的算法泄露。通過將原先參與生成零水印的“版權(quán)水印”進(jìn)行銷毀來杜絕零水印的可復(fù)制性，以防盜版等侵權(quán)行為；“算法銷毀”利用了本文算法中公有圖生成僅僅依賴于特征矩陣的特點，將原先生成算法中私有圖的生成算法進(jìn)行銷毀，僅留下公有圖生成算法用于后期提取對比。因為私有圖算法在銷毀前已存至認(rèn)證中心1，這樣即便是公有圖算法泄露，私有圖算法已經(jīng)銷毀且私有圖僅在認(rèn)證中心1可得，盜密者無法完成版權(quán)認(rèn)證的復(fù)制，從而實現(xiàn)了算法和版權(quán)認(rèn)證的安全性。

6　結(jié)　語

在考慮傳統(tǒng)水印算法以嵌入方式加入水印和難以實現(xiàn)篡改檢測的基礎(chǔ)上，提出了一種將二者結(jié)合的基于視覺密碼和邊緣檢測的零水印算法。同時，對版權(quán)保護(hù)過程中算法和水印的安全性進(jìn)行了設(shè)計。這樣，零水印算法不但保證了原始數(shù)據(jù)的完整性、算法的安全性，還可以通過篡改檢測的方式進(jìn)行篡改的定位和鑒別。本文算法在醫(yī)學(xué)和偵查領(lǐng)域若是能得到應(yīng)用，將會有較好的實際效果。實驗表明，本文算法在魯棒性上具有十分好的綜合性能，在安全性和篡改檢測方面也有較好效果和判斷結(jié)果。

[1] 陳帆,王宏霞.定位像素篡改的安全脆弱水印算法[J].鐵道學(xué)報,2011,33(1):63-68.

[2] Rao R Y.Secure visual cryptography[J].International Journal of Engineering and Computer Science, 2013, 2(1):265-303.

[3] 曲長波,楊曉陶,袁鐸寧.平衡多小波視覺密碼零水印算法[J].計算機(jī)工程,2014,40(9):178-182.

[4] He H,Chen F,Tai H M,et al.Performance analysis of a block-neighborhood-based self-recovery fragile watermarking scheme[J].Information Forensics and Security,IEEE Transactions on,2012,7(1):185-196.

[5] 符浩軍,范承嘯,朱長青,等.基于游程長度的二值柵格地理數(shù)據(jù)水印算法[J].測繪與空間地理信息,2014,37(11):14-17.

[6] 薛勝男,陳秀宏.基于混沌加密和SVD 的數(shù)字圖像水印算法[J].計算機(jī)工程,2012,38(19) :107-110.

[7] Hsu C S,Tu S F.Digital watermarking scheme with visual cryptography[J].IMECS,Hong Kong,2008,1:659-662.

[8] 王國棟,劉粉林,汪萍,等.一種篡改檢測與篡改定位分離的圖像認(rèn)證方案 [J].計算機(jī)學(xué)報,2007,30(10):1880-1888.

[9] Han Y Y,He W C,Ji S,et al.A digital watermarking algorithm of color image based on Visual Cryptography and Discrete Cosine Transform[C]//P2P,Parallel,Grid,Cloud and Internet Computing (3PGCIC),2014 Ninth International Conference on.IEEE,2014:525-530.

[10] 曲長波,楊曉陶,袁鐸寧.小波域視覺密碼零水印算法[J].中國圖象圖形學(xué)報,2014,19(3):365-372.

[11] 趙春暉,劉巍.基于壓縮感知的交互支持雙水印算法[J].電子學(xué)報,2012,40(4):681-687.

[12] 葉天語.DWT—SVD 域全盲自嵌入魯棒量化水印算法[J].中國圖象圖形學(xué)報,2012,17(6):644-650.

[13] 張德豐.數(shù)字圖像處理 (MATLAB 版)[M].人民郵電出版社,2009.

[14] 王麗娜,郭遲，李鵬.信息隱藏技術(shù)實驗教程[M].武漢大學(xué)出版社,2004.

[15] Amirtharajan R,Sulthana S,Rayappan J B B.Seeing and believing is a threat:A visual cryptography schemes[J].Research Journal of Information Technology,2013,5(3):435-441.

[16] Surekha B,Swamy G N.Visual Secret Sharing Based Digital Image Watermarking[J].International Journal of Computer Science Issues (IJCSI),2012,9(3):312-317.

[17] Naor M,Shamir A.Visual cryptography[C]//Advances in Cryptology—EUROCRYPT’94.Springer Berlin Heidelberg,2006,950:1-12.

[18] 趙芳,欒曉明,孫越.數(shù)字圖像幾種邊緣檢測算子檢測比較分析[J].自動化技術(shù)與應(yīng)用,2009,28(3):68,72.

[19] 和紅杰.數(shù)字圖像安全認(rèn)證水印算法及其統(tǒng)計檢測性能分析[D].成都:西南交通大學(xué),2008.

ZERO WATERMARKING ALGORITHM BASED ON VISUAL CRYPTOGRAPHY AND EDGE DETECTION

Qu ChangboLi Dongdong

(College of Software,Liaoning Technical University,Huludao 125105，Liaoning,China)

In the field of copyright certification, traditional watermarking algorithm usually embeds the binary image into carrier image.Such algorithm has two shortcomings:the one is that the embedded watermarking changes carrier image, but in the fields such as medicine and investigation there have higher demand in original data integrity; the other is that once the image is suffered from tampering attack, it is hard to judge the type and location of attacks.To solve the above two problems, this paper proposes a new zero watermarking algorithm which is based on visual cryptography and edge detection.First, it operates scrambling and singular value decomposition on carrier image to extract the characteristic matrix.Then, according to the algorithm it generates public graph and private graph from characteristics matrix.Finally, it saves the private graph and zero watermark to certification centre.In addition, it applies the run-length coding to make lossless compression on image edge to form secret key, which is used for tamper detection.Experiment shows that the algorithm has very good robustness and security, especially in noise attack resistance.It also achieves excellent effect in terms of tamper detection.

Copyright authenticationVisual cryptographyCharacteristic matrixEdge detection

2015-04-27。曲長波，高工，主研領(lǐng)域：網(wǎng)絡(luò)工程，信息安全技術(shù)。李棟棟，碩士生。

TP309.2

A

10.3969/j.issn.1000-386x.2016.09.076