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

明細書 :三次元物体モデルを検索するための方法、コンピュータプログラム及びシステム、及び、三次元物体を分類するための方法、コンピュータプログラム及びシステム

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2014-120026 (P2014-120026A)
公開日 平成26年6月30日(2014.6.30)
発明の名称または考案の名称 三次元物体モデルを検索するための方法、コンピュータプログラム及びシステム、及び、三次元物体を分類するための方法、コンピュータプログラム及びシステム
国際特許分類 G06T   1/00        (2006.01)
G06T  15/08        (2011.01)
G06T   7/00        (2006.01)
FI G06T 1/00 200E
G06T 15/08
G06T 7/00 C
G06T 7/00 300H
請求項の数または発明の数 16
出願形態 OL
全頁数 19
出願番号 特願2012-275452 (P2012-275452)
出願日 平成24年12月18日(2012.12.18)
発明者または考案者 【氏名】青野 雅樹
【氏名】立間 淳司
出願人 【識別番号】304027349
【氏名又は名称】国立大学法人豊橋技術科学大学
個別代理人の代理人 【識別番号】100095577、【弁理士】、【氏名又は名称】小西 富雅
【識別番号】100100424、【弁理士】、【氏名又は名称】中村 知公
【識別番号】100179202、【弁理士】、【氏名又は名称】木村 誠司
審査請求 未請求
テーマコード 5B050
5B080
5L096
Fターム 5B050BA09
5B050BA13
5B050DA10
5B050EA07
5B050EA18
5B050EA27
5B050EA28
5B050FA02
5B050GA08
5B080AA14
5B080AA17
5B080BA02
5B080DA06
5B080GA02
5L096AA09
5L096FA23
5L096HA07
5L096JA11
5L096JA18
要約 【課題】
多量のデータによる事前の学習を必要とすることなく、高い精度で三次元データの検索を行い得る装置及び方法を提供する。
【解決手段】
三次元物体から作成したボクセル表現内の複数のボクセルを所定のウィンドウにより順次複数のボクセル部分として抽出する。二番目以降に抽出するボクセル部分は先に抽出した何れかのボクセル部分の一部のボクセルと重複させる。ボクセル部分ごとに三次元フーリエ変換を適用して求めた複数のスペクトルから第1特徴量を求める。三次元物体を奥行バッファ法により二次元画像に投影し、二次元画像の中心から離れるに従って画素の濃淡が強調されるようにする。二次元画像に二次元フーリエ変換を適用して求めたスペクトルから第2特徴量を求める。第1特徴量と第2特徴量を複合して特徴量を求め、予め得られた三次元物体モデルの特徴量と比較し、三次元物体と三次元物体モデルとの類似度を判断する。
【選択図】 図1
特許請求の範囲 【請求項1】
三次元物体に類似した三次元物体モデルを検索する三次元物体モデルの検索方法であって、
前記三次元物体からボクセル表現を作成するステップと、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解するステップと、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求めるステップと、
前記複数のボクセル部分の複数のスペクトルから、前記三次元物体の第1特徴量を求めるステップと、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第2特徴量を求めるステップと、
前記第1特徴量と前記第2特徴量を複合することにより前記三次元物体の特徴量を求めるステップと、
前記三次元物体の特徴量と、予め得られた前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と前記三次元物体モデルとの類似度を判断するステップと、を有する検索方法。
【請求項2】
前記類似度を判断するステップは、前記三次元物体の特徴量と、予め得られた複数の前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と複数の前記三次元物体モデルとの類似度を判断し、
前記類似度が高い順に、複数の前記三次元物体モデルを順位付けするステップを更に有する、請求項1に記載の検索方法。
【請求項3】
前記ボクセル表現を作成するステップは、前記三次元物体の三次元物体モデルに対して複数の姿勢正規化処理を行う、請求項1又は2に記載の検索方法。
【請求項4】
前記姿勢正規化処理は前記三次元物体モデルを構成する三角面上にランダムな点を生成し、それを質点として主成分分析を行ない、主軸を求めて正規化を行なう第1の姿勢正規化処理と、前記三次元物体モデルの面上に生成したランダムな点と、それに近い三角形の2点との法線の分布をもとに主軸を求めて正規化を行なう第2の姿勢正規化処理とを含む、請求項3に記載の検索方法。
【請求項5】
請求項1に記載の方法をコンピュータに実行させるコンピュータプログラム。
【請求項6】
三次元物体を、予め用意した複数のカテゴリーの何れかに分類するための分類方法であって、
前記三次元物体からボクセル表現を作成するステップと、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解するステップと、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求めるステップと、
該複数のボクセル部分の複数のスペクトルから、前記三次元物体の第1特徴量を求めるステップと、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第2特徴量を求めるステップと、
前記第1特徴量と前記第2特徴量を複合することにより前記三次元物体の特徴量を求めるステップと、
前記三次元物体の特徴量と、前記複数のカテゴリーにそれぞれ予め付与された特徴量とを比較することにより、前記三次元物体を前記複数のカテゴリーのうち最も特徴量が類似するカテゴリーに分類するステップと、を含む分類方法。
【請求項7】
前記ボクセル表現を作成するステップは、前記三次元物体の三次元物体モデルに対して複数の姿勢正規化処理を行う、請求項6に記載の分類方法。
【請求項8】
前記姿勢正規化処理は前記三次元物体モデルを構成する三角面上にランダムな点を生成し、それを質点として主成分分析を行ない、主軸を求めて正規化を行なう第1の姿勢正規化処理と、前記三次元物体モデルの面上に生成したランダムな点と、それに近い三角形の2点との法線の分布をもとに主軸を求めて正規化を行なう第2の姿勢正規化処理とを含む、請求項7に記載の分類方法。
【請求項9】
請求項6に記載の方法をコンピュータに実行させるコンピュータプログラム。
【請求項10】
三次元物体に類似した三次元物体モデルを検索する三次元物体モデルの検索システムであって、
前記三次元物体からボクセル表現を作成する手段と、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解する手段と、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求める手段と、
該複数のボクセル部分の複数のスペクトルから、前記三次元物体の第1特徴量を求める手段と、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第2特徴量を求める手段と、
前記第1特徴量と前記第2特徴量を複合することにより前記三次元物体の特徴量を求める手段と、
前記三次元物体の特徴量と、予め得られた前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と前記三次元物体モデルとの類似度を判断する手段と、を有する検索システム。
【請求項11】
前記類似度を判断する手段は、前記三次元物体の特徴量と、予め得られた複数の前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と複数の前記三次元物体モデルとの類似度を判断し、
前記類似度が高い順に、複数の前記三次元物体モデルを順位付けする手段を更に有する、請求項10に記載の検索システム。
【請求項12】
前記ボクセル表現を作成する手段は、前記三次元物体の三次元物体モデルに対して複数の姿勢正規化処理を行う、請求項10又は11に記載の検索システム。
【請求項13】
前記姿勢正規化処理は前記三次元物体モデルを構成する三角面上にランダムな点を生成し、それを質点として主成分分析を行ない、主軸を求めて正規化を行なう第1の姿勢正規化処理と、前記三次元物体モデルの面上に生成したランダムな点と、それに近い三角形の2点との法線の分布をもとに主軸を求めて正規化を行なう第2の姿勢正規化処理とを含む、請求項13に記載の検索システム。
【請求項14】
三次元物体を、予め用意した複数のカテゴリーの何れかに分類するための分類システムであって、
前記三次元物体からボクセル表現を作成する手段と、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解する手段と、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求める手段と、
該複数のボクセル部分の複数のスペクトルから、前記三次元物体の第1特徴量を求める手段と、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第2特徴量を求める手段と、
前記第1特徴量と前記第2特徴量を複合することにより前記三次元物体の特徴量を求める手段と、
前記三次元物体の特徴量と、前記複数のカテゴリーにそれぞれ予め付与された特徴量とを比較することにより、前記三次元物体を前記複数のカテゴリーのうち最も特徴量が類似するカテゴリーに分類する手段と、を含む分類システム。
【請求項15】
前記ボクセル表現を作成する手段は、前記三次元物体の三次元物体モデルに対して複数の姿勢正規化処理を行う、請求項14に記載の分類システム。
【請求項16】
前記姿勢正規化処理は前記三次元物体モデルを構成する三角面上にランダムな点を生成し、それを質点として主成分分析を行ない、主軸を求めて正規化を行なう第1の姿勢正規化処理と、前記三次元物体モデルの面上に生成したランダムな点と、それに近い三角形の2点との法線の分布をもとに主軸を求めて正規化を行なう第2の姿勢正規化処理とを含む、請求項15に記載の分類システム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、三次元物体モデルを検索するための方法、コンピュータプログラム及びシステム、及び、三次元物体を分類するための方法、コンピュータプログラム及びシステムに関するものである。
【背景技術】
【0002】
三次元物体モデルの検索方法として各種の方法が知られている。
D2: D2はOsadaらの研究(非特許文献1)で最も高い検索精度を得た特徴量である。三次元物体の面上にランダムな点群を生成し、全2点間のユークリッド距離の頻度を示すヒストグラムを特徴量とする。特徴量間の距離は、求めたヒストグラムを一次元ベクトルと考えて計算したマンハッタン距離である。
Spherical Harmonics Descriptor(SHD): SHDはKazhdanらにより提案された手法である(非特許文献2)。ボクセル化した三次元物体を球面調和関数変換し、得られたパワースペクトルの低周波部分を特徴量とする。特徴量間の距離は、求めたパワースペクトルを1次元ベクトルと考えて計算したユークリッド距離である。
Light Field Descriptor(LFD): LFDはChenらにより提案された手法である(非特許文献3参照)。12面体の頂点を視点とし、それを回転させながら、多数の視点から三次元物体のシルエット画像を生成する。生成したシルエット画像のツェルニケモーメントとフーリエスペクトルを計算し特徴量とする。特徴量間の距離は、12面体の各頂点と全ての回転における組み合わせで最小L1距離を計算したものである。
Hybrid Descriptor(DSR472): DSR472はVranicの研究で最も高い検索精度を得た特徴量である(非特許文献4参照)。Vranicが考案した、デプスバッファ特徴ベクトル、シルエット特徴ベクトル、重心から任意の方向にベクトルを放つことで得られるRay特徴ベクトルの3つを組み合わせた特徴量である。特徴量間の距離は、複合特徴量を一次元ベクトルと考えてマンハッタン距離を計算したものである。
MFSD (Multi-Fourier Spectra Descriptor): MFSDは本発明の発明者らが提案した手法である(特許文献1参照)。MFSDは、Depth Buffer画像・シルエット画像・輪郭画像・ボクセル表現の四種類の形状表現から求めたフーリエスペクトルからなる特徴量である。それまでで最も検索精度が高いといわれていたDSR472法を凌駕する検索手法として提案したものである。
【先行技術文献】
【0003】

