JP2012118732A - ３次元形状認識装置及び方法 - Google Patents

Abstract

【課題】画像処理の処理効率の向上と共に相対的位置角度スケールを確実に検出できる３次元形状認識装置を実現することが求められる。
【解決手段】本実施形態によれば、３次元形状認識装置は、入力部と、幾何学的要素抽出部と、幾何学的要素対応付け処理部と、位置角度推定処理部とを備えた構成である。入力部は、同一の３次元形状の認識対象に対する複数の形状データを入力する。幾何学的要素抽出部は、前記各形状データのそれぞれから幾何学的要素を抽出する。幾何学的要素対応付け処理部は、角度または距離の比を含む相似不変量をキーとするハッシュテーブルを使用し、前記各幾何学的要素間で位置関係が合致する組み合わせを選出する。位置角度推定処理部は、前記選出される複数の組み合わせに基づいて前記各形状データ間で前記認識対象の相対的位置角度スケールを示す相対的位置角度情報を算出する。
【選択図】図１

Description

本発明の実施形態は、３次元形状認識装置の位置角度検出技術に関する。

一般的に、例えば物体の３次元形状を認識する３次元形状認識装置は、レンジファインダなどを使用して撮像（計測）した対象の距離画像データから、形状データ（メッシュデータ）を入力し、この形状データを使用して物体などの３次元形状を認識するための画像処理を実行する。

従来の画像処理手法の一例としては、２個の距離画像または部分形状データから、それぞれのデータ中の物体の相対的な位置角度または位置角度スケールを求めるために、それぞれのデータから位置情報を有する幾何学的要素（特徴点、部分セグメントなど）を検出する。さらに、一部（例えば３点以上）の幾何学的要素を抽出し、２個のデータ間でこれが合致するかを検証し、合致する場合にこれらの位置を一致させるような位置角度変換または位置角度スケール変換（相似変換）を算出する方法がある。この方法では、幾何学的要素の一部を抽出する組み合わせの全てに対して処理を実行し、投票処理またはその他の近いものをまとめる処理により、頻度の高い相対位置角度または相対位置角度スケールを抽出してこれを解とする。

また、ランダムサンプリング方法（RANSAC）を利用して、ランダムに選出した一部（３点以上）の幾何学的要素を使って相対位置角度または相対位置角度スケールを算出する方法がある。この方法は、残りのデータ（特徴点、直線、距離情報、形状情報など）を使用して、算出された相対位置角度または相対位置角度スケールが正しいか否かを検証する。

特許第３００２８９６号公報 特許第３９１４８６４号公報

前述のように従来の３次元（物体）形状認識装置では、距離画像または部分形状データから幾何学的要素を抽出し、この幾何学的要素を使用して相対的な位置角度を算出する方法が提案されている。前者の方法は、幾何学的要素の集合全体から、３個又はそれ以上を抽出する組み合わせの全てに対して合致するか否かの判定処理および位置角度変換または相似変換を算出する処理を行う。このため、判定処理、変換算出処理は幾何学的要素数に対して指数関数的に増加し、多大な処理時間を要する。また、後者の方法は、全体に対して合致する要素の割合が多い場合には有効だが、少ない場合には正しい組み合わせが選出される可能性は低くなる。この結果として、距離画像や部分形状データが広範囲を撮像したものである場合、対象物体の占める割合が小さい場合、撮影角度が異なるために合致する要素の割合が少ない場合などに、正しい結果を得られない。

そこで、画像処理の処理量（処理時間）を削減して処理効率の向上を図り、かつ相対位置角度または相対位置角度スケールを確実に検出できる信頼性の高い３次元形状認識装置を実現することが求められる。

本実施形態によれば、３次元形状認識装置は、入力手段と、幾何学的要素抽出手段と、幾何学的要素対応付け手段と、位置角度スケール推定手段とを備えた構成である。入力手段は、同一の３次元形状の認識対象に対する複数の形状データを入力する。幾何学的要素抽出手段は、前記各形状データのそれぞれから幾何学的要素を抽出する。幾何学的要素対応付け手段は、角度または距離の比を含む相似不変量をキーとするハッシュテーブルを使用し、前記各幾何学的要素間で位置関係が合致する組み合わせを選出する。位置角度スケール推定手段は、前記選出される複数の組み合わせに基づいて前記各形状データ間で前記認識対象の相対位置角度スケールを示す相対的位置角度スケール情報を算出する。

実施形態に関する３次元形状認識装置の構成を説明するためのブロック図。 実施形態に関する実施形態に関する距離画像の一例を示す図。 実施形態に関する実施形態に関する距離画像を説明するための模式図。 実施形態に関する実施形態に関する形状データの一例を示す図。 実施形態に関するデータ処理装置の動作を説明するためのフローチャート。 実施形態に関するデータ処理装置の動作を説明するためのフローチャート。 実施形態に関する幾何学的要素の具体例を説明するための図。 実施形態に関する幾何学的要素の具体例を説明するための図。 実施形態に関する幾何学的要素の具体例を説明するための図。 実施形態に関する幾何学的要素の具体例を説明するための図。 実施形態に関するハッシュテーブルを使用した対応探索処理を説明するための図。 実施形態の第１の変形例に関する推定処理の手順を説明するためのフローチャート。 実施形態の第２の変形例に関する推定処理の手順を説明するためのフローチャート。 第２の変形例に関する幾何学的要素間の特徴量を説明するための図。 実施形態の第３の変形例に関する推定処理の手順を説明するためのフローチャート。 実施形態の第４の変形例に関する推定処理の手順を説明するためのフローチャート。 第４の変形例に関する推定処理の概念を説明するための図。 第４の変形例に関する推定処理の概念を説明するための図。 実施形態の第５の変形例に関する推定処理の手順を説明するためのフローチャート。 実施形態の適用例であるパターンマッチング装置の構成を説明するためのブロック図。 実施形態の適用例である物体認識装置の構成を説明するためのブロック図。

以下図面を参照して、実施形態を説明する。

［物体形状認識装置の構成］
図１は、実施形態に関する３次元形状認識装置の構成を説明するためのブロック図である。

