圖像四叉樹剖分下的自適應數(shù)字水印算法

劉文星，陳偉，劉淵

?

圖像四叉樹剖分下的自適應數(shù)字水印算法

劉文星，陳偉，劉淵

（江南大學數(shù)字媒體學院，江蘇 無錫 214122）

提出了一種圖像四叉樹矩形剖分下的自適應數(shù)字水印算法。通過對原始圖像在多個尺度上進行最小二乘多項式逼近，將圖像進行非均勻剖分，并以四叉樹結(jié)構(gòu)的形式進行表達。該四叉樹結(jié)構(gòu)既實現(xiàn)了對原始圖像的逼近，同時攜帶了圖像的紋理結(jié)構(gòu)信息。通過統(tǒng)計各子區(qū)域上的剖分網(wǎng)格數(shù)目，計算不同區(qū)域上水印嵌入的強度，從而實現(xiàn)自適應數(shù)字水印方案。實驗結(jié)果表明，該算法具有良好的透明性和頑健性。

圖像剖分；四叉樹；最小二乘；水印

1 引言

隨著當代信息技術(shù)的蓬勃發(fā)展，傳統(tǒng)信號處理的研究內(nèi)容及應用范圍得到極大擴張。作為一類典型的二維信號，數(shù)字圖像處理涵蓋了去噪、壓縮、重構(gòu)、超分辨率、特征提取、水印等多個領域。與一維信號相比，二維圖像的特征更為豐富，也更為復雜。因此，如何高效地表達數(shù)字圖像是上述諸多應用的基礎[1]。

為了克服小波方法在捕獲圖像奇異特征方面的不足，來自多個領域的多位學者在小波變換理論的基礎上發(fā)展了多尺度幾何分析理論[3]，主要包括楔波[4]（wedgelet）、曲線波[5]（curvelet）、脊波[6]（ridgelet）、條帶波[7]（bandelet）、剪切波[8]（shearlet）、輪廓波[9]（contourlet）等。這些不同方法的理論是相似的，差別在于所選擇的基函數(shù)形態(tài)不同。與小波變換相比，多尺度幾何變換改進了圖像在奇異處的表達性能，其應用范圍也囊括了去噪、壓縮、復原、安全等圖像處理的多個領域。但是，實際圖像的類型十分復雜，不僅導致各種多尺度分析工具的計算復雜度很高，甚至會出現(xiàn)逼近效果不如傳統(tǒng)小波變換的情形。

作為圖像信息隱藏[10~12]的重要分支，數(shù)字水印技術(shù)得到廣泛的研究與發(fā)展[13,14]。針對多尺度幾何變換計算復雜度高、適用圖像類型單一的特點，本文研究圖像四叉樹矩形剖分下的數(shù)字水印算法。圖像四叉樹結(jié)構(gòu)分解作為一種高效的圖像多尺度逼近方法，在圖像處理的多個領域取得了成功的應用。在通常的數(shù)字水印嵌入算法中，首先圖像經(jīng)過均勻剖分（一般為8×8），對所有分塊逐個進行頻域變換（DCT、DWT等）后，再對每組頻域系數(shù)施加乘性或加性法則完成水印的嵌入。由于對圖像各區(qū)域不加區(qū)分地對待，即不論某區(qū)域的紋理復雜程度如何，均以相同的強度進行水印的嵌入，從而在水印圖像質(zhì)量與算法頑健性之間很難取得平衡。

另一方面，從人類視覺系統(tǒng)（HVS, human visual system）的特性出發(fā)，它具有以下特點：1)對圖像邊緣位置信息敏感，而對邊緣的灰度誤差不敏感；2) 視覺掩蓋效應，受背景亮度、紋理復雜度及信號頻率的影響，在保證不被人眼察覺的前提下，圖像不同局部特征的區(qū)域允許被改變的強度不同[15]。

本文從圖像四叉樹剖分算法出發(fā)，通過圖像剖分結(jié)果的非均勻特性，利用人類視覺系統(tǒng)特征，充分考慮圖像不同區(qū)域的灰度特性，根據(jù)圖像不同區(qū)域的紋理復雜程度，設計自適應水印嵌入算法，提高水印圖像質(zhì)量和算法的頑健性。

