Carsten Stoll, Zachi Karni, Christian Roessl, Hitoshi Yamauchi and Hans-Peter Seidel, ``Template Deformation for Point-Cloud Fitting,'' Proc. IEEE/Eurographics Symposium on Point-Based Graphics 2006, pp.27-35

Abstract: The reconstruction of high-quality surface meshes from measured data is a vital stage in digital shape processing. We present a new approach to this problem that deforms a template surface to fit a given point cloud. Our method takes a template mesh and a point cloud as input, the latter typically shows missing parts and measurement noise. The deformation process is initially guided by user specified correspondences between template and data, then during iterative fitting new correspondences are established. This approach is based on a Laplacian setting for the template without need of any additional meshing of the data or cross-parameterization. The reconstructed surface ts to the point cloud while it inherits shape properties and topology of the template. We demonstrate the effectiveness of the approach for several point data sets from different sources.

---

Easy abstract:

レンジスキャンなどのスキャンデータには通常ノイズや穴などがあります． また，完全に隠れている部分は通常スキャンできません． たとえば，ここでの手のモデルのスキャンデータ (b) では指を完全にスキャンすることはできません． この図では一方向からのスキャンしか利用していないので， 後方にあたる手の甲部分を点群のみから再構成することも困難です． しかし，template を用いた我々の方法では， 穴の部分やスキャンできなかった部分を template の deformation により補間するため，完全なモデルを再構成することができます(図(a)-(d))． 最初，我々はこれを人間や動物のポージングに利用することを考えました． 後に我々はこの方法がまったく同じ人間や動物でなくても「意味的に似ている」 物体ならば再構成に利用可能であることに気がつき， その方向で手法を開発することにしました． (ここで，「意味的に似ている」という言葉は定義が難しい言葉です．たとえば， 四足動物という意味ではらくだと馬は意味的に似ていると言うことができると思います． ただし，ペンギンとノートブックコンピュータはどうかというと難しいです． もしかしたらトポロジが同じものにはなる可能性はあります． すると意味的に似ていると言えるかもしれません． しかし，これはかなり難しいです．)