図１に示すように、３次元形状認識装置は、画像入力装置１０と、入力インターフェース１１と、表示出力装置１２と、データ処理装置（画像処理部）１３とを有する。画像入力装置１０は、例えばレンジファインダまたはステレオカメラを有し、認識対象の距離画像データを取得する計測器である。距離画像データとは、３次元的に計測された認識対象の特定形状を検出できる画像データであり、後述する形状データを作成するために使用される。画像入力装置１０は、認識対象の位置及び角度を変えて撮像（計測）して得られる複数の距離画像データを入力できる。

ここで、本実施形態は、認識対象として例えば部品や装置などの物体を想定する。但し、認識対象としては、例えば文字パターンなどが３次元形状で構成された立体パターンのようなものも含まれる。以下、認識対象を物体と表記する場合がある。

入力インターフェース１１は、画像入力装置１０により取得された距離画像データをデータ処理装置１３に転送する。データ処理装置１３は、入出力インターフェース１４と、幾何学的要素抽出部１５と、幾何学的要素対応付け処理部１６と、相対位置角度推定処理部１７とを有し、物体の形状を認識するための画像処理を実行する。

入出力インターフェース１４は、入力インターフェース１１から転送された距離画像データを入力し、またデータ処理装置１３の処理結果（相対的位置角度推定結果や物体認識結果など）を表示出力装置１２に出力する。表示出力装置１２は、画面上にデータ処理装置１３の処理結果を表示する。

［データ処理装置の動作］
以下、図５Ａのフローチャートを参照して、本実施形態のデータ処理装置１３の動作として、物体の認識処理に必要な相対的位置角度の推定処理（算出処理）の手順を説明する。

まず、データ処理装置１３は、入出力インターフェース１４を介して、図２に示すような距離画像データ２０１を入力する。距離画像データ２０１は、画像入力装置１０により取得される認識対象である物体の距離画像である。さらに、データ処理装置１３は、入力される１枚の距離画像データ２０１に基づいて、図４に示すように、認識対象である物体の見えている部分の形状データ２０４を作成する。

形状データ２０４は、物体の表面形状上の点の座標を表す頂点と、その隣接関係を表す辺で構成されるメッシュデータである。即ち、図３に示すように、各頂点座標は、距離画像データの画素２０２の位置と、距離を表す画素値から算出される。また、辺は、画素２０２間の隣接情報２０３から取得される。但し、隣接する画素であっても、距離の差が大きい場合は、連続した表面形状ではないため、それらの画素の間の辺は作成しない。

図５に示すように、データ処理装置１３は、入力される距離画像データから２枚の形状データＤ１，Ｄ２を取得する（ステップ３０１Ａ，３０１Ｂ）。幾何学的要素抽出部１５は、各形状データＤ１，Ｄ２のそれぞれから幾何学的要素を抽出する（ステップ３０２Ａ，３０２Ｂ，３１０）。

図６から図９は、本実施形態の幾何学的要素の具体例を示す図である。即ち、図６に示すように、幾何学的要素とは、例えば形状データ４０１の突出点、凹状点、鞍部上の点などを表す特徴点４０２であり、空間中の位置情報を有する代表点４０３で表すことができる性質のものである。また、図７に示すように、幾何学的要素とは、例えば形状データ５０１上の直線５０２や稜線５０３であり、空間中の位置情報を有する代表点５０４で表すことができる性質のものである。

さらに、図８に示すように、幾何学的要素とは、例えば形状データ６０１の領域分割結果６０２から得られる部分領域６０３であり、空間中の位置情報を有する代表点６０４で表すことができる性質のものである。また、図９に示すように、幾何学的要素とは、例えば形状データ７０１の一部を抽出した結果の部分領域７０２や、形状データ７０１の一部を近似する円筒などのプリミティブ形状７０３であり、空間中の位置情報を有する代表点７０４で表すことができる性質のものである。

これらに加えて、幾何学的要素としては、データ空間中の方向、幾何学的要素の性質やその代表点の周辺形状の性質を表す特徴量、２個の幾何学的要素の類似度やその間の関係を示す幾何学的要素間の特徴量などが定義できることが望ましい。

次に、幾何学的要素対応付け処理部１６は、形状データＤ１の幾何学的要素３点以上の組を格納するハッシュテーブル（hash table）を作成する（ステップ３０３）。ハッシュテーブルは、幾何学的要素３点以上の位置から算出される相似不変量をキーとする。相似不変量とは、角度、距離の比、面積の比であり、相似変換に関して不変な量である。たとえば幾何学的要素３点の組を扱う場合は、３点間の２個の線分の長さの比率（距離の比）、その２個の線分のなす角度をキーとする。幾何学的要素４点の組を扱う場合には、これに加えて面積の比もキーとすることができる。以下、幾何学的要素３点の組を扱い、３点間の２個の線分の長さの比率（距離の比）、その２個の線分のなす角度をキーとするハッシュテーブルを使う場合を説明する。

幾何学的要素対応付け処理部１６は、形状データＤ２から幾何学的要素３個を選び、ハッシュテーブルを検索して不変量の合致する形状データＤ１の幾何学的要素３個とを対応付ける（ステップ３０４、３１１）。

図１０は、幾何学的要素対応付け処理部１６によるハッシュテーブルを使用した対応探索処理の概念を説明するための図である。

図１０（Ａ）に示すように、形状データＤ１(８０１)から３点の幾何学的要素８０３を取り出し、不変量である２点間の線分８０４、２個の長さ８０５の比率（ａ／ｂ）となす角度８０６（θ）をキーとする。幾何学的要素対応付け処理部１６は、当該キーとして、図１０（Ｂ）に示すように、ハッシュテーブル８０７に格納する。幾何学的要素対応付け処理部１６は、形状データＤ１(８０１)の全ての３点の組をハッシュテーブル８０７に格納した後、図１０（Ｃ）に示すように、形状データＤ２(８０２)から幾何学的要素３点を取り出す。幾何学的要素対応付け処理部１６は、形状データＤ２(８０２)に関する同様の不変量を算出し、ハッシュテーブル８０７のこれに合致する位置を検索し、形状データＤ１の３点と対応付けを行なう。

