JP4284288B2 - パターン認識装置及びその方法 - Google Patents

Description

本発明は、パターン認識装置及びその方法に関する。

画像から特定の物体の位置、姿勢、形状を検出、認識する技術は、コンピュータビジョンの中で重要な技術である。従来法として、画像中から登録されている物体を認識するためのパターン認識方法として特許文献１に開示された方法がある。

特許文献１のパターン認識方法は、部分的な隠れに対応するために、下記の性質をもつものである。

第１の性質は、部分的な情報の登録とモデルの多重記述を行う。

第２の性質は、姿勢を規定しないための不変量に基づいたモデルの記述を行う。

第３の性質は、ノイズに強い検出が可能といった性質をもつ。

このパターン認識方法は、高速な部分テンプレートの検索のためにハッシュテーブルを用いた部分画像の分散モデル表現を行い、高速かつ正しい精度のよい物体認識、物体抽出を行うことを目的としている。

部分的な情報の登録と検索のために、ｎ個の画像特徴点の全てに対して、３点の組み合わせを行い、その３点の組み合わせによって得られた基底ベクトルに沿った部分パターンを切り出している。
特開２００３−２４２５０９公報

しかしながら、上記のパターン認識方法では、特徴点３点の組み合わせ数のオーダーはＯ（ｎ^３）となり、特徴点数が増加すると、多くの時間と登録のための大量のメモリを必要とすることに問題点がある。

図９の左図は、その特徴点３点の組み合わせ数と特徴点数をグラフにしたものであり、２００点の特徴点数で、その組合せ数は、８，０００，０００個に達する。

高速化の観点から、特許文献１では、下記の２つの方法が示されている。

第１の方法は、ランダムハフ変換で採用されているように、特徴点をランダムに選択し、投票数を削減することと同様な手法をとる。

第２の方法は、基底情報を構成するベクトルの長さ、角度、などに対する、いろいろな制約や制限を利用する。

しかしながら、特徴点の数が多くなった状況において、第１の方法では、十分な精度を得るためには、相当数の投票が必要である。また、第２の方法では、制限によって、特定の方向の物体が検出できなくなるなどの問題点がある。さらに、これらの高速化方法では、登録時の組み合わせ数を削減することは本質的ではなく十分ではない。

本発明は、認識対象物が撮影された画像と、予め登録したモデルとを比較して、前記認識対象物の認識を行うパターン認識装置であって、前記認識対象物が撮影された画像を入力する画像入力手段と、前記画像中から複数の特徴点を抽出する特徴点抽出手段と、前記複数の特徴点の全てを周上、または、内部領域に包含する凸多角形を形成し、当該凸多角形の頂点、または、前記複数の特徴点を頂点とする複数の三角形の領域に分割する三角形分割生成手段と、前記各三角形の各頂点にある特徴点の組み合わせを複数選択する特徴点選択手段と、前記複数選択された３点の特徴点の組み合わせから、これら特徴点の位置や位置関係を表す基底をそれぞれ計算する基底計算手段と、前記各基底に対応する前記認識対象物の部分パターンを前記画像からそれぞれ抽出する部分パターン抽出手段と、幾何学的変換に関して不変なパラメータを少なくとも含むインデックスパラメータに基づいて分割された複数の登録場所から構成され、かつ、前記モデルの部分パターンが、その部分パターンに関するインデックスパラメータに対応した登録場所に登録されたテーブルを記憶するテーブル記憶手段と、前記認識対象物の部分パターンに対応するインデックスパラメータに基づいて、前記テーブルの登録場所を決定するインデックス検索手段と、前記テーブルの登録場所に登録された前記モデルの部分パターンと、前記認識対象物の部分パターンの類似度とを判定するパターン類似度計算手段と、を有することを特徴とするパターン認識装置である。

本発明は、メモリの効率化と検索の高速化を行うことができる。これは、オクルージョンに強いなどの従来の性質を保ったまま、効率的なモデル探索が行われ、高速な検索への適用が可能となる。

本発明の実施形態の考え方について説明する。

物体認識の観点から、ある１つの物体の構成要素が離れた場所に現れることはないため、特徴点の組み合わせは、比較的近傍にある点にのみ制限してもよい。また、同じ特徴点集合に対しては、同じ組み合わせを生成できることが望ましい。

特徴点集合に対して、その近傍点の近傍領域毎に分割するボロノイ分割を考えると、ある特徴点の近傍領域には同じ物体が存在する確率が高い。

そこで、その双対グラフであるドロネー三角形分割を考える。このドロネー三角形分割では、比較的隣接した特徴点による三角形が構成される。しかも、ドロネー三角形分割による三角形は鈍角をもつものが少なくなるように構成されることが知られている。

そこで、本発明の実施形態では、ある特徴点集合に対して、ドロネー三角形分割を考え、その三角形に従った３点の選択を行うことで、組み合わせ数を削減し、かつ、幾何学的な周辺情報を反映した特徴点選択を可能とした。

以下、この考え方に基づいて本発明の各実施形態を図面に基づいて説明する。

［第１の実施形態］
以下、本発明の第１の実施形態のパターン認識装置について図面に基づいて説明する。

本実施形態は、ある画像中から対象とする物体の位置と姿勢を検出する方法である。認識対象物とする物体はどのようなものでも構わないが、本実施形態では、図２のような箱の物体を、検出する例を説明に用いる。

本実施形態では、この箱の任意の位置と任意の姿勢を写した画像を一つのモデルとして、様々な位置や姿勢の箱に関する画像を複数のモデルとして登録する。

そして、同じ箱が撮影された検出対象画像について、どのモデルと類似しているかを判断して、その検出対象画像に撮影された箱の位置と姿勢を認識するものである。

そこで、以下の説明では「モデルの登録」と「投票によるモデルの検出と識別」の２つのフェーズに分けて説明する。

（１）パターン認識装置の構成
図１は、本実施形態のパターン認識装置の構成図である。

図１に示すように、パターン認識装置は、画像入力部１、特徴点抽出部２、三角形分割生成部３、特徴点選択部４、基底計算部５、部分パターン構成部６、インデックス計算部７、テーブル登録部８、パターン類似度計算部９、仮説情報生成部１０及び物体認識部１１から構成される。

