形状の類似性による 3 次元モデルの検索
Shape Similarity Search of 3D Models
大渕 竜太郎Ryutarou Ohbuchi
山梨大学
University of Yamanashi
ABSTRACT

Proliferation of 3D shape model, for such diverse purposes as 3D TV content production, engineering CAD, drug design,
video game, or medical diagnostics and treatment planning, has created needs to analyze, group, compare, mine, edit, andsearch large number of 3D models based on their content, most importantly, their shapes. Comparing and analyzing alarge number of 3D models would enable “data driven” approaches to solve various problems. For example, combinedwith machine learning, auto-completion or semi-automatic synthesis of 3D models may become reality. This talkprovides an overview of shape based similarity comparison and search of 3D shape models, one of the enabling
technologies for data-driven 3D shape model processing.
Keywords: マルチメディア情報検索，3 次元形状モデリング，3D コンピュータグラフィックス．

1．活躍する 3 次元のカタチ
立体視のできる 3D TV が普及しはじめた．そのコンテンツ作成には，今まで以上に 3 次元形状モデル（3Dモデル）が使われそうである．Google Earth を豊かにする目的で Google が無料配布した 3D 形状モデリング
ソフト Google Sketchup は，100 万を超える数の建物，乗り物，家具，植物，などの 3D モデルを生み，これらがGoogle 3D Warehouse に蓄積されている．ユーザ生成の 3D モデルと，それを用いたユーザ生成の CG 動画コンテンツがネット上にあふれている．もちろん，ケータイ等のゲーム，機械の設計や強度解析，医療現場における診断や治療計画，創薬，セキュリティなどの場面でも広く 3D モデルが用いられている．これら多量の 3Dモデルの集合を，その内容に基づいて，編集し，（擬似）構造化し，分類し，整理し，マイニングする処理が注目を浴びつつある．代表的なのが，3D モデルをそのもっとも重要な属性である形に基づいて比較・検索する技術である[1][4][8]．
3D モデルをその形状で比較・検索できるようになれば，いろいろな応用が開ける．コンテンツ作成の際に，欲しい 3D モデルを検索で探し出しコンテンツ作成に再利用するのは検索の基本的な使い方である．大量の3D モデルの形を解析し，比較し，分類し，検索できるようになると，機械学習等と組み合わせることで，3D モデルの形を処理する種々の問題に「データ駆動」でアプローチできるようになる．例えば，検索して得た複数の 3Dモデルの中から複数の欲しい部分を「良いとこ取り」して組み合わせて手軽に新たな 3D モデルを生成する[2]，
大渕 竜太郎ohbuchiATyamanashi.ac.jp
国立大学法人 山梨大学・医学工学総合研究部〒400-8511 山梨県甲府市武田 4-3-11

あるいはレンジスキャナで獲得した 3 次元モデルの部分的な欠損を，検索して得た類似形状の 3D モデル（群）の情報で補う[6]，などのような，新たな形状モデリング手法が可能になる．検索でロボットの把持を助けることもできる．ロボットが物体を把持する際に，何処をどのようにつかめば良いのかはその形に大きく依存し，最適な把持の計算は手間がかかる．そこで，把持すべき物体に形の似た 3D モデルをデータベースから探し，検索した物体用に計算した結果を出発点とすれば，大幅に手間が省ける[3]．この他，3 次元の形と何か別のデータ，例えば，人の感情，あるいは機械の組み立て性や壊れやすさ，等を共にマイニングする，等すれば，さらに多様な応用がありそうである．
2．形で 3D モデルを比較・検索する
3D モデルは，その 3 次元の形に加え，表面や内部に種々の属性を持つ．見かけが重要な 3D モデルなら，面に色，法線マップやテクスチャ画像などを持つ．流体シミュレーションの結果なら，面または体積に圧力（スカラー），流れ場（ベクトル）等の属性を持つだろう．今のところは形状が 3D モデル類似検索の主な比較対象である．しかし今後は，種々の属性や，さらには形や属性の時間変化を考慮する比較・検索手法も現れるだろう．
3D モデルを形で比較・検索するクエリの組み立ては重要な課題である．最も多いのは 3D モデルの例示だが，都合よく手元に適当な 3D モデルがあるとは限らず，テキスト，2 次元（2D）スケッチ，3D スケッチ，写真，印象語，およびこれらの組み合わせもクエリとして用いられる．さらに，いわゆる意味の乖離（semantic gap）を超えて検索するために，意味（共有されて安定している）や意図（検索セッションごとに変わる）をどのようにしてシステムに伝えるかも重要な課題である．

