一種基于動態(tài)分塊和差值直方圖平移的可逆水印算法

何文廣，王耀民

（廣東醫(yī)學院信息工程學院，湛江524023）

一種基于動態(tài)分塊和差值直方圖平移的可逆水印算法

何文廣，王耀民

（廣東醫(yī)學院信息工程學院，湛江524023）

基于圖像內容的自適應嵌入已成為可逆水印算法的研究熱點。探討圖像分塊對算法性能的影響，得出基于差值直方圖平移的可逆水印算法不存在最優(yōu)分塊尺寸這一結論，繼而提出一種動態(tài)分塊的差值計算方法。算法的基本思想是以多種分塊替代固定分塊，動態(tài)分塊時充分考慮圖像紋理復雜度，使得多種分塊的數(shù)量比例能自適應于嵌入級別，解決傳統(tǒng)差值計算方法中因較小分塊引起的水印容量有限問題，以及因較大分塊引起的分塊內像素相似性下降問題。實驗結果表明算法在嵌入容量和圖像質量方面均有較大優(yōu)勢，為提高差值擴展的效率提供一種新思路。

圖像紋理；動態(tài)分塊；直方圖平移；可逆水印

0　引言

圖像數(shù)字水印技術根據(jù)含水印圖像是否可恢復分為可逆和不可逆水印技術［1］。可逆水印又稱無損水印，它對信號的篡改非常敏感并且能在提取出水印后無損地恢復原始圖像，適用于圖像完整性認證。因此，可逆圖像水印技術可用于醫(yī)學、軍事和遙感等特殊領域。

現(xiàn)有可逆水印算法中空域算法可進一步劃分為差值擴展、誤差擴展和直方圖平移三大類。差值擴展（Difference Expansion，DE）的方法首先由Tian［1］提出，算法思想是通過擴展相鄰像素的差值實現(xiàn)水印嵌入。Alattar［2］隨后通過擴展相鄰的多個像素差值擴展了DE算法，進一步提升了水印嵌入率。誤差擴展（Prediction Error Expansion，PEE）在差值擴展的基礎上引入了誤差預測技術，像素灰度值與預測值的差值被用于嵌入水印。由于預測值能基于多個相鄰像素計算產(chǎn)生，因此誤差擴展能獲得相對更優(yōu)的數(shù)據(jù)冗余。誤差擴展的方法由Thodi［3］首先提出，并衍生出一系列的改進算法，包括Hu［4］等提出的定位圖壓縮方法，Luo［5］等提出的線性插值方法，Chen［6］等提出多重預測方法，以及Li［7］等提出的單遍多比特嵌入方法。熊［8］對多遍單比特和單遍多比特兩類嵌入方案進行了性能分析。

Ni［9］首先提出了基于直方圖平移（Histogram Shifting，HS）的水印嵌入方法，算法具有復雜度低和水印圖像質量高的特點，但水印容量受限于峰值出現(xiàn)的頻率，不能高效地處理直方圖相對平坦的這一類載體圖像。針對這一問題，Lee［10］首先提出使用差值直方圖替代灰度直方圖，從而獲得了更為陡峭的直方圖，提高水印容量的同時也減少了平移像素個數(shù)。利用相鄰像素構建差值的方法在Lin［11］、Li［12］和Zhao［13］中也得到使用。Lin［11］首先以相鄰像素的灰度差值構建差值圖，然后劃分差值圖，在每一分塊內實施直方圖平移。Li［12］和Zhao［13］均通過逐一掃描所有像素并兩兩相減產(chǎn)生差值，Zhao［13］在Li［12］的基礎上使用了多重直方圖平移的方法。Kim［14］使用降采樣的方法構造多幅差值子圖，然后針對每一幅子圖實施多重直方圖平移。Kim［14］算法本質上利用了分塊內像素的相似性產(chǎn)生數(shù)據(jù)冗余，針對這一點Luo［15］提出選取分塊內的中值組成新的參考子圖，這使得差值直方圖更為陡峭，進而改進了Kim［14］算法。Li［16］在Lee［10］的基礎上提出了二維差值直方圖平移的水印嵌入方案，將部分待平移差值轉換為可嵌入差值，提高了算法性能。

本文提出一種自適應于載體圖像的動態(tài)分塊方法，以進一步提高差值直方圖平移中可嵌入差值的數(shù)量。算法的基本原理是根據(jù)圖像紋理復雜度做出分塊預測，將載體圖像進行非固定式分塊，最后在分塊內實施差值直方圖平移實現(xiàn)水印嵌入。

1　差值直方圖平移