このうち画像入力部１は、ＣＣＤカメラ、スキャナ、または、ディスク上、または、インターネット上に存在する画像ファイルを入力とする装置、などによって構成され、その他の特徴点抽出部２、三角形分割生成部３、特徴点選択部４、基底計算部５、部分パターン構成部６、インデックス計算部７、テーブル登録部８、パターン類似度計算部９、仮説情報生成部１０及び物体認識部１１の各機能は、パソコンなどのコンピュータに記憶されているプログラムによって実現される。

（２）モデルの登録
認識対象物のモデルの登録方法について図１、図３、図４を用いて説明する。

（２−１）モデル登録の処理の流れ
処理の流れを図３のフローチャートに基づいて説明する。

（２−１−１）画像入力部１
まず、図１の画像入力部１において、認識対象物を含む画像を入力する（図３のステップ３０１）。

（２−１−２）特徴点抽出部２
次に、特徴点抽出部２において、その画像に対して、特徴点の検出を行う（図３のステップ３０２）。

この特徴点の検出の手法としては、角点（コーナー）を検出するＨａｒｒｉｓのディテクタ〔非特許文献１参照：C.J.Harris and M.Stephens,A combined corner and edge Detector.InProc.4th Alvey Vision Conference,Manchester,pages 147-151,1988.〕によるものでよい。また、非特許文献２〔福井 和広、山口 修：“ 形状情報とパターン照合の組合せによる顔特徴点抽出”，信学論(D-II),vol.J80-D-II No.8(1997)〕で提案している分離度フィルタのようなものを用いてもよく、用途や認識対象物に合わせて方法を選択すればよい。

（２−１−３）三角形分割生成部３
次に、三角形分割生成部３において、特徴点集合に対する三角形分割を求める。ここで三角形分割の方法として、図９の右図のような、ドロネー三角形分割を用いる（図３のステップ３０３）。そこで分割された際に生成される三角形にしたがって、つぎの特徴点選択部４にて３点を選ぶ。

三角形分割生成部３が、どのようにしてドロネー三角形分割するかについて説明する。

モデル、または、認識対象物が写っている画面上に凸多角形を形成する。この凸多角形は、次の条件を満たすように形成される。

まず、モデルに凸多角形を形成する場合は、図２に示すようにこのモデルが含まれるようにするために、モデルを写した画像の特徴点を頂点として凸多角形を形成する。そして、検出された特徴点の全てが、凸多角形の内部か周上にあるようにする。なお、モデルが白い球のように特徴点を検出できない可能性がある物もある。そのときは、強制的に仮の特徴点（例えば、画像の四隅部）を頂点として凸多角形を形成する。

また、認識対象物に凸多角形を形成する場合は、図１０に示すように認識対象物を写した画像の特徴点、または、それ以外の仮の特徴点（例えば、画像の四隅部）を頂点として凸多角形を形成する。そして、検出された特徴点の全てが、凸多角形の内部か周上にあるようにする。

ドロネー三角形分割では、この凸多角形内部のすべての特徴点に対し、複数の三角形を求めるが、それぞれの三角形の外接円が他の特徴点を含まないように、三角形が分割される。

そして、このように形成された凸多角形の頂点または前記複数の特徴点を頂点とする複数の三角形の領域に分割する。

（２−１−４）特徴点選択部４
特徴点選択部４において、モデル、または、認識対象物を含む部分の特徴点を選択する。ここでは、特徴点の中から、生成された三角形の頂点の３つの点の組み合わせを求める（図３のステップ３０４）。

（２−１−５）それ以降の処理
そして、その組み合わせ毎に部分パターンの登録を行う。それぞれの３点の組み合わせから、基底計算部５にて、２つのベクトルを決定し、それに基づいた基底情報を用いて、部分パターン構成部６において、周辺の領域の部分濃淡パターンを切り出す（図３のステップ３０６）。

それぞれの切り出された部分濃淡パターンは、インデックス計算部６において、ハッシュ関数によって登録場所が計算され（図３のステップ３０７）、テーブル登録部７が管理するハッシュテーブルに登録される（図３のステップ３０８）。

これを繰り返し、全ての組み合わせが求まった時点で一つのモデルの登録が終了する（図３のステップ３０５）。複数のモデルを登録する場合には、上記処理を繰り返す。

（２−２）モデル登録の具体例
モデル対象である箱が撮影された図４−４０１の画像をモデル登録する場合について説明する。

モデル対象である箱の特徴点を検出した結果を図４−４０２に示す。これらの特徴点に対して、図４−４０３のようにドロネー三角形分割を求める。

次に、生成された三角形のそれぞれの頂点の３点の組み合わせを全て求める。この選択した３点の特徴点の組み合わせを特徴点グループという。

図４−４０４は、これら特徴点グループの中から１つの特徴点グループを図示したもので、その３点の特徴点から２つの基準ベクトルを求める。図４−４０５は、２つの基準ベクトルで張られる基底を示したもので、２つの基準ベクトルのそれぞれの長さＬ１、Ｌ２とその間の角度θを計算しておく。

なお、「基底」とは、いくつかの基準ベクトルから、座標系を構成するもので、原点と座標軸の情報をもつものである。ここでは、２つの基準ベクトルの始点を原点とし、各基準ベクトルの方向を座標軸の方向とする。

そして、特徴点グループの定義として、特徴点Ｆ１、Ｆ２、Ｆ３でグループを形成する場合に、特徴点Ｆ１を原点したものと、特徴点Ｆ２を原点としたものとでは異なるグループを形成するものとする。すなわち、１つの三角形に対しては、６通りの基底の取り方が存在する。

次に、その基底に対して、その原点と２つの基準ベクトルの周辺の画像パターンを切り出す（図４−４０６）。切り出しを行う場合、２つの基準ベクトルが張る基底の座標系を直交座標系に変換して画像パターンを切り出す。

この画像を切り出すために、２つの基準ベクトルが張る基底の座標系を直交座標系に変換する。すなわち、基準ベクトルのなす角度は直角に、２つの基準ベクトルの長さは同じになるように、画像全体を変形させる。

その後、基底の原点を中心とした、予め決められた範囲の濃淡画像（ｍ×ｎピクセルの画像）を部分パターンとして切り出す。

