呂金鵬，梁海華，張新鵬

上海大學(xué)通信與信息工程學(xué)院，上海200444

混合進(jìn)制嵌入的調(diào)色板圖像無損信息隱藏

呂金鵬，梁海華，張新鵬

上海大學(xué)通信與信息工程學(xué)院，上海200444

提出了一種基于混合進(jìn)制的調(diào)色板圖像無損信息隱藏方法.首先根據(jù)索引分布，區(qū)分有效索引與冗余索引.在調(diào)色板中分配若干冗余索引指向同一有效索引的顏色，使相同顏色的不同索引值承載不同的秘密信息，用于無損信息隱藏.用動態(tài)規(guī)劃方法產(chǎn)生最大嵌入量下的冗余索引分配方案.不同顏色承載的秘密信息為不同進(jìn)制秘密數(shù)字.該方法中嵌入機(jī)制并不影響原始圖像內(nèi)容.實(shí)驗(yàn)表明，與以往方法相比，該方法提高了數(shù)據(jù)嵌入量，醫(yī)學(xué)圖像尤為顯著.

無損信息隱藏；調(diào)色板圖像；混合進(jìn)制；動態(tài)規(guī)劃

信息隱藏是指在不過分影響數(shù)字載體的前提下，將秘密信息隱藏在數(shù)字媒體中，以實(shí)現(xiàn)版權(quán)保護(hù)、內(nèi)容認(rèn)證和數(shù)字信息安全傳遞等［1-5］.如果接收方在提取嵌入信息的同時，還可以毫無損傷地恢復(fù)原始載體，這種技術(shù)被稱為可逆信息隱藏［6］.目前，已經(jīng)有許多學(xué)者提出了可逆信息隱藏方法，如差值擴(kuò)展［7］、直方圖平移［8］、無損壓縮［9］等.這些方法在嵌入過程中允許引入失真，但這種失真是可逆的，在提取信息時可以將原始圖像恢復(fù).研究者希望減少嵌入信息后載體圖像的失真，以避免由失真引起觀察者對圖像內(nèi)容的誤解，因此需要一種嵌入信息后載體無失真的技術(shù)，即無損信息隱藏（lossless data hiding）.

調(diào)色板圖像在互聯(lián)網(wǎng)上很常見，也常應(yīng)用于醫(yī)學(xué)圖像，如X射線圖像以及磁共振成像（magnetic resonance imaging，MRI），可以作為信息隱藏的載體.它可以用不多于256種顏色來表現(xiàn)可以接受的視覺效果.通常，調(diào)色板圖像文件分為兩部分：前一部分是調(diào)色板，為每一個顏色分別定義一個索引值；后一部分為像素矩陣，給出每一個像素的索引值.對于一幅256種顏色的調(diào)色板圖像，一個索引值只需8比特，圖像所需的儲存空間便大大減少［10］.目前，針對調(diào)色板圖像的無損信息隱藏方法并不多.文獻(xiàn)［11］提出一種通過改變調(diào)色板中索引值與真實(shí)顏色的對應(yīng)關(guān)系進(jìn)行信息隱藏的方法，對調(diào)色板的顏色順序進(jìn)行重排以嵌入信息，但調(diào)色板數(shù)據(jù)的任意排列不影響圖像內(nèi)容，只要像素矩陣的索引值能有相應(yīng)變化即可.文獻(xiàn)［12］通過利用調(diào)色板圖像中未用的保留字隱藏秘密的信息，嵌入信息的圖像無失真，但嵌入量十分有限.文獻(xiàn)［13］首先對調(diào)色板預(yù)處理，使2L-1個冗余索引值對應(yīng)同一種顏色，其中L∈（0，8）.修改一個像素的索引值可嵌入L比特秘密數(shù)據(jù).由于修改前后索引值都指向同一個顏色，載體圖像在嵌入過程中無失真，此時每幅圖像的參數(shù)L通過遍歷（0，8）后計(jì)算最大嵌入量得到.文獻(xiàn)［14］在文獻(xiàn)［13］的基礎(chǔ)上進(jìn)行改進(jìn)，由于每種顏色的參數(shù)L不同，需要遍歷每種顏色L的取值，通過計(jì)算嵌入量得到最佳冗余分配方案，這樣在保證無失真的同時增大了圖像的嵌入量.