次に、相対位置角度推定処理部１７は、ハッシュテーブル８０７の検索により、相対的な位置角度情報を算出（推定）する一連の処理（３１２）を実行する。即ち、相対位置角度推定処理部１７は、対応付けられた３組の幾何学的要素の位置情報（代表点の位置情報）に基づいて、位置角度情報を算出する（ステップ３０５）。換言すれば、相対位置角度推定処理部１７は、形状データＤ１，Ｄ２により位置・角度合わせ処理を実行する。相対位置角度推定処理部１７は、このときの位置角度パラメータを位置角度パラメータ空間に投票する（ステップ３０６）。

相対位置角度推定処理部１７は、形状データＤ２の全ての３点の組み合わせについて処理が完了するまで、ステップ３０４〜３０６の処理を繰り返す（ステップ３０７）。相対位置角度推定処理部１７は、ステップ３０４〜３０６の処理が完了すると、位置角度パラメータ空間から投票数が極大である位置を検出する（ステップ３０８）。相対位置角度推定処理部１７は、投票数が極大となる位置に対応するパラメータで定義される位置角度変換の結果を示す相対的位置角度情報を算出する（ステップ３０９）。

以上のように本実施形態のデータ処理装置１３は、位置角度パラメータで定義される相対的位置角度情報を算出（推定）する。

［相対的位置角度スケールの推定処理］
以下、図５Ｂのフローチャートを参照して、本実施形態のデータ処理装置１３の動作として、物体の認識処理に必要な相対的位置角度スケールの推定処理（算出処理）の手順を説明する。便宜的に、各ステップの符号は図５Ａと同一である。

まず、データ処理装置１３は、入力される距離画像データから２枚の形状データＤ１，Ｄ２を取得する（ステップ３０１Ａ，３０１Ｂ）。幾何学的要素抽出部１５は、各形状データＤ１，Ｄ２のそれぞれから幾何学的要素を抽出する（ステップ３０２Ａ，３０２Ｂ，３１０）。

次に、幾何学的要素対応付け処理部１６は、形状データＤ１の幾何学的要素３点以上の組を格納するハッシュテーブル（hash table）を作成する（ステップ３０３）。ハッシュテーブルは、幾何学的要素３点以上の位置から算出される相似不変量をキーとする。以下、幾何学的要素３点の組を扱い、３点間の２個の線分の長さの比率（距離の比）、その２個の線分のなす角度をキーとするハッシュテーブルを使う場合を説明する。

幾何学的要素対応付け処理部１６は、形状データＤ２から幾何学的要素３個を選び、ハッシュテーブルを検索して不変量の合致する形状データＤ１の幾何学的要素３個とを対応付ける（ステップ３０４、３１１）。

図１０（Ａ）に示すように、形状データＤ１(８０１)から３点の幾何学的要素８０３を取り出し、不変量である２点間の線分８０４、２個の長さ８０５の比率（ａ／ｂ）となす角度８０６（θ）をキーとする。幾何学的要素対応付け処理部１６は、当該キーとして、図１０（Ｂ）に示すように、ハッシュテーブル８０７に格納する。幾何学的要素対応付け処理部１６は、形状データＤ１(８０１)の全ての３点の組をハッシュテーブル８０７に格納した後、図１０（Ｃ）に示すように、形状データＤ２(８０２)から幾何学的要素３点を取り出す。幾何学的要素対応付け処理部１６は、形状データＤ２(８０２)に関する同様の不変量を算出し、ハッシュテーブル８０７のこれに合致する位置を検索し、形状データＤ１の３点と対応付けを行なう。

次に、相対位置角度推定処理部１７は、ハッシュテーブル８０７の検索により、相対的な位置角度スケール情報を算出（推定）する一連の処理（３１２）を実行する。即ち、相対位置角度推定処理部１７は、対応付けられた３組の幾何学的要素の位置情報（代表点の位置情報）に基づいて、位置角度スケール情報を算出する（ステップ３０５）。換言すれば、相対位置角度推定処理部１７は、形状データＤ１，Ｄ２により位置・角度・スケール合わせ処理を実行する。相対位置角度推定処理部１７は、このときの位置角度スケールパラメータを位置角度スケールパラメータ空間に投票する（ステップ３０６）。

相対位置角度推定処理部１７は、形状データＤ２の全ての３点の組み合わせについて処理が完了するまで、ステップ３０４〜３０６の処理を繰り返す（ステップ３０７）。相対位置角度推定処理部１７は、ステップ３０４〜３０６の処理が完了すると、位置角度スケールパラメータ空間から投票数が極大である位置を検出する（ステップ３０８）。相対位置角度推定処理部１７は、投票数が極大となる位置に対応するパラメータで定義される位置角度スケール変換の結果を示す相対的位置角度スケール情報を算出する（ステップ３０９）。

以上のように本実施形態のデータ処理装置１３は、位置角度スケールパラメータで定義される相対的位置角度スケール情報を算出（推定）する。

本実施形態の推定処理方法であれば、形状データＤ１，Ｄ２から幾何学的要素を抽出し、その一部のみ（代表点）を使用して相対的位置角度情報または相対位置角度スケール情報を算出することができる。従って、形状データ全体や、抽出した幾何学的要素の全て使用する方法と比較して、推定処理量の削減を図ることができる。この場合、幾何学的要素として１点で代表する代表点であれば、点、線分、領域などの異なる性質の要素を混合して扱うことができるため、形状データに応じて信頼性の高い幾何学的要素を選択的に利用することができる。また、幾何学的要素対応付け処理部１６による対応付け処理において、相似不変量をキーとするハッシュテーブルを利用するため、位置、角度、スケール（領域の広さ）に関する不変性を残しつつ、高速な処理を実現することが可能となる。

（第１の変形例）
図１１は、図５Ａ，５Ｂのフローチャートで説明した本実施形態の基本的処理に対して、幾何学的要素の特徴量の類似度によるリジェクト処理を含む相対的位置角度の推定処理（算出処理）を説明するためのフローチャートである。

