단서는 흩어져 있습니다.

범인의 아지트에 경찰이 밟았을 때, 벌써 늦게, 범인은 증거의 사진을 슈레더에 걸친 후였다.
슈레더에 걸린 스트립 모양의 조각을 정렬하여 사진을 복원합시다.

화려한 사진 준비

사진 로드 → 변수 ar

s와 cks p. 이오 의 사진을 사용합니다. 파이썬으로 읽어 보겠습니다.

python3

import numpy as np, networkx as nx, matplotlib.pyplot as plt
from PIL import Image
from urllib import request
with request.urlopen('https://snap-photos.s3.amazonaws.com/'
                     'img-thumbs/960w/X8CW5LGMWI.jpg') as fd:
    im = Image.open(fd) # 写真読込
ar = np.array(im.convert('L').getdata()) # グレー('L')にして、np.ndarrayに変換
ar = ar.reshape((im.height, -1))
plt.imshow(ar, cmap='gray'); # 表示

사진을 흩어지기 → 변수 sp

20픽셀마다 옆으로 자르고 셔플하여 연결합니다.

python3

wd = 20 # 短冊の幅
n = im.height // wd # 分割数
r = range(n)

sp = [ar[i*wd:(i+1)*wd] for i in r]
tmp = sp[1:]
np.random.seed(1)
np.random.shuffle(tmp)
sp = [sp[0]] + tmp # 先頭のみ同じ順番のままにし、残りシャッフル
plt.imshow(np.concatenate(sp), cmap='gray'); # バラバラの写真

사고방식

n개의 스트립에 대해 연결할지 여부를 2부 그래프로 생각합니다.



즉, 위의 노드 i와 아래의 노드 j를 묶을 때, 스트립 i 아래에 스트립 j를 연결하기로 한다.
연결할 때 가중치는 "스트립 i 아래 1열의 픽셀과 스트립 j 위 1열의 픽셀 차이의 작은 값의 50%의 규범"의 마이너스로 하고 최소가 0이 되도록 조정합니다 .
이 2부 그래프에 대해서, 조합 최적화 문제 의 최대 가중치 매칭 문제를 풀어서, 배열 방법을 요구할 수 있습니다.

가중치 계산 → wgt

아래와 같이 계산합니다.

python3

nn = int(im.width * 0.5) # 50%を使う
t = [[np.linalg.norm(np.sort(np.abs(sp[i][-1] - sp[j][0]))[:nn])
      for j in r] for i in r]
wgt = np.max(t) - t

유향 그래프 작성 → g

위의 노드를 0...n-1, 아래 노드를 n...2*n-1이라고 합니다. 이 그래프는 2부 그래프입니다.

python3

g = nx.DiGraph() # 有向グラフ
for i in r:
    for j in r:
        if i != j:
            g.add_edge(i, j+n, weight=wgt[i][j])

해결하고 결과를 표시합니다 → mtc

2부 그래프의 최대 가중치 매칭 문제를 해결합니다. 0부터 순서대로 결과(mtc)를 따라가면 연결 방법을 알 수 있습니다.

python3

mtc = nx.max_weight_matching(g) # 最大重みマッチング問題を解く
# resに順番を入れる
i, res = 0, []
for _ in r:
    res.append(sp[i])
    i = mtc[i] - n
plt.imshow(np.concatenate(res), cmap='gray'); # 結果表示

일단 잘 작동했습니다.