【特許文献1】特許第5024767号公報
【特許文献2】特願2010-134589号
【0004】

【非特許文献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.
【発明の概要】
【発明が解決しようとする課題】
【0005】
上記のMFSDは、四種類の形状表現から特徴量を求めることにより、DSR472法を凌駕する検索精度を達成することができた。しかしながら、特徴量を求める場合に、データが肥大化するという問題があった。この問題の解決策として本発明者らは、LDP(線形拡散射影)法を提案している(特許文献2参照)。しかしながら、このLDP法は検索時に扱うデータ量を削減できるものの、多量のデータによる事前学習を必要とする点で、なお改善の余地があった。
【0006】
本発明は前記問題を解決するためになされたものであって、その目的は、多量のデータによる事前の学習を必要とすることなく、高い精度で三次元物体モデルの検索を行い得る方法及びシステム、及び、高い精度で三次元物体の分類を行い得る方法及びシステムを提供することにある。
【課題を解決するための手段】
【0007】
本発明者らは前記課題を解決するために鋭意検討を重ねた結果、下記のように本発明の各局面に想到した。
【0008】
即ち、本発明の第1の局面による三次元物体に類似した三次元物体モデルを検索する三次元物体モデルの検索方法は、
前記三次元物体からボクセル表現を作成するステップと、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解するステップと、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求めるステップと、
前記複数のボクセル部分の複数のスペクトルから、前記三次元物体の第1特徴量を求めるステップと、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第2特徴量を求めるステップと、
前記第1特徴量と前記第2特徴量を複合することにより前記三次元物体の特徴量を求めるステップと、
前記三次元物体の特徴量と、予め得られた前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と前記三次元物体モデルとの類似度を判断するステップと、を有する検索方法である。
【0009】
このような構成の検索方法は、MFSDでは用いていたシルエット特徴量及び輪郭特徴量を用いないため、MFSDよりも検索用のインデックスがコンパクトである。しかも、LDPのような事前学習の必要もないという利点を有する。また、ボクセル表現を各ボクセル部分に重複分解することで、ボクセル部分間をまたぐ形状の連続的変化を捉えることができ、三次元物体の輪郭等の形状をより詳細かつ高精度に把握することが可能となる。更には、重複分解したボクセル部分ごとに計算したフーリエスペクトルを特徴量として用いるため、三次元物体の外見的な形状的特徴だけでなく、三次元空間中にどのような形状がどこにあるかという空間的特徴をもより高精度に捉えることが可能となる。そのため、後に詳述する本発明者らの行った検証実験においても示されているように、本願発明による検索方法の検索精度はMFSDより高く、LDPと同等またはそれ以上である。
【0010】
本発明の第2の局面によれば、前記類似度を判断するステップは、前記三次元物体の特徴量と、予め得られた複数の前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と複数の前記三次元物体モデルとの類似度を判断し、検索方法は、前記類似度が高い順に、複数の前記三次元物体モデルを順位付けするステップを更に有する。
このような構成によれば、検索対象としての三次元物体と類似度の高いものから順に複数の三次元物体モデルに対して順位付けを行うことができ、ユーザは、この順位情報を考慮に入れた上で検索結果を考察し、利用することができるので利便性が高い。
【0011】
本発明の第3の局面によれば、前記ボクセル表現を作成するステップは、前記三次元物体の三次元物体モデルに対して複数の姿勢正規化処理(即ち、複数の正対化処理)を行う。
このような構成とすることで、三次元物体モデルの位置や向きが製作者やツール等によって異なる場合であっても、検索精度の低下を防止することができる。また、複数の姿勢正規化処理を行うことで、より好適な姿勢正規化処理結果を用いることができる。
【0012】
本発明の第4の局面によれば、前記姿勢正規化処理は前記三次元物体モデルを構成する三角面上にランダムな点を生成し、それを質点として主成分分析を行ない、主軸を求めて正規化を行なう第1の姿勢正規化処理と、前記三次元物体モデルの面上に生成したランダムな点と、それに近い三角形の2点との法線の分布をもとに主軸を求めて正規化を行なう第2の姿勢正規化処理とを含む。このような構成によれば、好適な姿勢正規化処理を行うことができる。
【0013】
本発明の第5の局面による三次元物体を、予め用意した複数のカテゴリーの何れかに分類するための分類方法は、
前記三次元物体からボクセル表現を作成するステップと、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解するステップと、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求めるステップと、
該複数のボクセル部分の複数のスペクトルから、前記三次元物体の第1特徴量を求めるステップと、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第2特徴量を求めるステップと、
前記第1特徴量と前記第2特徴量を複合することにより前記三次元物体の特徴量を求めるステップと、
前記三次元物体の特徴量と、前記複数のカテゴリーにそれぞれ予め付与された特徴量とを比較することにより、前記三次元物体を前記複数のカテゴリーのうち最も特徴量が類似するカテゴリーに分類するステップと、を含む分類方法である。
【0014】
このような構成の分類方法によれば、第1の局面について述べた理由と同様の理由により、三次元物体の分類用のインデックスがコンパクトであり、しかも分類の精度が高いという利点を有する。
【0015】
本発明の第6の局面による三次元物体に類似した三次元物体モデルを検索する三次元物体モデルの検索システムは、
前記三次元物体からボクセル表現を作成する手段と、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解する手段と、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求める手段と、
該複数のボクセル部分の複数のスペクトルから、前記三次元物体の第1特徴量を求める手段と、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第2特徴量を求める手段と、
前記第1特徴量と前記第2特徴量を複合することにより前記三次元物体の特徴量を求める手段と、
前記三次元物体の特徴量と、予め得られた前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と前記三次元物体モデルとの類似度を判断する手段と、を有する検索システムである。
このような構成の検索システムは、前記第1の局面による検索方法と同様の利点を有する。
【0016】
本発明の第7の局面による三次元物体を、予め用意した複数のカテゴリーの何れかに分類するための分類システムは、
前記三次元物体からボクセル表現を作成する手段と、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解する手段と、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求める手段と、
該複数のボクセル部分の複数のスペクトルから、前記三次元物体の第1特徴量を求める手段と、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第2特徴量を求める手段と、
前記第1特徴量と前記第2特徴量を複合することにより前記三次元物体の特徴量を求める手段と、
前記三次元物体の特徴量と、前記複数のカテゴリーにそれぞれ予め付与された特徴量とを比較することにより、前記三次元物体を前記複数のカテゴリーのうち最も特徴量が類似するカテゴリーに分類する手段と、を含む分類システムである。
このような構成の分類システムは、前記第5の局面による分類方法と同様の利点を有する。
【図面の簡単な説明】
【0017】
【図1】図1は、本発明の第1実施形態による検索システムを示すブロック図である。
【図2】図2は、ポイントSVDにおける鏡像が異なる例を示す図である。
【図3】図3は、ノーマルSVDにおける演算原理を示す図である。
【図4】図4は、ボクセル表現の例を示す図である。
【図5】図5は、ボクセルの重複分解の概念を示す図である。
【図6】図6は、ボクセルの重複分解を行う場合と行わない場合の比較図である。
【図7】図7は、デプスバッファ画像の例を示す図である。
【図8】図8は、周辺輝度強調により補正されたデプスバッファ画像(PEI画像)の例を示す図である。
【図9】図9は、周辺輝度強調により補正されたデプスバッファ画像を極座標変換した画像である。
【図10】図10は、第1実施形態による検索システムの効果を示すグラフである。
【図11】図11は、第1実施形態による検索システムの効果を示す別のグラフである。
【図12】図12は、本発明の第2実施形態による分類システムを示すブロック図である。
【発明を実施するための形態】
【0018】
(第1実施形態)
次に、本発明を具体化した第1実施形態に係る三次元物体モデルを検索するための検索システム1について、図面を参照しながら説明する。
図1は本実施形態の検索システム1の構成を示すブロック図である。検索システム1は汎用的なコンピュータ装置からなり、その機能をブロックで表すと図1のようになる。即ち、本実施形態の検索システム1は制御装置3、記憶部10、入出力部20、姿勢正規化処理部30、特徴量演算部40及び特徴量比較部50から構成される。