在Luo［15］算法中，載體圖像首先被劃分為若干尺寸為ΔU×ΔV、互不重疊的子塊；然后對子塊內所有像素按灰度值升序排序，如b1≤b2≤…≤bΔu×Δv，并選取中值作為參考像素bref。例如當ΔU=ΔV=4時，b8被選定為參考像素；最后，所有非參考像素減去參考像素產(chǎn)生差值：

1≤i≤ΔU×ΔV，i≠ref。在水印嵌入過程中，Luo［15］沿用了Kim［14］算法中多重直方圖平移的方法，整個過程可分為平移和擴展兩部分。首先，設置嵌入級別EL，落入?yún)^(qū)間（-∞，-EL）∪（EL，+∞）的差值不適用于嵌入水印，對其進行平移：

落入?yún)^(qū)間［-EL，EL］的差值通過差值擴展的方法嵌入一個水印比特w：

最后，計算出新的像素灰度：

1≤i≤ΔU×ΔV，i≠ref。由公式（3）、（4）可知，水印嵌入過程并沒有修改參考像素bref，因此在水印提取時需要傳輸?shù)妮o助信息只有分塊尺寸ΔU×ΔV及嵌入級別EL。

假設載體圖像大小為M×N，則劃分所得的子塊數(shù)量為?M/ΔU」×?N/ΔV」。由于每一分塊產(chǎn)生ΔU×ΔV-1個差值，因此差值總量為：

假設nin表示擴展差值數(shù)量，nout表示平移差值數(shù)量，則nd=nin+nout。顯然，分塊尺寸ΔU×ΔV決定了差值總量：尺寸越大，差值越多。另一方面，嵌入級別EL則決定了nin所占的比例：EL越大，nin所占比例越大。然而，當固定EL增大分塊尺寸時，分塊內像素之間的相似性往往相對變弱，容易導致nout的增長率超過nin的增長率，進而降低算法性能。同樣地，當固定分塊尺寸增大EL時，nout向nin轉換的比例將持續(xù)下降，而對載體圖像的擾動卻持續(xù)加劇。

綜上所述可知，基于固定分塊的差值直方圖平移方法不存在最優(yōu)的分塊尺寸。當容量需求較小時，適合選擇較小的分塊尺寸。而隨著容量需求的增長，必須逐步選擇更大的分塊尺寸。

2　本文算法

2.1動態(tài)分塊

假設原圖像為M×N的灰度圖像。首先，將原圖像劃分為若干8×8分塊，記為B8k，k=1，2，…，?M/8」×?N/ 8」。然后，對每一個8×8分塊進行以下處理：

圖1分塊劃分

當所有8×8分塊全部處理完畢后，載體圖像被劃分為四種尺寸不一的獨立嵌入子塊，記為BI，BII，BIII，BIV，如圖2所示。最后，針對每一個獨立的嵌入子塊實施差值直方圖平移實現(xiàn)水印嵌入。

圖2　獨立的嵌入子塊

表1以Lena圖為例對比了固定分塊與動態(tài)分塊兩種分塊方法對差值計算的影響。由表中數(shù)據(jù)可知，動態(tài)分塊的方法提供了近乎一致的水印嵌入容量，并同時較好地限制了平移差值的數(shù)量，對提高含水印圖像質量有重大意義。

表1　不同分塊方法對差值計算的影響

2.2水印嵌入

按上節(jié)所述對載體圖像進行動態(tài)分塊，得到一系列獨立嵌入子塊后，水印嵌入算法可描述為以下5個步驟。

（1）計算參考像素

將每一獨立嵌入子塊中的所有像素按灰度值升序排序，取中值作為參考像素。例如，BII子塊含有12個像素，則排序后排名第6的像素被選為參考像素，記為bref。

（2）子塊分類

分別用nL，nO，nR表示分塊內灰度值小于、等于和大于參考像素的像素個數(shù)，將分塊劃分為以下4類：

的引入能確保具有與參考像素相同灰度值的像素被修改后交替出現(xiàn)在參考像素的兩側，從而確保分塊內參考像素不變。

2.3水印提取和圖像恢復

在實施水印提取和圖像恢復之前，同樣需要參考2.1節(jié)對含水印圖像進行動態(tài)分塊。由于水印嵌入算法能維持獨立嵌入子塊的參考像素不變，因此在接下來的動態(tài)分塊中只需將分塊預測的條件改為“差值全落入?yún)^(qū)間［-2×EL-1，2×EL+1］”，即可得到與2.2節(jié)完全一致的圖像分塊。得到一系列獨立嵌入子塊后，水印提取和圖像恢復算法可描述為以下4個步驟。

（1）計算參考像素