切り出された濃淡画像は、各種の幾何学的変換に対して不変な形式となる。このように濃淡画像に対して予め座標変換を行って登録、検索することで、後のパターン同士の比較の際に、濃淡画像に対する幾何学的変換を行うことなく類似性を判断することが可能となる。

図４−４０７が、切り出された部分濃淡画像を表しており、本実施形態では、正方形の濃淡画像を表している。

切り出された部分画像は、基準ベクトルの長さ、方向によっては、歪んだ見え方になる場合がある。

図４−４０８は、同様に別の３点の組み合わせから、基底の構成と部分パターンの切り出しを行ったものである。

それぞれの切り出された部分パターンは、ハッシュ関数によって計算されたテーブル（以下、ハッシュテーブルという）の所定の登録場所に登録する。この登録内容は、部分濃淡画像に加え、着目点の種類や、認識対象物全体における部分パターンの相対的な位置情報などを同時に含んでもよい。これについては後述する。

（２−３）ハッシュテーブルへの登録
本実施形態では、ハッシュ関数の持つ性質として、与えた基底に対して、平行移動、回転、拡大縮小変換に対しての不変性を利用する。ある同じ条件の基底を持つものは、これらの変換を施したとしても、同じ返り値を返す関数を定義する。

ここで、基底を構成する２つの基準ベクトル間の角度と２つのベクトルの長さの比については、平行移動、回転、拡大、縮小といった幾何学的変換に対して不変であるため、この不変性を用いたハッシュ関数の構成を考える。すなわち、２つの基準ベクトル間の角度と２つのベクトルの長さの比を、幾何学的変換に関して不変なパラメータ（以下、インデックスパラメータという）として、ハッシュテーブルの登録場所を決定する。

ハッシュ関数Ｈは、以下のように３点の特徴点ｐ１，ｐ２，ｐ３を引数として与え、インデックスパラメータである長さの比Ｒａｘｓと角度θａｘｓを求めた後、量子化し、ハッシュテーブルの位置を返す。ここで、ｐ１、ｐ２、ｐ３の各位置は、絶対座標系の原点を基準にして表されている。また、基底における原点は、特徴点ｐ１とする。

図４−４０９は、２次元的にハッシュテーブルを表しており、縦軸は２つの基準ベクトルの長さの比Ｒａｘｓ、横軸は２つの基準ベクトルのなす角度θａｘｓを表すものとする。

ここで、各基底毎に求まった２つのベクトルの間の角度θａｘｓ、長さの比Ｒａｘｓを求め、その値が示すハッシュテーブルの位置に、切り出した部分濃淡パターンなどを登録する。

なお、これらのθａｘｓ、Ｒａｘｓについては、誤差も考慮して、適当な量子化を行ってよい。

各ハッシュテーブル上の（登録される）実体は、次のように表現する。なお、この形式、種類に限定されるものではない。

「Ａｘｓ」は、３つの特徴点に基づいた座標系情報を表す。具体的には３点の座標位置、２つの基底ベクトルの情報などを含む。

「Ｌａｂｅｌ」は、各特徴点がどの検出点であるかなどの情報を記述する。

「Ｉｎｖ」は、変換に対する不変量であり、先に示したθａｘｓ、Ｒａｘｓなどが含まれる。

「Ｒｅｌ」は、モデルを囲む矩形の領域Ｇｐを表現した点集合を相対的に表現したもので、検出結果の場所を示すためや再度その領域を抽出することなどに利用される。具体例としては、図５−５０５のような矩形の領域Ｇｐを表すための頂点集合の４点を、図５−５０６のように変換した平行四辺形の４点の座標位置で記述する。

「ＳＰａｔ」は、特徴点に囲まれた局所画像であり、切り出した部分濃淡パターンを示す。

「ＧＰａｔ」は、大域画像を利用したもので、例えば、図２（ａ）に示したような、箱全体の画像を利用し、画像のマッチング結果を利用する。

「ＦｅａＰｎｔ」は、画像特徴点とは異なる着目点列の情報を記述する。ここでの着目点とは、物体上の特徴的な点位置を表すもので、例えば、図５−５０１の例では、画像特徴点（図中の十字印）としては、箱の角の点が検出されていない。そこで、図５−５０１のように、着目点（図中の白丸印）の点を予め登録しておいて、後で述べる相対的な位置情報として、箱の角の位置を着目点位置として記憶する。これは、認識時に着目点位置から、物体の特徴的な場所の情報を推定するために利用される。それぞれの組み合わせ全てに対して同様の処理を行い、モデルを登録する。

図５は、各種のデータについて図示したものである。

図５−５０１は箱を含む画像である。着目点（ＦｅａＰｎｔ）としては、６つの点（箱の角）が選択されている。

図５−５０２は、特徴点（画像中の十字印）の３点から張られる基底を表し、その基底ベクトル間の角度、ベクトルの長さ比は、ハッシュテーブルのインデックスとして利用する。

図５−５０３は、その３点から張られる基底により、切り取られる周辺の濃淡パターン（ＬＰａｔ）を表す。

これに加え同時に図５−５０４のように、箱の領域全体の濃淡パターン（ＧＰａｔ）も切り出しておく。

さらに、その基底情報によって生成される座標系によって、全体の領域を表す矩形を図５−５０５から図５−５０６のように表現を替え、各頂点の相対的な座標Ｒｅｌを計算しておく。これは、検出された場合に相対的な全体領域の位置がどのようになるかを求めるために利用する。

モデルの登録時には、部分パターン（図５−５０３）だけを登録するのではなく、全体パターン（図５−５０４）と図５−５０６で示した全体領域の相対座標位置も追加する。

これは認識時には、同様に、部分パターンを切り出すが、それと同時に全体領域の切り出しを行うことも必要となる。選択された基底情報に対して、全体領域の相対座標位置を計算し、実際の画像上の座標位置をもとめ、その領域の濃淡パターンを全体パターン候補として利用する。

全体パターンの利用法としては、モデルの検索の際に、部分パターン同士の類似度に加え、全体パターン同士の類似度計算の結果を利用することが挙げられる。

これまで１枚の画像に対しての処理を述べたが、同じ認識対象物で撮影条件が異なる別の画像を用いて、同様に登録を行うことで、様々な環境で撮影された認識対象物の認識が可能となる。

