(57)【要約】      （修正有）【課題】３次元シーン中の対象物をより高速に認識する。【解決手段】３次元モデル点群およびシーン点群のデータを取得するＳ１００。モデル点群から選択されたポイントペアの幾何学的関係を規定するポイントペア特徴量とポイントペアとを関連付けて第１のテーブルに記録するＳ１１０。モデル点群のデータおよび第１のテーブルに基づいて、モデル点群から、複数のキーポイントを選択するＳ１２０。第１のテーブルに記録されたデータのうち、複数のキーポイントに関するデータのみを残した第２のテーブルを構築するＳ１３０。３次元シーンに含まれる１以上の物体の表面形状を表すシーン点群のデータを取得するＳ１４０。シーン点群のデータ、および第２のテーブルに基づいて、３次元シーン中の対象物の位置および姿勢を推定するＳ１５０。【選択図】図５
2018189510.tif 000002
【特許請求の範囲】
【請求項１】
３次元シーンにおける対象物の位置および姿勢を推定する方法であって、
前記対象物の表面の３次元形状を表すモデル点群のデータを取得するステップと、
前記モデル点群から選択されたポイントペアの幾何学的関係を規定するポイントペア特徴量（Ｐｏｉｎｔ  Ｐａｉｒ  Ｆｅａｔｕｒｅ）を、各ポイントペアについて計算し、前記ポイントペア特徴量と前記ポイントペアとを関連付けて第１のテーブルに記録するステップと、
前記モデル点群のデータおよび前記第１のテーブルに基づいて、前記モデル点群から、複数のキーポイントを選択するステップと、
前記第１のテーブルに記録されたデータのうち、前記複数のキーポイントに関するデータのみを残した第２のテーブルを構築するステップと、
前記３次元シーンに含まれる１以上の物体の表面形状を表すシーン点群のデータを取得するステップと、
前記シーン点群のデータ、および前記第２のテーブルに基づいて、前記３次元シーン中の前記対象物の位置および姿勢を推定するステップと、
を含む方法。
【請求項２】
前記複数のキーポイントを選択するステップは、
前記モデル点群における点ｍｉ（ｉは１以上Ｎｍ以下の整数、Ｎｍは前記モデル点群に含まれる点の数）と、点ｍｉからの距離が閾値よりも短い参照領域に含まれる点ｍｊ（ｊは１以上Ｍ以下の整数、Ｍは前記参照領域に含まれる点の数）とのポイントペア特徴量をそれぞれ計算するステップと、
前記第１のテーブルを参照して、計算した前記ポイントペア特徴量に類似するポイントペア特徴量をもつ少なくとも１つのポイントペアを探索するステップと、
探索した前記ポイントペアの各々について、点ｍｉおよび点ｍｊの対に整合させるための座標変換パラメータを決定するステップと、
点ｍｉのうち、決定した前記座標変換パラメータの各々を用いて前記モデル点群の座標を変換したとき、前記参照領域に含まれる全ての点の近傍に、変換後のモデル点群のいずれかの点が位置する場合の数が最小になる点ｍｉを、キーポイントとして選択するステップと、
を含む、請求項１に記載の方法。
【請求項３】
前記複数のキーポイントの個数は、前記モデル点群の点の個数の１／１００００倍以上１／２倍以下である、請求項１または２に記載の方法。
【請求項４】
前記複数のキーポイントの個数は、前記モデル点群の点の個数の１／１０００倍以上１／１００倍以下である、請求項１から３のいずれかに記載の方法。
【請求項５】
前記対象物の位置および姿勢を推定するステップは、
前記シーン点群における各点ｓｉ（ｉは１以上Ｎｓ以下の整数、Ｎｓは前記シーン点群に含まれる点の数）からの距離が、前記モデル点群に含まれる最も離れた２点間の距離以下である点の集合から、一部の点群Ｓｒを選択するステップと、
点ｓｉと、点群Ｓｒ内の各点Ｓｒｊ（ｊは１以上Ｍｓ以下の整数）とのポイントペア特徴量を計算するステップと、
前記第２のテーブルを参照して、計算した前記ポイントペア特徴量に類似するポイントペア特徴量をもつ少なくとも１つのポイントペアを探索するステップと、
探索した前記ポイントペアの各々について、点ｓｉおよび点Ｓｒｊの対に整合させるための座標変換パラメータを決定し、前記座標変換パラメータが示す姿勢ごとにカウント数を決定するステップと、
前記カウント数を決定した姿勢の中から、前記カウント数が多い順に複数の候補姿勢を選択するステップと、
前記複数の候補姿勢の中から、前記モデル点群と前記シーン点群との整合度が最も高くなる姿勢を、最終的な姿勢として決定するステップと、
を含む、請求項１から４のいずれかに記載の方法。
【請求項６】
請求項１から５に記載の方法をコンピュータに実行させるコンピュータプログラム。
【請求項７】
請求項６に記載のコンピュータプログラムを格納したメモリと、
前記コンピュータプログラムを実行するプロセッサと、
を備える処理装置。
【請求項８】
請求項７に記載の処理装置と、
エンドエフェクタと、
前記処理装置によって推定された前記対象物の位置および姿勢の情報に基づいて、前記エンドエフェクタを制御する制御回路と、
を備えるロボット。
【請求項９】
請求項７に記載の処理装置と、
ロボットと、
前記シーン点群データを取得する３次元センサと、
前記処理装置によって推定された前記対象物の位置および姿勢の情報に基づいて、前記ロボットを制御する制御回路と、
を備えるロボットシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、３次元シーンの中から対象物を認識してその姿勢を推定するための技術に関する。
【背景技術】
【０００２】
３次元シーンの中から、対象物を認識してその位置および姿勢を推定する様々な技術が開発されている。例えば、特許文献１および非特許文献１は、ポイントペア特徴量（Ｐｏｉｎｔ  Ｐａｉｒ  Ｆｅａｔｕｒｅ：ＰＰＦ）と呼ばれる特徴量を用いて、３次元物体を効果的に認識する方法を開示している。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許第８８３０２２９号明細書
【非特許文献】
【０００４】
【非特許文献１】Drost et al. "Model globally, match locally: Efficient and robust 3D object recognition", 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 13 June 2010, pp 998-1005
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本願は、３次元シーン中の対象物を、より高速に認識することが可能な技術を提供する。
【課題を解決するための手段】
【０００６】
本発明の一態様に係る方法は、３次元シーンにおける対象物の位置および姿勢を推定する方法である。前記方法は、前記対象物の表面の３次元形状を表すモデル点群のデータを取得するステップと、前記モデル点群から選択されたポイントペアの幾何学的関係を規定するポイントペア特徴量（Ｐｏｉｎｔ  Ｐａｉｒ  Ｆｅａｔｕｒｅ）を、各ポイントペアについて計算し、前記ポイントペア特徴量と前記ポイントペアとを関連付けて第１のテーブルに記録するステップと、前記モデル点群のデータおよび前記第１のテーブルに基づいて、前記モデル点群から、複数のキーポイントを選択するステップと、前記第１のテーブルに記録されたデータのうち、前記複数のキーポイントに関するデータのみを残した第２のテーブルを構築するステップと、前記３次元シーンに含まれる１以上の物体の表面形状を表すシーン点群のデータを取得するステップと、前記シーン点群のデータ、および前記第２のテーブルに基づいて、前記３次元シーン中の前記対象物の位置および姿勢を推定するステップと、を含む。
【０００７】
上記の包括的または具体的な態様は、装置、システム、方法、集積回路、コンピュータプログラム、記録媒体、またはこれらの任意の組み合わせによって実現され得る。
【発明の効果】
【０００８】
本発明の実施形態によれば、３次元シーン中の対象物をより高速に認識することができる。
【図面の簡単な説明】
【０００９】
【図１】例示的な実施形態におけるロボットシステムを模式的に示す図である。
【図２】制御装置１００の構成の一例を簡易的に示すブロック図である。
【図３】３次元センサ３００および制御装置１００を備えるロボット２００の一例を示す図である。
【図４】実施形態における物体認識処理の概要を示す図である。
【図５】信号処理回路１２０が実行する動作の全体の流れを示すフローチャートである。
【図６】ポイントペア特徴量（ＰＰＦ）を説明するための図である。
【図７】ハッシュテーブルの一例を示す図である。
【図８】特許文献１の図６に示されている図である。
【図９】実施形態におけるキーポイントの選択処理を示すフローチャートである。
【図１０Ａ】立方体形状のモデルの例を示す図である。
【図１０Ｂ】点ｍ０と、領域ＭＫ内の他の点ｍ１とから計算されるＰＰＦが、ハッシュテーブルにおけるＰＰＦと照合されることを示す図である。
【図１０Ｃ】点ｍ０について検出された同一のＰＰＦをもつポイントペアの組み合わせと、それらの各ポイントペアについて算出された姿勢との対応の例を示す図である。
【図１０Ｄ】モデル中のポイントペア（ｍｐ，ｍｑ）に対応付けられた座標変換パラメータ（局所座標）を用いてモデル全体を座標変換した場合の例を示す図である。
【図１０Ｅ】モデル中のポイントペア（ｍｘ，ｍｙ）に対応付けられた座標変換パラメータ（局所座標）を用いてモデル全体を座標変換した場合の例を示す図である。
【図１０Ｆ】角またはエッジにおける参照領域の例を示す図である。
【図１１】図５におけるステップＳ１５０の処理をより詳細に示すフローチャートである。
【図１２Ａ】２次元の積分画像を説明するための図である。
【図１２Ｂ】３次元積分画像を説明するための図である。
【図１３】シミュレーション実験に用いたモデルを示す図である。
【図１４Ａ】合成シーンについてのシミュレーション結果を示すグラフである。
【図１４Ｂ】合成シーンについてのシミュレーション結果を示すグラフである。
【図１５】工業部品についての認識結果の一例を示す画像である。
【図１６】現実のシーンについて、オクルージョンの割合を変化させたときの認識率の変化の例を示すグラフである。
【発明を実施するための形態】
【００１０】
（本発明の基礎となった知見）
本発明の実施形態を説明する前に、本発明の基礎となった知見を説明する。
【００１１】
３次元シーンの中から特定の物体を認識してその位置および姿勢を推定する技術は、例えばビンピッキングを行うロボットを実現する上で重要である。ビンピッキングとは、不規則な位置および姿勢で積み重ねられた複数の物体の中から特定の物体を把持して指定の場所に運ぶことを指す。そのような作業を行うロボットを実現するためには、乱雑に積み重ねられた複数の物体の中から、特定の物体の位置および姿勢を正確かつ迅速に認識することが求められる。
【００１２】
従来、３次元データから円または四角形などの単純な幾何形状を検出することによって物体を認識することは比較的容易に実現可能であった。例えば円筒形状のボルト、リング形状のベアリング、あるいは直方体形状の箱などの単純な形状の物体については、比較的正確に認識することができた。しかし、単純な幾何形状ではない形状をもつ物体（例えば工業用部品等）については、上記のような方法では正しく検出することが困難であった。
【００１３】
特許文献１および非特許文献１（以下、"Drost"と呼ぶ）は、Ｐｏｉｎｔ  Ｐａｉｒ  Ｆｅａｔｕｒｅ（ＰＰＦ）と呼ばれる特徴量を用いることにより、対象物の姿勢を従来よりも効果的に推定する方法を開示している。ＰＰＦは、３次元点群（３Ｄ  ｐｏｉｎｔ  ｃｌｏｕｄ）における２点間の変位ベクトルと、その２点における法線ベクトルとの幾何学的関係を記述する４次元量である。ＰＰＦは、２点間の変位ベクトルの大きさと、変位ベクトルおよび第１の点の法線ベクトルのなす角度と、変位ベクトルおよび第２の点の法線ベクトルのなす角度と、これらの２点の法線ベクトル同士がなす角度とによって記述される。Drostの方法では、物体の表面の３次元形状を表すモデル点群（ｍｏｄｅｌ  ｃｌｏｕｄ）における全ての２点のペアごとにＰＰＦが計算される。そのＰＰＦとポイントペアの情報とがハッシュテーブルに記録される。このハッシュテーブルに記録されたＰＰＦを利用することにより、シーン点群（ｓｃｅｎｅ  ｃｌｏｕｄ）からモデル点群に相当する部分が検出される。
【００１４】
Drostに開示された方法は、任意の形状の物体に適用でき、ある程度正確に対象物を認識することが可能である。しかしながら、本発明者らの検討によれば、例えば工業用部品のように、多くのポイントペアが類似するＰＰＦをもつような物体においては、認識速度が低下するという課題があることがわかった。
【００１５】
以上の知見に基づき、本発明者らは、上記課題を解決し得る新規な物体認識技術を開発するに至った。
【００１６】
本発明の一態様における方法は、
３次元シーンにおける対象物の位置および姿勢を推定する方法であって、
前記対象物の表面の３次元形状を表すモデル点群のデータを取得するステップと、
前記モデル点群から選択されたポイントペアの幾何学的関係を規定するポイントペア特徴量（Ｐｏｉｎｔ  Ｐａｉｒ  Ｆｅａｔｕｒｅ：ＰＰＦ）を、各ポイントペアについて計算し、前記ポイントペア特徴量と前記ポイントペアとを関連付けて第１のテーブルに記録するステップと、
前記モデル点群のデータおよび前記第１のテーブルに基づいて、前記モデル点群から、複数のキーポイントを選択するステップと、
前記第１のテーブルに記録されたデータのうち、前記複数のキーポイントに関するデータのみを残した第２のテーブルを構築するステップと、
前記３次元シーンに含まれる１以上の物体の表面形状を表すシーン点群のデータを取得するステップと、
前記シーン点群のデータ、および前記第２のテーブルに基づいて、前記３次元シーン中の前記対象物の位置および姿勢を推定するステップと、
を含む。
【００１７】
上記態様によれば、前記第１のテーブルに記録されたデータのうち、前記複数のキーポイントに関するデータのみを残した第２のテーブルを構築する。そして、前記シーン点群のデータ、および前記第２のテーブルに基づいて、前記３次元シーン中の前記対象物の位置および姿勢を推定する。これにより、対象物の位置および姿勢を推定するステップを高速化することができる。
【００１８】
第１のテーブルは、Drostに開示されたハッシュテーブルに相当する。このハッシュテーブルは、多くのデータを含むため、計算量が多くなるという課題がある。モデル点群における点の数をＮｍとすると、ハッシュテーブルに記録されるポイントペアの数は、Ｎｍ（Ｎｍ−１）である。これに対し、第２のテーブルは、モデル点群の中から選択された一部の点（キーポイント）に関するデータのみを含むため、より少ないデータ数をもつ。キーポイントの個数をＮｋ（＜Ｎｍ）とすると、ハッシュテーブルに記録されるポイントペアの数は、Ｎｋ（Ｎｍ−１）にまで削減することができる。キーポイントの数Ｎｋは、例えば、モデル点群に含まれる点の数Ｎｍの１／１００００倍以上１／２倍以下に設定され得る。ある例では、キーポイントの数Ｎｋは、例えば、モデル点群に含まれる点の数Ｎｍの１／１０００倍以上１／１００倍以下に設定され得る。このように少数のキーポイントが選択される場合には、ハッシュテーブルを用いた姿勢推定に要する計算時間を大幅に短縮することができる。
【００１９】
キーポイントは、モデル点群の中から所定の基準に基づいて厳選された好ましい点の集合である。キーポイントは、例えば、姿勢の独自性が高いと判断される点から選択される。複数のキーポイントを選択する処理は、例えば以下のステップを含み得る。
（ａ）前記モデル点群における点ｍｉ（ｉは１以上Ｎｍ以下の整数、Ｎｍは前記モデル点群に含まれる点の数）と、点ｍｉからの距離が閾値よりも短い参照領域に含まれる点ｍｊ（ｊは１以上Ｍ以下の整数、Ｍは前記参照領域に含まれる点の数）とのポイントペア特徴量をそれぞれ計算する。
（ｂ）前記第１のテーブルを参照して、計算した前記ポイントペア特徴量に類似するポイントペア特徴量をもつ少なくとも１つのポイントペアを探索する。
（ｃ）探索した前記ポイントペアの各々について、点ｍｉおよび点ｍｊの対に整合させるための座標変換パラメータを決定する。
（ｄ）点ｍｉのうち、決定した前記座標変換パラメータの各々を用いて前記モデル点群の座標を変換したとき、前記参照領域に含まれる全ての点の近傍に、変換後のモデル点群のいずれかの点が位置する場合の数が最小になる点ｍｉを、キーポイントとして選択する。
【００２０】
上記の処理によれば、姿勢の独自性の高い点がキーポイントとして選択されるので、後に続く推定処理を高速化することができる。
【００２１】
対象物の位置および姿勢を推定する処理は、例えば以下のステップを含み得る。
（ｅ）前記シーン点群における各点ｓｉ（ｉは１以上Ｎｓ以下の整数、Ｎｓは前記シーン点群に含まれる点の数）からの距離が、前記モデル点群に含まれる最も離れた２点間の距離以下である点の集合から、一部の点群Ｓｒを選択する。
（ｆ）点ｓｉと、点群Ｓｒ内の各点Ｓｒｊ（ｊは１以上Ｍｓ以下の整数）とのポイントペア特徴量を計算する。
（ｇ）前記第２のテーブルを参照して、計算した前記ポイントペア特徴量に類似するポイントペア特徴量をもつ少なくとも１つのポイントペアを探索する。
（ｈ）探索した前記ポイントペアの各々について、点ｓｉおよび点Ｓｒｊの対に整合させるための座標変換パラメータを決定し、前記座標変換パラメータが示す姿勢ごとにカウント数を決定する。
（ｉ）前記カウント数を決定した姿勢の中から、前記カウント数が多い順に複数の候補姿勢を選択する。
（ｊ）前記複数の候補姿勢の中から、前記モデル点群と前記シーン点群との整合度が最も高くなる姿勢を、最終的な姿勢として決定する。
【００２２】
上記の処理によれば、シーン点群の全ての点について、モデル点群との照合が行われるため、より正確に物体の位置および姿勢を推定することができる。さらに、データ量の少ない第２のテーブルを参照するため、照合処理に要する時間を短縮することができる。
【００２３】
本明細書に開示される方法は、コンピュータプログラムを実行するコンピュータ、プロセッサ、または処理回路によって実現され得る。そのようなコンピュータプログラムは、例えば装置内のメモリに格納される。本開示は、そのようなコンピュータプログラムを格納したメモリと、当該コンピュータプログラムを実行するプロセッサまたは処理回路とを備える処理装置またはロボットを含む。
【００２４】
以下、本発明のより具体的な実施形態を説明する。ただし、必要以上に詳細な説明は省略する場合がある。例えば、既によく知られた事項の詳細説明や実質的に同一の構成に対する重複説明を省略する場合がある。これは、以下の説明が不必要に冗長になることを避け、当業者の理解を容易にするためである。なお、発明者は、当業者が本開示を十分に理解するために添付図面および以下の説明を提供するのであって、これらによって特許請求の範囲に記載の主題を限定することを意図するものではない。以下の説明において、同一または類似する構成要素については、同じ参照符号を付している。
【００２５】
（実施形態）
［１．構成］
図１は、本発明の例示的な実施形態におけるロボットシステムを模式的に示す図である。このシステムは、ロボット２００と、３次元センサ３００と、制御装置１００とを備えている。本実施形態では、制御装置１００が備える信号処理回路１２０が、メモリ１３０に格納されたプログラムを実行することにより、本開示の一態様に係る方法を実行する。
【００２６】
ロボット２００は、複数のアームと、エンドエフェクタ（ハンド）とを備え、物体を把持して移動させることができる。ロボット２００は、制御装置１００からの指令を受けて、箱の中に乱雑に積まれた複数の物体８００の中から、特定の物体を把持して指定の位置に運ぶ作業（ビンピッキング）を行う。ロボット２００は、その内部に複数の電気モータおよび各モータを制御する少なくとも１つの制御回路を備えている。これらの制御回路は、制御装置１００からの指令に応じて各モータを適切に制御し、ロボット２００に所望の動作を実行させる。
【００２７】
３次元センサ３００は、箱の中の複数の物体８００を撮影し、３次元点群データを生成して出力する。この３次元点群データを、以下、「シーン点群データ」と称する。３次元センサ３００は、撮影対象の領域における距離分布などの３次元データを取得し、そのデータに基づいて３次元点群データを生成して出力する。３次元センサ３００は、例えばレーザレンジファインダ、ＴＯＦ（Ｔｉｍｅ  ｏｆ  Ｆｌｉｇｈｔ）カメラ、またはステレオカメラによって実現され得る。
【００２８】
「３次元点群」とは、３次元空間中に存在する１つ以上の物体の表面に分布する複数の点の集合を意味する。本実施形態においては、３次元センサ３００によって取得されるシーン点群データの他に、検出対象の物体（以下、「対象物」と称することがある）の３次元点群を示すモデル点群データが予め用意される。そのようなモデル点群データは、制御装置１００が有する記録媒体に格納されている。
【００２９】
制御装置１００は、ロボット２００および３次元センサ３００に有線または無線で接続され、これらの動作を制御する。制御装置１００は、３次元センサ３００によって取得されたシーン点群データと、予め用意されたモデル点群データとに基づいて、３次元シーンにおける検出対象の物体を認識し、その姿勢を推定する。
【００３０】
図２は、制御装置１００の構成の一例を簡易的に示すブロック図である。制御装置１００は、例えば汎用または専用のコンピュータであり、制御回路１１０と、信号処理回路１２０と、メモリ１３０とを備えている。制御装置１００は、他にも、通信回路、入／出力インタフェース、ハードディスクドライブなどの記録装置、電源回路などの構成要素を備え得るが、図２では省略されている。図２には、ロボット２００および３Ｄセンサ３００以外に、ディスプレイ４００が示されている。ディスプレイ４００は、制御装置１００に接続され、信号処理回路１２０による処理結果を表示する。
【００３１】
制御回路１１０は、例えばＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）などのプロセッサによって実現され得る。制御回路１１０は、メモリ１３０（例えばＤＲＡＭまたはＳＲＡＭ）に格納されたコンピュータプログラムを実行することにより、ロボット２００、３Ｄセンサ３００、および信号処理回路１２０を制御する。
【００３２】
信号処理回路１２０は、例えばＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）などのプロセッサによって実現され得る。信号処理回路１２０は、メモリ１３０に格納されたコンピュータプログラムを実行することにより、本実施形態における対象物の認識処理を行う。
【００３３】
図１および図２に示すシステムの構成は一例にすぎず、多様な変形が可能である。例えば、３次元センサ３００および制御装置１００の一方または両方は、ロボット２００内部に組み込まれていてもよい。
【００３４】
図３は、３次元センサ３００および制御装置１００を備えるロボット２００の一例を示す図である。このロボット２００は、エンドエフェクタ２２０の近傍に３次元センサ３００を備えている。ロボット２００はまた、筐体内に、制御装置１００を備えている。この例では、ロボット２００内の制御装置１００が、後述する認識処理を実行し、その結果に応じてアームおよびエンドエフェクタ２２０を制御する。ロボット２００はまた、３次元データを取得するために用いられる光源を備えていてもよい。そのような光源は、例えば可視光または近赤外線を発するレーザまたは発光ダイオードを含み得る。
【００３５】
［２．動作］
次に、制御装置１００内の信号処理回路１２０が実行する物体認識処理を説明する。
【００３６】
図４は、本実施形態における物体認識処理の概要を示す図である。図示されるように、本実施形態では、３次元センサ３００による３次元計測により、シーン点群データが取得される。また、モデルの３次元点群の分布を示すモデル点群データが予め用意されている。信号処理回路１２０は、これらの２種類の点群データを取得し、両者を照合する。これにより、３次元シーンの中から、モデルと同一の物体を認識し、結果を出力する。検出結果は、例えばディスプレイ４００に画像データとして出力され得る。
【００３７】
図５は、信号処理回路１２０が実行する動作の全体の流れを示すフローチャートである。本実施形態における処理は、オフラインフェーズとオンラインフェーズとを含む。オフラインフェーズは、３次元計測を行う前に行われる準備段階のフェーズである。オンラインフェーズは、３次元計測を行った後に行われるフェーズである。
【００３８】
オフラインフェーズは、ステップＳ１００、Ｓ１１０、Ｓ１２０、Ｓ１３０を含む。ステップＳ１００において、信号処理回路１２０は、モデル点群データをメモリ１３０から取得する。次に、ステップＳ１１０において、モデル点群における全ての２点間のＰＰＦを計算し、ハッシュテーブルに記録する。このハッシュテーブルは、前述の第１のテーブルに該当する。ステップＳ１２０において、信号処理回路１２０は、ハッシュテーブルに基づいて、モデル点群から、複数のキーポイントを選択する。複数のキーポイントは、モデル点群のうち、姿勢の独自性が高いと判断される特別な点である。ステップＳ１２０の詳細な処理については後述する。ステップＳ１３０において、信号処理回路１２０は、キーポイント以外の点に関するデータを除外したハッシュテーブルを再構築する。この再構築されたハッシュテーブルは、前述の第２のテーブルに該当する。再構築されたハッシュテーブルは、元のハッシュテーブルよりも少ないデータ量を有する。
【００３９】
以上のオフラインフェーズにおける処理により、オンラインフェーズで利用されるハッシュテーブルが構築される。このハッシュテーブルは、物体を正確に認識する上で好ましいと考えられる少数の厳選されたキーポイントに関するデータのみを含む。このため、オンラインフェーズにおける動作をより高速かつ正確に行うことができる。
【００４０】
オフラインフェーズは、ステップＳ１４０およびＳ１５０を含む。ステップＳ１４０において、信号処理回路１２０は、まずシーン点群データを取得する。シーン点群データは、３次元認識を開始する際に制御回路１１０の指示に基づいて３次元センサ３００が取得し、メモリ１３０に格納される。信号処理回路１２０は、制御回路１１０の指示に従い、メモリ１３０からシーン点群データを取得する。ステップＳ１５０において、信号処理回路１２０は、シーン点群データと、再構築したハッシュテーブルとに基づいて、シーン中の対象物の位置および姿勢を推定する。本実施形態では、Drostに開示された投票スキームを改良した方法が用いられる。詳細は後述するが、本実施形態ではシーン点群の各点について、多くの姿勢の候補が選定され、その中から、最も正しいと推定される姿勢が決定される。Drostの方法とは異なり、シーン点群中の全ての点について姿勢の検証が行われるため、より正確に対象物の姿勢を推定することができる。
【００４１】
［２−１．ＰＰＦおよびハッシュテーブル］
本実施形態において用いられるポイントペア特徴量（ＰＰＦ）およびハッシュテーブルを説明する。
【００４２】
図６は、ＰＰＦを説明するための図である。ＰＰＦは、法線ベクトルをもつ２つの点の相対的な位置および向きを表す。２つの点をｍ１およびｍ２とし、それらの点の法線ベクトルを、それぞれｎ１およびｎ２とする。点ｍ１およびｍ２のＰＰＦをＦ（ｍ１、ｍ２）と表現する。Ｆ（ｍ１、ｍ２）は、次の式（１）で表される。
【数１】
2018189510.tif 000003
ｄは、点ｍ１から点ｍ２へのベクトルを表す。∠（ａ，ｂ）は、ベクトルａおよびｂのなす角度（０以上π以下の実数）を表す。ｆ１、ｆ２、ｆ３、ｆ４の意味は、以下のとおりである。
ｆ１：点ｍ１およびｍ２の間の距離
ｆ２：ベクトルｄと法線ベクトルｎ１との角度
ｆ３：ベクトルｄと法線ベクトルｎ２との角度
ｆ４：法線ベクトルｎ１、ｎ２間の角度
【００４３】
本実施形態では、ステップＳ１１０において、モデル点群における全ての２点間のＰＰＦが計算され、ハッシュテーブルに格納される。
【００４４】
図７は、ハッシュテーブルの一例を示す図である。図示されるように、ハッシュテーブルは、ＰＰＦをキーとして、ＰＰＦと、対応するポイントペアとの関係を規定する。ＰＰＦにおける各成分ｆ１、ｆ２、ｆ３、ｆ４は、離散化されており、各成分の値が近い複数のＰＰＦは、同一のＰＰＦとして処理される。
【００４５】
［２−２．投票スキーム］
本実施形態におけるキーポイントの選択は、Drostに開示された投票スキームを一部利用している。このため、本実施形態におけるキーポイントの選択処理を説明する前に、Drostに開示された投票スキームを説明する。
【００４６】
Drostは、投票空間を２次元に減少させる効果的な投票スキームを提案している。Drostの方法では、オンラインフェーズにおいて、シーン点群における参照点ｓｒと他の点ｓｉとから、ＰＰＦすなわちＦ（ｓｒ，ｓｉ）が計算され、このＰＰＦがハッシュテーブルの中から探索される。これにより、類似するＰＰＦをもつモデルポイントペア（ｍｒ，ｍｉ）が探索される。参考のため、特許文献１の図６を図８として引用する。図８に示すように、モデルポイントペアをシーンポイントペアに揃えるために、次の２つのステップが実行される。
（ａ）ポイントペア（ｓｒ，ｓｉ）および（ｍｒ，ｍｉ）の各参照点を原点に並進移動させ、それらの法線をｘ軸に合せる。それらの並進行列をＴｍ、Ｔｓとする。
（ｂ）モデルポイントペア（ｍｒ，ｍｉ）をｘ軸のまわりに、シーンポイントペア（ｓｒ，ｓｉ）に一致するまで回転させる。
【００４７】
モデルポイントペア（ｍｒ，ｍｉ）と、シーンポイントペア（ｓｒ，ｓｉ）は、類似するＰＰＦをもつので、ｘ軸のまわりに回転させることにより、点ｍｉの位置および法線を、点ｓｉの位置および法線にほぼ一致させることができる。回転角をαとし、回転行列をＲｘ（α）とする。ｍｒとαとのペア（ｍｒ，α）は、局所座標（local coordinate）と呼ばれる。上記の操作により、２次元の累積テーブル（accumulator table)Ｔ（ｍｒ，α）が生成される。このテーブルに、局所座標の投票、つまり局所座標が何回現れるかが記録される。局所座標は、点Ｓｒの姿勢の候補を表す。回転角αを用いた座標変換は、以下の式（２）で表される。
【数２】
2018189510.tif 000004
【００４８】
Drostの方法においては、シーン点群の中から一部の参照点ｓｒが選択され、参照点ｓｒごとに、ｓｉを変えながら局所座標の投票が行われる。投票数の多い複数の局所座標に対応する複数の姿勢をクラスタリングして平均化するなどの処理を行うことにより、最終的な姿勢が決定される。
【００４９】
［２−３．キーポイントの選択］
オフラインフェーズにおけるキーポイント選択処理（ステップＳ１２０）の詳細を説明する。キーポイントの選択は、本実施形態における姿勢推定アルゴリズムにおいて極めて重要である。本実施形態においては、モデル点群の中から、いくつかのキーポイントが選択され、それらに対応する点および姿勢がシーン点群の中から探索される。このため、良好なキーポイントを選択することが重要である。本実施形態では、モデル点群の中から、独自性の高い点が選択される。これにより、物体認識の精度を高めることができる。
【００５０】
本実施形態では、オフラインフェーズにおいて、上記の投票スキームの考え方を利用して、モデル点群の中から独自性が高いと考えられるキーポイントが選択される。キーポイントを選択するために、モデル点群における点ｍｉおよびその周辺の点群を、シーン点群であるものとみなす。そして、そのシーンクラウドの姿勢を、前述の投票スキームを用いて推定する。仮に少数の姿勢のみが推定できた場合、そのシーンクラウドは十分に特別である、つまりそのｍｉはキーポイントとして適していると考える。
【００５１】
図９は、本実施形態におけるキーポイントの選択処理を示すフローチャートである。図示されるように、キーポイントは、例えば次の処理によって選択される。
【００５２】
１）モデル点群における全ての点ｍｉ（ｉは、１以上Ｎｍ以下の整数、Ｎｍはモデル点群に含まれる点の数）について、ｍｉからの距離が閾値よりも短い領域（参照領域と呼ぶ）内に含まれる点の集合を、ＭＫｉとする（ステップＳ１２１）。
【００５３】
２）ｍｉとＭＫｉ内の他の各点ｍｊ（ｊは、１以上Ｍ以下の整数、Ｍは参照領域に含まれる点の数）とのＰＰＦをそれぞれ計算する（ステップＳ１２２）。計算した各ＰＰＦを作成済みのハッシュテーブルの中から探索する（ステップＳ１２３）。この場合、対応するモデルポイントペアが１つ以上見つかる。その数をＣｊとする。Ｃｊ個のモデルポイントペアの各々について、局所座標（ｍｒ、α）を計算し、累積テーブルに投票する（ステップＳ１２４）。この投票は、ＭＫｉ内の最後の点ｍＭについて完了するまで繰り返される。
【００５４】
３）投票数がゼロではない全ての局所座標（姿勢の候補）について、全てのモデル点をシーン空間に移動（並進および回転）させる（ステップＳ１２５）。この際、式（２）が用いられる。ＭＫｉ内の全ての点の近傍（距離が閾値未満の位置）に、移動後のモデル点が位置する場合、ｍｉのスコアに１を加算する（ステップＳ１２６、Ｓ１２７）。ｍｉごとにこのスコアが決定される。
【００５５】
４）ｍ１からｍＮｍのうち、最小のスコアの点（群）をキーポイントとして選択する（ステップＳ１２８）。
【００５６】
表１は、図９のフローチャートが示すアルゴリズムの一例を示している。このようなアルゴリズムを用いることにより、信号処理回路１２０は、姿勢の独自性の高い良好なキーポイントを選択することができる。
【００５７】
【表１】
2018189510.tif 000005
【００５８】
なお、本実施形態では、エッジ上の点はキーポイントとして選択されない。常に低いスコアになるが、エッジ上の点における法線は信頼性が低いと考えられるからである。ただし、性能上問題がない場合は、エッジ上の点をキーポイントに含めてもよい。
【００５９】
図１０Ａから図１０Ｆは、本実施形態におけるスコア算出の考え方を説明するための図である。ここでは、簡単のため、モデルの表面形状が立法体である場合を考える。
【００６０】
図１０Ａは、立方体形状のモデルの例を示す図である。この例では、エッジ上の点を除き、各点の法線は、面に垂直である。ｍ０は、スコア算出対象の点である。図中の円は、点ｍ０からの距離が閾値以下である領域ＭＫを表している。本実施形態では、この領域ＭＫが、シーン中に存在すると仮定して、ＰＰＦの計算およびハッシュテーブルの探索が行われる。
【００６１】
図１０Ｂは、点ｍ０と、領域ＭＫ内の他の点ｍ１とから計算されるＰＰＦが、ハッシュテーブルにおけるＰＰＦと照合されることを示す図である。この例では、（ｍ０，ｍ１）のＰＰＦ（Ｆ０）と共通のＰＰＦをもつポイントペア（ｍｐ，ｍｑ）および（ｍｘ，ｍｙ）が検出されている。このようなＰＰＦの照合が、点ｍ０と、領域ＭＫ内の他の全ての点との組み合わせについて行われる。
【００６２】
図１０Ｃは、点ｍ０について検出された同一のＰＰＦをもつポイントペアの組み合わせと、それらの各ポイントペアについて算出された姿勢との対応の例を示す図である。姿勢Ｐ０〜Ｐｎは、上記の局所座標が示す姿勢を表している。姿勢Ｐ０〜Ｐｎのそれぞれについて、モデル点群が仮想的なシーンである領域ＭＫを含む座標系に座標変換される。
【００６３】
図１０Ｄは、モデル中のポイントペア（ｍｐ，ｍｑ）に対応付けられた座標変換パラメータ（局所座標）を用いてモデル全体を座標変換した場合の例を示している。この例では、領域ＭＫに含まれる全ての点の近傍（距離が閾値未満の位置）に、変換後のモデル点群のいずれかの点が存在する。このような場合は、ｍ０のスコアに１を加算する。
【００６４】
図１０Ｅは、モデル中のポイントペア（ｍｘ，ｍｙ）に対応付けられた座標変換パラメータ（局所座標）を用いてモデル全体を座標変換した場合の例を示している。この例では、領域ＭＫに含まれる一部の点については、その近傍（距離が閾値未満の位置）に、変換後のいずれのモデル点も存在しない。このような場合は、ｍ０のスコアは増加しない。
【００６５】
以上のような点数付けが、図１０Ｃに示す全ての姿勢Ｐ０〜Ｐｎについて行われ、ｍ０の最終的なスコアが決定される。同様の処理をモデル点群における全ての点について実行することにより、各点のスコアが決定される。最終的に、ステップＳ１２８において、最小のスコアの点または点群がキーポイントとして選出される。なお、最小のスコアの点に限らず、スコアが低い点から順に所定数の点をキーポイントとして選出してもよい。
【００６６】
図１０Ｆは、角またはエッジにおける参照領域の例を示す図である。角またはエッジである点Ａをキーポイントとして選出する場合、図１０Ｆにおいてハッチングされている領域が参照領域になる。このような点Ａについては、スコアが前述の点ｍ０よりも遥かに小さくなる傾向がある。
【００６７】
［２−３．ハッシュテーブルの再構築］
信号処理回路１２０は、複数のキーポイントを選択した後、ハッシュテーブルを再構築する。すなわち、ハッシュテーブルから、複数のキーポイントに関連しないデータが削除される。本実施形態では、全てのモデル点群間のＰＰＦをハッシュテーブルに保存するDrostのアプローチとは異なり、キーポイント（複数）と、他の各モデル点との間のＰＰＦのみがハッシュテーブルに残る。モデル点群の点の数をＮｍ、キーポイントの数をＮｋとすると、再構築後のハッシュテーブルに保存されるモデルポイントペアの数は、Ｎｋ（Ｎｍ−１）である。DrostのアプローチにおけるＮｍ（Ｎｍ−１）個と比較すると、Ｎｋ／Ｎｍ倍のデータ量で済む。Ｎｋ／Ｎｍは、例えば１／１０００から１／１００程度の低い値に抑えることができる。一例として、Ｎｍ＝３０００、Ｎｋ＝１０の場合、ハッシュテーブルのデータ量は、１／３００にまで減少する。これにより、オンラインフェーズにおける計算時間を短縮することができる。
【００６８】
［２−４．姿勢推定処理］
次に、図５のステップＳ１５０における姿勢推定処理の具体例を説明する。
【００６９】
図１１は、ステップＳ１５０の処理をより詳細に示すフローチャートである。本実施形態では、Drostの投票スキームよりもビンピッキングにより適した投票スキームが用いられる。シーン点群の一部ではなく、全ての点が選択され、周辺の点群との間でＰＰＦが計算される。
【００７０】
各シーン点ｓｉについて、ｓｉからの距離がモデルサイズよりも短い点群をＳｐｈｅｒｅｉとする。モデルサイズとは、モデル点群のうち、最も離れた２点間の距離を意味する。信号処理回路１２０は、点群Ｓｐｈｅｒｅｉのうちの一部をランダムに選択する（ステップＳ１５１）。ランダムに選択する代わりに、所定の規則（例えば１０個おきなど）に従って一部の点を選択してもよい。ここで選択される点群をＳｒとする。選択された点群Ｓｒにおける点の数は、点群Ｓｐｈｅｒｅｉに含まれる点の数のＮｒ倍とする。Ｎｒは、例えば１よりも十分に小さい数（Ｎｒ＜＜１）であり得る。
【００７１】
信号処理回路１２０は、点ｓｉと、Ｓｒに含まれるｊ番目の点Ｓｒｊ（ｊは１以上Ｍｓ以下の整数、ＭｓはＳｒ内の点の数）とのＰＰＦを計算する（ステップＳ１５２）。その後、前述の投票スキームを実行する。信号処理回路１２０は、計算したＰＰＦに近いＰＰＦをもつモデルポイントペアを、再構築したハッシュテーブルの中から探索する（ステップＳ１５３）。Ｃｊ個のモデルポイントペアが見つかったとする。信号処理回路１２０は、Ｃｊ個のモデルポイントペアの各々について、（ｓｉ，Ｓｒｊ）に整合させるための局所座標を決定し、各局所座標の投票数を決定する（ステップＳ１５４）。ステップＳ１５２からＳ１５４の処理を、ｊが１からＭｓになるまで繰り返す。
【００７２】
以上の処理がシーン点群に含まれる全ての点について実行される。全てのシーン点から局所座標を探索することにより、正しい姿勢が除外される可能性が低くなる。このスキームは、シーン内の複数の物体を検出するビンピッキングのような用途に適している。さらに、ハッシュテーブルが従来よりも遥かに小さいため、より多くのシーンポイントペアについてＰＰＦが計算されるにも関わらず、投票スキームに要する計算時間が増大することはない。
【００７３】
局所座標の投票数が多いほど、その局所座標が示す姿勢は多くのポイントペアに整合し、故に正しい姿勢である可能性が高い。したがって、投票数の多いいくつかの局所座標が検証のために選択される。信号処理回路１２０は、投票数が多い順にＮｖ個の局所座標を姿勢の検証のために選択する（ステップＳ１５５）。これらの局所座標は、対象物の姿勢の候補を表す。信号処理回路１２０は、各局所座標が示す姿勢を検証し、姿勢ごとに正確さを示すスコアを算出する（ステップＳ１５６）。そして、スコアが最も高い姿勢を、最終的な姿勢として決定する（ステップＳ１５７）。
【００７４】
なお、本実施形態では、投票の段階で、シーン点群から一部の点群Ｓｒがランダムに選択される。これは、シーン点群中の全ての２点間のＰＰＦを計算すると計算時間が長くなるからである。本実施形態では、絶対投票数ではなくランキングによって局所座標の候補が選択されるため、全ての２点間のＰＰＦを計算する必要はない。各ｓｉについて、Ｎｒが一定であれば、ランキングの結果は大きくは変わらない。誤差はＮｖ（検証される姿勢の数）が大きければ修正される。Ｎｒは、例えば３〜１０％程度の小さい数に抑えることができる。Ｎｖは、例えば８０００〜２００００程度の値である。
【００７５】
表２は、図１１のフローチャートが示すアルゴリズムの一例を示している。このようなアルゴリズムを用いることにより、信号処理回路１２０は、信頼性の高い姿勢を、比較的短時間で決定することができる。
【００７６】
【表２】
2018189510.tif 000006
【００７７】
［２−５．姿勢の検証］
次に、ステップＳ１５６における姿勢の検証処理をより詳細に説明する。
【００７８】
実施形態では、特許文献１および非特許文献１に開示された方法とは異なり、候補の姿勢のクラスタリングは行わない。より多くの候補姿勢の正確性を検証する。
【００７９】
従来の姿勢検証方法では、モデル点群がシーン点群に変換され、全てのモデル点について、最も近いシーン点が探索される。これらの２つの点の間の距離とそれらの法線の間の角度とが比較される。当該距離および角度のそれぞれが閾値よりも小さければ、そのモデル点はシーン点に整合していると考えられる。整合するモデル点の数が十分に多ければ、その姿勢は正しいと考えられる。例えば、Nguyen et al.（"Determination of 3d object pose in point cloud with cad model. 21st Korea-Japan Joint Workshop on Frontiers of Computer Vision, pp. 16, 2015）は、そのような考え方で、モデル点とシーン点とのフィッティングを行う方法を開示している。
【００８０】
この方法は、直感的ではあるが、多くの時間を要する。全ての姿勢の候補について、全てのモデル点に最も近い点を探索する必要があるからである。
【００８１】
本実施形態では、モデル点に最も近い点を見つける必要のない方法が用いられる。具体的には、３次元積分画像（ｉｎｔｅｇｒａｌ  ｉｍａｇｅ）が用いられる。これにより、姿勢検証の効率を大きく改善することができる。
【００８２】
図１２Ａは、２次元の積分画像を説明するための図である。２次元の積分画像においては、点（ｘ，ｙ）における画素値は、元画像における（ｘ，ｙ）の位置から左上に位置する領域における全ての画素値の総和である。すなわち、積分画像の画素値は、以下の式（３）で表される。
【数３】
2018189510.tif 000007
ｉｉ（ｘ，ｙ）は、積分画像の画素値を、ｉ（ｘ，ｙ）は、元画像の画素値を表している。
【００８３】
積分画像の画素値は、次の式（４）によって計算される。
【数４】
2018189510.tif 000008
【００８４】
積分画像を用いることにより、以下の式（５）に示すように、任意の長方形の画素値の和を、４つの配列の参照によって計算できる。
【数５】
2018189510.tif 000009
【００８５】
３次元の積分画像についても、基本的な考え方は２次元と同様である。異なる点は、探索される空間が、長方形から直方体に変わることのみである。
【００８６】
図１２Ｂは、３次元積分画像を説明するための図である。３次元積分画像は、任意の直方体の値の総和を計算するのに用いられる。ここで、直方体の各辺は、座標軸に平行である。式（４）と同様に、３次元積分画像は、以下の式（６）によって計算できる。
【数６】
2018189510.tif 000010
【００８７】
３次元積分画像を構築した後は、任意の直方体の値の総和を、次の式（７）によって計算できる。
【数７】
2018189510.tif 000011
【００８８】
３次元積分画像の考え方を用いることにより、アルゴリズムを高速化することができる。本実施形態では、シーン点群が存在する３次元空間を、３次元画像として取り扱う。１つの画素値は、その画素内のシーン点の数とする。これにより、３次元空間の３次元積分画像を生成する。任意の直方体の内部に含まれるシーン点の数は、式（７）で計算できる。
【００８９】
シーン点群が含まれる座標系に変換された全てのモデル点ｍｉについて、各点ｍｉは、各辺が座標軸に平行な立方体の中心に配置される。点ｍｉのまわりにシーン点があるか否かが判断される。この立方体中の点の数がゼロでない場合、その立方体中のいずれかの点は、ｍｉに対応する可能性がある。
【００９０】
法線間の角度を計算するために、３つの３次元積分マップが生成される。３次元積分マップは、シーン点群の法線のｘ、ｙ、ｚ成分を個別に格納する。同じ立方体中の３つの３次元積分マップの合計Σnx、Σny、Σnzは、その立方体中のシーン点全体の法線と考えることができる。ｍｉの法線と、（Σnx，Σny，Σnz）との角度が閾値よりも小さい場合、このモデル点は対応するシーン点をもち、このモデル点を正確点（correct point）と呼ぶことができる。この正確点の数（正確点数）を、各姿勢のスコアとする。
【００９１】
この方法では、正確点数は、認識性能を評価する上で重要なパラメータである。姿勢が既に与えられているため、全てのモデル点がシーン空間に変換される。もしその姿勢が正確なら、変換後、多くのモデル点がシーン点に整合する。つまり正確点数が多くなる。複数の候補の姿勢について、正確点数を比較することで、どの姿勢が最も正確かを容易に判別することができる。
【００９２】
３次元積分画像を用いることの利点は、計算の効率化が可能な点にある。本発明者らの実験によれば、例えば２秒間に１００００回以上の姿勢の検証が可能である。
【００９３】
本実施形態における姿勢検証法は、非常に高速であるため、Drostに開示された方法とは異なり、姿勢のクラスタリングは不要である。さらに、検証の正確性も向上する。類似する姿勢をクラスタリングして平均値をとるのではなく、最も高い正確点数をもつ姿勢を採用することにより、多くの場合、従来よりも正確に姿勢を推定することができる。
【００９４】
［２−６．複数物体の検出］
本実施形態におけるアルゴリズムの他の利点は、シーン中に複数の物体を見つけることが容易であることである。本実施形態では、多数の姿勢が検証される。これらの検証結果は、シーン中の複数の物体の姿勢を検証する際にも利用することができる。例えば、以下の方法を用いることができる。
１）全ての姿勢をスコアに従ってランク付けする。
２）最初に選択された姿勢をＰ１とする。Ｐ１に属する点群をシーン点群から削除する。
３）積分画像空間をリフレッシュする。
４）新たな積分画像空間において、ステップ１）においてランク付けされた姿勢群を検証する。
５）最高スコアの姿勢Ｐ２を新たに選ぶ。Ｐ２に属する点群をシーン点群から削除する。
６）  ３）に戻る。
【００９５】
［３．効果］
以上のように、本実施形態によれば、信頼性の高い厳選された点（キーポイント）のみを用いたハッシュテーブルが作成される。これにより、対象物の姿勢推定処理を高速化することができる。さらに、モデル点群の各点ｍｉの周囲の点群についてＰＰＦを計算し、座標計算によって座標変換パラメータ（局所座標）の投票を重ねる。投票数の多い姿勢から、前述の検証処理によって最善の姿勢が決定される。これにより、高速かつ信頼性の高い認識が可能となる。
【００９６】
本発明者らは、多数の合成シーンおよび現実のシーンについて実験を行い、本実施形態の効果を検証した。各入力シーンおよびモデルについて、点群は、ダウンサンプルされ、モデル点数は約３０００である。キーポイント数Ｎｋは、８から２０とし、Ｎｖ＝８０００〜２００００の姿勢を検証した。Ｎｒは３％から１０％とした。
【００９７】
工業部品および非工業部品を含む１６個のモデルを用いた。図１３は、それらのモデルを示している。図１３において、（ａ）〜（ｆ）は、Hinterstoisser et al. ("Model based training, detection and pose estimation of texture-less 3d objects in heavily cluttered scenes", Asian conference on computer vision, pp. 548-562, 2012)のデータセットから利用した。（ｇ）〜（ｊ）は、Mian et al. （"Three-dimensional modelbased object recognition and segmentation in cluttered scenes", IEEE Transactions on Pattern Analysis & Machine Intelligence, Vol. 28(10): pp. 1584-1601, 2006、および" On the repeatability and quality of keypoints for local feature-based 3d object retrieval from cluttered scenes. Int. Journal of Computer Vision, Vol. 89(2): pp. 348-361, 2010)のデータセットから利用した。（ｋ）〜（ｐ）は工業用部品である。
【００９８】
各実験において、誤差が閾値よりも小さい場合に結果が正しいと判定した。閾値は、変位についてはモデル中で最も離れた２点間の距離の１／２０とし、回転については１２度とした。
【００９９】
図１４Ａおよび図１４Ｂは、合成シーンについてのシミュレーション結果を示すグラフである。図１４Ａは、モデルごとに、正しく認識された率（認識率）を示している。図１４Ｂは、モデルごとの計算時間を示している。比較のため、Drostに開示された方法を使用した場合についても同じ条件で計算した。合成シーンについては、各シーンについて、複数の同じ物体を含むように生成した。各シーンにおける物体の数は、５個から１５個であり、４個の物体を検出した。
【０１００】
図１４Ａおよび図１４Ｂからわかるように、非工業部品については、本実施形態の方法でもDrostの方法でも良好な認識率および認識スピードが達成できた。しかし、工業部品については、認識率および認識スピードともに、本実施形態の方法の方が、Drostの方法よりも良好な結果が得られた。
【０１０１】
図１５は、工業部品についての認識結果の一例を示す画像である。（ａ）はDrostの方法を用いた場合の結果を示し、（ｂ）は本実施形態の方法を用いた場合の結果を示している。図中において、ハッチングされている箇所が、認識された箇所を示す。本実施形態の方法の方が、工業部品をより正確に認識できていることがわかる。
【０１０２】
図１６は、現実のシーンについて行った実験の結果を示すグラフである。図１６は、オクルージョンの割合を変化させたときの認識率の変化の例を示している。オクルージョンの割合は、シーン中のモデルの表面積の合計をモデルの全表面積で割った値を１から減じた値である。図１６Ａに示すように、本実施形態のアルゴリズムによれば、Drostのアルゴリズムと比較して、特にオクルージョンの割合が高い場合の認識率の低下を抑えることができる。
【０１０３】
なお、上記の［２−３．キーポイントの選択］、［２−４．姿勢推定処理］、［２−５．姿勢の検証］、［２−６．複数物体の検出］において説明した処理は、あくまでも例示にすぎず、各処理について様々な改変が可能である。例えば、図９に示すキーポイントの選択の処理におけるスコアの算出の方法を適宜変形してもよい。また、図１１から図１２Ｂを参照して説明した物体の姿勢の推定方法に代えて、例えばDrostに開示された方法を適用してもよい。Drost等の公知の方法を適用した場合であっても、本発明の実施形態におけるキーポイントに関するＰＰＦの情報のみを含むハッシュテーブルが用いられていれば、演算時間の短縮の効果が得られる。
【０１０４】
以上のように、本開示は、以下の項目に記載の方法、プログラム、および装置を含む。
【０１０５】
［項目１］
３次元シーンにおける対象物の位置および姿勢を推定する方法であって、
前記対象物の表面の３次元形状を表すモデル点群のデータを取得するステップと、
前記モデル点群から選択されたポイントペアの幾何学的関係を規定するポイントペア特徴量（Ｐｏｉｎｔ  Ｐａｉｒ  Ｆｅａｔｕｒｅ）を、各ポイントペアについて計算し、前記ポイントペア特徴量と前記ポイントペアとを関連付けて第１のテーブルに記録するステップと、
前記モデル点群のデータおよび前記第１のテーブルに基づいて、前記モデル点群から、複数のキーポイントを選択するステップと、
前記第１のテーブルに記録されたデータのうち、前記複数のキーポイントに関するデータのみを残した第２のテーブルを構築するステップと、
前記３次元シーンに含まれる１以上の物体の表面形状を表すシーン点群のデータを取得するステップと、
前記シーン点群のデータ、および前記第２のテーブルに基づいて、前記３次元シーン中の前記対象物の位置および姿勢を推定するステップと、
を含む方法。
【０１０６】
［項目２］
前記複数のキーポイントを選択するステップは、
前記モデル点群における点ｍｉ（ｉは１以上Ｎｍ以下の整数、Ｎｍは前記モデル点群に含まれる点の数）と、点ｍｉからの距離が閾値よりも短い参照領域に含まれる点ｍｊ（ｊは１以上Ｍ以下の整数、Ｍは前記参照領域に含まれる点の数）とのポイントペア特徴量をそれぞれ計算するステップと、
前記第１のテーブルを参照して、計算した前記ポイントペア特徴量に類似するポイントペア特徴量をもつ少なくとも１つのポイントペアを探索するステップと、
探索した前記ポイントペアの各々について、点ｍｉおよび点ｍｊの対に整合させるための座標変換パラメータを決定するステップと、
点ｍｉのうち、決定した前記座標変換パラメータの各々を用いて前記モデル点群の座標を変換したとき、前記参照領域に含まれる全ての点の近傍に、変換後のモデル点群のいずれかの点が位置する場合の数が最小になる点ｍｉを、キーポイントとして選択するステップと、
を含む、項目１に記載の方法。
【０１０７】
［項目３］
前記複数のキーポイントの個数は、前記モデル点群の点の個数の１／１００００倍以上１／２倍以下である、請求項１または２に記載の方法。
【０１０８】
［項目４］
前記複数のキーポイントの個数は、前記モデル点群の点の個数の１／１０００倍以上１／１００倍以下である、項目１から３のいずれかに記載の方法。
【０１０９】
［項目５］
前記対象物の位置および姿勢を推定するステップは、
前記シーン点群における各点ｓｉ（ｉは１以上Ｎｓ以下の整数、Ｎｓは前記シーン点群に含まれる点の数）からの距離が、前記モデル点群に含まれる最も離れた２点間の距離以下である点の集合から、一部の点群Ｓｒを選択するステップと、
点ｓｉと、点群Ｓｒ内の各点Ｓｒｊ（ｊは１以上Ｍｓ以下の整数）とのポイントペア特徴量を計算するステップと、
前記第２のテーブルを参照して、計算した前記ポイントペア特徴量に類似するポイントペア特徴量をもつ少なくとも１つのポイントペアを探索するステップと、
探索した前記ポイントペアの各々について、点ｓｉおよび点Ｓｒｊの対に整合させるための座標変換パラメータを決定し、前記座標変換パラメータが示す姿勢ごとにカウント数を決定するステップと、
前記カウント数を決定した姿勢の中から、前記カウント数が多い順に複数の候補姿勢を選択するステップと、
前記複数の候補姿勢の中から、前記モデル点群と前記シーン点群との整合度が最も高くなる姿勢を、最終的な姿勢として決定するステップと、
を含む、項目１から４のいずれかに記載の方法。
【０１１０】
［項目６］
項目１から５に記載の方法をコンピュータに実行させるコンピュータプログラム。
【０１１１】
［項目７］
項目６に記載のコンピュータプログラムを格納したメモリと、
前記コンピュータプログラムを実行するプロセッサと、
を備える処理装置。
【０１１２】
［項目８］
項目７に記載の処理装置と、
エンドエフェクタと、
前記処理装置によって推定された前記対象物の位置および姿勢の情報に基づいて、前記エンドエフェクタを制御する制御回路と、
を備えるロボット。
【０１１３】
［項目９］
項目７に記載の処理装置と、
ロボットと、
前記シーン点群データを取得する３次元センサと、
前記処理装置によって推定された前記対象物の位置および姿勢の情報に基づいて、前記ロボットを制御する制御回路と、
を備えるロボットシステム。
【産業上の利用可能性】
【０１１４】
本開示の実施形態における３次元物体の姿勢推定方法は、例えば、ビンピッキングを実行するロボットのための画像認識の分野で利用可能である。
【符号の説明】
【０１１５】
１００  制御装置
１１０  制御回路
１２０  画像処理回路
１３０  メモリ
１４０  入力インタフェース
１５０  出力インタフェース
２００  ロボット
３００  ３次元センサ
４００  ディスプレイ
８００  ばら積みされた物体
【図１】
2018189510.tif 000012
【図２】
2018189510.tif 000013
【図３】
2018189510.tif 000014
【図４】
2018189510.tif 000015
【図５】
2018189510.tif 000016
【図６】
2018189510.tif 000017
【図７】
2018189510.tif 000018
【図８】
2018189510.tif 000019
【図９】
2018189510.tif 000020
【図１０Ａ】
2018189510.tif 000021
【図１０Ｂ】
2018189510.tif 000022
【図１０Ｃ】
2018189510.tif 000023
【図１０Ｄ】
2018189510.tif 000024
【図１０Ｅ】
2018189510.tif 000025
【図１０Ｆ】
2018189510.tif 000026
【図１１】
2018189510.tif 000027
【図１２Ａ】
2018189510.tif 000028
【図１２Ｂ】
2018189510.tif 000029
【図１３】
2018189510.tif 000030
【図１４Ａ】
2018189510.tif 000031
【図１４Ｂ】
2018189510.tif 000032
【図１５】
2018189510.tif 000033
【図１６】
2018189510.tif 000034