Nuit du hack 2018——Shreddinger

这个题目是比赛中唯一的一道developping类型的题目，给了一个压缩包下载，下载下来之后发现是100张

这样的图片。当时的想法，直接将这100张图片拼接起来看看？

    toImage = Image.new('RGBA',(1000,1400))
    for i in range(100):
        fromImge = Image.open(str(inuse[i]) + '.png')
        # loc = ((i % 2) * 200, (int(i/2) * 200))
        loc = ((i) * 10, 0)
        print(loc)
        toImage.paste(fromImge, loc)

但是得到的结果却是完全不能阅读的图片...这个时候结合题目的名字，就能够想到这些图片是被打乱过顺序的，就像放入到了碎纸机之后。我们要想办法恢复这些图片的顺序才行。
但是怎么恢复呢🤔
搜索了一下，发现13年的数学建模当中也有这样的一道题目，纵切碎纸片的复原简单实现。
http://blog.gcusky.com/20160423-matlab-1/
参考了下gcusky大佬的博客，大致的思路就是

1. 构造一个矩阵fzz[i][j]，表示i的最右端与j的最左端灰度值序列的方差
2. 通过比较方差确定纸片的匹配度，将匹配度高的组合到一起。

思路还比较的简单，实现起来也比较的容易，但是唯一需要注意的是
这个题目切碎之后的图片还存在被反转过的（rotate 180），首先要将这些反转过的图片重新反转过来。

for i in arr:
    print i
    im = Image.open(i)
    for j in range(0, 10):
        pix = im.getpixel((j, 684))
        if ((pix[0] + pix[1] + pix[2]) / 3) < 255:
            im = im.transpose(Image.ROTATE_180)
            im.save(i)

通过检查在某一固定横坐标像素点是否存在黑色来确定是否要翻转。
实现了这个算法之后发现还是不能很好的还原这里的这个图片，只能做到大致的匹配上。

只好另想其他的办法，这里恢复度不够肯定是因为每个点的高度值没有用到，仅仅只是用到了每个点的像素值来计算方差，这样高度值的信息就丢失了。因此还需要将高度信息也加入到考虑当中。

最终代码如下

from PIL import Image
import numpy as np
import pytesseract
import re
import sys

arr = []
for i in range(0, 100):
    arr.append(str(i) + '.png')

for i in arr:
    print i
    im = Image.open(i)
    for j in range(0, 10):
        pix1 = im.getpixel((j, 684))
        if ((pix1[0] + pix1[1] + pix1[2]) / 3) < 255:
            im = im.transpose(Image.ROTATE_180)
            im.save(i)

arr_l = []
for i in arr:
    im = Image.open(i)
    tmp = []
    for j in range(1400):
        pix = im.getpixel((0, j))
        tmp.append(min(1, 255 * 3 - (pix[0] + pix[1] + pix[2])))
    arr_l.append(tmp)
print len(arr_l)

arr_r = []
for i in arr:
    im = Image.open(i)
    tmp = []
    for j in range(1400):
        pix = im.getpixel((9, j))
        tmp.append(min(1, 255 * 3 - (pix[0] + pix[1] + pix[2])))
    arr_r.append(tmp)
print len(arr_r)

fzz = np.identity(100)

for i in range(100):
    for j in range(100):
        r = np.array(arr_r[i])
        l = np.array(arr_l[j])
        l_r = abs(r - l)

        fzz[i][j] = np.sum(l_r)

print fzz

def merge_image(num):
    toImage = Image.new('RGBA',(1000,1400))
    for i in range(100):
        fromImge = Image.open(str(inuse[i]) + '.png')
        # loc = ((i % 2) * 200, (int(i/2) * 200))
        loc = ((i) * 10, 0)
        print(loc)
        toImage.paste(fromImge, loc)
    toImage = toImage.crop((0, 684, 1000, 725))
    text = pytesseract.image_to_string(toImage)
    text = re.sub(r'[^0-9A-Z]', '', text.upper())
    text = text.replace('O', '0').replace('P', 'F').replace('I', '1').replace('Z', '2').replace('Q', '0').replace('G', '6').replace('S', '5')
    print text
    toImage.save('merged.png')

min_sum = 100000000000000
min_st = 0
for st in range(0, 100):
        inuse = []
        start = st
        sm = 0
        inuse.append(start)
        while True:
            tmp = fzz[start].argsort()
            for i in tmp:
                if i in inuse:
                    continue
                else:
                    sm += fzz[start][i]
                    start = i
                    inuse.append(start)
                    break
            if len(inuse) == 100:
                break
        if min_sum > sm:
            min_sum = sm
            min_st = st
        print inuse
merge_image(min_st)