【0019】
制御装置3は記憶部10のプログラム記憶部11から制御用プログラムを読み出して、このプログラムにしたがって各要素を制御する。記憶部10の既知三次元物体モデルの特徴量データベース13には、以下に説明する方法で特徴量の演算された三次元物体モデルがその特徴量とともに保存されている。三次元物体モデルは後述する姿勢正規化処理(即ち、正対化処理)が施され、かつ正規化されている。
記憶部10は更に、ポイントSVD(Point SVD)化データ記憶部15、及び、ノーマルSVD(Normal SVD)化データ記憶部17を有する。

【0020】
入出力部20はキーボード/マウス21、ディスプレイ23、プリンタ25、データ入出力インターフェース27及び通信インターフェース29を備えている。検索対象である三次元物体のデータ(即ち、モデル化された三次元物体)はデータ入出力インターフェース27からシステム内に取り込むことができる。通信インターフェース29はシステムをインターネットへ接続する。

【0021】
姿勢正規化処理部30は、検索対象である三次元物体を姿勢正規化処理し、更に大きさをそろえるために正規化する。姿勢正規化処理部30にはポイントSVD部31とノーマルSVD部33があり、それぞれ異なる手法で三次元物体のデータを姿勢正規化処理する。正規化部35は三次元物体の大きさの任意性を解決するものである。
ポイントSVD部31で姿勢正規化されかつ正規化部35で正規化された三次元物体のデータは記憶部10のポイントSVD化データ記憶部15に一時保存され、ノーマルSVD部33で姿勢正規化されかつ正規化部35で正規化された三次元物体のデータは記憶部10のノーマルSVD化データ記憶部17に一時保存される。