雖然文獻(xiàn)［14］改進(jìn)了冗余索引的利用效率，但是冗余空間并未得到完全利用.為提高嵌入量，本文改進(jìn)了文獻(xiàn)［14］的方法，提出了一種基于混合進(jìn)制的無損信息隱藏方法.首先對調(diào)色板進(jìn)行預(yù)處理，不同于文獻(xiàn)［14］，分配給每一個顏色的冗余索引數(shù)目不局限于2L-1，為任意正整數(shù).本文通過動態(tài)規(guī)劃的方法尋找最大嵌入量下的冗余索引分配方案，在信息嵌入過程中只需將秘密信息進(jìn)行進(jìn)制轉(zhuǎn)換，根據(jù)轉(zhuǎn)換后的混合進(jìn)制數(shù)字序列修改像素的索引值.實(shí)驗(yàn)證明，嵌入信息的圖像相對于原始圖像沒有任何失真，且相較于文獻(xiàn)［14］的方法，本文方法提高了嵌入量，其中醫(yī)學(xué)圖像尤為顯著.

1　無損信息隱藏方案

調(diào)色板共有256種索引，但真實(shí)圖像通常并未使用調(diào)色板中的所有索引，而是存在冗余索引，可用于信息隱藏.在調(diào)色板中，分配若干冗余索引指向同一有效索引的顏色，使相同顏色的不同索引值承載不同秘密信息.通過動態(tài)規(guī)劃來確定最佳的冗余索引分配方案，嵌入時將秘密信息進(jìn)制轉(zhuǎn)換，在像素矩陣中根據(jù)轉(zhuǎn)換后的混合進(jìn)制數(shù)字序列修改像素的索引值；提取時由調(diào)色板恢復(fù)出索引分配方案，在像素矩陣中根據(jù)像素索引值提取其承載的混合進(jìn)制數(shù)字序列，轉(zhuǎn)為二進(jìn)制即為秘密信息.

1.1冗余索引分配

設(shè)圖像中索引i對應(yīng)的顏色Di=（ri，gi，bi），Di為三維向量，其中ri、gi、bi分別為該顏色的紅色分量、綠色分量、藍(lán)色分量.根據(jù)各顏色在圖像中像素?cái)?shù)目對256種顏色降序排列，其對應(yīng)的索引值修改為0，1，···，255.排序后顏色Di在圖像中像素?cái)?shù)目為H［i］，其中H［i］=0的索引值為冗余索引，其總數(shù)為N.

設(shè)（i，Di）為有效索引值與顏色對，在調(diào)色板中修改Si個冗余索引值f，f+1，f+2，···，f+Si-1指向顏色Di，其中Si∈［0，N］.此時顏色Di對應(yīng)Si+1個索引值，即Di對應(yīng)的索引值有Si+1種可能性.若每個索引值都攜帶一個隱藏碼K，那么一個顏色為Di的像素可以嵌入lb（Si+1）比特信息.假設(shè)像素矩陣為I，一個顏色為Di的像素的坐標(biāo)為（x，y），隱藏碼與索引值對應(yīng)關(guān)系為

在像素矩陣中，根據(jù)秘密信息修改索引值可以實(shí)現(xiàn)信息隱藏.因?yàn)樾薷那昂笏饕抵赶虻念伾詾镈i，所以載體圖像無失真.值得注意的是，式（1）隱藏碼不局限于二進(jìn)制.若秘密信息為二元數(shù)字序列，則需秘密信息轉(zhuǎn)為Si+1進(jìn)制數(shù)字序列.合理分配每個顏色對應(yīng)冗余索引的數(shù)目，可以使嵌入量達(dá)到最大.由式（1）可知，假設(shè)一個有效索引顏色對應(yīng)Si個冗余索引，那么圖像中該顏色可嵌入（Si+1）H［i］比特信息.N個冗余索引分配方案如圖1所示.顯然S0+S1+···+SN-1=N，此時調(diào)色板圖像的嵌入量C為

