Metropolisアルゴリズムを使って画像から乱数を生成してドット絵を生成する

概要

本記事は乱数生成アルゴリズムであるMetropolisアルゴリズムによって画像から乱数を生成し、ドット絵を作成するというものです。タイトルのままですみません。以下のような形です。

Motivation

最近Generative Artにハマっています。WikiによるGenerative Artの説明は以下。

ジェネレーティブアートまたはジェネラティブアート（英: Generative Art）は、コンピュータソフトウェアのアルゴリズムや数学的/機械的/無作為的自律過程によってアルゴリズム的に生成・合成・構築される芸術作品を指す。コンピュータの計算の自由度と計算速度を活かし、自然科学で得られた理論を実行することで、人工と自然の中間のような、統一感を持った有機的な表現を行わせる作品が多い。

Metropolisアルゴリズムのような乱数生成アルゴリズムとGenerative Artって相性良いのでは？というところからこういうことができるかやってみようと思いました。
初めにソースコードを貼っておきます。
また、ここでやっていることを応用し、写真からいくつかの処理（ドット絵、一筆書きの絵）などができるiOSアプリ作成したので宣伝しておきます。

Metropolisアルゴリズムとは

私の解釈も含んでいるので間違っている部分もあるかもしれませんがご了承ください。
$z$→$z'$の遷移確率を$T(z'|z)$とします。
この時、$T(z'|z)$を以下のように決めることを考えます。

T(z'|z) = min(1, \frac{p(z')}{p(z)})

すると、以下のような等式が成り立ちます。

\begin{align}
p(z)T(z'|z) &= min(p(z), p(z')) \\
&= p(z')T(z|z')
\end{align}

これはzから来てz'にいる確率と、z'から来てzにいる確率が同じことを意味します。
$z$で総和を取ると以下のような等式が成り立ちます。式を見ると、$p(z')$が常に一定であることがわかります。つまり、このように遷移確率を選ぶことにより、分布が崩れず常に同じ分布から乱数を生成できるようになります。

\begin{align}
p'(z') &= \sum_{z} p(z)T(z'|z) \\
&= \sum_{z} p(z')T(z|z') \\
&= p(z')\sum_{z} T(z|z') \\
&= p(z')
\end{align}

これを擬似コードにすると、以下のようになると思われます。

z = random(0, 1) * maxZ
for i in range(n):
    z_next = random(0, 1) * maxZ
    if p(z_next) < p(z):
        p(z_next)/p(z)の確率で、z = z_next
    else:
        z_next = z

コード

コードはシンプルで以下の通りです。

import random

import cv2
import numpy as np


class MetropolistDotPainting:
    def __init__(self, img_path, save_path):
        self.img = cv2.imread(img_path)
        self.save_path = save_path

    def draw(self, n, size):
        img_paint = np.ones(self.img.shape)
        img_paint *= 255

        img_width = self.img.shape[1]
        img_height = self.img.shape[0]

        x = img_width * random.random()
        y = img_height * random.random()

        for i in range(n):
            x_n = img_width * random.random()
            y_n = img_height * random.random()

            prob = self.get_prob(x, y)
            prob_n = self.get_prob(x_n, y_n)

            if prob_n < prob:
                ratio = prob_n / prob
                rand = random.random()
                if ratio > rand:
                    cv2.circle(img_paint, (int(x_n), int(y_n)), size, (0, 0, 0), -1)
                    x = x_n
                    y = y_n
            else:
                cv2.circle(img_paint, (int(x_n), int(y_n)), size, (0, 0, 0), -1)
                x = x_n
                y = y_n

        cv2.imwrite(self.save_path, img_paint)

    def get_prob(self, x, y):
        x = int(x)
        y = int(y)
        b = self.img[y, x, 0]
        g = self.img[y, x, 1]
        r = self.img[y, x, 2]
        prob = 0.299 * r + 0.587 * g + 0.114 * b
        prob /= 255
        prob = 1 - prob
        prob = prob ** 5
        return prob


if __name__ == '__main__':
    img_path = './data/lena.png'
    save_path = './data/lena_dot.jpg'
    mdp = MetropolistDotPainting(img_path, save_path)
    mdp.draw(100000, 1)

最後に

これを応用し、ドットをカラーにしたり、ドットのサイズを乱数で生成したり、ドットではなく多角形にしたりすると面白い画像ができるかもしれません。
間違っている部分などありましたらコメントいただけると幸いです。