TOP > 国内特許検索 > 三次元モデルの検索方法、コンピュータプログラム及び三次元モデルの検索システム > 明細書

明細書 :三次元モデルの検索方法、コンピュータプログラム及び三次元モデルの検索システム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5024767号 (P5024767)
登録日 平成24年6月29日(2012.6.29)
発行日 平成24年9月12日(2012.9.12)
発明の名称または考案の名称 三次元モデルの検索方法、コンピュータプログラム及び三次元モデルの検索システム
国際特許分類 G06T  15/08        (2011.01)
G06T  19/00        (2011.01)
FI G06T 15/08
G06T 19/00 A
請求項の数または発明の数 8
全頁数 21
出願番号 特願2008-543134 (P2008-543134)
出願日 平成19年11月9日(2007.11.9)
国際出願番号 PCT/JP2007/071765
国際公開番号 WO2008/056757
国際公開日 平成20年5月15日(2008.5.15)
優先権出願番号 2006305546
優先日 平成18年11月10日(2006.11.10)
優先権主張国 日本国(JP)
審査請求日 平成22年11月8日(2010.11.8)
特許権者または実用新案権者 【識別番号】304027349
【氏名又は名称】国立大学法人豊橋技術科学大学
発明者または考案者 【氏名】青野 雅樹
【氏名】関 洋平
【氏名】立間 淳司
個別代理人の代理人 【識別番号】100095577、【弁理士】、【氏名又は名称】小西 富雅
審査官 【審査官】伊知地 和之
参考文献・文献 特開2002-288687(JP,A)
特開2001-155026(JP,A)
特開2005-084717(JP,A)
特開2005-071095(JP,A)
特開2004-164503(JP,A)
特開2001-155019(JP,A)
特開2000-222428(JP,A)
高野 陽子 外1名,“カメラ画像で検索する3次元形状モデルデータベース”,Visual Computing グラフィクスとCAD 合同シンポジウム2005 予稿集,日本,2005年 6月16日,p.69-74
岩崎 圭介 外2名,“3次元多重空間フィルタリングに基づく部分形状の同定”,電子情報通信学会技術研究報告 Vol.92 No.104 PRU92-18~24 パターン認識・理解,日本,社団法人電子情報通信学会,1992年 6月19日,第92巻,第104号,p.45-51
調査した分野 G06T 15/00 - 19/20
G06F 17/30
G06T 7/00 - 7/60
CSDB(日本国特許庁)
特許請求の範囲 【請求項1】
補正部、フーリエ変換部、特徴量演算部及び特徴量比較部並びに制御装置を備えるコンピュータを用い、正対化処理された検索対象の三次元モデルに類似する既知三次元モデルを検索する三次元モデルの検索方法であって、
前記補正部により、前記検索対象の三次元モデルの特徴量(輪郭特徴量を除く)演算に用いられる二次元画像を、該二次元画像の中心から離れるにしたがって画素の濃淡が強調されるように補正するステップと、
前記フーリエ変換部により、前記補正された二次元画像をフーリエ変換するステップと、
前記特徴量演算部により、フーリエ変換の結果から特徴量を演算するステップと、
前記特徴量比較部により、得られた特徴量を前記既知三次元モデルの特徴量と比較するステップとを備える、ことを特徴とする三次元モデルの検索方法。
【請求項2】
前記二次元画像はデプスバッファ (DepthBuffer)画像若しくはシルエット画像であり、前記補正するステップでは前記二次元画像の中心からの距離をrとしたとき、補正後の二次元画像における各座標の輝度I´(x,y)を下記式で表すものとする、ことを特徴とする請求項1に記載の三次元モデルの検索方法、
r=((Kx-x)+(Ky-y)1/2
I´(x,y) = r * I(x,y)
ここに、Kx、Kyはそれぞれ補正前の二次元画像のx軸方向の中心座標、y軸方向の中心座標であり、I(x,y)は補正前の二次元画像における各座標の輝度を示す。
【請求項3】
前記コンピュータは輪郭画像用二次元画像形成部及び第2のフーリエ変換部、並びにボクセル用二次元画像形成部及び第3のフーリエ変換部を更に備え、
前記補正部によりデプスバッファ画像を請求項2に記載の方法で補正して得た第1の補正二次元画像と、前記補正部によりシルエット画像を請求項2に記載の方法で補正して得た第2の補正二次元画像とを前記フーリエ変換部でフーリエ変化し
前記輪郭画像用二次元画像形成部により形成されて輪郭特徴量の演算に用いられる第3の二次元画像を前記第2のフーリエ変換部でフーリエ変換し、
前記ボクセル用二次元画像形成部により形成されてボクセル特徴量の演算に用いられるボクセル格子をそれぞれ前記第3のフーリエ変換部でフーリエ変換し前記特徴量演算部は前記各フーリエ変換の結果から特徴量を演算し、得られた特徴量を複合することを特徴とする請求項2に記載の三次元モデルの検索方法。
【請求項4】
前記コンピュータは正対化処理部を更に備え、該正対処化理部は三次元モデルにつき複数の正対化処理を行ない、各正対化処理後の三次元モデルにつき請求項1~3のいずれかに記載の方法を実行する、ことを特徴とする三次元モデルの検索方法。
【請求項5】
前記正対化処理は前記三次元モデルを構成する三角面上にランダムな点を生成し、それを質点として主成分分析を行ない、主軸を求めて正規化を行なう第1の正対化処理方法と、前記三次元モデルの面上に生成したランダムな点と、それに近い三角形の2点との法線の分布をもとに主軸を求めて正規化を行なう第2の正対化処理方法とを含む、ことを特徴とする請求項4に記載の三次元モデルの検索方法。
【請求項6】
前記制御装置を用いて前記既知3次元モデルのデータベースをスペクトルクラスタリングにより、予めクラスタリングしておく、ことを特徴とする請求項1~5のいずれかに記載の三次元モデルの検索方法。
【請求項7】
請求項1に記載の方法をコンピュータに実行させるコンピュータプログラム。
【請求項8】
正対化処理された検索対象の三次元モデルに類似する既知三次元モデルを検索する三次元モデルの類似検索システムであって、
前記検索対象の三次元モデルの特徴量(輪郭特徴量を除く)演算に用いられる二次元画像を、該二次元画像の中心から離れるにしたがって画素の濃淡が強調されるように補正する手段と、
前記補正された二次元画像をフーリエ変換する手段と、
フーリエ変換の結果から特徴量を演算する手段と、
得られた特徴量を前記既知三次元モデルの特徴量と比較する手段とを備える、ことを特徴とする三次元モデルの検索システム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、三次元モデルの検索方法、コンピュータプログラム及び三次元モデルの検索システムに関するものである。
【背景技術】
【0002】
三次元モデルの検索方法として各種の方法が知られている。
D2 : D2はOsadaらの研究(非特許文献1)で最も高い検索精度を得た特徴量である。三次元モデルの面上にランダムな点群を生成し、全2点間のユークリッド距離の頻度を示すヒストグラムを特徴量とする。特徴量間の距離は、求めたヒストグラムを一次元ベクトルと考えて計算したマンハッタン距離である。
Spherical Harmonics Descriptor(SHD) : SHDはKazdanらにより提案された手法である(非特許文献2)。ボクセル化した三次元モデルを球面調和関数変換し、得られたパワースペクトルの低周波部分を特徴量とする。特徴量間の距離は、求めたパワースペクトルを1次元ベクトルと考えて計算したユークリッド距離である。
Light Field Descriptor(LFD) : LFDはChenらにより提案された手法である(非特許文献3参照)。12面体の頂点を視点とし、それを回転させながら、多数の視点から三次元モデルのシルエット画像を生成する。生成したシルエット画像のツェルニケモーメントとフーリエスペクトルを計算し特徴量とする。特徴量間の距離は、12面体の各頂点と全ての回転における組み合わせで最小L1距離を計算したものである。
Hybrid Descriptor(DSR472):DSR472はVranicの研究で最も高い検索精度を得た特徴量である(非特許文献4参照)。Vranicが考案した、デプスバッファ特徴ベクトル、シルエット特徴ベクトル、重心から任意の方向にベクトルを放つことで得られるRay特徴ベクトルの3つを組み合わせた特徴量である。特徴量間の距離は、複合特徴量を一次元ベクトルと考えてマンハッタン距離を計算したものである.

【非特許文献1】R.Osada, T.Funkhouser, B.Chazelle, D.Dobkin, Shape Distributions, ACM,TOG,21(4),pp.807-832,2002.
【非特許文献2】M.Kazhdan, T.Funkhouser, S.Rusinkiewicz, Rotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors, Proc.Eurographics, ACM SIGGRAPH Symp.on Geometry Processing,pp.156-164,2003.
【非特許文献3】D.-Y.Chen, X.-P.Tian, Y.-T.Shen, M.Ouhyoung, On Visual Similarity Based 3D Model Retrieval, Computer Graphics Forum,22(3),pp.223-232,2003.
【非特許文献4】D.Vranic, 3D Model Retrieval, Ph.D.thesis, University of Leipzig,2004.
【発明の開示】
【発明が解決しようとする課題】
【0003】
発明者らは現在最も検索精度が高いといわれるDSR472法を凌駕する新規な検索方法を得るべく鋭意検討を重ねてきた。その結果、実施例レベルでDSR472法の検索精度を上まわる検索精度得ることができた。かかる高い検索精度を得るには、特徴量の演算段階において、三次元モデルの特徴量(輪郭特徴量を除く)演算に用いられる二次元画像を、該二次元画像の中心から離れるにしたがって画素の濃淡が強調されるように補正する必要があることに気づき、本発明を完成するに至った。
即ち、正対化処理された検索対象の三次元モデルに類似する既知三次元モデルを検索する三次元モデルの検索方法であって、
前記検索対象の三次元モデルの特徴量(輪郭特徴量を除く)演算に用いられる二次元画像を、該二次元画像の中心から離れるにしたがって画素の濃淡が強調されるように補正するステップと、
前記補正された二次元画像をフーリエ変換するステップと、
フーリエ変換の結果から特徴量を演算するステップと、
得られた特徴量を前記既知三次元モデルの特徴量と比較するステップとを備える、ことを特徴とする三次元モデルの検索方法。
【図面の簡単な説明】
【0004】
【図1】この発明の実施例の検索システムを示すブロック図である。
【図2】ポイントSVDにおける鏡像が異なる例を示す図である。
【図3】ノーマルSVDにおける演算原理を示す図である。
【図4】デプスバッファ画像の例を示す図である。
【図5】周辺輝度強調により補正されたデプスバッファ画像(PEI画像)の例を示す図である。
【図6】周辺輝度強調により補正されたデプスバッファ画像を極座標変換した画像である。
【図7】シルエット画像の例を示す図である。
【図8】輪郭画像の例を示す図である。
【図9】ボクセルの例を示す図である。
【図10】実施例の検索方法と従来例の検索方法との検索性能を比較したグラフである。
【図11】同じく実施例の検索方法と従来例の検索方法との検索性能を比較したグラフである。
【図12】一般的なスペクトルクラスタリングの手法説明図である。
【図13】この実施例のスペクトルクラスタリングの手法説明図である。
【図14】スペクトルクラスタリングを施したときの検索精度を示すグラフである。
【図15】データベースをPSBとしたときの実施例の検索方法と従来例の検索方法との検索性能を比較したグラフである。
【図16】データベースをESBとしたときの実施例の検索方法と従来例の検索方法との検索性能を比較したグラフである。
【図17】データベースをSHREC2007としたときの実施例の検索方法と従来例の検索方法との検索性能を比較したグラフである。
【符号の説明】
【0005】
1 三次元モデルの検索システム、10 記憶部、 20 入出力装置、30 正対化処理部、40 特徴量演算部、50 特徴量比較部
【0006】
このように規定される第1の局面の発明によれば、三次元モデルの特徴量(輪郭特徴量を除く)演算に用いられる二次元画像を、該二次元画像の中心から離れるにしたがって画素の濃淡が強調されるように補正するので、補正された二次元画像では三次元モデルの外郭の特徴が強調される。その結果、類似検索の検索精度が向上する。
【0007】
三次元モデルの検索方法は、三次元モデルを正対化する正対化ステップと、正対化された三次元モデルの特徴量を演算する特徴量演算ステップと、計算された特徴量をデータベース化されている既知三次元モデルの特徴量と比較する比較ステップとを経る。
なお、既知三次元モデルの特徴量も、検索対象となる三次元モデルに対して行なったと同様の正対化ステップ及び特徴量演算ステップとを経て得られたものである。
【0008】
この発明の第1の局面は、上記特徴量演算ステップにおいて、三次元モデルの特徴量を得る際に用いられる周知の二次元画像を補正するものである。
ここに三次元モデルの特徴量演算用の二次元画像の例としてデプスバッファ(DepthBuffer)画像若しくはシルエット画像を挙げることができる。
ここでのデプスバッファ画像とは、三次元モデルに、視点方向から平行な光源を照射して得られる、表面までの距離(深さ)で濃淡が変化する二次元の濃淡画像で表したものである。
シルエット画像は、三次元モデルに光を当ててできた影を二次元の2値画像で表したものである。
その中心から離れるしたがって画素の濃淡が強調されるように二次元画像を補正する方法は任意に設定可能であるが、この発明の第2の局面によれば、次の方法が採用される。即ち、二次元画像の中心からの距離をrとしたとき、補正後の二次元画像における各座標の輝度I´(x,y)を下記式で表すものとする、
r=((Kx-x)+(Ky-y)1/2
I´(x,y) = r * I(x,y)
ここに、Kx、Kyはそれぞれ補正前の二次元画像のx軸方向の中心座標、y軸方向の中心座標であり、I(x,y)は補正前の二次元画像における各座標の輝度を示す。
このような補正を実行することにより、二次元画像の中心から離れるにしたがって画素の濃淡が強調されるとともに該中心へ近づくにつれて画素の値が小さく(暗く)なる。
【0009】
補正された二次元画像は直交座標から極座標へと変換され、二次元フーリエ変換されてパワースペクトルが得られる。このうちパワースペクトルの低周波成分のみを取出す。低周波成分のみを取出すのは、類似検索の場合、形状の微細な相違を表す高周波成分はノイズとして無視できると考えたからである。
パワースペクトルにおいて取り出された低周波成分に関しては、これを更にM個の低周波成分に分割する。次に、M個各々の絶対値からなる低周波成分値を要素とするベクトルを作成し、このベクトルを特徴量とする。
【0010】
複数の特徴量を用いて検索を行なう場合は、各特徴量を正規化し、それぞれへ重み付けをして複合する。重み付けの方法は任意に選択することができる。後述の実施例ではクラス分けされたデータベースがあるので、Purity法を用いて重み付けをしている。
【0011】
三次元モデルの位置、大きさ、向きは製作者により任意である。同じ形状の三次元モデルでも、位置、大きさ、向きが多少異なるだけでも、データの中身が大きく異なる。特徴量演算では、類似した形状の三次元モデルからは類似した特徴量が求まることが望ましい。そこで、特徴量演算を行なう前に三次元モデルの正対化処理を行なう。
この発明の他の局面では、複数の正対化処理を行なった三次元モデルに対して特徴量演算を行なうことを提案する。
また、新規な正対化方法として、三次元モデルを構成する三角面上にランダムな点を生成し、それを質点として主成分分析を行ない、主軸を求めて正規化を行なう第1の正対化処理方法と、三次元モデルの面上に生成したランダムな点と、それに近い三角形の2点との法線ベクトルの分布をもとに主軸を求めて正規化を行なう第2の正対化処理方法とを提案する。
【実施例】
【0012】
以下、この発明の実施例について説明をする。
図1は実施例の検索システム1の構成を示すブロック図である。
実施例の検索システム1は汎用的なコンピュータ装置からなり、その機能をブロックで表すと図1のようになる。即ち、実施例の検索システム1は制御装置3、記憶部10、入出力部20、正対化処理部30、特徴量演算部40及び特徴量比較部50から構成される。
【0013】
制御装置3は記憶部10のプログラム記憶部11から制御用プログラムを読み出して、このプログラムにしたがって各要素を制御する。
記憶部10の既知三次元モデルの特徴量データベース13には、以下に説明する方法で特徴量の演算された三次元モデルがその特徴量とともに保存されている。三次元モデルは正対化され、かつ正規化されている。
ポイントSVD(Point SVD)化データ記憶部15は、検索対象(検索クエリ)となる三次元モデルにつきポイントSVDにより正対化し、さらに正規化処理された三次元モデルのデータが一時的に保存される。ノーマルSVD(Normal SVD)化データ記憶部17は、検索対象(検索クエリ)となる三次元モデルにつきノーマルSVDにより正対化し、さらに正規化処理された三次元モデルのデータが一時的に保存される。
【0014】
入出力部20はキーボード/マウス21、ディスプレイ23、プリンタ25、データ入出力インターフェース27及び通信インターフェース29を備えている。検索対象である三次元モデルはデータ入出力インターフェース27からシステム内に取むことができる。
通信インターフェース29はシステムをインターネットへ連結する。
【0015】
正対化処理部30は、検索対象である三次元モデルを正対化処理し、更に大きさをそろえるために正規化する。
正対化処理部30にはポイントSVD部31とノーマルSVD部33があり、それぞれ異なる手法で三次元モデルを正対化処理する。正規化部35は三次元モデルの大きさの任意性を解決するものである。
ポイントSVD部31で正対化されかつ正規化部35で正規化された三次元モデルのデータは記憶部10のポイントSVD化データ記憶部15に保存され、ノーマルSVD部33で正対化されかつ正規化部35で正規化された三次元モデルのデータは記憶部10のノーマルSVD化データ記憶部17に保存される。
【0016】
以下、ポイントSVDについて詳細に説明する。
ポイントSVDでは、三次元モデルを構成する三角面上にランダムな点を生成する。これには、Osadaらの手法を用いる(R.Osada, T.Funkhouser, B.Chazelle, D.Dobkin, Shape Distributions, ACM,TOG,21(4),pp.807-832,2002.)。生成する点の座標を、三角面の頂点の座標ABCと擬似乱数r1、r2を用いて、下記式1で決める。
【数1】
JP0005024767B2_000002t.gif
本実施例では擬似乱数にメルセンヌTwister乱数を用いた。また、生成する点群数は全体でM個とする。実施例ではM=32768個である。こうして生成された点群より三次元モデルの重心を求める。重心mが原点となるよう平行移動することで、位置の任意性の問題を解決する。実施例での点群データ行列は以下の式で表現される。
【数2】
JP0005024767B2_000003t.gif
次に、点群行列Pを特異値分解することで回転行列Rを得る。
【数3】
JP0005024767B2_000004t.gif

【0017】
最後に、三次元モデルの鏡像を決める。軸が同じになっても、鏡像が異なれば特徴量は変化してしまう(図2参照)。
回転行列Rにより、点群を回転させる。
【数4】
JP0005024767B2_000005t.gif
モデルの鏡像行列Fは、M=32768個の実施例での点群の場合、以下のように計算する。
【数5】
JP0005024767B2_000006t.gif
以上の計算により求めた重心m、回転行列R、鏡像行列Fにより、モデル頂点Vを平行移動・回転させて正対を完成する。
【数6】
JP0005024767B2_000007t.gif

【0018】
ポイントSVDと同様の正対手法がOhbuchiらにより提案されている(R.Ohbuchi, T.Otagiri, M.Ibato, T.Takei, Shape-Similarity Search of Three-Dimensional Models Using Parameterized Statistics. Proc.Pacific Graphics 2002,pp.265-274.2002)。違いは、点群生成時に準乱数のSobol乱数を用いることと、鏡像の決定に中心からの距離を用いていることである。
【0019】
次に、ノーマルSVDについて詳細に説明する。
基本的な計算方法はポイントSVDと同様である。ノーマルSVDでは点群を生成するときに、生成した点と元になった三角形の頂点の最も近い2点との法線を質点として計算する(図3)
まず、法線ベクトルnの平均を求める。M=32768個の実施例での法線ベクトルの平均は以下のように求める。
【数7】
JP0005024767B2_000008t.gif
次に法線ベクトル行列Nを特異値分解し、回転行列Rを求める。
【数8】
JP0005024767B2_000009t.gif

【0020】
最後に、回転させた点群を元に、ポイントSVDと同様にして鏡像決定行列Fを計算する。
【数9】
JP0005024767B2_000010t.gif
以上により、正対は完了する。頂点行列Vの定義はポイントSVDと同様である。
【0021】
このようにして正対された各モデルはBounding Sphere法により正規化される。
ここに、Bounding Sphere法は、半径1の単位球であり、これに正対化された検索対象の三次元モデルが収まるようにする。具体的な計算方法としては、三次元モデルの全頂点と中心との距離の最大値で各頂点の座標を割る。
【0022】
特徴量演算部40は、デプスバッファ特徴量演算部41、シルエット画像特徴量演算部42、輪郭画特徴量演算部43、ボクセル特徴量演算部44、類似度演算部45及び複合部47を備えてなる。
デプスバッファ特徴量演算部41の二次元画像形成部411は、ノーマルSVD化データ記憶部15及びポイントSVD化データ記憶部17に記憶されている三次元モデルのデータを読出し、デプスバッファ特徴量の演算に用いる二次元画像(ディプスバッファ画像)を形成する。ここに、デプスバッファ画像は、任意の視点から三次元モデルの表面までの距離(深さ)を二次元画像で表したものである。
実施例では、三次元モデルの直交6方向からの視点で256×256の画素をもつデプスバッファ画像を形成する(図4参照)。
デプスバッファ画像が持つz値(深さ)は[0,255]の整数を取り、距離が遠いほど値は小さく、近いほど値は大きい。また、背景は0である。
【0023】
次に補正部413は、デプスバッファ画像に中心からの距離情報を埋め込むことにより、これを補正する。具体的には、デプスバッファ画像の各画素の輝度をI(x、y)としたとき、デプスバッファ画像の中心からの距離をrとすると、画素サイズを256×256とした実施例の場合、補正された画像の各座標の輝度I´(x,y)は次のように表される。
【数10】
JP0005024767B2_000011t.gif
補正された画像を周辺強調画像(Periphery Enhanced Image (PEI))とよぶことがある。
補正された画像を図5に示す。
図5及び式9より、補正された二次元画像は画像の中心から離れるしがたって画素の濃淡が強調されていることがわかる。また、画像の中心に近づくにしたがって画素が暗くなることもわかる。
最後に、補正されたデプスバッファ画像を直交座標から極座標へと変換する。極座標変換した画像を図6に示す。極座標は、横軸がr、縦軸が回転角θを表す。画像の大きさは、実施例の場合、128×512となる。
【0024】
次にフーリエ変換部415が極座標変換した画像をフーリエ変換し、フーリエ係数gρφを得る。
【数11】
JP0005024767B2_000012t.gif
ここに、ρは横軸の空間周波数、φは縦軸の空間周波数を表し、0≦ρ<128、0≦φ<512である。このフーリエ係数の大きさがパワースペクトルである。極座標では、直交座標における回転が平行移動となり、フーリエ変換により得られるパワースペクトルは平行移動不変の性質を持つ。正対に誤りがある場合に、向きの任意性を若干緩和できる。
以上の処理により得られた、6画像分のパワースペクトルの低周波成分のみ取出したものをデプスバッファ特徴量fDepth Buffer とする。
【数12】
JP0005024767B2_000013t.gif
低周波成分のみを特徴量として使用するのは、類似検索の場合、形状の微細な相違を表す高周波成分を無視するためである。
【0025】
シルエット画像特徴量演算部42の二次元画像形成部421はノーマルSVD化データ記憶部15及びポイントSVD化データ記憶部17に記憶されている三次元モデルのデータを読出し、シルエット画像特徴量の演算に用いる二次元画像(シルエット画像)を形成する。ここに、シルエット画像は、三次元モデルに光を当ててできた影を二次元の2値画像で表したものである。背景を0、影の部分を255の整数で表す(図7)。この実施例では、三次元モデルの直交3方向からの視点でシルエット画像を生成する。
次に補正部423が、デプスバッファ特徴量演算部41の補正部413と同様にして、シルエット画像を補整し、周辺強調画像を生成する。この時点で2値であったシルエット画像は補正により多値の濃淡画像となる。補正された多値のシルエット周辺強調画像を極座標変換する。
次に、フーリエ変換部425が極座標変換した画像をフーリエ変換し、得られた3画像分のパワースペクトルの低周波成分をとり、これを最終的なシルエット画像特徴量fsilhouetteとする。
【数13】
JP0005024767B2_000014t.gif

【0026】
輪郭画像特徴量演算部43の二次元画像形成部431はノーマルSVD化データ記憶部15及びポイントSVD化データ記憶部17に記憶されている三次元モデルのデータを読出し、輪郭画像特徴量の演算に用いる二次元画像(輪郭画像)を形成する。ここに、輪郭画像は、三次元モデルに光を当ててできた影の輪郭を二次元の2値画像で表したものである(図8)。背景を0、輪郭線の部分を255の整数で表す。
この輪郭画像には補正を行なわず、これを直接極座標変換する。
次に、フーリエ変換部435が輪郭画像をフーリエ変換し、得られた3画像分のパワースペクトルの低周波成分をとり、これを輪郭画像特徴量fContourとする。
【数14】
JP0005024767B2_000015t.gif

【0027】
ボクセル特徴量演算部44について説明する。
ボクセルは、三次元モデルの形状を小さな立方体の集合で表したものである。三次元モデルを格子空間内におき、面と交わる格子を1、その他の格子を0として表す(図9)。
ボクセル格子形成部431は、ノーマルSVD化データ記憶部15及びポイントSVD化データ記憶部17に記憶されている三次元モデルのデータを読出し、実施例では、64×64×64のボクセルに変換している。
次に、生成したボクセルに対して、3×3×3の大きさの三次元ガウシアンフィルタを施す。ガウシアンフィルタを施すことで、物体の曲線情報を高めることができる。ガウシアンフィルタを施した後のボクセル格子は[0,255]の値を取る。
フーリエ変換部435はかかるボクセル格子を三次元フーリエ変換し、パワースペクトルを得る。
【数15】
JP0005024767B2_000016t.gif
なお、実施例の場合、式15において0≦p<J=64,0≦q<K=64,0≦s<L=64である。
パワースペクトルの低周波成分を取りだして、ボクセル特徴量fVoxelとする。
【数16】
JP0005024767B2_000017t.gif

【0028】
デプスバッファ特徴量、シルエット画像特徴量、輪郭画像特徴量、及びボクセル特徴量はともにスペクトルであるため、これらを一次元ベクトルと考え、それぞれマンハッタン距離演算部417,427,437及び447でマンハッタン距離を演算する。
【数17】
JP0005024767B2_000018t.gif
この際に、ポイントSVD化データ記憶部15から読み出した三次元モデルの特徴量FVPointsとの距離とノーマルSVD化データ記憶部17から読み出した三次元モデルの特徴量FVNomalの距離を比較し、小さい方の距離を採用する。
【数18】
JP0005024767B2_000019t.gif

【0029】
重み演算部45は、上記で採用された小さい方の距離での検索クエリとデータベース内の全距離を用いて、重みを演算する。重みの演算には、Ohbuchiらのアルゴリズムを用いる(R.Ohbuchi, Y.Hata, Combining Multiresolution Shape Descriptors for 3D Model Retrieval, Proc.WSCG 2006,Plzen, Czech Republic,Jan. 30 Feb.2,2006.)。このアルゴリズムでは各特徴量の距離dを正規化することから始める。μ(di)は平均を、σ(di)は標準偏差を表すとすると、式18のように正規化する。
【数19】
JP0005024767B2_000020t.gif
なお、Purity値の計算は、仮定として、データベース内のモデルがM個のクラスCk(0<k≦M)に分類されているとする。検索結果上位t位Rtのうち、Ck内のモデルと適合する個数Skが最大いくらかがPurity値である。式で表すと次のようになる。
【数20】
JP0005024767B2_000021t.gif
このpurity値をn乗したものを重み(w)とする。
【0030】
複合部47では、このようにして得られた重みを各距離へかけ合わせその総和をとる。なお、purity値を用いることは必須ではなく、重み計算のひとつの方法として利用している。
【数21】
JP0005024767B2_000022t.gif
この距離を最終的な距離とすることで、各特徴量の統合を行なう。
【0031】
特徴量比較部50は、複合部47で得られた最終的な距離をデータベース13に保存されている距離と比較して、距離の近いものから順に並べてディスプレイへ表示する。
【0032】
実施例の検索システムを次のようにして評価した。
検索システムの評価を行う尺度として、First Tier(1-Tier),Second Tier(2-Tier),Nearest Neighbor(1-NN),および再現率(Recall),適合率(Precision)を用いる。各評価尺度を計算するためには、三次元モデルのデータベースをいくつかのクラスに分類しておく必要がある。クラスとは、システムが似ていると判断すべきモデルの集合を人間が主観的に判断し分類したものである。評価実験に使用するPSB(Princeton Shape Benchmark)データセットは、国際的に実験データベースとして使用され,907個の三次元モデルが92個のクラスに分類されている。検索クエリが属するクラスの三次元モデル数をc,検索結果の上位として返す三次元モデルの数をk,検索結果のうち検索クエリと同じクラスに属する三次元モデルの数をrelとすると、
【数22】
JP0005024767B2_000023t.gif
と定義される。ただし、First Tier,Second Tier,Nearest Neighbor においては検索クエリの3 次元モデルは除く。First Tier,Second Tier,Nearest Neighbor は高いほど性能が良く、再現率-適合率のグラフではカーブが右上に近づくほど性能が良い。First Tier,Second Tier,Nearest Neighbor についてはOsadaらの研究(R.Osada, T.Funkhouser, B.Chazelle, D.Dobkin, Shape Distributions, ACM,TOG,21(4),pp.807-832,2002.)、再現率と適合率についてはMinの研究(P.Min, A 3D Model Search Engine, Ph.D.Thesis, Princeton University, 2004.)で詳しく述べられている。
【0033】
実施例の検索方法(MFSD)と既述の従来例の検索方法との比較実験について説明する。
実施例の検索方法MFSD におけるポイントSVD,ノーマルSVDで生成した点群数は32768点であり、相違度計算での重みは検索結果上位4位までを使用して計算したpurity値の3乗とした。これらのパラメータは、事前の実験において得た最適値である。また、重みを全て1に固定したものについても比較した。
既述のD2,SHD、LFD、DSR472についてはそれぞれ公開されているプログラムを使用した。
図10は、これら代表的な4つの特徴量と実施例の検索方法MFSDとの比較実験の結果である。実施例のMFSD purity-weighted は重み計算にpurity法を用いたものである。MFSD fix-weighted は重みを全て1に固定したものである。
【0034】
全ての再現率-適合率の組み合わせにおいて、MFSD purity-weighted が他の特徴量を上回っていることがわかる。LFDの平均適合率が0.51,DSR472の平均適合率が0.53なのに対して、MFSD purity-weighted の平均適合率は0.60となった。また、MFSD fix-weighted の平均適合率は0.58であることから、重みを全て1に固定しても、他の特徴量を用いた場合より優れていることがわかる。
表1は、各特徴量の検索性能を1-Tier,2-Tier,1-NN で表したものである。
【表1】
JP0005024767B2_000024t.gif
1-Tier ではDSR472 より6.8%、2-TierではDSR472 より8.0%、1-NN ではLFD より8.5%、MFSDpurity-weighted が上回っている。MFSD fix-weighted でも、1-Tier,2-Tier,1-NN の全てで他の特徴量を上回っている。
以上の実験結果から、実施例の検索システムを実行することにより、高い精度の検索結果を得られることがわかる。
【0035】
デプスバッファ特徴量演算部41より得られる特徴量fDepth Buffer から得られるマンハッタン距離のみに基づいて検索をした場合(ポイントSVD + ノーマルSVD + PEI(Periphery Enhanced Image))、前記において正対化処理をポイントSVDのみとしたもの(ポイントSVD+PEI)、デプスバッファ特徴量演算部41において補正部413を省略したときの特徴量(但し、正対化処理はポイントSVDのみ)、即ちデプスバッファ画像を何ら補正することなくフーリエ変換して、得られたパワースペクトルから低周波成分を取りだしたスペクトルのマンハッタン距離(ポイントSVD)、DSR472及びLFDの検索性能比較を図11に示す。
図11の結果は図9の例と同様にして行った。図11の結果から、デプスバッファ画像を補正することにより、DSR472よりも優れた検索結果が得られることがわかる。
【0036】
前の実施例では、システムに与えられた検索クエリより特徴量を求め、予め計算しておいたデータベース内の全モデルの特徴量と距離計算を行い、距離の大きさによりモデルを並び替えていた。この手法では、たとえば自動車モデルを検索クエリとしたときに、自動車とは関係のない長方形のモデルまでもが、形状に類似性があるとして、検索結果上位に上がってくるという問題があった。
そこで、予め3次元モデルデータベースを形状によりクラスタリングして、検索結果をクラスタリングされた3次元モデル郡で提示することで、検索精度の向上を試みた。自動車モデルの例であれば、3次元モデルデータベース内の自動車クラスタに属するモデル群を検索結果上位に提示することで、自動車と関係のないモデルが検索結果上位に現れることを防ぐことができる。
【0037】
以下に、クラスタリングを前の実施例に適用した例について説明する。
予め特徴量データベース13内の特徴量をt個のクラスタに分割しておく。あるクラスタCi(i=1,・・・・,t)に割り当てられたデータベース内のm個の特徴量をfCi(j)(j=
1, ・・・・,m)とする。検索クエリが与えられると、その特徴量fを計算し、検索クエリの特徴量と各クラスタ内の全ての特徴量間で距離計算を行う。クラスタ内の全特徴量と検索クエリの特徴量間の最小距離を検索クエリに対するクラスタ距離dCiとする。以下でdL1はマンハッタン距離を表す。
【数23】
JP0005024767B2_000025t.gif

【0038】
このクラスタ距離dCiが小さい順にクラスタを並べる。クラスタ内の特徴量と検索クエリ特徴量との距離を計算し、距離の小さい順で対応する3次元モデルを並び替え、この検索結果を提示する。
【0039】
上記において、データベースのクラスタリングには、スペクトルクラスタリングを用いた。一般的なスペクトルクラスタリングの手順を図12に示す。
この実施例では、二次元画像の中心から離れるに従って画素の濃淡が強調するように補正された画像から得られたフーリエスペクトルより低周波成分のみを取り出し、これを前記MFSD特徴量として利用する。
一般にMFSD特徴量は高次元であるため、そのままのマンハッタン距離では、次元の呪い現象により特徴量間の正確な距離を測れないおそれがある。そこで、特徴量空間でm近傍は接続しているとして、ダイクストラ法により計算した最小測地線距離を特徴量間の距離とする。また、MFSD特徴量は図12の式(3)の段階で正規化されているので、類似行列の正規化処理は行わない。かかる修正を施した実施例のスペクトラルクラスタリングの手順を図13に示す。
図13において、σは類似行列Aの要素の減少速度を制御するスケーリングパラメータであり、平均測地線距離を用いる。これは実験により得た最適値である。
上記実施例のスペクトルクラスタリングでは、クラスタ数k、近傍点数mの2つがクラスタリングの精度を左右するパラメータとなる。
【0040】
実験データベースとしてのPSB(Princeton Shape Benchmark)データセットに対してスペクトルクラスタリングを実行する際のパラメータ、次元数(クラスタ数)k、近傍点数mの最適値を求めるために、これらを変更した場合の検索精度を、評価値に1-Tier(数22参照)を用いて実験を行った。結果を表2に示す。
【表2】
JP0005024767B2_000026t.gif
次元数(クラスタ数)kは、全モデル数907個に対して、1/100、3/100,・・・というように、近傍点数mは1/10、3/10,・・・というように変化させた。実験結果より、次元数(クラスタ数)k=45、近傍点数m=635付近に最適値があることがわかる。さらに細かく値を変化させて実験を行うと、次元数(クラスタ数)k=40、近傍点数m=615で、1-Tireが64.5%となった。近傍点数mは大きめに設定したほうがよいことがわかる。
このように修正したスペクトルクラスタリングをMSC(Modified Spectral Clustering)と呼ぶこととし、PSB(Princeton Shape Benchmark)データセットに適用し、前の実施例で説明した検索方法(MFSD)、通常のスペクトルクラスタリング法(SC)、およびMFSDのあとSCを適用する修正型スペクトルクラスタリング(MSC:Modified Spectral Clustering)を比較実行したときの結果を図14に示す。SCだけでは、MFSDよりも性能は悪いが、2つを組み合わせたMSCでは、検索性能が飛躍的に向上することがわかる。
【0041】
実施例の検索方法をMFSD(重み;全て1に固定)をPSB(Princeton Shape Benchmark)データセット以外のデータベースに適用した結果を以下に説明する。
PSB(Princeton Shape Benchmark)を対象としたときの性能を表3及び図15に示す。
【表3】
JP0005024767B2_000027t.gif
同様に、ESB(Engineering Shape Benchmark)を対象としたときの性能を表4及び図16に示す。
【表4】
JP0005024767B2_000028t.gif
同様に、SHREC2007(Shape Retrieval Contest 2007)を対象としたときの性能を表5及び図17に示す。
【表5】
JP0005024767B2_000029t.gif
全てのデータベースに対してこの実施例の検索方法が有意な効果を示すことがわかる。
【0042】
この発明は、上記発明の実施の形態及び実施例の説明に何ら限定されるものではない。特許請求の範囲の記載を逸脱せず、当業者が容易に想到できる範囲で種々の変形態様もこの発明に含まれる。
図面
【図1】
0
【図11】
1
【図12】
2
【図13】
3
【図14】
4
【図15】
5
【図16】
6
【図17】
7
【図2】
8
【図3】
9
【図4】
10
【図5】
11
【図6】
12
【図7】
13
【図8】
14
【図9】
15
【図10】
16