まず、基本的処理と同様に、データ処理装置１３は、入力される距離画像データから２枚の形状データＤ１，Ｄ２を取得する（ステップ９０１Ａ，９０１Ｂ）。幾何学的要素抽出部１５は、各形状データＤ１，Ｄ２のそれぞれから幾何学的要素を抽出する（ステップ９０２Ａ，９０２Ｂ）。幾何学的要素抽出部１５は、幾何学的要素の抽出処理後に、幾何学的要素の性質やその代表点の周辺形状の性質を表す特徴量を算出する（ステップ９０３Ａ，９０３Ｂ）。ここで、幾何学的要素の性質や周辺形状の性質とは、代表点の周辺の頂点の分布、代表点とその周辺の頂点との法線ベクトルのなす角の分布、曲率値、輝度値、曲率値や輝度値の勾配方向、曲率値や輝度値の勾配の大きさ、などである。

次に、幾何学的要素対応付け処理部１６は、形状データとＤ１の幾何学的要素３点の組を格納するハッシュテーブル（hash table）を作成する（ステップ９０４）。幾何学的要素対応付け処理部１６は、ハッシュテーブルを検索して２個の形状データＤ１，Ｄ２の幾何学的要素３組とを対応付ける（ステップ９０５）。このとき、幾何学的要素対応付け処理部１６は、対応する幾何学的要素の特徴量の類似度を算出し、これを予め設定された閾値と比較する（ステップ９０６）。

相対位置角度推定処理部１７は、特徴量の類似度が閾値以上の場合にのみ、相対的な位置角度情報を算出（推定）する一連の処理を実行する（ステップ９０６のＹＥＳ）。即ち、相対位置角度推定処理部１７は、対応付けられた３組の幾何学的要素の位置情報（代表点の位置情報）に基づいて、位置角度情報を算出する（ステップ９０７）。相対位置角度推定処理部１７は、このときの位置角度パラメータを位置角度パラメータ空間に投票する（ステップ９０８）。

以下同様にして、相対位置角度推定処理部１７は、形状データＤ２の全ての３点の組み合わせについて処理が完了するまで、ステップ９０５〜９０８の処理を繰り返す（ステップ９０９）。相対位置角度推定処理部１７は、一連の処理が完了すると、位置角度パラメータ空間から投票数が極大である位置を検出する（ステップ９１０）。相対位置角度推定処理部１７は、投票数が極大となる位置に対応するパラメータで定義される位置角度変換の結果を示す相対的位置角度情報を算出する（ステップ９１１）。

（第２の変形例）
図１２は、図１１のフローチャートで説明した第１の変形例の処理に対して、幾何学的要素間の特徴量の類似度によるリジェクト処理を含む相対的位置角度の推定処理（算出処理）を説明するためのフローチャートである。

まず、第１の変形例の処理と同様に、データ処理装置１３は、入力される距離画像データから２枚の形状データＤ１，Ｄ２を取得する（ステップ１００１Ａ，１００１Ｂ）。幾何学的要素抽出部１５は、各形状データＤ１，Ｄ２のそれぞれから幾何学的要素を抽出する（ステップ１００２Ａ，１００２Ｂ）。幾何学的要素抽出部１５は、幾何学的要素の抽出処理後に、２個の幾何学的要素間の方向の違いや性質の違いを表す特徴量を算出する（ステップ１００３Ａ，１００３Ｂ）。ここで、幾何学的要素間の特徴量とは、後述するように、法線ベクトルのなす角、曲率値など形状上の特徴を表す指標の勾配方向の２要素間の相違や、形状データ毎に光源強度が異なる環境で撮影した場合の同一形状データ内の２要素間の輝度差などである。

次に、幾何学的要素対応付け処理部１６は、形状データＤ１の幾何学的要素３点の組を格納するハッシュテーブル（hash table）を作成する（ステップ１００４）。幾何学的要素対応付け処理部１６は、ハッシュテーブルを検索して２個の形状データＤ１，Ｄ２の幾何学的要素３組とを対応付ける（ステップ１００５）。このとき、幾何学的要素対応付け処理部１６は、一方の形状データＤ１内の幾何学的要素２個の幾何学的要素間特徴量と、もう一方の形状データＤ２内のこれと対応する幾何学的要素２個の幾何学的要素間特徴量との類似度を算出し、これを予め設定された閾値と比較する（ステップ１００６）。

相対位置角度推定処理部１７は、特徴量の類似度が閾値以上の場合にのみ、相対的な位置角度情報を算出（推定）する一連の処理を実行する（ステップ１００６のＹＥＳ）。即ち、相対位置角度推定処理部１７は、対応付けられた３組の幾何学的要素の位置情報（代表点の位置情報）に基づいて、位置角度情報を算出する（ステップ１００７）。相対位置角度推定処理部１７は、このときの位置角度パラメータを位置角度パラメータ空間に投票する（ステップ１００８）。

以下同様にして、相対位置角度推定処理部１７は、形状データＤ２の全ての３点の組み合わせについて処理が完了するまで、ステップ１００５〜１００８の処理を繰り返す（ステップ１００９）。相対位置角度推定処理部１７は、一連の処理が完了すると、位置角度パラメータ空間から投票数が極大である位置を検出する（ステップ１０１０）。相対位置角度推定処理部１７は、投票数が極大となる位置に対応するパラメータで定義される位置角度変換の結果を示す相対的位置角度情報を算出する（ステップ１０１１）。

図１３は、幾何学的要素を表面形状上の特徴点とし、幾何学的要素間の特徴量を特徴点の法線方向のなす角とする場合について具体例を示す図である。

図１３（Ａ）は、形状データＤ１の特徴点と法線ベクトル１１０１を示す図である。また、図１３（Ｂ）は、形状データＤ２の特徴点と法線ベクトル１１０２を示す図である。図１３（Ａ）に示すように、幾何学的要素対応付け処理部１６は、形状データＤ１の特徴点３点(１１０３，１１０４，１１０５)とその位置の法線ベクトル(１１０９，１１１１，１１１２)から、１点の法線ベクトル(１１０９)と他の２点の法線ベクトル(１１１１，１１１２)とのなす角(１１１３，１１１４)を算出する。

