[PYTHON] Optimale Platzierung mehrerer Bilder

Letztes Mal habe ich einen Artikel Automatische Generierung von Collagenvorlagen geschrieben. Collage ist ein Anwendungsbeispiel, und es ist richtiger zu sagen, "eine Methode zur probabilistischen Aufteilung eines Bereichs in n Bereiche".

Diesmal ist es das Gegenteil davon, und wenn n Rechtecke (zum Beispiel Bilder) angegeben werden, ist die Methode, sie schön im Bereich von $ h \ times w $ (im Folgenden als Leinwand bezeichnet) anzuordnen, die richtige Lass uns darüber nachdenken.

Nun werden wir wieder eine probabilistische Methode verwenden. Ein Rechteck kann durch eine gleichmäßige Verteilung dargestellt werden. In der folgenden Abbildung ist beispielsweise die gleichmäßige Verteilung dargestellt, die die Leinwand $ 1 \ times 1 $ darstellt.

Da die zu platzierenden Rechtecke auch mit einer gleichmäßigen Verteilung ausgedrückt werden können, halte ich es für besser, die gleichmäßige Verteilung, die die Leinwand darstellt, mit der Mischung der gleichmäßigen Verteilung, die die zu platzierenden Rechtecke darstellt, abzugleichen. Divergenz kann verwendet werden, um Dinge wie den Abstand zwischen Wahrscheinlichkeitsdichtefunktionen zu messen. Diesmal wird die KL-Divergenz übernommen. Auf diese Weise wird die Mischung höchstwahrscheinlich geschätzt.

Nun habe ich geschrieben, dass Rechtecke durch eine gleichmäßige Verteilung dargestellt werden können, aber dies ist bei der Optimierung nicht sehr praktisch. Also werde ich versuchen, es mit Gauß zu approximieren. Die zu platzierenden Rechtecke seien $ \ {(h_i, w_i) \} _ {i = 1} ^ n $. Es wird jedoch angenommen, dass $ h_i und w_i $ die vertikale Breite bzw. die horizontale Breite des rechteckigen $ i $ darstellen.

Die Dichtefunktion der Wahrscheinlichkeitsverteilung, die das Rechteck $ i $ darstellt, sei $ N (x; \ mu_i, \ Sigma_i) $ (N bedeutet Normalverteilung). Hier ist $ \ Sigma_i $ wie folgt definiert.

\Sigma_i = \left[\begin{array}{ll}
\frac{h_i}{2} & 0 \\
0 & \frac{w_i}{2}
\end{array}\right]

Diese Verteilung nähert sich nun dem Bild an. Alles was Sie tun müssen, ist $ \ mu_i $ zu schätzen. Sei $ p (x) $ die Wahrscheinlichkeitsdichtefunktion der Verteilung, die die Leinwand darstellt, und $ q (x) = \ sum_ {i = 1} ^ n w_i N (x; \ mu_i, \ Sigma_i) $ für die zu platzierende rechteckige Mischung. ， Es sei jedoch $ \ sum_ {i = 1} ^ n w_i = 1 $. Diese Zeitklasse vor ist einheitlich, dh $ w_i = \ frac {1} {n} $.

Nun wird die KL-Divergenz zwischen $ p und q $ wie folgt ausgedrückt.

\begin{align*}
KL(p||q) &= \int p(x) \log \frac{p(x)}{q(x)} dx \\
&\approx - \frac{1}{m} \sum_{j=1}^m \log q(x_j)
\end{align*}

Schließlich wurde die Stichprobe als $ x_j \ sim p (x) $ angenähert. Dies wird minimiert, indem die Einschränkung auferlegt wird, dass das Rechteck nicht hervorsteht und nicht abdeckt. Verwenden Sie zur Optimierung scipy.optimize.minimize. Möglicherweise projizierter Gefälleabstieg.

Die experimentellen Ergebnisse sind wie folgt. Die erste Figur ist ein richtig angeordnetes Rechteck, und ich werde mein Bestes tun, um es zu reproduzieren. Die folgende Abbildung zeigt das Platzierungsergebnis. Sie können sehen, dass es gut angeordnet ist.

Beim nächsten Mal möchte ich in der Vorlagengenerierung des vorherigen Artikels Vorlagen generieren und einen Hochgeschwindigkeitsabgleich mit einer bestimmten Bildliste implementieren.

import itertools
import matplotlib.pyplot as plt
import numpy as np
from scipy import stats, optimize