對于一幅圖像，H［0］，H［1］，···，H［255］和N均為定值，圖像最大嵌入量是關(guān)于變量S0～SN-1非線性約束的組合優(yōu)化問題.優(yōu)化的標(biāo)準(zhǔn)式如下：

式中，h為S0～SN-1取值的第h種情況，為C（i，h）取最大值時Si的取值.對于上述問題，若通過遍歷，則計(jì)算量過大.本文采用動態(tài)規(guī)劃算法（dynamic programming，DP）來減少時間復(fù)雜度.對式（3）的求解步驟如下：

步驟1設(shè)M（u，v）表示u個冗余索引最多分為v組時的最大嵌入量.每組依次為指向顏色D0，D1，···，Dv-1的冗余索引值，設(shè)每組的數(shù)目依次為S0，S1，···，Sv-1.

步驟2當(dāng)v=1時，u個冗余索引值都分配給顏色D0

當(dāng)v＞1時，由式（2）可知，已知H［0］≥H［1］≥···≥H［255］，最大嵌入量下的S0～ Sv-1必須滿足S0≥S1···≥Sv-1，那么最后一組冗余索引數(shù)目Sv-1的取值范圍為，遍歷Sv-1的取值，則有

步驟3根據(jù)遞推關(guān)系，迭代求出N個冗余索引最多分為N組的最大嵌量M（N，N）以及此時S0～SN-1的值.

圖1　冗余索引分配示意圖Figure 1 Distribution solutions of redundant indices

1.2嵌入與提取過程

嵌入與提取過程的步驟如下：

步驟1修改調(diào)色板.由原始圖像索引分布并根據(jù)1.1可得最佳冗余索引分配方案S0～SN-1，按照該方案在調(diào)色板中修改冗余索引的顏色為其對應(yīng)有效索引的顏色.

步驟2對秘密信息進(jìn)行預(yù)處理.如圖2所示，假設(shè)加密后待嵌入二進(jìn)制信息S的數(shù)據(jù)總量為Payload，將S切割為N組，第i+1組的數(shù)據(jù)量Pi，其中i∈［0，N-1］，Pi對應(yīng)圖像中顏色Di嵌入信息量，Pi最多為「lb（Si+1）H［i］」比特.然后將每組大小為Pi的數(shù)據(jù)流分別轉(zhuǎn)換為S0+1，S1+1，···，SN-1+1進(jìn)制秘密數(shù)字序列.

步驟3在像素矩陣中嵌入信息.依次讀取信息量大小為Pi的Si+1進(jìn)制數(shù)字序列，設(shè)像素矩陣中顏色為Di的像素集合為Ui，根據(jù)式（1）索引值對應(yīng)的隱藏碼修改Ui的索引值.對N組數(shù)字序列重復(fù)上述操作后，已將秘密信息完全嵌入.

步驟4在接收端提取信息.由嵌入圖像的調(diào)色板可知冗余索引的分配方案，即S0～ SN-1.設(shè)顏色Di對應(yīng)冗余索引值為.掃描像素矩陣中索引值為， ···，根據(jù)式（1）提取Si+1進(jìn)制隱藏?cái)?shù)據(jù)，并轉(zhuǎn)化為二進(jìn)制序列，對顏色D0，D1，···， DN-1執(zhí)行上述操作，直到秘密信息完全提取為止.

圖2　秘密信息切割示意圖Figure 2 Segments of secret data

2　仿真與對比分析

本文從嵌入率來評估算法性能.為驗(yàn)證本文算法，采用12幅256色圖像作為測試載體，如圖3所示.

設(shè)圖像大小為X×Y，嵌入率e為平均每個像素可以承載的秘密信息量，則其表達(dá)式為

圖3　測試圖像Figure 3 Test images