形による 3D モデルの比較・検索は，全体と部分のどちらで比較するか，姿勢変化（articulation）や全体変形（global deformation）に対する不変性を求めるか，により分類できる．全体検索は，クエリと検索対象をそれぞれの全体形状で比較する．部分検索では，部分をクエリとしてその部分を含む全体を検索したり，あるいは，全体をクエリとしてその全体に含まれる部分形状を持つ全体を検索したりする．姿勢変化や全体変形に不変な比較ならば，人がしゃがむなどして姿勢が変化しても類似とすることができる．これまでの手法のほとんどは，剛体を仮定した全体検索であった．剛体の全体検索に限れば，用途（とデータベースの規模）を限定しさえすればその検索性能は実用的なレベルになった．姿勢変化
モデルの全体検索については，局所特徴の集合を用いるなどして，最近一定の成果が得られた．これらに対し，部分による比較・検索に関する研究は始まったばかりで，これといった成果は出ていない．
3D モデルの形状類似比較では，全体・部分のいずれで比べる場合も，相似変換などの大域的な幾何変換に対する不変性が求められる．3 次元の相似変換の 7自由度，特に回転 3 自由度に対する不変性の実現は難しい．相似変換不変性の実現には，完全に相似変換不変な特徴を用いるか，部分的な姿勢正規化と部分的に相似変換不変な特徴を組み合わせることが多い．
2D 画像と比べ，3D モデルの比較・検索に特徴的なのは，3D モデルの形状を表すために多種多様で，かつしばしば互いに互換性の無い形状表現が用いられていることである．例えば，（開いた）ポリゴンメッシュ（2 次元ならば開曲線に相当）を 3 次元のソリッド（立体）（2 次元ならば閉領域に相当）に変換することはできない．このため，回転等の幾何変換に対する不変性や姿勢変化に対する不変性をにらみつつ，与えられた形状表現から形状特徴を抽出できる方法を用いる必要がある．
Figure 1 は，多様な形状表現を比較できるように，3D モデルの見かけで比べる手法の例である[5]．多視点（42 視点）から生成した深さ値画像から，回転・拡大などに不変な 2 次元画像の局所特徴を多数抽出し，それらを 1 モデル 1 特徴ベクトルに統合してモデル間を比較する．局所特徴を用いるため，姿勢変化に対する不変性も持つ．ただ，この手法では，3D モデルの内部構造を考慮した比較はできない．
局所特徴抽出

多視点画像生成視点 1視点 i…
視点数
42

視点 42

Bag-ofFeatures

特徴数~10k 個

3．おわりに本稿では，3 次元モデルの形状による類似検索について簡単に紹介した．まだ比較的新しい研究分野であるが，近い将来，全体検索の実用化，部分による検索の研究の進展，が予想される．また，これらの技術を用いた多様な「データ駆動」型問題解決アプローチの展開が期待され，楽しみである．
参考文献[1] B. Bustos, D. Keim, D. Saupe, T. Schreck, Content-Based
3D Object Retrieval, IEEE CG&A, 27(4), pp. 22-27,(2007).
[2] T. Funkhouser, M. Kazhdan, P. Shilane, P. Min, W. Kiefer,
A. Tal, S. Rusinkiewicz, D. Dobkin, Modeling byExample, ACM TOG, 23(3), pp.652-663, (2004).
[3] C. Goldfeder, M. Ciocarlie, J. Peretzman, H. Dang, P. K.
Allen, Data-driven grasping with partial sensor data, Proc.
2009 IEEE/RSJ Int’l conf. on Intelligent Robots &Systems (IROS), pp. 1278-1283, (2009).
[4] M. Iyer, S. Jayanti, K. Lou, Y. Kalyanaraman, K. Ramani,
Three, Dimensional Shape Searching: State-of-the-art
Review and Future Trends, CAD, 5(15), pp. 509-530,(2005).

局所特徴
統合

…

この他，検索しようとする 3D モデル集合の性質も重要である．多様な形がある（例：自動車，人，飛行機，机，植木，…）のか，ほぼ均一か（例：人の顔のみ），また，表面電荷分布などの属性が重要か（例：化学物質），などにより使用するアルゴリズムが変わる．検索の使い道
によっては形よりもむしろ意味や意図が優先する場合がある．このような場合は，機械学習等を用い，「意味の乖離」を超えた検索手法の開発が必要となる．
マルチメディア検索の研究を進めるうえで，手法の評価に用いるベンチマークデータセットは大変重要な役割を果たす．例えば，2006 年以来，毎年開かれている
3D モデル検索の国際コンテスト SHape REtrieval
Contest (SHREC)[7]は技術の発展に寄与してきた．
2006 年には剛体の全体検索を評価する 1 種目のみが行われた．以後，年度ごとに内容は異なるものの，CADモデル，顔モデル，分子モデル，姿勢変化モデル，など多様な部門で競われてきた．今後，研究者として欲しいのは，検索手法のスケーラビリティと性能の両方が評価できるような，モデル数が 1 万（できれば 10 万）を超える大規模なベンチマークデータベースである．例えば，Google 3D Warehouse のスナップショットが公開されると大変ありがたい．

⎛ 5⎞⎜ ⎟⎜7⎟⎜ 4⎟⎝ ⎠特徴ベクトル~1k 次元Figure 1．Appearance based methods are tolerant to various
shape representation. This algorithm is also invariant toarticulation, by using bag-of-local visual features [5].

[5] R. Ohbuchi, K. Osada, T. Furuya, T. Banno, Salient local
visual features for shape-based 3D model retrieval, Proc.
IEEE Shape Modeling International (SMI) 2008,
pp. 93-102, (2008).
[6] M. Pauly, N. J. Mitra, J. Giesen, L. Guibas, M. Gross,Example-based 3D Scan Completion, Proc. 3rd
Eurographics Symposium on Geometry Processing (SGP)2005, Article No. 23, (2005).
[7] SHREC Home Page, R.C. Veltkamp,
http://www.aimatshape.net/event/SHREC

etal.,[8] J.W.H. Tangelder, R.C. Veltkamp, A survey of content
based 3D shape retrieval methods, Multimedia Tools andApplications, 39, pp. 441-471, (2008).