一种基于四方定理与幻方的矩形图像置乱方法*

李向军,喻 鹏,刘伯成,袁凌利

(1.南昌大学软件学院,江西 南昌 330046；2.南昌大学数学与计算机学院,江西 南昌 330031)

1 引言

当前互联网和多媒体系统的快速兴起导致了文字、图像和视频等内容快速激增，与此同时，海量数据的安全性却受到极大挑战。保护用户隐私、提升数据安全性越来越受到各方重视。

图像具有数据量大、信息冗余度高以及相邻像素间相关性强等固有特点。传统文本加密方式，例如数据加密标准DES、高级加密标准AES 、RSA和椭圆曲线加密ECC等[1 - 4]在保障数字图像安全传输与存储方面缺乏足够的速度和能力，直接将现有加密体制用于图像加密是不合适的。因此，大量基于不同技术的图像加密算法被研究人员提出，以缓解上述问题。

图像置乱是实现图像加密的一种重要手段，它能将一幅自然图像通过特定数学规则改变像素位置关系或像素值，使其变得杂乱无章无法识别,从而掩盖内容。尽管研究人员提出了大量图像置乱算法，但较少关注算法的变尺度置乱能力，在处理非等长的矩形图像时，这些算法并不能很好地发挥作用。

本文主要贡献在于：采用基于四方定理的图像分块规则，有效解决了已有算法变尺度置乱能力不足的问题。同时，引入分块置乱、拼接、转置以及改变形状等操作，显著降低了相邻像素的相关性，置乱程度获得了提高。仿真结果表明了本文算法的有效性和安全性，能对矩形图像进行置乱与恢复，置乱效果良好，具有一定的可扩展性。

2 相关工作

研究人员提出了许多图像加密算法[5 - 7]，主要分为7类，包括基于现代加密体制的图像加密算法[8]、基于神经网络的图像加密算法[9]、基于混沌的图像加密算法[10]、基于压缩的图像加密算法[11]、基于盲源分离的图像加密算法[12]、基于变换域的图像加密算法[13]和基于置乱的图像加密算法。

置乱以其研究的广泛性、使用的灵活性及加解密的高效性在图像加密应用中受到青睐。置乱最早起源于经典的加密理论和电视图像应用技术，主要用于加密图像内容和作为信息隐藏预处理。Arnold变换[14]、拼图变换、灰度变换、斐波那契变换[15]、格雷码、元胞自动机、幻方变换[16，17]、约瑟夫环变换[18]、混沌映射[19]、骑士巡游[20 - 22]及面包师变换是图像加密中比较常用的图像置乱算法，都具有实现简单和处理速度快等特点。其缺点亦较为明显，变尺度置乱能力较差，通常受限于图像固定的尺度空间，一般而言只能加密正方形图像

为克服上述算法变尺度置乱能力不足的缺点，研究人员进行了大量改进。孔涛等[23]对矩形图像填充部分行或者列，将其扩充为正方形；陈曦等[24]通过插值调整图像为正方形，但可能导致图像内容发生形变；胡薇薇等[25]将基于迭代函数系统的图像置乱方法由2n×2n拓展为N×N。然而这些处理方法会增加计算量与存储空间。上述研究从改变图像形状入手，还有一些研究从修改算法以适应图像角度展开。Qi等[26]提出用多维等长Arnold变换和Fibonacci-Q变换处理非等长图像，不需进行扩充等操作；Yang等[27]提出基于Arnold变换对称性的数字图像置乱技术，将L×H(L≥H)图像划分成多个H×H正方形图像块进行置乱，之后再还原为原始图像大小；邵利平等[28]提出二维非等长的Arnold置乱算法，适用于矩形图像；李永逵等[29]找到并证明了对任意高宽的数字图像都存在置乱变换周期的变换矩阵，可广泛应用于对任意尺寸数字图像的置乱变换过程；吴成茂[30]提出将二维非等长 Arnold 变换进行非仿射化修改,获得一种具有非线性变换特性的保面积且具有周期的置乱变换；Hu等[31]采用三维Hilbert曲线，将其基本单元扩展后应用于矩形图像置乱，避免了图像扩展缺陷的同时增强了置乱效果。这些算法通常基于Arnold进行改进，虽然没有增加传输加密图像的负载，但算法实现较为复杂，且推广至其他算法存在困难。常用的解决方法是将图像进行分块，然而问题并未妥善解决。当图像长与宽的比值不为整数时，如不加密剩余部分则可能会导致信息泄露，若在图像边缘填充零再加密，则会改变图像大小，在进行统计分析时容易被发现[21]。四方定理[32]为该问题的解决提供了便利，它能对任意大小的矩形图像分块且图像块正好为正方形，而正方形图像块能被幻方、骑士巡游、Arnold等方法置乱。因此，本文结合四方定理和幻方置乱，对矩形图像置乱的问题进行研究。

