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

任方，楊益萍，薛斐元

（1.西安郵電大學 網絡空間安全學院，西安 710121；2.西安郵電大學 無線網絡安全技術國家工程實驗室，西安 710121）

0 概述

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

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

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

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

1 基于像素值排序的可逆數據隱藏算法

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

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

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

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

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

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

2 本文算法

2.1 分塊模式

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

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

2.2 數據嵌入與提取

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

2.2.1 數據嵌入

數據分塊示意圖如圖4 所示。

圖4 數據分塊示意圖Fig.4 Schematic diagram of data block

在數據嵌入過程中，對于圖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)，計算預測誤差e1，j，如式（1）所示：

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

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

相應地，當數據被嵌入后，子塊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)，預測誤差e2，j如式（5）所示：

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

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

2.2.2 數據提取

2.2.3 數據嵌入與提取樣例

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

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

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

2.3 局部復雜度

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

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

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

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

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

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

3 算法流程

3.1 嵌入算法

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

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

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

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

3.2 提取算法

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

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

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

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

4 實驗結果與分析

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

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

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

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

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

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

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

當嵌入容量為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。這表明本文算法在低嵌入容量下能夠有效提升嵌入數據后的圖像質量。

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

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

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

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

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

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

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

5 結束語

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