劉博文，柏 森，陽 溢，劉程浩

（1.重慶通信學院，重慶 400035；2.應急通信重慶市重點實驗室，重慶 400035）

1 引言

隨著計算機網絡技術和多媒體技術的飛速發(fā)展，數字圖像、視頻等多媒體在人們日常生活中的應用越來越多，并成為人們傳遞信息的主要工具。由于這些傳輸信息的媒體需要在開放的網絡環(huán)境中傳輸和分享，人們對數據量的大小、安全性等方面提出了更高要求。目前，對數據進行加密處理是保證多媒體信息安全傳輸的主要方法之一。傳統(tǒng)的數據加密經過復雜性較高的基于數論的運算操作，不能滿足多媒體信息巨大的數據量及實時性的需求。在圖像加密算法中，主要包括與壓縮獨立的加密算法[1～3]和結合壓縮技術的加密算法[4～6]。文獻[4]較早在DCT 變換域中實現了圖像加密壓縮，但加密后的系數不在原始系數的取值區(qū)間，且不能表示成2的冪次方的形式，無法簡單地用諸如異或運算等方式實現加密。文獻[5]解決了加密后的系數回到原始系數區(qū)間的問題，但效率較低，加密運算需要迭代次數過多，并且使用一維混沌序列加密后圖像的安全性不高。文獻[6]中提到的CWF算法在小波域中進行加密壓縮，但其破壞了小波變換的多尺度分解樹型結構，勢必影響圖像的可壓縮性。加密和壓縮兩種技術的有效結合將兼顧數據的安全性及傳輸效率，因此成為當前國內外研究的熱點。

針對多媒體信息數據量大和實時性需求的特點，提出一種基于廣義騎士巡游的RGB 圖像加密壓縮算法。將原始圖像分塊處理，以8×8的塊作為最小單位在變換域中進行置亂，將加密和壓縮有效地結合起來，使處理速度更快。在滿足一定安全性的前提下，壓縮效率得到提高。

2 廣義騎士巡游及加密原理

18世紀50年代末，著名數學家Euler首次提出了騎士巡游問題KTP（Knight's Tour Problem）。騎士巡游問題，起源于國際象棋，就是騎士（馬）從棋盤上的某個初始棋格開始，以跳“斜日”的方式跳遍棋盤上的每個棋格一次且僅一次的一種方案[7]，如圖1所示。

Figure 1 Schematic diagram of knight's tour圖1 騎士巡游示意圖

所謂廣義騎士巡游，有兩層含義：（1）棋盤是廣義的，即棋盤是m 維空間上任意形狀的棋盤；（2）騎士是廣義的，即騎士不再局限于“馬跳斜日”，而是滿足一定條件[8]下的任意跳法。三維棋盤示意圖如圖2所示。

Figure 2 Schematic diagram of 3D-chessboard圖2 三維棋盤示意圖

騎士的巡游只由少數幾個參數（騎士巡游起始位置、巡游規(guī)則等）控制。在三維棋盤上建立坐標系，將第一層棋盤左上角視為原點，棋盤上的每一格視為對應坐標系上一個點，則騎士巡游起始位置k1（x，y，z）表示騎士從第z 層棋盤上第x 行、第y列的棋格上開始移動。巡游規(guī)則k2[i，j，k]表示騎士每次移動的方法，即從起始位置的棋格在空間三個方向上分別跳i、j、k 個棋格，簡稱為[i，j，k]馬。騎士巡游的巡游路徑用騎士巡游矩陣T 來表示，例如一個8×8×3棋盤上[1，2.2]馬的廣義騎士巡游矩陣如圖3所示。其中，1表示騎士巡游的起點，192表示巡游的終點。基于騎士巡游的置亂加密基本原理就是將棋盤中位置1的元素移動到位置2，位置2的元素移動到位置3，以此類推，最后將位置192的元素移到位置1上。

Figure 3 Matrix representation of generalized knight's tour path圖3 [1，2.2]馬廣義騎士巡游矩陣

3 基于廣義騎士巡游的RGB圖像加密壓縮算法

3.1 算法思想

在采用JPEG 算法壓縮圖像的過程中，DCT變換以8×8的塊作為最小單元。為減少加密對壓縮的影響，考慮以塊為單位進行置亂加密。本文提出的算法將原始圖像的Y、Cb、Cr三層分別進行8×8分塊操作，對塊化后的每一塊進行DCT 變換得到一個系數塊化矩陣。將這個系數塊化矩陣中的每一塊視為棋盤上的棋格，按照騎士巡游規(guī)則對每塊進行移動，以實現圖像的加密。對加密后的數據進行JPEG 壓縮編碼后，就得到加密壓縮圖像。這樣，采用本文算法不僅使得每一小塊內依然具有原有的相關性，還可以保持較高的可壓縮性。

