基于騎士巡游的灰度圖像加密壓縮算法

劉博文，柏 森，劉程浩，杜鶴峣

(1.重慶通信學(xué)院應(yīng)急通信重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400035;2.西南醫(yī)院健康體檢中心，重慶 400050)

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)和數(shù)字圖像技術(shù)的飛速發(fā)展，數(shù)字圖像已經(jīng)成為人們獲取信息的重要來(lái)源，并成為人們生活中傳遞信息的重要組成部分。人們對(duì)圖像信息的傳輸效率、安全性等方面也提出了更多要求，各種圖像加密算法［1］也應(yīng)運(yùn)而生。現(xiàn)有的圖像加密算法中，有基于空間域的，也有基于變換域的。前者算法簡(jiǎn)單、直觀，但其經(jīng)過(guò)加密后，像素之間的相關(guān)性會(huì)遭到破壞，以致壓縮率降低。由于變換域上任意一個(gè)系數(shù)發(fā)生變化，就會(huì)引起圖像原空間中的所有像素點(diǎn)發(fā)生變化，因而基于變換域的算法加密效率較高［2］。以往大量的工作，都只針對(duì)壓縮或加密單方面進(jìn)行研究與算法設(shè)計(jì)，而這對(duì)于某些對(duì)圖像數(shù)據(jù)量有較高要求的信息來(lái)說(shuō)，是無(wú)法滿足的。為了提高傳輸大量圖像信息的效率，同時(shí)又具有一定安全性，數(shù)字圖像加密和壓縮結(jié)合的技術(shù)成為了當(dāng)前國(guó)內(nèi)外研究的熱點(diǎn)。

目前，在變換域中實(shí)現(xiàn)圖像加密壓縮的文獻(xiàn)較少［3-6］。文獻(xiàn)［3］較早做了在DCT變換域中實(shí)現(xiàn)圖像加密壓縮的工作，但出現(xiàn)加密后的系數(shù)不在原始系數(shù)的取值區(qū)間，且不能表示成2的冪的形式，無(wú)法簡(jiǎn)單地用諸如異或運(yùn)算等方式實(shí)現(xiàn)加密。文獻(xiàn)［4］給出的是一種只對(duì)非零系數(shù)進(jìn)行加密的方法，其加密壓縮的效果并不能令人滿意，所以人為地對(duì)數(shù)據(jù)進(jìn)行選擇性加密會(huì)影響其安全性。文獻(xiàn)［5］解決了加密后的系數(shù)落在原始系數(shù)區(qū)間的問(wèn)題，但效率較低，加密運(yùn)算需要迭代次數(shù)過(guò)多，并且使用一維混沌序列的加密強(qiáng)度還有待加強(qiáng)。文獻(xiàn)［6］中提到的CWF算法在小波域中進(jìn)行加密壓縮，但其破壞了小波變換的多尺度分解樹型結(jié)構(gòu)，勢(shì)必嚴(yán)重影響圖像的可壓縮性。

為了保證圖像信息的安全性和壓縮效率，筆者對(duì)圖像加密壓縮進(jìn)行了研究，提出一種基于騎士巡游的灰度圖像加密壓縮方法。首先對(duì)原始圖像進(jìn)行8×8分塊操作，再對(duì)每個(gè)8×8塊進(jìn)行DCT變換，產(chǎn)生的一個(gè)系數(shù)塊化矩陣;然后對(duì)該系數(shù)塊化矩陣采用騎士巡游進(jìn)行以塊為單位的置亂加密;最后經(jīng)壓縮后得到加密壓縮圖像。這樣得到的加密壓縮圖像既能保證一定的安全性，又能保證較高的壓縮率。

1 騎士巡游及置亂加密原理