【0022】
以下、ポイント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】
JP2014120026A_000003t.gif
本実施形態では擬似乱数にメルセンヌTwister乱数を用いた。また、生成する点群数は全体でL個とする(Lは十分に大きい数とする)。実施例ではL=32768個である。こうして生成された点群より三次元物体モデルの重心を求める。重心mが原点となるよう平行移動することで、位置の任意性の問題を解決する。実施例での点群データ行列は以下の式で表現される。
【数2】
JP2014120026A_000004t.gif
次に、点群行列Pを特異値分解することで回転行列Rを得る。
【数3】
JP2014120026A_000005t.gif

【0023】
回転行列Rにより、点群を回転させる。これにより、主軸が三次元空間のx軸・y軸・z軸に沿うような回転をする。
【数4】
JP2014120026A_000006t.gif
最後に、三次元物体モデルの鏡像を決める。軸が同じになっても、鏡像が異なれば特徴量は変化してしまう(図2参照)。
モデルの鏡像行列Fは、L個(実施例では、L=32768個)の点群の場合、以下のように計算する。
【数5】
JP2014120026A_000007t.gif
以上の計算により求めた重心m、回転行列R、鏡像行列Fにより、モデル頂点Vを平行移動・回転させて姿勢正規化を完成する。
【数6】
JP2014120026A_000008t.gif