圖1 圖像區(qū)域的自相似剖分及其四叉樹表達

2 數(shù)字圖像四叉樹剖分與重構(gòu)

2.1 數(shù)字圖像四叉樹剖分

簡記為

如圖1(b)所示，四叉樹的根節(jié)點代表原始圖像，不同的層次代表遞歸剖分步數(shù)，葉子節(jié)點為最終剖分結(jié)果，每個剖分子區(qū)域（即每個葉節(jié)點）用一個幾何面片（本文選取二元一次多項式）進行逼近。因此，只需在四叉樹葉子節(jié)點處存儲面片信息即可。

最小二乘法是一種數(shù)學的優(yōu)化方法，通過最小化誤差平方和擬合數(shù)據(jù)最佳的函數(shù)匹配，利用最小二乘法匹配的函數(shù)可以簡便地求出未知的數(shù)據(jù)，并使所求的數(shù)據(jù)與原始數(shù)據(jù)的平方差最小。

本文是對圖像數(shù)據(jù)進行處理，所以使用的是二維情形下的最小二乘法。

線性二元函數(shù)表達式如下。

誤差平方差可表示為

計算平方差最小情況下的參數(shù)、、，即對上式的每個參數(shù)求偏導。

化簡并展開

將上述每個部分用1,2,…,9表示，將方程組化為矩陣形式

圖像的非均勻四叉樹剖分流程如圖2所示。

圖2 圖像的非均勻四叉樹剖分流程

2.2 圖像重構(gòu)

(a) 原始圖像

(b) 四叉樹剖分

圖3 圖像的四叉樹剖分

對于給定的圖像，誤差閾值設定越小，四叉樹剖分網(wǎng)格越精細，葉子節(jié)點越多，則重構(gòu)圖像質(zhì)量越高，但時間花費越高。表1列出了對同一張Lena圖像進行不同精度剖分的實驗結(jié)果。

從實驗結(jié)果可以看出，圖像剖分結(jié)果與預期一致。對于同一張圖像，隨著誤差閾值的減小，剖分網(wǎng)格不斷細化，新增加的精細網(wǎng)格主要集中在圖像紋理細節(jié)豐富區(qū)域，而灰度平緩區(qū)域的網(wǎng)格剖分幾乎保持不變。這一現(xiàn)象本質(zhì)上與圖像的多分辨分析及多尺度變換一致，這也正是下文中設計水印算法的依據(jù)。

3 圖像四叉樹剖分下的數(shù)字水印算法

3.1 算法設計思路

如前文所述，在通常的頻域水印嵌入算法中，將圖像均勻地剖分為8×8分塊，并未考慮圖像紋理在區(qū)域分布上的非均勻性。本文首先對圖像進行非均勻四叉樹剖分，然后計算每個8×8分塊中細分子塊的數(shù)目。根據(jù)剖分算法可知，在圖像紋理復雜的區(qū)域，剖分網(wǎng)格越精細，即細分子塊越多，反之亦然。因此，用細分子塊數(shù)目衡量該區(qū)域的紋理復雜程度。

本文算法設置最小剖分子塊尺寸為2×2。因此，在任意8×8分塊中，所含子塊的數(shù)目只有6種：1、4、7、10、13和16，如圖4所示。

圖4 細分子塊的種類

3.2 數(shù)字水印非均勻嵌入算法

1) 水印嵌入算法

①對二值水印圖像作Arnold置亂操作，得到經(jīng)次置亂的水印圖像img_mark，其中作為密鑰。

其中，參數(shù)代表水印嵌入靈活度，取值范圍為[0.01, 0.05]。

if_mark= 0, then= 1

else= ?1

_dct[0][0]=_dct[0][0]×(1+sI)

④將每個分塊進行DCT逆變換，得到含水印圖像。

2) 水印提取算法

①對含水印圖像，按8×8分塊做DCT變換，并提取出每個分塊的DC分量_dct[0][0]。

②對原圖做相同操作，記為_dct[0][0]。