將每一獨立嵌入子塊中的所有像素按灰度值升序排序，取中值作為參考像素。

（2）構建差值直方圖

計算每一個分塊Bk內所有非參考像素與參考像素的灰度差值，然后組成差值直方圖。

2.4溢出處理

對于灰度級為8比特的灰度圖像，像素灰度范圍為［0，255］。本文算法對灰度的最大修改值為EL+1，因此灰度值在［0，EL］或［255-EL，255］之內的像素在嵌入水印后可能產(chǎn)生溢出。本文采用了直方圖收縮的方法，使用「log2（EL+2）?長度的比特序列區(qū)分灰度值在［0，EL+1］或［255-EL-1，255］范圍內的像素。最后將上述比特序列做無損壓縮后嵌入到載體圖像中。

3　實驗結果與分析

為了分析和評估算法性能，本節(jié)將本文算法與若干水印嵌入容量較大的可逆水印算法進行比較，主要評價各算法在相同水印嵌入量下的含水印圖像質量。實驗中使用實際嵌入的水印位數(shù)（bits）或每像素嵌入比特率（bits per pixel，bpp）來描述算法水印容量，使用峰值信噪比（PSNR）來描述含水印圖像質量，其計算公式為：

實驗測試圖像來自USC-SIPI標準圖像庫，圖像大?。ㄏ袼貍€數(shù)）均為512×512，灰度級數(shù)為8 bit，如圖3所示。測試圖像紋理特征各異，其中Peppers平滑區(qū)域較多，Lena和Airplane次之，Barbara的紋理相對復雜。各算法嵌入的水印信息約定為相同的偽隨機序列值，由MATLAB隨機函數(shù)產(chǎn)生。

圖3　實驗測試圖像

圖4　不同測試圖像的性能比較

首先采用本文算法對所有測試圖像實施水印嵌入。圖4對各測試圖像在水印嵌入容量達0.9bpp之前的PSNR值進行了對比。對比的結果顯然符合預期，紋理相對復雜的Barbara不僅在相同嵌入級別時獲得較小的水印容量，并且在相同水印嵌入容量時PSNR值相對較小。

圖5將Luo［15］算法在4種分塊尺寸下的實驗數(shù)據(jù)與本文算法所得數(shù)據(jù)分別進行了比較。通過與本文算法的比較，不難發(fā)現(xiàn)Luo［15］算法在2×2和3×3分塊時水印容量增長停滯問題較為凸顯。當嵌入級別較小時，兩類算法表現(xiàn)出近似的性能。但隨著嵌入級別的提升，Luo算法逐漸出現(xiàn)水印容量增長的瓶頸。Luo算法4×4分塊與本文算法的性能差別表現(xiàn)在前期，凸顯的是分塊內像素相似性減弱的問題。這一點在5×5分塊的性能表現(xiàn)上得到進一步印證。

圖5　基于Lena圖像的性能比較

基于測試圖像Airplane和Barbara的性能比較出現(xiàn)類似的結果，分別如圖6、圖7所示。由此可見，動態(tài)分塊的方法能依據(jù)不同的嵌入級別高效地完成圖像分塊，分塊結果能同時維持水印容量增長和分塊內像素的相似性。另外，通過分別比較圖7（a）和圖8（a），以及圖7（b）和圖8（b），不難發(fā)現(xiàn)隨著圖像紋理復雜度的增加，盡管本文算法仍能保持水印容量增長方面的優(yōu)勢，但PSNR值方面的優(yōu)勢卻在逐步萎縮，這說明圖像紋理復雜度對本文算法中分塊預測的效率有直接影響。

圖6　基于Airplane圖像的性能比較

圖7　基于Barbara圖像的性能比較

Peppers圖像相對平滑，實驗結果表明本文算法性能優(yōu)于各種固定分塊方法，如圖8所示。

4　結語

圖像分塊在可逆水印算法中具有較大研究意義，分塊的方法能影響各類算法的性能。本文選擇差值直方圖平移作為切入點，得出不存在最優(yōu)分塊尺寸這一結論，繼而提出一種動態(tài)分塊的差值計算方法。實驗結果表明，基于圖像紋理復雜度和嵌入級別能實現(xiàn)有指導性的圖像分塊，以多種分塊替代固定分塊的動態(tài)分塊方法確實能解決了傳統(tǒng)差值計算方法中因較小分塊引起的水印容量有限問題，以及因較大分塊引起的分塊內像素相似性下降問題，最終在提升水印容量的同時較好地維持了水印圖像質量。

圖8　基于Peppers圖像的性能比較

［1］J.Tian.Reversible Data Embedding Using a Difference Expansion［J］.IEEE Transactions on Circuits and Systems for Video Technology，2003，13（8）：890-896.

