satouta310ta
@satouta310ta (さとうた)

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

マンデルブロ集合の自己相似点を自動検出していい感じの画像を生成したい

解決したいこと

マンデルブロ集合を使った画像生成システムを作るにあたって、図中の拡大箇所を自動で検出してくれるような機能を付けたいと思っています。
その際に、出力される画像を出来るだけ複雑な図柄にするために、マンデルブロ集合内の自己相似点を自動検出してそこを拡大していくようなアルゴリズムを考えているのですが、その具体的なコードが思い浮かびません…。
自分は数学がてんでダメなもので、言語は問いませんのでなるべくコードとして具体例をご教授いただけますと助かります。

自分で試したこと

マンデルブロ集合の描画、拡大、カラーリングなどに関しては調べたらいくらでもコード例はあるのですが、
「拡大箇所を自動検出する」となるとMisiurewicz points、Feigenbaum pointsのような数式を理解してコードに落とし込むしかないのか…と苦戦してます

0

2Answer

連投失礼します。
上の手法を自分でも試してみたのですが、イマイチ満足いく結果にならなかったので、次のような代案を考えてみました。
数学は全く必要なく、「絵を複雑にしたい」という目的をそのままコードに起こし込むものです。

まず「複雑度」を定義します。
どのような定義でも構いませんが、例えば次のようなものが簡便かと思います。
あるピクセルが集合の中(漸化式が収束する点)だったとします。
仮にとなりあう四ピクセルが全て同様に集合の中であれば周辺の複雑度は低いと考えます。
なぜならその周囲では構造変化が乏しく、絵的には面白くない点と考えられるからです。
一方で集合の外(漸化式が発散する点)がすぐ周囲に存在すれば、その点の周りには細かい構造が存在する、すなわち複雑度の高い点と考えられます。
着目するピクセルが集合外であった場合も全く同様で、プログラム的にはXOR演算に相当します。
これを元にしたアルゴリズムを以下に示します。

  1. 与えられた範囲に対して、よくマンデルブロ集合に対して行う内外処理を行い、収束すれば1、しなければ0のフラグを立てます(逆でも構いません)。
  2. 範囲を四等分(縦横にそれぞれ二等分)し、上のステップで計算したフラグを用いてそれぞれの範囲における複雑度の和を計算します。
  3. 四つの矩形うち一番複雑度の和が高い部分を取り出し、これを新しい範囲としてステップ1から繰り返します。

初期の集合全体を含む範囲からある程度の回数この操作を繰り返すことで、おそらく確実に境界を含む一部分を取り出すことができます。
なお繰り返しすぎると浮動小数点誤差が顕著になるため注意が必要かもしれません。
中心が求まればあとは範囲(ズーム)を適当に設定してお好みの着色をしていただければと思います。

蛇足かとも思いますが、上のアルゴリズムで中心点を決定した後12桁ほど拡大していった様子および使用したコードを以下に示します。

2Like

Comments

  1. @satouta310ta

    Questioner

    反応が遅くなってしまい申し訳ありません。
    記事とコードのほう見させていただき大変参考になりました。
    相似点を数学的に導いてプログラムに落とし込むしかないのか、と勝手思い込んでハマってたので、ご提示いただいた画像解析的、探索アルゴリズム的なアプローチには蒙が啓かれました!
    そのような考え方であればまた違ったアルゴリズムも検討の余地がありそうなので、自分の方でもまたいくつか試してみたいと思います。
    個人的には二分探索での境界線()を探索する方法にも惹かれてるので、この方法で上手いこといったらまた共有させていただきます。

  2. 面白いテーマでしたので勝手に深掘りさせていただきました。
    一案として捉えていただき、他のアプローチ含め色々と試していただければ幸いです。

複雑な数学が一切必要ない方法として以下のものが第一に思いつきました。

  1. 集合内外に一点ずつになるよう二点A(内)B(外)を選択します。
  2. 線上の一点Cをランダムに選択して漸化式を解き、Cの内外を判定します。
  3. Cが集合内の時はBCを、集合外の時はACを新たな対角としてこのプロセスを繰り返します。

端的に言えば二分探索です。
自己相似点について全く考慮していませんが、このプロセスでは二点を対角に持つ画像内に必ず境界が存在するので、ある程度の複雑性を持った図形をランダムに生成する目的は達成できるような気がします。

ただし注意点がいくつか考えられます。

  1. 基本的にはじめの二点ABは画像のアスペクト比と一致するように選ぶ必要があります。
  2. 反復を行うほど境界に近い二点を選ぶ確率が上がる(すなわち画像全体に複雑な模様が広がる)と思いますが、その分浮動小数点演算では精度が低下します。
  3. 検証は全くしていません(時間ができたらやってみます)。
1Like

Comments

  1. @satouta310ta

    Questioner

    な、なるほど!非常にシンプルな妙案で目から鱗が落ちました!ありがとうございます。試してみます

Your answer might help someone💌