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

曲長波　李棟棟

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

?

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

曲長波李棟棟

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

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

版權認證視覺密碼特征矩陣邊緣檢測

0　引　言

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

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

1　算法理論基礎

1.1奇異值分解

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

(1)

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

1.2視覺密碼技術

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

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

圖1　視覺密碼效果圖

2　零水印及密鑰生成算法

2.1特征矩陣提取算法

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

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

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

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

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

(2)

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

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

表1　零水印算法生成圖示

即：

(3)

(4)

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

2.3密鑰生成算法

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

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

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

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

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

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

3　零水印認證及篡改檢測算法

3.1水印認證算法

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

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

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

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

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

(5)

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

(6)

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

3.2篡改檢測算法

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

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

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

(3) 然后對E’應用游程編碼RLC進行無損壓縮得到一維數值序列K’。

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

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

4　實驗結果

4.1實驗參數

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

圖3　版權水印和載體圖像

4.2評價標準

數字水印魯棒性的衡量標準本文選擇歸一化相關系數(NC)來衡量：

(7)

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

圖4　噪聲攻擊對比圖像

圖5　剪切攻擊對比圖像

圖6　涂改攻擊對比圖像

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

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

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

續表3

注：-表示無此項

5　實驗結果分析

5.1篡改檢測分析

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

5.2魯棒性實驗分析

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

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

5.3安全性分析

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

6　結　語

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

[1] 陳帆,王宏霞.定位像素篡改的安全脆弱水印算法[J].鐵道學報,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].計算機工程,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] 符浩軍,范承嘯,朱長青,等.基于游程長度的二值柵格地理數據水印算法[J].測繪與空間地理信息,2014,37(11):14-17.

[6] 薛勝男,陳秀宏.基于混沌加密和SVD 的數字圖像水印算法[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] 王國棟,劉粉林,汪萍,等.一種篡改檢測與篡改定位分離的圖像認證方案 [J].計算機學報,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].中國圖象圖形學報,2014,19(3):365-372.

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

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

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

[14] 王麗娜,郭遲，李鵬.信息隱藏技術實驗教程[M].武漢大學出版社,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] 趙芳,欒曉明,孫越.數字圖像幾種邊緣檢測算子檢測比較分析[J].自動化技術與應用,2009,28(3):68,72.

[19] 和紅杰.數字圖像安全認證水印算法及其統計檢測性能分析[D].成都:西南交通大學,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。曲長波，高工，主研領域：網絡工程，信息安全技術。李棟棟，碩士生。

TP309.2

A

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