3 基于四方定理与幻方的矩形图像置乱算法

基于四方定理与幻方的矩形图像置乱算法的核心思路为：首先利用四方定理将矩形图像分为4个正方形图像块，解决幻方置乱算法局限于固定尺度的问题。再对各块进行幻方置乱、拼接，将图像恢复为原始图像大小。在整个算法中，采用转置、改变形状、多次置乱的方式，进一步提高幻方置乱程度，增强置乱效果。

3.1 基于四方定理的图像分块方法

四方定理可将一个自然数分解为4个自然数的平方和，如下所示。

四方定理设有一个自然数N，存在4个正整数a,b,c,d，满足式(1)：

N=a2+b2+c2+d2

(1)

四方定理的分解并不唯一，例如:

211=82+72+72+72=112+72+52+42

四方定理用于图像分块时，和其他预处理方法相比，优势在于能将图像分为4个正方形图像块且复杂度较小。图1为基于四方定理的图像分块方法示意图。先对像素总数N进行分解，再取对应数量的像素，即可实现分块。

Figure 1 Image block based on the four-square theorem图1 基于四方定理的图像分块

3.2 基于幻方的置乱规则

3.2.1 幻方定义与性质

幻方性质特殊，其数学定义为：n阶幻方的各行、各列和对角线的数字之和正好相等[33]，其值S=n(n2+1)/2称为幻和。

根据阶数特点，若n为奇数，则称该幻方为奇数阶幻方；若n为偶数，则可分为单偶数阶幻方和双偶数阶幻方2种情况，前者n=4k+2,k=0,1,2,…，后者n=4k,k=1,2,…。

3.2.2 幻方的生成

3种幻方生成方法[33]并不同。通常，奇数阶幻方构造算法有楼梯法[34]、loubere法、错位补角法及马步法[35]；双偶数阶幻方构造算法有Spring法[36]、环形平移补空法及Strachey法；单偶数阶幻方构造算法有Strachey法[37]。注意，不同幻方生成算法获得的幻方存在差异，因而本文为确保幻方的唯一性，采用loubere法生成奇数阶幻方，采用Strachey法生成单偶数阶幻方，采用Spring法生成双偶数阶幻方。

3.2.3 基于幻方的图像置乱规则

幻方置乱的缺陷在于：无法处理高与宽不等的矩形图像；置乱参数较少，加密密钥空间较小；经过多次幻方变换迭代后的图像，相邻像素之间仍然存在较强的相关性，算法安全性明显降低[17]。为增强置乱效果，有研究人员尝试将幻方置乱与其他一些技术如分块压缩感知[17]、信息光学技术[38]和位运算[39,40]结合。

假设灰度图像大小为n×n，记为In×n。传统幻方置乱算法[39]将图像In×n与n阶幻方A的行列一一对应后，按照式(2)进行变换。

(2)

即得到变换矩阵A1，将In×n中元素相应移动得到置乱一次的图像。同理可得到Ai(i为迭代变换次数)。不难发现，传统幻方置乱算法存在置乱周期，置乱n2次后恢复为原始图像，此时置乱失效，算法安全性降低。

