【Python】四分木の中で最も複雑な領域を分割し続けるアートを実装してみた

はじめに

数ヶ月前に、このツイートが目に留まりました。

非常に魅力的で、自分でも作りたいと思ったのですが、アルゴリズムや実装が公開されているにもかかわらず、実際にやっている人が少ないようでした。

そこで、本記事では、Pythonの画像処理ライブラリPillow(PIL)を使用して、四分木の中で最も複雑な領域を分割し続けるアートの実装方法について解説します。

アルゴリズム

以下の操作を再帰的に繰り返します。

• キャンバス上のすべての矩形領域の中から、最も複雑な領域を選んで四分割する。
• 新しくできた矩形領域において画像の複雑度(score)と平均色を求め、領域を平均色で塗りつぶす。

詳しくは元記事を参照してください。

実装

Rectクラス

Rectクラスは、長方形のフレームの座標情報を保持するクラスです。

calc_areaは長方形のフレームの面積を計算するメソッドです。

class Rect:
    def __init__(self, left: int, right: int, top: int, bottom: int):
        self.left = left
        self.right = right
        self.top = top
        self.bottom = bottom

    def calc_area(self) -> int:
        return (self.right - self.left + 1) * (self.bottom - self.top + 1)

Quadクラス

Quadクラスは、四分木(Quadtree)のノードを表すクラスであり、フレームの座標情報(rect)と複雑度(score)、平均色(color)を持たせています。

heapqで使用するため、__lt__により比較演算子を定義しています。

class Quad:
    def __init__(self, rect: Rect, score: float, color: tuple):
        self.rect = rect
        self.score = score
        self.color = color

    def __lt__(self, other):
        return self.score < other.score

QuadTreeGeneratorクラス

QuadTreeGeneratorクラスは、メインの処理を実装したクラスです。画像の読み込み、分割処理、結果の描画などが含まれています。

