2014-07-23

"Game & Design" セッション論文紹介 (SIGGRAPH '14)

2014年7月29日に私の所属する五十嵐研究室が主催の SIGGRAPH 勉強会があります。
SIGGRAPH 2014 Preview Seminar
この勉強会では各々が担当するセッションを事前に決めておき、当日１０分程度で担当セッションの論文内容を発表し合います。１日で全ての論文を網羅するので中々ハードな勉強会です。（外部の方でももちろん参加歓迎です。興味のある方は連絡下さい。）

私は Game & Design のセッションを担当します。この記事では Game & Design セッションの論文の内容をまとめていこうと思います（発表資料を作る前段階のメモ、程度の位置づけですが）。勉強会当日まで随時更新していきます。

セッションについて

以下の５本の論文が含まれています（名称は自分が勝手につけた略称です）。

Poisson-based Caustics Design (Yue et al.) (TOG)
High-contrast Caustics Design (Schwartzburg et al.)
Boxelization (Zhou et al.)
Connect-the-Dots (Löffler et al.)
Self-refining Game (Stanton et al.)

Games & Design | SIGGRAPH 2014

1. - 3. の３本は fabrication oriented design に関する論文です。近年流行ってる分野で、これら３本とは別に Fabrication Oriented Design というセッションがあったります。

これらのうち特に 1., 2. の２本は computational caustics design に関する論文で、同様の問題を扱っています。ただし 1. は TOG で Jun 2014 に先に公開されていたため、2. の中では 1. の内容を踏まえた議論（結果の比較など）が行われています。

1. Poisson-Based Caustics Design (TOG)

Yonghao Yue, Kei Iwasaki, Bing-Yu Chen, Yoshinori Dobashi, Tomoyuki Nishita
Poisson-based Continuous Surface Generation for Goal-based Caustics
ACM Transactions on Graphics (TOG) (2014)
http://nishitalab.org/user/egaku/tog14/absttog14.html

日本人による論文です。

概要の意訳

本論文はユーザが指定した集光現象 (caustics) のパターンを実現するような滑らかな表面形状を生成するための、Poisson ベースの手法を提案する。ファブリケートされた透明物体によって、滑らかで、自然で、非常に精細な caustics を得ることができる。

できるだけ短くまとめると

Goal-Based Caustics (または Computational Caustics Design) とは、ある目的の絵を入力として、集光現象を利用してその絵を描けるような透明物体の形状を出力とするような問題です。

このような問題に対して、今回の論文ではポアソン方程式を解くような定式化をする手法を提案しています。この手法は既存研究よりも高精度で滑らかな結果が得られるものとなっています。

Computational Caustic Design における一般的な問題設定

光源は並行光。
透明物体の光源側の表面は光軸に対して垂直な平面。
透明物体のスクリーン側の表面は滑らかな形状（これが出力）。
集光現象によってスクリーンに見える絵はユーザが指定できる（これが入力）。

具体的な評価基準（どんな性質を持つ形状が望ましいか？）

この論文では望ましい性質として以下の5つの評価基準を挙げています。

単純な絵だけでなく、一般的な複雑な絵を扱うことができる
高解像度である
連続的な輝度の分布を扱うことができる（特に輝度が低い領域でも高品質を保てる）
フォーカスの幅が広い
フォーカスが多少ずれても集光現象による絵が連続的である

既存研究はいくつか存在するものの [Finckh et al., 2010; Papas et al., 2011; Yue et al., 2012] 、これらの基準を同時に満たす手法は今回の提案手法が初めてであると論文内で主張されています。

手法

入力画像の caustics を生成できるように、ポアソン方程式を解きながら透明物体の表面とスクリーンの表面との全単射写像を決定し、続いてその制約を満たすように、（別の）ポアソン方程式を解きながら理想的な三次元形状を決定するそうです。（よく読めていないので語弊があるかもしれません）ポアソン方程式の形に定式化した点がポイントだそうです。

2. High-Contrast Caustic Design

Yuliy Schwartzburg, Romain Testuz, Andrea Tagliasacchi, Mark Pauly
High-contrast Computational Caustic Design
SIGGRAPH '14
Yuliy Schwartzburg

概要の意訳

スクリーンに投影される集光現象 (caustics) の様子が目的の絵になるような表面形状を求める caustic design のアルゴリズムを提案する。本手法は piecewise smooth surfaces と non-bijective mappings をサポートし、これによって、集光による絵の滑らかな遷移、infinite light density による特異点、完全に暗い領域などが可能となる。

できるだけ短くまとめると

上記の [Yue et al., 2014] と同様、Goal-Based Caustics (または Computational Caustics Design) に関する論文で、基本的には同じ問題を解いています。

ただし既存手法や [Yue et al., 2014] と比較しても、高いコントラスト（明るいところは明るく、暗いところは暗く）が実現できている点や、点や曲線などの形状の光が局所的に集中する部分（論文では singularity と呼んでいます）が実現できる点などの利点を持っています。

特徴

生成された表面形状は連続で、piecewise smooth である点が特徴だそうです。よく読んでいないので正確にはどういう意味か分かっていませんが、おそらく基本的には滑らかだけど大局的には滑らかではない（滑らかでない部分が存在できる）ような状態のことを指しているのだと思います。

また透明物体の表面の点とスクリーン上の点が、既存手法では二次元の全単射の写像になっていたのに対し、この手法では全単射でないような写像も許すような定式化となっています。これによって、完全に暗い領域を作れたりするなど、非常にコントラストの高い結果が望めます。また光が局所的に集中する点や曲線（singularity）が表現できるそうです。

手法の流れ

前半で、理想的な写像を決定 (optimal transport) します。この写像を実現できるように、後半で、理想的な三次元形状を決定 (target optimization) します。

[Yue et al., 2014] との比較

論文内で、Poisson-based continuous (PBC) method [Yue et al., 2014] との比較が行われています。同じ画像を入力とし、同じ入力光を仮定したときに、より高いコントラストが実現できることをシミュレーション結果の図を比較して説明しています。

手法としては、[Yue et al., 2014] がポアソン方程式を解くことで大域的に smooth な表面形状を生成する（制約が大きい）のに対し、提案手法は表面形状の normal field に不連続な分布を許しているため、表現能力が増しているというようなことが主張されています。

3. Boxelization

Yahan Zhou, Shinjiro Sueda, Wojciech Matusik, Ariel Shamir
Boxelization: Folding 3D Objects Into Boxes
SIGGRAPH '14

概要の意訳

立方体（箱型）に折り畳むことができるような三次元オブジェクトをデザインするための手法を提案する。更にその手法は折り畳む際の手順において交差が起きない (intersection-free) ことを保証する。この論文ではいくつかの入力三次元オブジェクトに対する結果を報告し、さらに三次元プリンタを用いたファブリケーションの結果も報告する。

できるだけ短くまとめると

三次元モデルを入力として、それを箱型に折り畳めるようにする (= boxelization) という研究です。

技術的なチャレンジとしては

特殊な voxelization (普通の voxelization では綺麗な箱型にならない)
箱型に折り畳めるような構造の探索 (ビームサーチのような探索手法？)
得られた解が実際に交差が起きずに (intersection-free) 折り畳んだり開いたりできるかの確認

の３つが挙げられています。

得られた結果は実際に三次元プリンタで出力してパズルとして遊ぶことができます。

4. The Connect-the-Dots Family of Puzzles: Design and Automatic Generation

Maarten Löffler, Mira Kaiser, Tim van Kapel, Gerwin Klappe, Marc van Kreveld, Frank Staals
The Connect-the-Dots Family of Puzzles: Design and Automatic Generation
SIGGRAPH '14

概要の意訳

伝統的な "Connect-the-Dots パズル" の革新的な派生を紹介する。これらの派生は幾何学的なルールに基づいている。我々は何が「良い」パズルを作るために必要かを解析し、数学的にモデル化した。更に、本論文では与えられた輪郭絵に対して自動的にパズルを生成する手法を提案する。

論文の全体像

この論文は大きく２つのパートに分かれます。

前半: パズルのルールの拡張

まずは Connect-the-Dots パズルのルールを拡張する方法について議論します。従来は点にふってある番号の順に線を繋いでいくのですが、番号をふる代わりに、

示された方向の点と結ぶ
最も近い点と結ぶ
一定の距離にある点と結ぶ

という３つの新しいルールを導入すること、従来よりも面白くて難しい（論文内では interesting and challenging と表現されています）Connect-the-Dots のパズルを考えることができます。

後半: パズの自動生成

後半では、このようにして定義された新しい Connect-the-Dots パズルをアルゴリズムによって自動生成するという話になります。この論文では

入力の線画にできるだけ近い
点の数が多すぎない
曖昧な部分が少ない

という基準を考慮しながらパズルを生成するアルゴリズムを考案しています。

5. Self-Refining Games

Matt Stanton, Ben Humberston, Brandon Kase, James O'Brien, Kayvon Fatahalian, Adrien Treuille
Self-Refining Games Using Player Analytics
SIGGRAPH '14
Self-Refining Games using Player Analytics

概要の意訳

データドリブンのアニメーションやレンダリングでは、数多く存在する「状態」の中から適切な状態を学習データとして選択することが重要である。ゲームのプレイ統計から学習することで、多くのプレイヤーが実際に直面することになる（起こりやすい）状態を推定することが可能である。学習データをこれらの（起こりやすい）状態の周辺に集中させることで、誤差や見た目上のアーティファクトを軽減することができる。

できるだけ短くまとめると

クラウドソーシングによって得られた統計データを活用することで、データドリブンシミュレーションの事前計算の質をより良くするという研究です。

またゲームという応用に関していうと、クラウド＝ゲームプレイヤとなるので、ゲームをプレイすればするほどシミュレーションの精度が上がるという意味で "Self-Refining Games" という概念が提案されています。

事前計算によるデータドリブンシミュレーション [Kim et al., SIGGRPAH '13]

データドリブンなシミュレーションにも色々ありますが、以下の手法 [Kim et al., SIGGRPAH '13] がこの論文で使われている手法の基礎となっています。（ちなみに著者は３人ほど被っています。）

Doyub Kim, Woojong Koh, Rahul Narain, Kayvon Fatahalian, Adrien Treuille, and James F. O'Brien
Near-exhaustive precomputation of secondary cloth effects
SIGGRPAH '13

この Kim らによる論文では、「衣服の揺れを（ほぼ）全て事前計算しておき、実行時には事前計算結果を適切に切り貼りしながら再生する」ということが行われています。

データドリブンシミュレーション [Kim et al., 2013] では何が難しいか

事前計算では、頂点を物理的な状態（相空間における点？）、辺を状態遷移（短いアニメーション）とするような巨大なグラフ (state graph) を構築するということが行われます。このグラフが大きければ大きいほどより精度の高いアニメーションを再現することができるということになります。

しかしながら、実際には物理的な状態は無限に存在するため、完全に全てを計算することはできません。したがって、どの状態を事前計算して、どの状態を事前計算しないかの取捨選択がここでのキーポイントとなります。

[Kim et al., 2013] ではキャラクタのモーションとして motion graph の手法を想定していたため、その特徴をうまく用いて賢く事前計算していたようでした。

クラウドソーシングを活用した賢い事前計算

そもそもクラウドソーシングとは

クラウドソーシング (crowdsourcing) とは、アウトソーシング (outsourcing) を改変した造語で、インターネット越しに待機している不特定多数の群衆 (crowd) にタスクをアウトソーシングするというアイデアを指す言葉です。
クラウドソーシングとは？ヒューマンコンピュテーションとは？ - yuki-koyama's blog

ゲームのプレイ統計をクラウドソーシングで集める

今回の論文のターゲットは「ゲームにおける流体シミュレーション」です。ゲームのようなユーザの目的がはっきりした環境では、流体がとり得る物理的な状態の空間は実はかなり偏っている、という特徴に着目し、クラウドソーシングによって集めたゲームのプレイ統計から賢く何を事前計算して何を事前計算しないのかを取捨選択しています。

2014-05-18

SIGGRAPH '14 におけるクラウドソーシング論文

論文 SIGGRAPH 2014 CG 機械学習

はじめに

クラウドソーシングに関する論文は CHI や UIST などの HCI (Human Computer Interaction) の国際会議や、AAAI などの機械学習の国際会議を中心に、この数年間で急激に増えています。

近年ではコンピュータグラフィクスの国際会議である SIGGRAPH でもクラウドソーシングという言葉を多く見かけるようになってきました。

この記事では SIGGRAPH 2014 におけるクラウドソーシングに関連した論文をまとめようと思います。

手作業で探しているため、見過ごしや、誤った解釈もあるかもしれません。随時修正します。

そもそもクラウドソーシングとは

クラウドソーシング (crowdsourcing) とは、アウトソーシング (outsourcing) を改変した造語で、インターネット越しに待機している不特定多数の群衆 (crowd) にタスクをアウトソーシングするというアイデアを指す言葉です。

SIGGRAPH や AAAI ではヒューマンコンピュテーション (Human Computation) の手段としてクラウドソーシングが用いられることが多い気がします。

詳しくは以下の記事を読んで下さい。
クラウドソーシングとは？ヒューマンコンピュテーションとは？ - yuki-koyama's blog

クラウドソーシングに関する論文

A Similarity Measure for Illustration Style

Elena Garces, Aseem Agarwala, Diego Gutierrez, Aaron Hertzmann
A Similarity Measure for Illustration Style
SIGGRAPH '14
http://webdiis.unizar.es/~elenag/projects/SIG2014_styleSim/

イラストの類似度を測るための特徴量をモデル化した、という論文です。特徴量の重み付けを学習するためにクラウドソーシングを用いているようです。

Self-Refining Games using Player Analytics

Matt Stanton, Ben Humberston, Brandon Kase, James O'Brien, Kayvon Fatahalian, Adrien Treuille
Self-Refining Games using Player Analytics
SIGGRAPH '14
http://graphics.cs.cmu.edu/projects/self-refining-games/

データドリブンの液体のシミュレーションに関する論文です。ゲームのシーンにおいて登場する液体の状態をクラウドソーシングによって集めておき、事前計算しておくことで、次にゲームをする人はよりリアリスティックな液体シミュレーションを用いてゲームをプレイすることができるようです。

Exploratory Font Selection Using Crowdsourced Attributes

Peter O'Donovan, Janis Libeks, Aseem Agarwala, Aaron Hertzmann
Exploratory Font Selection Using Crowdsourced Attributes
SIGGRAPH '14
http://www.dgp.toronto.edu/~donovan/font/

フォント選びを改善するという論文です。フォントのセマンティックな性質（happy とか strong とか formal とか）を測る特徴量をクラウドソーシングによって学習しておくことで、もうちょっと happy なフォントが欲しい、といったフォントの選び方ができるようになります。

Intrinsic Images in the Wild

Sean Bell, Kavita Bala, Noah Snavely
Sean Bell, Kavita Bala, Noah Snavely
SIGGRAPH '14
http://intrinsic.cs.cornell.edu/

Intrinsic Image とは、簡単に言うと、照明環境に依存しない「本来の色」を表す画像のことのようです（違ったらすみません）。例えば、明るい場所の黒と暗い場所の白なら、人間の目には黒の方が「本来の色」としては暗いと認識できるわけですが、照明環境によってはその輝度は逆転している可能性もあるため、機械にとっては黒の方が暗いと認識するのは難しいわけです。この論文では、Intrinsic Image を抽出するアルゴリズムを検証するためのベンチマークとなるデータベースを作成しています。正解データを作るために、クラウドソーシングを活用しています。

How Do People Edit Light Fields?

Adrian Jarabo, Belen Masia, Adrien Bousseau, Fabio Pellacini, Diego Gutierrez
How Do People Edit Light Fields?
SIGGRAPH '14
http://giga.cps.unizar.es/~ajarabo/pubs/lfeiSIG14/

~~論文が未だ公開されていないので定かではありませんが、スタディの中でクラウドソーシングを使っている可能性があります。~~
追記 (2014/05/24): クラウドソーシングは使っていませんでした。ライトフィールドを編集するという、かなり高度なタスクなため、簡単なタスクを大量に依頼するのが得意なクラウドソーシングとは相性が悪かったようです。

2014-05-18

論文読み: Unified Particle Physics for Real-Time Applications (SIGGRAPH '14)

論文 SIGGRAPH CG 2014

ゲーム物理エンジンに関する技術の集大成的論文

今回取り上げるのは今年の SIGGRAPH で発表される予定の論文です。正式な publication date は７月ですが、既に著者らがウェブ上で論文と動画を公開しています。

Miles Macklin, Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim.
Unified Particle Physics for Real-Time Applications.
SIGGRAPH '14 (to appear)
http://blog.mmacklin.com/flex/

この論文はこれまで個別に提案されてきたゲーム物理の技術を統合的に扱うという手法を提案しており、まさに集大成的な論文と言えると思います。公開されている動画も非常に印象的なものとなっています。

論文概要

短いので論文概要 (Abstract) を全て日本語訳してみようと思います。やや意訳している箇所があります。

我々は、リアルタイムな視覚的効果を演出するための統合的なダイナミクスの枠組みを提案する。基本要素として、制約によって接続されたパーティクルを用いることで、接触や衝突を統一的に扱うことを可能にした。ガス、液体、柔軟物体、剛体、布を、それらの相互作用も含めてモデル化するにあたって、この表現形式が十分な柔軟性を持つことを示す。我々は、パーティクルに基づく従来手法に共通するいくつかの問題に取り組み、またリアルタイムなアプリケーションでも十分高速に動作する、Position Based Dynamics に基づく並列制約ソルバーについても述べる。

この手法のメリット・強み

以下の点が挙げられます。

接触や衝突も上手く考慮できている
ガス、液体、柔軟物体、剛体、布を全て表現できる
異なる表現（ガスと布、液体と剛体など）の相互作用 (two-way interaction) も扱うことができる

これらの条件を全てクリアした上でちゃんと動作する手法は初めてではないでしょうか。

パーティクルに基づく手法

この手法はパーティクル（粒子）ベースの手法です。つまり、全ての物体はパーティクルの集合として表現されます。

他の可能性としては、メッシュによる表現（表面メッシュや、ボリューメトリックな四面体メッシュ、ボクセル状メッシュなど）や、空間をグリッドで分ける表現（オイラー的手法）などがあり得ます。計算コストを抑えることが求められるゲーム向けのリアルタイム物理においては、パーティクルベースの手法が多い気がします。

Position Based Dynamics に基づく手法

Position Based Dynamics とは、今回の論文の第二著者の Matthias Müller 氏を筆頭著者として 2006 年に提案された手法です。リアルタイム処理に向いた手法です。

M. Müller, B. Heidelberger, M. Hennix, J. Ratcliff
Position Based Dynamics
VRIPhys '06
著者のページ

これについては、過去に書いた以下の記事で少しだけ詳しく解説しています。

論文読み: Position Based Fluids (SIGGRAPH '13) - yuki-koyama's blog
Unity 上に自分で物理エンジンを実装したい - yuki-koyama's blog

よくある手法では、力を計算して、加速度を計算して、速度を計算して、位置を計算するという流れを取ります。流体や弾性体などの振る舞いをモデル化する際には、力に関する制約としてモデル化することになるので、Force Based と呼んだりします。

それに対し Position Based Dynamics では、物体の振る舞いを位置に関する制約としてモデル化します。これが Position Based と呼ばれる所以です。したがって、位置を計算して、位置から速度を逆算するようなアルゴリズムになっています。これによって数値安定性が得られるのも特徴の一つです。

いままでに提案されてきた個別の技術

この論文は、いままでに提案されてきた個別の技術を統合的に扱っている点が最大の特徴です。

個別の技術の例としては、以下の２つの手法が有名です。

柔軟物体 (Shape Matching 法)

柔軟物体は Shape Matching 法と呼ばれる手法を用いて表現できます。

Matthias Müller, Bruno Heidelberger, Matthias Teschner, Markus Gross.
Meshless Deformations Based on Shape Matching.
SIGGRAPH '05

Shape Matching 法に関してはその後多くの拡張手法が提案されています。

また、2011 年の CEDEC においてシリコンスタジオ株式会社が発表した技術デモとその資料がウェブで公開されています。ありがたいです。
4Gamer.net ― ［CEDEC 2011］シリコンスタジオが紹介するゲームの未来。次世代型弾性体表現技術「Shape Matching」とは
 http://www.siliconstudio.co.jp/presentations/

液体 (Position Based Fluids)

液体については昨年の SIGGRAPH で発表されました。以下のデモ動画は非常に有名になったため、見たことがある人も多いと思います。

Miles Macklin, Matthias Mueller Fischer
Position Based Fluids
SIGGRAPH '13

NVIDIA PhysX Lab

この論文は NVIDIA PhysX Lab というところから出た論文です。NVIDIA といえば有名な GPU メーカですが、そこが開発しているゲーム向け物理エンジン PhysX も有名です。ゲームエンジンとして有名な Unity でも採用されていますね。

今回の論文で発表した技術も、いずれは（既に？）PhysX に組み込まれるものだと考えられます。

細かいメモ

制約を解くのを並列に計算するために、Gauss-Seidel 法から Gauss-Jacobi 法に変更している。その際に positive definite じゃなくても収束するようにするために、constraint averaging [Bridson et al. 2002] とか mass-splitting [Tonge et al. 2012] とかいうアイデアを活用している。これによって、運動量保存則が破れてしまっている。
- 論文では言及されていないが、これは Lattice Shape Matching (LSM) [Rivers and James 2007] などでも使われていたアイデアで、実は LSM は運動量を保存していなかったということになる？
  - 追記 (2014/05/18): そもそも shape matching の制約は角運動量の保存は保証していなかったような。
Position Based Dynamics でガスを表現したのは初めて。
いままでは post processing 的に扱われていた摩擦の表現が、ちゃんと制約として解かれている。
衝突判定を高速化するために、シーン中の全てのパーティクルの半径は同じに設定されている。
剛体 (rigid bodies) もメッシュではなくパーティクルで表現されている。その制約としては Shape Matching 法が使われている。
- Position-Based Rigid Body Dynamics [Deul et al. 2014] は違うアプローチ？
Interlocking という、物体同士が突き刺さった状態になってしまう問題を、Signed Distance Field (SDF) を各パーティクルに保存しておき衝突処理で活用することで解決している。
Maya の Nucleus [Stem 2009] も実は Position Based Dynamics とよく似た計算方法をとっているが、そのことが論文中で簡単に触れられている。
- 特許とかどうなってるんだろう？Autodesk と NVIDIA で喧嘩になったりしないの？

2014-05-04

RBF 補間 (Radial Basis Function Interpolation) の概要と実装

ソースコード数学 CG 機械学習開発

はじめに

RBF 補間とは

RBF 補間とは、RBF (放射基底関数, radial basis function) を用いて入力となる散布データ (scattered data) の値を補間することです。または、与えられた散布データを元に非線形な関数をフィッティング (または近似) することだと考えることもできます。

どういうときに使えるか

下図のように、 $N$ 個の点列 $(x_1, y_1), \ldots , (x_N, y_N)$ が与えられ、それらの点を通るような滑らかな関数 $f$ を求めたいときに、RBF 補間が使えます。

f:id:yuki-koyama:20180312163612p:plain

また、より高次元 ( $n$ 次元とします) の空間における補間も可能です。この場合は $N$ 個の点列 $(\mathbf{x}_1, y_1), \ldots , (\mathbf{x}_N, y_N)$ が与えられたときに関数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ を求めることになります。

どういう特徴があるか

RBF 補間はノンパラメトリックなフィッティングの一種です。
与えられた点列を必ず通るような関数を求めることができます。
ノイズが多く密度の高いデータに対しては過学習 (over-fitting) が起きることがあります。
一度事前計算さえすれば、補間値の評価は (比較的) 高速に行うことができます。

RBF ネットワーク

この記事で紹介する内容は、機械学習などの分野では RBF ネットワークと紹介されることも多いようです。私の専門分野 (Computer Graphics) では散布データを補間する目的で使われるため RBF 補間と呼ぶことが多いようです。*1

RBF 補間の考え方

RBF とは

RBF とは、基本的には「その値が原点からの距離にのみ依存する実数値関数」のことを指し、普通 $\phi$ で表します。

$\displaystyle{ \phi(\mathbf{x}) = \left \| \mathbf{x} \right \| \\ \phi(\mathbf{x}) = \exp ( - \beta \left \| \mathbf{x} \right \| ) \:\: (\beta > 0) }$

などは代表的な RBF です。

また、「その値が RBF Center $\mathbf{c}$ からの距離のみに依存する実数値関数」も含めて RBF と呼ぶことがあります。この場合は入力 $\mathbf{x}$ に対して $\phi(\mathbf{x}, \mathbf{c}) = \phi(\left \| \mathbf{x} - \mathbf{c} \right \|)$ となります。

関数の表現

RBF 補間では、ある重み $\mathbf{w} = (w_1, \ldots , w_N)$ を用いて、関数 $f$ を

$\displaystyle{ f(\mathbf{x}) = \sum_i^N w_i \phi(\mathbf{x}, \mathbf{x}_i) }$

と表します。つまり、RBF の重み付き線形和です。あとは与えられたデータに対してこの重みを予め上手く見つけておけば良いということになります。

重みの決め方

$j$ 番目の入力データ $(\mathbf{x}_j, y_j)$ に関して、重み $\mathbf{w}$ が満たすべき条件式として次のような式を考えます。

$\displaystyle{ y_j = \sum_i^N w_i \phi(\mathbf{x}_j, \mathbf{x}_i) }$

つまり、得られる関数 $f$ が点 $(\mathbf{x}_j, y_j)$ を通るという条件です。これを $j=1, \ldots , N$ の全てについて考えると、以下のように列挙できます。

$\displaystyle{ y_1 = \sum_i^N w_i \phi_{1, i}\\ \vdots\\ y_N = \sum_i^N w_i \phi_{N, i} }$

ここで簡単のため $\phi_{j, i} = \phi(\mathbf{x}_j, \mathbf{x}_i)$ という表記を用いました。すると、これらは行列形式でまとめて

$\displaystyle{ \mathbf{y} = \Phi \mathbf{w} }$

と書くことができます。ただし $\mathbf{y}$ と $\Phi$ はそれぞれ

$\displaystyle{ \mathbf{y} = \begin{bmatrix} y_1 & \ldots & y_N \end{bmatrix}^T, }$
$\displaystyle{ \Phi = \begin{bmatrix} \phi_{1, 1} & \cdots & \phi_{1, N} \\ \vdots & \ddots & \vdots \\ \phi_{N, 1} & \cdots & \phi_{N, N} \end{bmatrix} }$

を表しているとします。ちなみに $\phi_{j, i} = \phi_{i, j}$ ですから、 $\Phi$ は対称行列になっています。さて、この条件式は $\mathbf{w}$ に関する連立一次方程式と見做すことができ、またほとんどの場合は $\Phi$ には逆行列が存在するので、

$\displaystyle{ \mathbf{w} = \Phi^{-1} \mathbf{y} }$

とすることで解を求めることができます。

C++ による RBF 補間の実装

f:id:yuki-koyama:20180510100442p:plain

C++ による実装例です。行列演算の部分は、外部ライブラリとして Eigen を用いています。

Eigen

重みの計算方法

入力 $(\mathbf{x}_1, y_1), \ldots , (\mathbf{x}_N, y_N)$ に対して重み $\mathbf{w}$ を計算する関数は例えば以下のように書けます。

#include <Eigen/Core>

using namespace Eigen;
using namespace std;

VectorXd compute_weights(const VectorXd& y, const vector<VectorXd>& x)
{
    MatrixXd Phi = MatrixXd::Zero(N, N);
    for (int i = 0; i < N; ++ i) {
        for (int j = 0; j < N; ++ j) {
            Phi(i, j) = phi(x[i], x[j]);
        }
    }
    const VectorXd w = solve_linear_system(Phi, y);
    return w;
}

ここで、RBF を表す関数 phi を以下のように定義しておきます。ここでは $\phi(\mathbf{x})=\left \| \mathbf{x} \right \|$ の定義を用いることにすると、

double phi(const VectorXd& x)
{
    return x.norm();
}

double phi(const VectorXd& x, const VectorXd& c)
{
    return phi(x - c);
}

のようになります。

また一般的な連立一次方程式 $\mathbf{A}\mathbf{x}=\mathbf{b}$ を解くための関数 solve_linear_system は、どのアルゴリズムを用いても良いですが、例えば完全ピボット選択の LU 分解 (LU decomposition with full pivoting) を用いる場合は

#include <Eigen/LU>
VectorXd solve_linear_system(const MatrixXd& A, const VectorXd& b)
{
    FullPivLU<MatrixXd> lu(A);
    const VectorXd x = lu.solve(b);
    return x;
}

のように書きます。今回 $\Phi$ は正定値エルミート行列ですので、コレスキー分解 (Cholesky decomposition) を用いても良いです。一回だけ計算すれば良いとはいえ、この部分の計算量 (時間計算量も空間計算量も) は大きく、例えば $N=10000$ などになると標準的なラップトップで計算するのが困難になることもあるので注意が必要です。

補間結果の値の評価

以上のように求めた重み $\mathbf{w}$ を用いると、任意の入力 $\mathbf{x}_{\mathrm{input}}$ に対する補間結果 $y_{\mathrm{interp}} = f(\mathbf{x}_{\mathrm{input}})$ は以下のように計算できます。

double f(const VectorXd& x_input)
{
    double y_interp = 0.0;
    for (int i = 0; i < N; ++ i) {
        y_interp += w[i] * phi(x_input, x[i]);
    }
    return y_interp;
}

ここからも分かる通り、補間値の評価の処理は RBF Center の数 $N$ に対して計算量は $O(N)$ となっています。一度重みの計算さえしておけば、補間値の評価は $N$ が多少大きくても非常に高速に計算可能です。

ソースコード

以下に C++, Eigen を用いて RBF 補間の機能を実装したライブラリを公開しました。後述する Regularization にも対応しています。

github.com

RBF 補間の応用

Computer Graphics (CG) 分野での応用例

次の 2001 年の SIGGRAPH で発表された論文では

物体表面を表す三次元点群データから滑らかな表面の構築
一部が欠損している表面メッシュデータの穴埋め

の二つの目的を、RBF 補間を応用することで達成しています。

この記事を書いている時点で被引用数が 1300 を超える有名論文で、RBF 補間について詳しく議論しています。

J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright, B. C. McCallum, and T. R. Evans.
Reconstruction and Representation of 3D Objects with Radial Basis Functions
SIGGRAPH '01
Reconstruction and representation of 3D objects with radial basis functions

また以下の4本の論文では、次のような処理が行われています。

Measurement-Based Model Fitting. 特定の条件下での実験観測データから、その条件下での物理特性を推定する
Data-Driven Simulation. 推定された特定の条件下における物理特性を RBF Center と見做し、RBF 補間することで、未知の条件下での物理特性を推定し、そのような未知の条件下でも信頼度の高いシミュレーションを行う

後者の過程で scattered data interpolation の考え方が使われており、ここでは RBF 補間が採用されています。

B. Bickel, M. Bächer, M. A. Otaduy, W. Matusik, H. Pfister, and M. Gross.
Capture and Modeling of Non-Linear Heterogeneous Soft Tissue
SIGGRAPH 2009

B. Bickel, M. Bächer, M. A. Otaduy, H. R. Lee, H. Pfister, M. Gross, and W. Matusik.
Design and Fabrication of Materials with Desired Deformation Behavior
SIGGRAPH 2010

N. Umetani, Y. Koyama, R. Schmidt, and T. Igarashi.
Pteromys: Interactive Design and Optimization of Free-formed Free-flight Model Airplanes
SIGGRAPH 2014
http://www.nobuyuki-umetani.com/publication/2014_sigg_pteromys/2014_siggraph_GliderDesign.html

M. Nakamura, Y. Koyama, D. Sakamoto, and T. Igarashi.
An Interactive Design System of Free-Formed Bamboo-Copters
Pacific Graphics 2016
https://mori0501.github.io/projects/BambooCopter/

過学習を避けるための工夫 (Regularization)

先に述べた通り、ナイーブな RBF 補間は過学習のようなことが起き得ます。これを避けるための一つの方法として、weight-decay regularization と呼ばれる手法があります。

f:id:yuki-koyama:20180509093627p:plain

次のページで詳しく説明されています。

rbf-interpolation - mathtoolbox

RBF Center の数を減らすための工夫 (Reduction)

その他の関連用語

Thin Plate Spline (TPS) Interpolation: https://en.wikipedia.org/wiki/Thin_plate_spline
Polyharmonic Spline Interpolation: https://en.wikipedia.org/wiki/Polyharmonic_spline

*1:追記 (2015/07/12): PRML の 6.3 章「RBF ネットワーク」にて次のように紹介されています："歴史的には，RBFが初めて導入されたのは関数補間 (function interpolation) を正確に行うためであった (Powell, 1987)．" (引用元：C.M. ビショップ. 元田他監訳. (2008). パターン認識と機械学習 (下) ベイズ理論による統計的予測. シュプリンガー・ジャパン株式会社.) つまり、RBF 補間という考え方がもともとあり、それをニューラルネットワークとして解釈したときに RBF ネットワークと呼ばれることがあるということだと思います。

セッションについて

1. Poisson-Based Caustics Design (TOG)

概要の意訳

できるだけ短くまとめると

Computational Caustic Design における一般的な問題設定

具体的な評価基準（どんな性質を持つ形状が望ましいか？）

手法

2. High-Contrast Caustic Design

概要の意訳

できるだけ短くまとめると

特徴

手法の流れ

[Yue et al., 2014] との比較

3. Boxelization

概要の意訳

できるだけ短くまとめると

4. The Connect-the-Dots Family of Puzzles: Design and Automatic Generation

概要の意訳

論文の全体像

前半: パズルのルールの拡張

後半: パズの自動生成

5. Self-Refining Games

概要の意訳

できるだけ短くまとめると

事前計算によるデータドリブンシミュレーション [Kim et al., SIGGRPAH '13]

データドリブンシミュレーション [Kim et al., 2013] では何が難しいか

クラウドソーシングを活用した賢い事前計算

そもそもクラウドソーシングとは

ゲームのプレイ統計をクラウドソーシングで集める

はじめに

そもそもクラウドソーシングとは

クラウドソーシングに関する論文

A Similarity Measure for Illustration Style

Self-Refining Games using Player Analytics

Exploratory Font Selection Using Crowdsourced Attributes

Intrinsic Images in the Wild

How Do People Edit Light Fields?

ゲーム物理エンジンに関する技術の集大成的論文

論文概要

この手法のメリット・強み

パーティクルに基づく手法

Position Based Dynamics に基づく手法

いままでに提案されてきた個別の技術

柔軟物体 (Shape Matching 法)

液体 (Position Based Fluids)

NVIDIA PhysX Lab

関連研究

細かいメモ

はじめに

RBF 補間とは

どういうときに使えるか

どういう特徴があるか

RBF ネットワーク

RBF 補間の考え方

RBF とは

関数の表現

重みの決め方

C++ による RBF 補間の実装

重みの計算方法

補間結果の値の評価

ソースコード

RBF 補間の応用

Computer Graphics (CG) 分野での応用例

過学習を避けるための工夫 (Regularization)

RBF Center の数を減らすための工夫 (Reduction)

その他の関連用語