ハッシングアルゴリズムにおいては、登録を逐次行っていった場合、ある３点の組み合わせにより同じハッシュ関数の値を持つ場合、その部分パターンが同じ場所に登録されてしまうことになる。そのためハッシュテーブルの各位置には、複数の候補パターンをリスト構造としてつなげて複数個持てるようにしておく。

（３）投票によるモデルの検出と識別
次に、画像中から認識対象物を検出する方法について説明する。

認識対象物の検出アルゴリズムをわかりやすく説明するために、ハッシュテーブルを用いたモデルの選択、仮説の生成と、仮説の統合、検証による認識とに分けて説明する。

（３−１）ハッシュテーブルを用いたモデルの選択
（３−１−１）モデルの選択処理の説明
ハッシュテーブルを用いたモデルの選択の処理の流れについて図６に基づいて説明する。

まず、認識対象物とする画像を、図１の画像入力部１に画像を読み込む（図６のステップ６０１）。

次に、特徴点抽出部２において、認識対象物とする画像に対して特徴点の抽出を行う（図６のステップ６０２）。

次に、検出された特徴点から、三角形分割生成部３において、検出された特徴点のドロネー三角形分割を求める（図６のステップ６０３）。

次に、生成された三角形の各頂点に対して、特徴点選択部４において、検出された特徴点の組合わせを選び（図６のステップ６０４）、組み合わせが全て選ばれるまで（図６のステップ６０５）、逐次行われる。

各組み合わせに対して、基底計算部５にて基底を計算する（図６のステップ６０６）。

そして、その基底におけるハッシュ関数のインデックスパラメータをインデックス計算部７にて計算する（図６のステップ６０７）。

テーブル登録部８において、そのインデックスパラメータに対応するハッシュテーブルの登録場所を検索する（図６のステップ６０８）。

これは、登録パターンが存在するかどうかにより判断が分かれる（図６のステップ６０９）。

登録パターンが存在する場合は、部分パターン構成部６で、周辺の部分パターンを切り出し、登録パターンと部分パターンとの類似度をパターン類似度計算部９において計算して比較する。なお、パターン同士の類似度の計算法については、一般の濃淡パターンに対する類似度の計算法、例えば、正規化相関、ＳＳＤ、単純類似度などでもよい。このパターン同士の類似度計算の方法については問わない。

登録パターンが存在しない場合は、モデルが存在しないため、類似度の計算は行われない（図６のステップ６０９）。

モデルの選択が行われた後、３点の組み合わせによる周辺領域の部分パターンが類似している場合、検出したい対象領域の一部である可能性を持っていることから、仮説情報生成部１０において、検出対象領域の仮説情報を生成する。これを全ての検出された特徴点の組み合わせについて行い、仮説情報の生成処理を繰り返す。これについては、後述する。

（３−１−２）モデルの選択処理の具体例
これまでの手順を図７を用いて具体的に説明する。

本処理の目的は、入力した画像に基づいて、先に説明したモデル登録で登録を行った箱の位置、姿勢の検出を行うことである。

図７−７０１が、認識対象物である箱が撮影された入力画像である。この画像からモデル登録と同様に特徴点検出を行う（図７−７０２）。

そして、その特徴点集合に対してドロネー三角形分割を求める（図７−７０３）。

次に、特徴点の中からモデル登録と同様に三角形分割にしたがって３点を選択する。

その３点に基づいて作成した基底情報により、周辺の領域の濃淡パターンを切り出す（図７−７０４）。

次に、基底情報の不変量に対応するハッシュテーブル（図７−７０５）の場所を検索する。

登録パターンが存在し、かつ、類似度が設定した閾値を超えた場合、仮説が生成される。

図７−７０６のように、適合するパターンがあった場合、それぞれの仮説が生成される。

（３−２）仮説情報の生成
仮説情報の内容としては、特徴点の場所の情報、位置や大きさの情報、濃淡パターン情報、モデルパターンとの類似度などの情報を含む。一例として仮説Ｈを次の５つ組で定義する。なお、仮説情報の定義はこれに限らない。

「ＴＲｅｌ」は、選択した３点の特徴点にしたがって、相対的な位置情報であるＲｅｌを変換した位置情報であり、画像中での認識対象物の存在領域を表している。

「Ｐｓｉｍ」は、モデルとして登録されている濃淡パターンと選択された部分パターンとの類似度を表す。

「Ｇｓｉｍ」はＴＲｅｌに対応する矩形から切り出された全体パターンと、登録されている全体パターンとの類似度を表す。

「ＴＦｅａＰｎｔ」は、相対的な着目点の位置情報を表すもので、詳細は第３の実施形態で述べる。

なお、検出時に選択された３点から決定されるパターン情報をハッシュテーブルに記述されているものと同様に次のＲｍのように表す。

また、同じハッシュ関数の値を持つ部分に存在する部分モデルを

とする。

すなわち、検索の結果で同じ場所にあるため、Ｉｎｖｘ＝Ｉｎｖｍが成立している。仮説情報を生成するためには、以下のような４つの関数によってそれぞれの要素が計算される。

「ＦｕｎｃＧｅｏｍ」は、選択された基底に基づいて物体の存在位置を計算する関数である。具体的には、以下の式で計算される。ここで（．，．）は座標を表す。

「ＦｕｎｃＦｅａ」は、入力画像上での着目点の位置ＴＦｅａＰｎｔを計算する関数である。ＦｕｎｃＦｅａについては、第３の実施形態で説明する。

となる。

「ＦｕｎｃＳｉｍ」は、濃淡パターン同士の類似度を計算する関数である。パターン同士の類似度を求める方法には、前述したように様々なものがあるが、例えば、単純類似度の場合は以下の式で計算される。

各ハッシュテーブルに登録されている部分モデルの内容に基づき、それぞれの仮説の内容を計算する。なお、類似度値は低いものについても、全て仮説情報を生成するという使い方でもよい。

各仮説情報は、検出対象領域の一部であるという情報をもっているため、これらの情報を統合することによって物体の認識が行える。

