まえがき

フラクタルから複雑でランダムな部分を抽出する簡便な手法を考えてみました。

TL;DR

複雑度を定量的に定義し、決められた範囲内の複雑度の高い場所を拡大していくことで、集合の「絵的に面白い」部位をランダムかつ自動的に選択します。
成果物はこちらに置いてあります。

問題設定

以下の手法はフラクタルの種類に関係なく用いることができますが、有名さと定義の簡便さからマンデルブロ集合を考えます。
Wikipediaの記事を参考にまずは問題設定をします。

数学的背景

$z_n$に関する漸化式

\begin{aligned}
&
z_{n+1} 
=
z_{n}^2
+
c, \\
&
z_{0} = 0
\end{aligned}

を考えます。ここで$z_n$と$c$はともに複素数とします。
複素平面上の全ての$c = x + i y$に対して上記の漸化式を考えると、$z_{\infty}$が発散する場合としない場合の二通りに分けられますが、このうち発散しない部分をマンデルブロ集合と定義します。

数値的取り扱い

コンピュータ上で全ての複素数を連続的に扱うことはできないので、必然的に離散化することになります。
すなわち、無限個の$c = x + i y$の代わりに、二次元格子上の有限の点$(x_m, y_n)$を考え、それぞれの点での集合内外の結果をそのまま画像のピクセルに対応させます。
ここで$m = 0, 1, \cdots, N_x - 1$、$n = 0, 1, \cdots, N_y - 1$で、$N_x, N_y$は解像度に相当します。

同様に漸化式の無限項$z_{\infty}$を求めることはできないので、十分な回数の反復をもって収束と判定します。

こちらにマンデルブロ集合を可視化する簡単な実装（PythonによるシンプルなものとCによるOpenMP並列化されたもの）をおいてあります。

以下の有名な図において、白が収束する数（マンデルブロ集合内）、黒が発散する数（マンデルブロ集合外）です。

複雑な構造は基本的に白い部分と黒い部分の間に存在しますので、上の図の境界部分にフォーカスしていくことになりますが、ランダムかつ安定して拡大するには少し工夫が必要です。

手法

マンデルブロ集合はよく研究されていて、様々な興味深い特徴を持つ点が知られていますが、理解して実装するには相応の数学的知識が必要です。
今回は簡単で再現性が高い方法を考えます。

複雑度

「絵を複雑にしたい」という目的をコードに起こし込むため、まずは複雑さを定量的に定義します。
特に絶対的な定義があるわけではないので好きに決めることができます。
以下では私が思いついた２通りを挙げています。

例１

二次元画像内のあるピクセルpixel(i, j)に着目した時、その点が集合内（pixel(i, j) == True）だったとします。
仮にとなりあう四点(i-1, j)、(i+1, j)、(i, j-1)、(i, j+1)が同じくTrueである場合、この点の周囲では構造変化が乏しく、複雑度は低い（絵的に面白くない）と考えられます。
一方で集合の外（False）がすぐ周囲に存在すれば、(i, j)の周りには細かい構造が存在する、すなわち複雑度が高い（絵的に面白い）点と考えられます。
この事実を元に、「ある点に着目したときの周りの点との集合内外の違いの数」を「複雑度」と定義します。

集合内外に対してそれぞれ0と1のフラグを立てると、0同士や1同士では複雑度は0、それ以外では1となり、これはただのXOR演算a ^ bとなります。

pseudo.py

def check_local_complexity(pixel, i, j):
    center = pixel[j, i]
    x_neg = pixel[j, i-1]
    x_pos = pixel[j, i+1]
    y_neg = pixel[j-1, i]
    y_pos = pixel[j+1, i]
    complexity = 0
    complexity += center ^ x_neg
    complexity += center ^ x_pos
    complexity += center ^ y_neg
    complexity += center ^ y_pos
    return complexity

この考えを元にして複雑な部位を自動的かつランダムに選択する手法を以下に示します。

例２

例１では局所的な複雑さに着目しましたが、もう少し広範囲に対して考えてみます。
集合内外を例えば-1と1で数値化してある領域内を全て合計することを考えます。
仮に全てが集合内であればピクセル数分の負の値を、集合外であればピクセル数分の正の値をとります。
もしこの領域がある程度複雑であれば、-1と1が打ち消しあって、ある程度0に近しい値を取ることが予測されます。

アルゴリズム

上述の複雑度を用いて、複雑な部位を選択する手続きを以下に示します。

マンデルブロ集合の一部を含むように画像中心とグリッド幅を適当に選びます。以下の実装ではこの時の中心をランダムに選択することで毎回異なる結果を得られるようにしています。
与えられた範囲に対して、マンデルブロ集合の内外判定を行い、01のフラグを立てます。
範囲を四等分（縦横にそれぞれ二等分）し、フラグを用いてそれぞれの範囲における複雑度の和を計算します。
四つの矩形のうち一番複雑度の和が高いものを取り出し、これを新しい画像範囲とします。
2に戻ります。

この手続きを任意の回数繰り返すことで、複雑な構造を含む範囲：画像中心を特定できます。

グリッド幅の下限
繰り返すたびに画像範囲が狭まっていく、すなわちグリッド幅が小さくなっていく実装にしているため、浮動小数点誤差が顕著になってきます。
回避する手法が存在しますが、ただの画像生成には少々過ぎた内容だと思い実装は見送りました。
また狭い範囲内では収束判定に必要なイテレーション数も増加し、計算量が多くなっていきます。
おおよそ$10^{-12}$以下の幅に対してはあまり良いパフォーマンスが出ないため、ある程度で打ち切るのが良いかと思います。

画像中心が求まれば、範囲（ズーム）を適当に設定して着色を行うことができます。
以下の動画は求めた中心にフォーカスしていく例です。

実装

最後にコードを示します。

特にこの記事のメインの探索アルゴリズムはこちらに実装しています。

あとがき

マンデルブロ集合の面白い部分をランダムに選択して可視化する手法を考えてみました。
複雑度が定義できれば適用できますので、$z_0 = 0$以外の場合、一般化された集合、または他のフラクタルに対しても使えるかと思います。

謝辞

この記事は@satouta310taさんの質問に触発されたものです。
興味深い問題設定を頂けたことを感謝いたします。

フラクタルの複雑部位をランダムに選択する方法