形状特徴に基づく web 上の 3 次元オブジェクトの効率的検索手法の提案
石 川古 川雅浩†亮††

鈴 木 崇 之††† 下
河 合 由 起 子††† 川野崎博†††洋†

近年，3 次元オブジェクトの利用は増加の一途にあり，CG 映画やゲームなど様々な状況で用いられている．一方，実物体の 3 次元形状取得方法も大幅な進歩を遂げており，様々なスキャン手法が開発されている．その結果，これら 3 次元オブジェクトを web 上にアップする機会が今後大幅に増加すると考えられる．しかし，web 上に多数公開された 3 次元オブジェクトを検索する手法についてはこれまであまり検討されていない．そこで本論文では，近い将来実物体をスキャンした 3 次元オブジェクトが web 上に大量に公開されることを想定した，web3 次元オブジェクトの効率的な検索手法を提案する．

Shape Re-ranking technique for Web3D object based on 3D features
Masahiro Ishikawa,† Takayuki Suzuki,††† Hiroshi Shimono,†††Ryo Furukawa,†† Yukiko Kawai††† and Hiroshi Kawasaki†
In recent years, usage of 3D object for various purposes, such as CG movie, games andso on, are rapidly increasing. In addition, 3D shape capturing method is also improved andseveral commercial products are now widely available. As a result, a number of 3D objects
those are uploaded and published on the Web will increase greatly in the near future. On
the other hand, the method for retrieving the 3D object from the Web is not thoroughly
researched yet. In this paper, we propose an eﬃcient method to retrieve a 3D object fromthe Web using both 3D feature of the 3D objects and ranking results of web search.

1. は じ め に2006 年からはコンテスト (SHREC) が開催され認識精度が競い合われている．しかし，これらの手法は基近年，プロジェクタやカメラなどを組み合わせる

本的には物体の全周形状が完全に獲得されることを前ことで簡易に物体の 3 次元形状を計測する手法が数多提としており，実環境において，3 次元スキャナなどく提案され，誰もが容易に高精度な 3 次元形状を取得

により 1 視点からのみ得られた形状については十分にできるようになりつつある．さらに，3D コンテンツ考えられていない．一方で，実物体を計測した 3 次元を web 上に公開する方法も提案されている1) ．これに形状については SpinImage2) や CCHLAC3) (カラー伴い，web 上に公開された多くの 3 次元形状を検索

立体高次局所自己相関) を用いた認識法が提案されてする仕組みが必要になると考えられる．そこで本論文いるが，基本的には同一の物体を認識する手法のため，では，web 上にある 3 次元オブジェクトを高精度に検web に不特定多数アップされた 3 次元オブジェクトの索する手法を提案する．3 次元オブジェクトを検索す検索にそのまま利用することはできない．

るためには，3 次元オブジェクトの分類や認識が一般

近年，高精度な画像検索法として Visual Rank が提に必要と考えられる．例えば，3 次元オブジェクトの案されている4) ．これは，Google の検索エンジンで認識に関しては，これまで CAD やモデリングソフトも採用されている Page Rank の 2 次元への拡張であで作成された CG を対象として盛んに行われており，る．Page Rank は，「多くの良質なページからリンクされているページは，良質なページである」という考† 埼玉大学
Saitama University†† 広島市立大学
Hiroshima City University††† 京都産業大学
Kyoto Sangyo University

えに基づいて設計されているが，VisualRank も「良い画像は多くの画像と強く結びつき合っている」という仮説に基づいている．最大の特徴は画像特徴を検索基準に採用した点であり，従来のキーワード入力型画像検索エンジンよりも高精度な検索結果が得られる．

情報処理学会 インタラクション 2010

そこで本研究では，Visual Rank の 3 次元オブジェク

は，シンプルな方法としては距離値を用いた手法5) やト検索への拡張を目的として Shape Rank を提案す

pixel depth を用いる手法などが提案されている．本る．本手法では，3 次元オブジェクトを入力とした一研究では，視点依存性を避けるため不変特徴量として般物体認識を目指すのではなく，3 次元オブジェクト良く使われる曲率を用いる．

が web 上に数多く普及した状況においてユーザに高3.1 主 曲 率

精度な検索結果を提示することを目的とする．具体的

3 次元形状の曲率を計算する場合，主曲率を計算には以下の条件下での検索を前提とする．まず，従来する．主曲率は，いくつかの計算方法が考えられるがの画像検索同様にキーワード検索によって 3 次元オ

本研究では 2 次曲面当てはめによって求めることとしブジェクトを絞り込めるとする．これは，3 次元オブた．当てはめる 2 次曲面を，式 1 のような 2 次多項

ジェクトが普及し web 上に公開される際にも画像情式で表す．

報同様に文字情報が記載される可能性が高いと考えられることから妥当と考えられる．次に，キーワード検h(x, y) = a1 +a2 x+a3 y+a4 x2 +a5 xy+a6 y 2 (1)
この時 a は 2 次曲面を定めるパラメータである. 最索によって得られる 3 次元オブジェクトの検索精度は適な a は式 2 によって求まる.