class QuadTreeGenerator:
    def __init__(
        self,
        input_path: str,
        iterations: int,
        min_size: int = 4,
        area_power: float = 0.2,
    ):
        self.img = Image.open(fp=input_path)
        self.img_arr = np.asarray(self.img)
        self.iterations = iterations  # 分割を繰り返す回数
        self.min_size = min_size  # 分割を終了する最小のサイズ
        self.area_power = area_power  # 面積のスコアに対する重み

        self.gif_frames = []  # GIFのフレーム
        self.canvas = Image.new("RGB", self.img.size)  # Canvas
        self.draw = ImageDraw.Draw(self.canvas)  # Canvasに描画するためのオブジェクト

        root = self.create_quad(
            rect=Rect(0, self.img.width - 1, 0, self.img.height - 1)
        )
        self.heap = []  # すべてのquadを管理する優先度付きキュー
        heapq.heappush(self.heap, root)

    # 再帰的にを四分木の中で最も複雑な領域を分割し続けるメソッド。指定された回数分だけ`Quad`を生成し、優先度付きキューに追加します。
    def generate_quad_tree(self):
        for _ in range(self.iterations):
            quad = heapq.heappop(self.heap)
            quads = self.split(quad.rect)
            for q in quads:
                heapq.heappush(self.heap, q)
            self.render_and_append_frame(quads=quads)

    # 新しく生成された`Quad`をキャンバスに描画して、`self.gif_frames`にフレームとして追加するメソッド。
    def render_and_append_frame(self, quads: list):
        for quad in quads:
            self.draw.rectangle(
                [
                    (quad.rect.left, quad.rect.top),
                    (quad.rect.right, quad.rect.bottom),
                ],
                fill=quad.color,
                outline=(0, 0, 0),  # 枠線の色は黒
            )
        self.gif_frames.append(self.canvas.copy())

    # 指定された`Rect`から`Quad`オブジェクトを生成するメソッド。最小サイズ以下であれば、分割を終了します。
    def create_quad(self, rect: Rect) -> Quad:
        r_color, r_error = self.calc_color_and_error(rect=rect, color_index=0)
        g_color, g_error = self.calc_color_and_error(rect=rect, color_index=1)
        b_color, b_error = self.calc_color_and_error(rect=rect, color_index=2)
        error = (r_error + g_error + b_error) / 3

        score = -(error * rect.calc_area() ** self.area_power)

        if self.is_quad_below_min_size(rect=rect):
            score = 0

        return Quad(rect=rect, score=score, color=(r_color, g_color, b_color))

    # 指定された`Rect`と色のチャンネルに対して、平均色と複雑度を計算して返すメソッド。
    def calc_color_and_error(self, rect: Rect, color_index: int) -> tuple:
        hist = self.get_rect_color(rect=rect, color_index=color_index)
        total = np.sum(hist * np.arange(len(hist)))
        pixel_num = np.sum(hist)
        average_color = total / pixel_num

        error = (
            np.sum(hist * (np.arange(len(hist)) - average_color) ** 2) / pixel_num
        ) ** 0.5

        return int(average_color), error

    # 指定された`Rect`と色のチャンネルに対して、元の画像の色の分布を`numpy.histogram`として返すメソッド。平均色や複雑度の計算に利用されます。
    def get_rect_color(self, rect: Rect, color_index: int) -> np.ndarray:
        hist, _ = np.histogram(
            self.img_arr[
                rect.top : rect.bottom + 1, rect.left : rect.right + 1, color_index
            ],
            bins=256,
            range=(0, 256),
        )
        return hist

    # 指定された`Rect`が最小サイズ以下かどうかを判定するメソッド。
    def is_quad_below_min_size(self, rect: Rect) -> bool:
        return (
            rect.right - rect.left + 1 <= self.min_size
            or rect.bottom - rect.top + 1 <= self.min_size
        )

    # 指定された`Rect`を四分割して生成された、新しい`Quad`のリストを返すメソッド。
    def split(self, rect: Rect) -> list:
        x_center = (rect.left + rect.right) // 2
        y_center = (rect.top + rect.bottom) // 2

        rects = [
            Rect(rect.left, x_center - 1, rect.top, y_center - 1),
            Rect(x_center, rect.right, rect.top, y_center - 1),
            Rect(rect.left, x_center - 1, y_center, rect.bottom),
            Rect(x_center, rect.right, y_center, rect.bottom),
        ]
        quads = [self.create_quad(rect) for rect in rects]
        return quads

    # `self.gif_frames`のフレームを繋いで、アニメーションGIFを生成するメソッド。
    def save_gif(self, output_path: str, duration: int = 10):
        self.gif_frames[0].save(
            output_path,
            save_all=True,
            append_images=self.gif_frames[1:],
            duration=duration,
            loop=0,
        )

heapq.heappopは最小の要素を取り出すことに注意してください。今回は複雑度が最も高いQuadを取り出すために、スコアをあらかじめ -1 倍しています。

コード全体

requirements.txt

numpy==1.26.2
pillow==10.1.0

main.py

from PIL import Image, ImageDraw
import numpy as np
import heapq


class Rect:
    def __init__(self, left: int, right: int, top: int, bottom: int):
        self.left = left
        self.right = right
        self.top = top
        self.bottom = bottom

    def calc_area(self) -> int:
        return (self.right - self.left + 1) * (self.bottom - self.top + 1)


class Quad:
    def __init__(self, rect: Rect, score: float, color: tuple):
        self.rect = rect
        self.score = score
        self.color = color

    def __lt__(self, other):
        return self.score < other.score


