(57)【要約】【課題】精度良く、三次元物体検索を行うことができる【解決手段】ヒストグラム作成部２５とヒストグラム作成部４４が、三次元物体を覆うバウンディングボックスを定義し、バウンディングボックスを所定の方法で分割し、分割された各小領域を表現するヒストグラム特徴量を計算し、これらヒストグラム特徴量をつなぎ合わせることによって三次元物体を表現するヒストグラム特徴量を計算する。ヒストグラム比較部４６が、検索対象物体を表現するヒストグラム特徴量と、ヒストグラム作成部２５によって計算され三次元物体記憶部３４に記憶されたヒストグラム特徴量の比較を行い、類似度を計算する。物体検索処理部４８が、比較結果記憶部３６から、検索対象物体との類似度が高い物体を取り出す。【選択図】図１
2018013927.tif 000002
【特許請求の範囲】
【請求項１】
入力として与えられた検索対象物体を表す三次元物体に対して、データベースを構成する三次元物体集合の中から検索対象物体に類似した三次元物体を取り出す物体検索装置であって、
三次元物体を構成する各点に対して点周辺の情報を表現する局所特徴量を計算する局所特徴量計算部と、
あらかじめ前記三次元物体集合から作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって検索対象物体を構成する点周辺の情報から計算された局所特徴量を割り当てる局所特徴量割当部と、
前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、前記検索対象物体を表現するヒストグラム特徴量を計算するヒストグラム作成部と、
前記ヒストグラム作成部によって前記検索対象物体から計算されたヒストグラム特徴量及び前記三次元物体集合に含まれる前記三次元物体から計算されたヒストグラム特徴量の類似度を計算するヒストグラム比較部と、
前記ヒストグラム比較部によって計算されたスコアから検索結果を決定する物体検索処理部と、
を含み、
前記ヒストグラム作成部は、ヒストグラム作成対象である三次元物体を覆う直方体であるバウンディングボックスを、予め定められたパラメータに応じて決定したパターンに応じて垂直方向および水平方向に分割し、分割した結果得られる小領域内に含まれる各点に対する局所特徴量に基づき、小領域ごとに前記ヒストグラム特徴量を作成し、各ヒストグラム特徴量にあらかじめ決定した定数を乗じたものをつなぎ合わせることによって１つのヒストグラム特徴量を計算する
物体検索装置。
【請求項２】
前記ヒストグラム作成部は、前記バウンディングボックスを垂直方向に分割する際、前記バウンディングボックスの中央部の柱状部分と、前記中央部の柱状部分を含み、かつ、前記中央部の柱状部分より大きい柱状部分のうち、前記中央部の柱状部分を除いた環状部分と、内側の環状部分を含み、かつ、前記内側の環状部分より大きい柱状部分のうち、内側の全ての環状部分及び前記中央部の柱状部分を除いた環状部分とに分割する請求項１に記載の物体検索装置。
【請求項３】
検索対象物体である三次元物体の各点に対して点周辺の情報を表現する局所特徴量を計算する局所特徴量計算部と、
データベースを構成する三次元物体集合からあらかじめ作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって検索対象物体を構成する点周辺の情報から計算された局所特徴量を割り当てる局所特徴量割当部と、
前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、検索対象物体を表現するヒストグラム特徴量を計算するヒストグラム作成部と、
を含み、
前記ヒストグラム作成部は、検索対象物体を覆う直方体であるバウンディングボックスを、予め定められたパラメータに応じて決定したパターンに応じて垂直方向および水平方向に分割し、分割した結果得られる小領域内に含まれる各点に対する局所特徴量に基づき、小領域ごとに前記ヒストグラム特徴量を作成し、各ヒストグラム特徴量にあらかじめ決定した定数を乗じたものをつなぎ合わせることによって１つのヒストグラム特徴量を計算する
三次元物体モデル化装置。
【請求項４】
前記ヒストグラム作成部は、前記バウンディングボックスを垂直方向に分割する際、前記バウンディングボックスの中央部の柱状部分と、前記中央部の柱状部分を含み、かつ、前記中央部の柱状部分より大きい柱状部分のうち、前記中央部の柱状部分を除いた環状部分と、内側の環状部分を含み、かつ、前記内側の環状部分より大きい柱状部分のうち、内側の全ての環状部分及び前記中央部の柱状部分を除いた環状部分とに分割する請求項３に記載の三次元物体モデル化装置。
【請求項５】
局所特徴量計算部、局所特徴量割当部、ヒストグラム作成部、ヒストグラム比較部、及び物体検索処理部を含み、入力として与えられた検索対象物体を表す三次元物体に対して、データベースを構成する三次元物体集合の中から検索対象物体に類似した物体を取り出す物体検索装置における物体検索方法であって、
前記局所特徴量計算部が、三次元物体を構成する各点に対して点周辺の情報を表現する局所特徴量を計算するステップと、
前記局所特徴量割当部が、あらかじめ前記三次元物体集合から作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって検索対象物体を構成する点周辺の情報から計算された局所特徴量を割り当てるステップと、
前記ヒストグラム作成部が、前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、前記検索対象物体を表現するヒストグラム特徴量を計算するステップと、
前記ヒストグラム比較部が、前記ヒストグラム作成部によって前記検索対象物体から計算されたヒストグラム特徴量及び前記三次元物体集合に含まれる前記三次元物体から計算されたヒストグラム特徴量の類似度を計算するステップと、
前記物体検索処理部が、前記ヒストグラム比較部によって計算されたスコアから検索結果を決定するステップと、
を含み、
前記ヒストグラム作成部が計算するステップでは、ヒストグラム作成対象である三次元物体を覆う直方体であるバウンディングボックスを、予め定められたパラメータに応じて決定したパターンに応じて垂直方向および水平方向に分割し、分割した結果得られる小領域内に含まれる各点に対する局所特徴量に基づき、小領域ごとに前記ヒストグラム特徴量を作成し、各ヒストグラム特徴量にあらかじめ決定した定数を乗じたものをつなぎ合わせることによって１つのヒストグラム特徴量を計算する
物体検索方法。
【請求項６】
局所特徴量計算部、局所特徴量割当部、及びヒストグラム作成部を含む三次元物体モデル化装置における三次元物体モデル化方法であって、
前記局所特徴量計算部が、検索対象物体である三次元物体の各点に対して点周辺の情報を表現する局所特徴量を計算するステップと、
前記局所特徴量割当部が、データベースを構成する三次元物体集合からあらかじめ作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって検索対象物体を構成する点周辺の情報から計算された局所特徴量を割り当てるステップと、
前記ヒストグラム作成部が、前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、検索対象物体を表現するヒストグラム特徴量を計算するステップと、
を含み、
前記ヒストグラム作成部が計算するステップでは、検索対象物体を覆う直方体であるバウンディングボックスを、予め定められたパラメータに応じて決定したパターンに応じて垂直方向および水平方向に分割し、分割した結果得られる小領域内に含まれる各点に対する局所特徴量に基づき、小領域ごとに前記ヒストグラム特徴量を作成し、各ヒストグラム特徴量にあらかじめ決定した定数を乗じたものをつなぎ合わせることによって１つのヒストグラム特徴量を計算する
三次元物体モデル化方法。
【請求項７】
コンピュータを、請求項１若しくは２に記載の物体検索装置、又は請求項３若しくは４に記載の三次元物体モデル化装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物体検索装置、三次元物体モデル化装置、方法、及びプログラムに係り、特に、三次元物体データベースの中から検索対象物体と類似した物体を検索するための物体検索装置、三次元物体モデル化装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
三次元物体検索において一般的に用いられる手法として、あらかじめ複数の三次元物体を数値ベクトルに変換してデータベースを構築しておき、検索クエリとして与えられた物体との類似度を計算し、類似度が高いものを検索結果とするものがある（非特許文献３参照）。
【０００３】
三次元物体を数値ベクトルに変換するための手法の１つとして、Bag−of−Visual−Words（BoVW）（非特許文献１参照）や、BoVWのパラダイムに基づくさまざまな特徴量を用いたものがある。これは、物体の局所的な形状情報やテクスチャ情報を統計処理することによって得られる大域特徴量である。この特徴量は、統計処理の対象となる局所的な情報が物体の回転に対して不変であれば、BoVWベースの特徴量も物体の回転に対して不変になる。また、BoVWベースの特徴量は物体の局所的な変形や情報の欠損に対して頑健であるという特徴を持っており、三次元メッシュで表現されたノイズがほとんど含まれていない三次元物体のみならず、レーザーレンジファインダ等で実世界から計測されたノイズや欠損が多く含まれる三次元点群によって表現された三次元物体を表現するのにも適した特徴量であると言える。
【０００４】
一方、BoVWベースの特徴量は局所的な情報が持つ位置情報、すなわち物体を構成するパーツの位置に関する情報をまったく利用していないため、所望の物体とは異なるデータベース中の物体と検索クエリの物体との類似度が高くなってしまうことがある。これに対して、大まかな位置情報を利用するための手法としてSpatial Pyramid Matching（SPM）がある（非特許文献２参照）。この手法は、画像を対象とした物体認識にために提案されたもので、画像全体、あるいは画像の中の一部の注目領域をいくつかの小領域に分割し、分割してできた小領域のそれぞれに対して小領域を表現する特徴量を計算し、これらをひとつの特徴量に纏め上げて画像全体を表現する特徴量を構成することにより、おおよその位置情報を利用しようというものである。
【０００５】
三次元物体をBoVWベースの特徴量で表現する際も同様のアイデアを利用することによっておおよそのパーツの位置情報を利用することが可能であると考えられるが、物体を不適切な方法で分割してしまうと対象物体の回転に応じてBoVWベースの特徴量の内容が変化してしまうため、かえって性能の低下を招いてしまう。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】J. Sivic and A. Zisserman. Video Google: A Text Retrieval Approach to Object Matching in Videos. In Proceedings of ICCV, 2003.
【非特許文献２】S. Lazebnik, C. Schmid, and J. Ponce. Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories. In Proceedings of CVPR, 2006.
【非特許文献３】R. Toldo, U. Castellani, and A. Fusiello. A bag of words approach for 3d object categorization. In Proceedings of MIRAGE, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
BoVWベースの特徴量は局所的な情報の欠落、あるいは変形といったノイズには頑健であるが、三次元物体を表現する上で重要である幾何学的情報をまったく利用していないため、これによるエラーを避けることができない。
【０００８】
本発明は、BoVWベースの特徴量を用いて三次元物体を表現する際に、三次元物体の回転に対する特徴量の不変性をおおよそ失うことなく、表現対象の三次元物体が持つ幾何学的情報を利用して物体を表現することにより、精度よく、三次元物体データベースから物体を検索することができる物体検索装置、三次元物体モデル化装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明に係る物体検索装置は、入力として与えられた検索対象物体を表す三次元物体に対して、データベースを構成する三次元物体集合の中から検索対象物体に類似した三次元物体を取り出す物体検索装置であって、三次元物体を構成する各点に対して点周辺の情報を表現する局所特徴量を計算する局所特徴量計算部と、あらかじめ前記三次元物体集合から作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって検索対象物体を構成する点周辺の情報から計算された局所特徴量を割り当てる局所特徴量割当部と、前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、前記検索対象物体を表現するヒストグラム特徴量を計算するヒストグラム作成部と、前記ヒストグラム作成部によって前記検索対象物体から計算されたヒストグラム特徴量及び前記三次元物体集合に含まれる前記三次元物体から計算されたヒストグラム特徴量の類似度を計算するヒストグラム比較部と、前記ヒストグラム比較部によって計算されたスコアから検索結果を決定する物体検索処理部と、を含み、前記ヒストグラム作成部は、ヒストグラム作成対象である三次元物体を覆う直方体であるバウンディングボックスを、予め定められたパラメータに応じて決定したパターンに応じて垂直方向および水平方向に分割し、分割した結果得られる小領域内に含まれる各点に対する局所特徴量に基づき、小領域ごとに前記ヒストグラム特徴量を作成し、各ヒストグラム特徴量にあらかじめ決定した定数を乗じたものをつなぎ合わせることによって１つのヒストグラム特徴量を計算する。
【００１０】
本発明に係る物体検索方法は、局所特徴量計算部、局所特徴量割当部、ヒストグラム作成部、ヒストグラム比較部、及び物体検索処理部を含み、入力として与えられた検索対象物体を表す三次元物体に対して、データベースを構成する三次元物体集合の中から検索対象物体に類似した物体を取り出す物体検索装置における物体検索方法であって、前記局所特徴量計算部が、三次元物体を構成する各点に対して点周辺の情報を表現する局所特徴量を計算するステップと、前記局所特徴量割当部が、あらかじめ前記三次元物体集合から作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって検索対象物体を構成する点周辺の情報から計算された局所特徴量を割り当てるステップと、前記ヒストグラム作成部が、前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、前記検索対象物体を表現するヒストグラム特徴量を計算するステップと、前記ヒストグラム比較部が、前記ヒストグラム作成部によって前記検索対象物体から計算されたヒストグラム特徴量及び前記三次元物体集合に含まれる前記三次元物体から計算されたヒストグラム特徴量の類似度を計算するステップと、前記物体検索処理部が、前記ヒストグラム比較部によって計算されたスコアから検索結果を決定するステップと、を含み、前記ヒストグラム作成部が計算するステップでは、ヒストグラム作成対象である三次元物体を覆う直方体であるバウンディングボックスを、予め定められたパラメータに応じて決定したパターンに応じて垂直方向および水平方向に分割し、分割した結果得られる小領域内に含まれる各点に対する局所特徴量に基づき、小領域ごとに前記ヒストグラム特徴量を作成し、各ヒストグラム特徴量にあらかじめ決定した定数を乗じたものをつなぎ合わせることによって１つのヒストグラム特徴量を計算する。
【００１１】
本発明に係る三次元物体モデル化装置は、検索対象物体である三次元物体の各点に対して点周辺の情報を表現する局所特徴量を計算する局所特徴量計算部と、データベースを構成する三次元物体集合からあらかじめ作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって検索対象物体を構成する点周辺の情報から計算された局所特徴量を割り当てる局所特徴量割当部と、前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、検索対象物体を表現するヒストグラム特徴量を計算するヒストグラム作成部と、を含み、前記ヒストグラム作成部は、検索対象物体を覆う直方体であるバウンディングボックスを、予め定められたパラメータに応じて決定したパターンに応じて垂直方向および水平方向に分割し、分割した結果得られる小領域内に含まれる各点に対する局所特徴量に基づき、小領域ごとに前記ヒストグラム特徴量を作成し、各ヒストグラム特徴量にあらかじめ決定した定数を乗じたものをつなぎ合わせることによって１つのヒストグラム特徴量を計算する。
【００１２】
本発明に係る三次元物体モデル化方法は、局所特徴量計算部、局所特徴量割当部、及びヒストグラム作成部を含む三次元物体モデル化装置における三次元物体モデル化方法であって、前記局所特徴量計算部が、検索対象物体である三次元物体の各点に対して点周辺の情報を表現する局所特徴量を計算するステップと、前記局所特徴量割当部が、データベースを構成する三次元物体集合からあらかじめ作成された局所特徴量のクラスタ中心に対して、前記局所特徴量計算部によって検索対象物体を構成する点周辺の情報から計算された局所特徴量を割り当てるステップと、前記ヒストグラム作成部が、前記局所特徴量割当部によって局所特徴量を割り当てた結果から各クラスタに割り当てられた局所特徴量の数を計算し、検索対象物体を表現するヒストグラム特徴量を計算するステップと、を含み、前記ヒストグラム作成部が計算するステップでは、検索対象物体を覆う直方体であるバウンディングボックスを、予め定められたパラメータに応じて決定したパターンに応じて垂直方向および水平方向に分割し、分割した結果得られる小領域内に含まれる各点に対する局所特徴量に基づき、小領域ごとに前記ヒストグラム特徴量を作成し、各ヒストグラム特徴量にあらかじめ決定した定数を乗じたものをつなぎ合わせることによって１つのヒストグラム特徴量を計算する。
【００１３】
本発明に係るプログラムは、上記の物体検索装置又は上記の三次元物体モデル化装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１４】
本発明の物体検索装置、三次元物体モデル化装置、方法、及びプログラムによれば、三次元物体を適切に分割することによって、ヒストグラム特徴量が三次元物体の回転から受ける影響を抑えつつ、三次元物体が持つ幾何学的情報をヒストグラム特徴量に組み込むことができ、精度良く、三次元物体データベースから物体を検索することができる、という効果が得られる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施の形態に係る物体検索装置の構成を示すブロック図である。
【図２】基礎データ記憶部２１の一例を示す図である。
【図３】局所特徴量記憶部３０の一例を示す図である。
【図４】クラスタ記憶部３２の一例を示す図である。
【図５】三次元物体記憶部３４の一例を示す図である。
【図６】比較結果記憶部３６の一例を示す図である。
【図７】ヒストグラム作成部２５において定義されるバウンディングボックスBを示す図である。
【図８】ヒストグラム作成部２５において定義される立体Uの一例を示す図である。
【図９】ヒストグラム作成部２５において定義される立体Vの一例を示す図である。
【図１０】本発明の実施の形態に係る物体検索装置における前処理ルーチンを示すフローチャートである。
【図１１】本発明の実施の形態に係る物体検索装置における物体検索処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１７】
まず、本発明の実施の形態に係る物体検索装置の構成について説明する。図１に示すように、本発明の実施の形態に係る物体検索装置１００は、ＣＰＵと、ＲＡＭと、後述する物体検索処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この物体検索装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００１８】
入力部１０は、データベースを構成するN個（NはN≧１である自然数）の三次元物体を受け付ける。各三次元物体は、レーザーレンジファインダや、赤外線センサ、または超音波センサなどの、三次元点群を計測する装置によって得られた物体の表面上の位置を計測した計測結果である複数の位置を表す三次元点群や、複数の三次元点とこれらの組から構成される面とから構成される三次元メッシュである。
【００１９】
また、入力部１０は、検索対象である三次元物体を受け付ける。受け付けた三次元物体は基礎データ記憶部２１に格納するものとする。
【００２０】
演算部２０は、前処理部２２と、基礎データ記憶部２１と、局所特徴量記憶部３０と、クラスタ記憶部３２と、三次元物体記憶部３４と、比較結果記憶部３６と、局所特徴量計算部４０と、局所特徴量割当部４２と、ヒストグラム作成部４４と、ヒストグラム比較部４６と、物体検索処理部４８とを含んで構成されている。
【００２１】
前処理部２２は、以下に説明する各部の処理によって、データベースを構成するN個の三次元物体を受け付け、物体の検索に必要な局所特徴量、クラスタ、及び各三次元物体を表現するヒストグラム特徴量を計算する。
【００２２】
前処理部２２は、局所特徴量計算部２３と、クラスタリング部２４と、ヒストグラム作成部２５とを含んで構成されている。
【００２３】
基礎データ記憶部２１には、入力部１０で受け付けた、前処理に用いる、データベースを構成する複数の三次元物体が格納されている。また、入力部１０で受け付けた、検索対象物体を表す３次元点群が格納されている。基礎データ記憶部２１の一例を図２に示す。
【００２４】
局所特徴量計算部２３は、データベースを構成する複数の三次元物体の各点について、点周辺の情報を利用して局所特徴量を計算し、点の三次元座標と共に局所特徴量記憶部３０に格納する。局所特徴量として利用可能なものとしては、FPFH（非特許文献４参照）やSHOT（非特許文献５参照）がある。なお、三次元点群からサンプリングした点の各々について、局所特徴量を計算してもよい。ここで計算した局所特徴量の数をM個（Mは自然数）とする。サンプリングの方法としては、三次元物体が存在する三次元空間上で等間隔に三次元点を選び出したり、特徴点抽出アルゴリズム（非特許文献６参照）を利用して三次元点を選び出したりするなどの方法がある。
【００２５】
[非特許文献４]：R.B. Rusu, N. Blodow, and M. Beetz. Fast Point Feature Histograms (FPFH) for 3D Registration. In Proceedings of ICRA, 2009.
【００２６】
[非特許文献５]：F. Tombari, S. Salti, and L. Di Stefano. Unique signatures of histograms for surface and texture description. In Proceedings of ECCV, 2010.
【００２７】
[非特許文献６]：F. Tombari, S. Salti, and L. Di Stefano. Performance Evaluation of 3D Keypoint Detectors. International Journal of Computer Vision, vol. 102, no. 1, pp. 198-220, 2013.
【００２８】
局所特徴量記憶部３０には、局所特徴量計算部２３によって計算されたＭ個の局所特徴量が格納されている。また、局所特徴量には、計算の際に利用した点が属する物体の番号、及び後述するクラスタリング部２４によって割り当てられたクラスタ中心のクラスタ番号が付与される。局所特徴量はＤ次元のベクトルで表現される。また、局所特徴量に対応した三次元点の座標ｘ、ｙ、ｚの座標値も記憶しておく。局所特徴量記憶部３０の一例を図３に示す。
【００２９】
クラスタリング部２４は、局所特徴量計算部２３によって計算されたＭ個の局所特徴量に基づいて、非特許文献１に記載のコードブック学習の手法を用いて、Ｋ個のクラスタについて、クラスタ中心を計算し、各クラスタに、Ｍ個の局所特徴量の各々を割り当てる。計算したクラスタ中心はクラスタ記憶部３２に格納する。また、各クラスタに各局所特徴量を割り当てた結果として、各局所特徴量に対するクラスタ番号を局所特徴量記憶部３０に格納する。クラスタ数Ｋはあらかじめ設定により定めておく。ここでは、大量の３次元点群のデータを用いてクラスタリングすることによって、有意なクラスタ中心を得ることができる。
【００３０】
クラスタ記憶部３２には、クラスタリング部２４によって計算されたＫ個のクラスタのクラスタ中心が格納されている。クラスタ記憶部３２の一例を図４に示す。
【００３１】
本実施例においては非特許文献１に記載の方法を用いてクラスタリング及びクラスタへの局所特徴量の割り当てを行ったが、局所特徴量記憶部３０とクラスタ記憶部３２に格納する情報を適宜修正することによって利用可能な他の手法として混合ガウス分布を利用したsoft assignmentによる手法（非特許文献７参照）やLocality-constrained Linear Coding（非特許文献８参照）、Fisher Vector（非特許文献９参照）などがある。
【００３２】
[非特許文献７]：J. Farquhar, S. Szedmak, H. Meng, and J. Shawe-Taylor. Improving “bag-of-keypoints” image categorization: Generative Models and PDF-Kernels. Technical report, University of Southampton, 2005.
【００３３】
[非特許文献８]：J. Wang, J. Yang, K. Yu, F. Lv, T. Huang, and Y. Gong. Locality-constrained Linear Coding for Image Classification. In Proceedings of CVPR, 2010.
【００３４】
[非特許文献９]：F. Perronnin, J. Sanchez, and T. Mensink. Improving the Fisher Kernel for Large-Scale Image Classification. In Proceedings of ECCV, 2010.
【００３５】
ヒストグラム作成部２５は、パラメータによってあらかじめ定めておいた分割方法によって三次元物体を分割した後、分割によって定義された小領域に含まれる各三次元点の局所特徴量に基づいて、三次元物体を表現するヒストグラム特徴量を計算する。
【００３６】
ヒストグラム作成部２５において物体を分割する際、三次元物体の性質に応じて適応的に水平方向と垂直方向を決定した後、三次元物体を覆うバウンディングボックスを定義し、その後バウンディングボックスを水平方向と垂直方向に分割することにより小領域を定義する。
【００３７】
三次元物体に応じた水平方向と垂直方向の決定の仕方としては、実世界を計測して得られた三次元データであれば重力が向いている方向やその反対の方向、あるいは地面と直交する軸を垂直方向とし、これに直交する方向として水平方向を決めるなどの方法がある。その他の方法としては、三次元物体を構成する点を対象として主成分分析を実施した結果得られる三つの固有ベクトルについて、固有値が大きなものから順に新たなｘ軸、ｙ軸、ｚ軸として、ｚ軸が向いている方向を垂直方向、これに直交する方向を水平方向とするなどの方法がある。本実施例においては重力と反対の方向を垂直方向とした。このようにして決定した物体の垂直方向と三次元物体が存在している空間のｚ軸が一致するように三次元物体を回転させる。
【００３８】
回転が施された三次元物体に対して、バウンディングボックスは三次元物体に含まれる各点が持つｘ、ｙ、ｚ座標値のそれぞれについての最小値と最大値を持つ２点、（ｘmin、ｙmin、ｚmin）と（ｘmax、ｙmax、ｚmax）によって定義される直方体である（図７参照）。
【００３９】
このようにして定義されたバウンディングボックスを分割するために、まず、パラメータr（0≦r≦1）が与えられたときに角柱Trを次のように定義する。
【００４０】
【数１】
2018013927.tif 000003
この定義を用いて、0≦r1＜r2≦1を満たす二つのパラメータr1とr2が与えられたとき、分割された立体U(r1,r2)を次のように定義する。
【００４１】
【数２】
2018013927.tif 000004
【００４２】
これは図８に示すような、角柱の中心部、あるいは角柱の中心部をくりぬいたような立体を示す。すわなち、バウンディングボックスの中央部の角柱部分と、中央部の角柱部分を含み、かつ、中央部の角柱部分より大きい角柱部分のうち、中央部の角柱部分を除いた環状部分と、内側の環状部分を含み、かつ、内側の環状部分より大きい角柱部分のうち、内側の全ての環状部分及び中央部の角柱部分を除いた環状部分とに分割する。
【００４３】
この立体U(r1,r2)をさらに水平面を用いて分割して出来る立体V(r1,r2,s1,s2)を0≦s1＜s2≦1を満たすパラメータを用いて次のように定める（図９参照）。
【００４４】
【数３】
2018013927.tif 000005
【００４５】
ヒストグラム作成部２５は、これらの定義を用いて、あらかじめ定めたパラメータである垂直分割パラメータPと水平分割パラメータHを用いて、上記方法を用いて入力物体に対して定義されたバウンディングボックスBを次式のように共有部分を持たない複数の立体V(ri-1,ri,sj-1,sj)に分割する。
【００４６】
【数４】
2018013927.tif 000006
ここでNPとNHはそれぞれPとHに含まれる添え字付けられた実数の数を表す。
【００４７】
分割された各立体V(ri-1,ri,sj-1,sj)の小領域に含まれる局所特徴量のみから、各クラスタに割り当てられた局所特徴量の数をカウントし、分割して作成された各小領域に対応するヒストグラム特徴量を作成する。立体V(ri-1,ri,sj-1,sj)の小領域に含まれる局所特徴量から作られたヒストグラム特徴量をVijとすると、バウンディングボックスに含まれる物体全体に対して定義されるヒストグラム特徴量Fは、Vijを一列に並べることによって得られる。
【００４８】
【数５】
2018013927.tif 000007
【００４９】
ここで、ヒストグラム特徴量を並べる際に各ヒストグラム特徴量に対して小領域の位置などに応じた重みをかけたものを並べても良い。たとえば、Vijに対する重みをWijとすると、
2018013927.tif 000008
などとすることによって、バウンディングボックスの中心から離れた領域が検索に与える影響を相対的に小さくするといったことが可能である。上式はすべての重みを１とした場合に相当する。また、VijがK次元実数値ベクトルであるから、ここで求めたFは、K×(NP-1)×(NH-1)次元の実数値ベクトルである。
【００５０】
このようにバウンディングボックスを分割してからヒストグラム特徴量を計算することによって、バウンディングボックス内の物体の水平面内での回転に対しておおよそ不変でありながら、物体を構成するパーツのおおよその位置情報をもつヒストグラム特徴量を計算することができる。
【００５１】
上記方法によって、データベースを構成する三次元物体集合に含まれる各三次元物体に対して計算されたヒストグラム特徴量を三次元物体記憶部３４に格納する。したがって三次元物体記憶部３４には三次元物体集合に含まれる三次元物体と同じ数、すなわちN個のヒストグラム特徴量が格納される（図５参照）。
【００５２】
局所特徴量計算部４０は、基礎データ記憶部２１に格納された検索対象物体の三次元物体情報に基づいて、検索対象物体からサンプリングされた各点について、局所特徴量を計算し、局所特徴量記憶部３０に格納する。ここでは、局所特徴量計算部２３と同様の、サンプリング方法と局所特徴量を算出する（上記非特許文献２参照）。
【００５３】
局所特徴量割当部４２は、クラスタ記憶部３２に格納された各クラスタのクラスタ中心と、局所特徴量計算部４０によって検索対象物体を表す三次元物体の各点について計算された局所特徴量とに基づいて、各クラスタに、検索対象物体を表す三次元物体の各点について計算された局所特徴量の各々を割り当てる。
【００５４】
ヒストグラム作成部４４は、ヒストグラム作成部２５と同様のパラメータ及び方法で検索対象物体を覆うバウンディングボックスを分割し、分割によって得られた各小領域に含まれる局所特徴量を局所特徴量割当部４２によって各クラスタに割り当てた結果から、各クラスタに割り当てられた局所特徴量の数を計算し、検索対象物体の一部を表現する、各クラスタの出現頻度を表すヒストグラム特徴量を計算し、各小領域に対して作成されたヒストグラム特徴量をつなぎ合わせることによって、検索対象物体を表すヒストグラム特徴量を計算する。
【００５５】
ヒストグラム比較部４６は、ヒストグラム作成部４４によって計算された検索対象物体のヒストグラム特徴量と、ヒストグラム作成部２５によって計算され三次元物体記憶部３４に格納されているN個のヒストグラム特徴量の類似度を正規化コサイン類似度によって計算し、三次元物体記憶部３４に格納された各物体と検索対象物体との類似度を比較結果記憶部３６に格納する（図６参照）。二つのヒストグラム特徴量F1、F2の正規化コサイン類似度Sは次式で表される。
【００５６】
【数６】
2018013927.tif 000009
【００５７】
ここで・は内積の演算子を表し、
2018013927.tif 000010
はベクトルのL2ノルムを表す。
【００５８】
ヒストグラム特徴量は実数値ベクトルであるため、ユークリッド距離やベクトル間の内積に基づく類似度、あるいはchi-square kernel等を利用した類似度の計算が可能である。
【００５９】
物体検索処理部４８は、比較結果記憶部３６に格納された類似度を参照し、類似度が大きい順にL個（Lは１以上の自然数）の物体を取り出し、検索結果として出力部５０に出力する。
【００６０】
次に、本発明の実施の形態に係る物体検索装置１００の作用について説明する。入力部１０において物体が存在する環境における３次元点群を受け付けて基礎データ記憶部２１に格納すると、物体検索装置１００は、図１０に示す前処理ルーチンを実行する。
【００６１】
まず、ステップＳ１００では、基礎データ記憶部２１に格納された、データベースを構成する三次元物体集合に含まれる三次元物体の各点について、局所特徴量を計算し、局所特徴量記憶部３０に記憶する。
【００６２】
ステップＳ１０２では、局所特徴量計算部２３によって計算されたＭ個の局所特徴量に基づいて、非特許文献１に記載のコードブック学習の手法を用いて、Ｋ個のクラスタについて、クラスタ中心を計算し、各クラスタにＭ個の局所特徴量の各々を割り当て、Ｍ個の局所特徴量の各々に対するクラスタ番号を局所特徴量記憶部３０に格納し、各クラスタのクラスタ中心をクラスタ記憶部３２に格納する。
【００６３】
ステップＳ１０４では、基礎データ記憶部２１に格納されたデータベースを構成する三次元物体集合に含まれる三次元物体のそれぞれに対して、バウンディングボックスを定義し、予め定められたパラメータを用いてバウンディングボックスをあらかじめ定めておいた分割方法によって垂直方向と水平方向に分割し、分割によって定義された小領域に含まれる局所特徴量のクラスタ番号を利用して、各小領域に対応したクラスタ番号の出現頻度からなるヒストグラム特徴量を計算し、各小領域に対して計算されたヒストグラム特徴量をつなぎ合わせることによって三次元物体を表現するヒストグラム特徴量を計算し、三次元物体記憶部３４に記憶する。
【００６４】
次に、物体検索処理ルーチンについて説明する。入力部１０において検索対象物体を受け付けて基礎データ記憶部２１に格納すると、物体検索装置１００は、図１１に示す物体検索処理ルーチンを実行する。
【００６５】
ステップＳ２００では、基礎データ記憶部２１に格納された検索対象物体の各点について、局所特徴量を計算し、局所特徴量記憶部３０に格納する。
【００６６】
ステップＳ２０２では、クラスタ記憶部３２に格納された各クラスタのクラスタ中心に基づいて、ステップＳ２００で検索対象物体を表す３次元物体の各点について計算された局所特徴量を、各クラスタに割り当てる。
【００６７】
ステップＳ２０４では、検索対象物体に対して、バウンディングボックスを定義し、予め定められたパラメータを用いてバウンディングボックスをあらかじめ定めておいた分割方法によって垂直方向と水平方向に分割し、分割によって定義された小領域に含まれる局所特徴量を利用して、ステップＳ２０２で局所特徴量をクラスタに割り当てた結果から、各小領域に対応したヒストグラム特徴量を計算し、各小領域に対して計算されたヒストグラム特徴量をつなぎ合わせることによって検索対象物体を表現するヒストグラム特徴量を計算する。
【００６８】
ステップＳ２０６では、ステップＳ２０４においてヒストグラム作成部４４によって計算された検索対象物体を表現するヒストグラム特徴量と、ヒストグラム作成部２５によって計算された三次元物体記憶部３４に格納されているデータベースを構成する三次元物体集合の各三次元物体を表現するヒストグラム特徴量の類似度を計算し、比較結果記憶部３６に計算した類似度を格納する。
【００６９】
ステップＳ２０８では、比較結果記憶部３６に格納された類似度を用いて、類似度が大きい順にＬ個の物体番号を取り出し、これを物体検索結果として出力部５０に出力し処理を終了する。
【００７０】
以上説明したように、本発明の実施の形態に係る物体検索装置によれば、三次元物体を構成する各点に対して点周辺の情報を表現する局所特徴量を計算し、局所特徴量をクラスタに対して割り当て、局所特徴量を割り当てた結果に基づき、物体を覆うバウンディングボックスを水平方向と垂直方向に分割することによって得られた各小領域内で各クラスタに割り当てられた局所特徴量の数をカウントすることにより小領域を表現するヒストグラム特徴量を計算し、小領域を表現するヒストグラム特徴量をつなぎ合わせることによって検索対象物体を表現するヒストグラム特徴量を計算し、検索対象を表現するヒストグラム特徴量と三次元物体集合から計算された集合内の各三次元物体を表現するヒストグラム特徴量の類似度を計算し、ヒストグラム特徴量の類似度が高い順に所定の個数の物体を取り出すことによって、精度よく、三次元物体集合の中から所望の物体を検索することができる。
【００７１】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００７２】
例えば、上述した実施の形態では物体検索装置１００について説明したがこの装置及び構成に限定されるものではない。例えば、検索対象物体をモデル化するために、基礎データ記憶部２１と、局所特徴量記憶部３０と、クラスタ記憶部３２と、局所特徴量計算部４０と、局所特徴量割当部４２と、ヒストグラム作成部４４と、を含む三次元物体モデル化装置として構成するようにしてもよい。
【符号の説明】
【００７３】
１０   入力部
２０   演算部
２２   前処理部
２１   基礎データ記憶部
２３   局所特徴量計算部
２４   クラスタリング部
２５   ヒストグラム作成部
３０   局所特徴量記憶部
３２   クラスタ記憶部
３４   三次元物体記憶部
３６   比較結果記憶部
４０   局所特徴量計算部
４２   局所特徴量割当部
４４   ヒストグラム作成部
４６   ヒストグラム比較部
４８   物体検索処理部
５０   出力部
１００ 物体検索装置
【図１】
2018013927.tif 000011
【図２】
2018013927.tif 000012
【図３】
2018013927.tif 000013
【図４】
2018013927.tif 000014
【図５】
2018013927.tif 000015
【図６】
2018013927.tif 000016
【図７】
2018013927.tif 000017
【図８】
2018013927.tif 000018
【図９】
2018013927.tif 000019
【図１０】
2018013927.tif 000020
【図１１】
2018013927.tif 000021