(57)【要約】      （修正有）【課題】不完全な三次元物体からでも高精度な検索を実現する三次元形状検索方法及び三次元形状検索システムを提供する。【解決手段】本発明に係る三次元形状検索方法は、三次元形状データベースに対し、三次元形状モデルの一部または全体を検索質問とし、前処理として三次元物体を点群に変換し、多視点レンダリングにより部分形状を抽出し、特徴量抽出として該部分形状の姿勢精機化を行って、多視点からの法線ヒストグラムを用いて第一の特徴ベクトルを求め、前記検索質問に対して、三次元物体を点群に変換し、多視点レンダリングにより部分形状を抽出し、特徴量抽出として該部分形状の姿勢正規化を行って、多視点からの法線ヒストグラムを用いて第二の特徴ベクトルを求め、検索時には、前記第一の特徴ベクトル及び第二の特徴ベクトル間の相違度を求めて、該相違度の値により類似として選別することを特徴とする。【選択図】図１
2018136642.tif 000002
【特許請求の範囲】
【請求項１】
三次元形状データベースに対し、三次元形状モデルの一部または全体を検索質問とし、該検索質問における部分の形状に基づいて、類似する三次元形状を選び出す三次元形状検索方法であって、
前処理として三次元物体を点群に変換し、多視点レンダリングにより部分形状を抽出し、
特徴量抽出として該部分形状の姿勢正規化を行って、多視点からの法線ヒストグラムを用いて第一の特徴ベクトルを求め、
前記検索質問に対して、三次元物体を点群に変換し、多視点レンダリングにより部分形状を抽出し、
特徴量抽出として該部分形状の姿勢正規化を行って、多視点からの法線ヒストグラムを用いて第二の特徴ベクトルを求め、
検索時には、前記第一の特徴ベクトル及び第二の特徴ベクトル間の相違度を求めて、該相違度の値により類似として選別することを特徴とする三次元形状検索方法。
【請求項２】
前記検索質問として、スキャンにより数値化された三次元形状データの一部または全体を用いることを特徴とする請求項１に記載の三次元形状検索方法。
【請求項３】
前記検索質問として用いる三次元形状データであって、
部分形状を抽出するための視点を決定し、
該視点からレンダリングにより生成した二次元画像及び点群へ変換した三次元物体を用い、平行投影により部分形状を抽出し、
前記二次元画像から前記三次元物体に含まれる点が可視部分であるか否かを判定して前記部分形状の法線ベクトルを整列化し、
スキャンした三次元物体の部分形状を疑似的に点群から生成することを特徴とする請求項２に記載の三次元形状検索方法。
【請求項４】
前記特徴量抽出は点群特徴量であって、
対象となる三次元物体に対し、三次元空間上の点群に対する特異値分解を行い、
視線ベクトルによる該三次元物体の主軸を固定し、
二次元投影平面上の点群に対する特異値分解により該三次元物体の向きの正規化し、
向きが正規化された該三次元物体に対し、格子状にブロックを設定して分割して、該ブロックごとの法線方向ヒストグラムを求め、その値を連結して特徴量とすることを特徴とする請求項１ないし３のいずれかに記載の三次元形状検索方法。
【請求項５】
三次元形状データベースに対し、三次元形状モデルの一部または全体を検索質問とし、該検索質問における部分の形状に基づいて、類似する三次元形状を選び出す三次元形状検索システムであって、
前処理として三次元物体を点群に変換する手段と、
多視点レンダリングにより部分形状を抽出する手段と、
特徴量抽出として該部分形状の姿勢正規化を行って、多視点からの法線ヒストグラムを用いて第一の特徴ベクトルを求める手段と、
前記検索質問に対して、三次元物体を点群に変換する手段と、
多視点レンダリングにより部分形状を抽出する手段と、
特徴量抽出として該部分形状の姿勢正規化を行って、多視点からの法線ヒストグラムを用いて第二の特徴ベクトルを求める手段と、
検索時には、前記第一の特徴ベクトル及び第二の特徴ベクトル間の相違度を求めて、該相違度の値により類似として選別する手段と、を備えることを特徴とする三次元形状検索システム。
【請求項６】
前記検索質問として、スキャンにより数値化された三次元形状データの一部または全体を用いることを特徴とする請求項５に記載の三次元形状検索システム。
【請求項７】
前記検索質問として用いる三次元形状データであって、
部分形状を抽出するための視点を決定する手段と、
該視点からレンダリングにより生成した二次元画像及び点群へ変換した三次元物体を用い、平行投影により部分形状を抽出する手段と、
前記二次元画像から前記三次元物体に含まれる点が可視部分であるか否かを判定して前記部分形状の法線ベクトルを整列化し、
スキャンした三次元物体の部分形状を疑似的に点群から生成する手段と、を備えることを特徴とする請求項６に記載の三次元形状検索システム。
【請求項８】
前記特徴量抽出は点群特徴量であって、
対象となる三次元物体に対し、三次元空間上の点群に対する特異値分解を行う手段と、
視線ベクトルによる該三次元物体の主軸を固定する手段と、
二次元投影平面上の点群に対する特異値分解により該三次元物体の向きの正規化する手段と、
向きが正規化された該三次元物体に対し、格子状にブロックを設定して分割して、該ブロックごとの法線方向ヒストグラムを求め、その値を連結して特徴量とする手段と、を備えることを特徴とする請求項５ないし７のいずれかに記載の三次元形状検索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元形状検索方法及びそれを用いる三次元形状検索システムに関するものである。とくに、三次元形状データベースに対し、任意の三次元形状モデルを検索質問とし、該データベースから類似する部分の形状を正確に選び出す三次元形状検索方法及び三次元形状検索システムに関する。
【背景技術】
【０００２】
三次元形状検索及び部分形状類似検索に関する従来技術として、例えば、特許文献１が開示されている。色ヒストグラム、及び、Grid Fourier特徴量、または、グラフ特徴量を用いることに特徴がある。
【０００３】
一方、代表的な三次元形状データに対する部分形状類似検索技術は、三次元スキャナ（以下、3Dスキャナということがある。）から定義される部分形状に対するタスクのひとつである。
【０００４】
RSVP（Random Sub-Volume Partitioning）技術（非特許文献１を参照）は、三次元物体の部分の形状を手掛かりとして、三次元物体を検索する技術である。技術の概要は次の通りである。前処理として、三次元物体をメッシュポリゴンから点群へ変換し、該点群に対し、位置、大きさ、向きがランダムな直方体を計算し、Sub-Volumeを生成する。次に、生成したSub-Volumeから点群の局所特徴量を抽出し、クラスタリング、次元削減、バイナリ化を行って特徴ベクトルを得て、部分形状類似検索に用いる。特徴は、高速な検索が可能であり、使用するメモリ量を抑えられるが、検索の精度及び特徴量の再現性に課題がある。
【０００５】
また、P-SV-DSIFT（Super Vector-Dense Scale Invariant Feature Transform）技術（非特許文献２を参照）は、おもにSuper Vector技術及びDense Scale Invariant Feature Transform（以下、Dense SIFTということがある。）技術からなるものである。技術の概要は次の通りである。前処理として、三次元物体に対し多視点からレンダリングし、複数の二次元画像を生成する。次に、得られた該二次元画像に対しDense SIFT特徴量を抽出する。該特徴量からクラスタリングにより特定のコードブックを生成し、さらに特定のエンコードを行って特徴ベクトルを求め、部分形状類似検索に用いる。検索精度が、該特徴量のサンプリングなどに影響を受けやすい。また、ランダムに直方体を切り出しその中に点群を発生させるため、部分形状を抽出することが出来ない。さらに、部分形状に対する法線ベクトルの整列化を行っていないため、3Dセンサーからスキャンした三次元物体の再現性に乏しい部分形状が抽出されることに課題がある。
【０００６】
Tranらの手法（非特許文献３を参照）は、RootRoPS特徴量、BoVW(Bag of Visual Words)及びICP(Iterative Closest Point algorithm)を組み合わせたものである。点群からISS(Intrinsic shape signatures)により特徴点検出を行い、RootRoPS特徴量を抽出する。抽出したRootRoPS特徴量からKMeansクラスタリングにより、5,000個のコードブック作成し、3近傍によるsoft-assignmentな量子化手法（BoVW）を用いてエンコードした5,000次元のベクトルを生成し特徴ベクトルとする。また、ICPによる点群同士の位置合わせを高速に行うために、検索質問の点群を、各座標軸に対し45度ずつ回転し、83=512個の向きの点群を生成することに特徴がある。検索質問と検索対象との最小距離を物体間の相違度として用いている。
【０００７】
KVLAD（非特許文献３を参照）は、画像の局所特徴量であるKAZE特徴量及びVLAD(Vector of Locally Aggregated Descriptor)を組み合わせた手法である。3次元物体に対し、92視点からのレンダリングにより2次元画像を生成し、複数の2次元画像からKAZE特徴量を抽出する。抽出したKAZE特徴量からGMMクラスタリングで100個のコードブックの作成し、VLADによってエンコードした128×100×2＝25,600次元のベクトルを特徴ベクトルとする。スケール推定に非線形スケールスペースを用いることで、物体の輪郭をシャープに保持することが可能となっているが、コードブック作成時のKAZE特徴量のサンプリング方法によって、同じ3次元物体から求められる特徴ベクトルに違いが生じるため、検索精度が不安定であることに課題がある。
【０００８】
最後に、非特許文献４に記載されているPointSVDは、三次元モデルの面にランダムに点を生成し、それらの点群の平均を三次元モデルの重心として、三次元空間の原点に平行移動することで位置の任意性を解決する。また、サンプル点を特異値分解することで、三次元モデルの主軸を求める。その主軸を、三次元空間のx軸，y軸，z軸に沿うように回転を行うことで回転の任意性を解決するものである。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特許第5104743号公報
【非特許文献】
【００１０】
【非特許文献１】T. Furuya and R. Ohbuchi, Randomized Sub-Volume Partitioning for Part-Based 3D Model Retrieval, Eurographics Workshop on 3D Object Retrieval 2015, 8pp, (2015)
【非特許文献２】Furuya, T., and Ohbuchi, R., Fusing Multiple Features for Shape-based 3D Model Retrieval, In BMVC., September, 2014.
【非特許文献３】I. Pratikakis, et al., "SHREC'16 Track: Partial Shape Queries for 3D Object Retrieval", Proc. 3DOR Proceedings of the 2016 Eurographics Workshops on 3D Object Retrieval, 11pp, Lisbon, Portugal, May 8, 2016.
【非特許文献４】立間淳司, 関洋平, 青野雅樹, 大渕竜太郎, “多重フーリエスペクトル表現に基づく三次元モデルの形状類似検索,” 電子情報通信学会論文誌 D, 91(1), pp23-36 (2008).
【発明の概要】
【発明が解決しようとする課題】
【００１１】
前述した先行技術に基づいた三次元形状検索及び部分形状類似検索の課題は、不完全な三次元データ（3Dメッシュ）を検索質問としたとき、質問された部分形状に類似する三次元形状データを求める検索精度が低いことである。とくに、3Dスキャナなどにより取得される複雑な向きを持つ面から構成される部分形状から、高精度で類似検索を実現することが課題であった。本発明は前記先行技術の課題を鑑み成されたものである。
【００１２】
本発明が解決しようとする課題は、3Dスキャナなどにより取得される不完全な三次元データ、あるいは、複雑な向きを持つ面から構成される部分形状を検索質問としたときでさえ、高精度に類似検索を実現する三次元形状検索方法及び三次元形状検索システムを提供することである。
【課題を解決するための手段】
【００１３】
本発明に係る三次元形状検索方法は、
三次元形状データベースに対し、三次元形状モデルの一部または全体を検索質問とし、該検索質問における部分の形状に基づいて、類似する三次元形状を選び出す三次元形状検索方法であって、
前処理として三次元物体を点群に変換し、多視点レンダリングにより部分形状を抽出し、
特徴量抽出として該部分形状の姿勢正規化を行って、多視点からの法線ヒストグラムを用いて第一の特徴ベクトルを求め、
前記検索質問に対して、三次元物体を点群に変換し、多視点レンダリングにより部分形状を抽出し、
特徴量抽出として該部分形状の姿勢正規化を行って、多視点からの法線ヒストグラムを用いて第二の特徴ベクトルを求め、
検索時には、前記第一の特徴ベクトル及び第二の特徴ベクトル間の相違度を求めて、該相違度の値により類似として選別することを特徴とする。
【００１４】
前記検索質問として、スキャンにより数値化された三次元形状データの一部または全体を用いることを特徴とする。
【００１５】
前記検索質問として用いる三次元形状データであって、
部分形状を抽出するための視点を決定し、
該視点からレンダリングにより生成した二次元画像及び点群へ変換した三次元物体を用い、平行投影により部分形状を抽出し、
前記二次元画像から前記三次元物体に含まれる点が可視部分であるか否かを判定して前記部分形状の法線ベクトルを整列化し、
スキャンした三次元物体の部分形状を疑似的に点群から生成することを特徴とする。
【００１６】
前記特徴量抽出は点群特徴量であって、
対象となる三次元物体に対し、三次元空間上の点群に対する特異値分解を行い、
視線ベクトルによる該三次元物体の主軸を固定し、
二次元投影平面上の点群に対する特異値分解により該三次元物体の向きの正規化し、
向きが正規化された該三次元物体に対し、格子状にブロックを設定して分割して、該ブロックごとの法線方向ヒストグラムを求め、その値を連結して特徴量とすることを特徴とする。
【００１７】
本発明に係る三次元形状検索システムは、
三次元形状データベースに対し、三次元形状モデルの一部または全体を検索質問とし、該検索質問における部分の形状に基づいて、類似する三次元形状を選び出す三次元形状検索システムであって、
前処理として三次元物体を点群に変換する手段と、
多視点レンダリングにより部分形状を抽出する手段と、
特徴量抽出として該部分形状の姿勢正規化を行って、多視点からの法線ヒストグラムを用いて第一の特徴ベクトルを求める手段と、
前記検索質問に対して、三次元物体を点群に変換する手段と、
多視点レンダリングにより部分形状を抽出する手段と、
特徴量抽出として該部分形状の姿勢正規化を行って、多視点からの法線ヒストグラムを用いて第二の特徴ベクトルを求める手段と、
検索時には、前記第一の特徴ベクトル及び第二の特徴ベクトル間の相違度を求めて、該相違度の値により類似として選別する手段と、を備えることを特徴とする。
【００１８】
前記三次元形状検索システムにおける検索質問として、スキャンにより数値化された三次元形状データの一部または全体を用いることを特徴とする。
【００１９】
前記三次元形状検索システムにおける検索質問として用いる三次元形状データであって、
部分形状を抽出するための視点を決定する手段と、
該視点からレンダリングにより生成した二次元画像及び点群へ変換した三次元物体を用い、平行投影により部分形状を抽出する手段と、
前記二次元画像から前記三次元物体に含まれる点が可視部分であるか否かを判定して前記部分形状の法線ベクトルを整列化し、
スキャンした三次元物体の部分形状を疑似的に点群から生成する手段と、を備えることを特徴とする。
【００２０】
前記三次元形状検索システムにおける特徴量抽出は点群特徴量であって、
対象となる三次元物体に対し、三次元空間上の点群に対する特異値分解を行う手段と、
視線ベクトルによる該三次元物体の主軸を固定する手段と、
二次元投影平面上の点群に対する特異値分解により該三次元物体の向きの正規化する手段と、
向きが正規化された該三次元物体に対し、格子状にブロックを設定して分割して、該ブロックごとの法線方向ヒストグラムを求め、その値を連結して特徴量とする手段と、を備えることを特徴とする。
【発明の効果】
【００２１】
本発明に係る三次元形状検索方法及び三次元形状検索システムにより、高精度な部分形状類似検索を実現できる。
【図面の簡単な説明】
【００２２】
【図１】本発明に係る三次元形状検索の処理フローを表す模式図である。
【図２】本発明に係る三次元形状検索において検索対象である三次元物体の特徴量抽出に関する処理フローを表すブロック図である。
【図３】本発明に係る三次元形状検索において検索質問である三次元物体の特徴量抽出に関する処理フローを表すブロック図である。
【図４】本発明に係る三次元形状検索において点群化に関する処理フローを表すブロック図である。
【図５】本発明に係る三次元形状検索において部分形状抽出に関する処理フローを表すブロック図である。
【図６】本発明に係る三次元形状検索において視線ベクトルによる法線ベクトルの整列化に関する概念図である。
【図７】本発明に係る三次元形状検索において部分形状の特徴量抽出に関する処理フローを表すブロック図である。
【図８】本発明に係る三次元形状検索において法線方向ヒストグラムの算出に関する概念図である。
【発明を実施するための形態】
【００２３】
本発明を実施するための形態について、図及び表等を参照しながら以下に説明する。
本発明に係る三次元形状検索の処理フローの概要を図１に示す。さらに、検索対象、すなわち三次元データベースに格納されている三次元物体モデル、の特徴量抽出の処理フローを図２に、検索質問、すなわち検索のクエリ入力として与えられる三次元物体モデル、の特徴量抽出の処理フローを図３に、それぞれ示す。
【００２４】
本発明に係る三次元形状検索の処理フローは、次の通りである。
まず、前処理として、検索対象データに対し、三次元物体をポリゴンメッシュから、点群へ変換する。次に、多視点レンダリングによる部分形状抽出法で部分形状を抽出し、抽出された部分形状から本発明に係る第一の特徴ベクトルを求める。
【００２５】
一方、本発明に係る検索システムを用いる検索時には、検索質問として、ユーザーから三次元物体が与えられたら、該三次元物体データを点群へ変換し、前記前処理と同様にして本発明に係る第二の特徴ベクトルを求める。類似形状を抽出するためには、第一の特徴ベクトル及び第二の特徴ベクトル間で相違度を求め、該相違度により並び替えたリストを作成し、該リストを類似形状検索の結果として、ユーザーに提示する。
【００２６】
前記検索質問では、3Dセンサーなどを用いて物体形状を取得して三次元形状のデータを生成し、用いることができる。3Dセンサーを用いるスキャンは、１回のスキャンでは単一の視点からの三次元物体形状となり、死角となる形状をスキャンすることが出来ないため、欠損を含み、不完全な三次元物体形状となる。また、3Dセンサーの精度に依存して、ノイズ成分を多く含み、これらの要因で三次元形状検索の精度に影響を及ぼすことになる。
【００２７】
そこで、本発明係る三次元形状検索では、多視点レンダリングを用いた部分形状抽出と、法線方向ヒストグラムを用いた特徴量を用いる。該部分形状抽出の前処理として、三次元物体をポリゴンメッシュから点群に変換した後、三次元物体に対し、多視点レンダリングを行い、部分形状の抽出を行う。次に、抽出された部分形状に対し、姿勢正規化を行い、多視点からの法線方向ヒストグラムを用いた特徴量を抽出し、前記第一の特徴ベクトルとして類似形状検索に用いる。
【００２８】
＜前処理＞
多視点レンダリングを用いた部分形状抽出及び、法線方向ヒストグラムを用いた特徴量計算のための前処理を行う。前処理として、三次元物体に対し点群の位置と大きさの正規化、ポリゴンメッシュからの法線計算、ポリゴンメッシュから点群への変換を行う。図４に処理フローを示す。
【００２９】
（位置と大きさの正規化）
三次元物体に対し、位置と大きさの正規化を行うことで、位置の任意性と大きさの任意性を解決する。初めに、位置の正規化を行う。三次元物体から重心を求め、求めた重心と座標の原点が一致するように平行移動を行うことで、三次元物体の位置の正規化が行われる。次に大きさの正規化を行う。重心からの最大距離を求め、三次元物体が半径1のBounding sphereの中に納まるように、三次元物体のスケールを変更することで、三次元物体の大きさの正規化が行われる。
【００３０】
（法線ベクトルの算出）
三次元物体から、特徴量抽出のための法線ベクトルを求める。本発明に係る法線ベクトルは、三次元物体を構成する、頂点、辺、面の集合で定義されたポリゴンメッシュから求められる。三つの頂点A,B,Cを持つ三角面からの法線ベクトルをnとすると、数１においてv1,v2は三角面の二つの辺を表すベクトルであり、法線ベクトルnは二つのベクトルの外積によって求められる。
【００３１】
【数１】
2018136642.tif 000003
【００３２】
（点群への変換）
部分形状抽出の前処理として、三次元物体をポリゴンメッシュから点群へ変換する。点群への変換に用いる。三つの頂点A，B，Cを持つ三角面上に点Pを生成する式を数２に示す。
【００３３】
【数２】
2018136642.tif 000004
r1，r2は、乱数値であり、0から1の範囲の値である。点を生成した後、生成元の三角面の情報をひも付け、上記で計算された法線ベクトルの情報を付与する。本発明に係る点群への変換では、点を生成するための乱数としてNiederreiter疑似乱数を用いる。また、本発明に係る実施例では、検索対象の三次元物体に対し生成する点の個数を64,000，検索質問の三次元物体に対し生成する点の個数を8,000としている。
【００３４】
＜部分形状抽出＞
3Dセンサーからスキャンした三次元物体を部分形状として扱い、多視点レンダリングを用いた部分形状抽出によって部分形状の抽出を行う。3Dセンサーを用いて、単一の視点からスキャンした三次元物体は、3Dセンサーの方向に面を向いた形状の情報のみを保持するため、全ての面の法線ベクトルは3Dセンサーの方向を向いている。図５に処理フローを示す。
【００３５】
本発明に係る部分抽出では、部分形状を抽出するための視点を決定し、各視点からレンダリングにより生成した二次元画像と点群へ変換した三次元物体を用いて、平行投影に基づく部分形状の抽出を行う。二次元画像の情報から、三次元物体に含まれる点が可視部分の点かどうかを判定し法線ベクトルの整列化を行うことで、3Dセンサーからスキャンした三次元物体の生成を疑似的に点群から行っている。
【００３６】
（視点の決定）
レンダリングを用いた部分形状の抽出のための視点を決定する。三次元物体を囲む立方体に基づいて視点を決定すると、視点を増やす際、立方体では、一様な視点を生成することが難しい。そこで、本発明係る視点の決定は、正八面体ベースで視点を増やす手法を用いる。該正八面体の座標を(±1,0,0)，(0,±1,0)，(0,0,±1)として、視点を以下の順で求める。
【００３７】
（A1）三次元座標の原点に中心を持つ正八面体を用意し、単位球に収まるようにする。
（A2）分割数nを決定する。
（A3）ある正三角形を選択する。
（A4）正三角形の頂点A, B, Cと二つの整数s, t(0≦s, t≦n)を用いて、以下の数３からベクトルvstを算出する。
（A5）||vst=1||となるように正規化を行う。
【００３８】
【数３】
2018136642.tif 000005
【００３９】
（平行投影に基づく部分形状抽出）
平行投影に基づく部分形状の抽出を行う。上記で決定した視点を用いて、二次元画像の生成を行う。二次元画像には、各視点から投影した三次元物体の奥行距離を保持している。本発明に係る実施例では、二次元画像の解像度を256×256としている。
【００４０】
三次元物体をワールド座標系から視点座標系へ座標変換を行い、指定した範囲のクリッピング空間へ移動する。三次元物体の移動には、数４及び数５にそれぞれ示す平行投影変換行列M及び視野変換行列Tを用いる。
【００４１】
【数４】
2018136642.tif 000006
【００４２】
【数５】
2018136642.tif 000007
【００４３】
平行投影変換行列Mは、三次元物体を視野空間からクリッピング空間への座標変換に用いられる。right，left，top，bottom，near，farは、クリッピング空間の範囲を指定するためのパラメータであり、本発明に係る部分形状抽出では、right=top=1、left=bottom=-1、near=0、far=2と定義する。
【００４４】
視野変換行列Tは、視点を原点へ移動し、視線を任意の方向へ向けるために用いる。eは視点、tは目標点、uは視点の上方向を表す。x’，y’，z’は視点座標系の直交基底である。本発明に係る実施例では、t={0,0,0}、u={0,1,0}と定義している。
【００４５】
平行投影変換行Mと視野変換行列Tを用いて三次元物体である点群Pを回転させ、三次元物体はワールド座標系から視点座標系へ座標変換され、クリッピング空間に移動する（数６）。
【００４６】
【数６】
2018136642.tif 000008
【００４７】
次に、座標変換した三次元物体を、点とそれに対応するピクセルで可視部分の点であるかどうかを判定する。点の座標値からそれに対応する二次元画像のピクセルの位置と奥行距離に変換する。同じ視点からレンダリングした、二次元画像のピクセルの奥行距離ziと点の座標値から変換した奥行距離zpを用いて、数７により、可視部分の点かどうかを判定する。また、可視部分の判定はz値が小さい点から行い、各ピクセルで可視部分と判定した点の数の上限を１とすることで、不可視部分の点を誤って可視部分の点であると判定することを防ぐ。全ての点に対して同様の処理を行い、可視部分の点と判定された点の集合を部分形状として抽出し、3Dセンサーからスキャンした不完全な三次元物体を再現している。
【００４８】
【数７】
2018136642.tif 000009
【００４９】
（法線ベクトルの整列化）
上述したようにして抽出した部分形状に対し、視線方向に基づく法線ベクトルの整列化を行う。図６に示すように、単一の視点からスキャンした三次元物体の面の法線ベクトルは、一貫した方向を向くため、法線ベクトルを視点のある方向に向くように整列化を行う。本発明に係る法線ベクトルの整列化では、部分形状を抽出した後、視線ベクトルと法線ベクトルの内積を計算し、内積が0より小さい法線ベクトルを視点のある方向へ向けるよう整列化を行うことで、法線ベクトルの向きを一貫した方向に向かせている。
【００５０】
＜特徴量抽出＞
多視点レンダリングに基づく部分形状抽出によって抽出した三次元物体から、法線方向ヒストグラムを用いた点群特徴量の抽出を行う。図７に処理フローを示す。初めに三次元物体に対し、三次元空間上で、点群からの特異値分解（以下、PointSVDと呼ぶ。）、視線ベクトルによる主軸固定、二次元空間上でのPointSVDによる向きの正規化を行う。次に向きの正規化を行った三次元物体に対し、格子状に分割し複数のブロックを求め、ブロックごとに法線方向ヒストグラムを計算し、連結したものを特徴量として抽出する。
【００５１】
（三次元物体の向きの正規化）
三次元物体の向きの任意性を解決するために、向きの正規化を行う。本発明に係る点群特徴量は、物体の向きに対する不変性を持たないため、三次元物体に対し向きの正規化が必要となる。向きの正規化手法として、三次元空間上でのPointSVD、視線ベクトルによる主軸固定、及び、二次元空間上でのPointSVDを行い、特徴量を抽出する。複数の視線ベクトルを用いて様々な方向から特徴量を抽出することで、三次元物体の向きの任意性を解決する。
【００５２】
・三次元空間上でのPointSVD
三次元物体の向きの正規化にはPointSVDを用いる。該PointSVDは，点群に対し特異値分解を行い、三つの主軸を決定し回転させることで、三次元物体の向きの正規化を行うものである。三次元空間上でのPointSVDによる、物体の向きの正規化を以下の手順で示す。
【００５３】
(B1)  M個の点群から重心Gを求め、重心が原点と一致するように平行移動を行い、点群行列Pを求める。
【００５４】
【数８】
2018136642.tif 000010
【００５５】
(B2)  点群行列Pに対し、特異値分解を行い、点群から主軸を求める。
【００５６】
【数９】
2018136642.tif 000011
ここで、Uは3×3の直交行列、Σは3×3の対角要素が特異値である対角行列、WTが3×Mの直交行列である。
【００５７】
(B3)  左特異値行列Uを転置したUTを点群の回転行列Qとする。
【００５８】
【数１０】
2018136642.tif 000012
【００５９】
(B4)  最後に，回転行列Qを用いて点群Pと法線ベクトル行列Nを回転し、三次元物体の向きが正規化される。
【００６０】
【数１１】
2018136642.tif 000013
【００６１】
・視線ベクトルを用いた主軸固定
三次元物体をPointSVDで向きの正規化を行った後、視線ベクトルを用いた主軸固定を行う。三次元空間上でのPointSVDは、3Dセンサーでスキャンした不完全な三次元物体に対して適用すると、欠損等のノイズ成分によって、決定される三つの主軸に変化が生じてしまう。そのため三次元物体の向きの任意性を十分に解決することが出来ない。
本発明に係る主軸の固定では、視線ベクトルを用いて、物体の向きを決定する三つの主軸の内、第1主軸を固定する。視線ベクトルを用いた主軸固定を以下の手順で示す。
【００６２】
(C1)  ある一つの座標軸と視線ベクトルとの偏角をθ、視点をeとして，視線ベクトルと座標軸に直交するベクトルuを求める．
【００６３】
(C2)  偏角θ、ベクトルuから視線ベクトルと座標軸を一致するように回転行列Rを求める。
【００６４】
【数１２】
2018136642.tif 000014
【００６５】
(C3)  回転行列Rを用いて、三次元物体を視線ベクトルと座標軸を一致するように回転し、物体の向きを決定する第1主軸を一つ固定する。
【００６６】
本発明に係る主軸の固定では、三次元物体をz軸と視線ベクトルが一致するように回転し、主軸の固定を行う。よって視点e={ex,ey,ez}から、z軸と視線ベクトルとの偏角をθ=cos-1ez、z軸と視線ベクトルに直交するベクトルをu={-ey,ex,0}と定義した。
【００６７】
・二次元空間上でのPointSVD
視線ベクトルを用いて物体の向きを決定する第1主軸を決定した後、残り二つの第2主軸及び第3主軸を二次元空間上でのPointSVDによって決定する。二次元空間上でのPointSVDによる、物体の向きの正規化を以下の手順で示す。本発明に係る第2主軸及び第3主軸の決定では、xy平面上でのPointSVDを行い、二つの主軸を決定する。
【００６８】
(D1)  M個の点群から重心Gを求め、重心が原点と一致するように平行移動を行い、点群行列Pを求める。
【００６９】
【数１３】
2018136642.tif 000015
(D2)  点群行列Pに対し、特異値分解を行い、点群から主軸を求める。
【００７０】
【数１４】
2018136642.tif 000016
ここで、Uは2×2の直交行列、Σは2×2の対角要素が特異値である対角行列WTが2×Mの直交行列である。
【００７１】
(D3)  左特異値行列Uを転置したUTを点群の回転行列Qとする。
【００７２】
【数１５】
2018136642.tif 000017
【００７３】
(D4)  最後に、回転行列Qを用いて点群Pと法線ベクトル行列Nを回転し、三次元物体の向きが正規化される。
【００７４】
【数１６】
2018136642.tif 000018
【００７５】
（点群特徴量の抽出）
本発明に係る点群特徴量では、法線ベクトルの向きを考慮した点群特徴量を抽出する。図８に示すように、三次元物体からBounding boxを計算し、複数のブロックに分割する。そして、ブロックごとに、三つの平面に射影した法線を用いて法線方向ヒストグラムを計算し、連結することで特徴量を抽出するものである。
【００７６】
・Bounding boxの計算
向きの正規化を行った三次元物体から、特徴を抽出するためのBounding boxを求める。Bounding boxを計算し特徴量抽出を行うことで、三次元物体の形状を空間的に密に捉えた特徴量を抽出することが出来る。Bounding boxは各座標軸で三次元物体の両端[Xmin-ε,Ymin-ε,Zmin-ε]-[Xmax+ε,Ymax+ε,Zmax+ε]から計算することが出来る。εは境界面上でデータを失わないようにするためのパラメータでε=1.0e-5とした。
【００７７】
・法線方向ヒストグラムの計算
三次元物体から計算したBounding boxを各辺で4分割し、64個のブロックを得る。次に各ブロックで法線方向ヒストグラムの計算を行う。計算の手順を以下に示す。
【００７８】
(E1)  ブロック内に存在する点の法線ベクトルを二次元平面に射影する。点群を二次元平面に射影して特徴量を抽出する手法に基づいて、法線ベクトルn={nx, ny, nz}をxy平面、yz平面、zx平面の3平面に射影し、法線ベクトルnxy, nyz, nzxを求める。
【００７９】
(E2)  法線方向ヒストグラムを計算する。二次元平面に射影した法線ベクトルnxy, nyz, nzxからH次元の法線方向ヒストグラムhxy, hyz, hzxを求める。前記ヒストグラムの計算では重み付けを用いたビン(bins)への割当てを行う。射影した法線ベクトルの法線方向θxy, θyz, θzxと割り当てる重みwxy, wyz, wzxをnxy, nyz, nzxのノルムから求める。本発明に係る実装では、ヒストグラムのビン数を経験上H=8としている。
【００８０】
【数１７】
2018136642.tif 000019
【００８１】
hxy, hyz, hzxを連結し、24次元の法線方向ヒストグラムhbを求めることが出来る。
【００８２】
【数１８】
2018136642.tif 000020
【００８３】
(E3)  各ブロックで求めたヒストグラムhbを全て連結し、L1ノルムで正規化した24×64=1,536次元のベクトルfを特徴量とする．
【００８４】
【数１９】
2018136642.tif 000021
【００８５】
1体の三次元物体から抽出することが出来る特徴量の数は、視点の数によって決定される。本発明に係る特徴量の抽出では、検索対象の三次元物体に対し66×66=4,356個、検索質問の三次元物体に対し66個の特徴量を抽出する。該特徴量は特徴ベクトルとして相違度計算に用いる。
【００８６】
（相違度計算）
類似形状検索のため、特徴ベクトルで相違度計算を行う。本発明に係る類似形状検索では、1体の三次元物体から複数の特徴ベクトルを得るので、特徴ベクトルの集合間で相違度計算を行う。本発明に係る相違度計算において、複数の相違度が小さい特徴ベクトルの、重みつき平均の線形和を用いることによって、二つの三次元物体間の相違性を精密に計算し、特徴量の抽出に用いた視点の依存性を解消することで検索精度の向上を図る。検索質問の特徴ベクトルの集合をQ、検索対象の特徴ベクトルの集合Tをとする。特徴ベクトルの集合間の相違度を求める式を以下に示す。はじめに検索質問の特徴ベクトルq∈Qごとに、t∈Tとのマンハッタン距離d(q,t)が最小となるような相違度の集合δminを求める。次に求めたδminに対し、相違度を小さいものから順に並び替えを行い、上位i番目の相違度dmin(i)に対し重みwiを付けて加算し、i=K番目となるまで同様の計算を行う。最後にK番目まで加算した相違度に対しKで除算して平均を取った相違度をQとTの最終的な相違度D(Q,T)とする。本発明に係る相違度では、相違度計算で用いるパラメータをK=60としている。
【００８７】
【数２０】
2018136642.tif 000022
【００８８】
本発明に係る築地検索システムは、演算装置、メモリ、外部記憶装置、表示装置及び入力機器が電気的に接続されている計算機のハードウェアを適宜、制御してなり、C言語などのプログラムミング言語を用いて、そのアルゴリズムが実装される。
【実施例】
【００８９】
評価実験に用いるデータセットとして、SHREC 2016 Partialデータセット（例えば、I. Pratikakis, et al., "SHREC'16 Track: Partial Shape Queries for 3D Object Retrieval", Proc. 3DOR Proceedings of the 2016 Eurographics Workshops on 3D Object Retrieval, 11pp, Lisbon, Portugal, May 8, 2016.を参照）を用いる。
【００９０】
SHREC 2016 Partial データセットは、考古遺品を管理するHVM(Hampson Virtual Museum, http://hampson.cast.uark.edu/)の三次元物体から作成された三次元部分形状検索用のデータセットである。全体形状を持つ検索対象の三次元物体が383個、部分形状を持つ検索質問の三次元物体が192個、それぞれ6クラスで構成している。検索質問の三次元物体は、クラスArtificial、クラスBreuckmann、Kinectの3種類の方法で部分形状の作成を行っている。Artificialは人手で切り分けて部分形状を作成したものであり、全体形状の25%(Q25)と40%(Q40)の部分形状を検索質問としている。一方、Breuckmann，Kinectは3Dセンサーからスキャンした三次元物体を部分形状として作成したものであり、3方向(View1，View2，View3)からスキャンして三次元物体を生成している。Breuckmannは高精度の3Dセンサーでノイズ成分が少ない三次元物体を生成し，Kinectは低精度の3Dセンサーでノイズ成分の多い三次元物体を生成する。本発明に係る評価実験では、当該データセットを用いて、従来技術との検索精度の比較を行った。
【００９１】
評価実験における評価尺度として、NN(Nearest Neighbor)、FT(First Tier)、ST(Second Tier)、F(F-Measure)、MAP(Mean Average Precision)、DCG(Discounted Cumulative Gain)、Recall-Precision曲線を用いる。当該データセットに用いた評価尺度は、国際コンテストで採用された基準に準拠している。
【００９２】
前記評価尺度を求める数式を以下に示す。rel(k)は、検索結果のランキング上位k位に検索質問と同じクラスの三次元物体が何個存在するのかを表し、Cは検索対象に含まれる同じクラスの三次元物体の個数を表す。F-Measureの計算で上位32位までの結果rel(32)を用いたのは、国際コンテストで採用された基準に準拠するためである。DCGの計算においてG(i)は、検索結果i位が正解ならば1、そうでなければ0であることを表す。
【００９３】
【数２１】
2018136642.tif 000023
【００９４】
【数２２】
2018136642.tif 000024
【００９５】
評価実験で本発明に係る実施例及び従来手法との比較を表１に示す。SHREC 2016 Partial データセットでの評価実験では、KVLAD及びTranらの手法、さらに、RSVPを比較手法とする。
【００９６】
【表１】
2018136642.tif 000025
【００９７】
Breuckmannでの実験結果を表２、表３、表４に示す。手法(View1)、手法(View2)、手法(View3)いずれにおいても、本発明に係る類似形状検索システムの検索精度が従来技術より良いことを示している。
【００９８】
【表２】
2018136642.tif 000026
【００９９】
【表３】
2018136642.tif 000027
【０１００】
【表４】
2018136642.tif 000028
【０１０１】
従来技術では、検索結果の上位に検索質問と同じ三次元物体が出現していないが、本発明に係る類似形状検索システムの検索結果の上位には検索結果と同じ三次元物体が出現していることが分かる。評価実験結果より、3Dセンサーからスキャンした不完全な三次元物体を検索質問とした三次元形状検索に適していることが分かる。また、本発明に係る類似形状検索システムによって、3Dセンサーでスキャンした不完全な三次元物体を再現することが実現できている。
【図１】
2018136642.tif 000029
【図２】
2018136642.tif 000030
【図３】
2018136642.tif 000031
【図４】
2018136642.tif 000032
【図５】
2018136642.tif 000033
【図６】
2018136642.tif 000034
【図７】
2018136642.tif 000035
【図８】
2018136642.tif 000036