【0024】
ポイント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乱数を用いることと、鏡像の決定に中心からの距離を用いていることである。

【0025】
次に、ノーマルSVDについて詳細に説明する。
基本的な計算方法はポイントSVDと同様である。ノーマルSVDでは点群を生成するときに、生成した点と元になった三角形の頂点の最も近い2点との法線を質点として計算する(図3)
まず、法線ベクトルnの平均を求める。L個(実施例では、L=32768個)での法線ベクトルの平均は以下のように求める。
【数7】
JP2014120026A_000009t.gif
次に法線ベクトル行列Nを特異値分解し、回転行列Rを求める。
【数8】
JP2014120026A_000010t.gif

【0026】
最後に、回転させた点群を元に、ポイントSVDと同様にして鏡像決定行列Fを計算する。
【数9】
JP2014120026A_000011t.gif
以上により、姿勢正規化は完了する。頂点行列Vの定義はポイントSVDと同様である。

【0027】
このようにして姿勢正規化された各モデルはBounding Sphere法により正規化される。
ここに、Bounding Sphere法は、半径1の単位球であり、これに姿勢正規化された検索対象の三次元物体モデルが収まるようにする。具体的な計算方法としては、三次元物体モデルの全頂点と重心との距離の最大値で各頂点の座標値を割る。

【0028】
このように2種類の姿勢正規化法を用いる理由は以下の通りである。即ち、凹凸の多い物体の姿勢正規化に有効とされるPoint SVDと、角張った形状の姿勢正規化に有効とされるNormal SVDとを備えることで、より多様な三次元物体の姿勢正規化に対応でき、頑強性が高められるからである。