3.3 FMSS算法

本文提出了一种四分块幻方置乱FMSS(Four-block Magic Square Scrambling) 算法，其思路如下：设原始图像大小为H×W，像素总数可分解为a,b,c和d4个整数的平方和。根据排列组合共有4!=24种分块方式，默认使用(a2,b2,c2,d2)组合。接着生成所需幻方，对各个图像块进行幻方置乱，再将块拼接恢复成H×W的图像。常用的多次置乱方法有2种:(1)直接在分块的基础上继续进行置乱再拼接；(2)在图像块置乱后，拼接成原始大小的图像，将其转置并改变形状(reshape),使其恢复为原始大小，再进行分块置乱。由于方法(2)通过转置和改变形状使像素在多次置乱中被分配至不同图像块中，从而打破了图像块之间的壁垒，可充分进行置乱，进而消除块效应[41]。为增强安全性及置乱效果，本文采用方法(2)进行多次置乱。最后重复上述过程直至达到置乱次数后输出置乱图像。需要注意的是，此时变化形状得到的图像与之前转置获得的图像不同，形状变化如下所示：

图2给出了FMSS算法流程，具体描述如算法1所示：

算法1四分块幻方置乱FMSS算法

输入：灰度明文图像大小为H×W，置乱次数t，图像块的分解方式及排列组合顺序，如：a,b,c,d。

输出：灰度置乱图像大小为H×W。

步骤1根据输入图像尺寸，采用四方定理将图像分为4个正方形块(I1,I2,I3，I4)。

步骤2根据正方形图像块尺寸，使用幻方生成算法生成幻方矩阵组合(M1,M2,M3,M4)。

步骤3使用(M1,M2,M3,M4)依次对每个图像块执行幻方置乱，获得置乱图像块(I′1,I′2,I′3，I′4)。

步骤5若当前置乱次数小于t，则继续对S3执行步骤3和步骤4。

步骤6输出置乱图像S。

Figure 2 Flow chart of FMSS algorithm图2 FMSS算法流程图

Figure 3 Flow chart of FMSS recovery图3 FMSS恢复流程图

Figure 4 Image scrambling and recovery results图4 置乱与恢复结果

在FMSS算法中，置乱、分块、拼接、转置及形状变化均可逆，因而置乱图像可被恢复为原始图像，且恢复过程与置乱过程相反。图3给出了置乱图像恢复的流程图，因篇幅限制不再赘述。

4 实验与结果分析

为测试FMSS的有效性，本节进行了多组仿真实验，以检验置乱图像相邻像素间的相关性、抵抗各种攻击的鲁棒性以及置乱和恢复的速度。

实验运行环境：64位Windows 10操作系统，平台为Matlab 2014a，16 GB内存，CPU为Intel 酷睿i7-8750H 2.2 GHz。仿真实验所用图像为USC-SIPI图像数据集[42]以及Matlab图像处理标准图像库中的Green(500×300)、Football(320×256)和Lena(256×256)图像，均为bmp格式的图像文件。

4.1 置乱图像结果

四方定理有效解决了幻方置乱的变尺度置乱能力不足问题，使得待置乱图像不再局限于方形图像。为检验实际效果，本节利用Football和Green等矩形图像进行实验验证。设置乱次数t∈[1,100]，将FMSS算法置乱后的图像保存。图4展示了矩形图像置乱1次和100次的结果。可以看到，使用FMSS算法置乱1次后的图像出现明显的条痕现象。这是因为图像分块置乱次数不足导致块与块之间差异明显。然而，随着置乱次数的增加，该现象彻底消失。置乱100次时，图像充满随机的噪点，无法从直观上观察到该图像与原始图像存在任何联系。此时置乱图像完全掩盖了原始图像，且又能恢复为原始图像。由此可知FMSS算法可对非等长图像进行置乱，突破了幻方置乱的局限，增强了幻方置乱算法的变尺度置乱能力，置乱图像具有不可识别性和噪声性，这表明该算法具有良好的置乱和恢复效果。