18世紀(jì)50年代末，著名數(shù)學(xué)家Euler［7］率先提出了騎士巡游問(wèn)題。騎士巡游問(wèn)題 (Knight’s Tour Problem)，簡(jiǎn)稱KTP，來(lái)源于國(guó)際象棋，就是騎士(馬)從棋盤上的某個(gè)初始棋格開始，以跳“斜日”的方式跳遍棋盤上的每個(gè)棋格一次僅且一次的一種方案［8］。騎士的巡游只由少數(shù)幾個(gè)參數(shù)(騎士巡游起始位置、巡游規(guī)則等)控制。在棋盤上建立坐標(biāo)系，將棋盤左上角視為原點(diǎn)，棋盤上的每一格視為對(duì)應(yīng)坐標(biāo)系上一個(gè)點(diǎn)。則騎士巡游起始位置k1(x，y)就表示騎士從(x，y)格上開始移動(dòng)。巡游規(guī)則k2［i，j］表示騎士每次移動(dòng)的方法，即水平方向跳 i個(gè)棋格，垂直方向跳 j個(gè)棋格，或相反。例如 k1(1，1)，k2［1，2］的騎士巡游如圖1a所示。一個(gè)m×n的棋盤上騎士巡游路徑可以用騎士巡游矩陣T進(jìn)行表示，其中矩陣T中1表示騎士巡游的起點(diǎn)，mn表示巡游的終點(diǎn)。例如，一個(gè)8 ×8 棋盤上 k1(1，2)，k2［1，2］的騎士巡游路徑可以用圖1b所示的矩陣來(lái)表示。其中，第1行第2列的元素1表示騎士巡游的起點(diǎn)，第1行第1列的元素64表示騎士巡游的終點(diǎn)，t表示騎士第t步所處棋盤上的位置，t=1，2，…，64。置亂加密基本原理就是將矩陣T中位置1的元素移動(dòng)到位置2，位置2的元素移動(dòng)到位置3，以此類推，最后將位置mn的元素移到位置1上。

圖1 騎士巡游示意圖

經(jīng)多年來(lái)的研究表明，騎士巡游在圖像加密上的應(yīng)用［9-10］效果非常好。筆者在騎士巡游置亂加密圖像的基礎(chǔ)上，將加密與壓縮結(jié)合，研究新的圖像加密壓縮算法。

2 基于騎士巡游的圖像加密壓縮算法

2.1 算法思想

由于圖像JPEG壓縮中的DCT變換是以8×8作為最小單元進(jìn)行變換。因此本文提出的算法將原始圖像進(jìn)行8×8分塊操作后，對(duì)塊化后的圖像進(jìn)行DCT變換得到系數(shù)塊化矩陣。將系數(shù)塊化矩陣中的每一塊視為棋盤上的棋格，按照騎士的移動(dòng)規(guī)則對(duì)每塊進(jìn)行移動(dòng)，以實(shí)現(xiàn)圖像中的塊置亂。再經(jīng)JPEG壓縮后，就得到加密壓縮圖像。這樣，由于塊化操作，使得每一個(gè)小塊內(nèi)依然具有原有的相關(guān)性，就能很好地防止壓縮率降低的問(wèn)題。

這里提出一種加密壓縮流程，如圖2所示。

2.2 原理與步驟

設(shè)原始圖像為 Im×n，加密后圖像為 I'm×n，加密壓縮后圖像為I″m×n。本文加密壓縮算法表述如下:

圖2 加密壓縮流程圖

1)讀取原始灰度圖像Im×n，對(duì)其先進(jìn)行8×8分塊，將圖像分成k×l個(gè)小塊，然后對(duì)每一塊進(jìn)行DCT變換后，得到系數(shù)塊化矩陣 Ck×l。其中，k=?m/8」，l=?n/8」，?」表示下取整。

2)根據(jù)前面第2節(jié)的介紹，選擇起始位置k1(x，y)、巡游規(guī)則k2［i，j］作為初始密鑰，使用文獻(xiàn)［11］中的算法得到騎士巡游矩陣Tk×l。

3)將 Ck×l中每個(gè)8 ×8 塊看成 Tk×l上的一格，使 Ck×l與Tk×l中元素一一對(duì)應(yīng)。根據(jù)騎士巡游置亂原理進(jìn)行騎士巡游塊置亂，得到加密后的系數(shù)塊化矩陣C'k×l。

4)對(duì)C'k×l進(jìn)行DCT逆變換，將逆變換后的數(shù)據(jù)塊化還原，得到加密后圖像I'm×n。

