情報科学と人工知能のノート

初等的な知識から最新論文の解説まで色々集めていきます．備忘録兼用．

ボロノイ図

ボロノイ図 自動生成

距離空間とその中の複数個の点（母点、seed などと呼ばれます）が与えられたときに、空間上の各点が与えられたどの点に最も近いかを分類した図をボロノイ図といいます．
与えられた距離空間を (X, d)、与えられた点を x_1, \cdots, x_k \in X とおいて数式で書くと 点 x_i に対応する領域は \{ x \in X \ | \ d(x, x_i) \leq d(x, x_j) \ \mbox{for all j \neq i}\} となります．与える点を X の部分空間に拡張することもできます．当然、距離関数にはユークリッド距離以外を使うこともできます．

応用

ボロノイ図は機械学習や物理学や化学や古くは疫学など非常に多くの分野で使用されているらしいのですが、いきなり単体で出てくると正直「で？」となるのではないでしょうか．僕自身そう思い、かといって応用として自分の研究に出てくることもなく、ずっと敬遠していたのですが、画像やテクスチャの自動生成に応用できるということで非常に興味が湧きました．

次の図は A Survey of Procedural Techniques for City Generation（Kelly et al., 2006, Institute of Technology Blanchardstown Journal）の図 15 からの引用です．
f:id:ti2236:20130106172332p:plain
一番左は石畳かなにかで、二番目はおそらく樹木の表皮です．三番目はなんだか分かりませんが生化学的ななにかでしょうか．いずれの画像もボロノイ図を加工して自動生成された画像です．

また、次の図は A Method for Creating Mosaic Images Using Voronoi Diagrams （Dobashi, et al., EUROGRAPHICS 2002）の図 7 の a からの引用です．
f:id:ti2236:20130106172344p:plain
こちらは与えられた画像に対して点をばらまき、その点に対するボロノイ図を加工することによって生成された、ステンドグラスのようなモザイク画像です．

どちらもいずれ独立した記事で解説しようと思います．

リアリティを考慮した都市地区自動配置アルゴリズム

自動生成 ゲーム 地図自動生成

この記事では Procedural City Layout Generation Based on Urban Land Use Models (Groenewegen, et al., EUROGRAPHICS 2009) という論文の都市地区自動配置アルゴリズムを紹介します．
最近、ゲームに関する自動化技術を勉強したり考えたりしているのですが、この論文はそういった話に関連するアルゴリズムを提案したものです．ちなみに EUROGRAPHICS はコンピュータグラフィックスの学会で、この学会も上記の論文もデジタルゲームだけのためのものではありませんが、せっかく勉強したので紹介しようと思います．

論文概要

読んで字の如しですが、この論文は仮想の都市を自動生成するための都市地区の配置を行うアルゴリズムです．
建物を並べて仮想の都市を創る技術はこの論文以前にもあったのですが、大量のデータが必要だったり、あるいは都市計画に関する専門家が操作しないとなんだか意味不明な町並みになったり（病院の横に工場があったりとかでしょうかね）、色々な問題があったそうです．そこでこのアルゴリズムは、「この辺りは住宅地区、この辺りは工業地区、…」という自然な地区の配置を少ないデータと計算量で求めるべく提案されたもののようです．ちなみにこのアルゴリズムはお城や大きな教会やあるいは高層ビルなどといったランドマークを中心に形成されている街並みを創ることを前提としているようです．

このアルゴリズムでは以下の図の手順で都市地区を配置します（上記論文の図 2 からの引用．quoted from Figure 2 in Groenewegen et al.'s paper）．
f:id:ti2236:20130106150856p:plain

  1. まず地形を入力し
  2. 中心地区と街全体の大体の半径を入力し
  3. 主要道路の本数を決め（等間隔の自動仮配置．手動入力も可能？）
  4. 地区候補点をばらまき
  5. 候補点から各地区の中心地の位置を決定し（詳細は後述）
  6. ボロノイ図によって地区の範囲を仮決めし
  7. ボロノイ図の境界線にノイズを加えて地区を決定し
  8. 既存のアルゴリズムで道路を配置して完成です．

各地区の中心地位置の決定については論文中に厳密な記述がなされていないのですが、評価関数の最適化によって一つ一つ順に決定していきます*1．評価関数は、既に配置されている他の地区との関係、地形、河川などに関する５種類の評価値の重み付き和で構成されます．全ての評価値の式やパラメータの値は公開されていませんが、例えば配置済みの他のn 個の地区との関係は\sum_{i=1}^n A_{d_i} * 1 / (\Delta_{d_i} - \Delta_{\min}) という式によって決定されるらしいです．A_{d_i} は地区 d_i と現在着目している地区との誘因度（-100〜+100）で \Delta_{d_i} は地区中心候補点の距離、\Delta_{\min} は中心点最小距離（これを下回る距離の位置に中心点を配置してはいけない）です．

これを元に西ヨーロッパの都市風のパラメータ設定を行ってアルゴリズムを走らせると以下の図のような配置が生成されるそうです（上記論文の図 3 の 1 からの引用．quoted from Figure 3-1 in Groenewegen et al.'s paper）．
f:id:ti2236:20130106154710p:plain
3 種類の青系が住宅地で色が薄い方が高級、海沿いの灰色が重工業で一番薄い色が軽工業、2 種の緑が商業地区（区別不明）、黄色が運送業、赤計二種が政治・教会関連（区別不明）です．地形は左上が海で、右下に行くほど山になっているようです．
特徴を解説すると、まず住宅地は高級になるほど山側に配置されていて（どこの国でも山の手はお金持ちの地域です）、低級住宅地と高級住宅地の分化がきちんとできています．また、重工業地区は海沿いに配置され、それを取り囲むように軽工業地区および低級住宅地が配置されています．商業地区の大部分は高級住宅地の脇に固まっていて、残りは住宅地の隙間にちらほらとあるだけです．おそらく高級住宅地横の商業地区は服飾や宝石、高級食品を取り扱っていて、それ以外は主に食品店や日用品点などを扱う中流〜貧困層のためのお店なんでしょうね．
ただアトランダムに配置されただけではない、人間の生活感を感じさせる自然な配置がうまく生成されています．まぁ、そうなるようにパラメータが設定されているわけですが、パラメータさえ設定すればこれが簡単に創れるというのは面白いことだと思います．

論文は全４ページで、何も考えずに実装さえすれば使えるレベルの詳細な記述が無いためディテールを埋めないければならないのですが、こういうアルゴリズムはそれっぽく作れば詳細が元論文と一致していなくても大体なんとかなるようになっています．

*1:配置のもっともらしさはその順序にも影響されると思うのですが、処理量はかさむものの同時配置の最適化じゃなくてよいのでしょうか？

おねえさんの栞

雑記 数え上げ問題

いっときほどほどに流行ったおねえさんの動画の栞をいただきました．知り合いが関係者です．
f:id:ti2236:20121217212350p:plain
ぽぽぽぽーんとか選挙とかと同種の流行り方だったと思うのですが*1、大ブームに至らなかったのは、キャラクターの固有名称も不思議な歌も無かったからかなと推測している今日この頃．あといじって遊ぶにはたぶん長い．

*1:すなわちニコニコ動画周辺の流行．