基于Arnold变换的改进骑士巡游图像加密算法*

兰 红，方 毅

（江西理工大学 信息工程学院，江西 赣州 341000）

0 引 言

图像加密是指在密钥和加密函数的共同作用下，将一幅有意义的图像转变为杂乱无章的无意义图像，从而使原始图像所要表达的真实信息无法被直观感知和察觉。图像加密算法主要可以分为：基于空间域的像素置乱、基于现代密码体制的图像加密、基于混沌的加密、基于变换域的加密、基于神经网络和元胞自动机的加密、基于压缩的加密和基于盲源分离的加密等[1]。基于空间域像素置乱的基本思想，是把一幅图像经过一系列数学变换，破坏图像中原有的空间有序性和局部相关性，把图像变得杂乱无章、无法识别，使图像呈现出一种类似噪声的形式。骑士巡游图像加密算法[1]属于空间域像素置乱方法中的一种，具有密钥空间大、密钥敏感性强等优点，近年来受到了普遍关注，并成为图像加密应用领域的研究热点[2-6]。

骑士巡游算法采用“试探-回溯”方法构建巡游矩阵，时间复杂度较大，有文献对其进行改进。文献[2]采用“智能试探-智能回溯”算法构建骑士巡游矩阵，但需要多次迭代加密才能取得满意的加密效果。文献[3]对图像进行骑士巡游置乱后局部信息得到了隐藏，但原图像内容的整体轮廓信息依然清晰，全局加密性不高。文献[4]提出了骑士巡游改进置乱算法，但变换前后灰度直方图一样。文献[5]采用分块处理，将图像分块后再利用骑士巡游矩阵对其进行置乱，但加密图像显示块效应明显。文献[6]提出骑士巡游结合位运算的数字图像加密算法，取得了较好的加密效果，但是其使用的骑士巡游矩阵是与原图大小相同的矩阵，没有降低时间复杂度。本文结合文献[5-6]的改进思想，提出了一种基于Arnold变换的改进骑士巡游图像加密算法，降低了传统骑士巡游算法的时间复杂度，提升了加密效果。

1 骑士巡游算法

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

骑士巡游即骑士在棋盘中的巡游，其行动轨迹和中国象棋中马一样，走“日”字。设(x,y)为骑士在棋盘上的起始位置，巡游规则用K(i, j)表示，其中i和j分别表示骑士在水平和垂直方向上跳的棋格数。在传统骑士巡游算法中，骑士只能走日字。所以，i、j的取值为{1，2}。若i=1, j=2，则巡游规则为K(1,2)，表明下一步骑士有可能巡游到的位置为 (x-1,y-2)、(x-1,y+2)、(x+1,y-2)和 (x+1,y+2)； 反之，若i=2, j=1，则巡游规则为K(1,2)，表明下一步骑士有可能巡游到的位置为(x-2,y-1)、(x-2,y+1)、(x+2,y-1)、(x+2,y+1)。

骑士巡游算法的目的是找出一条最优巡游路径，使得骑士可以不重复地巡游到棋盘上的每一个格子。骑士巡游求解最优路径的“试探-回溯”算法的求解过程如下：

（1）定义出路数m：表示下一步在棋盘内共有m个没有巡游到的格子可供选择；

（2）初始值设置：设骑士当前位置为(x,y)，下一步要到达的位置为(x1,y1)，其中(x1,y1)默认为(x+2,y-1)；如果(x1,y1)的出路数m为0，则下一步位置按照逆时针规则进行选择，即为(x+1,y-2)，以此类推。

（3）寻找当前位置所能到达的所有下一步位置(x1,y1)，并找出位置(x1, y1)的最小出路数m，设其为min；

（4） 若 min=0， 则 回 溯 一 步 至 (x,y)； 若min≠0，则骑士巡游到下一个位置为(x1,y1)；

（5）重复（3）、（4）操作，直至找出一条完整的骑士巡游路径。

对于一幅数字图像而言，像素点相当于骑士，而图像本身就是棋盘。按照骑士巡游的规则移动像素点的位置，就可对图像进行置乱加密。

