反復関数集合によるフラクタル画像生成

Fractal Image Generation with Iterate Function Set

浅井貴浩
Takahiro Asai
研究開発本部 村山塾
Murayama juku, Research and Development Group

本CD-ROMに収録されているプログラムにより、 「反復関数集合によるフラクタル画像生成」を実際に試すことができます。 詳しくは「IFSViewer ver.1.0」を御覧下さい。


要旨

反復関数集合を用いることにより、少ないデータから多彩なフラクタル画像を得る方法を開発した。 従来のフラクタル画像生成方法、 例えばジュリア・マンデルブロー集合を図示するものや自己相似関数を用いるHata-Hatchinsonの方法では、 いずれも反復過程において常に一種類のパラメータしか用いないために生成される画像は単純なものであった。 本研究では、複数のパラメータからなる反復関数集合を作成し、 反復の各段階において集合の要素であるパラメータを選択して適用することにより、 少ないデータからより多彩な画像を生成することを可能とした。

ABSTRACT

A new fractal image generation method using a generation function set is developed. The generation function set which has several different parameters is defined, one of which to be selected at each recursion. The usual methods use only one parameter, such as the Julia-Mandelbrot and the Hata-Huchinson methods. As a result, various kinds of unique class of non-linear fractal images from a few data are constructed.

1. はじめに

近年ポスター等のデザインや映画、テレビCM等において計算機システムにより作成される CG(Computer Graphics)画像が多用されており、 新しい種類の画像を生成するためのアルゴリズムへの期待が高まっている。 またDTP(Desk Top Publishing)システムやInternetの普及に伴い、 個人による文書やWebページの作成等に使用するデジタルコンテンツとしてのCG画像、 それらを作成するアプリケーションへの需要が高まっている。

こうした背景の中でMandelbrotにより提唱されたフラクタル幾何学 [1] はCG画像を生成するアルゴリズムの一つとして現在広く使われている。 フラクタル画像生成の方法は大きく2種類に分けることができ、 一方はfBm [2] 等を利用して不確定要素を付加することによりフラクタル性を持つ形状を生成するもので、 ランダムフラクタルあるいは非決定論的フラクタルと呼ばれる。 これは主に地形の起伏や雲等の自然物の形状モデルを作成するために使われている。 もう一方は数式により求められるフラクタル集合を画像として描くもので、 不確定要素がないことから決定論的フラクタルと呼ばれる。 反復関数集合による方法 [3]、 Hata-Hatchinsonの方法 [4]、 L-systemによる方法 [5]やJulia、Mandelbrot集合を図示する方法 [1]等がこれに当たる。 決定論的フラクタルアルゴリズムにより作成された画像は、 形状の独特な複雑さから計算機による画像を連想させ、主にポスターや広告等のデザインに使われることが多い。

決定論的フラクタルによる画像生成の場合、同じ数式を用いるならば一種類のパラメータにより一種類の画像が決まる。 従ってパラメータを変化させながら生成画像のバリエーションを得ることになるが、 同じ数式から生成される画像には一定の傾向が見られるため変化に乏しい。 さらに生成される画像は自己相似集合 [6] [7] となるため、全体のミニチュアが各部に繰り返し現れるパターン画像となり形状が単調で面白みに欠ける。 そこで反復回数等の条件付けによる色の変更、 集合を図示する領域を変える等の処理で画像のバリエーションを得ているのが現状である。

本研究はこうした決定論的フラクタルによる画像生成の問題点に着目し、 反復関数系を用いる決定論的フラクタル画像生成方法を拡張、 複数のパラメータを反復段階において変更することで 多彩なフラクタル画像を生成可能とする技術を開発することを目的とした。

2. 反復関数系によるフラクタル画像生成

2.1. 反復関数系

基本となる反復関数系の定義および定理を示す。 詳細は [8] にある。

定義2.1

(X, d)を完備な距離空間とする。 このときハウスドルフ空間Hとは、 空間内の点が空集合を除くコンパクトな部分集合となるような空間を意味する。