（３−３）仮説情報の統合、検証による認識
部分パターンの類似度を用いて、検出対象領域の一部であるという仮説情報を前述のように生成し、全ての仮説情報を仮説空間に投票し、結果を統合する。これは、物体認識部１１において処理される。
本実施形態では、モデルの登録時に設定した着目点の場所を特定できるような検出方法について説明を行う。

（３−３−１）仮説投票処理の具体例
仮説情報を投票するための仮説空間は、物体認識部１１に含まれる仮説統合部で管理される。図７−７０７は、仮説空間を図的に表したものである。図７−７０８は、仮説空間は、それぞれの検出される物体の姿勢、位置、などに対応したそれぞれの仮説投票箱により構成される。

図７−７０４に示した３点が選ばれた場合の仮説に対し、それぞれがもつ、部分パターンＬＰａｔ、全体パターンＧＰａｔとテーブルに登録されているパターンとのパターンマッチングの類似度Ｐｓｉｍ，Ｇｓｉｍを計算する。その双方、もしくは条件的に片方のみが設定した閾値を超えたもののみを投票する仮説として扱う。

図７−７０６では、３つの部分パターンが検索されているが、２つのみがパターンの閾値を超えたとして、その対応する仮説投票箱に、パターンの類似度値だけ投票を行う。ここでは、Ｇｓｉｍの示す類似度値を加算することとする。全ての組み合わせに関する全ての仮説情報に対して、投票を行う。

次に、投票値の多かったものを組み合わせから、順に得票値の高いものを各特徴点の検出結果として、その座標値を出力する（図７−７０９）。

これについては、ある閾値を設定し、その設定値以上の得票値を得たもののみを出力するなどの処理を行って良い。このとき全体のパターンの位置がどこにあるのかを計算し、出力としてよい（図７−７１０）。この場合は、物体の存在位置を示すＴＲｅｌの情報を組み合わせた結果とすればよい。

（３−３−２）仮説投票処理の説明
図８は、仮説統合部の処理フローチャートを示す。

図８のステップ８０１で、一つの仮説情報を受け取ると、その仮説情報で計算されるＴＲｅｌの位置に対応する仮説投票箱があるかどうかを調べる（図８のステップ８０２）。同じものがある場合は、その仮説投票箱の投票値に先に求めた類似度を加算し、投票値を更新する（図８のステップ８０３）。同じものがない場合は、結果となる座標が異なるため、別の仮説投票箱を用意し（図８のステップ８０４）、類似度を加算して更新を開始する。全ての仮説情報の投票が終了したかどうかを判定し（図８のステップ８０５）、終了していなければ、仮説情報の投票を繰り返す。

終了した場合、それぞれの仮説投票箱の投票値の中から、得票値の高いものを出力し、検出結果とする（図８のステップ８０６）。また、登録された物体に識別ラベルをつけておくことにより、検出された物体がなにであるかを求めることもできる。

［第２の実施形態］
第２の実施形態について説明する。

ドロネー三角形分割を用いることで、組み合わせ数の削減を行うことができるが、大きさが異なるような対象を複数検出する場合にはドロネー三角形分割の性質から近傍の三角形のみを生成するだけである。さらに精度を向上させるために、様々なスケールの三角形を生成することを考える。ここでは、複数の特徴点集合を作り、それらの作り方を変えることにより、様々なスケールの三角形分割を生成する。

（１）第１の方法
様々なスケールの三角形分割を生成する第１の方法について説明する。

まず、特徴点抽出部２により特徴点検出を行い、特徴点集合を作成する。各特徴点には、その特徴点抽出部２による評価値のようなものが存在する。例えば、特許文献１のＨａｒｒｉｓのコーナーディテクタの場合、そのコーナーの度合いを表す値や、特許文献２の分離度フィルタの場合には、その分離度を評価値とする。その評価値については、Ｌａｂｅｌに記載することとする。

次に、その評価値に対して、複数のいくつかの閾値を設定する。分離度の場合を例にとると、分離度の取りうる値は、０．００〜１．００であるため、閾値を、０．３３ずつに刻むとすると、０．６６，０．３３，０．００と３段階の閾値ができる。

これを先ほど求めた特徴点集合に対して、閾値以上のもののみを含む部分特徴点集合を作成する。このとき、閾値の高い方から順に、特徴点数の少ない部分特徴点集合ができる。この閾値を適宜変えることに包含関係をもつ３段階の特徴点集合ができる。この３つの特徴点集合それぞれに対してドロネー三角形分割を求めると、大きさの異なる三角形の集合が作成されることとなる。

このように多段階に生成された特徴点３点の集合を全て投票することにより、より安定した認識を行うことができる。全ての段階の全ての三角形の組み合わせの投票を行った後、統合処理を行ってもよいが、その各段階毎に統合処理を行ってもよい。

または、ある段階で行った後、候補領域となりうる場所に対して、さらに別の段階の処理を行うというＣｏａｒｓｅ−ｔｏ−ｆｉｎｅの処理を行っても良い。

（２）第２の方法
様々なスケールの三角形分割を生成する第２の方法について説明する。

第２の方法としては、特徴点検出のパラメータを変化させることで、多段階の三角形分割を作成できる。

図１０では、Ｈａｒｒｉｓのコーナーディテクタのパラメータを変化させることによって得られた４段階の特徴点集合の例を示す。顔画像に対して特徴点検出処理を行ったもので、下段が特徴点の検出結果を表し、上段にそれぞれのドロネー三角形分割の結果を示す。パラメータの変更により、大きさの異なる三角形ができていることがわかる。

この後の処理については、第１の方法と同様である。

［第３の実施形態］
第１、第２の実施形態の認識結果は、物体の位置、姿勢だけであったが、認識された物体の着目点の場所を求める方法について説明する。物体認識部１１に対して、次の機能を持つ着目点推定部を追加する。

例えば、着目点としては、図５−５０１を用いて説明すると、箱の角部であり、白丸印で示した点である。

（１）着目点推定部の動作
この着目点推定部の動作について説明する。

（１−１）モデルの着目点の登録
まず、モデルの着目点を登録する。モデルの着目点は、モデル登録の際に、特徴点とは異なる点として、ＦｅａＰｎｔに登録する。例えば、図５−５０１の例では、箱をモデルとして登録する場合に、画像の特徴点（図中の十字印）とは異なる箱の角の点が着目点（図中の白丸印）として登録される。

