1,a) 1 1 1,b) 2 1 A Pattern Creation Support System for Escher-Like Tiling Megumi Kisanuki 1,a) Hirohumi Machii 1 Kiyomasa Sakimoto 1 Satoshi Ono 1,b) Kazunori Mizuno 2 Shigeru Nakayama 1 Abstract: This paper proposed a system for Escher-like tiling design, which allows a user drawing a desirable pattern shape image. Due to the hard constraints of the tiling design, it is difficult to produce a pattern shape which is sufficiently similar to the given one and satisfies the tiling constraints. A previous work produces Escher-like tiling pattern automatically, but it has been not sufficient to help the creativity of users because it produces only one output from one input shape. The proposed system therefore iterates drawing the desirable pattern shape with the user and searching for feasible pattern shapes by interactive iterative Genetic Algorithms. Keywords: Genetic Algorithm Interactive Evolutionary Computing Tiling Design Support 1. 1 1 21-40 2 815-1 a) k0790524@kadai.jp b) ono@ibe.kagoshima-u.ac.jp [1] c 2013 Information Processing Society of Japan 1
[3] 2. 2.1 M.C. Escher Escher 1 Escher Escherization Problem [5] Escherization Problem S ( 1 ) T S ( 2 ) T T [5] Escherization Problem isohedral isohedral isohedral 93 IH01, IH02,..., IH93 2.2 Genetic Algorithm : GA [6] GA [7] GA 2.3 GA Evolutionary Computing : EC Interactive Evolutionary Computing : IEC [9] IEC IEC Interactive Genetic Algorithm : IGA GA [11] 1 IGA IGA GA GA c 2013 Information Processing Society of Japan 2
2.4 1 IGA Kaplan Simulated Annealing : SA Escherization Problem [2] T isohedral 93 Escherization Problem [12] Escherization Problem [13] 3. 3.1 1: GA 2: GA GA 3.2 GA 2 GA Genotype Phenotype Genotype 2 IH07 IH07 120 Genotype 1 3 3 3 AB,CD,EF 3 BC,DE,FA 3 3 Phenotype 3.3 3 GA ( 1 ) c 2013 Information Processing Society of Japan 3
2 Genetype Phenotype 3 ( 3 ) Turning Function GA ( 4 ) [8] 2 Genotype v 0, v 1 Genotype ( 5 ) GA GA 4 [10] 4 ( 2 ) [13] 3.4 Turning Function 2 Turning Function[14] 5 2 Θ(l) l 0 l 1 2 D = 1 0 {Θ A (l) Θ B (l)}dl D 2 3.5 6 c 2013 Information Processing Society of Japan 4
情報処理学会研究報告 図 7 図 5 最良解の適応度の推移 Turning Function を用いた多角形の類似度計算の例 図 10 提案する方式で生成された図形のタイリング例 1 図 11 提案する方式で生成された図形のタイリング例 2 図 6 提案する方式の画面構成 ト内で任意の色を選択し描画することができる IEC の処理では メニューバーのタイリングメニューか ら行列計算や GA を開始し 処理が始まる際にそれぞれ の解を提示するフレームがウィンドウ内に表示される ま た 解が表示されたウィンドウをクリックすることで GA の処理の最中に表示された解をキャンバスに反映し ユー ることがわかる ザが図形を直接編集することができる 4. 実行例 4.1 GA を用いた実行例 個体数を 100 世代数の上限を 10,000 世代とし 初期個 4.2 IGA を用いた実行例 提案する方式の実行過程を図 9 に それにより生成され た例を図 10 11 に示す 図 9 では犬の顔を表した図形を入力図形としていたが 体は行列計算に基づく生成と 生成された解に入力図形の IGA の処理の過程でユーザの意図する図形が変化し 最終 一部の形状を取り入れた個体を複数生成した 交叉法には 的に初期の目標図形とは全く異なる形状の出力図形が生成 二点交叉を用い エリート個体数を 2 突然変異率を 0.5 された とした 図 10 11 の (a) はユーザが描画した入力図形を表し (b) 図 7 に最良解の適応度の推移を表したグラフを示す こ は GA とユーザの対話によって得られたタイリング可能な れは試行回数 5 回の平均値をとったものである 上記の図 出力図形である (c) にこの図形によるタイリング結果を から 世代数が大きくなるにつれて適応度が高くなってい もとにユーザが着色等を行った例を示す ることがわかる GA のみを用いて生成された例を図 8 に 図 10 11 より 提案する方式を用いて同じ入力図形か 示す (a) は入力図形 (b) は行列計算をもとに生成した図 ら異なる出力図形を得ることができ また その図形はタ 形 (c) は GA を用いて生成した図形 (d) は自動生成され イリングが可能であることがわかる 以上のことから 提 たタイリング画像を示す 図 7 8 より 右側上部や左側 案する方式は ユーザの発想を支援し 様々なタイリング の凹凸の形状等 GA を用いて生成された図形は行列計算 画像の作成が可能であると考える をもとに生成した図形より入力図形に近い形状になってい c 2013 Information Processing Society of Japan 5
8 GA 9 5. IGA IGA GA IGA 2 [1] Branko Grunbaum, G. C. Shephard: Tilings and Patterns. W. H. Freeman, New York (1987). [2] Craig S. Kaplan: Computer Graphics and Geometric Ornamental Design, PhD thesis, University of Washington (2002). [3], Vol. 13, No. 5, pp. 692-703 (1998). [4] J.L. M.C. : (1995). [5] Craig S. Kaplan and David H. Salesin: Escherization. Proceedings of SIGGRAPH, New Orleans, pp. 499-510 (2000). [6] Goldberg, D.E. : Genetic Algorithms in Search, Optimization Machine Learning, Addison - Wesley, pp. 1-25 (1989). [7] (2008). [8],,, Vol. 12, No. 5, pp. 734 744 (1997). [9] Hideyuki Takagi: Interactive evolutionary compu- tation - fusion of the capabilities of ec optimization and human evaluation. In Proceedings of the IEEE, Vol.89, pp. 1275-1296 (2001). [10] Gary Bradski, Adrian Kaehler: Learning OpenCV: Computer Vision with the OpenCV Library, O Reilly Media, 1st edition, September (2008). [11] MPS pp 113-116 (2008). [12] (2010). [13], NICOGRAPH (2009). [14] Esther M. Arkin, L. Paul Chew, Daniel P. Huttenlocher, Klara Kedem, Joseph S. B. Mitchell: An Efficiently Computable Metric for Comparing Polygonal Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.13, No.3, pp.209-216 (1991). c 2013 Information Processing Society of Japan 6