def generate_template(n, width, height, random_state=1, max_random_state=10000, offset=0):
    L = [np.array([offset, offset, width-offset, height-offset])]
    random_state_lists = stats.randint.rvs(0, max_random_state, size=(n-1, 4), random_state=random_state)

    for random_state_list in random_state_lists:
        n_areas = len(L)
        if n_areas == 1:
            i = 0
        else:
            p = np.repeat(1 / (n_areas + i), n_areas)
            x = stats.multinomial.rvs(1, p, size=1, random_state=random_state_list[0])[0]
            i = x.argmax()

        y = stats.bernoulli.rvs(0.5, size=1, random_state=random_state_list[1])[0]
        if y == 0:
            b = stats.uniform.rvs(L[i][0], L[i][2] - L[i][0], size=1, random_state=random_state_list[2])[0]
            #b = stats.uniform.rvs(L[i][0], L[i][2] - L[i][0], size=1, random_state=random_state_list[2])[0]
        else:
            b = stats.uniform.rvs(L[i][1], L[i][3] - L[i][1], size=1, random_state=random_state_list[3])[0]
            #b = stats.uniform.rvs(L[i][1], L[i][3] - L[i][1], size=1, random_state=random_state_list[3])[0]
        if y == 0:
            area1 = np.array([L[i][0], L[i][1], b-offset/2, L[i][3]])
            area2 = np.array([b+offset/2, L[i][1], L[i][2], L[i][3]])
        else:
            area1 = np.array([L[i][0], L[i][1], L[i][2], b-offset/2])
            area2 = np.array([L[i][0], b+offset/2, L[i][2], L[i][3]])
        L.pop(i)
        L.append(area1)
        L.append(area2)
    return L


def negative_log_likelihood(L, X, Z):
    n_components = X.shape[0]
    L = L.reshape((n_components, 2))
    mixture_rate = np.repeat(1/n_components, n_components)
    values = np.zeros((Z.shape[0], n_components))
    for i in range(n_components):
        q = stats.multivariate_normal(L[i]+X[i]/2, [[X[i][0]/2, 0], [0, X[i][1]/2]])
        values[:, i] = q.pdf(Z) * mixture_rate[i]
    tmp = values.sum(axis=1)
    return - np.log(tmp[tmp!=0]).sum()


def compute_intersected_area(p1, p2, x1, x2):
    left = np.max([p1[0], p2[0]])
    right = np.min([p1[0] + x1[0], p2[0] + x2[0]])
    bottom = np.max([p1[1] + x1[1], p2[1] + x2[1]])
    top = np.min([p1[1], p2[1]])
    return np.max([0, (right - left) * (bottom - top)])


def constraint(L, X):
    P = L.reshape(X.shape)
    intersected_area = 0.0
    for i, j in itertools.combinations(range(X.shape[0]), 2):
        #intersected_area += compute_intersected_area(P[i], P[j], X[i]*s[i], X[j]*s[j])
        intersected_area += compute_intersected_area(P[i], P[j], X[i], X[j])
    return intersected_area


def estimate(X, w, h, scale=2, random_state=1):
    r = np.random.RandomState(random_state)
    Ls = r.uniform(0, 1, size=(20, X.shape[0]*2))

    px = stats.uniform(0, 1)
    py = stats.uniform(0, 1)
    pxy = lambda xy: px.pdf(xy[:, 0]) * py.pdf(xy[:, 1])

    n_samples = 500

    Z = np.c_[px.rvs(n_samples, random_state=rs), py.rvs(n_samples, random_state=rs+1)]

    constraints = ({"type": "eq", "fun": constraint, "args": (X,)})
    #bounds = [tmp for i in range(X.shape[0]) for tmp in [(0, scale-X[i][0]), (0, scale-X[i][1])]]
    bounds = [tmp for i in range(X.shape[0]) for tmp in [(0, w*scale-X[i][0]), (0, h*scale-X[i][1])]]
    lowest_loss = np.inf
    best_result = None
    for L in Ls:
        result = optimize.minimize(
            negative_log_likelihood,
            L.ravel(),
            args=(X, Z),
            bounds=bounds,
            options={"disp": True, "maxiter": 500},
            constraints=constraints,
        )
        if result.status != 0:
            continue
        loss = negative_log_likelihood(result.x.reshape(X.shape), X, Z)
        if loss < lowest_loss:
            best_result = result
            lowest_loss = loss
    result = best_result
    return result.x.reshape(X.shape)


def plot_result(L_pred, X, n_samples=100, colors=["b", "g", "r", "c", "m", "y", "k"]):
    n = L_pred.shape[0]
    for i in range(n):
        Z_i = np.c_[stats.uniform.rvs(L_pred[i][0], X[i][0], size=n_samples),
                    stats.uniform.rvs(L_pred[i][1], X[i][1], size=n_samples)]
        print(Z_i.max())
        plt.scatter(Z_i[:, 0], Z_i[:, 1], c=colors[i])
    plt.show()

rs = 1
width, height = 1, 1

L = generate_template(2, width, height, random_state=3, offset=0)
L = np.array(L)
X = np.c_[L[:, 2] - L[:, 0], L[:, 3] - L[:, 1]]


L_pred = estimate(X, width, height, scale=2)

tmp = np.maximum((L_pred + X).max(axis=0), 1)
plot_result(L_pred / tmp, X / tmp, n_samples=500)