基于像素值排序與塊再分的可逆數(shù)據(jù)隱藏算法

任方，楊益萍，薛斐元

（1.西安郵電大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，西安 710121；2.西安郵電大學(xué) 無線網(wǎng)絡(luò)安全技術(shù)國家工程實驗室，西安 710121）

0 概述

可逆數(shù)據(jù)隱藏是一種只需要對載體圖像的像素進行輕微修改，并將數(shù)據(jù)隱藏在載體圖像中的技術(shù)。該技術(shù)從被嵌入數(shù)據(jù)的載體圖像中無損地提取數(shù)據(jù)，同時完全恢復(fù)出原載體圖像［1-2］。可逆數(shù)據(jù)隱藏技術(shù)在醫(yī)學(xué)圖像［3-5］、軍事圖像、法律取證等領(lǐng)域中傳輸和使用數(shù)據(jù)時，能夠確保數(shù)據(jù)不失真［6-8］。

早期的可逆數(shù)據(jù)隱藏技術(shù)［9-11］通過壓縮載體圖像的一個位平面來創(chuàng)造空間，并進行數(shù)據(jù)嵌入，但其可逆性高度依賴于壓縮算法的性能。文獻(xiàn)［12］提出DE 算法，通過對載體圖像進行整數(shù)小波變換，同時計算并擴展差值，以嵌入可逆數(shù)據(jù)。為充分利用自然圖像的冗余空間，預(yù)測誤差擴展（Prediction Error Expansion，PEE）［13］采用預(yù)測誤差代替DE 算法中的差值，受到許多研究人員的關(guān)注［14-16］。

文獻(xiàn)［17］結(jié)合PEE 提出像素值排序（Pixel Value Ordering，PVO）算法。該算法將載體圖像分成非重疊同等大小的塊，并對塊內(nèi)的像素進行排序，通過計算預(yù)測誤差為塊中最大（小）值與次大（小）值的差值，以修改最大（小）值嵌入數(shù)據(jù)。在PVO 算法中，預(yù)測誤差等于1 的圖像塊被用于嵌入數(shù)據(jù)，預(yù)測誤差等于0 的圖像塊未被利用。文獻(xiàn)［18］提出改進的PVO（IPVO）算法，根據(jù)最大（小）值和次大（小）值的空間位置預(yù)測誤差，誤差等于0 和誤差等于1 的圖像塊都被用于嵌入數(shù)據(jù)，以提高PVO 的嵌入容量。文獻(xiàn)［19］提出PVO-K，同時修改k個最大（小）值以嵌入1 bit數(shù)據(jù)，當(dāng)k=1時，PVO-K退化為PVO。文獻(xiàn)［20］提出PPVO，打破了PVO 中分塊的限制，將每個像素作為一個嵌入單元。文獻(xiàn)［21］將PVO 生成的預(yù)測誤差兩兩分為一組，采用2D 的方式成對修改誤差以嵌入數(shù)據(jù)。研究人員利用可逆約束對像素進行動態(tài)預(yù)測，從而提升PVO 的嵌入容量［22］。為獲得更大的嵌入容量，文獻(xiàn)［23］將圖像塊的復(fù)雜度分為m個級別，根據(jù)不同級別動態(tài)地修改塊內(nèi)像素的個數(shù)。

本文提出基于像素值排序的塊再分算法。構(gòu)建12種分塊模式將1 個圖像塊分為2 個子塊，對每個子塊采用不同的掃描順序及嵌入策略，以充分利用圖像塊中每個像素之間的相關(guān)性。此外，設(shè)計一種局部復(fù)雜度的計算方式，當(dāng)嵌入數(shù)據(jù)時，只處理復(fù)雜度小于閾值的圖像塊，提高嵌入數(shù)據(jù)后圖像的視覺質(zhì)量。

1 基于像素值排序的可逆數(shù)據(jù)隱藏算法

PVO 算法［17］通過對圖像進行分塊，并將塊內(nèi)的n個像素按照升序排列，使得xσ(1)≤xσ(2)≤…≤xσ(n)，在此基礎(chǔ)上，計算預(yù)測誤差emax=xσ(n)-xσ(n-1)。PVO 和IPVO 算法的預(yù)測誤差直方圖如圖1 所示。

圖1 PVO 和IPVO 算法的預(yù)測誤差直方圖Fig.1 Prediction error histogram of PVO and IPVO algorithms