［2］A.M.Alattar.Reversible Watermark Using the Difference Expansion of a Generalized Integer Transform［J］.IEEE Transactions on Image Processing，2004，13（8）：1147-1156.

［3］Thodi D M，Rodriguez J J.Expansion Embedding Techniques for Reversible Watermarking［J］.IEEE Transactions on Image Processing，2007，16（3）：721-730.

［4］Y.Hu，H.K.Lee，J.Li.DE-Based Reversible Data Hiding with Improved Overflow Location Map［J］.IEEE Trans on Circuits and Systems for Video Technology，2009，19（2）：250-260.

［5］L.Luo，Z.Chen，M.Chen，X.Zeng，Z.Xiong，Reversible Image Watermarking Using Interpolation Technique，IEEE Trans.Inf. Forensics Secur，2010，5（1）：187-193.

［6］Chen X Y，Sun X M，et al.Reversible Watermarking Method Based on Asymmetric-Histogram Shifting of Prediction Errors［J］.Journal of Systems and Software，2013，86（10）：2620-2626.

［7］X.Li，B.Yang，T.Zeng.Effcient Reversible Watermarking Based on Adaptive Prediction-Error Expansion and Pixel Selection［J］. IEEE Transactions on Image Processing，2011，20（12）：3524-3533.

［8］熊祥光.基于直方圖平移的多遍與多比特嵌入性能比較［J］.計算機應用研究，2015，32（8）：2437-2440，2446.

［9］Z.Ni，Y.-Q.Shi，N.Ansari，W.Su.Reversible Data Hiding［J］.IEEE Trans on Circuits and Systems for Video Technology，2006，16（3）：354-362.

［10］S.K.Lee，Y.H.Suh，Y.S.Ho.Reversible Image Authentication Based on Watermarking［C］.In Proc.IEEE ICME 2006：1321-1324.

［11］Lin C C，Tai W L，Chang C C.Multilevel Reversible Data Hiding Based on Histogram Modification of Difference Images［J］.Pattern Recognition，2008（41）：3582-3591.

［12］Y.C.Li，C.M.Yeh，C.C.Chang.DataHidingBasedontheSimilarityBetween NeighboringPixelswithReversibility［J］. Digital Signal Processing，2010，20（4）：1116-1128.

［13］Z.-Z.Zhao，H.Luo，Z.-M.Lu，J.-S Pan.Reversible Data Hiding Based on Multilevel Histogram Modification and SequentialRecovery［J］.Journal of Electronics and Communications，2011，65：814-826.

［14］Kim K，Lee M，et al.Reversible Data Hiding Exploiting Spatial Correlation Between Sub-Sampled Images［J］.Pattern Recognition，2009（42）：3083-3096.

［15］Luo H，Yu F X，et al.Reversible Data Hiding Based on Block Median Preservation［J］.Information Sciences，2011，181：308-328.

［16］X.Li，W.Zhang，X.Gui，and B.Yang.A Novel Reversible Data Hiding Scheme Based on Two-Dimensional Difference-Histogram Modication［J］.IEEE Transactions on Information Forensics and Security，2013，8（7）：1091-1100.

A Reversible Watermarking Scheme Based on Dynamic Partition and Difference Histogram Shifting

HE Wen-guang，WANG Yao-min
（School of Information Engineering，Guangdong Medical University，Zhanjiang 524023）

Adaptive embedding based on image content has become a hot research topic of reversible watermarking.Discusses the impact of image partition on the performance of the scheme，and the conclusion is that there is no optimal block size for difference histogram shifting based reversible watermarking schemes.After that proposes a new method for difference calculation based on dynamic partition.The basic idea of dynamic partition is to replace the fixed block size with multiple block sizes and the image texture complexity can be taken into account to achieve effective image partition.The numbers of several size-variable blocks are adaptive to the embedding level，which helps to solve the problem of the limited amount of embedding capacity due to small block and the problem of low similarity of pixels within large block existed in traditional difference calculation.The experimental results verify that the proposed scheme not only perform outperformance about embedding capacity and watermarked image quality，but also provides a new way for improving the efficiency of difference expansion.

Image Texture；Dynamic Partition；Histogram Shifting；Reversible Watermarking

1007-1423（2016）23-0057-07DOI：10.3969/j.issn.1007-1423.2016.23.015

2016-05-10

2016-08-10

國家自然科學基金（No.81201763）、湛江市科技攻關項目（No.2013B01181）

何文廣，講師，碩士，研究方向為信息隱藏、圖像處理王耀民，講師，碩士，研究方向為計算機安全