【0029】
特徴量演算部40は、重複分解ボクセル特徴量演算部41、デプスバッファ特徴量演算部42及び複合部43を備えてなる。
最初に、重複分解ボクセル特徴量演算部41のボクセル表現作成部411が、姿勢正規化処理部30にて姿勢正規化及び正規化を経た三次元物体のデータからボクセル表現を作成する。ボクセル表現とは例えば図4のように、三次元物体を立方体の集合で表したものである。本実施形態のボクセル表現作成部411においては、三次元物体の面上にランダムな点群を生成し、それらをM×M×Mの空間に量子化することで、三次元物体をボクセル表現に変換する。このとき、ボクセル表現の非0要素の値は、ボクセル空間の中心からのユークリッド距離とする。すなわち、すべてのボクセルは0または正の実数値をとることを意味する。実施例では、M=64とした。

【0030】
次に、三次元物体から生成したボクセル表現を、重複分解部413において、一定の大きさを有する三次元のウィンドウにて重複的に抽出し、各々を「ボクセル部分」として抽出する。
ボクセルの重複的な抽出について詳述すると、三次元的なウィンドウの寸法(即ち三次元空間に占める大きさ)は、ウィンドウ内に一度に複数のボクセルが含まれ得るように設定される。そして、ウィンドウをM×M×Mの空間内で三次元物体のボクセル表現に重ね合わせ、ウィンドウ内に存在する複数のボクセルを一つのボクセル部分として抽出する。

【0031】
次に、前記空間内で、ウィンドウを所定方向に所定の距離だけ移動させる。そして、ウィンドウ内に存在する複数のボクセルを、別のボクセル部分として抽出する。このように、ウィンドウを移動させながら、順次、ボクセル部分を抽出していく。その際、二番目以降に抽出されるボクセル部分と先に抽出されたボクセル部分との間で、一部のボクセルが重複するように、即ち、共通のボクセルを含むように、抽出する。ただし、ボクセル部分同士が完全一致しないようにする。このように、ボクセル表現を、複数のボクセル部分であって、それらの一部のボクセルが重複するような複数のボクセル部分として抽出することを、「ボクセル表現を重複分解する」と呼ぶこととする。

【0032】
ボクセル表現の重複分解について、図5の例により説明する。図5の例では、分かりやすさのため、ボクセル空間を二次元で表現している。この例では、ボクセル空間が64個×64個のボクセルからなり、ウィンドウの大きさは32個×32個のボクセルに相当する。まず図5(A)において32個×32個のボクセルを第1番目のボクセル部分として抽出する。次に、図5(B)のように、ウィンドウを16個のボクセルに相当する距離だけ右方向に移動させ、その場所においてウィンドウに囲まれる32個×32個のボクセルを第2番目のボクセル部分として抽出する。図5(A)、5(B)より、第1番目のボクセル部分と第2番目のボクセル部分とでは、全体として同一ではないが、その一部のボクセルが重複していることが分かる。

【0033】
そして更に図5(B)から図5(C)へは、同じくウィンドウを16個のボクセルに相当する距離だけ右方向に移動させる。図5(C)から図5(D)へは、32個のボクセルに相当する距離の左方向への移動と、16個のボクセルに相当する距離の下方向への移動を合わせた移動を行っている。そして更に順次、図5(E)~(I)のようにウィンドウを右方向、左斜め下方向、右方向、・・・というように所定の方向に所定の距離ずつずらしていきながら、ボクセル空間の全体を、一部が重複し合う複数のボクセル部分として抽出していく(即ち、重複分解する)。このように複数のボクセル部分を、その一部が重複し合うように抽出することで、データの冗長さを犠牲にしつつも、特徴量の連続的変化を高精度に捉えることが可能となる。

【0034】
なお、ウィンドウを「所定の方向」に「所定の距離」だけ移動させるという場合、それら「所定の方向」と「所定の距離」は終始一定のものには限られず、所定の取り決めに従って、途中で別の方向や異なる距離に切り替えられるものとして良い。例えば、ウィンドウがM×M×Mの空間の端まで進んだ場合には、M×M×Mの空間の逆の端に戻り、そこから、既にボクセルを抽出した範囲と一部重複するようにボクセルの抽出を継続するようにしても良い。あるいは、到達した端から折り返して、既にボクセルを抽出した範囲と一部重複するように抽出を継続するようにしても良い。その他、「所定の方向」及び「所定の距離」についての取り決めは、M×M×Mの空間内においてウィンドウを移動させ得る限り、任意のものを採用することができる。

【0035】
ボクセル空間を,単に複数のボクセル部分に分解するのではなく、重複させて分解するのは、ボクセル部分をまたぐ形状の連続的変化を捉えるためである。図6は,重複分解を行う場合(A)と行わない場合(B)とで、捉えられる形状的特徴の違いを表したものである。重複分解を行う場合(A)では、中央の円形を捉えることができるが、重複分解を行わない場合(B)では、この円形は分断され、中央に円形があるという情報は、特徴量に反映されない。