POV 預(yù)測誤差emax的直方圖誤差范圍在(0，+∞)，峰值點為1。PVO 算法通過emax=1 來嵌入數(shù)據(jù)。

文獻(xiàn)［18］提出改進的像素值排序（IPVO）算法，其目的是利用在PVO 算法中被放棄的最大（小）值與次大（小）值相等的圖像塊來嵌入數(shù)據(jù)。IPVO 計算得到的預(yù)測誤差dmax=xu-xv，其中u=min(σ(n)，σ(n-1))，v=max(σ(n)，σ(n-1))。IPOV 預(yù)測的誤差直方圖如圖1（b）所示，預(yù)測誤差dmax的直方圖誤差范圍在(-∞，+∞)，峰值點為0。IPVO 利用dmax=0和dmax=1 來嵌入數(shù)據(jù)，大幅增大了PVO 的嵌入容量。

IPVO 在3×3 圖像塊最大值上嵌入和提取數(shù)據(jù)的過程如圖2 所示。

圖2 IPVO 算法在最大像素上嵌入和提取數(shù)據(jù)的過程Fig.2 The process embedding and extraction data of IPVO algorithm on maximum pixel

2 本文算法

2.1 分塊模式

分塊模式將原始圖像分成3×3 不重疊的塊，將每一個塊內(nèi)包含的9個像素劃分為2個像素集，即像素集A和像素集B。像素集A 包含4 個像素，采用次大像素值預(yù)測最大像素值和次小像素值的方法。像素集B 包含當(dāng)前塊內(nèi)剩下的5 個像素，采用中值像素分別預(yù)測其余4 個像素的方法。這樣的劃分方式共有種，其目的是為了更充分利用像素之間的相關(guān)性。由于像素之間的相關(guān)性越高，產(chǎn)生的預(yù)測誤差直方圖分布越集中，因此可被用于嵌入數(shù)據(jù)的像素就越多。本文考慮到像素與像素之間的距離越近，其相關(guān)性越好，因此，像素集的劃分應(yīng)盡可能地讓像素集內(nèi)的像素彼此相連。在這種劃分方式中，12 種細(xì)分塊的模式如圖3 所示。

圖3 12 種分塊模式Fig.3 12 block modes

2.2 數(shù)據(jù)嵌入與提取

本文采用圖3 中的模式1 進行數(shù)據(jù)嵌入與提取。

2.2.1 數(shù)據(jù)嵌入

數(shù)據(jù)分塊示意圖如圖4 所示。

圖4 數(shù)據(jù)分塊示意圖Fig.4 Schematic diagram of data block

在數(shù)據(jù)嵌入過程中，對于圖4 中的子塊A，首先逐行讀取子塊A 的像素，獲得像素序列{p1，p2，p4，p5}，然后將其按照升序排列，得到{pω(1)，pω(2)，pω(3)，pω(4)}，其中，ω是一個雙射，使得pω(1)≤pω(2)≤pω(3)≤pω(4)。如果像素pω(w)=pω(r)，并且w＜r，則ω(w)＜ω(r)，計算預(yù)測誤差e1，j，如式（1）所示：

其中：j∈{1，2}；當(dāng)j=1 時，u=min{ω(j)，ω(2)}，v=max{ω(j)，ω(2)}；當(dāng)j=2 時，u=min{ω(j+1)，ω(4)}，v=max{ω(j+1)，ω(4)}。

如果b為嵌入的數(shù)據(jù)，b∈{0，1}，那么計算得到的水印誤差如式（2）所示：

相應(yīng)地，當(dāng)數(shù)據(jù)被嵌入后，子塊A 的最小像素pω(1)被修改為：

對于子塊B，采用從上向下和從右至左的順序讀取像素，得到像素序列{p3，p6，p9，p8，p7}，將其按照升序排列得到{pτ(1)，pτ(2)，pτ(3)，pτ(4)，pτ(5)}，其中，τ是雙射，使得pτ(1)≤pτ(2)≤pτ(3)≤pτ(4)≤pτ(5)。如果pτ(w)=pτ(r)，并且w＜r，則τ(w)＜τ(r)，預(yù)測誤差e2，j如式（5）所示：

本文算法將3×3 的圖像塊修改為可以嵌入6 bit圖像塊，與PVO 和IPVO 等算法相比，大幅提升了嵌入容量。IPVO 和本文算法的預(yù)測誤差值對比如圖5所示。圖5 選取了Lena 的3×3 的圖像塊，如果采用IPVO 算法，則只能得到2 個可以被用于嵌入數(shù)據(jù)的預(yù)測誤差。如果使用本文算法，將得到6 個可以被用來嵌入數(shù)據(jù)的預(yù)測誤差。

