[PYTHON] Restore disjointed photos with optimization!

The clues are disjointed photos

When police stepped into the criminal's hideout, it was too late, after the criminal shredded a photo of the evidence. Rearrange the shredded strips and restore your photos.

Preparing disjointed photos

Load photo → variable ar

Use the photo from stocksnap.io. Let's load it in Python.

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) #Photo reading
ar = np.array(im.convert('L').getdata()) #gray('L')And np.Convert to ndarray
ar = ar.reshape((im.height, -1))
plt.imshow(ar, cmap='gray'); #display

image

Break apart photos → Variable sp

Cut it horizontally and shuffle it every 20 pixels.

python3


wd = 20 #Strip width
n = im.height // wd #Division number
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 #Leave only the beginning in the same order and shuffle the rest
plt.imshow(np.concatenate(sp), cmap='gray'); #Dismembered photos

image

Way of thinking

Consider whether or not to connect n strips with a bipartite graph.

image

That is, when the upper node i and the lower node j are connected, the strip j is connected under the strip i. When connected, the weight should be minus the "norm of 50% of the small difference between the pixels in the lower row of strip i and the pixels in the upper row of strip j", and the minimum should be 0. .. For this bipartite graph, you can find the arrangement by solving the maximum weight matching problem of Combinatorial optimization problem.

Calculate weight → wgt

Calculate as follows.

python3


nn = int(im.width * 0.5) # 50%use
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

Create directed graph → g

Let the upper node be 0 ... n-1 and the lower node be n ... 2 * n-1. This graph is a bipartite graph.

python3


g = nx.DiGraph() #Directed graph
for i in r:
    for j in r:
        if i != j:
            g.add_edge(i, j+n, weight=wgt[i][j])

Solve and display the result → mtc

Solves the maximum weight matching problem for bipartite graphs. If you follow the result (mtc) in order from 0, you can see how to connect.

python3


mtc = nx.max_weight_matching(g) #Solve the maximum weight matching problem
#Put the order in res
i, res = 0, []
for _ in r:
    res.append(sp[i])
    i = mtc[i] - n
plt.imshow(np.concatenate(res), cmap='gray'); #Result display

image

For the time being, it worked.

Recommended Posts