Restaurez les photos décousues avec l'optimisation!

Les indices sont des photos décousues

Lorsque la police est entrée dans la cachette du criminel, il était trop tard, après que le criminel eut déchiqueté une photo des preuves. Réorganisez les bandes déchiquetées pour restaurer vos photos.

Préparation de photos disjointes

Charger la photo → Ar variable

Utilisez la photo de stocksnap.io. Je vais le lire avec 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) #Lire des photos
ar = np.array(im.convert('L').getdata()) #gris('L')Et np.Convertir en ndarray
ar = ar.reshape((im.height, -1))
plt.imshow(ar, cmap='gray'); #afficher

image

Séparer la photo → SP variable

Coupez-le horizontalement et mélangez-le tous les 20 pixels.

python3


wd = 20 #Largeur de bande
n = im.height // wd #Numéro de division
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 #Ne laissez que le début dans le même ordre, mélangez le reste
plt.imshow(np.concatenate(sp), cmap='gray'); #Photos démembrées

image

Façon de penser

Pour n bandes, déterminez si elles seront connectées ou non dans un graphe en deux parties.

image

C'est-à-dire que lorsque le nœud supérieur i et le nœud inférieur j sont connectés, la bande j est connectée sous la bande i. Lorsqu'il est connecté, le poids est réglé à moins "50% de la norme de la petite différence entre les pixels de la ligne inférieure de la bande i et les pixels de la ligne supérieure de la bande j", et le minimum est ajusté à 0. .. Pour ce graphique en deux parties, vous pouvez trouver l'arrangement en résolvant le problème de correspondance de poids maximum du problème d'optimisation de combinaison.

Calculer le poids → wgt

Calculez comme suit.

python3


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

Créer un graphe orienté → g

Soit le nœud supérieur 0 ... n-1 et le nœud inférieur n ... 2 * n-1. Ce graphique est un graphique en deux parties.

python3


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

Résoudre et afficher le résultat → mtc

Résout le problème de correspondance de poids maximum pour un graphique en deux parties. Si vous suivez le résultat (mtc) dans l'ordre de 0, vous pouvez voir comment vous connecter.

python3


mtc = nx.max_weight_matching(g) #Résolvez le problème de correspondance de poids maximum
#Mettre l'ordre en res
i, res = 0, []
for _ in r:
    res.append(sp[i])
    i = mtc[i] - n
plt.imshow(np.concatenate(res), cmap='gray'); #Affichage des résultats

image

Pour le moment, cela a fonctionné.

Recommended Posts