一文带你了解Arnold猫脸变换

2023-10-27 约 500 字预计阅读 3 分钟 - 次阅读 - 条评论

Arnold’s cat map(国人最喜欢的猫脸变换🐱)

Arnold猫脸变换

概述

利用Arnold变换（又称猫脸变换）可以对图像进行置乱，使得原本有意义的图像变成一张无意义的图像。该变换可以在其它图像处理前对图像做预处理，例如在数字盲水印嵌入前对水印进行置乱。也可以用于普通的图像加密。通常一次Arnold变换达不到理想效果，需要对图像进行连续多次的变换。Arnold变换具有周期性，即对图像连续进行Arnold变换，最终又能得到原图像。变换的周期和图像的尺寸有关。当图像是一张方形的图像时，Arnold变换存在逆变换。经过N次Arnold变换后的数据可以通过N次逆变换恢复数据。 Arnold变换不仅可以用于图像置乱，也可以用于其它数据的置乱和加密。

/images/1698415022433.webp

Arnold置换原理

所谓的打乱次序指的是对图像进行“坐标变换”，只不过这种变换不是随意的变换，变换需要具有两个硬性要求：

（1）变换就是加密，那么必须存在对应的逆变换（解密）

（2）变换能保证图像的像素被彻底打乱，观察者看不出加密后图像包含的信息

为此，Arnold发明了下面的变换方式：

广义猫脸变换矩阵公式

/images/1698415062023.webp

其中x和y表示坐标，new表示变换以后的坐标，ori表示原始的坐标（original缩写），a和b是两个可选的参数，mod为求余数操作，N是图像的长或者宽，这里只考虑长度和宽度相等的图像，上式表示的就是“图像的坐标变换”。

广义猫脸变换行列式公式

/images/1698415088110.webp

其逆变换公式为：

广义猫脸逆变换矩阵公式

/images/1698415115884.webp

广义猫脸逆变换多项式公式

/images/1698415128735.webp

代码实现

有几个参数是必须考虑的，比如：

打乱的次数
a和b的取值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69


# -*- coding: utf-8 -*-
# @Author  : 1cePeak

import matplotlib.pyplot as plt
import cv2
import numpy as np
from PIL import Image

img = cv2.imread('flag.png')

def arnold_encode(image, shuffle_times, a, b):
    """ Arnold shuffle for rgb image
    Args:
        image: input original rgb image
        shuffle_times: how many times to shuffle
    Returns:
        Arnold encode image
    """
    # 1:创建新图像
    arnold_image = np.zeros(shape=image.shape)
    
    # 2：计算N
    h, w = image.shape[0], image.shape[1]
    N = h   # 或N=w
    
    # 3：遍历像素坐标变换
    for time in range(shuffle_times):
        for ori_x in range(h):
            for ori_y in range(w):
                # 按照公式坐标变换
                new_x = (1*ori_x + b*ori_y)% N
                new_y = (a*ori_x + (a*b+1)*ori_y) % N
                
                # 像素赋值
                print(image[ori_x, ori_y, :])
                print(arnold_image[new_x, new_y, :])
                arnold_image[new_x, new_y, :] = image[ori_x, ori_y, :]

    cv2.imwrite('flag_arnold_encode.png', arnold_image, [int(cv2.IMWRITE_PNG_COMPRESSION), 0])
    return arnold_image

def arnold_decode(image, shuffle_times, a, b):
    """ decode for rgb image that encoded by Arnold
    Args:
        image: rgb image encoded by Arnold
        shuffle_times: how many times to shuffle
    Returns:
        decode image
    """
    # 1:创建新图像
    decode_image = np.zeros(shape=image.shape)
    # 2：计算N
    h, w = image.shape[0], image.shape[1]
    N = h  # 或N=w

    # 3：遍历像素坐标变换
    for time in range(shuffle_times):
        for ori_x in range(h):
            for ori_y in range(w):
                # 按照公式坐标变换
                new_x = ((a * b + 1) * ori_x + (-b) * ori_y) % N
                new_y = ((-a) * ori_x + ori_y) % N
                decode_image[new_x, new_y, :] = image[ori_x, ori_y, :]

    cv2.imwrite('flag.png', decode_image, [int(cv2.IMWRITE_PNG_COMPRESSION), 0])
    return decode_image

# arnold_encode(img, 1, 2, 3)
arnold_decode(img, 1, 29294, 7302244)

例题实现

/images/1698415205209.png

上述代码跑完之后的结果如下：

/images/1698415242290.png

可以看出，成功恢复出了图片的像素。

彩蛋一

在本文恰好发布8个月后（2023年10月27日-2024年6月27日，就很神奇），B站知名网络安全UP主（SageMath）也就是@LOV3师傅发现了预置的彩蛋。如果你认真分析了上面Arnold的代码，会发现shuffle_times这个参数其实是没有生效的，无论shuffle_times是多少，图片都没有变化。可能国内很多Arnold题目的出题人也没有注意到这一点，直接照抄了现成的代码。不过也挺好的，参赛选手的解题时间也会大大缩短。修正过的代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


def arnold_encode(image, shuffle_times, a, b):
    """ Arnold shuffle for rgb image
    Args:
        image: input original rgb image
        shuffle_times: how many times to shuffle
    Returns:
        Arnold encode image
    """
    # 1:创建新图像
    arnold_image = np.zeros(shape=image.shape)
    
    # 2：计算N
    h, w = image.shape[0], image.shape[1]
    N = h   # 或N=w
    
    # 3：遍历像素坐标变换
    for time in range(shuffle_times):
        for ori_x in range(h):
            for ori_y in range(w):
                # 按照公式坐标变换
                new_x = (1*ori_x + b*ori_y)% N
                new_y = (a*ori_x + (a*b+1)*ori_y) % N

                # 像素赋值
                # print(image[ori_x, ori_y, :])
                # print(arnold_image[new_x, new_y, :])
                arnold_image[new_x, new_y, :] = image[ori_x, ori_y, :]
        
        # 更新坐标
        image = np.copy(arnold_image)

    cv2.imwrite('flag_arnold_encode.png', arnold_image, [int(cv2.IMWRITE_PNG_COMPRESSION), 0])
    return arnold_image

彩蛋二

如果shuffle_times很大的情况下，如何优化代码呢？

参考文献

https://www.jianshu.com/p/39727dbaffd9

https://zhuanlan.zhihu.com/p/90483213