Laplacian mesh deformation では回転に関しては invariant を保つことができません． (この詳しい意味も簡単ではないのですが，論文や参考文献にて議論されています． たとえば，Olga Sorkine's EG2005 の論文などを参考にして下さい．) 我々の方法では，各対応点における local frame の回転とスケールを計測によって予測し，deformation に利用する Laplacian matrix と同じ matrix により補間を行い，その情報に従って deformation を行う部分が新しい部分です．これを導入しないと，簡単に self intersection や，candy lapping などの問題が発生し，モデルのポーズの再構成は困難です． local frame の Laplacian による補間は EG2005 の Zayer et. al の論文によります．また，点群の情報を用いて， より正確な fitting も行います．

提案した方法では，一つの Laplacian matrix を何度も様々な方法に応用していることが興味をひくかもしれません．local frame 補間，scale 補間，deformation は全て同じ framework で行なわれています．(ただし scaling の measure だけは Dijkstra 法を使っています．) このように一つの framework に拘るのはなぜかと尋ねられても，それが最良かどうかは確かにわかりません． しかし，一つの数学的基礎でほとんどできるということは， 我々は単純で美しいと考えています． 数学的な興味からという答えがそこにはあります． 研究の過程で我々は他の手法，Multi-resolutin 解析，random sampling なども試してみましたが， 我々の手法でほとんどの場合に同程度か良い結果を得ることができました． それならば単純な方が良いと考えます． これによる恩恵は実装が簡単になるということもあります． また，私は Laplacian matrix がこれほど様々な問題に応用できるものだということを今回の研究を通じて知り， 驚きました．

Hitoshi Yamauchi, Waqar Saleem, Shin Yoshizawa, Zachi Karni, Alexander Belyaev and Hans-Peter Seidel, `` Towards Stable and Salient Multi-View Representation of 3D Shapes,'' In: IEEE International Conference on Shape Modeling and Applications 2006 (SMI2006), Matsushima, JAPAN, IEEE, Los Alamitos, 2006, pp.265-270

Additional materials:

• Slides

Abstract: An approach to automatically select stable and salient representative views of a given 3D object is proposed. Initially, a set of viewpoints are uniformly sampled along the surface of a bounding sphere. The sampled viewpoints are connected to their closest points to form a spherical graph in which each edge is weighted by a similarity measure between the two views from its incident vertices. Partitions of similar views are obtained using a graph partitioning procedure and their ``centroids'' are considered to be their representative views. Finally, the views are ranked based on a saliency measure to form the object's representative views. This leads to a compact, human-oriented 2D description of a 3D object, and as such, is useful both for traditional applications like presentation and analysis of 3D shapes, and for emerging ones like indexing and retrieval in large shape repositories.

---

Easy abstract:

3次元の物体が与えられた場合，いったいどこから見るのが良いのでしょうか? 良い視点という意味は，ある場所から物体を見た場合， より簡単にその物体が何であるかを理解できるような視点というふうに考えます． この質問に答えたくてこの研究をしました． 応用できる範囲としては3次元のサムネイルの自動生成， あるいは正規化した視点の自動生成(物体を検索するのに利用可能)などがあります．

物体を認識するという分野では， 一つの視点は物体の認識には十分ではないという意見が多数あります． ここではその考えに従い，いくつかの視点を提案し， その視点をある規範に従ってソートして提示するというシステムを構築することを考えます．

ここでは最初に 162 の視点をサンプルして画像を生成します(図(a))． 最初にこのサンプルから不要な視点をフィルタリングして消去します． 次に残った視点を人間の知覚をモデルとした手法でソートして表示します．

ステージ 1 (不要な視点のフィルタリング，安定な視点の探索): フィルタリングは，少し違う視点から物体を見て， どれだけその物体の見え方が違うかを計算し， もし視点を少し変更しても同じような画像が見えるのであれば 片方は不要な視点であると判断することで行います． 画像の類似度はよく利用されている Zernika moment 法を用いました． そして，この類似度を Edge に割り当てた Spherical Graph を構成し，Graph Cut 法を用いて視点領域の分割を行います(図(b))． この方法によると一つの領域の内部ではある程度同様な画像が観測されますので， 一つの領域内部で一つの視点だけを求めれば良いことになります． こうして不要な視点をフィルタリングすることで， 少ない視点候補を得ることができます．この論文では 162 のサンプルから 8 の候補にしぼりました．

ステージ 2 (Saliency を用いて視点を順位づけする): ステージ 1 によって視点を少ない数の候補にしぼりました． あとはこれをどういう順番に並べるかという問題になります． そのために，ここでは人間の知覚モデルを用いた saliency を計測し， それによって順位づけを行いました． 知覚モデルは Itti ら，Lee らのモデルを用いています．

Hitoshi Yamauchi, Stefan Gumhold, Rhaleb Zayer and Hans-Peter Seidel, ``Mesh Segmentation Driven by Gaussian Curvature,'' Pacific Graphics 2005, Macao, China, 2005, Oct.10-12, Visual Computer, Vol.21, No.8-10, pp. 649-658, http://dx.doi.org/10.1007/s00371-005-0319-x

Additional materials:

• PG2005, Mesh Segmentation Driven by Gaussian Curvature Slide (PDF)

Abstract: Mesh parameterization is a fundamental problem in computer graphics as it allows for texture mapping and facilitates a lot of mesh processing tasks. Although there exists a variety of good parameterization methods for meshes that are topologically equivalent to a disc, the segmentation into nicely parameterizable charts of higher genus meshes has been studied less. In this paper we propose a new segmentation method for the generation of charts that can be flattened efficiently. The integrated Gaussian curvature is used to measure the of a chart and a robust and simple scheme is proposed to integrate the Gaussian curvature. The segmentation approach evenly distributes Gaussian curvature over the charts and automatically ensures disc-like topology of each chart. For numerical stability, we use area on the Gauss map to represent Gaussian curvature. Resulting parameterization shows that charts generated in this way have less distortion compared to charts generated by other methods.

---

概要(やさしめ版):

ここでは，Texture mapping (parameterization) 用の Segmentation を考える．

Parameterization の Distortion(ゆがみ)を低くするため， セグメントされたパッチは developable (展開可能) に近いものとなることが望ましい． Developability は Gaussian curvature で計ることが可能である． そこで，全部のパッチが 0 の Gaussian curvature を持つならばそれでこの問題は解決される． 実はこれは可能で，メッシュを全部個々の三角形に分解してしまうことで達成できる． しかし，メッシュを個々の三角形にばらしてしまうと Texture を貼った時に， 三角形の境界付近に artifact ができてしまう． そのため，Texture mapping を考えると， パッチの数を少なくし，かつ同時に各パッチが低い Gaussian curvature を持つ ようなパッチを生成する問題を解かなくてはならない．

したがって，セグメンテーションは Gaussian curvature をパッチ全体にわたっ て分散させ，高い Gaussian curvature を持つ部分をパッチ境界にするようなも のが望ましい．そういうアルゴリズムがあれば，Parameterization の結果は distortion の低いものとなるだろう．

この論文はそのような問題への回答の一つを与える．ここでは Gauss area とい う Gauss map 上の面積を Gaussian curvature の代わりに使う．我々の目的は Segmentation であり，Gaussian curvature の良い近似を求めるものではない． Gaussian curvature は実は integration するのは数値的に難しさがあり， Segmentation にはちょっと使いにくいのである．Gauss area は数値的にコンパ クトで計算は簡単であり，しかも Gaussian curvature の持つ developability を計測できるという特性を供えている．そこで Gauss area を使うことにする．

Gauss area を計算することで，developability を計測することができた． すると，次の問題は Gauss area をどうやってパッチ全体に分散させるかという 問題がある．この問題を解くために，我々は t-floding というアルゴリズムを 開発した．これは time parameterized flooding の意味である．Gauss area を 計算するとその全体の値がわかるので，Patch の数 n が決まれば，各パッチが 持つべき Gauss area の総量が判明する．これを使うと Patch の成長速度が予 想できる．それに従って各パッチを成長させていけば，最後には同じような量の Gauss area を持ったパッチができる．なぜなら，全部のパッチが同様の速度で 成長するからである．

Hitoshi Yamauchi, Seungyong Lee, Yunjin Lee, Yutaka Ohtake, Alexander Belyaev and Hans-Peter Seidel, ````Feature Sensitive Mesh Segmentation with Mean Shift,'' In Shape Modeling International 2005, Cambridge, MA, USA, IEEE, Los Alamitos, 2005, 236-243

Additional materials:

• SMI2005 Slide (PDF)
• Demo video (same demo as performed at SMI2005) : noisy octahedron, Mannequin 21k tris. (1), Mannequin 21k tris. (2),
• Appendix video : Fandisk 13k tris. (1), Fandisk 13k tris. (2)
• Data : Octahedron with noise (off format), Fandisk model (off format)

Abstract: Feature sensitive mesh segmentation is important for many computer graphics and geometric modeling applications. In this paper, we develop a mesh segmentation method which is capable of producing high-quality shape partitioning. It respects fine shape features and works well on various types of shapes, including natural shapes and mechanical parts. The method combines a procedure for clustering mesh normals with a modification of the mesh chartification technique in [23]. For clustering of mesh normals, we adopt Mean Shift, a powerful general purpose technique for clustering scattered data. We demonstrate advantages of our method by comparing it with two state-of-the-art mesh segmentation techniques.

---

概要(やさしめ版):

ここではメッシュを部品に分解する(セグメンテーション)ことを考えます． 心理学の分野には人間がどう物体を部品に分解しているかということに関して， 広く信じられている minima rule という仮説があります．これは，人間は物体 の表面の normal 方向の変化の激しい部分を境界と見る傾向があるという仮説で す．特に凹の部分に人間は反応するというものです．我々はこの仮説を検討して， normal の変化の激しい部分を人間は物体の境界と見ていることを信じることに しました．この論文ではこのような境界を feature (特徴) と呼び，それは normal の変化の激しい部分にあると定義します．

まずは問題が定義されました．次は仮説に従った問題定義をどうセグメンテー ション用に数学の問題として解釈するかです．ある人々はこれを curvature の 問題と考えました．しかし，curvature の計算は数値的にはなかなか難しいもの です．そしてセグメンテーションではある連続した境界が必要で，これもなかな か難しいです．特にスキャンした物体には必ず存在するといっていいメッシュの ノイズがある場合は難しいです．

feature とノイズを同時に扱うために，様々な試みがありました． morphology operation, diffusion process, distance function with weight coefficient などなど．調べていて一つの疑問が我々の頭に浮かびました． distance function を使う人達は普通は非等方性を使いません，でもこれらの方 法では，dihedral angle のような feature を考えているものがあります．そし てfeature には普通等方性がありません．

これらの問いに対する我々の答えは単純です．まずは，非等方性のカーネル 密度評価手法である Mean Shift 法で feature を解析し，feature のエンハン スも行ないます．その後にfeature に sensitive なセグメンテーション方法を 適用するのです．featureに sensitive というのは noise に弱いということで もあるのですが，しかし，既に Mean Shift によって feature が enhance され， ノイズの除去も行なわれているため，これまでとは違う sensitive な方法が使 えるのです．これまでの方法では，ノイズと feature のバランスをどうとるか を決めるパラメータが(複数ある場合も)ありました．しかし我々の方法では，セ グメンテーションにはそのパラメータは不要です．もちろん我々の方法でも feature 解析部分で一つのパラメータが必要ですが，これまでに比較してその選 択は容易になっています．これは，feature の解析とセグメンテーションが分離 されたプロセスになっているからです．様々な要因が絡んだ最後の結果だけしか 見ることができない方法と違い，途中の様子がわかるという意味で容易です．

feature analysis では 6次元の空間を対象にします (geometry position + normal). セグメンテーションでは，この feature space とメッシュ の connectivity を考慮します．

Hitoshi Yamauchi, Hendrik P.A. Lensch, Jörg Haber and Hans-Peter Seidel, The Visual Computer, 21(4), pp.217-241, ISBN 0178-2789, ISSN: 0178-2789 (Paper) 1432-8726 (Online), DOI 10.1007/s00371-005-0283-5, Springer, Heidelberg, May, 2005

We describe texture generation methods for complex objects. Recent 3D scanning devices and high-resolution cameras can capture complex geometry of an object and provide high-resolution images. However, generating a textured model from this input data is still a difficult problem.

This task is divided into three sub-problems: parameterization, texture combination, and texture restoration. A low distortion parameterization method is presented, which minimizes geometry stretch energy. Photographs of the object taken from multiple viewpoints under modestly uncontrolled illumination conditions are merged into a seamless texture by our new texture combination method.

We also demonstrate a texture restoration method which can fill in missing pixel information when the input photographs do not provide sufficient information to cover the entire surface due to self-occlusion or registration errors.

Our methods are fully automatic except the registration between a 3D model with input photographs. We demonstrate the application of our method to human face models for evaluation. The techniques presented in this paper make a consistent and complete pipeline to generate a texture of a complex object.

---

概要(やさしめ版):
複雑な3次元物体とその写真からどうやったら texture map された物体を作るこ とができるかという問題を考えます．できるだけ自動でやるにはどうしたら良い かということに特に重点を置いた手法をここでは考えました．

複雑な物体の CAD データを手で作り，それに Texture 座標と画像を生成す るというのはそんなに簡単ではありません．この論文ではこれを簡単化(あるい は自動化)するいくつかの手法を提案しています．この方法はゲームのキャラク タの生成や，仮想美術館，映画のキャラクタの生成には利用できるでしょう．も ちろん映画の場合には主人公は無理でしょうが，背景の人達やTexture 付きの物 体の自動生成には使えると思います．

物体の3次元データといくつかの写真，そしてレジストレーションデータが必要 な入力の全てです．もう少し詳しく言うと，入力は3次元の(スキャンした)デー タのメッシュ，その物体のいくつかの方向からの写真，そして物体と写真のレジ ストレーションデータです．レジストレーションデータというのは，3次元物体 のある点が写真のどこに対応しているかというデータです．ここでは，アルゴリ ズムがどれだけ上手く働くかを調べるために，人間の顔を例題に再構成を行って みました．実際，人間の顔というのは一番難しい問題に入ります．映画に出てく る宇宙人とか怪物，幽霊とかいうものの方が簡単です．というのも，「これが私 の怪物モデルです．」と言われたら，それがちょっと変でもなかなか反論できな いからです．これこそが「本物(?)」の怪物だ，と誰かが保証するのはまず無理 でしょう．私は身近な物体を再構成する方が皆が知っているために問題は難しい 感じます．(韓非子(B.C.2世紀)の中にも同様の話があります．絵描きが本物そっ くりに物を書く能力があるかどうかを調べるには，幽霊や怪物を描かせるのでは なく，犬や猫を描かせる方がよくわかるというような話です．) レジストレーショ ンデータとしては，人間の顔の場合，鼻のてっぺんはどこかとか，目尻の点はど こかという対応点が 20 から 30 点あれば十分です．この論文では，対応点を決 める部分だけは残念ながら自動でできませんでした．論文の例では，1つの顔に5 枚の写真を入力とし，対応点の入力には 10 分から 20 分ほどかかりました．

入力データが集まったら，Texture を生成します．ここでは， 次の 3 つの問題を解いて Texture を生成するという方法を考えました．

• Parameterization ... ゆがみの少ない Texture 座標をどうやって生成するかという問題．
• Texture combination ... 入力写真を継目なく自動合成する問題．
• Texture restoration ... 画像を自動で修復する問題．

この論文では，以上の 3つの問題を解きました．全部を説明することはできませ んが，いくつかのトピックをとりあげてみます．

Parameterization には geometric stretch error を使う方法を基本に改良しま した．この方法では，parameterization 前と後の三角形間の affine 変換の matrix の特異値を使います．(なにか難しい言葉ですが，とにかくこの値を見れ ば，三角形が3次元上から2次元上にうつされた時どれだけゆがんだかがあるレベ ルでわかります．高校生レベルの数学で十分理解できる考えです．) しかし，総 合のエラーが各三角形のエラーの和になるので，local minima 問題というもの につきあたります．たとえば，ほんの一部の三角形が degenerate してしまって も，全体としてはエラーが少なかったりということが発生します．degenerated な三角形というのは，直感的にはつぶれてしまった三角形です．三角形の3点が 直線上に並んでしまったり，一点に集まってしまった場合を言います．この論文 では，このような degenerated な(つぶれた)三角形を作らないようにするため の項を導入しました．総合のエラー，つまりゆがみそのものは多少大きくなりま すが，texture map では三角形がつぶれてしまう方がひどい結果になるので，そ れを避ける方法を提案しました．

ある物体に対して複数方向の写真をとった時，さえぎられて見えない部分や，写 真を撮った時の光の加減で見えない部分や，あるいは，レジストレーションのエ ラーによって見えないピクセルがでてくることがあります．画像を自動で修復す る問題というのは，こういう失なわれたピクセルをどうやって自動で推定するか というものです．もちろん Photoshop や gimp で直してもかまいません．この 方法は Photoshop や gimp 使いの人にも，とりあえず自動で修復して，あとか らもっとちゃんと直すという時の「とりあえず直しておく」に利用できます．ど んなアルゴリズムも美的な仕事の場合には，美術的センスの優れたアーティスト にはかないません．しかし，このアルゴリズムが「そこそこ使える助手」として 優れたアーティストの助けにならないかなと思います．

これらの手順は一種のパイプラインのように矛盾なく働きます．いろんな方法を 組合せると上手くいかなくなるいうこともありますが，ここの方法は全体を評価 して確認しています．

Hitoshi Yamauchi, Jörg Haber and Hans-Peter Seidel, Proc. Computer Graphics International (CGI) 2003, 2003, pp.120-125, 9-11 July, Tokyo, Japan

CGI 2003 papers TOC, paper download from IEEE computer digital library

We present a new method for the restoration of digitized photographs. Restoration in this context refers to removal of image defects such as scratches and blotches as well as to removal of disturbing objects as, for instance, subtitles, logos, wires, and microphones.

Our method combines techniques from texture synthesis and image inpainting, bridging the gap between these two approaches that have recently attracted strong research interest. Combining image inpainting and texture synthesis in a multiresolution approach gives us the best of both worlds and enables us to overcome the limitations of each of those individual approaches.

The restored images obtained with our method look plausible in general and surprisingly good in some cases. This is demonstrated for a variety of input images that exhibit different kinds of defects.

---

概要(やさしめ版): やりたいことは，画像の欠けた部分を自動で修復すると いうことです．たとえば，画像中の不要なものを消したいとか， 見えなくなっている部分を自動で直すというものです．

画像の自動修理方式としては2つの主な方法があります． 一つは PDE (Partial differential equation 偏微分方程式) を解くことによる方式で，もう一つは Texture synthesis 法と呼ばれるものです． PDE を基本にした方法は画像輝度の連続性を上手く扱えます． これは基本的にこの方法が拡散方程式を基本にしているからです． 一方で，Texture synthesis 方式は類似した小さな部分画像を転送することで 新しい画像の生成を行う方式です．この方式は類似な物を探索して転送するため， 連続性のようなことはあまり考えません．

ここで私達は，「この二つの方法の利点を， それぞれの欠点を排除しながら上手く組み合わせられないだろうか」 ということを考えました． PDE 法では連続性を考えますが， それはスムーズになってしまって細い模様などを再現しにくいです． Texture synthesis 法は詳細な模様を生成できるけれども， 画像の連続性や画像の持つ大きな構造を再現することができません． 片方は偏微分方程式を解く方法で，もう片方は探索と再構成です． いったいこれらを上手く組み合わせる方法はあるのでしょうか?

我々が各方法を見て考えたことは次のようなものでした．

• PDE 法で連続性を保つというのは，言いかえれば 入力画像の低周波数成分を再構成するという意味ではないだろうか．
• Texture synthesis 法による類似部分画像の探索と転送とは， 言いかえれば画像の高周波成分をするという意味ではないだろうか．

こう考えて次のような解答を考えました．

• 低周波数成分 : 大域的構造/大きな gradient 領域
  • => PDE 法を元にして再構成
• 高周波数成分 : Texture/詳細な構造
  • => Texture synthesis 法を元にして再構成
• これを合成する方法
  • => 周波数分解を使う!

ここでは，入力画像を FFT/DCT などの方法を用いて 高周波数成分と低周波数成分に分解し，各成分を PDE 法と 多重解像度 texture synthesis 法を用いて再構成し，最後に合成するという アルゴリズムを提案します．また，何が高周波数成分/低周波数成分なのか， つまりその周波数はいくつなのか， ということに関してもこの論文では議論し， その周波数パラメータをみつける方法に関しても提案を行なっています．

Kolja Kähler, Jörg Haber, Hitoshi Yamauchi, and Hans-Peter Seidel In: Proceedings of the 2002 ACM SIGGRAPH Symposium on Computer Animation, San Antonio, USA, July 21-22, 2002, ACM SIGGRAPH, New York, 2002, pp. 55-64

You can find the PDF version of this paper and its demo movie at this page.

Abstract: We present a versatile construction and deformation method for head models with anatomical structure, suitable for real-time physics-based facial animation. The model is equipped with landmark data on skin and skull, which allows us to deform the head in anthropometrically meaningful ways. On any deformed model, the underlying muscle and bone structure is adapted as well, such that the model remains completely animatable using the same muscle contraction parameters. We employ this general technique to fit a generic head model to imperfect scan data, and to simulate head growth from early childhood to adult age.

---

概要(やさしめ版) : 人の顔のスキャンデータと10 分程度の作業で， 物理シミュレーションに基づくアニメーション可能な 3D model を作る方法． 機械的にスキャンしたデータや，それを G-H 法などで decimation しただけの顔のメッシュでは， アニメーションを行うのは簡単ではないことが多いです． たとえば，そのままでは口を動かしにくかったり， 目や口はどうするかとかの問題があります． この論文ではそのような問題に対する一つのアプローチを試みています． 必要なものは，3D スキャンデータと 10 分程度の操作のみ． 操作というのは特徴点となるlandmark を計算機に教える作業です． ただ，3D スキャン自体に時間がかかるのと，計算機がいろいろ計算するまで多少待つ 必要はあります． もちろん自動で生成されたデータが気に入らない場合には手作業が必要ですが， それでもこの結果からスタートすると楽になると思います．

まず，Generic model という landmark のついているモデルを最初に一回作っ ておきます．これはアニメーションができるようにポリゴンの数を調整するなど してあります．でもこのモデルではどこかの誰かの顔でしかありません．この Generic model から個人の顔を作る方法をこの論文で述べます．

• まず，X さんの顔をレンジスキャンして 3D の情報を得ます．
• Landmark を 60 点ほどスキャンデータに打ちます． ここだけはマニュアルです． この作業には我々の場合 10 分から 20 分ほどかかりました． Landmark は顔の特徴点で，たとえば目尻とか鼻のてっぺんなどです． このような点は解剖学の研究者の方々が定義しているものを使いました．
• ここで論文のアルゴリズムを走らせると，Generic model がスキャンデータにフィットします． アニメーションができる X さんの顔のできあがりです．

解剖学の方々は年齢と Landmark 間の関係の研究をしています． そのデータとこの論文のアルゴリズムで，X さんの顔を年寄の顔にしたり， 若い人にすることが自動でできます． レンダリングは最近の PC + グラフィックスのカードがあればリアルタイムです． ここで使ったのは 1.7 GHz x 2 PentiumIV + GeForce3 です． 他にもリアルな顔にする手法，たとえば， 顔の表面に皺が寄っている様子をリアルタイムレンダリングする 方法なども述べます．

Marco Tarini, Hitoshi Yamauchi, Jörg Haber and Hans-Peter Seidel, Proceedings Graphics Interface 2002, Calgary, Canada, 27-29 May 2002, A K Peters, Natick, 2002, 89-98

You can find the PDF version of this paper and its demo movie at this page.

Abstract: We present a number of techniques to facilitate the generation of textures for facial modeling. In particular, we address the generation of facial skin textures from uncalibrated input photographs as well as the creation of individual textures for facial components such as eyes or teeth. Apart from an initial feature point selection for the skin texturing, all our methods work fully automatically without any user interaction. The resulting textures show a high quality and are suitable for both photo-realistic and real-time facial animation.

---

概要(やさしめ版) : 顔の要素，特に複数の写真から継目のない Texture 画像をできるだけ自動で合成する方法を述べます． もちろん，写真ならなんでも良いので，昔のスターの写真とかでも OK です．

1. 顔の皮膚 texture はスキャンした3 次元モデルといくつかの方向からデジタルカメラでとった写真を合成します． 継ぎ目のない UV 座標の作り方と複数の写真の画像を継ぎ目なく継ぐ方法を述べます． Texture に継ぎ目がないといっても単にぼかしてしまうのは意味がありませんので， いくつかの解像度レベルに分解し，各段階で Spline で継ぎます．
2. 目の Texture では目の一部を検出し， それを元に目全体を合成する方法を述べます． 目の Texture は極座標上では一様な性質を持つことを利用します．
3. 歯の Texture の作成では歯のおおまかな部分を写真から指定すると， Shading の影響を調整し，色を元にして歯を抽出します． それを imposter として歯のモデルに貼ります．

Jörg Haber, Kolja Käler, Irene Albrecht, Hitoshi Yamauchi and Hans-Peter Seidel, Proceedings of the 3rd Israel-Korea Binational Conference on Geometrical Modeling and Computer Graphics, Seoul, Korea, October 11-12, 2001, pp.73-82 (Invited talk: From Real Humans to Realistic Facial Animation)

You can find the PDF version of this paper and its demo movie at this page.

Abstract: We present a system for photo-realistic facial modeling and animation, which includes several tools that facilitate necessary tasks such as mesh processing, texture registration, and assembling of facial components. The resulting head model reflects the anatomical structure of the human head including skull, skin, and muscles. Semiautomatic generation of high-quality models from scan data for physics-based animation becomes possible with little effort. A state-of-the-art speech synchronization technique is integrated into our system, resulting in realistic speech animations that can be rendered at real-time frame rates on current PC hardware.

---

概要(やさしめ版) : 顔を生成するためのツールとして有用なシステムの概要を述べます． 以下の手法が説明されます．

• 三次元メッシュとデジタル写真画像の対応から， UV 座標を生成する手法．ここでの UV 座標は三角形ごとに定義されます．
• 筋肉モデルに基づく顔のアニメーション手法
• スピーチ音声とアニメーションの自動同期に関する手法．
• アニメーション(スピーチ含む)のレンダリングはリアルタイムで行なわれます．

Jörg Haber, Karol Myszkowski, Hitoshi Yamauchi and Hans-Peter Seidel, Computer Graphics Forum, Proceedings of Eurographics 2001, Manchester, UK, September 3-7, 2001, Blackwell, Oxford, 2001. PDF version, The full paper and its demo movie are also available at the Eurographics Digital Library

Abstract: One of the basic difficulties with interactive walkthroughs is the high quality rendering of object surfaces with non-diffuse light scattering characteristics. Since full ray tracing at interactive rates is usually impossible, we render a precomputed global illumination solution using graphics hardware and use remaining computational power to correct the appearance of non-diffuse objects on-the-fly. The question arises, how to obtain the best image quality as perceived by a human observer within a limited amount of time for each frame. We address this problem by enforcing corrective computation for those non-diffuse objects that are selected using a computational model of visual attention. We consider both the saliency- and task-driven selection of those objects and benefit from the fact that shading artifacts of ``unattended'' objects are likely to remain unnoticed. We use a hierarchical image-space sampling scheme to control ray tracing and splat the generated point samples. The resulting image converges progressively to a ray traced solution if the viewing parameters remain unchanged. Moreover, we use a sample cache to enhance visual appearance if the time budget for correction has been too low for some frame. We check the validity of the cached samples using a novel criterion suited for non-diffuse surfaces and reproject valid samples into the current view.

Iterative Square root 5 sample results. Square root 5 resampling method (as recursive) is proposed by M. Stamminger, G. Drettakis: Interactive Sampling and Rendering for Complex and Procedural Geometry, Rendering Techniques 2001 (Proc. EGWR 2001), Springer Verlag, pp. 151-162. An iterative algorithm of square root 5 resampling is shown up this paper.

---

概要(やさしめ版) : 14 フレーム毎秒でレイトレーシング画像を 生成する一つの方法を提案します． これはパーセプションに基づく interactive raytracing 手法に関する論文です．ゲームなどでは OpenGL でも結構すごい絵が最近は見えます．レイトレーシングの方が綺麗ですが， OpenGL でもかなり良い近似だと思いませんか? では，画像の基本部分を OpenGL とグラフィックスハードウェアで描いて， 反射とか透過とかグラフィックスハードウェアがあまり得意でない部分だけ レイトレーシングすればいいんじゃないかというのがこの論文です．

• フレーム毎秒(fps)を固定したい．ここでは 10 から 15 fps に固定しました．
• 画面のどこをレイトレーシングすれば良いかを どうやって決めるかに関する手法．物体の属性などを用います．
• どこをレイトレーシングすれば良いかという場所がわかっても， fps が決まっていれば計算できる時間は限られているので 全部レンダリングできないかもしれません． その次はどこから計算すれば良いかを考えます． それは人間の感覚モデルに基づいて決めます． 例えば遠くで暗い場所は動きが激しい場合には skip しても気付きにくいだろうから後にするとかいうモデルを使います． Interactive なので視点が移動してしまえば 気付かないまま進んでしまうかもしれません．
• 全部レイトレーシングしなくてはいけないような場面もあります． しかも操作する人がじっくり見たい場合があります． その場合には最終結果に素早く収束するサンプリング方法はどういうものか を考えています．
• 一度通って見たシーンの情報は再利用できる場合があります． たとえば，物体の normal vector と view vector との内積がほとんど同じ場合とかは，既に計算したレイ情報が再利用できます． それを高速に再利用するためのアルゴリズムを述べます．

With: Kobayashi Hiroaki, Maeda Atusi

Some people say ``Java? That is slow and useless.'' And the others say ``That is good and useful.'' But, usually former people didn't write any real application with Java. And latter people just write applications with Java. Therefore, the reasonable comparisons for applications are hard to find. What all we can find the comparisons are ``overhead of method call, overhead of memory allocation, comparison the performance of matrix multiplication, etc.'' Yes, it is very important, but, I just want to know the how some applications are.

So, my question is ``Does anybody write a real application with Java and C++, and how were they?''

Here is a parallel radiosity and ray-tracing renderer with written in both Java and C++ by the same person (me). We will show the comparisons of both performance, memory consumptions, and etc.

(This model is the soda shop from Radiance site, and rendered by our parallel rendering system written in Java.)

---

概要(やさしめ版) : Java 結構良くできた言語だと思うのですが， 皆が「遅い」と言います． 確かに 2000 年の時点で Browser に入っているバージョンは同じようなコードを C で書いた場合に比べて 10 倍以上とか遅いですが， 最近のものは 2 倍程度の差になっています． でもやっぱり遅いと言われてしまいます．本当なんでしょうか． それにまともなアプリケーションがあまりないですね． やっぱり大きなプログラムは駄目なのでしょうか? と思って並列ラジオシティ/レイトレーシング法を Java で実装してみました．

やってみると，私の場合には C++ よりも楽に実装できる上に，実行時間は 2 倍とか最悪でも 3 倍程度です．(Sun SDK 1.2) こういう速度が重要なプログラムだと 2 倍は嫌という人がいるかもしれませんが，日々のプログラム， エディタとかではプログラム開発にかかる時間を考えると，Java は十分良いのではないかなと思います． ただ一つ，メモリの消費量が多いのは気になりましたが， これはどうしてなのかわかりません． この論文では同じ人が同じアプリケーションを書いた場合に， どれだけの差があるのかなどについて議論しました． 参考文献には違う人が書くとどれだけ違うかの研究がありますが， 単なるサーチでも 100 倍とか簡単に違うそうです． この論文はプログラマを選んだ後で， どの言語を選択するかの時には参考にはなります． でも言語の差は 3 倍とかなので，まず，100 倍差のでることもあるプログラマの方をちゃんと選ばないといけません．

With: Kobayashi Hiroaki, Maeda Takayuki, Nakamura Tadao, Toh Yuichiro, Tokunaga Mayumi (in alphabetical order), and Nakamura Laboratory.

One of the big problem of parallel rendering is load balancing. Dynamic load balancing method needs some computation for balance the system load. Therefore, static way is better if it is possible. Of course, the combination of both methods is good idea like coarse load balancing with static way and fine tuning with dynamic way. But a load estimation for a static load balancing method is difficult.

Our basic idea is using random mapping methods of tasks to processing nodes. Since the load will be usually unbalanced with the common task allocation methods. Then, I randomly mapped the problems to computation nodes. This idea works well and we show how to implement this idea and evaluate it.

(This model is the conference room from Radiance site, and rendered by our parallel rendering system.)

---

概要(やさしめ版) : 並列プログラムで問題なのは Load balance です． 100 台使っても，1 台しか働いていなければ速くならないし， 遅くなることもあります． たとえば，黒板を一冊のノートに写すという作業を 100 人で分担してやろうとしたら，一人の方がよっぽど早いこともあるでしょう．

並列画像生成法に，空間分割型の並列処理方法というものがあります． これは空間を分割して各空間ごとに並列処理する方法です． 空間の分割に regular な格子を使うと光の伝搬計算時に高速な DDA という手法が使えるのでこれを使ってみましたが， 物体の存在がだいたいいつも偏るので，どうも上手く分担できません． というのは重力の影響で物はいつも床の近くとか，壁の近くにあって， 普通のシーンでは空中にぎっしりと物が 詰まって浮いているとかがないからです．

そこで，どうせ偏るなら，空間をもっと細く分割して， CPU をランダムに割り当ててしまえばいいんじゃないか． 偏っているものを細くしてランダムに割り当てれば平均化するのではというアイデアで 負荷分散を行なったのがこの研究です． 結構上手くいく，たとえば，48 台で 30 倍高速化される， のですが，しかし，数学的にランダムネスを解析するとか， そういう部分がちょっと弱かったかもしれません． どのようなランダムネス，実際は hashing なのですが， が良いのかに関しても一応考察していますが， 理論的にもっと良いものがあるかとかは今後の課題です．