图1（a）所示是一幅8×8的骑士巡游矩阵，T=[t(i, j)]8×8，T中1表示像素的起始位置，2、3、4…表示按照巡游规则得出的下一步移动位置。骑士巡游加密的基本原理为：图像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）加密图像的灰度直方图和与原图的灰度直方图相同。骑士巡游算法只是改变了像素点的空间位置，而像素点的值并没有发生改变，因而加密图像和原图像的灰度直方图是一样的，如图2（c）和图2（d）所示，使得加密图像易被破解，降低了算法的安全性。

图2 骑士巡游加密图及其直方图

2 基于Arnold变换的改进骑士巡游算法

2.1 算法改进的基本思想

针对骑士巡游加密算法在上述三个方面的不足，本文提出基于Arnold变换的改进骑士巡游图像加密算法。第一，采用将图像拆分和优化骑士巡游算法来降低时间复杂度；第二，引入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，得到：

其中方阵规模为M/8。

步骤4：整体图像加密，采用“分治-回溯-合并”的改进骑士巡游算法对图像整体加密。

针对传统骑士巡游采用“试探-回溯”算法效率不高的不足，采用文献[8]提出的“分治-回溯-合并”算法确定骑士巡游路径，将每个胞元数组当作一个元素，转换成包含m×m个元素的矩阵，对其进行骑士巡游变换。

“分治-回溯-合并”算法的思想是首先将矩阵规模为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个位平面，然后做位平面交换操作。本文算法采用的位平面交换规则为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），巡游规则为K(1,2)和K(2,1)，选择像素点右边的点与像素点做按位异或运算，位平面的交换规则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）分别是本文改进算法对这两个灰度图像的加密图。可以看出，原始图像的尺寸大小并没有对本文加密算法的效果产生影响。直观上，使用文献[6]算法和本文改进算法的加密图像和噪声无异，比较传统骑士巡游加密算法的加密效果有了明显提升，都在视觉上取得了很好的置乱效果。

图4 灰度图像加密效果图

4.2 算法分析

4.2.1 时间复杂度分析

算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，很大程度上能很好地反映算法的优劣。文献[5-6]算法并没有对骑士巡游路径进行改进，这两种算法的时间复杂度仍然是指数级的。本文的改进算法通过优化骑士巡游算法、图像划分胞元数组的操作，时间复杂度得到了优化，算法第3步～第5步的时间复杂度均为O(n2)，其余步骤的时间复杂度都是常数级，故本文算法的时间复杂度为O(n2)，相较本文算法的时间复杂度得到了极大优化。

4.2.2 安全性分析

（1）像素点信息的改变。骑士巡游变换和Arnold变换改变了图像内像素点的空间位置，算法第5步使用位运算后，改变了像素点的值。图5（a）和图5（c）表示的是未经加密图像的灰度直方图，图5（b）和图5（d）表示的是采用本文算法加密后图像的灰度直方图。可以看出，经过改进算法加密后的图像的灰度直方图与原图有明显区别，弥补了加密图灰度直方图和原图一致的缺陷。

（2）密钥空间大，能有效抵抗密钥穷尽攻击。本文算法将图像分成8×8的胞元数组，采用骑士巡游加密算法对其进行加密，理论上骑士巡游路径的个数约为3.019×1022个[6]。

（3）密钥敏感性强，不易被解密。图6（a）是本文采用本文改进算法的WALL.E加密图，对该加密图进行解密。图6（b）是位运算规则R正确、骑士巡游的参数不正确的解密图，即初始位置和巡游规则错误，解密后的图像完全看不出原图的痕迹，图6（c）是位运算规则R错误、骑士巡游的参数正确的解密图，解密后的图像与随机噪声在直观上是一致的。经过大量试验证明，当位运算规则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，表明本文算法在置乱度上要优于以上两个算法，更好地破坏了图像像素点之间的相关性。

5 结 语

本文提出的基于Arnold变换的改进骑士巡游图像加密算法，采用划分胞元数组和优化骑士巡游路径等方法，降低了算法的时间复杂度，通过胞元数组内部做Arnold变换提升了算法的整体加密，然后结合位运算，解决了骑士巡游加密后的图像灰度直方图与原图一致的问题。通过对实验结果及算法的分析，证明了本文改进算法具有时间复杂度低、整体加密性良好的特性。在图像信息加密越来越被重视的今天，该算法的简单有效性具有很好的运用空间。