画像リストからのコラージュ自動生成

前回，前々回の続きです．

- <a href="http://qiita.com/nkt_dev/items/bc8f8002856363d1491a" target="_blank">コラージュテンプレート自動生成</a>
- <a href="http://qiita.com/nkt_dev/items/75121a999469d0d9642d" target="_blank">複数画像の最適配置</a>

ただ，最適化問題を解く「複数画像の最適配置」よりもいい手法を見つけたので，今回はそちらを採用しました．

コラージュテンプレート自動生成により，ほぼ無限にテンプレートを作成できます．なので，たくさんテンプレートを作って，与えられた画像リストを最も綺麗に表示できるものを選べば良いことになります．本当はパラメータでテンプレートを表して，最適化問題を解けば良いのですが，それは今後の課題ということで．

さて，まず「最も綺麗に表示できる」とはどういうことかを考えなくてはいけません．今回は以下の2点を重要視することにしました．

1. 縦横比をいかに維持できるか
2. 画像サイズの分散が小さい

一つ目の基準はわかりやすいです．画像の縦横比を崩せば崩すほど，それは綺麗ではなくなってしまうので，これを維持するようにします．ただ，一つ目の基準だけだと，ある一つの画像だけが大きく表示されて，他の画像をかなり小さくする（究極的には表示しない）ことが許されてしまいます．そのために二つ目の基準を採用しました．

どのようにこれらを実現するかというと，まず以下の値が与えられるとします．

・$h$: 作成するコラージュの縦幅
・$w$: 作成するコラージュの横幅
・$\\{x_i\\}_{i=1}^n$: 埋め込むn枚の画像（$x\_i \in \mathbb{R}\_{++}^2$でそれぞれ縦幅，横幅を表す）

次にテンプレートを位置$L = [\ell\_1 | \cdots | \ell\_n]^T \in \mathbb{R}\_{+}^{n \times 2}$とサイズ$S = [s\_1 | \cdots | s\_n]^T \in \mathbb{R}\_{+}^{n \times 2}$で定義します（本当ははみ出ないように定義を書くべきですが，簡単のため省略します）．テンプレートは以下の関数で作成します．

```py3
def generate_template(n, width, height, random_state=1, max_random_state=1000000, 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 idx, random_state_list in enumerate(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]
        else:
            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 np.array(L)
```

nに対してrandom_stateを変えれば様々なテンプレートを生成できます．ちなみにoffsetは画像と画像の間隔（枠線の太さ）です．

次に，それぞれの画像をテンプレートのどこにおくかを決めます．これは縦横比が最も類似するところを選ぶことで実現します．画像$i$を配置するテンプレート内の場所$j\_i$を以下で求めます．

```math
\begin{align*}
j_i &= \text{argmin}_{j} \ \|r_i - r'_j \|^2 \\
r_i &= \frac{[x_i]_1}{[x_i]_0}, \ r'_j = \frac{[s_j]_1}{[s_j]_0}
\end{align*}
```

ただし，$[x]_i$は$x$の第$i$成分です．なお，一度選んだ場所は選べないこととします．つまり，$\\{j\_1, \ldots, j\_n\\} = \\{1, \ldots, n\\}$です．

以上を用いて，テンプレートのサイズ$S$に対してスコア関数$f$を以下のように定義します．

```math
\begin{align*}
f(S) = \sum_{i=1}^n \|r_i - r_{j_i}\|^2 + \frac{\alpha}{n}
 \sum_{i=1}^n \left( [s_i]_1 [s_i]_2 - \frac{1}{n} \sum_{i'=1}^n [s_{i'}]_1 [s_{i'}]_2 \right)^2
\end{align*}
```

テンプレートを$m$個作成し，これを$S^{(1)}, \ldots, S^{(m)}$とします．最終的に$f$を最小化するテンプレートを選びます．

以上を踏まえて実験してみました．なお，以下の画像を使わせていただきました．

- https://hapila.jp/wp-content/uploads/2017/04/coffee-stock-photo-0e8b300f42157b6f.jpg
- http://www.menshealth.com/sites/menshealth.com/files/coffee-mug.jpg
- https://upload.wikimedia.org/wikipedia/commons/thumb/4/45/A_small_cup_of_coffee.JPG/1280px-A_small_cup_of_coffee.JPG

実験結果は以下のようになりました．

![test3.png](https://qiita-image-store.s3.amazonaws.com/0/37248/a9cbba48-6472-4492-5cad-9bcc2322b891.png)

まぁまぁうまく埋め込めているのではないでしょうか？

今回は，コラージュの自動生成に挑戦してみました．結果として，それなりのものができたんじゃないかなあと思います．今後の課題としては，

- テンプレートをparametrizeして最適化すること
- テンプレートと画像リストとの高速マッチング

などでしょうか．なお，実験に使ったコードは下に載せておきます．読んでいただきありがとうございました．

```py3
import itertools
import glob
import numpy as np
import matplotlib.pyplot as plt
from scipy import stats
from skimage import io, transform


def generate_template(n, width, height, random_state=1, max_random_state=1000000, 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 idx, random_state_list in enumerate(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]
        else:
            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 np.array(L)


def estimate(X, w, h, random_states, offset=0):
    r = np.c_[X[:, 0] / X[:, 1]]
    r2 = r**2
    best_L = None
    best_s = None
    lowest_linkage = np.inf
    for random_state in random_states:
        s = stats.uniform.rvs(0, 1, random_state=random_state)
        L = generate_template(X.shape[0], w*s, h*s, random_state=random_state, offset=offset*s)
        r_temp = np.c_[(L[:, 2] - L[:, 0]) / (L[:, 3] - L[:, 1])]
        r_temp2 = r_temp**2
        dist2 = r2 + r_temp2.T - r.dot(r_temp.T)

        assignment = []
        linkage = 0
        selected = set()
        for i, idx in enumerate(dist2.argsort(axis=1)):
            for j in idx:
                if j not in selected:
                    linkage += dist2[i, j]
                    assignment.append(j)
                    selected.add(j)
                    break
        assignment = np.array(assignment)
        L = L[assignment]
        A = L.copy()
        size = np.c_[L[:, 2] - L[:, 0], L[:, 3] - L[:, 1]]
        L = np.c_[L[:, 0], L[:, 1], np.min(size / X, axis=1)]
        mu = L[:, 2].mean()
        var = np.sqrt(np.mean((L[:, 2] - mu)**2))
        linkage = linkage + var
        if linkage < lowest_linkage:
            lowest_linkage = linkage
            best_L = A
            best_s = s
    return best_L, best_s, lowest_linkage


if __name__ == '__main__':
    images = []
    X = []
    for filename in glob.glob("img/*")[:3]:
        image = io.imread(filename)
        images.append(image)
        X.append((image.shape[0], image.shape[1]))
    X = np.array(X)

    Z = np.c_[X[:, 1], X[:, 0]]

    width, height = 375, 667
    L, s, linkage_value = estimate(Z, width, height, range(100), offset=0)
    L = L / s
    print(linkage_value)

    position = np.int32(np.c_[L[:, 1], L[:, 0]])
    size = np.int32(np.c_[L[:, 3] - L[:, 1], L[:, 2] - L[:, 0]])
    
    canvas = np.zeros((height, width, 3))
    for i in range(len(images)):
        image = images[i]
        print(image.shape)
        canvas[position[i][0]:position[i][0]+size[i][0], position[i][1]:position[i][1]+size[i][1]] = transform.resize(image, size[i])    

    plt.imshow(canvas)
    plt.show()
```