基于Arnold變換的改進騎士巡游圖像加密算法*

蘭 紅，方 毅

（江西理工大學 信息工程學院，江西 贛州 341000）

0 引 言

圖像加密是指在密鑰和加密函數的共同作用下，將一幅有意義的圖像轉變?yōu)殡s亂無章的無意義圖像，從而使原始圖像所要表達的真實信息無法被直觀感知和察覺。圖像加密算法主要可以分為：基于空間域的像素置亂、基于現代密碼體制的圖像加密、基于混沌的加密、基于變換域的加密、基于神經網絡和元胞自動機的加密、基于壓縮的加密和基于盲源分離的加密等[1]?；诳臻g域像素置亂的基本思想，是把一幅圖像經過一系列數學變換，破壞圖像中原有的空間有序性和局部相關性，把圖像變得雜亂無章、無法識別，使圖像呈現出一種類似噪聲的形式。騎士巡游圖像加密算法[1]屬于空間域像素置亂方法中的一種，具有密鑰空間大、密鑰敏感性強等優(yōu)點，近年來受到了普遍關注，并成為圖像加密應用領域的研究熱點[2-6]。

騎士巡游算法采用“試探-回溯”方法構建巡游矩陣，時間復雜度較大，有文獻對其進行改進。文獻[2]采用“智能試探-智能回溯”算法構建騎士巡游矩陣，但需要多次迭代加密才能取得滿意的加密效果。文獻[3]對圖像進行騎士巡游置亂后局部信息得到了隱藏，但原圖像內容的整體輪廓信息依然清晰，全局加密性不高。文獻[4]提出了騎士巡游改進置亂算法，但變換前后灰度直方圖一樣。文獻[5]采用分塊處理，將圖像分塊后再利用騎士巡游矩陣對其進行置亂，但加密圖像顯示塊效應明顯。文獻[6]提出騎士巡游結合位運算的數字圖像加密算法，取得了較好的加密效果，但是其使用的騎士巡游矩陣是與原圖大小相同的矩陣，沒有降低時間復雜度。本文結合文獻[5-6]的改進思想，提出了一種基于Arnold變換的改進騎士巡游圖像加密算法，降低了傳統騎士巡游算法的時間復雜度，提升了加密效果。

1 騎士巡游算法

1.1 騎士巡游算法的基本原理

騎士巡游即騎士在棋盤中的巡游，其行動軌跡和中國象棋中馬一樣，走“日”字。設(x,y)為騎士在棋盤上的起始位置，巡游規(guī)則用K(i, j)表示，其中i和j分別表示騎士在水平和垂直方向上跳的棋格數。在傳統騎士巡游算法中，騎士只能走日字。所以，i、j的取值為{1，2}。若i=1, j=2，則巡游規(guī)則為K(1,2)，表明下一步騎士有可能巡游到的位置為 (x-1,y-2)、(x-1,y+2)、(x+1,y-2)和 (x+1,y+2)； 反之，若i=2, j=1，則巡游規(guī)則為K(1,2)，表明下一步騎士有可能巡游到的位置為(x-2,y-1)、(x-2,y+1)、(x+2,y-1)、(x+2,y+1)。

騎士巡游算法的目的是找出一條最優(yōu)巡游路徑，使得騎士可以不重復地巡游到棋盤上的每一個格子。騎士巡游求解最優(yōu)路徑的“試探-回溯”算法的求解過程如下：

（1）定義出路數m：表示下一步在棋盤內共有m個沒有巡游到的格子可供選擇；

（2）初始值設置：設騎士當前位置為(x,y)，下一步要到達的位置為(x1,y1)，其中(x1,y1)默認為(x+2,y-1)；如果(x1,y1)的出路數m為0，則下一步位置按照逆時針規(guī)則進行選擇，即為(x+1,y-2)，以此類推。

（3）尋找當前位置所能到達的所有下一步位置(x1,y1)，并找出位置(x1, y1)的最小出路數m，設其為min；

