(57)【要約】【課題】  多量のデータによる事前の学習を必要とすることなく、高い精度で三次元データの検索を行い得る装置及び方法を提供する。【解決手段】  三次元物体から作成したボクセル表現内の複数のボクセルを所定のウィンドウにより順次複数のボクセル部分として抽出する。二番目以降に抽出するボクセル部分は先に抽出した何れかのボクセル部分の一部のボクセルと重複させる。ボクセル部分ごとに三次元フーリエ変換を適用して求めた複数のスペクトルから第１特徴量を求める。三次元物体を奥行バッファ法により二次元画像に投影し、二次元画像の中心から離れるに従って画素の濃淡が強調されるようにする。二次元画像に二次元フーリエ変換を適用して求めたスペクトルから第２特徴量を求める。第１特徴量と第２特徴量を複合して特徴量を求め、予め得られた三次元物体モデルの特徴量と比較し、三次元物体と三次元物体モデルとの類似度を判断する。【選択図】  図１
2014120026.tif 000002
【特許請求の範囲】
【請求項１】
三次元物体に類似した三次元物体モデルを検索する三次元物体モデルの検索方法であって、
前記三次元物体からボクセル表現を作成するステップと、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解するステップと、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求めるステップと、
前記複数のボクセル部分の複数のスペクトルから、前記三次元物体の第１特徴量を求めるステップと、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第２特徴量を求めるステップと、
前記第１特徴量と前記第２特徴量を複合することにより前記三次元物体の特徴量を求めるステップと、
前記三次元物体の特徴量と、予め得られた前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と前記三次元物体モデルとの類似度を判断するステップと、を有する検索方法。
【請求項２】
前記類似度を判断するステップは、前記三次元物体の特徴量と、予め得られた複数の前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と複数の前記三次元物体モデルとの類似度を判断し、
前記類似度が高い順に、複数の前記三次元物体モデルを順位付けするステップを更に有する、請求項１に記載の検索方法。
【請求項３】
前記ボクセル表現を作成するステップは、前記三次元物体の三次元物体モデルに対して複数の姿勢正規化処理を行う、請求項１又は２に記載の検索方法。
【請求項４】
前記姿勢正規化処理は前記三次元物体モデルを構成する三角面上にランダムな点を生成し、それを質点として主成分分析を行ない、主軸を求めて正規化を行なう第１の姿勢正規化処理と、前記三次元物体モデルの面上に生成したランダムな点と、それに近い三角形の２点との法線の分布をもとに主軸を求めて正規化を行なう第２の姿勢正規化処理とを含む、請求項３に記載の検索方法。
【請求項５】
請求項１に記載の方法をコンピュータに実行させるコンピュータプログラム。
【請求項６】
三次元物体を、予め用意した複数のカテゴリーの何れかに分類するための分類方法であって、
前記三次元物体からボクセル表現を作成するステップと、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解するステップと、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求めるステップと、
該複数のボクセル部分の複数のスペクトルから、前記三次元物体の第１特徴量を求めるステップと、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第２特徴量を求めるステップと、
前記第１特徴量と前記第２特徴量を複合することにより前記三次元物体の特徴量を求めるステップと、
前記三次元物体の特徴量と、前記複数のカテゴリーにそれぞれ予め付与された特徴量とを比較することにより、前記三次元物体を前記複数のカテゴリーのうち最も特徴量が類似するカテゴリーに分類するステップと、を含む分類方法。
【請求項７】
前記ボクセル表現を作成するステップは、前記三次元物体の三次元物体モデルに対して複数の姿勢正規化処理を行う、請求項６に記載の分類方法。
【請求項８】
前記姿勢正規化処理は前記三次元物体モデルを構成する三角面上にランダムな点を生成し、それを質点として主成分分析を行ない、主軸を求めて正規化を行なう第１の姿勢正規化処理と、前記三次元物体モデルの面上に生成したランダムな点と、それに近い三角形の２点との法線の分布をもとに主軸を求めて正規化を行なう第２の姿勢正規化処理とを含む、請求項７に記載の分類方法。
【請求項９】
請求項６に記載の方法をコンピュータに実行させるコンピュータプログラム。
【請求項１０】
三次元物体に類似した三次元物体モデルを検索する三次元物体モデルの検索システムであって、
前記三次元物体からボクセル表現を作成する手段と、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解する手段と、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求める手段と、
該複数のボクセル部分の複数のスペクトルから、前記三次元物体の第１特徴量を求める手段と、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第２特徴量を求める手段と、
前記第１特徴量と前記第２特徴量を複合することにより前記三次元物体の特徴量を求める手段と、
前記三次元物体の特徴量と、予め得られた前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と前記三次元物体モデルとの類似度を判断する手段と、を有する検索システム。
【請求項１１】
前記類似度を判断する手段は、前記三次元物体の特徴量と、予め得られた複数の前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と複数の前記三次元物体モデルとの類似度を判断し、
前記類似度が高い順に、複数の前記三次元物体モデルを順位付けする手段を更に有する、請求項１０に記載の検索システム。
【請求項１２】
前記ボクセル表現を作成する手段は、前記三次元物体の三次元物体モデルに対して複数の姿勢正規化処理を行う、請求項１０又は１１に記載の検索システム。
【請求項１３】
前記姿勢正規化処理は前記三次元物体モデルを構成する三角面上にランダムな点を生成し、それを質点として主成分分析を行ない、主軸を求めて正規化を行なう第１の姿勢正規化処理と、前記三次元物体モデルの面上に生成したランダムな点と、それに近い三角形の２点との法線の分布をもとに主軸を求めて正規化を行なう第２の姿勢正規化処理とを含む、請求項１３に記載の検索システム。
【請求項１４】
三次元物体を、予め用意した複数のカテゴリーの何れかに分類するための分類システムであって、
前記三次元物体からボクセル表現を作成する手段と、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解する手段と、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求める手段と、
該複数のボクセル部分の複数のスペクトルから、前記三次元物体の第１特徴量を求める手段と、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第２特徴量を求める手段と、
前記第１特徴量と前記第２特徴量を複合することにより前記三次元物体の特徴量を求める手段と、
前記三次元物体の特徴量と、前記複数のカテゴリーにそれぞれ予め付与された特徴量とを比較することにより、前記三次元物体を前記複数のカテゴリーのうち最も特徴量が類似するカテゴリーに分類する手段と、を含む分類システム。
【請求項１５】
前記ボクセル表現を作成する手段は、前記三次元物体の三次元物体モデルに対して複数の姿勢正規化処理を行う、請求項１４に記載の分類システム。
【請求項１６】
前記姿勢正規化処理は前記三次元物体モデルを構成する三角面上にランダムな点を生成し、それを質点として主成分分析を行ない、主軸を求めて正規化を行なう第１の姿勢正規化処理と、前記三次元物体モデルの面上に生成したランダムな点と、それに近い三角形の２点との法線の分布をもとに主軸を求めて正規化を行なう第２の姿勢正規化処理とを含む、請求項１５に記載の分類システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元物体モデルを検索するための方法、コンピュータプログラム及びシステム、及び、三次元物体を分類するための方法、コンピュータプログラム及びシステムに関するものである。
【背景技術】
【０００２】
三次元物体モデルの検索方法として各種の方法が知られている。
D2:  D2はOsadaらの研究（非特許文献１）で最も高い検索精度を得た特徴量である。三次元物体の面上にランダムな点群を生成し、全２点間のユークリッド距離の頻度を示すヒストグラムを特徴量とする。特徴量間の距離は、求めたヒストグラムを一次元ベクトルと考えて計算したマンハッタン距離である。
Spherical Harmonics Descriptor（SHD）:  SHDはKazhdanらにより提案された手法である（非特許文献２）。ボクセル化した三次元物体を球面調和関数変換し、得られたパワースペクトルの低周波部分を特徴量とする。特徴量間の距離は、求めたパワースペクトルを1次元ベクトルと考えて計算したユークリッド距離である。
Light Field Descriptor（LFD）:  LFDはChenらにより提案された手法である（非特許文献３参照）。12面体の頂点を視点とし、それを回転させながら、多数の視点から三次元物体のシルエット画像を生成する。生成したシルエット画像のツェルニケモーメントとフーリエスペクトルを計算し特徴量とする。特徴量間の距離は、12面体の各頂点と全ての回転における組み合わせで最小L1距離を計算したものである。
Hybrid Descriptor（DSR472）:  DSR472はVranicの研究で最も高い検索精度を得た特徴量である（非特許文献４参照）。Vranicが考案した、デプスバッファ特徴ベクトル、シルエット特徴ベクトル、重心から任意の方向にベクトルを放つことで得られるRay特徴ベクトルの3つを組み合わせた特徴量である。特徴量間の距離は、複合特徴量を一次元ベクトルと考えてマンハッタン距離を計算したものである。
MFSD (Multi-Fourier Spectra Descriptor):  MFSDは本発明の発明者らが提案した手法である（特許文献１参照）。MFSDは、Depth Buffer画像・シルエット画像・輪郭画像・ボクセル表現の四種類の形状表現から求めたフーリエスペクトルからなる特徴量である。それまでで最も検索精度が高いといわれていたDSR472法を凌駕する検索手法として提案したものである。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第５０２４７６７号公報
【特許文献２】特願２０１０−１３４５８９号
【非特許文献】
【０００４】
【非特許文献１】R.Osada, T.Funkhouser, B.Chazelle, D.Dobkin, Shape Distributions, ACM,TOG,21(4),pp.807-832,2002.
【非特許文献２】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.
【非特許文献３】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.
【非特許文献４】D.Vranic, 3D Model Retrieval, Ph.D.thesis, University of Leipzig,2004.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記のMFSDは、四種類の形状表現から特徴量を求めることにより、DSR472法を凌駕する検索精度を達成することができた。しかしながら、特徴量を求める場合に、データが肥大化するという問題があった。この問題の解決策として本発明者らは、LDP（線形拡散射影）法を提案している（特許文献２参照）。しかしながら、このLDP法は検索時に扱うデータ量を削減できるものの、多量のデータによる事前学習を必要とする点で、なお改善の余地があった。
【０００６】
本発明は前記問題を解決するためになされたものであって、その目的は、多量のデータによる事前の学習を必要とすることなく、高い精度で三次元物体モデルの検索を行い得る方法及びシステム、及び、高い精度で三次元物体の分類を行い得る方法及びシステムを提供することにある。
【課題を解決するための手段】
【０００７】
本発明者らは前記課題を解決するために鋭意検討を重ねた結果、下記のように本発明の各局面に想到した。
【０００８】
即ち、本発明の第１の局面による三次元物体に類似した三次元物体モデルを検索する三次元物体モデルの検索方法は、
前記三次元物体からボクセル表現を作成するステップと、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解するステップと、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求めるステップと、
前記複数のボクセル部分の複数のスペクトルから、前記三次元物体の第１特徴量を求めるステップと、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第２特徴量を求めるステップと、
前記第１特徴量と前記第２特徴量を複合することにより前記三次元物体の特徴量を求めるステップと、
前記三次元物体の特徴量と、予め得られた前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と前記三次元物体モデルとの類似度を判断するステップと、を有する検索方法である。
【０００９】
このような構成の検索方法は、ＭＦＳＤでは用いていたシルエット特徴量及び輪郭特徴量を用いないため、ＭＦＳＤよりも検索用のインデックスがコンパクトである。しかも、ＬＤＰのような事前学習の必要もないという利点を有する。また、ボクセル表現を各ボクセル部分に重複分解することで、ボクセル部分間をまたぐ形状の連続的変化を捉えることができ、三次元物体の輪郭等の形状をより詳細かつ高精度に把握することが可能となる。更には、重複分解したボクセル部分ごとに計算したフーリエスペクトルを特徴量として用いるため、三次元物体の外見的な形状的特徴だけでなく、三次元空間中にどのような形状がどこにあるかという空間的特徴をもより高精度に捉えることが可能となる。そのため、後に詳述する本発明者らの行った検証実験においても示されているように、本願発明による検索方法の検索精度はＭＦＳＤより高く、ＬＤＰと同等またはそれ以上である。
【００１０】
本発明の第２の局面によれば、前記類似度を判断するステップは、前記三次元物体の特徴量と、予め得られた複数の前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と複数の前記三次元物体モデルとの類似度を判断し、検索方法は、前記類似度が高い順に、複数の前記三次元物体モデルを順位付けするステップを更に有する。
このような構成によれば、検索対象としての三次元物体と類似度の高いものから順に複数の三次元物体モデルに対して順位付けを行うことができ、ユーザは、この順位情報を考慮に入れた上で検索結果を考察し、利用することができるので利便性が高い。
【００１１】
本発明の第３の局面によれば、前記ボクセル表現を作成するステップは、前記三次元物体の三次元物体モデルに対して複数の姿勢正規化処理（即ち、複数の正対化処理）を行う。
このような構成とすることで、三次元物体モデルの位置や向きが製作者やツール等によって異なる場合であっても、検索精度の低下を防止することができる。また、複数の姿勢正規化処理を行うことで、より好適な姿勢正規化処理結果を用いることができる。
【００１２】
本発明の第４の局面によれば、前記姿勢正規化処理は前記三次元物体モデルを構成する三角面上にランダムな点を生成し、それを質点として主成分分析を行ない、主軸を求めて正規化を行なう第１の姿勢正規化処理と、前記三次元物体モデルの面上に生成したランダムな点と、それに近い三角形の２点との法線の分布をもとに主軸を求めて正規化を行なう第２の姿勢正規化処理とを含む。このような構成によれば、好適な姿勢正規化処理を行うことができる。
【００１３】
本発明の第５の局面による三次元物体を、予め用意した複数のカテゴリーの何れかに分類するための分類方法は、
前記三次元物体からボクセル表現を作成するステップと、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解するステップと、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求めるステップと、
該複数のボクセル部分の複数のスペクトルから、前記三次元物体の第１特徴量を求めるステップと、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第２特徴量を求めるステップと、
前記第１特徴量と前記第２特徴量を複合することにより前記三次元物体の特徴量を求めるステップと、
前記三次元物体の特徴量と、前記複数のカテゴリーにそれぞれ予め付与された特徴量とを比較することにより、前記三次元物体を前記複数のカテゴリーのうち最も特徴量が類似するカテゴリーに分類するステップと、を含む分類方法である。
【００１４】
このような構成の分類方法によれば、第１の局面について述べた理由と同様の理由により、三次元物体の分類用のインデックスがコンパクトであり、しかも分類の精度が高いという利点を有する。
【００１５】
本発明の第６の局面による三次元物体に類似した三次元物体モデルを検索する三次元物体モデルの検索システムは、
前記三次元物体からボクセル表現を作成する手段と、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解する手段と、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求める手段と、
該複数のボクセル部分の複数のスペクトルから、前記三次元物体の第１特徴量を求める手段と、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第２特徴量を求める手段と、
前記第１特徴量と前記第２特徴量を複合することにより前記三次元物体の特徴量を求める手段と、
前記三次元物体の特徴量と、予め得られた前記三次元物体モデルの特徴量とを比較することにより、前記三次元物体と前記三次元物体モデルとの類似度を判断する手段と、を有する検索システムである。
このような構成の検索システムは、前記第１の局面による検索方法と同様の利点を有する。
【００１６】
本発明の第７の局面による三次元物体を、予め用意した複数のカテゴリーの何れかに分類するための分類システムは、
前記三次元物体からボクセル表現を作成する手段と、
前記ボクセル表現の一部を構成する複数のボクセルであって、所定の大きさの三次元的なウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、続いて、前記ウィンドウを所定の方向へ所定の距離だけ移動させて、前記ウィンドウ内に存在する複数のボクセルをボクセル部分として抽出し、以下同様に複数のボクセル部分を抽出し、二番目以降に抽出するボクセル部分が先に抽出したいずれかのボクセル部分の一部のボクセルと重複するように順次抽出することにより、前記ボクセル表現を重複分解する手段と、
前記ボクセル部分ごとに三次元フーリエ変換を適用してスペクトルを求める手段と、
該複数のボクセル部分の複数のスペクトルから、前記三次元物体の第１特徴量を求める手段と、
前記三次元物体を奥行バッファ法により投影した二次元画像であって、該二次元画像の中心から離れるに従って画素の濃淡が強調されるように投影した該二次元画像に対して二次元フーリエ変換を適用してスペクトルを求めることにより、前記三次元物体の第２特徴量を求める手段と、
前記第１特徴量と前記第２特徴量を複合することにより前記三次元物体の特徴量を求める手段と、
前記三次元物体の特徴量と、前記複数のカテゴリーにそれぞれ予め付与された特徴量とを比較することにより、前記三次元物体を前記複数のカテゴリーのうち最も特徴量が類似するカテゴリーに分類する手段と、を含む分類システムである。
このような構成の分類システムは、前記第５の局面による分類方法と同様の利点を有する。
【図面の簡単な説明】
【００１７】
【図１】図１は、本発明の第１実施形態による検索システムを示すブロック図である。
【図２】図２は、ポイントＳＶＤにおける鏡像が異なる例を示す図である。
【図３】図３は、ノーマルＳＶＤにおける演算原理を示す図である。
【図４】図４は、ボクセル表現の例を示す図である。
【図５】図５は、ボクセルの重複分解の概念を示す図である。
【図６】図６は、ボクセルの重複分解を行う場合と行わない場合の比較図である。
【図７】図７は、デプスバッファ画像の例を示す図である。
【図８】図８は、周辺輝度強調により補正されたデプスバッファ画像(PEI画像)の例を示す図である。
【図９】図９は、周辺輝度強調により補正されたデプスバッファ画像を極座標変換した画像である。
【図１０】図１０は、第１実施形態による検索システムの効果を示すグラフである。
【図１１】図１１は、第１実施形態による検索システムの効果を示す別のグラフである。
【図１２】図１２は、本発明の第２実施形態による分類システムを示すブロック図である。
【発明を実施するための形態】
【００１８】
（第１実施形態）
次に、本発明を具体化した第１実施形態に係る三次元物体モデルを検索するための検索システム１について、図面を参照しながら説明する。
図１は本実施形態の検索システム１の構成を示すブロック図である。検索システム１は汎用的なコンピュータ装置からなり、その機能をブロックで表すと図１のようになる。即ち、本実施形態の検索システム１は制御装置３、記憶部１０、入出力部２０、姿勢正規化処理部３０、特徴量演算部４０及び特徴量比較部５０から構成される。
【００１９】
制御装置３は記憶部１０のプログラム記憶部１１から制御用プログラムを読み出して、このプログラムにしたがって各要素を制御する。記憶部１０の既知三次元物体モデルの特徴量データベース１３には、以下に説明する方法で特徴量の演算された三次元物体モデルがその特徴量とともに保存されている。三次元物体モデルは後述する姿勢正規化処理（即ち、正対化処理）が施され、かつ正規化されている。
記憶部１０は更に、ポイントＳＶＤ（Point SVD）化データ記憶部１５、及び、ノーマルＳＶＤ(Normal SVD)化データ記憶部１７を有する。
【００２０】
入出力部２０はキーボード／マウス２１、ディスプレイ２３、プリンタ２５、データ入出力インターフェース２７及び通信インターフェース２９を備えている。検索対象である三次元物体のデータ（即ち、モデル化された三次元物体）はデータ入出力インターフェース２７からシステム内に取り込むことができる。通信インターフェース２９はシステムをインターネットへ接続する。
【００２１】
姿勢正規化処理部３０は、検索対象である三次元物体を姿勢正規化処理し、更に大きさをそろえるために正規化する。姿勢正規化処理部３０にはポイントＳＶＤ部３１とノーマルＳＶＤ部３３があり、それぞれ異なる手法で三次元物体のデータを姿勢正規化処理する。正規化部３５は三次元物体の大きさの任意性を解決するものである。
ポイントＳＶＤ部３１で姿勢正規化されかつ正規化部３５で正規化された三次元物体のデータは記憶部１０のポイントＳＶＤ化データ記憶部１５に一時保存され、ノーマルＳＶＤ部３３で姿勢正規化されかつ正規化部３５で正規化された三次元物体のデータは記憶部１０のノーマルＳＶＤ化データ記憶部１７に一時保存される。
【００２２】
以下、ポイントＳＶＤについて詳細に説明する。
ポイントＳＶＤでは、三次元物体モデル（又はモデル化された三次元物体）を構成する三角面上にランダムな点を生成する。これには、Osadaらの手法を用いる(R.Osada, T.Funkhouser, B.Chazelle, D.Dobkin, Shape Distributions, ACM,TOG,21(4), pp.807-832, 2002.)。生成する点の座標を、三角面の頂点の座標ABCと擬似乱数ｒ１、ｒ２を用いて、下記式１で決める。
【数１】
2014120026.tif 000003
本実施形態では擬似乱数にメルセンヌTwister乱数を用いた。また、生成する点群数は全体でＬ個とする（Ｌは十分に大きい数とする）。実施例ではＬ=32768個である。こうして生成された点群より三次元物体モデルの重心を求める。重心ｍＩが原点となるよう平行移動することで、位置の任意性の問題を解決する。実施例での点群データ行列は以下の式で表現される。
【数２】
2014120026.tif 000004
次に、点群行列Ｐを特異値分解することで回転行列Ｒを得る。
【数３】
2014120026.tif 000005
【００２３】
回転行列Ｒにより、点群を回転させる。これにより、主軸が三次元空間のｘ軸・ｙ軸・ｚ軸に沿うような回転をする。
【数４】
2014120026.tif 000006
最後に、三次元物体モデルの鏡像を決める。軸が同じになっても、鏡像が異なれば特徴量は変化してしまう（図２参照）。
モデルの鏡像行列Ｆは、Ｌ個（実施例では、Ｌ=32768個）の点群の場合、以下のように計算する。
【数５】
2014120026.tif 000007
以上の計算により求めた重心ｍＩ、回転行列Ｒ、鏡像行列Ｆにより、モデル頂点Ｖを平行移動・回転させて姿勢正規化を完成する。
【数６】
2014120026.tif 000008
【００２４】
ポイントＳＶＤと同様の姿勢正規化手法が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乱数を用いることと、鏡像の決定に中心からの距離を用いていることである。
【００２５】
次に、ノーマルＳＶＤについて詳細に説明する。
基本的な計算方法はポイントＳＶＤと同様である。ノーマルＳＶＤでは点群を生成するときに、生成した点と元になった三角形の頂点の最も近い２点との法線を質点として計算する（図３）
まず、法線ベクトルｎの平均を求める。Ｌ個（実施例では、Ｌ=32768個）での法線ベクトルの平均は以下のように求める。
【数７】
2014120026.tif 000009
次に法線ベクトル行列Ｎを特異値分解し、回転行列Ｒを求める。
【数８】
2014120026.tif 000010
【００２６】
最後に、回転させた点群を元に、ポイントＳＶＤと同様にして鏡像決定行列Fを計算する。
【数９】
2014120026.tif 000011
以上により、姿勢正規化は完了する。頂点行列Ｖの定義はポイントＳＶＤと同様である。
【００２７】
このようにして姿勢正規化された各モデルはBounding Sphere法により正規化される。
ここに、Bounding Sphere法は、半径１の単位球であり、これに姿勢正規化された検索対象の三次元物体モデルが収まるようにする。具体的な計算方法としては、三次元物体モデルの全頂点と重心との距離の最大値で各頂点の座標値を割る。
【００２８】
このように２種類の姿勢正規化法を用いる理由は以下の通りである。即ち、凹凸の多い物体の姿勢正規化に有効とされるPoint SVDと、角張った形状の姿勢正規化に有効とされるNormal SVDとを備えることで、より多様な三次元物体の姿勢正規化に対応でき、頑強性が高められるからである。
【００２９】
特徴量演算部４０は、重複分解ボクセル特徴量演算部４１、デプスバッファ特徴量演算部４２及び複合部４３を備えてなる。
最初に、重複分解ボクセル特徴量演算部４１のボクセル表現作成部４１１が、姿勢正規化処理部３０にて姿勢正規化及び正規化を経た三次元物体のデータからボクセル表現を作成する。ボクセル表現とは例えば図４のように、三次元物体を立方体の集合で表したものである。本実施形態のボクセル表現作成部４１１においては、三次元物体の面上にランダムな点群を生成し、それらをＭ×Ｍ×Ｍの空間に量子化することで、三次元物体をボクセル表現に変換する。このとき、ボクセル表現の非０要素の値は、ボクセル空間の中心からのユークリッド距離とする。すなわち、すべてのボクセルは０または正の実数値をとることを意味する。実施例では、Ｍ＝６４とした。
【００３０】
次に、三次元物体から生成したボクセル表現を、重複分解部４１３において、一定の大きさを有する三次元のウィンドウにて重複的に抽出し、各々を「ボクセル部分」として抽出する。
ボクセルの重複的な抽出について詳述すると、三次元的なウィンドウの寸法（即ち三次元空間に占める大きさ）は、ウィンドウ内に一度に複数のボクセルが含まれ得るように設定される。そして、ウィンドウをＭ×Ｍ×Ｍの空間内で三次元物体のボクセル表現に重ね合わせ、ウィンドウ内に存在する複数のボクセルを一つのボクセル部分として抽出する。
【００３１】
次に、前記空間内で、ウィンドウを所定方向に所定の距離だけ移動させる。そして、ウィンドウ内に存在する複数のボクセルを、別のボクセル部分として抽出する。このように、ウィンドウを移動させながら、順次、ボクセル部分を抽出していく。その際、二番目以降に抽出されるボクセル部分と先に抽出されたボクセル部分との間で、一部のボクセルが重複するように、即ち、共通のボクセルを含むように、抽出する。ただし、ボクセル部分同士が完全一致しないようにする。このように、ボクセル表現を、複数のボクセル部分であって、それらの一部のボクセルが重複するような複数のボクセル部分として抽出することを、「ボクセル表現を重複分解する」と呼ぶこととする。
【００３２】
ボクセル表現の重複分解について、図５の例により説明する。図５の例では、分かりやすさのため、ボクセル空間を二次元で表現している。この例では、ボクセル空間が６４個×６４個のボクセルからなり、ウィンドウの大きさは３２個×３２個のボクセルに相当する。まず図５（Ａ）において３２個×３２個のボクセルを第１番目のボクセル部分として抽出する。次に、図５（Ｂ）のように、ウィンドウを１６個のボクセルに相当する距離だけ右方向に移動させ、その場所においてウィンドウに囲まれる３２個×３２個のボクセルを第２番目のボクセル部分として抽出する。図５（Ａ）、５（Ｂ）より、第１番目のボクセル部分と第２番目のボクセル部分とでは、全体として同一ではないが、その一部のボクセルが重複していることが分かる。
【００３３】
そして更に図５（Ｂ）から図５（Ｃ）へは、同じくウィンドウを１６個のボクセルに相当する距離だけ右方向に移動させる。図５（Ｃ）から図５（Ｄ）へは、３２個のボクセルに相当する距離の左方向への移動と、１６個のボクセルに相当する距離の下方向への移動を合わせた移動を行っている。そして更に順次、図５（Ｅ）〜（Ｉ）のようにウィンドウを右方向、左斜め下方向、右方向、・・・というように所定の方向に所定の距離ずつずらしていきながら、ボクセル空間の全体を、一部が重複し合う複数のボクセル部分として抽出していく（即ち、重複分解する）。このように複数のボクセル部分を、その一部が重複し合うように抽出することで、データの冗長さを犠牲にしつつも、特徴量の連続的変化を高精度に捉えることが可能となる。
【００３４】
なお、ウィンドウを「所定の方向」に「所定の距離」だけ移動させるという場合、それら「所定の方向」と「所定の距離」は終始一定のものには限られず、所定の取り決めに従って、途中で別の方向や異なる距離に切り替えられるものとして良い。例えば、ウィンドウがＭ×Ｍ×Ｍの空間の端まで進んだ場合には、Ｍ×Ｍ×Ｍの空間の逆の端に戻り、そこから、既にボクセルを抽出した範囲と一部重複するようにボクセルの抽出を継続するようにしても良い。あるいは、到達した端から折り返して、既にボクセルを抽出した範囲と一部重複するように抽出を継続するようにしても良い。その他、「所定の方向」及び「所定の距離」についての取り決めは、Ｍ×Ｍ×Ｍの空間内においてウィンドウを移動させ得る限り、任意のものを採用することができる。
【００３５】
ボクセル空間を，単に複数のボクセル部分に分解するのではなく、重複させて分解するのは、ボクセル部分をまたぐ形状の連続的変化を捉えるためである。図６は，重複分解を行う場合（Ａ）と行わない場合（Ｂ）とで、捉えられる形状的特徴の違いを表したものである。重複分解を行う場合（Ａ）では、中央の円形を捉えることができるが、重複分解を行わない場合（Ｂ）では、この円形は分断され、中央に円形があるという情報は、特徴量に反映されない。
【００３６】
次に、抽出したボクセル部分ごとに、次式によりフーリエ変換部４１５にてパワースペクトルを得る。
【数１０】
2014120026.tif 000012
ここでは、各ボクセル部分の大きさをＮ×Ｎ×Ｎとした。Ｎはボクセルの数を表す。また、１≦ｐ，ｑ，ｒ≦Ｎである。フーリエスペクトルの高周波成分には、形状の詳細情報やノイズが現れる。そこで、類似検索のため、本実施形態では、１≦ｐ，ｑ，ｒ≦Ｂの低周波数成分fcellを用いる。実施例では、Ｂ＝８とした。
【数１１】
2014120026.tif 000013
結局全体はＢ３＝ＣＭＡＸ次元となる。実施例では、ＣＭＡＸ＝５１２（＝８３）となる。
次に、ボクセル部分から計算したフーリエスペクトルの低周波成分を、全体総和で正規化する。
【数１２】
2014120026.tif 000014
これらボクセル部分ごとに求めたフーリエスペクトルを並べたものが、重複分解ボクセル特徴量fDVDであり、高密度ボクセルスペクトル記述子（Dense Voxel Spectrum Descriptor: DVD）とも呼ぶこととする。実施例では、ＤＶＤ＿ＭＡＸ＝２７とした。
【数１３】
2014120026.tif 000015
【００３７】
重複分解ボクセル特徴量fDVDは、ボクセル空間を、所定の大きさの複数のボクセル部分に重複分解し、ボクセル部分ごとに計算したフーリエスペクトルを並べたものである。そのため、このままでは、重複分解ボクセル特徴量fDVDの次元数は、（（Ｍ−Ｎ）／Ｔ＋１）３×Ｂ３となり、実施例の数字（実施例では、Ｔ＝１６、Ｎ＝３２とする）を代入すると、１３，８２４次元と大きなものとなってしまう。そこで、各ボクセル部分から計算した、低周波数成分のフーリエスペクトルＢ３＝８３＝ＣＭＡＸ＝５１２次元を、主成分分析により、Ｋ次元に削減する。実施例では、上位主成分で、寄与率の高かった次元として、Ｋ＝２０とした。その後、次元削減したフーリエスペクトルを並べ、全体をＬ１ノルム（マンハッタン距離）で正規化したものを、あらためて重複分解ボクセル特徴量fDVDとする。重複分解ボクセル特徴量fDVDの最終的な次元数は、（（Ｍ−Ｎ）／Ｔ＋１）３×Ｋで、実施例の数字を代入すると、５４０次元となる。
【００３８】
デプスバッファ特徴量演算部４２の二次元画像形成部４２１は、姿勢正規化処理部３０にて姿勢正規化及び正規化を経た三次元物体のデータに基づき、デプスバッファ特徴量の演算に用いる二次元画像（ディプスバッファ画像）を形成する。ここに、デプスバッファ画像は、任意の視点から三次元物体モデルの表面までの距離（深さ）を二次元画像で表したものである。
実施例では、三次元物体モデルの直交６方向からの視点で２５６×２５６の画素をもつデプスバッファ画像を形成する（図７参照）。
デプスバッファ画像が持つｚ値（深さ）は[0，255]の整数を取り、距離が遠いほど値は小さく、近いほど値は大きい。また、背景は０である。
【００３９】
次に補正部４２３は、デプスバッファ画像に中心からの距離情報を埋め込むことにより、これを補正する。具体的には、デプスバッファ画像の各画素の輝度をＩ（ｘ、ｙ）としたとき、デプスバッファ画像の中心からの距離をｒとすると、画素サイズを２５６×２５６とした実施例の場合、補正された画像の各座標の輝度Ｉ´（ｘ，ｙ）は、次のように表される（実施例では、Ｒ＝１２８）。
【数１４】
2014120026.tif 000016
補正された画像を周辺強調画像（Periphery Enhanced Image (PEI)）とよぶことがある。補正された画像を図８に示す。図８及び式１４より、補正された二次元画像は画像の中心から離れるしがたって画素の濃淡が強調されていることがわかる。また、画像の中心に近づくにしたがって画素が暗くなることもわかる。
最後に、補正されたデプスバッファ画像を直交座標から極座標へと変換する。極座標変換した画像を図９に示す。極座標は、横軸がｒ、縦軸が回転角θを表す。画像の大きさは、実施例の場合、Ｒ×Θ＝１２８×５１２（ただし、Ｒ＝１２８、Θ＝５１２）となる。
【００４０】
次にフーリエ変換部４２５が極座標変換した画像をフーリエ変換し、フーリエ係数ｇρφを得る。
【数１５】
2014120026.tif 000017
ここに、ρは横軸の空間周波数、φは縦軸の空間周波数を表し、０≦ρ＜１２８、０≦φ＜５１２である。このフーリエ係数の大きさがパワースペクトルである。極座標では、直交座標における回転が平行移動となり、フーリエ変換により得られるパワースペクトルは平行移動不変の性質を持つ。姿勢正規化に誤りがある場合に、向きの任意性を若干緩和できる。
以上の処理により得られた、６画像分のパワースペクトルの低周波成分のみ取出したものをデプスバッファ特徴量ｆDepth Bufferとする。次式の通り、デプスバッファ特徴量ｆDepth Bufferは、（Ｎ１＋１）×（Ｎ２＋１）次元の特徴量次元である。なお、実施例においては、Ｎ１＝７、Ｎ２＝３１とした。
【数１６】
2014120026.tif 000018
低周波成分のみを特徴量として使用するのは、類似検索の場合、形状の微細な相違を表す高周波成分を無視するためである。
複合部４３は、重複分解ボクセル特徴量演算部４１により得られた重複分解ボクセル特徴量fDVDと、奥行バッファ特徴量演算部４２により得られた奥行バッファ特徴量ｆDepth Bufferを複合する。
【００４１】
特徴量比較部５０は、複合部４３で得られた最終的な距離をデータベースに保存されている距離と比較する。複合特徴量の相違度計算には、マンハッタン距離を用いる。
【数１７】
2014120026.tif 000019
また、正規化手法の選択は、Point SVDにより正規化した三次元物体から生成した相違度dpointと、Normal SVDにより正規化した三次元物体から生成した相違度dnormalとで、値が小さいものを、最適な正規化手法として選択する。次式で、最終的な相違度を計算する。
【数１８】
2014120026.tif 000020
【００４２】
そして、特徴量比較部５０は、最も距離の短い三次元物体モデルをディスプレイに表示したり、あるいは、距離の近いものから順に並べてディスプレイへ表示したりすることによって、検索結果を出力する。
【００４３】
次に、第１実施形態の検索システム１の効果を、実施例により説明する。ＰＳＢ(Princeton Shape Benchmark)を用いた再現率−適合率曲線は、図１０のような結果となった。図１０の縦軸「precision」は検索精度（誤検索の少なさ）を表し、横軸「recall」は再現率（検索漏れの少なさ）を表す。図１０において、実線アが検索システム１による効果を示し、実線は、実線イ、ウ、エ、オ、カ、キ、クはそれぞれ比較対象として、重複分解ボクセル特徴量のみを用いた場合（即ち、第１実施形態においてデプスバッファ特徴量を複合せずに、式１７、式１８の計算を行った場合）、MFSD、DESIRE（ドイツ、Vranicらによる複合特徴量、2004年）、LFD、SHD、SPRH（ドイツ航空センターWahlらの特徴量、2003年）、D2を表す。これらの比較対象のいずれと比べても、本願発明による手法が上回っていることが分かる。
【００４４】
一方、ＬＤＰ法との比較を図１１に示す。本願発明即ち、重複分解ボクセル特徴量とデプスバッファ特徴量の併用の効果は実線ａにより示す。ＬＤＰ法は、任意の手法で得られた特徴量を次元削減するものであり、特徴量算出手法と独立に適用できるため、図１１では、ＭＦＳＤ＋ＬＤＰ（実線ｂ）という形で比較した。実線ｃはＭＦＳＤ単独による効果、実線ｄは重複分解ボクセル特徴量単独による効果を示す。
ＬＤＰは特徴量が得られた後のデータに対して学習を行い次元削減するものであり一般に高性能となるが、図１１によれば、本願発明の重複分解ボクセル特徴量とデプスバッファ特徴量を併用する手法により、ＬＤＰにほぼ匹敵する検索性能が得られることが分かる。
【００４５】
（第２実施形態）
次に、本発明の第２実施形態について、図１２を参照して説明する。
図１２に示す第２実施形態の三次元物体を分類するための分類システム１０１は、第１実施形態の特徴量比較部５０に代えて、分類部６０を有する。また、記憶部１０は、第１実施形態の既知三次元物体モデルの特徴量データベース１３に代えて、カテゴリー特徴量記憶部１３１を有する。カテゴリー特徴量記憶部１３１は、予め、複数の三次元物体モデルをそれぞれ含む複数のカテゴリー（例えば、自動車、動物、昆虫、あるいは更に詳細に、四輪自動車、オートバイ、バス、犬、猫、ウサギ、カブトムシ、テントウムシ、・・・等）を記憶しており、各カテゴリーには、それぞれ各カテゴリーの三次元物体モデルを代表する特徴量（例えば、各カテゴリーの三次元物体モデルの平均的な特徴量）が付与されている。その他の構成は図１の検索システム１と同じである。
【００４６】
分類システム１０１の特徴量演算部４０は、第１実施形態の検索システム１と同じ方法により、モデル化された三次元物体の複合特徴量を求める。そして、分類部６０は、複合特徴量と、前記複数のカテゴリーにそれぞれ予め付与された特徴量を比較することにより、三次元物体を複数のカテゴリーのうち最も特徴量が類似するカテゴリーに分類する。分類結果は入出力部２０を介して出力される。
これにより、高い精度で三次元物体をカテゴリーに分類することができる。
【００４７】
本明細書の中で明示した論文、公開特許公報、特許公報などの内容は、その全ての内容を援用によって引用することとする。
【符号の説明】
【００４８】
１  三次元物体モデルの検索システム、  １０  記憶部、  ２０  入出力装置、３０  姿勢正規化処理部、４０  特徴量演算部、５０  特徴量比較部、  ６０  分類部、  １０１  三次元物体の分類システム
【図１】
2014120026.tif 000021
【図２】
2014120026.tif 000022
【図３】
2014120026.tif 000023
【図４】
2014120026.tif 000024
【図５】
2014120026.tif 000025
【図６】
2014120026.tif 000026
【図７】
2014120026.tif 000027
【図８】
2014120026.tif 000028
【図９】
2014120026.tif 000029
【図１０】
2014120026.tif 000030
【図１１】
2014120026.tif 000031
【図１２】
2014120026.tif 000032