개요

본 기사는 난수 생성 알고리즘인 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)

마지막으로

이를 적용하고 도트를 컬러로 만들거나 도트 크기를 난수로 생성하거나 도트가 아닌 다각형으로 만들면 재미있는 이미지가 생길 수 있습니다.
틀린 부분 등 있으면 댓글 주시면 다행입니다.