（4） 若 min=0， 則 回 溯 一 步 至 (x,y)； 若min≠0，則騎士巡游到下一個位置為(x1,y1)；

（5）重復（3）、（4）操作，直至找出一條完整的騎士巡游路徑。

對于一幅數字圖像而言，像素點相當于騎士，而圖像本身就是棋盤。按照騎士巡游的規(guī)則移動像素點的位置，就可對圖像進行置亂加密。

圖1（a）所示是一幅8×8的騎士巡游矩陣，T=[t(i, j)]8×8，T中1表示像素的起始位置，2、3、4…表示按照巡游規(guī)則得出的下一步移動位置。騎士巡游加密的基本原理為：圖像1位置的像素信息移動到位置2，圖像2位置的像素信息移動到位置3，依次移動像素點的位置，最后將圖像64位置的像素信息移動到位置1。圖1（b）是與圖1（a）對應的完整的騎士巡游路徑。

圖1 騎士巡游算法

1.2 騎士巡游算法存在的不足

騎士巡游加密算法能夠實現圖像的加密，但也存在以下三個方面不足。

（1）時間復雜度高。騎士巡游算法的核心是采用“試探-回溯”算法求解騎士巡游的下一步，由于每一步試探都有8個可能的點，對于M×N的矩陣，該算法的時間復雜度為O(8M×N-1)，為指數級，影響加密效率。

（2）加密圖與原圖相似。騎士巡游算法對像素點的置亂是在相鄰的幾行或者幾列進行，局部置亂效果明顯，全局效果欠佳。如圖2（a）的rice圖，圖2（b）是對其采用騎士巡游算法得到的加密圖，直觀上看，加密后的圖像與原圖有很大相似性，單純使用騎士巡游算法加密圖像，整體加密效果不佳。

（3）加密圖像的灰度直方圖和與原圖的灰度直方圖相同。騎士巡游算法只是改變了像素點的空間位置，而像素點的值并沒有發(fā)生改變，因而加密圖像和原圖像的灰度直方圖是一樣的，如圖2（c）和圖2（d）所示，使得加密圖像易被破解，降低了算法的安全性。

圖2 騎士巡游加密圖及其直方圖

2 基于Arnold變換的改進騎士巡游算法

2.1 算法改進的基本思想

針對騎士巡游加密算法在上述三個方面的不足，本文提出基于Arnold變換的改進騎士巡游圖像加密算法。第一，采用將圖像拆分和優(yōu)化騎士巡游算法來降低時間復雜度；第二，引入Arnold變換，提升圖像整體加密性；第三，引入位運算，改變像素值，提升算法加密的安全性。

2.2 Arnold變換

Arnold變換[7]是一種基于矩陣變換的圖像置亂算法。變換原理是先對像素點作x軸方向的錯切變換，再作y軸方向的錯切變換，最后做模運算。通過這一過程可以將圖像內的離散像素點重新排列。對于一個N×N型的矩陣，其Arnold變換及逆變換為：

其中(x,y)是原圖像的像素點的坐標位置，(x', y')是變換后圖像的像素點坐標位置，a和b表示的是模板參數，n表示的是Arnold變換的次數，N表示矩陣大小。Arnold變換主要針對方陣進行置亂。

2.3 改進算法的實現步驟

根據算法的改進思想，算法實現主要包括以下五步。

步驟1：圖像預處理，將M×N圖像轉換為M×M圖像。

設原圖像大小為M×N，因Arnold變換只應用于方陣，將原圖像轉換為方陣。若M＞N，則將圖像以0或255補齊為M×M；反之，補齊為N×N。本文所取圖像默認M＞N。

步驟2：圖像分解，原圖像劃分成m×m的胞元數組。

將M×M的圖像矩陣分割成m×m的胞元數組，此時胞元數組內的像素點個數為(M/m)×(M/m)，本文取m=8。

步驟3：局部置亂變換，即對每個胞元數組內部做Arnold變換。