このＦｅａＰｎｔは、画像全体の矩形に対して、相対的な位置情報をそれぞれの点に対して保持する。図１１−１１０２のような、ローカルな座標系を用いて、それぞれの点を記述する。ここで、（ｐｘ１，ｐｘ１）（ｐｘ２，ｐｘ２）・・・がローカルな座標系におけるモデルの着目点の座標位置である。このローカルな座標系は全体の矩形に対して定義され、矩形の下の辺に対する座標をｘ軸、矩形の左側の辺に対する座標をｙ軸として、その位置が記述される。

（１−２）認識対象物の着目点の認識
次に認識対象物の着目点の認識について説明する。

図７−７０７で行われた仮説の投票の結果、認識結果となった仮説投票箱には、複数の仮説（ｋ個）が投票されている。

図１１−１１０１は、箱の検出の様子を図に表したものであって、図中の各点線の矩形ＴＲｅｌが投票された仮説１つに相当し、ある認識対象物（箱）が検出されるためには、同じ位置、姿勢に複数の矩形が描かれることとなる。

図１１−１１０２は、モデルの着目点ＦｅａＰｎｔを図に表したものであって、図中の矩形Ｇｐ内に６個ある。

図１１−１１０３は、認識対象物の着目点ＴＦｅａＰｎｔを図に表したものであって、図中の矩形ＴＲｅｌ内に６個ある。但し、仮説Ｈｉが複数あるため、仮説Ｈｉ毎に矩形ＴＲｅｌと認識対象物の着目点ＴＦｅａＰｎｔがあるため、ぶれて記載されている。

今、その一つの仮説をＨｉ（１＝＜ｉ＝＜ｋ）とする。

各仮説Ｈｉには、数１０にあるように、モデルの着目点の座標位置ＦｅａＰｎｔが記述されており、投票される情報に含まれている。この投票されている各仮説Ｈｉにおいて、入力画像中の認識対象物の着目点の位置の求め方について説明する。

（１−２−１）仮説毎の認識対象物の着目点の認識
この認識対象物の着目点は、仮説Ｈｉ毎に求める。

図１１−１１０２の各モデルに対しての座標位置と図１１−１１０３の入力画像中の認識対象物の座標位置の対応を考える。認識対象物の着目点位置ＴＦｅａＰｎｔは、ＴＲｅｌで求まった矩形、すなわち、ここでは回転した矩形に対する相対的な位置として計算される。

各モデルの全体領域を表す矩形Ｒｅｌを用いて数９のように入力画像上での矩形ＴＲｅｌが計算される。これにしたがってＦｅａＰｎｔから実際の入力画像上での認識対象物の着目点の位置ＴＦｅａＰｎｔを、数１１に示す計算式で計算される。

「ＦｕｎｃＦｅａ」は、入力画像上での着目点の位置を計算する関数である。

また、数１１に用いられる符号について再度説明しておく。

「ＴＦｅａＰｎｔ」は、上記したように、入力画像上での認識対象物の着目点の位置である。

「ＦｅａＰｎｔ」は、上記したように、画像上でのモデルの着目点の位置である。

「Ｒｅｌ」は、上記したように、モデルを囲む矩形の領域Ｇｐを表現した点集合を相対的に表現したもので、検出結果の場所を示すためや再度その領域を抽出することなどに利用される。具体例としては、図５−５０５のような矩形の領域Ｇｐを表すための頂点集合の４点を、図５−５０６のように変換した平行四辺形の４点の座標位置で記述する。

「ＴＲｅｌ」は、上記したように、選択した３点の特徴点にしたがって、相対的な位置情報であるＲｅｌを変換した位置情報であり、画像中での認識対象物の存在領域を表している。

上記のようにして、ＴＲｅｌと認識対象物の着目点位置ＴＦｅａＰｎｔとの関係、Ｒｅｌとモデルの着目点位置ＦｅａＰｎｔとの関係、ＴＲｅｌとＲｅｌとの関係に基づき、ＦｕｎｃＦｅａを用いて、仮説Ｈｉ毎にＴＲｅｌとＦｅａＰｎｔから認識対象物の着目点位置ＴＦｅａＰｎｔが計算できる。

（１−２−２）複数の仮説における認識対象物の着目点の統合
一般には、入力画像とは異なる位置、姿勢の物体が存在し、また画像のノイズや量子化誤差の影響から、通常、複数の仮説Ｈｉは、実際には、ずれた位置にも検出される。このように部分的なパターンのマッチングを集積して認識する方法では、同じような位置に多数投票されることとなる。図１１−１１０３は、その様子を図示したものである。さらに図１１−１１０３では、それぞれの仮説Ｈｉ毎の、ＴＦｅａＰｎｔを、検出された位置にあわせて計算した、相対的な着目点列の位置を図示している。

このように同じ着目点は、ほぼ同じ場所に位置しているため、着目点のおおまかな位置を求めることができる。よって、これらの多数の仮説を統計的に統合することで、それぞれの着目点のもっともらしい位置を推定することができる。

推定に用いる方法としては、例えば次のようなものがある。

第１の推定方法は、全ての着目点の生起確率が同じだと仮定して、全ての各着目点位置の平均値を用いて推定値とする。

例えば、各ｊ番目の仮説のＴＦｅａＰｎｔのｉ番目の位置の着目点推定位置Ｅｉは、数１２で計算される。

第２の推定方法は、それぞれの投票の際のマッチングの類似度値を信頼度とした重み付平均値を用いる。

第３の推定方法は、大きな外れ値を外すためにＬｅａｓｔ Ｍｅｄｉａｎ ｏｆ Ｓｑｕａｒｅｓ（ＬＭｅｄＳ）基準に基づいたロバスト推定などを用いることもできる。

この推定方法については、上述したものに限定するものではなく、他の方法を用いてよい。

図１１−１１０４は、統合して得られた着目点の推定位置を黒丸で表している。

（２）応用例
このメカニズムにより次のことも可能となる。

図１２は、顔の部品検出を行う問題を考えた場合、それぞれ、目、鼻孔、口端の６点を着目点とする画像を表している。