圖5 IPVO 算法和本文算法的預(yù)測誤差值對比Fig.5 Prediction error values comparison between IPVO algorithm and the proposed algorithm

2.2.2 數(shù)據(jù)提取

2.2.3 數(shù)據(jù)嵌入與提取樣例

本文算法的數(shù)據(jù)嵌入與提取過程如圖6 所示。數(shù)據(jù)嵌入過程首先將原始塊分為子塊A 和子塊B，對于子塊A，逐行掃描像素，排序得到像素序列pω={159，160，160，161}。根據(jù)式（1）計算預(yù)測誤差e1，1和e1，2，根據(jù)式（3）和 式（4）修改最大和最小像素嵌入b1和b2。對于子塊B，從上向下和從右到左掃描像素，排序得到像素序列pτ={159，160，160，161，163}，根據(jù)式（5）計 算4 個預(yù)測誤差為e2，1、e2，2、e2，3和e2，4，根據(jù)式（3）和 式（4）將p8、p6、p5、p9修改為′，以嵌入b3、b4和b5。最后將兩個子塊內(nèi)所有被修改的像素更新到原始塊對應(yīng)的位置上，以生成水印塊。

圖6 本文算法的數(shù)據(jù)嵌入與提取過程Fig.6 Data embedding and extraction process of the proposed algorithm

數(shù)據(jù)提取過程與數(shù)據(jù)嵌入過程相同，首先對水印塊進行分塊，得到水印像素序列和，然后分別計算這兩個水印序列的預(yù)測誤差，對于，計算誤差和，對于，計算誤差，根據(jù)式（6）提取出b1、b2、b3、b4和b5，根據(jù)式（7）和式（8）恢復(fù)出原始像素p2、p3、p8、p6、p5和p9，最后將所有恢復(fù)的像素更新到水印塊的相對位置上，得到原始塊。

2.3 局部復(fù)雜度

本文考慮到自然圖像中包含大量粗糙塊，如果對這些粗糙塊進行數(shù)據(jù)的嵌入操作，將會產(chǎn)生大量的移位像素，從而降低圖像的嵌入性能。在文獻(xiàn)［17］中，一個塊的局部復(fù)雜度定義為當(dāng)前塊的次大像素值與次小像素值的差值。然而，當(dāng)分塊較小時，參與排序的像素過少，難以反映灰度值的變化趨勢，因此，文獻(xiàn)［17］計算的局部復(fù)雜度不準(zhǔn)確。

由于自然圖像的相鄰像素呈高度相關(guān)關(guān)系，因此可以推斷相鄰圖像塊的復(fù)雜度也具有高度相關(guān)關(guān)系。一個光滑塊周圍的圖像塊也光滑，一個粗糙塊周圍的圖像塊必定粗糙。本文定義一個圖像塊的上下文像素為其所有相鄰塊中距離該塊最近的像素。圖像塊的上下文像素集C如式（9）所示：

上下文像素集C的方差被定義為圖像塊的局部復(fù)雜度NNL，如式（10）所示：

一個3×3 圖像塊的上下文像素示意圖如圖7所示。

圖7 3×3 圖像塊的上下文像素Fig.7 Context pixel of 3×3 image block

如果一個圖像塊的NNL小于給定的閾值T，則是平滑塊。本文按照2.2 節(jié)的方式對平滑塊進行塊再分，以嵌入數(shù)據(jù)。如果一個圖像塊的NNL大于等于給定的閾值T，則為復(fù)雜塊，對于復(fù)雜塊不做任何處理。

3 算法流程

3.1 嵌入算法

嵌入算法主要分為以下3 個步驟：

1）圖像分塊與位置地圖的構(gòu)建。首先將原始圖像中除第一行像素以外的所有像素分為3×3 不重疊的塊{X1，X2，…，XN}，其中，N為塊的總數(shù)。如果一個像素為255 或者0，則在嵌入過程中有可能被修改為256 或者-1，會造成上溢或者下溢。為解決該問題，若Xi內(nèi)含有像素255 或者0，將其標(biāo)記為LLM（i）=1；否則標(biāo)記為LLM（i）=0。最后將所有的LLM，即圖像的位置地圖壓縮成一個長度為LCLM的比特流串。