實(shí)驗(yàn)用占圖像50%的顏色種類數(shù)目T來表示圖像索引顏色分布的復(fù)雜程度.在圖3中，圖像（a）～（e）為醫(yī)學(xué)圖像，T集中在［1，10］，紋理較為簡單；圖像（f）～（h）為卡通圖像，T集中在（10，20］，紋理較復(fù)雜；圖像（i）～（l）為自然圖像，T集中在（20，+∞），紋理最復(fù)雜.本文對12幅圖像進(jìn)行信息嵌入，所得嵌入率與文獻(xiàn)［14］的對比如表1所示.

從表1中可以看出，圖像的嵌入率與圖像內(nèi)容具有很大的相關(guān)性.對于實(shí)驗(yàn)中的3類圖像，醫(yī)學(xué)圖像表現(xiàn)最好，圖像（c）的嵌入率可達(dá)4.723 bpp（bpp為平均每像素嵌入的比特?cái)?shù)）.因?yàn)獒t(yī)學(xué)圖像冗余索引較多，且顏色分布較集中，所以嵌入量就較多.

文獻(xiàn)［14］在冗余索引分配時，2L-1個冗余索引對應(yīng)同一有效索引的顏色，嵌入信息為二進(jìn)制.由于混合進(jìn)制充分利用了冗余索引，針對第1類醫(yī)學(xué)圖像，嵌入率較文獻(xiàn)［14］提高較多，最多可提高36.4%；對第3類圖像及第2類部分圖像，其顏色分布平均，較文獻(xiàn)［14］只提高1%～4.85%，可見本方法在醫(yī)學(xué)圖像上的性能更顯著.

表2給出了文獻(xiàn)［14］與本文方法的冗余索引分配方案.MRI圖像為簡單紋理圖像，冗余索引數(shù)目為6，經(jīng)排序后對應(yīng)的索引值為250～255.排序后H［0］～H［5］為［90 156，2 339，1 447，1 440，1 205，1 108］.文獻(xiàn)［14］冗余索引分配方案如表3所示.索引值［0，250，251，252］對應(yīng)顏色為D0，索引值［1，253］對應(yīng)顏色為D1，索引值［2，254］對應(yīng)顏色為D2，索引值［3，255］對應(yīng)顏色為D3.本方法分配給每個顏色的冗余索引數(shù)目為任何正整數(shù)，由動態(tài)規(guī)劃得到的最佳分配方案可知，索引值［0，250，251，252，253，254，255］均對應(yīng)D0.混合進(jìn)制嵌入方法更高效地利用了冗余索引，故本文提出方法的嵌入量大于文獻(xiàn)［14］.

表1　本文方法與文獻(xiàn)［14］方法所得嵌入率對比Table 1 Embedding rate comparison of the proposed method and reference［14］

針對復(fù)雜紋理圖像，如Flower圖像和Lake圖像，文獻(xiàn)［14］與本文方法的冗余索引分配方案如表2所示.相較于二進(jìn)制信息嵌入方法［14］，本文提出的混合進(jìn)制嵌入方法更高效地利用了冗余索引，嵌入量均有所提高.

表2　冗余索引分配方案對比Table 2 Comparison of distribution solutions of redundant indices

3　結(jié)語

本文提出了一種基于混合進(jìn)制的調(diào)色板圖像無損信息隱藏方法.分配若干冗余索引指向同一有效索引的顏色，使相同顏色的不同索引值承載不同秘密信息.在嵌入過程中，對加密后的秘密信息進(jìn)制進(jìn)行轉(zhuǎn)換，根據(jù)轉(zhuǎn)換后的混合進(jìn)制數(shù)字序列修改像素的索引值.實(shí)驗(yàn)結(jié)果表明，同文獻(xiàn)［14］相比，混合進(jìn)制嵌入方法更高效地利用了冗余索引，提高了嵌入量，對于醫(yī)學(xué)圖像尤為顯著.在實(shí)際應(yīng)用中，更高的嵌入量給隱蔽通信帶來極大的便利，所以本文的研究很有意義.

