[PYTHON] Stellen Sie unzusammenhängende Fotos mit Optimierung wieder her!

Die Hinweise sind unzusammenhängende Fotos

Als die Polizei das Versteck des Verbrechers betrat, war es zu spät, nachdem der Verbrecher ein Foto der Beweise vernichtet hatte. Ordnen Sie die zerkleinerten Streifen neu an, um Ihre Fotos wiederherzustellen.

Vorbereitung nicht zusammenhängender Fotos

Foto laden → Variable ar

Verwenden Sie das Foto von stocksnap.io. Ich werde es mit Python lesen.

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) #Fotos lesen
ar = np.array(im.convert('L').getdata()) #grau('L')Und np.In ndarray konvertieren
ar = ar.reshape((im.height, -1))
plt.imshow(ar, cmap='gray'); #Anzeige

image

Brechen Sie das Foto auseinander → Variable sp

Schneiden Sie es horizontal und mischen Sie es alle 20 Pixel.

python3


wd = 20 #Streifenbreite
n = im.height // wd #Abteilungsnummer
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 #Lassen Sie nur den Anfang in der gleichen Reihenfolge und mischen Sie den Rest
plt.imshow(np.concatenate(sp), cmap='gray'); #Zerstückelte Fotos

image

Denkweise

Überlegen Sie für n Streifen, ob sie in einem zweiteiligen Diagramm verbunden werden sollen oder nicht.

image

Das heißt, wenn der obere Knoten i und der untere Knoten j verbunden sind, ist der Streifen j unter dem Streifen i verbunden. Wenn verbunden, wird das Gewicht auf minus "50% Norm der kleinen Differenz zwischen den Pixeln in der unteren Reihe des Streifens i und den Pixeln in der oberen Reihe des Streifens j" eingestellt, und das Minimum wird auf 0 eingestellt. .. Für dieses zweiteilige Diagramm können Sie die Anordnung finden, indem Sie das Problem der maximalen Gewichtsanpassung von [Problem der Kombinationsoptimierung] lösen (http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721).

Gewicht berechnen → Gewicht

Berechnen Sie wie folgt.

python3


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

Erstellen Sie einen gerichteten Graphen → g

Der obere Knoten sei 0 ... n-1 und der untere Knoten sei n ... 2 * n-1. Dieses Diagramm ist ein zweiteiliges Diagramm.

python3


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

Löse und zeige das Ergebnis → mtc

Behebt das Problem der maximalen Gewichtsanpassung für ein zweiteiliges Diagramm. Wenn Sie dem Ergebnis (mtc) in der Reihenfolge von 0 folgen, können Sie sehen, wie Sie eine Verbindung herstellen.

python3


mtc = nx.max_weight_matching(g) #Lösen Sie das Problem der maximalen Gewichtsanpassung
#Geben Sie die Bestellung in res
i, res = 0, []
for _ in r:
    res.append(sp[i])
    i = mtc[i] - n
plt.imshow(np.concatenate(res), cmap='gray'); #Ergebnisanzeige

image

Vorerst hat es funktioniert.

Recommended Posts