[PYTHON] Placement optimal de plusieurs images

La dernière fois, j'ai écrit un article Génération automatique de modèle de collage . Le collage est un exemple d'application, et il est plus correct de dire "une méthode de division probabiliste d'une zone en n zones".

Cette fois, c'est l'opposé de cela, et quand n rectangles (par exemple, des images) sont donnés, la méthode pour les organiser joliment dans la zone de $ h \ times w $ (ci-après dénommée canevas) est Pensons-y.

Maintenant, encore une fois, nous utiliserons une méthode probabiliste. Un rectangle peut être représenté par une distribution uniforme. Par exemple, la distribution uniforme représentant le canevas $ 1 \ times 1 $ est illustrée dans la figure ci-dessous.

Puisque les rectangles à placer peuvent également être exprimés avec une distribution uniforme, je pense qu'il est bon de faire correspondre la distribution uniforme représentant le canevas avec le mélange de la distribution uniforme représentant les rectangles à placer. La divergence peut être utilisée pour mesurer des choses comme la distance entre les fonctions de densité de probabilité. Cette fois, la divergence KL est adoptée. De cette manière, le mélange est le plus susceptible d'être estimé.

Maintenant, j'ai écrit que les rectangles peuvent être représentés par une distribution uniforme, mais ce n'est pas très pratique en optimisation. Donc, je vais essayer de l'approcher avec Gaussian. Soit les rectangles à placer $ \ {(h_i, w_i) \} _ {i = 1} ^ n $. Cependant, on suppose que $ h_i et w_i $ représentent respectivement la largeur verticale et la largeur horizontale du rectangle $ i $.

Soit la fonction de densité de la distribution de probabilité représentant le rectangle $ i $ $ N (x; \ mu_i, \ Sigma_i) $ (N signifie distribution normale). Ici, $ \ Sigma_i $ est défini comme suit.

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

Cette distribution se rapproche maintenant de l'image. Tout ce que vous avez à faire est d'estimer $ \ mu_i $. Soit $ p (x) $ la fonction de densité de probabilité de la distribution représentant le canevas, et $ q (x) = \ sum_ {i = 1} ^ n w_i N (x; \ mu_i, \ Sigma_i) $ pour le mélange rectangulaire à placer. ， Cependant, soit $ \ sum_ {i = 1} ^ n w_i = 1 $. Cette classe de temps a priori est uniforme, c'est-à-dire $ w_i = \ frac {1} {n} $.

Maintenant, la divergence KL entre $ p et q $ est exprimée comme suit.

\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*}

Enfin, l'échantillon a été approximé comme étant $ x_j \ sim p (x) $. Ceci est minimisé en imposant la contrainte que le rectangle ne dépasse pas et ne couvre pas. Utilisez scipy.optimize.minimize pour l'optimisation. Peut-être une descente de gradient projetée.

Les résultats expérimentaux sont les suivants. La première figure est un rectangle correctement agencé et je ferai de mon mieux pour le reproduire. La figure suivante est le résultat du placement. Vous pouvez voir que c'est bien agencé.

La prochaine fois, dans la génération de modèles de l'article précédent, j'aimerais générer des modèles et implémenter une correspondance à grande vitesse avec une liste d'images donnée.

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)