定義2.2

反復関数系は、完備な距離空間(X, d)と、 n = 1,2,...,Nにおいてそれぞれ縮小係数snを持つ縮小写像 omega_{n}: X -> Xの有限集合とから成る。 'IFS'の略記は'iterated function system(反復関数系)'として使用される。 このIFSを
{X: omega_{n}, n =1, 2,
...,N}と表記し、またその縮小係数は
s = Max{sn:n = 1, 2, ..., N} である。

定理2.1

{X: omega_{n}, n =1, 2, ...,N}を縮小係数sをもつIFSとすると、 全ての B in H(X) において変換 W: H(X) -> H(X)

{W(B) = bigcup_{n=1}^{N}
omega_{n}(B)}

で定義される。これは完備な距離空間(H(X), h(d))上での縮小係数sの縮小写像である。 この縮小写像の一意の不動点 A inH(X) は以下の式を満たす。

A = W(A) = bigcup_{n=1}^{N}
omega_{n}(A)

また任意の B in H(X) について、 A = Lim_{n->infnity} W^{circle n}(B)で与えられる。

2.2. 画像生成の例

IFSを利用するフラクタル画像生成方法について説明する。 ここでは距離空間(X, d)をユークリッド平面R2とユークリッド距離とし、 R2上の縮小写像 omega_{i}: R^{2} ->
R^{2}をアフィン変換

2D Affine Transformation … (1)

とする。

例えばKochの雪片曲線を作成するためのIFSは2つの縮小写像から成り、 それぞれ式(1)に対応するパラメータ a, b, c, d, e, f はTable.1のようになる。

Table.1. Parameters of generating the Koch curve

a

b

c

d

e

f

a.W1

omega_1

1/2

sqrt{3}/6

sqrt{3}/6

-1/2

0

0

omega_2

1/2

-sqrt{3}/6

-sqrt{3}/6

-1/2

1/2

sqrt{3}/6

初期集合K0を適当に定め、 K0からn回反復後の集 合