③ if_dct[0][0]?_dct[0][0] > 0

水印 = 0

else 水印 = 1

對所得水印圖像做次逆Arnold變換，恢復水印圖像_。

表1 不同誤差閾值下的圖像剖分結(jié)果

4 實驗

為了比較所提取水印圖像的質(zhì)量，計算歸一化相關度（NC, normalized correlation）來度量提取水印與原始水印的相似程度，以此評判算法的頑健性。計算公式如下。

本文對不同嵌入強度下多種攻擊（包括無攻擊、椒鹽噪聲、剪切、不同壓縮率等）進行了測試。因篇幅所限，這里僅顯示對Lena圖的實驗結(jié)果，包括被攻擊水印圖像的形態(tài)及其、水印嵌入強度、提取的水印圖像的形態(tài)及誤差等，如表2~表6所示。嵌入強度表征了自適應水印嵌入的靈活程度，實驗結(jié)果表明，通過適當提高嵌入強度，本文算法對以上各種攻擊的頑健性均有所提高，特別是剪切攻擊和壓縮攻擊，效果更為明顯。

表2 無攻擊情況下測試結(jié)果

表3 椒鹽噪聲攻擊情況下測試結(jié)果

表4 剪切攻擊情況下測試結(jié)果

表5 壓縮攻擊（壓縮率0.4）情況下測試結(jié)果

表6 壓縮攻擊（壓縮率0.6）情況下測試結(jié)果

表7 不同強度受JPEG壓縮的水印效果（Q=40）

以上實驗中，嵌入強度的范圍在（0.01, 0.06）較為合適，通過大量實驗，提高嵌入強度對各種攻擊的頑健性均有提高，其中最為明顯的是剪切攻擊，其次是壓縮攻擊，椒鹽噪聲攻擊的頑健性幾乎沒有提高。同時也能發(fā)現(xiàn)強度的提高會降低加水印圖片的質(zhì)量，靈活度提升到0.04以上時，幾乎各種攻擊的頑健性的提升幾乎為零，甚至會出現(xiàn)=0.03與=0．02剪切攻擊頑健性下降的情況，所以為了保證嵌水印圖像的質(zhì)量即較高，將設置為合適的值即可，經(jīng)過實驗，通常設置=0.02。

5 傳統(tǒng)均勻嵌入水印的方法比較

常用的DCT域上將水印信息嵌入DC系數(shù)的方法雖然在抗壓縮方面的頑健性較好，但改變DC分量對宿主圖像的影響很大，會出現(xiàn)方塊效應。

6 結(jié)束語

針對傳統(tǒng)圖像多尺度幾何變換計算復雜度高、適用圖像類型單一等缺點，本文基于圖像的四叉樹矩形剖分，將圖像表達為一系列幾何面片，并根據(jù)逼近結(jié)果計算圖像不同區(qū)域的紋理復雜程度，設計出自適應的非均勻水印嵌入強度算法。實驗結(jié)果表明，本文算法在保證載體圖像質(zhì)量的條件下，對多種攻擊（特別是噪聲攻擊、壓縮攻擊等）的頑健性均有所提高。

[1] YANG J, PENG Y, XU W, et al. Ways to sparse representation: a overview[J]. Science in China Series F: Information Sciences, 2009, 52(4): 547-722.

[2] 戴瓊海. 多維信號處理: 快速變換、稀疏表達與低秩分析[M]. 北京: 清華大學出版社, 2016.

DAI Q H. Multidimensional signal processing: fast transform, sparse representation, and low rank analysis[M]. Beijing: TsinghuaUniversityPress, 2016.

[3] 焦李成，譚山. 圖像的多尺度幾何分析: 回顧和展望[J]. 電子學報, 2003, 31(12A):1975-1981.

JIAO L C, TAN S. Development and prospect of image multiscale geometric analysis[J]. Acta Electronica Sinica, 2003, 31(12A): 1975-1981.

[4] CANDèS E J. Ridgelets: theory and applications[D]. Stanford: Department and Statistics, Stanford University, 1998.

[5] CANDèS E J, DONOHO D L. Curvelets and curvilinear integrals[J]. Annals of Smfisfies, 1999, 27(3):859-897.