5)令 Im×n=I'm×n，重復(fù)步驟1)至5)，直至得到滿意的加密效果為止。最后將I'm×n進(jìn)行JPEG壓縮，得到最終加密壓縮圖像 I″m×n。

解密是上述過(guò)程的逆過(guò)程。

3 算法仿真與評(píng)價(jià)

3.1 直觀效果

通過(guò)對(duì)256×256的Lena和Baboon兩幅測(cè)試圖像進(jìn)行5 次循環(huán)加密實(shí)驗(yàn)，設(shè)置初始密鑰 k1(1，1)，k2［1，2］和k1(1，2)，k2［1，4］，其加密壓縮效果分別如圖3 和圖4。

圖3 Lena圖像加密壓縮效果圖

圖4 Baboon圖像加密壓縮效果圖

可以看出基于騎士巡游的加密壓縮方案得到了較好的加密效果，而且解密的效果理想。

3.2 置亂度

置亂度(SM)用來(lái)評(píng)估圖像被置亂或加密程度，即圖像加密的直觀效果好壞的重要指標(biāo)，它能較為客觀地反映圖像的加密效果。目前，許多文獻(xiàn)都給出了置亂度的定義，但又各不相同。這里引用文獻(xiàn)［12］中定義的置亂度來(lái)評(píng)估圖像的置亂或加密程度，其計(jì)算式為

式中:I={Iij}M×N表示原始圖像，～I(xiàn)={～I(xiàn)ij}M×N表示置亂或加密圖像，R={Rij}M×N表示與原始圖像相同大小的均勻分布噪聲圖像。為了使得加密圖像的置亂度具有可比性，通常采用同一幅均勻分布的噪聲圖像。本文取k1(1，1)，k2［1，2］為密鑰，得到的實(shí)驗(yàn)結(jié)果如表1。

表1 加密后圖像的置亂度

為了提高算法的壓縮率，采用了塊化操作，這使得加密置亂的單位是8×8塊而不是單個(gè)像素，從而導(dǎo)致加密的置亂度有一定下降，可通過(guò)增加循環(huán)加密次數(shù)來(lái)解決置亂度較低的問(wèn)題。

3.3 壓縮率

壓縮率作為圖像壓縮的一個(gè)評(píng)價(jià)指標(biāo)，其計(jì)算式為

在壓縮率測(cè)試中，采用256×256的Lena圖像進(jìn)行測(cè)試。算法選擇k1(1，1)，k2［1，2］的騎士巡游矩陣作為密鑰，文獻(xiàn)［15］采用閾值為100時(shí)的最好效果，經(jīng)過(guò)1次加密后得到壓縮率如表2所示。

表2 壓縮效率比較

隨著本文算法加密次數(shù)的增加，壓縮率將保持不變。其結(jié)果如表3。

表3 加密次數(shù)與壓縮率

可以看出，采用基于騎士巡游的灰度圖像加密壓縮算法在壓縮性上較文獻(xiàn)［15］提高了不少，接近對(duì)原始圖像直接壓縮的效果。并隨著加密次數(shù)的增加，壓縮率基本保持不變。因此選取加密次數(shù)為5次，以節(jié)約運(yùn)算時(shí)間。

3.4 安全性分析

騎士巡游矩陣作為密鑰時(shí)，其密鑰空間如表4所示。

表4 騎士巡游矩陣數(shù)量統(tǒng)計(jì)表［16］

結(jié)果表明，對(duì)于一個(gè)8×8的棋盤，其擁有的騎士巡游矩陣的數(shù)量至少3.019×1022個(gè)。由于人眼可以分辨其內(nèi)容的圖像大小一般為50×50以上，所以用騎士巡游矩陣作為圖像加密的密鑰，其密鑰量將會(huì)是個(gè)天文數(shù)字。換個(gè)角度來(lái)說(shuō)，用騎士巡游矩陣作為密鑰時(shí)，其密鑰空間足夠大。

圖像加密還要求較高的密鑰敏感性，即密鑰之間發(fā)生變化時(shí)，就能夠?qū)е陆饷苁　＿@樣就能保證密碼系統(tǒng)針對(duì)窮舉攻擊、統(tǒng)計(jì)攻擊的安全性。這里使用初始密鑰k1(1，1)，k2［1，2］進(jìn)行一次圖像加密，分別用密鑰 k1(1，2)，k2［1，2］和 k1(1，1)，k2［1，4］解密 Lena 圖像，其解密效果如圖5所示。