同様に、図１３（Ｂ）に示すように、幾何学的要素対応付け処理部１６は、形状データＤ２の特徴点３点(１１０６，１１０７，１１０８)とその位置の法線ベクトル(１１１５，１１１７，１１１８)から、１点の法線ベクトル(１１１５)と他の２点の法線ベクトル(１１１７，１１１８)とのなす角(１１１９，１１２０)を算出する。これに基づいて、幾何学的要素対応付け処理部１６は、形状データＤ１の法線ベクトルのなす角(１１１３，１１１４)とこれに対応する形状データＤ２の法線方向のなす角(１１１９，１１２０)との差が閾値以下の場合は、３点が対応付かないとしてリジェクトする（ステップ１００６のＮＯ）。

なお、幾何学的要素間の特徴量としては、法線ベクトルのなす角の他に、曲率値など形状上の特徴を表す指標の勾配方向の２要素間の相違や、形状データ毎に光源強度が異なる環境で撮影した場合の同一形状データ内の２要素間の輝度差などがある。これは、対応する、つまり同じ位置を表す幾何学的要素の特徴量が異なる形状データ間では異なる値をとり得るものの、同一形状データ内の２要素間の関係を表す特徴量は、異なる形状データ間でも同じ値をとるような性質を有することである。

（第３の変形例）
図１４は、図５のフローチャートで説明した基本的処理に対して、正解候補選出処理を含む相対的位置角度の推定処理（算出処理）を説明するためのフローチャートである。

まず、基本的処理と同様に、データ処理装置１３は、入力される距離画像データから２枚の形状データＤ１，Ｄ２を取得する（ステップ１２０１Ａ，１２０１Ｂ）。幾何学的要素抽出部１５は、各形状データＤ１，Ｄ２のそれぞれから幾何学的要素を抽出する（ステップ１２０２Ａ，１２０２Ｂ）。

次に、幾何学的要素対応付け処理部１６は、形状データＤ１の幾何学的要素３点の組を格納するハッシュテーブル（hash table）を作成する（ステップ１２０３）。幾何学的要素対応付け処理部１６は、ハッシュテーブルを検索して２個の形状データＤ１，Ｄ２の幾何学的要素３組とを対応付ける（ステップ１２０４）。

相対位置角度推定処理部１７は、対応付けられた３組の幾何学的要素の位置情報（代表点の位置情報）に基づいて、位置角度情報を算出する（ステップ１２０５）。相対位置角度推定処理部１７は、このときの位置角度パラメータを位置角度パラメータ空間に投票する（ステップ１２０６）。相対位置角度推定処理部１７は、形状データＤ２の全ての３点の組み合わせについて処理が完了するまで、ステップ１２０４〜１２０６の処理を繰り返す（ステップ１２０７）。

相対位置角度推定処理部１７は、一連の処理が完了すると、位置角度パラメータ空間から投票数が極大である複数の位置を検出する（ステップ１２０８）。相対位置角度推定処理部１７は、形状データＤ１，Ｄ２の全体を使用して最も合致するものを正解として選出する（ステップ１２０９）。ここで、合致の度合いの測定処理として、例えば投票数の極大位置に対応する位置角度パラメータを使用して、一方の形状データＤ１をもう一方の形状データＤ２に重ね合わせたものを初期値としてＩＣＰ（iterative closest point）処理等を実行する。このときに、対応付けられる形状上の点数や法線方向の一致する点数を基準として、それらの点数が多い場合に合致の度合いが大きいとして測定する。相対位置角度推定処理部１７は、正解として選出される投票数が極大となる位置に対応するパラメータで定義される位置角度変換の結果を示す相対的位置角度情報を算出する（ステップ１２１０）。

なお、第１から第４の変形例では、位置角度パラメータのみから相対的位置角度情報を算出（推定）する処理について説明したが、これにスケール成分を加えた相対的位置角度スケール情報も同様に算出することができる。

（第４の変形例）
図１５から図１７は、第４の変形例に関する相対的位置角度の推定処理（算出処理）を説明するための図である。

図１４に示す第３の変形例において、パラメータ空間への投票処理と投票数極大点からのパラメータ推定処理において、位置角度は全部で６自由度、位置角度スケールは全部で７自由度（位置３自由度、角度３自由度、スケール１自由度）である。このため、これを一度に投票するためには、6次元または７次元のパラメータ空間が必要である。しかし、現実的にはこのような高次元の空間をコンピュータのメモリ上に確保するのは困難である。

そこで、投票と極大値選出処理を多段階に分けて実行し、角度、スケール、位置をそれぞれ別の段階で算出する方法を提案する。以下、図１５のフローチャート及び図１６、１７の概念図を参照して、パラメータ空間への投票処理と投票数極大点からのパラメータ推定処理を複数段階に分ける場合の推定処理の手順を説明する。

まず、基本的処理と同様に、データ処理装置１３は、入力される距離画像データから２枚の形状データＤ１，Ｄ２を取得する（ステップ１３０１Ａ，１３０１Ｂ）。幾何学的要素抽出部１５は、各形状データＤ１，Ｄ２のそれぞれから幾何学的要素を抽出する（ステップ１３０２Ａ，１３０２Ｂ）。次に、幾何学的要素対応付け処理部１６は、形状データＤ１の幾何学的要素３点の組を格納するハッシュテーブル（hash table）を作成する（ステップ１３０３）。幾何学的要素対応付け処理部１６は、ハッシュテーブルを検索して２個の形状データＤ１，Ｄ２の幾何学的要素３組とを対応付ける（ステップ１３０４）。

