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

劉文星，陳偉，劉淵

?

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

劉文星，陳偉，劉淵

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

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

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

1 引言

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

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

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

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

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

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

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

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

簡(jiǎn)記為

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

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

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

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

誤差平方差可表示為

計(jì)算平方差最小情況下的參數(shù)、、，即對(duì)上式的每個(gè)參數(shù)求偏導(dǎo)。

化簡(jiǎn)并展開

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

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

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

2.2 圖像重構(gòu)

(a) 原始圖像

(b) 四叉樹剖分

圖3 圖像的四叉樹剖分

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

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

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

3.1 算法設(shè)計(jì)思路

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

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

圖4 細(xì)分子塊的種類

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

1) 水印嵌入算法

①對(duì)二值水印圖像作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)

④將每個(gè)分塊進(jìn)行DCT逆變換，得到含水印圖像。

2) 水印提取算法

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

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

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

水印 = 0

else 水印 = 1

對(duì)所得水印圖像做次逆Arnold變換，恢復(fù)水印圖像_。

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

4 實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

[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] 戴瓊海. 多維信號(hào)處理: 快速變換、稀疏表達(dá)與低秩分析[M]. 北京: 清華大學(xué)出版社, 2016.

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

[3] 焦李成，譚山. 圖像的多尺度幾何分析: 回顧和展望[J]. 電子學(xué)報(bào), 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] 陳偉，陳亞楠，劉淵. 復(fù)數(shù)基下的數(shù)字媒體表達(dá)及信息隱藏[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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]. 計(jì)算機(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ù)及應(yīng)用[M]. 北京: 科學(xué)出版社, 2004.

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

[14] 王志紅, 黃惠芬, 常玉紅. 基于SVD分解和Hadamard變換的圖像半脆弱水印技術(shù)[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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]. 計(jì)算機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61602213）；國(guó)家科技支撐計(jì)劃基金資助項(xiàng)目（No.2015BAH54F00）

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

劉文星（1994 -），男，重慶人，江南大學(xué)本科生，主要研究方向?yàn)閳D像處理。

陳偉（1986 -），男，江蘇寶應(yīng)人，博士，江南大學(xué)副教授，主要研究方向?yàn)閳D像處理。

劉淵（1967-），男，江蘇無錫人，江南大學(xué)教授，主要研究方向?yàn)榫W(wǎng)絡(luò)安全。