圖5 Lena圖像解密效果圖

仿真實(shí)驗(yàn)表明，騎士巡游矩陣的密鑰發(fā)生變化時(shí)，就無(wú)法正確解密出原始圖像。因此，本文的加密壓縮算法對(duì)騎士巡游棋盤密鑰具有很好的敏感性。

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

本文提出的一種基于騎士巡游的圖像加密壓縮算法，實(shí)現(xiàn)了具有加密效果較好、密鑰空間大、密鑰敏感性強(qiáng)等優(yōu)點(diǎn)的加密壓縮方法。通過(guò)在變換域中使用騎士巡游塊置亂加密，在保證一定安全性的前提下，降低了加密對(duì)壓縮效率的影響。經(jīng)實(shí)驗(yàn)證實(shí)將加密和壓縮相結(jié)合，既能保證傳輸涉密圖像的安全性，又能大大提高存儲(chǔ)和傳輸效率。在圖像信息的發(fā)布與交流越來(lái)越普及的今天，該方法具有很好的應(yīng)用前景。

［1］李昌剛，韓正之，張浩然.圖像加密技術(shù)綜述［J］.計(jì)算機(jī)研究與發(fā)展，2002，39(17):1317-1324.

［2］李娟，馮勇，楊旭強(qiáng).壓縮圖像的三維混沌加密算法［J］.光學(xué)學(xué)報(bào)，2010，30(2):399-404.

［3］孫鑫，易開祥，孫優(yōu)賢.基于混沌系統(tǒng)的圖像加密算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14(2):136-139.

［4］李興華，高飛.一種基于混沌序列的數(shù)字圖像加密算法［J］.電訊技術(shù)，2006，46(1):99-104.

［5］彭成，柳林.基于混沌序列的壓縮圖像加密算法［J］.計(jì)算機(jī)工程，2008，34(20):177-179.

［6］平亮，孫軍，周軍.一種基于JEPG2000標(biāo)準(zhǔn)的數(shù)字圖像加密算法［J］.電視技術(shù)，2006，30(7):87-90.

［7］EULER L.Solution d’une question curieuse qui ne parait soumise à aucune analyse［M］.Berlin:Mémoire de I’Académie Royale des Scìences XV，1759:310-337.

［8］PARBERRY I.An efficient algorithm for the knight's tour problem［J］.Discrete Applied Mathematics，1997，73(3):251-260.

［9］柏森，曹長(zhǎng)修.一種新的數(shù)字圖像置亂隱藏算法［J］.計(jì)算機(jī)工程，2001，27(11):18-19.

［10］姜德雷，柏森，董文明.基于廣義騎士巡游的圖像比特位平面間置亂算法［J］.自然科學(xué)進(jìn)展，2009，19(6):691-696.

［11］BAI Sen，LIAO Xiaofeng，QU Xiaohong，et al.Generalized knight’s tour problem and its solutions algorithm［C］//Proc.2006 International Conference on Computational Intelligence and Security:Part I.［S.l.］:IEEE Press，2006:570-573.

［12］侯啟檳，楊小帆，王陽(yáng)生，等.一種基于小波變換和騎士巡游的圖像置亂算法［J］.計(jì)算機(jī)研究與發(fā)展，2004，41(2):369-375.

［13］CHEN G，ZHAO X Y，LI J L.A self-adaptive algorithm on image encryption［J］.Journal of Software，2005，16(11):1975-1982.

［14］MAO Y B，CHEN G，LIAN S G.A novel fast image encryption scheme based on the 3D chaotic barker map［J］.Int.J.Bifurcat Chaos，2004，14(10):3613-3624.

［15］鄧紹江，濮忠良，張岱固.基于小波壓縮和混沌置亂的圖像處理算法［J］.重慶大學(xué)學(xué)報(bào)，2008，31(8):918-921.

［16］姜德雷.基于騎士巡游的圖像和視頻加密技術(shù)研究［D］.重慶:重慶通信學(xué)院，2009:61-62.