[6] DONOHO D L. Wedgelets: nearly minimax estimation of edges[J]. Journal of Approximation Theory, 2001, 113(1):59-90.

[7] PENNEC E L, MALLAT S. Sparse geometric image representation with bandelets[J]. IEEE Transactions on Image Processing, 2005, 14(1): 1665-1677.

[8] EASLEY G, LABATE D, LIM W Q. Sparse directional image representation using the discrete shearlet transform[J]. Applied and Computational Harmonic Analysis, 2008, 25 (1): 25-46.

[9] DO M N, VETTERLI M. The contourlet transform: an efficient directional multiresolution image representation[J]. IEEE Transactions on Image Processing, 2005, 14(12): 2091-2106.

[10] 陳偉，陳亞楠，劉淵. 復數(shù)基下的數(shù)字媒體表達及信息隱藏[J]. 網(wǎng)絡與信息安全學報, 2016, 2(12): 20-26.

CHEN W, CHEN Y N, LIU Y. Digital media representation under complex number base and its application on information hiding[J]. Chinese Journal of Network and Information Security, 2016, 2(12): 20-26.

[11] HENGARTNER U. Hiding location information from location-based services[C]//The International Conference on Mobile Data Management, Mannheim. 2007:268-272.

[12] 余建德，宋瑞霞，齊東旭. 基于數(shù)字圖像三角形剖分的信息偽裝算法[J]. 計算機研究與發(fā)展, 2009,46(9):1432-1437.

YU J D, SONG R X, QI D X. A Scheme for steganography based on triangular partition of digital images[J]. Journal of Computer Research and Development, 2009,46(9):1432-1437.

[13] 孫圣和，陸哲明. 數(shù)字水印技術(shù)及應用[M]. 北京: 科學出版社, 2004.

SUN S H, LU Z M. Digital watermarking technology and application[M]. Beijing: Science Press, 2004.

[14] 王志紅, 黃惠芬, 常玉紅. 基于SVD分解和Hadamard變換的圖像半脆弱水印技術(shù)[J]. 網(wǎng)絡與信息安全學報, 2017,3(5): 26-31.

WANG Z H, HUANG H F, CHANG Y H. Semi-fragile watermarking technology based on SVD decomposition and Hadamard transform[J]. Chinese Journal of Network and Information Security, 2017, 3(5): 26-31.

[15] 王晶，王向陽. 基于人類視覺系統(tǒng)的數(shù)字圖像水印方法[J]. 計算機工程, 2011,37(13):107-108,112.

WANG J, WANG X Y. Digital image watermark method based on human visual system[J]. Computer Engineering, 2011, 37(13): 107-108,112.

Adaptive digital watermarking algorithm under image quad-tree partition

LIU Wen-xing, CHEN Wei, LIU Yuan

(School of Digital Media, Jiangnan University, Wuxi 214122, China)

An adaptive digital watermarking algorithm based on image quad-tree partition was proposed. The original image was approximated by various least square polynomial patches at multiple scales and was organized by a quad-tree structure. At the same time, this representation also reflected the texture information of image. By calculating the watermark embedding intensity in different regions, an adaptive digital watermarking scheme based on the number of the refined meshes in each region was realized. The experiment results show that this algorithm has the good imperceptibility and robustness.

image partition, quad-tree, least square, watermarking

TP393

A

10.11959/j.issn.2096-109x.2017.00219

2017-10-14；

2017-12-03。

陳偉，wchen_jdsm@163.com

國家自然科學基金資助項目（No.61602213）；國家科技支撐計劃基金資助項目（No.2015BAH54F00）

The National Natural Science Foundation of China (No.61602213), The National Science and Technology Support Program (No.2015BAH54F00)

劉文星（1994 -），男，重慶人，江南大學本科生，主要研究方向為圖像處理。

陳偉（1986 -），男，江蘇寶應人，博士，江南大學副教授，主要研究方向為圖像處理。

劉淵（1967-），男，江蘇無錫人，江南大學教授，主要研究方向為網(wǎng)絡安全。