此外，为验证FMSS算法与其他针对正方形图像的置乱算法相比在图像置乱上效果的优势，本节还使用FMSS算法对正方形图像进行了测试。对比实验采用了骑士巡游置乱[20]和幻方置乱[39]。原始图像采用Lena图像，所有算法置乱次数均设置为100，实验结果如图5所示。图5a表明，在提升置乱效果方面，FMSS算法的优势更加明显；图5b和图5c表明，使用骑士巡游置乱和幻方置乱的结果保留了一定的原始图像细节信息，未充分置乱，置乱效果不满足加密要求。

Figure 5 Scrambling results of square images图5 正方形图像置乱结果

上述实验结果表明,FMSS算法对矩形图像置乱是有效的，增强了幻方置乱算法变尺度能力，且图像置乱效果良好，显示了FMSS算法的可行性与优势。

4.2图像分块对置乱的影响

毫无疑问，分块的方式、数量将对置乱图像产生一定的影响。原始图像采用Lena，利用经典幻方置乱算法[39]进行对比实验，置乱次数t∈[1,100]。图6给出了实验结果。

相比于幻方置乱算法，FMSS算法采用的分块方法明显提升了图像置乱效果。原始幻方置乱算法置乱不充分，大量原始图像细节信息被保留,增加置乱次数也未能缓解该不足。在置乱次数较少时FMSS算法置乱图像出现明显条纹，随着置乱次数t的增加，图像充满随机噪点，整体趋于混乱。这是因为首次置乱之后再拼接会存在较为明显的痕迹，分块作用随着置乱次数的增加逐渐显现，块之间的像素充分交换，图像混乱程度加深。

Figure 6 Effect of block on image scrambling图6 分块对图像置乱的影响

另外，FMSS算法的分块过程可继续递归进行，例如将图像进一步划分为16块、64块，甚至更多。为检验FMSS算法分块数量对图像置乱的影响，依旧采用Lena图像，将图像分为数量不同的块，依次设分块数量bn为4,16,64，设置置乱次数t∈[1,100]。图7给出了实验结果。不难发现，在置乱次数t较低的情况下，不同分块数量的置乱图像存在明显差异。置乱次数t为1时，分块数量bn越多，条纹越明显；t为5时，该现象得到一定程度缓解；t为10时，条纹基本消失，分块数量的影响几乎相同；t为100时，基本无区别。

由实验结果可知，分块一方面增强了幻方置乱变尺度置乱能力，同时也获得了更好的置乱效果。图像分块的数量仅在置乱次数较少时有显著作用，当置乱次数增多时，置乱效果互相接近。因此，可将分块数量合理地设置为4，在不影响置乱效果的前提下加快FMSS算法置乱与恢复的速度，降低时间复杂度。

4.3 相邻像素点的相关性分析

自然图像在水平、垂直及对角线方向上的相邻像素通常具有较高的相关性。研究人员常利用该统计特性分析加密图像的算法，所以在一定程度上，相关性代表着加密算法的安全性。安全性高的加密算法能够有效降低图像相邻像素的相关性。

Figure 7 Influence of block numbers on image scrambling图7 分块数量对图像置乱的影响

严格的相关系数定义如式(3)～式(5)所示：

(3)

(4)

(5)

其中，x和y表示选中的相邻像素序列，xi和yi表示x,y中的第i个像素的像素值，样本数量为K，x的期望和方差分别为E(x)和D(x)。一般而言，当相关系数绝对值大于0.8时，相邻像素间存在较强的相关性;当相关系数绝对值小于0.3时，相邻像素间的相关性较弱。

FMSS算法引入了图像拼接、分块、转置与改变形状等操作，所有像素在多次的分块、拼接过程中被充分打乱，有效破坏了相邻像素的位置关系。为验证上述操作在降低图像相邻像素相关性和提升安全性上的表现，本节采用Green图像作为明文图像，设置不同的置乱次数，分别从水平、垂直和对角线方向随机选取200行200列进行仿真分析，进行200次相同操作，取200次实验结果的平均值，结果如表1所示。