相対位置角度推定処理部１７は、対応付けられた３組の幾何学的要素の位置情報（代表点の位置情報）に基づいて、位置角度スケールを示す位置角度情報を算出する（ステップ１３０５）。即ち、図１６に示すように、形状データＤ１(１４０１)の不変量から位置角度スケール変換（１４０４）により、形状データＤ２(１４０２)に関する同様の不変量を算出する。ここで、図１６に示すように、形状データＤ１(１４０１)から３点の幾何学的要素１４０３を取り出し、不変量である２点間の長さの比率（ａ／ｂ）となす角度（θ）をキーとする。幾何学的要素対応付け処理部１６は、当該キーとして、形状データＤ１(１４０１)の全ての３点の組をハッシュテーブル８０７に格納した後、形状データＤ２(１４０２)から幾何学的要素３点を取り出す。幾何学的要素対応付け処理部１６は、形状データＤ２(１４０２)に関する同様の不変量を算出し、ハッシュテーブル８０７のこれに合致する位置を検索し、形状データＤ１の３点と対応付けを行なう。

相対位置角度推定処理部１７は、このときの位置角度スケール(１４０４)を角度パラメータ空間に投票し、角度パラメータごとに位置角度情報を記憶部に保存する（ステップ１３０６）。具体的には、図１７（Ａ）に示すように、位置角度スケール(１４０４)を角度パラメータ空間(１４０５)に投票し、位置スケールパラメータを角度パラメータごとにリスト(１４０６)に保存する。相対位置角度推定処理部１７は、形状データＤ２の全ての３点の組み合わせについて処理が完了するまで、ステップ１３０４〜１３０６の処理を繰り返す（ステップ１３０７）。

相対位置角度推定処理部１７は、全ての組み合わせについての処理が完了すると、角度パラメータ空間(１４０５)から投票数の極大位置（１４０７）を１個以上選出する（ステップ１３０８）。このとき、図１７（Ｂ）に示すように、角度パラメータに対応するリスト(１４０６)内の位置スケールをスケールパラメータ空間(１４０９)に投票する（ステップ１３０９）。相対位置角度推定処理部１７は、位置パラメータをスケールパラメータごとにリスト(１４１０)に格納する。

相対位置角度推定処理部１７は、リスト(１４０６)内の全てのパラメータについて投票処理が完了した後に、スケールパラメータ空間(１４０９)から投票数の極大位置(１４０７)を検出する（ステップ１３１０のＹＥＳ、１３１１）。さらに、図１７（Ｃ）に示すように、このリスト(１４１０)内の位置パラメータを位置パラメータ空間(１４１２)に投票する（ステップ１３１２）。相対位置角度推定処理部１７は、全ての組み合わせについて投票処理が完了した後に、位置パラメータ空間(１４１２)から同様に投票数の極大位置(１４０７)を検出する（ステップ１３１３のＹＥＳ、１３１４）。

最終処理として、相対位置角度推定処理部１７は、各段階のパラメータ空間の極大位置(１４０７)に対応する角度成分(１４０８)、スケール成分(１４１１)、平行移動成分(１４１３)を合わせて、２形状データＤ１，Ｄ２間の位置角度スケール変換(１４１４)の結果を示す相対的位置角度情報を算出する（ステップ１３１５）。

なお、スケールパラメータに関しては、入力となる形状データＤ１，Ｄ２が、レーザレンジファインダ等の予め対象物体の大きさが現実世界に対して固定であるような入力機器を使用して取得される場合は推定する必要がない。この場合の推定処理は、スケールパラメータを１として固定し、これを推定する処理を省略して、角度と位置の推定処理を２段階で実行することになる。

（第５の変形例）
図１８は、第５の変形例に関する相対的位置角度の推定処理（算出処理）を説明するための図である。

図５に示す本実施形態の基本的処理において、入力形状データＤ１，Ｄ２が、広範囲を撮像したものや、細かい形状を撮像したものである場合に、そこから抽出される幾何学的要素の数は増大する。これに伴って、幾何学的要素３点の組み合わせ数も急激に増大し、同じキーをもつ組み合わせ数も増大する。このような場合にも、対応づける組み合わせ数を抑制して処理効率を維持する方法として、入力形状データＤ１，Ｄ２を分割し、部分形状データ毎に位置角度を推定して結果を統合する方法が有効である。

以下、図１８のフローチャートを参照して、いわばデータ分割・統合方法を適用した相対的位置角度の推定処理（算出処理）を説明する。

まず、基本的処理と同様に、データ処理装置１３は、入力される距離画像データから２枚の形状データＤ１，Ｄ２を取得する（ステップ１５０１Ａ，１５０１Ｂ）。次に、データ処理装置１３は、各形状データＤ１，Ｄ２のそれぞれを、空間情報によって複数の領域にデータ分割処理を実行する（ステップ１５０２Ａ，１５０２Ｂ）。データ分割方法としては、例えば予め設定された間隔で格子状に分割する。

データ処理装置１３は、形状データＤ１，Ｄ２毎に分割領域を選択し、選択した各分割領域について、図５のフローチャートで示す相対的位置角度の推定処理を実行する（ステップ１５０３Ａ，１５０３Ｂ，１６１５）。即ち、幾何学的要素抽出部１５は、各分割領域のそれぞれから幾何学的要素を抽出する（ステップ１５０４Ａ，１５０４Ｂ）。次に、幾何学的要素対応付け処理部１６は、形状データＤ１の分割領域の幾何学的要素３点の組を格納するハッシュテーブル（hash table）を作成する（ステップ１５０５）。幾何学的要素対応付け処理部１６は、形状データＤ２の分割領域から幾何学的要素３個を選び、ハッシュテーブルを検索して不変量の合致する形状データＤ１の分割領域の幾何学的要素３個とを対応付ける（ステップ１５０６）。

次に、相対位置角度推定処理部１７は、対応付けられた３組の幾何学的要素の位置情報（代表点の位置情報）に基づいて、位置角度情報を算出する（ステップ１５０７）。相対位置角度推定処理部１７は、このときの位置角度パラメータを位置角度パラメータ空間に投票する（ステップ１５０８）。相対位置角度推定処理部１７は、形状データＤ２の分割領域全ての３点の組み合わせについて処理が完了するまで、ステップ１５０６〜１５０８の処理を繰り返す（ステップ１５０９）。相対位置角度推定処理部１７は、全ての組み合わせについて処理が完了すると、位置角度パラメータ空間から投票数が極大である位置を検出する（ステップ１５１０）。

