三次元物体における Medial Axis の安定な推定法
076211 菅 和聖

指導教員 杉原 厚吉 教授

まず，次の Medial Geodesic Function (MGF) を定義す

1 はじめにる．この関数は，|Γ(x)| = 2 となる点の集合 MA2 上で定Medial Axis (MA) は物体形状の基本的な表現方法の一義される．

つであり，これまでに様々な応用が考えられてきた．しかし，MA は物体形状の摂動に弱いという性質をもっており，

定義 1 (Medial Geodesic Function) x ∈ MA2 に対安定的にこれを推定することは難しい．

して，Γ(x) = {ax , bx } であるとき，ax と bx の境界 ∂X 上

今回，３次元の物体に対してその形状を表す多面体を入力として取り，MA を安定的に推定する手法を提案する．
この手法は次のような特徴がある．の距離を f (x) とおく．この関数 f を MGF とする．
以下では MA の２多様体部分の極大部分集合の閉包を２多様体のシートと呼ぶ．これを用いて次の発散と CS を定• 摂動によって出来た枝や面を削除できる義する．

• ホモトピーを保存する• くびれのある図形でもうまく動く

定義 2 (発散) MA2 の閉包上の点 x における発散を次の• 重みの閾値を上げることによって MA が単調に減少ように定義する：x に隣接している各々のシートについてする

1div|S (x) = lim|B|→0 |B|

今までに３次元物体に対する MA の簡略化法の研究として様々な手法 [1, 4] が提案されているが，くびれのある図形を中心を低く評価したり，ホモトピーを保存するために複雑な操作を必要としている．
そこで本研究では，MA に単調な重みを与える戦略で２次元の物体に対する MA の簡略化を行った坂井ら [3] の手法を３次元の物体に対して拡張することを試みた．

Z∇f · n ds∂Bとおく．ここで，S は x に隣接するシート，B は S における x の開近傍であり，n は B の境界における外向き法線ベクトルである．この div|S (x) を x のシート S における発散と定義する．
定義 3 (Curve Skeleton) MA のうち，隣接するすべてのシートにおいて発散が負になる点の集合を A とし，隣接2 Medial Axis の不安定性
物体 X ⊂ Rn は開集合であるとする．点 x ∈ X と物体境界との最近点の集合を Γ(x) = {y ∈ X c : d(x, y) =するシートが存在しない点の集合を B とする．このとき，A ∪ B の閉包を CS とする．

d(x, X c )} とする．このとき，物体内部の点のうち境界へ閉包をとっている理由は，孤立点が原因で非連結になるこの最近点を２点以上持つ点の集合とを防ぐためである．

MA[X] = {x ∈ X : |Γ(x)| ≥ 2}を物体 X の MA という．

MA は物体形状の摂動に対して不安定である．なぜなら，物体に僅かな摂動を加えただけで，MA に新たな枝を生じさせ，大きく変化してしまうからである．