class QuadTreeGenerator:
    def __init__(
        self,
        input_path: str,
        iterations: int,
        min_size: int = 4,
        area_power: float = 0.2,
    ):
        self.img = Image.open(fp=input_path)
        self.img_arr = np.asarray(self.img)
        self.iterations = iterations  # 分割を繰り返す回数
        self.min_size = min_size  # 分割を終了する最小のサイズ
        self.area_power = area_power  # 面積のスコアに対する重み

        self.gif_frames = []  # GIFのフレーム
        self.canvas = Image.new("RGB", self.img.size)  # Canvas
        self.draw = ImageDraw.Draw(self.canvas)  # Canvasに描画するためのオブジェクト

        root = self.create_quad(
            rect=Rect(0, self.img.width - 1, 0, self.img.height - 1)
        )
        self.heap = []  # すべてのquadを管理する優先度付きキュー
        heapq.heappush(self.heap, root)

    # 再帰的にを四分木の中で最も複雑な領域を分割し続けるメソッド。指定された回数分だけ`Quad`を生成し、優先度付きキューに追加します。
    def generate_quad_tree(self):
        for _ in range(self.iterations):
            quad = heapq.heappop(self.heap)
            quads = self.split(quad.rect)
            for q in quads:
                heapq.heappush(self.heap, q)
            self.render_and_append_frame(quads=quads)

    # 新しく生成された`Quad`をキャンバスに描画して、`self.gif_frames`にフレームとして追加するメソッド。
    def render_and_append_frame(self, quads: list):
        for quad in quads:
            self.draw.rectangle(
                [
                    (quad.rect.left, quad.rect.top),
                    (quad.rect.right, quad.rect.bottom),
                ],
                fill=quad.color,
                outline=(0, 0, 0),  # 枠線の色は黒
            )
        self.gif_frames.append(self.canvas.copy())

    # 指定された`Rect`から`Quad`オブジェクトを生成するメソッド。最小サイズ以下であれば、分割を終了します。
    def create_quad(self, rect: Rect) -> Quad:
        r_color, r_error = self.calc_color_and_error(rect=rect, color_index=0)
        g_color, g_error = self.calc_color_and_error(rect=rect, color_index=1)
        b_color, b_error = self.calc_color_and_error(rect=rect, color_index=2)
        error = (r_error + g_error + b_error) / 3

        score = -(error * rect.calc_area() ** self.area_power)

        if self.is_quad_below_min_size(rect=rect):
            score = 0

        return Quad(rect=rect, score=score, color=(r_color, g_color, b_color))

    # 指定された`Rect`と色のチャンネルに対して、平均色と複雑度を計算して返すメソッド。
    def calc_color_and_error(self, rect: Rect, color_index: int) -> tuple:
        hist = self.get_rect_color(rect=rect, color_index=color_index)
        total = np.sum(hist * np.arange(len(hist)))
        pixel_num = np.sum(hist)
        average_color = total / pixel_num

        error = (
            np.sum(hist * (np.arange(len(hist)) - average_color) ** 2) / pixel_num
        ) ** 0.5

        return int(average_color), error

    # 指定された`Rect`と色のチャンネルに対して、元の画像の色の分布を`numpy.histogram`として返すメソッド。平均色や複雑度の計算に利用されます。
    def get_rect_color(self, rect: Rect, color_index: int) -> np.ndarray:
        hist, _ = np.histogram(
            self.img_arr[
                rect.top : rect.bottom + 1, rect.left : rect.right + 1, color_index
            ],
            bins=256,
            range=(0, 256),
        )
        return hist

    # 指定された`Rect`が最小サイズ以下かどうかを判定するメソッド。
    def is_quad_below_min_size(self, rect: Rect) -> bool:
        return (
            rect.right - rect.left + 1 <= self.min_size
            or rect.bottom - rect.top + 1 <= self.min_size
        )

    # 指定された`Rect`を四分割して生成された、新しい`Quad`のリストを返すメソッド。
    def split(self, rect: Rect) -> list:
        x_center = (rect.left + rect.right) // 2
        y_center = (rect.top + rect.bottom) // 2

        rects = [
            Rect(rect.left, x_center - 1, rect.top, y_center - 1),
            Rect(x_center, rect.right, rect.top, y_center - 1),
            Rect(rect.left, x_center - 1, y_center, rect.bottom),
            Rect(x_center, rect.right, y_center, rect.bottom),
        ]
        quads = [self.create_quad(rect) for rect in rects]
        return quads

    # `self.gif_frames`のフレームを繋いで、アニメーションGIFを生成するメソッド。
    def save_gif(self, output_path: str, duration: int = 10):
        self.gif_frames[0].save(
            output_path,
            save_all=True,
            append_images=self.gif_frames[1:],
            duration=duration,
            loop=0,
        )


# 使用例
quad_tree_generator = QuadTreeGenerator(input_path="./kamome.jpg", iterations=300)
quad_tree_generator.generate_quad_tree()
quad_tree_generator.save_gif(output_path="./kamome.gif")

生成例

背景がベタ塗りで、複雑度にコントラストがある画像を選ぶと上手くいくようです。

出典: Pixabay

おわりに

いかがでしたか？ぜひみなさんも好きな言語で実装してみましょう！

参考