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

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

(1.重慶通信學院應急通信重慶市重點實驗室，重慶 400035;2.西南醫院健康體檢中心，重慶 400050)

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

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

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

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

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

圖1 騎士巡游示意圖

經多年來的研究表明，騎士巡游在圖像加密上的應用［9-10］效果非常好。筆者在騎士巡游置亂加密圖像的基礎上，將加密與壓縮結合，研究新的圖像加密壓縮算法。

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

2.1 算法思想

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

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

2.2 原理與步驟

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

圖2 加密壓縮流程圖

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

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

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

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

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

解密是上述過程的逆過程。

3 算法仿真與評價

3.1 直觀效果

通過對256×256的Lena和Baboon兩幅測試圖像進行5 次循環加密實驗，設置初始密鑰 k1(1，1)，k2［1，2］和k1(1，2)，k2［1，4］，其加密壓縮效果分別如圖3 和圖4。

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

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

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

3.2 置亂度

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

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

表1 加密后圖像的置亂度

為了提高算法的壓縮率，采用了塊化操作，這使得加密置亂的單位是8×8塊而不是單個像素，從而導致加密的置亂度有一定下降，可通過增加循環加密次數來解決置亂度較低的問題。

3.3 壓縮率

壓縮率作為圖像壓縮的一個評價指標，其計算式為

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

表2 壓縮效率比較

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

表3 加密次數與壓縮率

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

3.4 安全性分析

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

表4 騎士巡游矩陣數量統計表［16］

結果表明，對于一個8×8的棋盤，其擁有的騎士巡游矩陣的數量至少3.019×1022個。由于人眼可以分辨其內容的圖像大小一般為50×50以上，所以用騎士巡游矩陣作為圖像加密的密鑰，其密鑰量將會是個天文數字。換個角度來說，用騎士巡游矩陣作為密鑰時，其密鑰空間足夠大。

圖像加密還要求較高的密鑰敏感性，即密鑰之間發生變化時，就能夠導致解密失敗。這樣就能保證密碼系統針對窮舉攻擊、統計攻擊的安全性。這里使用初始密鑰k1(1，1)，k2［1，2］進行一次圖像加密，分別用密鑰 k1(1，2)，k2［1，2］和 k1(1，1)，k2［1，4］解密 Lena 圖像，其解密效果如圖5所示。

圖5 Lena圖像解密效果圖

仿真實驗表明，騎士巡游矩陣的密鑰發生變化時，就無法正確解密出原始圖像。因此，本文的加密壓縮算法對騎士巡游棋盤密鑰具有很好的敏感性。

4 結束語

本文提出的一種基于騎士巡游的圖像加密壓縮算法，實現了具有加密效果較好、密鑰空間大、密鑰敏感性強等優點的加密壓縮方法。通過在變換域中使用騎士巡游塊置亂加密，在保證一定安全性的前提下，降低了加密對壓縮效率的影響。經實驗證實將加密和壓縮相結合，既能保證傳輸涉密圖像的安全性，又能大大提高存儲和傳輸效率。在圖像信息的發布與交流越來越普及的今天，該方法具有很好的應用前景。

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

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

［3］孫鑫，易開祥，孫優賢.基于混沌系統的圖像加密算法［J］.計算機輔助設計與圖形學學報，2002，14(2):136-139.

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

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

［6］平亮，孫軍，周軍.一種基于JEPG2000標準的數字圖像加密算法［J］.電視技術，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］柏森，曹長修.一種新的數字圖像置亂隱藏算法［J］.計算機工程，2001，27(11):18-19.

［10］姜德雷，柏森，董文明.基于廣義騎士巡游的圖像比特位平面間置亂算法［J］.自然科學進展，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］侯啟檳，楊小帆，王陽生，等.一種基于小波變換和騎士巡游的圖像置亂算法［J］.計算機研究與發展，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］.重慶大學學報，2008，31(8):918-921.

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