画像検索と同程度の精度とする．これについても，前a = (XT WX)−1 XT h

述の条件を満たしていれば 3 次元オブジェクトの内容に関係無くテキストデータから求められるため妥当と(2)

この時,a,h,X は, それぞれ式 3, 式 4, 式 5 のようになる.

考えられる．最後に，対象は全周形状に限らない．こa = (a1 ,…, a1 )T(3)

れは，計測システムが普及し web 上に実環境の 3 次

T(4)

h = (h1 ,…, h6 )元オブジェクトが広まった場合，1 視点の形状のみで公開されるケースも十分に考えられるためである．

1x1

y1

x21

x1 y1y12X =  ...

...

...

...

...

. . .  (5)

1xN

yN

x2NxN yN

2. 提 案 手 法

2yN

この時,h は距離値ベクトルになる. 係数ベクトル aから 1 次と 2 次の偏微分を求めることができる．以上
を用いて，最大曲率と最小曲率を求めることができる．

3.2 shape index
主曲率を形状情報として扱う場合，ガウス曲率と平均曲率を用いて領域分割する手法や平均曲率が 0 であるような曲面を用いる手法など様々な扱い方が考えられる．本研究では，曲面変化の凹凸情報を強調した画像を用いることを目的として shape index 値を用い
図 1 本手法の概略

本論文では，通常の Visual Rank に形状特徴抽出と類似度計算処理に修正を加えた図 1 のような手法を提案する．まず，3 次元オブジェクトをキーワードることとした．Shape index 値は距離画像上の各ピクセルにおいて式 6 を用いて求めることができる．

SI =kmax (i) + kmin (i)11− ∗ arctan
2πkmax (i) − kmin (i)(6)

検索によって検索する．次に，3 次元オブジェクトか

ここで，kmax は最大曲率，kmin は最小曲率であら形状特徴を抽出 (3 章) し，各 3 次元オブジェクトる．この時，Shape index 値は [0，1] の範囲で求まる．

間の類似度計算を行う．最後に，3 次元オブジェクト

本研究では，Shape Rank として扱いやすいよう [0，の Shape Rank(4 章) を計算する．Shape Rank とは，255] に正規化し，グレースケール画像に変換する．

Visual Rank の 3 次元オブジェクトへの拡張であり，3 次元オブジェクトを扱うため，形状特徴を用いて視点依存性などを解消した手法となっている．

3. 形状特徴量抽出

3.3 視点依存性の解消
Shape Rank の計算において最も問題となるのが，3 次元オブジェクトどうしの類似度を計算するための特徴量の記述方法である．本論文では，Shape indexが不変 3 次元特徴量であることから，これを 2 次元的類似度計算を行うためには，各 3 次元オブジェに配置した Shape index 画像を作成し，この Shapeクトの形状特徴量を抽出する必要がある．形状特徴量

Index 画像に対して SIFT を適用し特徴抽出を行うも形状特徴に基づく web 上の 3 次元オブジェクトの効率的検索手法の提案のとする．ただし，Shape Index 自体は不変特徴量でオブジェクトと距離画像の分類を必要とせずに類似度はあるものの，Shape index 画像は，視点変化の影響計算が可能となる．

を受けてしまうため，Shape Rank の計算においてはこれを解決する必要がある．そこで本研究では，図 2のように正二十面対の頂点全てからの Shape index 画像を生成し，これを用いることで，視点依存性のないSIFT 記述子を獲得する．ただし，対象の 3 次元オブ4.2 ランキング計算
隣接行列 M が求まれば，式 8 を用いてランキングが収束するまで計算を繰り返す．
′r = (1 − α)M r + αP(8)ジェクトが単視点の場合 (距離画像) の場合は，処理

これは，PageRank と同じ方法で，P は直接のつの簡便さのため単視点の Shape index 画像 1 枚のみながりが無いケースを反映するためである．従って，を用いることとした．これは，3 次元オブジェクトがα はランキングベクトル r と P の重み付けである．

単視点から計測されている場合，その形状は全体の一部分でしかなく，視点を少し変化させるだけで，その形状のほとんどが観測されなくなり，特徴点も非常に少ししか抽出されないためである．

5. 実験と結果
5.1 実 験 環 境
実験には，プロジェクタ・カメラシステムによるレンジセンサを用いることとした．全周形状は，複数方向から対象オブジェクトを計測し，位置合わせ，形状統合を行い，3 次元形状を獲得する．計測した例を
図 3 に示す。

図 2 正二十面体の頂点

4. Shape Rank

アヒルの玩具

ShapeRank は基本的には PageRank と同様の構造をしており，ハイパーリンクの代わりに各形状間の土偶

埴輪

ダルマ

花瓶

図 3 計測結果

5.2 実計測データを用いたランキング実験類似度を定義する．これによって，キーワード検索にShapeRank の動作確認として，同一オブジェクよって求まった形状ランキングの修正を行う．形状間トの全周形状と様々な視点から撮影した距離画像群との類似度がより高いものが上位にランキングされるたノイズオブジェクトを用いてランキング計算を行った．