【0036】
次に、抽出したボクセル部分ごとに、次式によりフーリエ変換部415にてパワースペクトルを得る。
【数10】
JP2014120026A_000012t.gif
ここでは、各ボクセル部分の大きさをN×N×Nとした。Nはボクセルの数を表す。また、1≦p,q,r≦Nである。フーリエスペクトルの高周波成分には、形状の詳細情報やノイズが現れる。そこで、類似検索のため、本実施形態では、1≦p,q,r≦Bの低周波数成分fcellを用いる。実施例では、B=8とした。
【数11】
JP2014120026A_000013t.gif
結局全体はB=CMAX次元となる。実施例では、CMAX=512(=8)となる。
次に、ボクセル部分から計算したフーリエスペクトルの低周波成分を、全体総和で正規化する。
【数12】
JP2014120026A_000014t.gif
これらボクセル部分ごとに求めたフーリエスペクトルを並べたものが、重複分解ボクセル特徴量fDVDであり、高密度ボクセルスペクトル記述子(Dense Voxel Spectrum Descriptor: DVD)とも呼ぶこととする。実施例では、DVD_MAX=27とした。
【数13】
JP2014120026A_000015t.gif

【0037】
重複分解ボクセル特徴量fDVDは、ボクセル空間を、所定の大きさの複数のボクセル部分に重複分解し、ボクセル部分ごとに計算したフーリエスペクトルを並べたものである。そのため、このままでは、重複分解ボクセル特徴量fDVDの次元数は、((M-N)/T+1)×Bとなり、実施例の数字(実施例では、T=16、N=32とする)を代入すると、13,824次元と大きなものとなってしまう。そこで、各ボクセル部分から計算した、低周波数成分のフーリエスペクトルB=8=CMAX=512次元を、主成分分析により、K次元に削減する。実施例では、上位主成分で、寄与率の高かった次元として、K=20とした。その後、次元削減したフーリエスペクトルを並べ、全体をL1ノルム(マンハッタン距離)で正規化したものを、あらためて重複分解ボクセル特徴量fDVDとする。重複分解ボクセル特徴量fDVDの最終的な次元数は、((M-N)/T+1)×Kで、実施例の数字を代入すると、540次元となる。

【0038】
デプスバッファ特徴量演算部42の二次元画像形成部421は、姿勢正規化処理部30にて姿勢正規化及び正規化を経た三次元物体のデータに基づき、デプスバッファ特徴量の演算に用いる二次元画像(ディプスバッファ画像)を形成する。ここに、デプスバッファ画像は、任意の視点から三次元物体モデルの表面までの距離(深さ)を二次元画像で表したものである。
実施例では、三次元物体モデルの直交6方向からの視点で256×256の画素をもつデプスバッファ画像を形成する(図7参照)。
デプスバッファ画像が持つz値(深さ)は[0,255]の整数を取り、距離が遠いほど値は小さく、近いほど値は大きい。また、背景は0である。

【0039】
次に補正部423は、デプスバッファ画像に中心からの距離情報を埋め込むことにより、これを補正する。具体的には、デプスバッファ画像の各画素の輝度をI(x、y)としたとき、デプスバッファ画像の中心からの距離をrとすると、画素サイズを256×256とした実施例の場合、補正された画像の各座標の輝度I´(x,y)は、次のように表される(実施例では、R=128)。
【数14】
JP2014120026A_000016t.gif
補正された画像を周辺強調画像(Periphery Enhanced Image (PEI))とよぶことがある。補正された画像を図8に示す。図8及び式14より、補正された二次元画像は画像の中心から離れるしがたって画素の濃淡が強調されていることがわかる。また、画像の中心に近づくにしたがって画素が暗くなることもわかる。
最後に、補正されたデプスバッファ画像を直交座標から極座標へと変換する。極座標変換した画像を図9に示す。極座標は、横軸がr、縦軸が回転角θを表す。画像の大きさは、実施例の場合、R×Θ=128×512(ただし、R=128、Θ=512)となる。

【0040】
次にフーリエ変換部425が極座標変換した画像をフーリエ変換し、フーリエ係数gρφを得る。
【数15】
JP2014120026A_000017t.gif
ここに、ρは横軸の空間周波数、φは縦軸の空間周波数を表し、0≦ρ<128、0≦φ<512である。このフーリエ係数の大きさがパワースペクトルである。極座標では、直交座標における回転が平行移動となり、フーリエ変換により得られるパワースペクトルは平行移動不変の性質を持つ。姿勢正規化に誤りがある場合に、向きの任意性を若干緩和できる。
以上の処理により得られた、6画像分のパワースペクトルの低周波成分のみ取出したものをデプスバッファ特徴量fDepth Bufferとする。次式の通り、デプスバッファ特徴量fDepth Bufferは、(N1+1)×(N2+1)次元の特徴量次元である。なお、実施例においては、N1=7、N2=31とした。
【数16】
JP2014120026A_000018t.gif
低周波成分のみを特徴量として使用するのは、類似検索の場合、形状の微細な相違を表す高周波成分を無視するためである。
複合部43は、重複分解ボクセル特徴量演算部41により得られた重複分解ボクセル特徴量fDVDと、奥行バッファ特徴量演算部42により得られた奥行バッファ特徴量fDepth Bufferを複合する。

