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

任方，楊益萍，薛斐元

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

0 概述

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

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

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

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

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

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

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

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

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

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

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

2 本文算法

2.1 分塊模式

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

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

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

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

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

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

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

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

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

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

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

對(duì)于子塊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ù)測(cè)誤差e2，j如式（5）所示：

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

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

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

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

2.3 局部復(fù)雜度

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

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

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

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

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

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

3 算法流程

3.1 嵌入算法

嵌入算法主要分為以下3 個(gè)步驟：

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

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

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

3.2 提取算法

提取算法主要分為以下3 個(gè)步驟：

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

圖8 本文實(shí)驗(yàn)6 張測(cè)試圖Fig.8 Six test images of the proposed experiment

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

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

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

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

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

當(dāng)嵌入容量為1 000 bit 時(shí)，不同算法在6 張圖上的PSNR 對(duì)比如表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 時(shí)不同算法的PSNR 對(duì)比Table 1 PSNR comparison among different algorithms when embedding capacity is 1 000 bit dB

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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