相対位置角度推定処理部１７は、推定処理に算出された分割領域の相対的位置角度情報を記憶部に格納する（ステップ１５１１）。なお、相対位置角度推定処理部１７は、図５に示す推定処理の代わりに、図１１、１２、１４、１５に示す推定処理の方法を適用してもよい。

相対位置角度推定処理部１７は、全ての分割領域について処理が完了すると、格納された分割領域間の相対的位置角度を統合して一つの結果を算出する（ステップ１５１２のＹＥＳ、１５１３)。相対位置角度推定処理部１７は、算出した統合結果を入力形状データＤ１，Ｄ２全体の相対位置角度情報として算出する（ステップ１５１４）。

なお、分割領域間の相対的位置角度を統合する方法としては、例えば、個々の位置角度推定処理と同様に、分割領域毎の位置角度推定結果を位置角度パラメータに投票し、投票数の極大位置を選出する方法でもよい。本変形例によれば、入力形状データＤ１，Ｄ２を複数の領域に分割して、投票と極大選出による位置角度推定処理を２段階に分けて実行する方法により、幾何学的要素３点の組み合わせの数を大幅に削減し、推定処理効率を向上することができる。

ここでは、位置角度パラメータのみから相対的位置角度情報を算出（推定）する処理について説明したが、これにスケール成分を加えた相対的位置角度スケール情報も同様に算出することができる。

（応用例）
図１９及び図２０は、本実施形態の推定処理方法を具体的な装置に適用した場合の構成を示す図である。

図１９は、パターンマッチング装置の構成を示す図である。図１９に示すように、パターンマッチング装置は、図１に示す本実施形態の装置と同様に、画像入力装置１０と、入力インターフェース１１と、表示出力装置１２と、データ処理装置（画像処理部）１３とを有する。データ処理装置（画像処理部）１３は、入出力インターフェース１４と、幾何学的要素抽出部１５と、幾何学的要素対応付け処理部１６と、相対位置角度推定処理部１７と共に、パターンマッチング処理部１８を含む構成です。

パターンマッチング処理部１８は、前述の位置角度推定方法により相対位置角度推定処理部１７で算出された位置角度情報（位置角度スケール変換による情報）を使用して、２個の形状データ中の物体が同じ形状であるか否かを判別する。具体的には、２個の形状データを重ね合わせ、一方の形状上の各点についてもう一方の形状上の対応点の有無、対応点との距離を調べることにより、物体が同じ形状であるか否かを判別する。

このパターンマッチング装置を、例えば機械部品の検査システムに適用する場合に、標準物体の形状データと検査対象物体の形状データを入力として、検査対象物体の形状が正常であるか否かを判定する。また、例えば建造物等が設計段階のものと同じか否かを検査するシステムに適用する場合に、設計段階のＣＡＤデータから生成した形状データと、建造物を計測した形状データとを入力として、ＣＡＤデータと建造物の形状が同じであるか否かを判定する。さらに、建造物が建築時と比較して変形しているか否かを検査するためには、建築時に計測した形状データと現在計測した形状データとを入力データとして、同様に形状の相違を判定する。

図２０は、物体認識装置の構成を示す図である。図２０に示すように、物体認識装置は、図１に示す本実施形態の装置と同様に、画像入力装置１０と、入力インターフェース１１と、表示出力装置１２と、データ処理装置（画像処理部）１３とを有する。データ処理装置（画像処理部）１３は、入出力インターフェース１４と、幾何学的要素抽出部１５と、幾何学的要素対応付け処理部１６と、相対位置角度推定処理部１７と共に、物体認識処理部１９を含む構成です。

物体認識処理部１９は、前述の位置角度推定方法により相対位置角度推定処理部１７で算出された位置角度情報（位置角度スケール変換による情報）を使用して、２個の形状データ中の物体の相違度を測定する。具体的には、２個の形状データを重ね合わせ、一方の形状上の各点についてもう一方の形状上の対応点の有無、対応点との距離を調べることにより、物体が相違度を測定する。物体認識処理部１９は、この測定結果に基づいて、データベース(ＤＢ)２０に登録された形状データと入力形状データとを比較し、入力形状データと最も近いデータベース２０中の物体を認識結果として出力する。データベース２０には、例えば車種判別を目的とする場合には、認識対象の車種のＣＡＤデータまたは形状データが登録される。また、顔認識を目的とする場合には、認識対象の顔形状データがデータベース２０に登録される。

以上要するに、本実施形態及び各変形例によれば、形状データから幾何学的要素を抽出し、その一部のみを使って相対的位置角度情報を算出する。このため、形状データ全体や、抽出した幾何学的要素の全てを使用する方法と比較して、相対的位置角度情報を推定（算出）するための処理量の削減を図ることが可能となる。具体的には、１点で代表することのできる情報であれば、点、線分、領域などの異なる性質の要素を混合して扱うことができるため、認識対象の形状データに応じて信頼性の高い要素を選択的に利用することができる。また、幾何学的要素対応付け処理においては、相似不変量をキーとするハッシュテーブルを利用するため、位置、角度、スケールに関する不変性を残しつつ、処理速度の高速化を量ることが可能となる。

さらに、幾何学的要素の特徴量や、幾何学的要素間の特徴量を利用する処理により、これらの類似度に基づいて対応する候補を絞り込むことが可能となるため、処理量の削減に有効である。また、形状データの部分的な情報に基づいて複数の位置角度候補を想定した後に、形状データ全体を使用して候補を絞り込む方法により、部分的な情報のみを使う方法よりも、信頼性の高い結果を得ることが可能となる。さらに、形状データを分割し、分割された要素それぞれで位置角度を算出し、最終的な処理として各算出結果を統合する方法により、位置角度推定処理に使用する３点の組み合わせ数を大幅に削減できるため、推定処理量を効果的に減少できる。

本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。