め，キーワード検索によって集まった形状群の代表的正しい検索結果として想定する 3D オブジェクトは図な形状が上位に表示されることになる．これは，基本4 左のような石膏像とする．全周形状は，図 4 右のよ

的には Visual Rank と同様のアプローチである．

うに各スキャンデータを統合した 3D オブジェクトを4.1 類似度の計算用いた．SIFT 特徴量の計算は，各距離画像群に関しShape Rank を計算するには，類似度を要素とては，計測時のカメラの視線方向から計算した (全 14する隣接行列 M が必要である．隣接行列の類似度 を方向)．全周形状に関しては，正二十面対の各頂点かSIFT を用いて画像間の対応点数を計算し，式 7 のよら計算した SIFT 特徴量を合わせたものとなる．このうに定義する．

ため，各視点から得られる ShapeIndex の SIFT 特徴Mij
Cij =(Ti + Tj )/2(7)

ここで，Mij は各画像間の対応点数，Ti ，Tj は各画像の SIFT キーポイントの数である．正二十面体量と，全周形状の SIFT 特徴量は完全には一致しない．
用いた 3 次元オブジェクトの No．1-14 が個々の距離画像であり，No．15 が全周囲形状であり，No16-20が，関連のないノイズオブジェクトである．の頂点を用いることで，均一な視点からの SIFT 記述

提案手法によるランキング結果を図 5 に示す．また，子を獲得することができる．全周形状に対して獲得し上位にランキングされたオブジェクトを図 6 に示す．

た SIFT 記述子は全て保持し，他のオブジェクトと比図 5 から，石膏像の全周囲形状がノイズに影響されず較する際は，最も SIFT 対応点の多かった視点を採用に 1 位にランクインしていることが分かる．また，ラすることとした。従って，式 7 で比較する際には全周ンキング結果の上位には図 6 に示したとおり石膏像と情報処理学会 インタラクション 2010

図 4 石膏像と統合結果

類似性の高い距離画像がランクインしていることが確認できる．しかし，6 位にアヒルの玩具を計測した全周形状がランクインされた．これは，全周形状の場合最も対応点数の多かった視点を SIFT 記述子として採用するため，無関係のオブジェクト間においても誤接続が発生したことが原因と考えられる．

図 7 類似度を辺重みとする重み付きグラフ

ら見た Shape Index 画像を用いることで，視点依存性のない特徴抽出を実現する手法となっている．今後の課題として，オブジェクト群と関連の無い全周形状がランキングの上位に入ってしまう点の改善がある．
謝辞 本研究の一部は，総務省戦略的情報通信研究開発制度 (SCOPE) 若手 ICT(072103013) の一環として実施されたものである．ここに記して謝意を表す．

参 考
図 5 ランキング結果

図6

ランキング上位オブジェクト

5.3 オブジェクト間の類似度考察
各オブジェクト間の類似度を辺重みとする重み付きグラフを図 7 に示す．図 7 を見ると，石膏像の全周形状が石膏像の距離画像と類似性が高くなっていることが確認できる．ノイズとしてあたえた No.19 の円柱状の資材に類似度が求まっているが，他の距離画像に比べて低いことも確認できる．しかし，一部の石膏像の距離画像と類似度が求まっておらず，計算した 12 視点の全周形状と視点が離れており，SIFT による角度変化の吸収が十分でなかったものと思われる．アヒルの全周形状については，石膏像の全周形状と距離画像に類似度が求まっており，このためリランキング結果の上位に入ってしまったものと考えられる．

6. まとめと今後の課題
本研究では，web 上に公開された多数の 3 次元オブジェクトの高精度な検索手法として，形状特徴を用いた Shape Rank を提案し，実験によりその有効性を確認した．Shape Rank とは，Page Rank を 3 次元形状へと拡張したものであり，正二十面体の各頂点か

文献1) 加納 利英, 川嶋 紀弘, 田澤 翔吾, 成田 直樹, 河合 由起子, 川崎 洋 ”ユーザの選好に基づく 3D コ
ンテンツの情報推薦と視点に依存した提示手法”,
インタラクティション 2008, 3.2008.
2) A.E.Johnson and M.Hebert, Using spin images for eﬃcient object recognition in cluttered
3D scenes , IEEE Trans. Pattern Anal. And
Mach. Intell.,21,pp.433-449,1999.
3) A. Kanezaki, T. Harada and Y. Kuniyoshi,”Partial Matching for Real Textured 3D Objects using Color Cubic Higher-order Local Auto-Correlation Features”,Eurographics
Workshop on 3D Object Retrieval 2009, pp.9–12, 2009.
4) Y. Jing, and S. Baluja, Visual Rank: Applying Page Rank to large-scale image search
IEEE Transaction on Pattern Analysis and Machine Intelligence, vol.30, no.11, pp.1877-1890,Nov.2008.
5) Ryutarou Ohbuchi, Kunio Osada, TakahikoFuruya, Tomohisa Banno, ”Salient local visual featuers for shape-based 3D model retrieval” Proc. IEEE Shape Modeling International (SMI), pp 93-102 ,2008.