為降低對原圖像整體做騎士巡游算法的時間復雜度，采用Arnold變換和騎士巡游相結合的方法。首先對每一個胞元數組做Arnold變換，根據式（1），模板參數選擇文獻[7]中的a=1,b=1，得到：

其中方陣規(guī)模為M/8。

步驟4：整體圖像加密，采用“分治-回溯-合并”的改進騎士巡游算法對圖像整體加密。

針對傳統騎士巡游采用“試探-回溯”算法效率不高的不足，采用文獻[8]提出的“分治-回溯-合并”算法確定騎士巡游路徑，將每個胞元數組當作一個元素，轉換成包含m×m個元素的矩陣，對其進行騎士巡游變換。

“分治-回溯-合并”算法的思想是首先將矩陣規(guī)模為r的矩陣分割成如5×5、7×7的小矩陣，然后采用回溯算法求各小矩陣的騎士巡游路徑，最后連接各小矩陣的騎士巡游路徑，合并成為r×r矩陣的騎士巡游路徑。該算法的時間復雜度為O(n2)[8]。

步驟5：位運算改變灰度直方圖，提升圖像加密安全性。

灰度圖像像素點的取值范圍為0～255，可以將像素點值轉化成8位的二進制數。為提升圖像加密的安全性，改變加密后圖像的灰度直方圖，將上述置亂后的胞元數組轉換為矩陣元素，重新生成M×M的圖像矩陣，實行位運算。

位運算的具體操作包括兩步：

（1）像素點異或運算。設I為經算法前4步的初步加密圖像，矩陣大小為M×M，I(i, j)表示圖像內的像素點。異或算法描述如算法1所示。

算法1：異或運算算法

for i=1:M

for j=1:N

// I(i,j)與右邊第一個點異或

I'(x,y)=bitxor(I(i,j),I(i+1,j));

end

end

（2）位平面交換。圖像內的所有像素點做完位異或運算后，提取出圖像的8個位平面，然后做位平面交換操作。本文算法采用的位平面交換規(guī)則為R={8，4，7，2，6，5，3，1}，表示的是第1位平面與第8位平面交換，第2位平面與第4位平面交換，以此類推。

2.4 改進算法的解密算法

解密過程是加密過程的逆操作。首先對M×M的加密圖像做逆位運算（加密算法步驟5的逆操作），然后矩陣劃分為m×m的胞元數組，對胞元數組做逆騎士巡游變換；接著對每一個胞元數組內部做Arnold逆變換，最后m×m的胞元數組還原為M×M的解密圖像，將原先補齊的邊界像素點去除，得到最終的M×N解密圖。

3 改進算法的整體流程

解密過程是加密過程的逆操作。給出改進算法的加密流程圖，如圖3所示。

4 實驗及算法分析

為證明本文改進算法的有效性，分別選取灰度圖像和彩色圖像，在處理器為Intel（R） Core（TM）i5-4210U 1.70GHz的Windows 7操作系統下，采用MATLAB R2014a仿真軟件平臺進行實驗仿真，并分別與文獻[5-6]進行對比。其中，文獻[6]的算法應用于灰度圖像，文獻[5]的算法應用于彩色圖像。

算法初始參數設置：騎士巡游起始位置為（5，4），巡游規(guī)則為K(1,2)和K(2,1)，選擇像素點右邊的點與像素點做按位異或運算，位平面的交換規(guī)則R={8，4，7，2，6，5，3，1}。

圖3 算法加密流程

4.1 實驗結果

圖4 （a）和圖4（e）分別是大小為256×256的灰度圖像lena圖和512×512的WALL.E圖，圖4（b）和圖4（f）分別是傳統騎士巡游加密算法對lena圖和WALL.E圖的加密圖，圖4（c）和圖4（g）分別是文獻[6]算法對lena圖和WALL.E圖的加密圖，圖4（d）和圖4（h）分別是本文改進算法對這兩個灰度圖像的加密圖?？梢钥闯觯紙D像的尺寸大小并沒有對本文加密算法的效果產生影響。直觀上，使用文獻[6]算法和本文改進算法的加密圖像和噪聲無異，比較傳統騎士巡游加密算法的加密效果有了明顯提升，都在視覺上取得了很好的置亂效果。

