[ISCC2023线下] MISC1 WP

  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
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

import math
import numpy as np
from PIL import Image
from numpy.lib import ndindex

X, Y = 103, 137
N = 20
BOX_SIZE = 23
PIXEL_SIZE = 11

def set_pix(array, x, y, val):
    '''将图片数组 array 中第 (x, y) 个二维码格设为 val
    '''
    x1 = x * PIXEL_SIZE
    x2 = (x+1) * PIXEL_SIZE
    y1 = y * PIXEL_SIZE
    y2 = (y+1) * PIXEL_SIZE
    array[x1:x2, y1:y2] = val

# check box[i, j]
def check(ar, i, j):
    '''判断图片数组 ar 生成的马赛克的第 (i, j) 个块是否要求的相符
    即比较数组 ar 对应位置的平均值和马赛克数组的对应格
    '''
    x1 = X + i*BOX_SIZE
    x2 = X + (i+1)*BOX_SIZE
    y1 = Y + j*BOX_SIZE
    y2 = Y + (j+1)*BOX_SIZE
    # print('box:\n', ar[x1:x2, y1:y2])
    mean = ar[x1:x2, y1:y2].mean()
    return math.floor(mean) == mosaic[i, j]

def set_pixels(ar, uncertains, t):
    for k, pos in enumerate(uncertains):
        color = ((t >> k) & 1) * 255
        set_pix(ar, pos[0], pos[1], color)

def solve():
    error = False
    # for every box in pixelated area.
    for (i, j) in np.ndindex(mosaic.shape):
        # 考虑马赛克的每个格子 (i, j)，在 ar 中起始坐标是 (x, y)
        x = X + i*BOX_SIZE
        y = Y + j*BOX_SIZE

        # 只有从 (px, py) 开始的 3x3 个二维码格子会影响这个马赛克格子
        px = x // PIXEL_SIZE
        py = y // PIXEL_SIZE

        # 3x3 个格子中还不确定的位置
        uncertains = []
        for tx, ty in np.ndindex(3, 3):
            if not flags[px+tx, py+ty]:
                uncertains.append((px+tx, py+ty))
        if len(uncertains) == 0:
            continue

        possibles = []
        print(f'Try mosaic{(i, j)}, from pixel{(x, y)}, uncertains: {uncertains}')
        for t in range(2**len(uncertains)):
            '''遍历2^k种可能性'''
            # print('Try: {0:0{1}b}'.format(t, len(uncertains)))
            set_pixels(ar, uncertains, t)   # 将 ar 对应位置按 t 的每一位设置为对应颜色
            if check(ar, i, j):     # 判断马赛克颜色是否正确，正确则加入可能性列表
                possibles.append(t)

        if len(possibles) == 1:     # 只有一种可能性，那么是正确答案
            set_pixels(ar, uncertains, possibles[0])
            for x, y in uncertains:
                flags[x, y] = True
        elif len(possibles) > 1:
            # 多个可能就随便设一个，但是不标记为已经确定
            set_pixels(ar, uncertains, possibles[0])
            # 也可以用下面的方法，将所有可能性中颜色都相同的格子找出来，设置为确定的
            # 这样可以大大增加能解出的格子数（从 81% 提升到 88%）
            # print(possibles)
            # a = np.bitwise_and.reduce(np.asarray(possibles))
            # b = np.bitwise_or.reduce(np.asarray(possibles))
            # c = np.bitwise_xor(a, b)
            # print(f'{c:0{len(uncertains)}b}')
            # for k, pos in enumerate(uncertains):
            #     color = ((possibles[0] >> k) & 1) * 255
            #     set_pix(ar, pos[0], pos[1], color)
            #     if (c >> k) & 1 == 0:
            #         flags[pos[0], pos[1]] = True
        elif len(possibles) == 0 and len(uncertains) != 0:
            # 出现不明原因的错误
            print(f'Error: [{i}, {j}]')
            error = True
            break
        if error:
            break
        print(f'Solved: [{i}, {j}]')
    return flags.sum()  # 返回目前确定的格子数

im = Image.open('pixelated_qrcode.bmp')
ar = np.asarray(im, dtype='uint8')  # 在该数组上逐步恢复和试算二维码
mosaic = ar[X::BOX_SIZE, Y::BOX_SIZE][:N, :N].copy()    # 马赛克每格的数据
solved = ar[::PIXEL_SIZE, ::PIXEL_SIZE]     # 用于存放答案，开始取二维码每格左上角值
                                            # 注意 solved 是个引用，所以修改 ar 会跟着变
flags = (solved == 0) | (solved == 255)     # 如果某格是 0 或 255，已经能确定颜色

rd_corner = ar[PIXEL_SIZE-1::PIXEL_SIZE, PIXEL_SIZE-1::PIXEL_SIZE]  # 二维码每格右下角
rd_flags = (rd_corner == 0) | (rd_corner == 255)  # 按右下角能确定颜色的二维码格

for i, j in np.ndindex(flags.shape):
    # 按左上角和右下角边缘，将能够确定的格补全
    if flags[i, j]:
        set_pix(ar, i, j, solved[i, j])
    if rd_flags[i, j]:
        set_pix(ar, i, j, rd_corner[i, j])
flags = (solved == 0) | (solved == 255)  # 更新已确定的位置

while True:
    # 如果有新的格子被推算出来，那么继续算，否则已经没得算了
    num_ok = flags.sum()
    if solve() == num_ok:
        break

solved_im = Image.fromarray(ar)
solved_im.save('solved.bmp')
print('CertainRate:', flags.sum() / flags.size)