１０…画像入力装置、１１…入力インターフェース、１２…表示出力装置、
１３…データ処理装置（画像処理部）、１４…入出力インターフェース、
１５…幾何学的要素抽出部、１６…幾何学的要素対応付け処理部、
１７…相対位置角度推定処理部、１８…パターンマッチング処理部、
１９…物体認識処理部、２０…データベース。

Claims (13)

1. 同一の３次元形状の認識対象に対する複数の形状データを入力する入力手段と、
   前記各形状データのそれぞれから幾何学的要素を抽出する幾何学的要素抽出手段と、
   相似不変量をキーとするハッシュテーブルを使用し、前記各幾何学的要素間で位置関係が合致する組み合わせを選出する幾何学的要素対応付け手段と、
   前記選出される複数の組み合わせに基づいて、前記各形状データ間で前記認識対象の相対的位置角度を示す相対的位置角度情報を算出する位置角度推定手段と
   を具備したことを特徴とする３次元形状認識装置。
2. 同一の３次元形状の認識対象に対する複数の形状データを入力する入力手段と、
   前記各形状データのそれぞれから幾何学的要素を抽出する幾何学的要素抽出手段と、
   相似不変量をキーとするハッシュテーブルを使用し、前記各幾何学的要素間で位置関係が合致する組み合わせを選出する幾何学的要素対応付け手段と、
   前記選出される複数の組み合わせに基づいて、前記各形状データ間で前記認識対象の相対的位置角度スケールを示す相対的位置角度スケール情報を算出する位置角度推定手段と
   を具備したことを特徴とする３次元形状認識装置。
3. 前記位置角度推定手段は、
   前記各幾何学的要素間で位置関係が合致する３点の幾何学的要素の組み合わせから算出される相対的位置角度スケールとして、前記相対的位置角度情報を算出するように構成されていることを特徴とする請求項１または請求項２のいずれか１項に記載の３次元形状認識装置。
4. 前記幾何学的要素は、特徴点、線分、稜線、部分領域、部分領域を近似するプリミティブ形状などの前記形状データの特徴的な部分を表す情報であり、
   前記位置角度推定手段は、
   前記各幾何学的要素を１点の代表点として表し、当該代表点の位置情報を使用して前記相対的位置角度情報を算出するように構成されていることを特徴とする請求項１、請求項２、請求項３のいずれか１項に記載の３次元形状認識装置。
5. 前記位置角度推定手段は、
   前記相対的位置角度スケールを位置角度スケールのパラメータ空間に投票し、
   前記投票数が極大となる位置に対応するパラメータで表される位置角度スケールを示す前記相対的位置角度情報を算出するように構成されていることを特徴とする請求項２に記載の３次元形状認識装置。
6. 前記各幾何学的要素の性質又はその周辺情報の性質を表す特徴量を算出する手段を含み、
   前記幾何学的要素対応付け手段は、
   前記各幾何学的要素の特徴量の類似度が基準値より低い場合には前記各幾何学的要素の組み合わせをリジェクトするように構成されている請求項１から請求項５のいずれか１項に記載の３次元形状認識装置。
7. 前記各幾何学的要素間の関係を表す特徴量を算出する手段を含み、
   前記幾何学的要素対応付け手段は、
   同一の第１の形状データに存在する２個の幾何学的要素間の特徴量と、前記第１の形状データとは異なる第２の形状データに存在し前記２個の幾何学的要素と対応付けされる２個の幾何学的要素間の特徴量との類似度が基準値より低い場合には、前記各幾何学的要素の組み合わせをリジェクトするように構成されている請求項１から請求項５のいずれか１項に記載の３次元形状認識装置。
8. 前記位置角度推定手段は、
   前記相対的位置角度スケールを前記パラメータ空間に投票した投票数が極大となる複数の位置を検出し、
   前記各位置に対応するパラメータで表される位置角度スケールから前記各形状データの全体を使用して最も合致するものを正解として選出し、
   前記選出される位置角度スケールを示す前記相対的位置角度情報を算出するように構成されていることを特徴とする請求項５に記載の３次元形状認識装置。
9. 前記各形状データを空間上で分割する手段を含み、
   前記位置角度推定手段は、
   前記分割された各分割領域に関する各相対的位置角度情報を算出し、
   前記各相対的位置角度情報を統合した相対的位置角度情報を算出結果として出力するように構成されていることを特徴とする請求項１又は請求項２のいずれか１項に記載の３次元形状認識装置。
10. 請求項１又は請求項２のいずれか１項に記載の３次元形状認識装置を利用し、形状データの同定処理を実行するパターンマッチング処理手段を有する構成であることを特徴とするパターン認識装置。
11. 請求項１又は請求項２のいずれか１項に記載の３次元形状認識装置を利用し、予め用意される形状データと入力形状データとの比較結果に基づいて物体を認識する物体認識処理手段を有する構成であることを特徴とする物体認識装置。
12. ３次元形状認識装置に適用する位置角度推定方法であって、
    同一の３次元形状の認識対象に対する複数の形状データを入力する処理と、
    前記各形状データのそれぞれから幾何学的要素を抽出する処理と、
    相似不変量をキーとするハッシュテーブルを使用し、前記各幾何学的要素間で位置関係が合致する組み合わせを選出する処理と、
    前記選出される複数の組み合わせに基づいて、前記各形状データ間で前記認識対象の相対的位置角度を示す相対的位置角度情報を算出する処理と
    を実行することを特徴とする位置角度推定方法。
13. ３次元形状認識装置に適用する位置角度推定方法であって、
    同一の３次元形状の認識対象に対する複数の形状データを入力する処理と、
    前記各形状データのそれぞれから幾何学的要素を抽出する処理と、
    相似不変量をキーとするハッシュテーブルを使用し、前記各幾何学的要素間で位置関係が合致する組み合わせを選出する処理と、
    前記選出される複数の組み合わせに基づいて、前記各形状データ間で前記認識対象の相対的位置角度スケールを示す相対的位置角度スケール情報を算出する処理と
    を実行することを特徴とする位置角度推定方法。

Images