【0041】
特徴量比較部50は、複合部43で得られた最終的な距離をデータベースに保存されている距離と比較する。複合特徴量の相違度計算には、マンハッタン距離を用いる。
【数17】
JP2014120026A_000019t.gif
また、正規化手法の選択は、Point SVDにより正規化した三次元物体から生成した相違度dpointと、Normal SVDにより正規化した三次元物体から生成した相違度dnormalとで、値が小さいものを、最適な正規化手法として選択する。次式で、最終的な相違度を計算する。
【数18】
JP2014120026A_000020t.gif

【0042】
そして、特徴量比較部50は、最も距離の短い三次元物体モデルをディスプレイに表示したり、あるいは、距離の近いものから順に並べてディスプレイへ表示したりすることによって、検索結果を出力する。

【0043】
次に、第1実施形態の検索システム1の効果を、実施例により説明する。PSB(Princeton Shape Benchmark)を用いた再現率-適合率曲線は、図10のような結果となった。図10の縦軸「precision」は検索精度(誤検索の少なさ)を表し、横軸「recall」は再現率(検索漏れの少なさ)を表す。図10において、実線アが検索システム1による効果を示し、実線は、実線イ、ウ、エ、オ、カ、キ、クはそれぞれ比較対象として、重複分解ボクセル特徴量のみを用いた場合(即ち、第1実施形態においてデプスバッファ特徴量を複合せずに、式17、式18の計算を行った場合)、MFSD、DESIRE(ドイツ、Vranicらによる複合特徴量、2004年)、LFD、SHD、SPRH(ドイツ航空センターWahlらの特徴量、2003年)、D2を表す。これらの比較対象のいずれと比べても、本願発明による手法が上回っていることが分かる。

【0044】
一方、LDP法との比較を図11に示す。本願発明即ち、重複分解ボクセル特徴量とデプスバッファ特徴量の併用の効果は実線aにより示す。LDP法は、任意の手法で得られた特徴量を次元削減するものであり、特徴量算出手法と独立に適用できるため、図11では、MFSD+LDP(実線b)という形で比較した。実線cはMFSD単独による効果、実線dは重複分解ボクセル特徴量単独による効果を示す。
LDPは特徴量が得られた後のデータに対して学習を行い次元削減するものであり一般に高性能となるが、図11によれば、本願発明の重複分解ボクセル特徴量とデプスバッファ特徴量を併用する手法により、LDPにほぼ匹敵する検索性能が得られることが分かる。

【0045】
(第2実施形態)
次に、本発明の第2実施形態について、図12を参照して説明する。
図12に示す第2実施形態の三次元物体を分類するための分類システム101は、第1実施形態の特徴量比較部50に代えて、分類部60を有する。また、記憶部10は、第1実施形態の既知三次元物体モデルの特徴量データベース13に代えて、カテゴリー特徴量記憶部131を有する。カテゴリー特徴量記憶部131は、予め、複数の三次元物体モデルをそれぞれ含む複数のカテゴリー(例えば、自動車、動物、昆虫、あるいは更に詳細に、四輪自動車、オートバイ、バス、犬、猫、ウサギ、カブトムシ、テントウムシ、・・・等)を記憶しており、各カテゴリーには、それぞれ各カテゴリーの三次元物体モデルを代表する特徴量(例えば、各カテゴリーの三次元物体モデルの平均的な特徴量)が付与されている。その他の構成は図1の検索システム1と同じである。

【0046】
分類システム101の特徴量演算部40は、第1実施形態の検索システム1と同じ方法により、モデル化された三次元物体の複合特徴量を求める。そして、分類部60は、複合特徴量と、前記複数のカテゴリーにそれぞれ予め付与された特徴量を比較することにより、三次元物体を複数のカテゴリーのうち最も特徴量が類似するカテゴリーに分類する。分類結果は入出力部20を介して出力される。
これにより、高い精度で三次元物体をカテゴリーに分類することができる。

【0047】
本明細書の中で明示した論文、公開特許公報、特許公報などの内容は、その全ての内容を援用によって引用することとする。
【符号の説明】
【0048】
1 三次元物体モデルの検索システム、 10 記憶部、 20 入出力装置、30 姿勢正規化処理部、40 特徴量演算部、50 特徴量比較部、 60 分類部、 101 三次元物体の分類システム
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11