圖4 灰度圖像加密效果圖

4.2 算法分析

4.2.1 時間復雜度分析

算法的時間復雜度反映了程序執(zhí)行時間隨輸入規(guī)模增長而增長的量級，很大程度上能很好地反映算法的優(yōu)劣。文獻[5-6]算法并沒有對騎士巡游路徑進行改進，這兩種算法的時間復雜度仍然是指數級的。本文的改進算法通過優(yōu)化騎士巡游算法、圖像劃分胞元數組的操作，時間復雜度得到了優(yōu)化，算法第3步～第5步的時間復雜度均為O(n2)，其余步驟的時間復雜度都是常數級，故本文算法的時間復雜度為O(n2)，相較本文算法的時間復雜度得到了極大優(yōu)化。

4.2.2 安全性分析

（1）像素點信息的改變。騎士巡游變換和Arnold變換改變了圖像內像素點的空間位置，算法第5步使用位運算后，改變了像素點的值。圖5（a）和圖5（c）表示的是未經加密圖像的灰度直方圖，圖5（b）和圖5（d）表示的是采用本文算法加密后圖像的灰度直方圖?？梢钥闯?，經過改進算法加密后的圖像的灰度直方圖與原圖有明顯區(qū)別，彌補了加密圖灰度直方圖和原圖一致的缺陷。

（2）密鑰空間大，能有效抵抗密鑰窮盡攻擊。本文算法將圖像分成8×8的胞元數組，采用騎士巡游加密算法對其進行加密，理論上騎士巡游路徑的個數約為3.019×1022個[6]。

（3）密鑰敏感性強，不易被解密。圖6（a）是本文采用本文改進算法的WALL.E加密圖，對該加密圖進行解密。圖6（b）是位運算規(guī)則R正確、騎士巡游的參數不正確的解密圖，即初始位置和巡游規(guī)則錯誤，解密后的圖像完全看不出原圖的痕跡，圖6（c）是位運算規(guī)則R錯誤、騎士巡游的參數正確的解密圖，解密后的圖像與隨機噪聲在直觀上是一致的。經過大量試驗證明，當位運算規(guī)則R和騎士巡游的參數有所改變時，得到的解密圖和正確解密圖直觀上無任何關聯?？梢姡疚乃惴ㄔ诶碚摵蛯嵺`中具有很高的安全性。

圖6 算法錯誤和正確解密

4.2.3 置亂度分析

置亂度（SM）是用來評估圖像被置亂或加密程度的一個指標，能夠很好地體現出一幅數字圖像的加密效果。本文引用文獻[9]中定義的置亂度來評估圖像的置亂程度，計算式為：

式（4）中，X代表原始圖像，X '表示加密圖像，R={rij}m×n表示與原始圖像相同大小的均勻分布噪聲圖像。使用256×256的灰度圖像lena圖為例，分別求出加密一次和三次的置亂度。因文獻[5]是對RGB圖像加密的，故取其置亂效果最好的R分量作為對比參數，得到了如表1所示的實驗結果。

表1 加密圖像置亂度分析

由表1可以看出，本文算法的置亂度相比較于文獻[5-6]算法有所提高，最低分別提高了0.334 6和0.344 9，表明本文算法在置亂度上要優(yōu)于以上兩個算法，更好地破壞了圖像像素點之間的相關性。

5 結 語

本文提出的基于Arnold變換的改進騎士巡游圖像加密算法，采用劃分胞元數組和優(yōu)化騎士巡游路徑等方法，降低了算法的時間復雜度，通過胞元數組內部做Arnold變換提升了算法的整體加密，然后結合位運算，解決了騎士巡游加密后的圖像灰度直方圖與原圖一致的問題。通過對實驗結果及算法的分析，證明了本文改進算法具有時間復雜度低、整體加密性良好的特性。在圖像信息加密越來越被重視的今天，該算法的簡單有效性具有很好的運用空間。