Written for hackergame 2021

qr_mosaic_recovery.py

import math
import pickle
from collections import Counter

import numpy as np
import tqdm as tqdm
from PIL import Image

X, Y = 103, 137  # 马赛克左上角位置(单位为像素)
N = 20  # 马赛克块的数量（共N*N块）
BOX_SIZE = 23  # 每个马赛克块的大小（边长，单位为像素）
PIXEL_SIZE = 11  # 二维码每个块的大小（边长，单位为像素）
pix, piy = math.floor(X / PIXEL_SIZE), math.floor(Y / PIXEL_SIZE)

qrcode = [[0 for _ in range(57)] for _ in range(0, 57)]


# flag{QRcodes_are_pixel_arts_EvSwCSAWtP}

def get_qr_ind(px, py):
    return px // PIXEL_SIZE, py // PIXEL_SIZE


def gen_mappings(mappings, cur_mapping, coords):
    if len(coords) == 0:
        mappings.append(cur_mapping)
        return
    cur = cur_mapping.copy()
    cur[coords[0]] = True
    gen_mappings(mappings, cur, coords[1:])
    cur = cur_mapping.copy()
    cur[coords[0]] = False
    gen_mappings(mappings, cur, coords[1:])


def gen_coords(x, xe, y, ye):
    res = []
    for ix in range(x, xe + 1):
        for iy in range(y, ye + 1):
            res.append((ix, iy))
    return res


if __name__ == '__main__':
    im = Image.open("pixelated_qrcode.bmp").convert('L')
    p = np.array(im)
    wid, hei = p.shape

    global_candidates = pickle.load(open('mosaic_global_candidates', 'rb'))
    definite = {}
    prob = Counter()
    probn = Counter()


    def conflict(c, definite):
        for overl in set(c.keys()).intersection(definite.keys()):
            if c[overl] != definite[overl]:
                return False
        return True


    while True:
        oldlen = len(definite)
        for cs in global_candidates:

            newcs = [c for c in cs if conflict(c, definite)]
            for coord in set(newcs[0].keys()):
                vals = set(c[coord] for c in newcs)
                if len(vals) == 1:
                    definite[coord] = list(vals)[0]
                else:
                    for c in newcs:
                        if c[coord]:
                            prob[coord] += 1
                        probn[coord] += 1
        if len(definite) == oldlen:
            break
    # print(definite)
    #print(len(definite))
    #print(prob)
    #print(probn)

    for ix in range(X, X + BOX_SIZE * N):
        for iy in range(Y, Y + BOX_SIZE * N):
            qr = get_qr_ind(ix, iy)


            def get_qr(ind):
                if ind in definite:
                    return definite[qr]
                else:
                    return prob[ind] / probn[ind] > 0.5


            p[ix, iy] = 0 if get_qr(qr) else 255
    Image.fromarray(p).save('result.png')
    exit(0)


    global_candidates = []
    prog = tqdm.tqdm(total=N * N)
    for ix in range(N):
        for iy in range(0, N):
            prog.update()
            boxX, boxY = X + ix * BOX_SIZE, Y + iy * BOX_SIZE  # start pos in px
            boxXed, boxYed = boxX + BOX_SIZE, boxY + BOX_SIZE
            qrX, qrY = get_qr_ind(boxX, boxY)
            qrXed, qrYed = get_qr_ind(boxXed, boxYed)

            # workX, workY = qrX * PIXEL_SIZE, qrY * PIXEL_SIZE
            # workXed, workYed = workX + PIXEL_SIZE, workY + PIXEL_SIZE

            color = p[boxX + BOX_SIZE // 2, boxY + BOX_SIZE // 2]

            mappings = []
            candidates = []
            gen_mappings(mappings, {}, gen_coords(qrX, qrXed, qrY, qrYed))
            for mapping in mappings:
                colsum = 0
                for bx in range(boxX, boxXed):
                    for by in range(boxY, boxYed):
                        if mapping[get_qr_ind(bx, by)]:
                            colsum += 0
                        else:
                            colsum += 255
                calced_color = colsum // (BOX_SIZE * BOX_SIZE)
                if color == calced_color:
                    candidates.append(mapping)
            global_candidates.append(candidates)
    pickle.dump(global_candidates, open('mosaic_global_candidates', 'wb'))
    print(global_candidates)