［1］王朔中，張新鵬，張開文.數(shù)字密寫和密寫分析：互聯(lián)網(wǎng)時代的信息戰(zhàn)技術(shù)［M］.北京：清華大學(xué)出版社有限公司，2005.

［2］CHAN C K，CHENG L M.Hiding data in images by simple LSB substitution［J］.Pattern Recognition，2004，37（3）：469-474.

［3］SALLEE P.Model-based steganography［M］//Digital Watermarking.Berlin Heidelberg：Springer，2004：154-167.

［4］ZHANG X，WANG S.Efficient steganographic embedding by exploiting modification direction［J］. IEEE on Communications Letters，2006，10（11）：781-783.

［5］PENG F，LI X，YANG B.Adaptive reversible data hiding scheme based on integer transform［J］. Signal Processing，2012，92（1）：54-62.

［6］ZHANG X.Reversible data hiding in encrypted image［J］.Signal Processing Letters，2011，18（4）：255-258.

［7］TIAN J.Reversible data embedding using a difference expansion［J］.IEEE Transactions on Circuits and Systems for Video Technology，2003，13（8）：890-896.

［8］NI Z，SHI Y Q，ANSARI N，SU W.Reversible data hiding［J］.IEEE Transactions on Circuits and Systems for Video Technology，2006，16（3）：354-362.

［9］CELIL M U，SHARMA G，TEKALp A M，SABER E.Lossless generalized-LSB data embedding［J］. IEEE Transactions on Image Processing，2005，14（2）：253-266.

［10］張新鵬，王朔中.對OPA密寫的檢測和增強(qiáng)安全性的調(diào)色板圖像密寫方案［J］.電子學(xué)報(bào)，2004，（10）：1702-1705. ZHANG X P，WANG S Z.Detection of OPA stego-data and secure steganography in palette images［J］.Acta Electronica Sinica，2004（10）：1702-1705.（in Chinese）

［11］KWAN M.The gifshuffie homepage［EB/OL］.http：//www.darkside.com.au/gifshuffie/，2003

［12］BANDYOpADHYAY S K，MAITRA I K，BHATTACHARYYA D，TAI-HOON K.Reserved fields of palette for data hiding in steganography［C］//International Conference on Computational Intelligence and Communication Networks（CICN），2010 International Conference，2010：398-402.

［13］LIU H M，ZHANG Z F，HUANG J W，HUANG X L，SHI Y Q.A high capacity distortion-free data hiding algorithm for palette image［C］//IEEE International Symposium on Circuits and Systems（ISCAS），2003：916-919.

［14］SALEHA N A，BOGHDAYA H N，SHAHEENB S I，DARWISHB A M.High capacity lossless data embedding technique for palette images based on histogram analysis［J］.Digital Signal Processing，2010，20（6）：1629-1636.

（編輯：秦?。?/p>

Lossless Data Hiding in Palette Images Based on Mix-ary Codes

Lü Jin-peng，LIANG Hai-hua，ZHANG Xin-peng
School of Communication and Information Engineering，Shanghai University，Shanghai 200444，China

This paper proposes a lossless data hiding method in palette images based on mix-ary codes.According to the distributionof indices，the indices are divided into effective indices and redundant indices.In the palette a certain number of redundant indices are mapped to the color of an effective index.Then the indices mapping to the same color stand for different secret digits in order to embed extra data losslessly.A dynamic programming algorithm is used to find the best allocation for redundant indices to achieve the highest embedding capacity.Embedded data subsets carried by different colors are different notational sequences.The data embedding operation does not affect the original image.Experiments showthat themethod has higher embedding capacity than previous methods，especially for medical images.

lossless data hiding，palette image，mix-ary code，dynamic programming

TN911.73

0255-8297（2015）06-0637-07

10.3969/j.issn.0255-8297.2015.06.007

2015-06-26；

2015-07-20

國家自然科學(xué)基金（No.61472235）資助

張新鵬，教授，博導(dǎo)，研究方向：多媒體信息安全，E-mail：xzhang@shu.edu.cn