モデルとして、図１２−１２０１のＡさんのモデルと、図１２−１２０２のＢさんのモデルだけが登録されているとする。

ここで、認識対象として全く異なるＣさんの画像を入力する。それぞれ図１２−１２０１と図１２−１２０２のモデルが入力画像と類似しているとした場合、この２つの着目点の位置を統合し推定値を求めることで、Ｃさんの着目点の位置を推定できる。

このように、登録されていない認識対象に対しても、類似した別のモデルを用いて、着目点の位置を推定することが可能となる。

また、画像特徴点と着目点が必ずしも対応しておらず、相対的な位置の集積によって着目点位置を計算できるということは、通常の特徴点検出によって見つけにくいような着目点を推定することができることを示唆している。例えば、人間の頬の位置を画像認識によって見つけようとした場合を考える。一般に人間の頬には、テクスチャが少ないため、特徴点検出やパターンマッチングによって検出することは難しい。しかし、このような方法で、その周辺にある特徴点（例えば、目、鼻、口など）とその領域に対する着目点の位置を記述しておくことで、頬の位置を別の特徴点位置の検出から導くことができる。このように通常見つけにくい対象に対しての位置を求める方法としては有効な方法となる。

（３）着目点位置が正しいか否かの判断
先に述べたように、着目点位置は、一般には特徴点位置と異なる場所に存在していることである。もし、着目点位置と特徴点位置が同一であると制限できるならば、各特徴点（着目点）位置でのパターンマッチングの類似度を信頼度として利用できる。しかし、上記推定方法では、推定された着目点位置が正しいかどうかは判定していない。

そこで、別途、推定された着目点位置付近のパターンを切り出し、登録されているパターンとのパターンマッチングによって類似度を求めて、各着目点位置が正しいかどうかを判定するようにしてもよい。

［変更例］
本発明は上記各実施形態に限らず、その主旨を逸脱しない限り種々に変更することができる。また、本発明は、その主旨を逸脱しない限り、異なる実施形態に記載された事項を組み合わせた内容、及び、異なる実施形態に記載された事項に置換した内容をも含む。

例えば、三角形分割については、ドロネー三角形分割ではなく、別の三角形分割を求める方法を用いても良い。一般には、メッシュを作成する手順において、また一般にドロネー分割は互いに重なることがなく、互いに素な分割となっているが、場合によっては、互いに素な分割でなくてもよい。

また、高次ボロノイ分割の双対グラフであるｎ次ドロネー三角形分割を用いてもよい。この場合、互いに三角形が重なりをもつこととなるが、本実施形態では、３点の組み合わせだけを対象とするため、この問題は発生しない。

また、ｎ次のドロネー分割は、ｎ番目に近い点との連結を考慮しているため、より複雑な探索が可能となる。

また、登録のみ、もしくは、認識のみにドロネー三角形分割を利用し、他方では特許文献１と同様に、全探索や基底ベクトルの長さに対する制限つきの探索などを行うというのでもよい。また、メモリ容量の範囲内であれば、その逆に登録時には全部の組み合わせをいれておき、認識時にドロネー三角形分割を利用するのでもよい。

本発明の第１の実施形態を示す物体認識装置の構成図である。 検出対象（箱）に特徴点検出処理やドロネー分割を求めた概念図である。 モデルの登録時のフローチャートである。 モデルの登録方法である。 部分パターン情報の登録情報についての図である。 検出時のフローチャート（仮説情報の生成）である。 検出方法の説明図である。 統合のフローチャートである。 特徴点３点の組み合わせ数とドロネー三角形分割の例である。 段階的に三角形分割を求めるための説明図である。 着目点の推定に関する説明図である。 顔の着目点の推定に関する説明図である。

符号の説明

１ 画像入力部
２ 特徴点抽出部
３ 三角形分割生成部
４ 特徴点選択部
５ 基底計算部
６ 部分パターン構成部
７ インデックス計算部
８ テーブル登録部
９ パターン類似度計算部
１０ 仮説情報生成部
１１ 物体認識部

Claims (13)

1. 認識対象物が撮影された画像と、予め登録したモデルとを比較して、前記認識対象物の認識を行うパターン認識装置であって、
   前記認識対象物が撮影された画像を入力する画像入力手段と、
   前記画像中から複数の特徴点を抽出する特徴点抽出手段と、
   前記複数の特徴点の全てを周上、または、内部領域に包含する凸多角形を形成し、当該凸多角形の頂点、または、前記複数の特徴点を頂点とする複数の三角形の領域に分割する三角形分割生成手段と、
   前記各三角形の各頂点にある特徴点の組み合わせを複数選択する特徴点選択手段と、
   前記複数選択された３点の特徴点の組み合わせから、これら特徴点の位置や位置関係を表す基底をそれぞれ計算する基底計算手段と、
   前記各基底に対応する前記認識対象物の部分パターンを前記画像からそれぞれ抽出する部分パターン抽出手段と、
   幾何学的変換に関して不変なパラメータを少なくとも含むインデックスパラメータに基づいて分割された複数の登録場所から構成され、かつ、前記モデルの部分パターンが、その部分パターンに関するインデックスパラメータに対応した登録場所に登録されたテーブルを記憶するテーブル記憶手段と、
   前記認識対象物の部分パターンに対応するインデックスパラメータに基づいて、前記テーブルの登録場所を決定するインデックス検索手段と、
   前記テーブルの登録場所に登録された前記モデルの部分パターンと、前記認識対象物の部分パターンの類似度とを判定するパターン類似度計算手段と、
   を有することを特徴とするパターン認識装置。
2. 前記テーブルへ登録しようとするモデルのモデル画像を入力する画像入力手段と、
   前記モデル画像中から複数の特徴点を抽出する特徴点抽出手段と、
   前記複数の特徴点の全てを周上、または、内部領域に包含する凸多角形を形成し、当該凸多角形の頂点、または、前記複数の特徴点を頂点とする複数の三角形の領域に分割する三角形分割生成手段と、
   前記各三角形の各頂点にある特徴点の組み合わせを複数選択する特徴点選択手段と、
   前記複数選択された３点の特徴点の組み合わせから、これら特徴点の位置や位置関係を表す基底をそれぞれ計算する基底計算手段と、
   前記モデルの部分パターンに対応するインデックスパラメータをインデックスとして、前記テーブルの登録場所を決定するインデックス決定手段と、
   前記決定されたテーブルの登録場所へ前記モデルの部分パターンを登録するテーブル登録手段と、
   を有することを特徴とする請求項１記載のパターン認識装置。