本文提出的加密壓縮流程如圖4所示。

3.2 算法步驟

設原始圖像為Im×n×3，加密后圖像為I′m×n×3，加密壓縮后圖像為I″m×n×3。本文加密壓縮算法過程如下：

（2）根據第2節(jié)的介紹，選擇起始位置k1（x，y，z）、巡游規(guī)則k2[i，j，k]作為初始密鑰，使用文獻[9]中的算法得到騎士巡游矩陣Tk×l×3。

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

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

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

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

4 實驗與分析

為驗證本文算法的有效性，本節(jié)以大小為256×256的Lena和Baboon 兩幅測試圖像為例，采用MATLAB 進行仿真實驗。實驗中起始位置都選取k1（1，1，1），初始密鑰由巡游規(guī)則k2決定。

4.1 直觀效果

采用[1，6，2.馬作為初始密鑰分別對測試圖像進行1次、2次、5次加密實驗，其加密壓縮效果分別如圖5和圖6所示。

Figure 5 Encryption and compression results of Lena圖5 Lena圖像加密壓縮效果圖

通過效果圖可以看出，以[1，6，2.馬作為密鑰，1次加密后的圖像效果并不十分理想，可以看出一些原始圖像輪廓，進行2次加密后就能得到較好的加密效果，且不同加密次數下加密效果接近。從直觀效果來看，基于廣義騎士巡游的圖像加密壓縮方案在加密效果上較理想。

4.2 置亂度

置亂度用來評估圖像被置亂或加密程度，即圖像加密的直觀效果好壞的重要指標，它能較為客觀地反映圖像的加密效果。目前，許多相關研究都給出了置亂度的定義，但又各不相同。本文引用文獻[10]定義的置亂度作為評價標準，其計算式為：

Figure 4 Flowchart of encryption and compression圖4 加密壓縮流程圖

Figure 6 Encryption and compression results of Baboon圖6 Baboon圖像加密壓縮效果圖

從表1可以清楚地看出，采用[1，6，2.馬加密后圖像在RGB三層上的置亂度都高于[1，2.2]馬和[1，4，2.馬的置亂度，其主要原因在于[1，6，2.馬的移動距離大于后兩者，使得相關性破壞更嚴重，加密效果更好。

隨著加密次數的增加，加密算法的置亂度也將隨之變化，采用[1，6，2.馬進行多次加密測試，其置亂次數與置亂度關系如圖7所示。

Figure 7 Relationship between times of scrambling and scrambling measure圖7 [1，6，2.馬置亂次數與置亂度關系圖

圖7中，隨著加密次數的增加，前3次的置亂度出現較大振蕩，但經過5次加密后，其置亂度維持在0.67～0.91，可視為穩(wěn)定。采用基于廣義騎士巡游的圖像加密壓縮算法，只需較少置亂次數就能達到置亂的效果，算法的效率高、處理速度快。

4.3 壓縮率

壓縮率作為圖像壓縮的一個評價指標，其計算式如式（2）所示：

在壓縮率測試中，對Lena圖像算法分別選擇[1，2.2]馬、[1，4，2.馬、[1，6，2.馬作為密鑰，經過1次加密后得到壓縮率如表2所示。

Table 2 Efficiency of compression圖2 壓縮效率

隨著加密次數的增加，其壓縮率也將隨之降低。采用[1，6，2.馬作為密鑰，進行多次加密后圖像的壓縮率如表3所示。

Table 3 Relationship of encryption times and compression圖3 加密次數與壓縮率

由表2和表3可以看出，采用基于廣義騎士巡游的RGB圖像加密壓縮算法得到的壓縮率較高，接近對原始圖像直接壓縮的壓縮率，并且隨著加密次數的增加，壓縮率緩慢下降。由于高壓縮率可以滿足現實生活中多媒體技術的需求，本文的算法具有很好的實用性。

4.4 密鑰敏感性測試

圖像加密要求具有較高的密鑰敏感性，即密鑰之間發(fā)生微小變化時，加密算法得到的效果是敏感的，這樣就能保證密碼系統(tǒng)針對窮舉攻擊、統(tǒng)計攻擊的安全性。本文采用[1，6，2.馬和[1，4，2.馬進行1次加密測試，其加密效果如圖8所示。

Figure 8 Experiment results of secret key's sensitivity圖8 密鑰敏感性測試

通過圖8可以看出，密鑰中坐標上移動2個單位的變換時，將導致加密圖像大部分發(fā)生改變，即產生了雪崩效應。因此，本文的加密壓縮算法對騎士巡游棋盤密鑰具有很高的敏感性，可以抵抗常見密碼攻擊和差分攻擊。

4.5 實時性分析

為檢測算法的時效性，本文采用50 幅256×256圖像樣本分別作測試，密鑰選取[1，6，2.馬，取運算時間的平均值作為本算法的有效運算時間，壓縮采用MATLAB 中imwrite函數實現，然后計算出平均壓縮率。實驗結果如表4所示。

Table 4 Relationship of times and compression圖4 運算時間與壓縮率

通過表4可以看出，基于廣義騎士巡游的圖像加密壓縮算法的運算時間較短，并且壓縮率較高。快速的運算時間可以滿足多媒體技術的需求，使得網絡上的信息傳輸效率更高。

5 結束語

本文提出了一種基于廣義騎士巡游的RGB圖像加密壓縮算法，經實驗證實，在保證傳輸信息較高安全性的前提下，獲得了較高的壓縮率。該算法可作為一種圖像的加密方法，將加密壓縮后的涉密圖像進行傳輸，較大程度提高了傳輸效率；也可作為進一步信息隱藏的預處理過程?；趶V義騎士巡游的圖像加密壓縮方法在多媒體信息化時代具有較強的實用性，更能夠滿足現實生活中信息安全的各種應用場合的需要。由于塊加密的局限性，本文算法只有對分辨率在256×256以上的圖像加密才能得到較好效果。如何解決還原圖像塊效應和在JPEG 2000壓縮標準下的加密壓縮算法是下一步研究的重點。

[1]Rhouma R，Meherzi S，Belghith S.OCML-based colour image encryption[J].Chaos，Solitons ＆ Fractals，2009，40（1）：309-318.

[2]Huang C K，Nien H H.Multi chaotic systems based pixel shuffle for image encryption[J].Optics Communications，2009，2.2（11）：2123-2127.

[3]Tian Yan，Xie Yu-bo，Li Tao，et al.An image scrambling method based on image blocking and chaos system[J].Journal of Image and Graphics，2007，12（1）：56-60.（in Chinese）

[4]Sun Xin，Yi Kai-xiang，Sun You-xian.New image encryption algorithm based on chaos system[J].Journal of Computer-Aided Design＆Computer Graphics，2002，14（2）：136-139.（in Chinese）

[5]Peng Cheng，Liu Lin.Encryption algorithm for compressed images based on chaotic sequences[J].Computer Engineering，2008，34（20）：177-179.（in Chinese）

[6]Ping Liang，Sun Jun，Zhou Jun.An algorithm for image encryption based on JPEG2000[J].Applieation＆Project of Video Technologies，2006，7（1）：87-90.（in Chinese）

[7]Parberry I.An efficient algorithm for the knight's tour problem[J].Discrete Applied Mathematics，1997，73（3）：251-260.

[8]Tao Ke.The problem about ND-knight move[J].Mathematics in Practice and Theory，1982（1）：26-31.（in Chinese）

[9]Sen Bai，Liao Xiao-feng，Qu Xiao-hong，et al.Generalized knight's tour problem and its solutions algorithm[C]∥Proc of the 2006International Conference on Computational Intel-ligence and Security，2006：570-573.（in Chinese）

[10]Chen G，Zhao X Y，Li J L.A self-adaptive algorithm on image encryption[J].Journal of Software，2005，16（11）：1975-1982.（in Chinese）

附中文參考文獻：

[3]田巖，謝玉波，李濤，等.一種基于分塊和混沌網的圖像置亂方法[J].中國圖象圖形學報，2007，12（1）：56-60.

[4]孫鑫，易開祥，孫優(yōu)賢.基于混沌系統(tǒng)的圖像加密算法[J].計算機輔助設計與圖形學學報，2002，14（2）：136-139.

[5]彭成，柳林.基于混沌序列的壓縮圖像加密算法[J].計算機工程，2008，34（20）：177-179.

[6]平亮，孫軍，周軍.一種基于JEPG2000標準的數字圖像加密算法[J].視頻技術應用與工程，2006，7（1）：87-90.

[8]陶克.關于n維馬步問題[J].數學的實踐與認識，1982（1）：26-31.

[9]柏森，廖曉峰，曲曉紅，等.廣義騎士巡游問題與它的解決算法[C]∥2006 年國際計算智能與信息會議論文集，2006：570-573.

[10]陳剛，趙曉宇，李均利.一種自適應的圖像加密算法[J].軟件學報，2005，16（11）：1975-1982.