Table 1 Correlation coefficient between adjacent pixels of plain image and scrambling image

在水平和垂直方向上，明文图像相邻像素相关系数绝对值在0.88附近，而对角线方向为0.78左右，表明相关性较强。当置乱次数t从1增加到100时，置乱图像相邻像素相关系数接近0，与原始图像相比下降约80%，表明FMSS算法具有较好的安全性，可有效抵抗统计分析。

为进一步分析FMSS算法的安全性，从Green置乱图像中随机选取1 000个点，分别绘制了3个方向的相关性图，如图8所示。从图8a～图8c可看到，明文图像样本均分布于对角线两侧，表明相关性较强，而置乱图像图8d～图8f的样本则随机散布在整个空间中，相邻像素间相关性显著降低，说明置乱100次后图像像素之间关联非常小。同时这也表明置乱图像具有较高的混乱程度和较好的安全性。

Figure 8 Experimental results of image correlation analysis图8图像相关性分析实验结果

由此可知，FMSS算法显著降低了相邻像素间的相关性，能够抵抗统计攻击，具有较好的安全性。考虑到FMSS算法的分块、拼接、转置、改变形状及置乱并未改动任意像素的像素值，因此不会对图像直方图做出任何改变。

4.4 鲁棒性分析

数据在传输过程中可能会有噪声，因此置乱要求能抵抗一定的攻击和分析，包括压缩图像、裁剪图像及添加噪声等攻击。由于置乱图像经过了拼接、分块和转置，所以邻域相关像素分散比较均匀，因而可以抵御剪切、擦除等常规图像攻击。

峰值信噪比PSNR(Peak Signal to Noise Ratio)和归一化相似度NC(Normalized Correlation)等评价指标能够客观反映被攻击后的图像质量，常被用于评价鲁棒性，其严格的数学定义如式(6)～式(8)所示：

(6)

(7)

(8)

其中,明文图像(i,j)位置的像素值为W(i,j)，恢复后该位置的像素值为W′(i,j)，MAX=255，H和W分别为图像的高和宽。NC取值为[0,1]，越接近1，表明恢复图像越接近明文图像；PSNR值越大，说明恢复图像质量越高。通常PSNR低于30 db表示恢复图像劣化严重。

为检验抗噪声攻击及剪切的鲁棒性，本节采用Green和Lena图像，对图像添加椒盐噪声和进行剪切攻击。部分Lena被攻击图像与恢复图像如图9所示，表2给出了所有实验结果。

不难发现，在添加少量椒盐噪声时，图9a和图9b的图像恢复受到了轻微影响;图9c和图9d的恢复图像中噪点充满整幅图像;图9e～图9g能获得图像大部分信息，NC值高于0.9;而图9h则严重劣化，PSNR值很低，NC值下降至0.8附近。

剪切攻击图像(图9i～图9p)表明，图像质量劣化程度随着剪切比例的增大而加深。剪切左上角1/16(6.25%)图像时，剪切攻击造成的影响被FMSS算法均匀分散，图像质量轻微劣化，可通过滤波去噪技术将噪点滤除，进而提高恢复图像质量。而图9j和图9k的NC值和PSNR值接近，这表明裁剪程度一定时，裁剪位置产生的影响较小，有损攻击被均匀分散到图像各个位置。不难发现，此时恢复图像质量劣化程度进一步加深，仍可以观察到图像轮廓信息。当裁剪一半图像时，恢复图像丢失大部分信息，图像质量存在非常严重的劣化，视觉感官上难以接受。

Table 2 Experimental results of salt & pepper noise and shear attack

