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变换的原理，我们还可以用来加密其它数据，而不仅仅是图像。

转载须注明出处：http://www.jianshu.com/p/39727dbaffd9