时间：2022-06-02 03:28:29
摘要：针对非等长图像的Arnold变换的适用性问题，该文从线性方程组的角度进证明了任意大小的图像都存在Arnold置乱周期，其关键在于置乱变换矩阵系数的选择。实验结果也表明像素矩阵的长宽比为整数并非是其存在置乱周期的必要条件；当长宽比不为整数时，也存在置乱周期。这使得在实际中，可以对任意图像用Arnold变换进行图像加密。
关键词：Arnold；图像；置乱；图像加密；矩阵
中图分类号：TP37 文献标识码：A 文章编号：1009-3044（2013）34-8421-02
1 概述
近年来，随着多媒体技术的迅猛发展及网络的广泛使用，图像的使用也越来越频繁。随之而产生的图像的版权保护及加密技术等也受到人们更多的关注。而图像置乱技术就是一类重要的图像加密方法。其中比较经典的有：Arnold变换、幻方变换、Hilbert 曲线等。Arnold变换因为简单，而受到人们的喜爱。但是由于其特点，一般仅将其使用在长宽相等的图像，对于长宽不等的图像进行加密，则需要复杂的处理，这就限制了其使用范围。
于是，许多学者对这方面进行了研究：文献[1]先把长宽不等的图像矩阵先填充成长宽相等的方阵后再进行Arnold变换；文献[2]提出了一种新颖的二维非等长图像置乱变换，并给出了周期存在判据；文献[3]-[7]也做了相应地研究。在这些方法中，有的需要对图像进行填充，有的需要对图像划分成可重叠的正方形区域块，有的需要对图像进行插值，这都增加了处理的难度。文献[2]虽然提出了一种新颖的非等长图像置乱方法，但是其认为并不是所有的非等长图像都具有置乱周期。该文将在文献[2]的基础上证明，任意非等长的图像都具有置乱周期。
2 传统的Arnold变换
对于大小为N×N的图像方阵，传统的Arnold变换公式为：
[x'y'=1112xymodN] （1）
其中[xy]为原来方阵中的坐标，[x'y']为变换后方阵中的坐标，[1112]为变换矩阵。
后来又有学者把变换矩阵推广到[acbd]，其中只要a，b，c，d四个元素满足[acbd=ad-bc]c=±1即可。这样就增加了破译的难度，提高了Arnold变换的实用性。但是这样的Arnold变换，只适用于正方形矩阵，而不能用于长宽不相等的图像。
文献[2]中提出了一种新颖的图像置乱公式，设像素矩阵为[M×N]，像素坐标为（x，y）且[x∈[0，M-1]，y∈[0，N-1]]，则一次置乱后的坐标（x’，y’）由公式（2）得到。
[x'y'=acbdxymodMN] （2）
3 任意大小矩阵的Arnold变换
文献[2]虽然证明了：二维非等长图像置乱变换周期存在，当且仅当像素矩阵所有元素，按式（2）一次迭代后，映射为新像素矩阵的不同元素。但是其在后面的推论中，仅说明了M/N为整数比，或者图像置乱系数满足a=1，b>0，c=0，d=1（a=1，b=0，c>0，d=1）时，才可对任意图像在水平（垂直）方向置乱，才存在可恢复周期。该文将在文献[2]的基础上证明任意大小的图像矩阵都存在Arnold变换周期。
文献[2]知：二维非等长图像置乱变换周期存在，当且仅当像素矩阵所有元素，按式（2）一次迭代后，映射为新像素矩阵的不同元素。此结论等价于：能找到一个置乱系数矩阵，使得原像素矩阵中的任意不同的两点按式（2）进行一次迭代后不能映射到同一点上；或者是如果原像素矩阵中的两点按式（2）映射到新像素矩阵中的一点上，那么原像素矩阵中的这两点必定是同一个点。在这两种情况都说明有置乱周期存在。
设原像素矩阵中存在两点[（x1，y1）]，[（x2，y2）]，按公式（2）一次迭代映射为新像素矩阵的[（x0，y0）]，则有：
[ax1+by1=k1M+x0ax2+by2=k2M+x0cx1+dy1=k3N+y0cx2+dy2=k4N+y0] （3）
用式（3）中的第一式减去第二式，第三式减去第四式，并令[k1-k2=l1，k3-k4=l2]，则可得到公式（4）：
[a（x1-x2）+b（y1-y2）=（k1-k2）M=l1Mc（x1-x2）+d（y1-y2）=（k3-k4）N=l2N] （4）
设[X=x1-x2]，[Y=y1-y2]，如果[X=0]且[Y=0]，说明[（x1，y1）]，[（x2，y2）]为原像素矩阵中的同一个点；如果[X]和[Y]不同为0，则说明[（x1，y1）]，[（x2，y2）]是原像素矩阵中的不同点。把式（4）写成矩阵形式（5）：
[acbdXY=l1Ml2N] （5）
对于式（5）下面分两种情况讨论：
①[l1=l2=0]。则[l1M=0，l2M=0]，根据线性代数知识，只要行列式[D=acbd≠0]，则式（5）只有唯一解[X=0]，[Y=0]。即只要找到使[D≠0]成立的a，b，c，d就可以使得映射为同一点的，只能是原像素矩阵中的相同点，即 [（x1，y1）]，[（x2，y2）]为同一个点。
②[l1]和[l2]中至少有一个不为零。由线性代数中的克莱姆法则知道，如果式（5）无解或者有多个解必定有[D=acbd=0]。在这种情况下，如果能找到a，b，c，d使得[D=0]，保证式（5）无解，就可以确定不会有像素映射到同一位置上。
综合上面的两种情况，只要找到a，b，c，d使得映射到同一个点的只能是原像素矩阵中的同一个点；或者是不可能原像素矩阵中的不同点映射到同一个点上，则可以保证原像素矩阵中的不同点不会映射到同一点上，也就保证了任意非等长图像的置乱周期的存在性。
4 实验结果
对大小为[3×7]的像素矩阵，可以找到[A1=2335]做为系数变换矩阵，其变换周期为4。其坐标序号的变换过程如图1所示。其中原始坐标序号由[3×y+（x+1）]得到，[x∈[0，2]，y∈[0，6]]
（a）原始坐标序号 （b）第1次置乱 （c） 第2次置乱 （d） 第3次置乱 （e） 第4次置乱
图1 用[A1]对[3×7]像素矩阵的置乱
从图1中可以看到当M/N（或N/M）不为整数时，非等长图像矩阵也存在变置乱换周期。这就证明了非等长图像的长宽比为整数并不是其置乱周期存在的必要条件。
5 结束语
本文在文献[2]的基础上，证明了任意大小图像都存在置乱周期。其中置乱周期的存在和变换矩阵中的系数相关。从实验中，可以看到当M/N（或N/M）不是整数比时，置乱周期也存在。因此在实际的图像加密中，只要选择合适的变换矩阵系数，就可以对非等长图像进行Arnold变换。由于该变换存在周期，因此加密图像也可以进行恢复。
参考文献：
[1] 孔涛，张亶.Arnold反变换的一种新算法[J].软件学报，2004，10（15）.
[2] 邵利平，覃征，高洪江，等.二维非等长图像置乱变换[J].电子学报，2007，35（7）：1290-1294.
[3] 李永逵，冯乔生，周粉，等. 二维Arnold 变换及非等长图像置乱变换[J].计算机工程与设计，2009，30（13）：3133-3135.
[4] 梁小勇，郭琳琴，李香林，等.基于Arnold 变换的非正方形图像置乱新算法[J].吕梁学院学报，2012，2（2）：9-12.
[5] 陈曦，向菲，张志勇，王剑，等. 二维非等长图像置乱方法的研究与验证[J].安徽工业大学学报：自然科学版，2013，36（8）：929-932.
[6] 孙燮华， 章仁江. 计算Arnold 变换周期的新算法[J].计算机技术与发展，2008，18（11）：66-68.
[7] 黎罗罗.Arnold型置乱变换周期分析[J].中山大学学报：自然科学版，2005，44（2）：1-4.