表2数据表明，受到噪声攻击时，不同图像的恢复图像质量接近。面对噪声攻击，Lena图像与Green图像的PSNR值接近但后者略低(Green图像未在图9中展示)。NC值在噪声较少时接近，差距随着椒盐噪声量增大而逐渐增大。面对剪切攻击，Lena图像与Green图像的PSNR值差距较小，但Green图像的略高，NC值基本一致。由此可知，与经典的幻方置乱算法相比，FMSS算法具有较好的鲁棒性，有损攻击被均匀分散，抗噪声和裁剪能力得到显著提高。

Figure 9 Experimental results of salt & pepper noise and shear attack图9 椒盐噪声与剪切攻击实验结果

此外，由于JPEG格式图像在互联网上传输使用相对更为广泛，而仿真实验采用BMP格式图像，为了检验和扩展FMSS算法的实用性，本节还进行了JPEG有损压缩攻击实验。实验使用Green图像，设FMSS置乱次数t为100，表3给出了实验结果。

显然，PSNR值和NC值随着压缩因子递增而增大，恢复图像质量越来越高。压缩因子较低时，恢复图像与原始图像的NC值仍然较大。这表明即使是受到一定程度的JPEG压缩，存在一定的失真情况，恢复图像质量仍然较高，图像轮廓依然清晰可见。总体而言,JPEG压缩并不会影响置乱图像质量，这说明FMSS算法具有较强的抗JPEG有损压缩的能力，满足实际应用要求。

由前述实验结果不难得知，FMSS算法通过位置置乱有效分散了错误像素，椒盐噪声、剪切和JPEG压缩等攻击对FMSS算法影响有限。因此，FMSS算法具有良好的鲁棒性，较之传统幻方置乱算法有所增强，可在实际网络环境中应用。

Table 3 Experimental results of JPEG compression attack

4.5 运行时间分析

因为图像置乱和恢复过程互为逆向，因而在理论上置乱和恢复的时间开销基本一致。为检验算法置乱和恢复时间，对Lena、Football和Green图像采用FMSS算法分别进行10次置乱，表4给出了置乱20次和恢复所用的时间平均值、最大值和最小值。从表4可以看出，FMSS算法置乱与恢复所用时间相差无几，且置乱所用时间与图像像素总数成正相关。还可以看出，FMSS算法具有较快的置乱和恢复速度，其原因在于，幻方生成算法判断、循环语句及移动元素操作较少，时间复杂度相对较低，因而FMSS算法置乱与恢复较快。

Table 4 Image scrambling and recovery time

5 结束语

本文基于四方定理和幻方置乱，提出了一种新的矩形图像置乱算法FMSS。首先，该算法根据明文图像的尺寸使用四方定理将图像划分成4个正方形图像块;其次，利用幻方生成算法生成所需大小的幻方，并按约定的顺序对每个图像块分别进行幻方置乱；最后，将置乱后的图像块按顺序拼接成图像，恢复为原始图像大小。在整个算法中，采用多次置乱处理以增强置乱效果。恢复图像过程为上述过程的逆过程。FMSS算法能够快速处理矩形图像，具有良好的置乱效果。仿真实验结果表明，分块、拼接、转置及变换形状等操作显著消除了图像相邻像素间的相关性，相比传统幻方置乱算法，密钥空间较大，还增强了变尺度置乱能力、鲁棒性与安全性。本文的工作拓展了幻方置乱算法的应用范围，为数字图像置乱研究提供了一条新途径。在本文工作基础上，值得进一步拓展研究之处包括：

(1) 测试所提置乱算法周期性。FMSS算法引入了分块、拼接、转置和变化形状等操作，同一像素点每次所在图像块不固定，从而使得置乱图像周期性出现的可能性大大减小，一定程度上提高了安全性。当前仍需要足够的测试验证并完善算法的安全性。

(2)将FMSS算法扩展应用于局部图像置乱。 在某些应用场景下，仅需要对局部图像进行处理。因此，可对FMSS算法进一步完善，即可用于实际局部图像置乱，提高其实用性。

(3)将FMSS算法扩展应用于要求明文图像为正方形的置乱处理中，与Arnold置乱算法、斐波那契置乱算法、骑士周游置乱算法等融合研究，并应用于视频、音频加密处理。