Arnold变换详解
1. 概述
利用Arnold变换（又称猫脸变换）可以对图像进行置乱，使得原本有意义的图像变成一张无意义的图像。该变换可以在其它图像处理前对图像做预处理，例如在数字盲水印嵌入前对水印进行置乱。也可以用于普通的图像加密。
通常一次Arnold变换达不到理想效果，需要对图像进行连续多次的变换。Arnold变换具有周期性，即对图像连续进行Arnold变换，最终又能得到原图像。变换的周期和图像的尺寸有关。
当图像是一张方形的图像时，Arnold变换存在逆变换。经过N次Arnold变换后的数据可以通过N次逆变换恢复数据。
Arnold变换不仅可以用于图像置乱，也可以用于其它数据的置乱和加密。
2. 狭义的猫脸变换
2.1 公式
狭义的猫脸变换即最简单的一种变换。网络上绝大部分关于Arnold变换的博客都是狭义Arnold变换。
其矩阵运算公式为：
狭义猫脸变换矩阵公式
转化为多项式为：
狭义猫脸变换多项式公式
其中mod()是取模运算，N是正方形图像的边长，(x', y')是像素点(x, y)变换后的坐标。
注意求模运算(mod) ≠ 求余运算(%) 。在被除数是负数时两者存在差别，例如： -5 mod(6) = 1, 但 -5 % 6 = -5。
/**
* 求模运算
*/
private int mod(int number, int mod) {
return (number % mod + mod) % mod;
}
2.2 物理意义和示意图
置乱的实质是新位置与旧位置的映射，且该映射是一一对应的。下图是一次猫脸变换的示意图：
狭义猫脸变换示意图
- (a)是原图
- (b)是先做水平方向的错切
- (c)是在(b)的基础上再做一次竖直方向的错切
- (d)是对图像求模，即切割回填操作，得到变换后的图像。
如果你想知道为什么要这样变换，为什么是水平错切一个单位，竖直错切两个单位：
实际上这里水平错切的长度是一倍图像的高度，竖直错切的长度是一倍图像的高度加一倍图像的宽度。由于图像的宽高相等，所以这里看起来是水平错切一个单位，竖直两个单位。
为什么这样子错切，是因为置乱的实质是新位置与旧位置的映射，且该映射是一一对应的。
也就是说，其它错切形式可能造成多个点移动到同一个位置，导致图像信息的丢失。例如下面两种错切方式：
其他错切情形
第一种是水平和竖直方向都错切一个单位，第二种是水平一个单位，竖直三个单位。可以看出，取模后两种错切方式都有部分区域重叠了。因此错切的单位是有一定要求的，详见后文广义的Arnold变换。
2.3 代码实现
2.3.1 Java泛型的实现
此处宽高需要相等是方便后续的逆变换。
public class Arnold<T> {
/**
* 猫脸变换
* @param origin 原始图像
* @param dest 用于保存变换后的图像
* @param count 变换的次数
*/
public void arnold(T[][] origin, T[][] dest, int count) {
int newY, newX;
while (count > 0) {
for (int row = 0; row < origin.length; row++) {
for (int col = 0; col < origin[0].length; col++) {
newX = (col + row) % origin.length;
newY = (col + 2 * row) % origin.length;
dest[newY][newX] = origin[row][col];
}
}
count--;
origin = Arrays.copyOf(dest, dest.length);
}
}
}
2.3.2 适用于Android的一维数组形式
/**
* 猫脸变换
* @param origin 原始图像，宽高必须一致
* @param dest 用于保存输出
* @param SIZE 宽和高
* @param count 变换的次数
*/
public void arnold(int[] origin, int[] dest, int SIZE, int count) {
int oldY, oldX, newY, newX;
while (count > 0) {
for (int index = 0; index < origin.length; index++) {
oldX = index % SIZE;
oldY = index / SIZE;
newX = (oldX + oldY) % SIZE;
newY = (oldX + 2 * oldY) % SIZE;
dest[newY * SIZE + newX] = origin[index];
}
count--;
origin = Arrays.copyOf(dest, dest.length);
}
}
2.3.3 实际运行结果
如图所示，一次变换后，原图得到了一定程度的置乱，但还能分辨出原始图像的信息，6次变换后图像已看不出原始图像的信息。
狭义猫脸变换运行结果
3. 狭义猫脸变换的逆变换
当一张图片的宽度和高度相同时，Arnold变换具有逆变换。虽然Arnold变换具有周期性，可以通过一直变换下去得到原图，但是周期越长，恢复原图也越长。通过逆变换可以较为方便地把变换后的图像恢复。
3.1 逆变换公式
狭义猫脸逆变换矩阵公式
转换为多项式为：
狭义猫脸逆变换多项式公式
3.2 代码实现
3.2.1 泛型形式的实现
/**
* 猫脸逆变换
* @param origin 原始图像
* @param dest 用于保存变换后的图像
* @param count 变换的次数
*/
public void inverseArnold(T[][] origin, T[][] dest, int count) {
int newY, newX;
while (count > 0) {
for (int row = 0; row < origin.length; row++) {
for (int col = 0; col < origin[0].length; col++) {
newX = (col + row) % origin.length;
newY = (col + 2 * row) % origin.length;
dest[newY][newX] = origin[row][col];
}
}
count--;
origin = Arrays.copyOf(dest, dest.length);
}
}
3.2.2 适用于Android的一维数组形式
/**
* 猫脸逆变换
* @param origin 原图
* @param dest 保存变换后的图像
* @param SIZE 宽高
* @param count 变换次数
*/
public void inverseArnold(int[] origin, int[] dest, int SIZE, int count) {
int oldY, oldX, newY, newX;
while (count > 0) {
for (int index = 0; index < origin.length; index++) {
oldX = index % SIZE;
oldY = index / SIZE;
newY = mod((oldY - oldX), SIZE);
newX = mod((2 * oldX - oldY), SIZE);
dest[newY * SIZE + newX] = origin[index];
}
count--;
origin = Arrays.copyOf(dest, dest.length);
}
}
逆变换的效果当然就是把图像复原了。此处就不在贴效果图了。
4. 广义的猫脸变换
4.1 公式
如前文所述，只要错切的单位满足取模回填后，原图与变换后的图能够一一对应，那么该变换就是有效的。满足这个条件的公式是：
广义猫脸变换矩阵公式.png
广义猫脸变换行列式公式
其逆变换公式为：
广义猫脸逆变换矩阵公式.png
广义猫脸逆变换多项式公式.png
4.2 代码实现
这里只列出了用于Android的一维数组形式：
4.2.1 广义正变换
/**
* 广义猫脸变换
* @param origin 原图
* @param dest 变换后的图
* @param SIZE 图像宽度和高度
* @param count 变换次数
*/
public void arnold(int[] origin, int[] dest, int SIZE, int count, int a, int b) {
final int ab_plus_1 = a * b + 1;
int oldY, oldX, newY, newX;
while (count > 0) {
for (int index = 0; index < origin.length; index++) {
oldX = index % SIZE;
oldY = index / SIZE;
newX = (oldX + a * oldY) % SIZE;
newY = (b * oldX + ab_plus_1 *oldY) % SIZE;
dest[newY * SIZE + newX] = origin[index];
}
count--;
origin = Arrays.copyOf(dest, dest.length);
}
}
4.2.2 广义逆变换
/**
* 广义猫脸逆变换
* @param origin 原图
* @param dest 变换后的图
* @param SIZE 图像宽度和高度
* @param count 变换次数
*/
public void inverseArnold(int[] origin, int[] dest, int SIZE, int count, int a, int b) {
final int ab_plus_1 = a * b + 1;
int oldY, oldX, newY, newX;
while (count > 0) {
for (int index = 0; index < origin.length; index++) {
oldX = index % SIZE;
oldY = index / SIZE;
newX = mod(ab_plus_1 * oldX - a * oldY, SIZE);
newY = mod(oldY - b * oldX, SIZE);
dest[newY * SIZE + newX] = origin[index];
}
count--;
origin = Arrays.copyOf(dest, dest.length);
}
}
5. 利用Arnold变换进行加密
对于广义Arnold变换，当a、b、count任何一个值不同时，变换后图像也是不相同的。因此，可以把（a、b、count）作为加密参数对图像进行加密。此外，还可以对图像的不同部分进行不同的加密，使得更难破解。例如，可以把图像分为四份（甚至可以有交集），分别对每一份子图进行加密，这样又增大了破解的难度。
Arnold加密后，如果图像被破坏了，例如压缩、涂改等。解密后的图像依然能恢复一部分数据。
下图是以参数（7，11，4）加密的图像，以及对加密后的图像进行涂抹后再解密的结果。
鲁棒性测试
- (a) 原图
- (b) 加密后的图像
- (c) 涂抹
- (d) 解谜后的图像
可以看出Arnold变换有较高的鲁棒性，即使添加了多个较大的圆也能恢复出原图的大致信息。
根据Arnold变换的原理，我们还可以用来加密其它数据，而不仅仅是图像。