K_{n} = omega_{1}(K_{n-1} \cup
omega_{2}(K_{n-1}) = W^{\circle n}(K_{0})

を算出し、画像として描画する。

K0を頂点 (0, 0), (1, 0), (1/2,
\sqrt{3}/6)とする三角形と し、 8回反復後のK8を求めて画像生成していく様子を Fig.1に 示す。

Generating Koch curve
Fig.1. Example of generating the Koch curve under IFS

算出された集合を画像にする際、反復回数や軌跡による色の変更等の処理を行なうことでバリエーションが得られる。 また反復回数nを十分大きくとるとき 不動点は出力デバイス上で1ピクセルに収束するため初期集合は任意であるが、 生成する形状の興味という点からは少ない回数で反復を打ち切ることも可能であり、 このときFig.1K1か らK3に見られるように 細部にK0の形状が現れる。 文献 [4] ではK0を工夫することにより 画像のバリエーションを増やしている。

IFS {omega_{1}, omega_{2}} のパラメータを変化させることで様々な形状を生成することが可能である。 パラメータを変化させたときに同様の方法で生成した画像の例を Fig.2 b.からfに示す。 各画像を生成するためのパラメータは APPENDIX A.1. に示した。

Images generated by IFS
Fig.2. Example of image generated by IFS

3. 反復関数集合によるフラクタル画像生成

3.1. 反復関数集合

反復関数系を拡張する。 拡張の目的はより多彩なフラクタル画像を得ることにある。 反復法における変換Wは反復過程において終始固定であるため、最終的に得られる集合は常に一定であった。 そこで反復の各段階において変換Wを変更可能となるよう反復関数集合を定義する。

定義3.1 (反復関数集合)

反復関数集合は、m =1, 2,...,Mについてそれぞれ縮小係数smをもつ縮小写像 omega_{n}:X -> Xからなる有限集合を W={omega_{m}, m = 1,2,...,M}と したとき、N個のWからなる有限集合 {W_{n}, n = 1,2,...,N}を意味する。

反復の各段階で反復関数集合から変換を選択して適用することで パラメータを変化させることが可能となる。

定義3.2 (確率付き反復関数集合)

確率付き反復関数集合は、反復関数集合 {W_{n}, n =
1,2,...,N}と、n = 1, 2,..., Nにおいて

p1+p2+p3+,...,+pn = 1, pn >= 0

を満たすN個の有限集合 {p_{n}, n = 1, 2,...,
N}とから成る。 確率付き反復関数集合を {W_{n};p_{n},
n = 1, 2,..., N}と表記する。

pnは、 ある反復過程で反復関数集合のn番目の要素が変換として選択される確率を示す。

3.2. 画像生成の例

Fig.2のa, bに示したKochの雪片曲線とPolya曲線の2つの変換からなる反復関数集合 {W_{1},W_{2}}={{omega_{11},omega_{12}, {omega_{21},omega_{22}}を例 に、 反復関数集合による画像生成方法について説明する。

まず各反復過程での変換W1,W2の適用順序を定める。 ここでは反復回数nが奇数のときW1、 偶数のときW2を適用するとすると、 変換を4回反復した後の集合K4

K_4 = W_2(W_1(W_2(W_1(K_0))))

となる。 反復過程において形状が変化していく様子をFig.3に示す。 変換の適用順序が異なると必ず形状が異なる画像を生成できるため、 少ないパラメータから多彩なフラクタル画像を得ることが可能である。

Generating images by IFS with a function set
Fig.3. Example of generating images by IFS with a function set

3.3. 反復関数集合によるフラクタル形状制御

反復関数集合を利用することでフラクタル形状の制御を行なうことが可能となる。 一般にフラクタル画像を生成する際に未知のパラメータから算出される不動点をあらかじめ予測するのは非常に困難であり、 実際に計算機を使用して画像生成した後に形状を確認しているのが現状である。 そこであらかじめ不動点のわかっている既知のパラメータのみを用いて反復関数集合を作成し、 それを利用して画像生成を行なうことで、最終的な形状をある程度制御できる。

またコラージュ定理 [8] によれば、パラメータの値に小さな変更を与えたときには不動点 すなわち形状も小さな変更を受けることがいえる。 従って パラメータに小さな変更を加えて新しいパラメータを作成し、 それらを要素とする反復関数集合を使用して画像生成を行なうことにより、 元の形状を基本的に崩さずに細かな変更を与えることができる。 Fig.4では基本となる変換W1のパラメータの値を少しずつ変更して W2からW5を作成し、 それらからなる反復関数集合を使用して画像生成を行なうことで最終形状にわずかな変更を与えてみた。 b.からe.のどの画像も基本的な形状は元のa.と大差ないが、細部はいずれも異なっている。

Control fracatl image
Fig.4. Controling fractal images by IFS with a function set

確率付き反復関数集合を利用することで選択される変換に重み付けを行ない、 さらに細かい制御を行なうことも可能である。

3.4. 3Dモデリング

距離空間を(R3, d)とし、 R2上の写像式(1)をR3上の写像式(2)にすることで、 2次元の場合と同じアルゴリズムで反復関数集合による3次元フラクタルモデルを生成することが可能である。

3D Affine Transform … (2)

例として3Dシェルピンスキーガスケットと3D Levyからなる反復関数集合を使用してモデルを生成し、 適当なレンダリングを施して表示させた例をFig.5に示す。 初期集合K0R3上の5点 (0,0,0), (1,0,0), (1/2,0,\sqrt(3)/6), (1/2,0,-\sqrt(3)/6), (1/2,\sqrt(3)/6),0) を頂点とする四角錐とした。

3D
fractal model
Fig.5. Example of 3D Fractal Model generated by IFS with a function set

4. 応用

4.1. パターン画像の作成

反復関数集合によるフラクタル画像の一つのアプリケーションとしてパターン画像作成ツールを開発した。 パターン画像とはFig.6に示すように 'タイル' と呼ばれる基本画像を平面上に幾何的に複数配置することで得られる繰り返しを持つ画像のことを指す。

Tiling image
Fig.6. Generating a pattern by a tile image

まず基本となる画像を反復関数集合を用いるフラクタルアルゴリズムで自動生成し、 生成された画像をそのまま、 あるいは全体を左右/上下対称となるようにアフィン変換を施したものとの重ね合わせを行うことで'タイル'を作成した。

Fig.2で示された6種類の反復関数系を要素として持つ反復関数集合から作成可能なタイルの例を Fig.7に示す。 各タイルを作成するためのパラメータをAPPENDIX A.4.に示す。

Tiles
Fig.7. Examples of tiles generated by IFS with a function set

このような操作で得られたタイルをツールを用いてビットマップ上に幾何的に繰り返し配置し、 最終的に葉書作成アプリケーションで使用する背景用テンプレート用画像(文様または地紋)とした。 反復関数集合により作成された文様、地紋の例を Fig.8 a, bに示す。

background of a card A background of a card B
Fig.8 a. b. Examples of patterns by fractal images

結論

反復関数集合によるフラクタル画像生成は従来の方法と比較して以下の点で有効である。

バリエーションの飛躍的な増加

異なる変換を異なる順序で適用することにより生成可能な形状を飛躍的に増加させることが可能である。 反復関数集合の要素数m、反復回数nのときに得られる画像のバリエーションの総数は mn種類であり、 例えばFig.2に示した6種類のパラ メータを利用して 反復回数10回の画像を生成する場合に生成し得るバリエーションの総数は 6^10 = 60,466,176種類となる。

形状制御

既知のパラメータを組み合わせて使用する、 あるいは一つのパラメータの値から新しいパラメータを作成し、 それらを組み合わせることで形状を制御することができる。 パラメータの値をランダムに変更する方法と比較して'最終形状に連結性を保持したい' 等の細かな形状制御をする必要がある場合に特に有効である。 さらに適用する変換の選択される確率を設定することにより、より細かな制御を行なうことも可能である。

データサイズの圧縮

多数のフラクタル画像をデータ化する際に、反復関数集合の要素を複数の形状間で共用することにより データサイズを少なく抑えることが可能である。 反復関数集合の要素数をm、反復回数をnとすると、 色などの付加データを除く形状のみのデータは変換の適用順序だけで済むため、 データサイズの理論値は1つの形状につき n * log_2 m ビットとなる。

今後の展開

今後の展開として3Dモデリングへの応用を進めていく予定である。本文中で述べたフラクタルモデリングに加えて景観シミュレーションやテクスチャ画像生成 などへの応用、また植物形状を表現するために広く用いられているL-systemにおける反復段階でのパラメータ変更方法の検討も行なっていく。

参考文献

  1. Mandelbrot,B.B.: Fractal Geometry of Nature, W.H.Freeman and Co., New York, 1982
  2. Mandelbrot,B.B. and Ness, J.W.van: Fractional Brownian Motion, fractional noises and applications, SIAM Review 10,4 1968, p.422-437
  3. M.Barnsley and S. Demko: Iterated Function Systems and the Global Construction of Fractals, Proceedings of the Royal Society of London, A399 1985, p.243-275
  4. Day, N. and Murayama, N.: Fractal Image Generation, IP-94-33, IEEJ Chaos Workshop, 1994
  5. Przemyslaw Prusinkiewicz: Graphical Applications of L-system, Graphics Interface, 1986, p.247-253
  6. Hata, M.: On the structure of self-similar sets, Japan Journal of Applied Mathematics 2,2 1985, p.381-414
  7. Hutchinson,J.: Fractals and self-similarity, Indiana University Journal of Mathematics 30 1981, p.713-747
  8. M.Barnsley: Fractals Everywhere, Academic Press, Inc. 1988, p.96-97

APPENDIX


<- Indexにもどる


Takahiro Asai
Copyright (c) 1998 Ricoh Co.,ltd. All rights reserved.