4 Medial Axis と Curve Skeleton の重み
CS と MA 上のグローバルな重みを定義する．まず，MAの部分集合 A に対して対応する表面の面積の割合で重みを与え，ローカルな重みとする．すなわち，２多様体曲面の面積を S とするとき，入力となる物体形状のデータに含まれる観測誤差や数値w(A) = 2 · S(誤差などの摂動によって生成された不要な枝を刈ることが[Γ(x))/S(∂X)

x∈A

MA の簡略化の動機である．
である．

3 Curve Skeleton の定義

次に，CS 上の点に対してグローバルな重みを定義する．

Dey ら [2] によって提案された Curve Skeleton (CS) の3仮定から X は１点にホモトピー同値であり，CS が１次元定義を述べる．CS は３次元の物体 X ⊂ R の１次元の中であることから，CS は木になる．点 x ∈ CS で CS を切断心軸である．物体 X は有界であり，境界 ∂X は滑らかか

すると，幾つかの部分木 T1 , . . . , Tk (k ≥ 2) に分かれる．

つ連結であるとする．

それぞれの木に対して ∇f に沿って MA のローカルな重みを集めて重みを定める：

w

[
SRC(z) .

y∈Ti

ここで，z ∈ CS に対して SRC(z) とは，x ∈ MA を起点とする ∇f の流れが，CS 上の点 z に到達するような点 xの集合である．x ∈ CS の重みは，この木 T1 , . . . , Tk の重みのうち，２番目に大きいものとする．
最後に，MA 上の点 x のグローバルな重みは，x から ∇f(a)(b)(c)に沿って辿っていき，到達した CS 上の点の上で定めた重みとする．これが最終的に求めたかった重みである．

図 1 (a) 多面体「Homer」，(b)CS，(c)MA ∪ CS
重みが大きい部分が赤い色で示されている．

5 アルゴリズム
入力は３次元物体の表面メッシュ P である．
ステップ１ (MA の計算)：P の頂点を母点集合としてボロノイ図を作成し，P の内部にあるボロノイ面を取り出し，MA とする．
ステップ２ (CS の計算)：Dey ら [2] の方法に従ってそこで，ある閾値に対して Y に穴が開いた場合，まず開いた穴の境界辺をループとして検出する．そして，MA の中でループの内側に入っている面を復元する．

6 出力例

MA に含まれる辺を CS として選ぶ．MA の面にたいして

図 1 は，このアルゴリズムの出力例である．(a) が入力∇f ベクトルを計算し，それらのベクトルがすべての隣接となる多面体，(b) が CS，(c) が MA ∪ CS をそれぞれ表面において入ってくる辺を選ぶ．

している．色は重みの高いところほど赤く塗られている．

ステップ３ (ラベル付け)：MA の面 F から，∇f 方向にMA を簡略化する際には，閾値 θ をユーザが指定し，そ面を辿って行ったときに初めて CS の辺 e に到達する．これ以下の重みの MA の面と CS の辺を削る．万が一穴が開のとき，面 F を CS の辺 e でラベル付けする．

いていれば，その穴を埋める．

∇f に沿って辿る際は，面 F の中で発散が最小になる辺e を選び，その辺に向かい合う面を次の面とする．もし，選んだ辺 e が３枚以上の面と接していたならば，発散の最も大きな面を次の面 Fnext として選ぶ．

7 まとめ
本研究では３次元物体における Medial Axis の安定的な簡略化法を提案した．この方法は，MA の点に単調性を持

ステップ４ (重みの計算)：MA の頂点 v に対して双対のつ重みを構成し，閾値以下の点を削除することで簡略化をドロネー四面体を取る．この四面体の面のうち，多面体 P行う．その際，物体のホモトピーを保存し，くびれた図形の境界上にある三角形の面積を P の総表面積で割り，２倍の中心部分を高く重み付けするなどの特徴を持つ．

したものを v の重みとする．そして，頂点 v の重みを隣接する面の数で均等に割り，v に隣接する面に配る．これでMA の面にローカル重みがついた．
CS の辺 e に対して，ラベルが e となる面のローカルな重みの和を取る．ここで，CS の頂点 v で CS を切断して得られる部分木 T1 , . . . , Tk に対してそれぞれ CS の辺の重みを足して木の重みとする．それらの中で，２番目に大きい値を v の重みとする．CS の辺の両端点の重みを平均して，CS の辺のグローバルな重みとする．最後に，MA の面 F のラベルが e ならば，面 F のグローバルな重みを eの重みで与える．
ステップ５ (穴埋め)：MA の面と CS の辺の和集合を Yとする：Y = MA ∪ CS．ある閾値に対して，Y から重みが閾値以下の MA の面と CS の辺を取り除いてできたものを「簡略化された MA」と呼ぶ．任意の閾値 θ に対して，簡略化された MA がホモトピーを保存するようにしたい．

参考文献[1] T. K. Dey and W. Zhao: Approximating the medial axis
from the Voronoi diagram with a convergence guarantee.
Algorithmica, 2003, Vol. 38 (1), pp. 179–200.
[2] T. K. Dey and J. Sun: Defining and computing curveskeletons with medial geodesic function. In Proceedingsof the 4th Eurographics Symposium on Geometry Processing, 2006, pp. 143–152.
[3] H. Sakai and K. Sugihara:
Stable and topologypreserving extraction of medial axes. In Proceedings ofthe 3rd International Symposium on Voronoi Diagramsin Science and Engineering, 2006, pp. 40–47.
[4] A. Sud, M. Foskey and D. Monocha:
Homotopypreserving medial axis simplification. In Proceedings ofthe 2005 ACM Symposium on Solid and Physical Modeling, 2005, pp. 39–50.