2）秘密數(shù)據(jù)嵌入。在執(zhí)行數(shù)據(jù)嵌入的過程中，嵌入算法只對所有LLM（i）=0 的圖像塊進行嵌入。對于每個LLM（i）=0 的圖像塊Xi，首先計算它的局部復(fù)雜度NNL。如果NNL≥T，則為粗糙塊，不做任何處理；如果NNL＜T，則為平滑塊。按照2.2.1 節(jié)提出的方法進行塊再分，根據(jù)式（1）和式（5）計算誤差e1，j和e2，j，根據(jù)式（2）進行誤差的擴展或者移位以嵌入秘密數(shù)據(jù)。當(dāng)所有的秘密數(shù)據(jù)都被嵌入完成后，該步驟將停止，最后一個嵌入數(shù)據(jù)的圖像塊被記為Xend。

3）輔助數(shù)據(jù)和位置地圖的嵌入。為實現(xiàn)數(shù)據(jù)的可逆恢復(fù)，輔助數(shù)據(jù)和位置地圖被嵌入到圖像第一行像素的最低有效位（Least Significant Bit，LSB）中。輔助數(shù)據(jù)為壓縮位置地圖的長度LCLM、閾值T、塊尺寸以及結(jié)束位置Xend。利用這些數(shù)據(jù)替換圖像第一行的LSB，并將替換掉的LSB 壓縮成比特流SLSB，最后按照步驟2 將其嵌入到圖像的剩余區(qū)域中，即{Xend，Xend+1，…，XN}。

3.2 提取算法

提取算法主要分為以下3 個步驟：

1）輔助數(shù)據(jù)與位置地圖的提取。在解碼端，提取算法讀取水印圖像第一行像素的LSB 位，提取LCLM、閾值T、塊尺寸、結(jié)束位置Xend以及壓縮的位置地圖，并將其解壓得到位置地圖。

2）數(shù)據(jù)提取。首先將水印圖像除第一行以外的所有像素分為3×3的塊，然后查找每個塊的標(biāo)記LLM（i），計算LLM（i）=0 的水印塊復(fù)雜度NNL，最后將滿足LLM（i）=0 并且NNL＜T的水印塊按照2.2節(jié)的方法進行再分塊，計算水印誤差和，并根據(jù)式（6）提取出秘密數(shù)據(jù)和壓縮的比特流SLSB。

3）圖像恢復(fù)。首先將提取的秘密數(shù)據(jù)按照2.2.2節(jié)的方法恢復(fù)出圖像的原始塊{X1，X2，…，XN}，然后解壓SLSB，將其替換掉圖像第一行像素的LSB 位，最后恢復(fù)出整個圖像。

4 實驗結(jié)果與分析

本文利用MATLAB R2018a 軟件在6 幅512×512像素的灰度圖像上，對比現(xiàn)有的基于像素值排序的可逆數(shù)據(jù)隱藏算法與本文算法的性能。6 張測試圖如圖8 所示，這些圖像都是從USC-SIPI 數(shù)據(jù)庫中下載獲得，在嵌入過程中數(shù)據(jù)b是隨機生成的0，1序列。

圖8 本文實驗6 張測試圖Fig.8 Six test images of the proposed experiment

本文在12 種分塊模式下對Lena 圖和Baboon 圖進行峰值信噪比（Peak Signal to Noise Ratio，PSNR）對比，結(jié)果如圖9 所示。從圖9 可以看出，當(dāng)采用分塊模式1 時，圖像的PSNR 性能最優(yōu)，因此，本文算法的最優(yōu)模式為模式1。

圖9 不同分塊模式下的PSNR 對比Fig.9 Comparison of PSNR in different block modes

在最優(yōu)模式下不同算法的PSNR對比如圖10所示。從圖10可以看出，在大多數(shù)情況下，本文算法的PSNR都最優(yōu)，并且隨著嵌入容量的增大，PSNR 的增益更明顯。因此，嵌入容量越大，本文算法的性能越優(yōu)。

圖10 不同算法的PSNR 對比Fig.10 PSNR comparison among different algorithms