3. 前記認識対象物が画像中のどの位置に存在かを表す仮説情報を前記両部分パターンの類似度に基づいて生成し、その生成した仮説情報を仮説空間にそれぞれ投票する仮説情報生成手段と、
   前記各仮説空間に投票された仮説情報の投票数に基づいて、前記認識対象物の識別、位置、または、姿勢を決定する物体認識手段と、
   を有することを特徴とする請求項１記載のパターン認識装置。
4. 前記仮説情報生成手段は、
   前記テーブルの検索場所における前記認識対象物の存在位置に属する前記両部分パターンの類似度を含む情報を仮説情報として、前記仮説空間の中の前記各存在位置毎に設けられた仮説投票箱にそれぞれ投票することにより、前記各存在位置毎の投票数を求め、
   前記物体認識手段は、
   前記仮説投票箱における投票数が閾値を越えた存在位置を前記認識対象物に対応する存在位置であるとする
   ことを特徴とする請求項３記載のパターン認識装置。
5. 前記三角形分割生成手段において、ドロネー三角形分割により三角形を求める
   ことを特徴とする請求項１のパターン認識装置。
6. 前記三角形分割生成手段は、前記複数の特徴点の部分集合を求め、前記部分集合に対して三角形分割をそれぞれ求める
   ことを特徴とする請求項１から４の中で少なくとも一項に記載のパターン認識装置。
7. 前記特徴点抽出手段は、前記特徴点抽出のパラメータを変化させて、複数の特徴点を作成し、
   前記三角形分割生成手段は、前記複数の特徴点の部分集合を求め、前記部分集合に対して三角形分割をそれぞれ求める
   ことを特徴とする請求項１から４の中で少なくとも一項に記載のパターン認識装置。
8. 前記物体認識手段は、前記認識対象物の着目点の位置を、前記テーブルに予め記憶された前記モデルの各着目点の相対位置情報に基づいて求める
   ことを特徴とする請求項３に記載のパターン認識装置。
9. 前記モデルの着目点は特徴点以外の点であって位置情報から構成されている
   ことを特徴とする請求項８に記載のパターン認識装置。
10. 前記着目点の位置情報が前記仮説情報に含まれ、
    前記仮説情報毎に前記認識対象物の着目点の位置を求める
    ことを特徴とする請求項８に記載のパターン認識装置。
11. 前記仮説情報毎に求められた前記認識対象物の着目点の位置を統計的に統合して一つの前記認識対象物の着目点を求める
    ことを特徴とする請求項８に記載のパターン認識装置。
12. 認識対象物が撮影された画像と、予め登録したモデルとを比較して、前記認識対象物の認識を行うパターン認識方法であって、
    画像入力部が、前記認識対象物が撮影された画像を入力する画像入力ステップと、
    特徴点抽出部が、前記画像中から複数の特徴点を抽出する特徴点抽出ステップと、
    三角形分割生成部が、前記複数の特徴点の全てを周上、または、内部領域に包含する凸多角形を形成し、当該凸多角形の頂点、または、前記複数の特徴点を頂点とする複数の三角形の領域に分割する三角形分割生成ステップと、
    特徴点選択部が、前記各三角形の各頂点にある特徴点の組み合わせを複数選択する特徴点選択ステップと、
    基底計算部が、前記複数選択された３点の特徴点の組み合わせから、これら特徴点の位置や位置関係を表す基底をそれぞれ計算する基底計算ステップと、
    部分パターン抽出部が、前記各基底に対応する前記認識対象物の部分パターンを前記画像からそれぞれ抽出する部分パターン抽出ステップと、
    テーブル登録部が、幾何学的変換に関して不変なパラメータを少なくとも含むインデックスパラメータに基づいて分割された複数の登録場所から構成され、かつ、前記モデルの部分パターンが、その部分パターンに関するインデックスパラメータに対応した登録場所に登録されたテーブルを記憶するテーブル記憶ステップと、
    インデックス計算部が、前記認識対象物の部分パターンに対応するインデックスパラメータに基づいて、前記テーブルの登録場所を決定するインデックス検索ステップと、
    パターン類似度計算部が、前記テーブルの登録場所に登録された前記モデルの部分パターンと、前記認識対象物の部分パターンの類似度とを判定するパターン類似度計算ステップと、
    を有することを特徴とするパターン認識方法。
13. 認識対象物が撮影された画像と、予め登録したモデルとを比較して、前記認識対象物の認識を行うパターン認識方法をコンピュータに実現させるためのパターン認識プログラムであって、
    前記認識対象物が撮影された画像を入力する画像入力機能と、
    前記画像中から複数の特徴点を抽出する特徴点抽出機能と、
    前記複数の特徴点の全てを周上、または、内部領域に包含する凸多角形を形成し、当該凸多角形の頂点、または、前記複数の特徴点を頂点とする複数の三角形の領域に分割する三角形分割生成機能と、
    前記各三角形の各頂点にある特徴点の組み合わせを複数選択する特徴点選択機能と、
    前記複数選択された３点の特徴点の組み合わせから、これら特徴点の位置や位置関係を表す基底をそれぞれ計算する基底計算機能と、
    前記各基底に対応する前記認識対象物の部分パターンを前記画像からそれぞれ抽出する部分パターン抽出機能と、
    幾何学的変換に関して不変なパラメータを少なくとも含むインデックスパラメータに基づいて分割された複数の登録場所から構成され、かつ、前記モデルの部分パターンが、その部分パターンに関するインデックスパラメータに対応した登録場所に登録されたテーブルを記憶するテーブル記憶機能と、
    前記認識対象物の部分パターンに対応するインデックスパラメータに基づいて、前記テーブルの登録場所を決定するインデックス検索機能と、
    前記テーブルの登録場所に登録された前記モデルの部分パターンと、前記認識対象物の部分パターンの類似度とを判定するパターン類似度計算機能と、
    をコンピュータに実現させるためのパターン認識プログラム。

Images