從圖10 可以看出，當(dāng)Baboon 圖的嵌入容量小于8 000 bit 以及Barbara 圖的嵌入容量小于12 000 bit時，本文算法的PSNR 不是最高，其原因主要有兩個：1）本文算法未根據(jù)嵌入容量自適應(yīng)選擇圖像塊大小，即不能在嵌入容量較低時，采用更大的5×5圖像塊進行再分塊，而對于這類復(fù)雜圖像，相鄰像素聯(lián)系不緊密，使得對平滑塊的選擇更為精確，需要更多的上下文像素來計算局部復(fù)雜度，因此，本文算法的PSNR 不是最高；2）以上對比的其他算法在實驗過程中都通過窮舉搜索法選擇最優(yōu)參數(shù)，盡管這種方式可以提升PSNR，但是也會增大計算復(fù)雜度。

當(dāng)嵌入容量為1 000 bit 時，不同算法在6 張圖上的PSNR 對比如表1 所示。從表1 可以看出，相比其他算法，本文算法的平均PSNR 增益分別為1.22 dB、2.00 dB、2.08 dB、1.99 dB、1.68 dB、0.70 dB。這表明本文算法在低嵌入容量下能夠有效提升嵌入數(shù)據(jù)后的圖像質(zhì)量。

表1 當(dāng)嵌入容量為1 000 bit 時不同算法的PSNR 對比Table 1 PSNR comparison among different algorithms when embedding capacity is 1 000 bit dB

不同算法的最大嵌入容量對比如圖11 所示。分塊越小，最大嵌入容量就越大。在文獻(xiàn)［17］中，當(dāng)采用2×2 分塊時，圖像的嵌入容量達(dá)到了最大值。本文算法是在3×3固定大小的分塊上實現(xiàn)的。從圖11可以看出，本文算法的最大嵌入容量在某些圖像上是最大的，其原因為對于一個3×3 大小的圖像塊，最多可以嵌入6 bit數(shù)據(jù)，充分地利用了圖像塊內(nèi)的每一個像素。不同算法的計算復(fù)雜度對比如表2 所示。

圖11 不同算法的最大嵌入容量對比Fig.11 Maximum embedding capacity comparison among different algorithms

表2 不同算法的計算復(fù)雜度對比Table 2 Computational complexity comparison among different algorithms

文獻(xiàn)［17］通過窮舉搜索出三個最優(yōu)參數(shù)，即塊尺寸rL，cL和閾值TL，其中rL∈{2，3，4，5}，cL∈{2，3，4，5}，TL有NL個候選數(shù)，因此，文獻(xiàn)［17］的計算復(fù)雜度近似為O(16NL)。同理，文獻(xiàn)［18］的計算復(fù)雜度近似為O(16NP)，其中，16和NP分別為最優(yōu)尺寸rP×cp和最優(yōu)閾值Tp的候選數(shù)。文獻(xiàn)［23］需要窮舉搜索4 個最優(yōu)參數(shù)，即vT、Tw、rw和cw，其中，rw∈{3，4，5}，cw∈{3，4，5}，Tw有m個候選數(shù)，m=，vT有Nw個候選數(shù)。文獻(xiàn)［23］的計算復(fù)雜度近似為O(9m×Nw)。而本文算法只需要確定一個參數(shù)，即閾值T，因此計算復(fù)雜度僅為O(N)，其中，N為閾值T的候選數(shù)。

本文根據(jù)不同的嵌入容量，采用不同的最優(yōu)閾值T*改進本文算法。本文改進的算法與文獻(xiàn)［17-18］、文獻(xiàn)［23-26］算法在Barbara和Baboon的PSNR對比如圖12所示。從圖12 可以看出，無論嵌入容量是多少，本文改進算法的PSNR 都遠(yuǎn)大于現(xiàn)有算法。

圖12 本文改進算法與其他算法的PSNR 對比Fig.12 PSNR comparison among the proposed improved algorithm and other algorithms

5 結(jié)束語

本文提出基于像素值排序的可逆數(shù)據(jù)隱藏算法。通過計算每一個圖像塊的局部復(fù)雜度，并對比局部復(fù)雜度與閾值的大小，將局部復(fù)雜度小于閾值的圖像塊進行分塊，同時設(shè)計12 種分塊模式，并通過實驗測試不同分塊模式下的嵌入性能，選擇能夠得到最優(yōu)嵌入性能的模式進行數(shù)據(jù)嵌入。此外，通過改進本文算法，根據(jù)嵌入容量自適應(yīng)地選擇最優(yōu)閾值T*，以提高嵌入性能。實驗結(jié)果表明，本文算法能夠充分利用圖像塊內(nèi)的每個像素，具有較優(yōu)的嵌入性能。后續(xù)將在4×4 和6×6 圖像塊上設(shè)計分塊策略，進一步提升圖像塊的嵌入性能。