JP3776340B2 - 対象物認識システム及び方法 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、一般的に機械視覚システムに関し、詳細には、部分オクルージョン（ｏｃｃｌｕｓｉｏｎ）、クラッタ、又は非線形コントラスト変化の下での対象物の視覚認識に関する。
【０００２】
【従来の技術】
対象物の認識において、そして特に、多くの機械視覚タスクにおいて、人は、イメージの中のユーザ定義モデル対象物を認識することに関心がある。イメージの中の対象物は、ある一定クラスの幾何学的変換の任意変換を受けてしまっている場合がある。変換のクラスが平行移動のクラスである場合、人は、イメージ中のモデルの位置を得ることに関心がある。平行移動のクラスは、通常、モデルが常にイメージの中で同じ回転及び大きさで生じることを保証することができる場合用いられる。それは、例えば、モデルがｘ−ｙステージ上に固定角度で取り付けられ、そしてカメラがそのステージに対して垂直の固定位置に取り付けられるからである。変換のクラスが固定変換のクラスである場合、更にイメージ中の対象物の回転が望まれる。このクラスの変換は、例えば、カメラがステージに対して垂直に取り付けられるが、しかし対象物の角度が固定状態に保つことができない場合用いることができる。変換のクラスが類似の変換のクラスである場合、更にイメージ中の対象物のサイズが変わり得る。このクラスの変換は、例えば、カメラと対象物との距離を固定状態に保つことができない場合、又は対象物自体がサイズの変化を受け得る場合、生じることができる。対象物に対するカメラの位置も３Ｄ回転も固定状態に保つことができない場合、対象物は、イメージの中で一般的透視変換を受けるであろう。カメラの内部向きが未知である場合、２つの面（即ち、対象物の表面及びイメージ面）間の透視投影は、同次座標における３×３マトリックスにより表すことができる。即ち、
【０００３】
【数１】

マトリックス及びベクトルは、全目盛係数まで決定されるのみである（Ｈａｒｔｌｅｙ及びＺｉｓｓｅｒｍａｎｎ（２０００）［Ｒｉｃｈａｒｄ Ｈａｒｔｌｅｙ及びＡｎｄｒｅｗ Ｚｉｓｓｅｒｍａｎｎ著「コンピュータ・ビジョンにおける多重ビュー・ジオメトリ（Ｍｕｌｔｉｐｌｅ Ｖｉｅｗ Ｇｅｏｍｅｔｒｙｉｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ）」ケンブリッジ大学出版発行、２０００年］１．１−１．４章参照）。従って、対象物の姿勢（ポーズ）を決定するマトリックスは、８の自由度を有する。カメラの内部向きが既知である場合、これらの８の自由度は、カメラに対する対象物の姿勢の６の自由度（平行移動に対して３でそして回転に対して３）に低減する。
【０００４】
多くの場合、このタイプの変換は、一般的２Ｄアフィン変換、即ち出力点（ｘ′，ｙ′）^Tが入力点（ｘ，ｙ）^Tから次の公式により得られる変換により近似される。
【０００５】
【数２】

一般的アフィン変換は、例えば、次の幾何学的直観的変換、即ち、異なる目盛係数ｓ_x及びｓ_yによる元のｘ及びｙのスケーリング、ｘ軸に対するｙ軸のスキュー（斜め）変換、即ちｘ軸が固定されたままでｙ軸の角度θの回転、両方の軸の角度φの回転、そして最後にベクトル（ｔ_x，ｔ_y）^Tによる平行移動に分解されることができる。従って、任意のアフィン変換は次のように書くことができる。
【０００６】
【数３】

図１は一般的アフィン変換を図式的に示す。ここで、辺の長さ１の正方形が、平行四辺形に変換される。相似変換は、スキュー角θが０であり且つ両方の目盛係数が同一である、即ち、ｓ_x＝ｓ_y＝ｓであるアフィン変換の特別のケースである。同様に、固定変換は、目盛係数が１、即ちｓ＝１である相似変換の特別のケースである。最後に、平行移動は、φ＝０である固定変換の特別のケースである。幾何学的変換のクラスの関連パラメータは、イメージ中の対象物の姿勢と称されるであろう。例えば、固定変換に対して、姿勢は、回転角φ及び平行移動ベクトル（ｔ_x，ｔ_y）^Tから成る。従って、対象物認識は、イメージ中のモデルの全インスタンス（ｉｎｓｔａｎｃｅｓ）の姿勢を決定することである。
【０００７】
幾つかの方法が、イメージの中の対象物を認識するため当該技術において提案されてきた。それらの大部分は、モデルが追加のクラッタ対象物により遮られ又は劣化される場合そのモデルがイメージの中に見つけられないという制約を欠点として持っている。更に、既存の方法の大部分は、イメージが非線形コントラスト変化を、例えば照明の変化に起因して示す場合モデルを検出しない。
【０００８】
全ての既知の対象物認識方法は、モデルが発生される時点でメモリの中のモデルの内部表示を発生する。イメージの中のモデルを認識するため、大部分の方法においては、モデルは、対象物の姿勢に対する選定されたクラスの変換の全ての許容可能な自由度を用いてイメージと体系的に比較される（例えば、Ｂｏｒｇｅｆｏｒｓ（１９８８）［Ｇｕｎｉｌｌａ Ｂｏｒｇｅｆｏｒｓ著「階層的面取り部整合：パラメトリック・エッジ整合アルゴリズム（Ｈｉｅｒａｒｃｈｉｃａｌｃｈａｍｆｅｒ ｍａｔｃｈｉｎｇ：Ａ ｐａｒａｍｅｔｒｉｃ ｅｄｇｅ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ）」パターン解析及び機械知能についてのＩＥＥＥトランザクション（ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ）１０（６）：８４９−８６５頁、１９８８年１１月発行］、Ｂｒｏｗｎ（１９９２）［Ｌｉｓａ Ｇｏｔｔｅｎｆｅｌｄ Ｂｒｏｗｎ著「イメージ位置合わせ技術の調査（Ａ Ｓｕｒｖｅｙ ｏｆ ｉｍａｇｅ ｒｅｇｉｓｔｒａｔｉｏｎ ｔｅｃｈｎｉｑｕｅｓ）」ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ、２４（４）：３２５−３７６頁、１９９２年１２月発行］、及びＲｕｃｋｌｉｄｇｅ（１９９７）［Ｗｉｌｌｉａｍ Ｊ．Ｒｕｃｋｌｉｄｇｅ著「ハウスドルフ距離を用いた対象物の効率的配置（Ｅｆｆｉｃｉｅｎｔｌｙ ｌｏｃａｔｉｎｇ ｏｂｊｅｃｔｓ ｕｓｉｎｇ ｔｈｅ Ｈａｕｓｄｏｒｆｆ ｄｉｓｔａｎｃｅ）」Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ、２４（３）：２５１−２７０頁、１９９７年発行］参照）。姿勢のパラメータの各組に対して、いかにうまくモデルが考慮中の姿勢でイメージに対して適合するかの尺度を与える整合メトリック（ｍａｔｃｈ ｍｅｔｒｉｃ）が計算される。許容可能な変換の空間に対する探索を加速するため、通常イメージ・ピラミッドがモデルとイメージの両方について用いられて、調査される必要があるデータ量を低減する（例えば、Ｔａｎｉｍｏｔｏ（１９８１）［Ｓｔｅｖｅｎ Ｌ．Ｔａｎｉｍｏｔｏ著「ピラミッドにおけるテンプレート整合（Ｔｅｍｐｌａｔｅ ｍａｔｃｈｉｎｇ ｉｎ ｐｙｒａｍｉｄｓ）」Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ａｎｄ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ、１６：３５６−３６９頁、１９８１年発行］、Ｂｏｒｇｅｆｏｒｓ（１９８８）又はＢｒｏｗｎ（１９９２）参照）。
【０００９】
最も単純なクラスの対象物認識方法は、モデル及びイメージそれ自体のグレー値に基づいており、そして正規化された相互相関を整合メトリックとして用いる（例えば、米国特許Ｎｏ．４９７２３５９、米国特許Ｎｏ．５２２２１５５、米国特許Ｎｏ．５５８３９５４、米国特許Ｎｏ．５９４３４４２、米国特許Ｎｏ．６０８８４８３及びＢｒｏｗｎ（１９９２）参照）。正規化された相互相関は、それが線形輝度変化に対して不変であり、即ち、対象物が線形照明変化を受けた場合その対象物を認識することができるという利点を有する。しかしながら、正規化された相互相関は、幾つかの明らかな欠点を有する。第１に、計算は費用がかかり、それはこのメトリックに基づく方法を非常に遅くさせる。これは、さもなければたとえイメージ・ピラミッドを用いたとしても探索がリアルタイム用途にとっては時間が余りにかかり過ぎる理由だけで結局変換のクラスが通常平行移動のクラスとして選定されることになる。第２に、メトリックは、対象物のオクルージョン（ｏｃｃｌｕｓｉｏｎ）に対してロバストでない、即ち、対象物は、たとえ対象物のほんの小さい部分がイメージの中に遮られた場合でも通常見つけられないであろう。第３に、メトリックは、クラッタに対してロバストでない、即ち、対象物は、対象物についての外乱又は閉鎖がある場合通常見つけられないであろう。
【００１０】
別のクラスのアルゴリズムはまた、モデル及びイメージそれ自体のグレー値に基づいているが、しかし二乗グレー値差の和又はグレー値差の絶対値の和のいずれかを整合メトリックとして用いる（例えば、米国特許Ｎｏ．５５４８３２６及びＢｒｏｗｎ（１９９２）参照）。このメトリックは、線形輝度変化に対して不変にすることができる（Ｌａｉ及びＦａｎｇ（１９９９）［Ｓｈａｎｇ−Ｈｏｎｇ Ｌａｉ及びＭｉｎｇ Ｆａｎｇ著「自動化された視覚検査のための正確で速いパターン局所化アルゴリズム（Ａｃｃｕｒａｔｅ ａｎｄ ｆａｓｔ ｐａｔｔｅｒｎ ｌｏｃａｌｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｕｔｏｍａｔｅｄ ｖｉｓｕａｌ ｉｎｓｐｅｃｔｉｏｎ）」Ｒｅａｌ−Ｔｉｍｅ Ｉｍａｇｉｎｇ、５：３−１４頁、１９９９年発行］）。二乗差の和又は絶対値差の和を計算するのは正規化された相互相関を計算する程費用がかかるわけではないので、通常一層大きなクラスの変換、例えば固定変換が許される。しかしながら、このメトリックは、相関ベースの方法と同じ欠点を有し、即ち、それは、オクルージョン又はクラッタに対してロバストでない。
【００１１】
より複雑なクラスの対象物認識方法は、モデル及び対象物それ自体のグレー値を用いないが、しかし整合のため対象物のエッジを用いる。モデルの生成の間に、エッジ抽出が、モデル・イメージ及びその導出されたイメージ・ピラミッドについて実行される（例えば、Ｂｏｒｇｅｆｏｒｓ（１９８８）、Ｒｕｃｋｌｉｄｇｅ（１９９７）及び米国特許Ｎｏ．６００５９７８参照）。エッジ抽出は、グレー・レベル・イメージをバイナリ・イメージに変換するプロセスであり、そこにおいてエッジに対応する点のみが値１にセットされ、他方全ての他のピクセルは値０を受け取り、即ち、イメージは実際にエッジ領域の中にセグメント化される。勿論、セグメント化されたエッジ領域は、バイナリ・イメージとして格納される必要はないが、しかしまた他の手段、例えばランレングス符号化により格納されることができる。通常、エッジ・ピクセルは、勾配の大きさが勾配の方向で最大であるイメージの中のピクセルとして定義される。エッジ抽出はまた、その中でモデルが認識されることになるイメージ及びその導出されたイメージ・ピラミッドについて実行される。次いで、種々の整合メトリックを用いて、モデルをイメージと比較することができる。１つのクラスの整合メトリックは、考慮中の姿勢の下でのモデル・エッジのイメージ・エッジに対する距離を測定することに基づいている。エッジの距離の計算を容易にするため、距離変換がイメージ・ピラミッドについて計算される。Ｂｏｒｇｅｆｏｒｓ（１９８８）における整合メトリックは、モデル・エッジとイメージエッジとの平均距離を計算する。この整合メトリックは、クラッタ・エッジがモデル内で生じないで、従って、モデルからイメージ・エッジまでの平均距離のみを低減することができるので、クラッタ・エッジに対してロバストである。この整合メトリックの欠点は、モデルの一部のエッジがイメージの中で欠落している場合最も近いエッジに対する距離が著しく増大するので、その整合メトリックがオクルージョンに対してロバストでないことである。Ｒｕｃｋｌｉｄｇｅ（１９９７）における整合メトリックは、イメージ・エッジに対するモデル・エッジのｋ番目に大きな距離を計算することによりこの欠点を取り除こうとしている。モデルがｎ個の点を含む場合、メトリックは、１００＊ｋ／ｎ％オクルージョンに対してロバストである。別のクラスの整合メトリックは、単純な２進相関に基づいていて、即ち、整合メトリックは全ての点の平均であり、そこにおいて、現在の姿勢の下でのモデル及びイメージの両方がエッジ・ピクセル・セットを有する（例えば、米国特許Ｎｏ．６００５９７８及び米国特許Ｎｏ．６１１１９８４参照）。モデルの潜在的インスタンスの探索を加速するため、米国特許Ｎｏ．６００５９７８においては、一般化されたハフ（Ｈｏｕｇｈ）変換（Ｂａｌｌａｒｄ（１９８１）［Ｄ．Ｈ．Ｂａｌｌａｒｄ「任意の形状を検出するためのハフ変換の一般化（Ｇｅｎｅｒａｌｉｚｉｎｇ ｔｈｅ Ｈｏｕｇｈ ｔｒａｎｓｆｏｒｍ ｔｏ ｄｅｔｅｃｔ ａｒｂｉｔｒａｒｙ ｓｈａｐｅｓ）」Ｐａｔｔｅｒｎ Ｒｅｃｏｇｉｔｉｏｎ、１３（２）：１１１−１２２頁、１９８１年発行］）が用いられる。この整合メトリックは、モデルの中のエッジとイメージの中のエッジとの整列が考慮中の姿勢の下で整合メトリックの正しい値を生じるため非常に良好であることを必要とするという欠点を有する。複雑なスキームが、イメージの中のエッジをより広くして正しい整合メトリックを得るため用いられる。最後に、エッジは時に、相関ベースのアプローチに使用のため関連の点を定義するため用いられる（米国特許Ｎｏ．６０２３５３０及び米国特許Ｎｏ．６１５４５６７参照）。これらのアプローチは、整合メトリックが同じ又は非常に類似しているので、前述の相関ベースのスキームと同じ欠点を有することは明らかである。これら全ての整合メトリックは、それらがエッジの方向を考慮していない欠点を有する。米国特許Ｎｏ．６００５９７８においては、エッジ方向は、一般化されたハフ変換の使用を通してその方法に入るが、しかし整合メトリックにおいて無視されている。しかしながら、エッジ方向情報を無視することは、結局イメージにおけるモデルの多くの間違った決定的なインスタンス、即ち、モデルの真のインスタンスでない見つけられたモデルにつながることが周知である（Ｏｌｓｏｎ及びＨｕｔｔｅｎｌｏｃｈｅｒ（１９９７）［Ｃｌａｒｋ Ｆ．Ｏｌｓｏｎ及びＤａｎｉｅｌ Ｐ．Ｈｕｔｔｅｎｌｏｃｈｅｒ著「方向付けされたエッジ・ピクセルを整合させることによる自動目標認識（Ａｕｔｏｍａｔｉｃ ｔａｒｇｅｔ ｒｅｃｏｇｉｎｉｔｏｎ ｂｙ ｍａｔｃｈｉｎｇ ｏｒｉｅｎｔｅｄ ｅｄｇｅ ｐｉｘｅｌｓ）」、イメージ処理についてのＩＥＥＥトランザクション（ＩＥＥＥ Ｔｒａｎｓｓａｃｔｉｏｎ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ）６（１）：１０３−１１３頁、１９９７年１月発行］。この理由のため、一部のアプローチは、エッジ方向情報を整合メトリックの中に組み込む（例えば、米国特許Ｎｏ．５５５０９３３、米国特許Ｎｏ．５６３１９８１、米国特許Ｎｏ．６１５４５６６、及びＨａｓｈｉｍｏｔｏ他（１９９２）［Ｍａｎａｂｕ Ｈａｓｈｉｍｏｔｏ、Ｋａｚｕｈｉｋｏ Ｓｕｍｉ、Ｙｏｓｈｉｋａｚｕ Ｓａｋａｕｅ及びＳｈｉｎｊｉｒｏ Ｋａｗａｔｏ著「輪郭点の情報を用いた高速テンプレート整合アルゴリズム（Ｈｉｇｈ−Ｓｐｅｅｄ Ｔｅｍｐｌａｔｅ Ｍａｔｃｈｉｎｇ ＡｌｇｏｒｉｔｈｍｓＵｓｉｎｇ Ｉｎｆｏｍａｔｉｏｎ ｏｆ Ｃｏｎｔｏｕｒ Ｐｏｉｎｔｓ）」、システム及びコンピュータ（日本）２３（９）：７８−８７頁、１９９２年発行］参照）。しかしながら、これらのアプローチは、（中止させるのに十分な程実行時間を大きくする）探索を加速するためイメージ・ピラミッドを用いてなく、モデルの平行移動を計算するだけである。前述の全てのアプローチにおいては、イメージ自体が２値化されるので、整合メトリックは、狭い範囲の照明変化に対してのみ不変である。イメージ・コントラストが低下される場合、徐々に少ないエッジ点がセグメント化され、それは、徐々に大きいオクルージョンと同じ効果を有する。
【００１２】
【発明が解決しようとする課題】
対象物認識のための現状技術の方法は幾つかの欠点を持つことは明らかである。どのアプローチもオクルージョン、クラッタ及び非線形なコントラストの変化に対して同時にロバストでない。更に、多くの場合、計算的に費用がかかる事前処理オペレーション、例えば、距離変換又は一般化されたハフ変換は、対象物認識を容易にするため実行される必要がある。多くの応用において、対象物認識ステップは、前述のタイプの変化に対してロバストであることが必要である。例えば、印刷品質検査において、モデル・イメージは、例えば、ロゴの理想的プリントである。検査においては、人は、現在のプリントが理想的なプリントからはずれているか否かを決定することに関心がある。そうするため、イメージの中のプリントは、（通常固定変換により）モデルと整合されねばならない。対象物認識（即ち、プリントの姿勢の決定）は、そのキャラクタ又はパーツを欠落していること（オクルージョン）及びプリントの中の余分なインク（クラッタ）に対してロバストでなければならないことは明らかである。照明が視野全体にわたり一定に保つことができない場合、対象物認識はまた、非線形な照明変化に対してロバストでなければならない。
【００１３】
従って、本発明の目的は、オクルージョン不変及びクラッタ不変の対象物認識のための改善された視覚的認識システム及び方法を提供することにある。
本発明の別の目的は、オクルージョン不変、クラッタ不変及び照明不変の対象物認識のための視覚的認識システム及び方法を提供することにある。
【００１４】
【課題を解決するための手段】
これらの目的は特許請求の範囲の特徴により達成される。本発明は、オクルージョン、クラッタ及び非線形のコントラスト変化に対してロバストである対象物認識のためのシステム及び方法を提供する。
【００１５】
認識されるべき対象物のモデルは対応する方向ベクトルを持つ複数の点から成り、それらは標準イメージ事前処理アルゴリズム、例えばライン又はエッジ検出方法により得ることができる。モデルの生成時に、モデルは、モデルを曲げ得る幾何学的変換のクラスからの複数の変換、例えば固定変換によりモデル・イメージを変換することによりメモリに格納される。イメージの中のモデルを認識するため、モデルの生成時に用いられた同じ事前処理オペレーションが、その中にモデルを見つけることになるイメージに適用される。従って、例えば、ライン検出がモデルを構成するため用いられた場合、ライン・フィルタリングが考慮中のイメージについて用いられる。対象物は、イメージの中のモデルの全てのあり得る変換に対して整合メトリックを計算することにより認識される。整合メトリックは、モデル及びイメージの幾何学的情報、即ちモデル及びイメージの中の点の位置及び方向を考慮する。整合メトリックは、例えば、（事前計算された）変換されたモデルのうちの１つと事前処理されたイメージとのドット積の和であり得て、又は代替実施形態において、（事前計算された）変換されたモデルのうちの１つと事前処理されたイメージとの正規化ドット積の和であり得る。正規化されてないドット積は幾何学的情報のみに依拠するので、モデル・イメージと、その中にモデルが見つけられことになるイメージとをセグメント化（２値化）することが必要がない。これは、本方法をオクルージョン及びクラッタに対してロバストにする。正規化されたドット積が整合メトリックとして用いられる場合、モデル・イメージをセグメント化して、方向情報が信頼できるそれらのポイントを得ることが好ましい。再び、その中にモデルが見つけられることとなるイメージがセグメント化されないで、結局任意の照明変化、並びにオクルージョン及びクラッタに対して真のロバストさにつながる。イメージの中のモデルの位置は、整合メトリックがある一定のユーザ選択可能しきい値より高い１組の変換（姿勢）により与えられ、そして選択された変換のクラス内で極大である。
【００１６】
対象物認識プロセスを加速するため、許容可能な変換の空間は、再帰的な粗から微細への方法（ｒｅｃｕｒｓｉｖｅ ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ ｓｔｒａｔｅｇｙ）を用いて探索される。
【００１７】
イメージの中のモデルの見つけられたインスタンスのパラメータ、例えば、平行移動及び回転を用いて、そのような幾何学的情報を用いるロボット又はいずれの他の装置を制御することができる。
【００１８】
本発明は、オクルージョン、クラッタ及び非線形コントラスト変化に対してロバストである対象物認識のための方法を提供する。以下の説明は、当業者が本発明を作り及び使用するのを可能にするよう提供される。特定の応用の説明は例示としてのみ提供されている。
【００１９】
【発明の実施の形態】
整合メトリック
対象物のモデルは、対応する方向ベクトルを備える複数の点から成る。典型的には、モデルは対象物のイメージから発生され、そこにおいて任意の関心の領域（ＲＯＩ）は、その中に対象物が配置されるイメージのその部分を指定する。ＲＯＩは、例えば、システムのユーザにより対話的に指定されることができる。代替として、ＲＯＩは、例えば、機械視覚方法、例えば、しきい値処理、形態学のような種々のセグメント化操作の使用によりにより発生することもできる。モデル発生方法の詳細が以下に説明されるであろう。
【００２０】
図２は、認識されるべき対象物のサンプル・イメージ：即ち、明るい背景上の暗い十字記号を表示する。図３は、対象物のモデルを表示し、それは、このケースにおいては、エッジ・フィルタを用いることにより発生される（以下のモデル発生についてのセクションを参照）。モデルのポイントは矢印の尾により表され、一方それらの方向は矢印の向きにより表される。モデルとしての対象物の別のあり得る表示が、図４に示されている。そこでは、モデルのポイントを決定するためライン抽出が用いられて、結局十字記号の中心線を表すモデルということになる。モデルを発生する更に別の方法、例えば、コーナー検出が、以下のモデル発生についてのセクションで説明される。
【００２１】
前述のことに照らして、モデルは、ポイントｐ_i＝（ｐ_i ^x、ｐ_i ^y）^T及び関連の方向ベクトルｄ_i＝（ｄ_i ^x、ｄ_i ^y）^T（ｉ＝１、…、n）から成り、ここで、ｎはモデル内のポイントの数である。ポイントｐ_iは、ＲＯＩ又はｎ個のポイントそれ自体の重心に関しての座標であり、即ち、重心が、原点であり、そしてモデルの基準点である。同様に、その中にモデルが認識されることとなるイメージは、方向ベクトルｅ_x,y＝（ｅ^x _x,y、ｅ^y _x,y）^Tが各イメージ点（ｘ、ｙ）^Tに対して得られる表示に変換することができる。整合プロセスにおいて、変換されたモデルは、イメージと特定の位置で比較されねばならない。最も一般的ケースにおいては、変換は透視変換である。アルゴリズムの説明を単純にしておくため、アフィン変換を残りの説明全体にわたり用いる。しかしながら、これは、アルゴリズムがこのクラスの変換に制限されることを含意すると解釈すべきでない。アフィン変換の平行移動部分を線形部分から分離することは有効である。従って、線形変換されたモデルは、ポイントｐ_i′＝Ａｐ_i、及びそれで変換された方向ベクトルｄ_i′＝Ａｄ_iにより与えられ、ここでＡは次式のとおりである。
【００２２】
【数４】

前述したように、変換されたモデルがイメージ内容と整合メトリックにより比較されるが、その整合メトリックはオクルージョン、クラッタ及び照明変化に対してロバストでなければならない。本発明の一実施形態に従ってこのゴールを達成する１つのあり得るメトリックは、変換されたモデルの方向ベクトルとイメージとのモデルの全ての点にわたる（正規化されてない）ドット積の和を取って、整合スコアをイメージの特定のポイント（ｘ、ｙ）^Tで計算し、即ち、変換されたモデルの整合メトリックをポイント（ｘ、ｙ）^Tで計算することであり、その和はアフィン変換の平行移動部分に対応して、次のように計算される。
【００２３】
【数５】

この整合スコアの利点は、モデル・イメージも、その中にモデルが認識されることとなるイメージもセグメント化（２値化）される必要がないことであり、即ち、イメージをまたセグメント化する抽出操作の代わりに方向ベクトルを生じるのみであるフィルタリング動作を用いることで十分である。従って、モデルがエッジ又はライン・フィルタリングにより発生され、且つイメージが同じ要領で事前処理される場合、この整合メトリックは、オクルージョン及びクラッタに対するロバストさの要件を満たす。対象物の部分がイメージの中で欠落している場合、イメージの中のモデルの対応する位置にラインもエッジも無い、即ち方向ベクトル
【００２４】
【数６】

は、小さい長さを有し、従って上記和に対して殆ど寄与しない。同様に、イメージの中にクラッタ・ライン又はエッジが有る場合、モデルの中のクラッタ位置に点が無いか、又はクラッタ・ライン又はエッジが小さい長さを有するかのいずれかであり、それは、上記和に対して殆ど寄与しないことを意味する。従って、上記整合メトリックは、いかに良好に、相互に対応するイメージ及びモデルの中の点が幾何学的に位置合わせを行うかを表す。
【００２５】
しかしながら、上記の整合メトリックを用いて、イメージの明るさが、例えば一定の係数だけ変化された場合、整合メトリックは同じ量だけ変わる。従って、変換されたモデルの方向ベクトルとイメージとのモデルの全ての点にわたる正規化されたドット積の和、即ち、次式を計算することにより整合メトリックを修正することが好ましい。
【００２６】
【数７】

方向ベクトルの正規化のため、この整合メトリックは、任意の照明変化に対して追加的に不変である。この好適な実施形態においては、全てのベクトルは、１の長さにスケーリングされ、そしてこのメトリックをオクルージョン及びクラッタに対してロバストにさせることは、エッジ又はラインが欠落している場合モデルの中又はイメージの中のいずれかにおいて雑音がランダムな方向ベクトルを引き起こし、それが平均して上記和に何も寄与しないことである。
【００２７】
モデルの全ての方向ベクトルとイメージとが整列即ち同じ方向に向いている場合、上記整合メトリックは高いスコアを戻す。エッジを用いてモデル及びイメージ・ベクトルを発生する場合、これは、モデル及びイメージが各エッジに対して同じコントラスト方向を持たねばならないことを意味する。このメトリックは、例えば、モデルが背景より暗い十字記号から発生される場合、背景より暗い十字記号のみを認識することができるであろう。時には、たとえそのコントラストが逆にされた場合でも対象物を検出できることが望ましい。整合メトリックをそのようなコントラストの全体的な変化に対してロバストにさせるため、正規化されたドット積の和の絶対値を本発明の別の好適な実施形態に従って用いることができ、即ち、整合メトリックは次式のようになる。
【００２８】
【数８】

この整合メトリックは、幾何学的に、イメージの中の全ての方向ベクトル（全体として）がモデルの中の方向ベクトルと同じ方向に向くか又は反対方向に向くかのいずれかでなければならないことを意味する。
【００２９】
まれな環境において、例えば、認識されるべき対象物が中間のグレーのボディから成る場合、局所的コントラスト変化すら無視することが必要なことがあり得る。なお、その中間のグレーのボディは、その上により暗い又はより明るいプリントを持つことができる。このケースにおいては、更に別の実施形態に従って、整合メトリックは、正規化されたドット積の絶対値の和であるよう修正されることができる。次式はその和である。
【００３０】
【数９】

幾何学的には、この整合メトリックは、イメージの中の各方向ベクトルが個々にモデルの中の対応する方向ベクトルと同じ方向か又は反対方向のいずれかに向かなければならないことを意味する。
【００３１】
上記３つの正規化された整合メトリックは、対象物がオクルージョンされた場合その対象物が見つけられるという意味においてオクルージョンに対してロバストである。前述のように、これは、イメージの中のモデルのインスタンス内の欠落している対象物のポイントが平均して上記和に何も寄与しないことから生じる。イメージの中のモデルのいずれの特定のインスタンスに対して、これは、例えば、イメージ内の雑音が非相関ではないので、真ではない場合がある。これは、たとえモデルがイメージの中で移動しなくても、モデルのインスタンスが異なるイメージにおける異なる姿勢の中に見つけられるという望ましくないことを引き起こす。それは、モデルの特定のイメージにおいてランダムな方向ベクトルが上記和に対して僅かに異なる量寄与し、従って整合メトリックの最大がランダムに変化するからである。モデルの局在化をより微細にするため、イメージ内の欠落しているモデル・ポイントの寄与をゼロにセットすることは有効である。これを行う最も容易な方法は、イメージの中の方向ベクトルの長さ
【００３２】
【数１０】

がイメージ内の雑音レベルと、イメージの中の方向ベクトルを抽出するため用いられる事前処理オペレーションとに依存するしきい値より小さい場合、イメージの中の方向ベクトルの逆数の長さ
【００３３】
【数１１】

をゼロにセットすることである。このしきい値は、ユーザにより指定される。整合メトリックのこの修正により、モデルのオクルージョンされたインスタンスは、それがイメージの中で移動しない場合、常に同じ姿勢の中に見つけられることを保証することができる。
【００３４】
３つ全ての正規化された整合メトリックは、それらが潜在的整合のスコアとして１より小さい数を生じる特性を有する。全てのケースにおいて、１のスコアは、モデルとイメージとの間の完全な整合を示す。更に、スコアは、おおまかに、イメージの中に視認できるモデルの部分に対応する。例えば、対象物が５０％オクルージョンされている場合、スコアは０．５を超えることができない。これは、対象物が認識された見なされるべきであるときに対して直観的しきい値を選択するための手段をユーザ与えるので、極めて望ましい特性である。
【００３５】
方向ベクトルのドット積は方向ベクトルが逆余弦関数により囲む角度と関連付けられるので、上記整合メトリックの幾何学的意味をも捕捉する他の整合メトリックが定義されることができる。１つのそのようなメトリックは、モデルの中の方向ベクトルとイメージの中の方向ベクトルとが囲む角度の絶対値を合計することである。このケースにおいては、整合メトリックは、ゼロより大きい又はそれに等しい値に戻すであろう。なお、ゼロの値は完全な整合を示す。このケースにおいて、モデルの姿勢は、整合メトリックの最小から決定されねばならない。
【００３６】
対象物認識方法
イメージの中の対象物を見つけるため、アプリオリ無境界探索空間が境界付けされる必要がある。これは、ユーザを介して探索空間のパラメータに対してしきい値を設定することにより達成される。従って、アフィン変換の場合、ユーザは、２つの目盛係数、スキュー角及び回転角に対するしきい値を指定する。即ち、
【００３７】
【数１２】

平行移動パラメータに対する境界はまた各々２つのしきい値により指定されることができるが、しかしこれは平行移動の空間を長方形に制限するであろう。従って、本発明の方法に従って、変換パラメータに対する境界は、その中でモデルが認識されることとなるイメージの中の任意の関心領域として一層都合良く指定される。
【００３８】
整合の最も単純な形式は、例えば、以下に説明するように、境界付けされた探索空間を離散化し、そしてそのように得られた変換パラメータの全ての組み合わせによりモデルを変換し、更に全ての結果として生じた変換されたモデルに対して整合メトリックを計算することである。これは、全てのあり得るパラメータの組み合わせに対して１つのスコアをもたらす。この後、全ての有効な対象物インスタンスが、各組のパラメータでのスコアがユーザにより選択された最小しきい値より上である、即ちｍ≧ｍ_minであること、且つスコアが変換空間において整合メトリックの極大であることを要求することにより選択されることができる。
【００３９】
認識されるべき対象物が対称性、例えば図２における十字記号の回転及び鏡映対称性を有する場合、対象物の幾つかのインスタンスが見つけられ、それは、例えばそれらの回転及びスケーリング・パラメータの点で異なるが、しかし非常に近い平行移動パラメータを有するであろう、即ち認識された対象物は重なっているであろう。大部分のケースにおいては、最良のスコアを有するインスタンスを除いて重なっている全てのインスタンスを取り除くことが望ましい。そうするため、見つけられたインスタンスの相互重なりが、モデルの見つけられたインスタンスの任意の向きの最小包囲長方形と２つの包囲長方形のうちの小さい方との交差範囲を比較することにより計算される。重なりがユーザ選択可能な小部分（フラクション）より多い場合、より小さいスコアを有するインスタンスが捨てられる。
【００４０】
オペレーションの通常のモードにおいては、スコア及び重なり基準を満たす全てのインスタンスは、本発明の方法により戻される。時に、モデルのどのくらい多くのインスタンスがイメージの中で見つけられる必要があるかは演繹的に知られる。従って、ユーザは、イメージの中で見つけられるべきモデルのインスタンスの数ｏを指定する。このケースにおいては、重なっているインスタンスの除去後のｏ個の最良インスタンスのみが戻される。
【００４１】
探索空間の離散化
本発明で開示した全ての整合メトリックは、計算されるべき正しいスコアに対して、変換されたモデルとイメージ中の対象物の大きな重なりを要求する。重なりの程度は、方向情報を得るため取られた事前処理ステップにより影響を及ぼされる。ライン又はエッジ・フィルタリング方法を用いて、方向情報を得る場合、モデルとイメージにおけるインスタンスの重なりの程度は、ライン又はエッジ・フィルタで用いられた平滑化の程度に直接依存する。小さい平滑化を有するフィルタ、例えばソーベル（Ｓｏｂｅｌ）・エッジ・フィルタを用いた場合、変換されたモデルの全てのポイントは、（カメラの光学素子によりイメージの中で対象物のエッジがいかに不鮮明に見えるかに依存して）イメージ中のインスタンスのほぼ１個のピクセル内になければならなく、それにより正しいスコアが得られる。エッジ又はライン抽出が実行される前にイメージが平滑化される場合、この距離は、適用される平滑化量に比例してより大きくなる。それは、エッジ又はラインが平滑化動作により広くされるからである。例えば、サイズｋ×ｋの平均フィルタが特徴抽出（例えば、ライン又はエッジ・フィルタリング）の前に又はそれにおいて適用された場合、モデル・ポイントは、インスタンスのｋ個のピクセル内になければならない。類似の結果が、他の平滑化フィルタ、例えばキャニー（Ｃａｎｎｙ）・エッジ抽出器及びステガー（Ｓｔｅｇｅｒ）ライン検出器で用いられるガウス・フィルタに対して当てはまる。
【００４２】
変換空間は、イメージ中のインスタンスから多くてもｋ個のピクセルにある全てのモデル・ポイントの上記の要件が保証されることができる要領で離散化される必要がある。図５は、離散化ステップ長を導出するため用いられるパラメータと共に鍵のサンプル・モデルを示す。ポイントｃは、モデルの基準点、例えばその重心である。距離ｄ_maxは、基準点からの全てのモデル・ポイントの最大距離である。距離ｄ_xは、ｘ方向のみ測定した基準点からの全てのモデル・ポイントの最大距離である。即ち、モデル・ポイントのｘ座標が距離を測定するため用いられる。同様に、距離ｄ_yは、ｙ方向のみ測定した基準点からの全てのモデル・ポイントの最大距離である。モデルをｘ方向にスケーリングすることにより生成された全てのモデル・ポイントがイメージの中のインスタンスからｋ個のピクセル内に有ることを保証するため、ステップ長Δｓ_xがΔｓ_x＝ｋ／ｄ_xとして選定されねばならない。同様に、Δｓ_yは、Δｓ_y＝ｋ／ｄ_yとして選定されねばならない。スキュー角の離散化は、ｘ軸がスキュー操作において固定されたままであるので、距離ｄ_yのみの依存する。従って、スキュー角のステップ長Δθは、Δθ＝ａｒｃｃｏｓ（１−ｋ²／（２ｄ² _y））として選定されねばならない。同様に、回転角のステップ長は、Δφ＝ａｒｃｃｏｓ（１−ｋ²／（２ｄ² _max））として選定されねばならない。最後に、平行移動パラメータにおけるステップ長は、両方共ｋに等しく、即ちΔｔ_x＝Δｔ_y＝ｋでなければならない。
【００４３】
認識方法の加速
前述の全数探索アルゴリズムは、対象物が存在する場合イメージの中に対象物を見つけるが、しかしその方法の実行時間は全く大きいであろう。種々の方法が、認識プロセスを加速するため本発明の好適な実施形態に従って用いられる。
【００４４】
最初に、ドット積の和が完全に計算されないのが好ましい。それは、スコアが潜在的インスタンスが得られるように最小スコアｍ_minより上でなければならないからである。ｍ_jがモデルのｊ番目の要素までドット積の部分的和を示すとする。正規化されたドット積の和を用いる整合メトリックに対して、これは次のようになる。
【００４５】
【数１３】

和の残りの（ｎ−ｊ）個の項の全ては全て１より小さいか又は１に等しい。従って、ｍ_j＜ｍ_min−１＋ｊ／ｎである場合、部分的スコアｍ_jは決して要求されたスコアｍ_minに達することができなく、従って和の評価はこの条件が満たされているときは常にｊ番目の要素の後で中断することができる。この判定基準は、認識プロセスを相当に加速する。それにも拘わらず、更なる加速が大いに望ましい。別の判定基準は、全ての部分的和がｍ_minより良いスコア、即ちｍ_j≧ｍ_minであることを要求することである。この判定基準を用いるとき、探索は、非常に速いが、しかしもはや、この方法はモデルの正しいインスタンスを見つけることを保証することができない。それは、モデルの欠落部分が最初にチェックされる場合部分的スコアは要求スコアより低いからである。対象物がイメージの中で視覚可能であるにも拘わらず対象物が見つからないことが非常に低い確率である状態で認識プロセスを加速するため、次の発見法を用いることができる。即ち、モデル・ポイントの第１の部分を比較的安全な停止判定基準で検査し、一方モデル・ポイントの残りの部分を厳しいしきい値ｍ_minを用いて検査する。ユーザは、モデル・ポイントのどの部分をパラメータｇを有する厳しいしきい値を用いて検査することを指定することができる。ｇ＝１の場合、全ての点が厳しいしきい値を用いて検査され、一方ｇ＝０の場合は、全ての点が安全な停止判定基準を用いて検査される。これを用いて、部分的和の評価は、ｍ_j＜ｍｉｎ（ｍ_min−１＋ｆｊ／ｎ、ｍ_min）（ここで、ｆ＝（１−ｇｍ_min）／（１−ｍ_min））であるときは常に停止される。典型的には、パラメータｇは、イメージの中のインスタンスの欠落なしで０．９程の高い値にセットされることができる。前述の判定基準と同じ趣旨の他の停止判定基準を定義することができるは明らかである。
【００４６】
第２に、モデル・ポイントに対する勾配長の正規化は、モデルが生成される時点、即ちモデル・ポイントが長さ１の方向ベクトルを有して格納される時点に最良に行われることは明らかである。イメージ点の勾配長の逆数
【００４７】
【数１４】

は、方向ベクトルの成分が取ることができる値の範囲が制限される場合前もって計算することができる。このケースにおいては、その勾配長の逆数は、１回のみ計算され、そして方向ベクトルの２つの成分により指標付けされるマトリックスの中に格納される。例えば、方向ベクトルを符号化するため符号を付された１バイト値を用いる場合、マトリックスのサイズは２５６×２５６であろう。方向ベクトルの逆数長を格納することは、除法が乗法により置換される追加の利点を有し、乗法は、殆ど全てのマイクロプロセッサについてはるかに速い。逆数長を格納する最後の利点は、前述した欠落する対象物ポイントの寄与分の棄却がある一定の長さより下の全ての逆数方向ベクトル長を０にテーブルで設定することにより単純に行うことができることである。
【００４８】
別の大きな加速は、再帰的な粗から微細への方法を用いて許容可能な変換の空間を探索することにより得られる。前述の対象物認識方法は、最も微細なあり得る離散化を持つ探索空間における探索に対応し、そこにおいてステップ長は、ｋ＝１に対して得られる値に設定される。これは、比較的遅い全数探索をもたらす。その探索を加速するため、ステップ長が最も微細なレベルでのステップ長の整数倍である探索空間において全数探索を実行することができる。次いで、この粗く離散化された探索空間の中で見つけられた整合は、その整合が最も微細なレベルの離散化で見つけられるまで、前進的により微細に離散化された探索空間を通して追跡されねばならない。全てのレベルの離散化において、探索空間の離散化についてのセクションにおける平滑化についてのしるしが観察されねばならなく、即ち、各レベルの離散化に対する一時的イメージが生成されねばならず、そこにおいては各イメージは、対象物が常に見つかることを保証するため、対応する離散化レベルのステップ長に対応する量だけ平滑化されねばならない。異なる離散化レベルのためのステップ長パラメータに対する良好な選定は、それらを、ｋ＝２^l（ここで、ｌ＝０、…、ｌ_max）である場合得られる値に設定することである。離散化レベルの数（ｌ_max＋１）がユーザにより選定されるべきであり、それにより対象物は、ｋ＝２^lmaxの対応する値のため必要な平滑化の下で依然認識できる。一例として、探索空間が固定変換の空間である場合で、そしてモデルがｄ_max＝１００の最大を有する場合で、且つｌ_max＝３がユーザにより選定される場合、以下のステップ長が、「探索空間の離散化」のセクションで説明される方法に従って異なる離散化レベルの探索空間に対して得られる。
【００４９】
【表１】

更なる加速のため、モデルの中の点の数がまた、異なる離散化レベルの探索空間に対して係数ｋ＝２^lにより低減されることが好ましい（以下のモデル発生についてのセクション参照）。必要な平滑化は、平均フィルタを用いることにより得られることが好ましい。それは、平均フィルタが再帰的に実行されることができ、従ってイメージを平滑化するための実行時間が平滑化パラメータに依存しないからである。代替として、ガウス型平滑化フィルタの再帰的実行を用いることができる。この離散化及び平滑化方法が既に許容可能な実行時間を生成するにも拘わらず、更なる加速は、各離散化レベルについて平行移動ステップ長Δｔ_x及びΔｔ_yと同一である係数によりイメージをサブサンプリングすることよっても得られることができる。このケースにおいては、平行移動パラメータに対するステップ長は、勿論、各レベルで１に設定されねばならない。しかしながら、ここで、正しい平行移動パラメータを離散化のレベルにわたって伝搬することに注意しなければならない。前述したように、平行移動ステップ長が各レベルの離散化空間において２倍になる場合、見つけられた対象物の平行移動パラメータは、次のより微細な離散化レベルを探索する前に２倍にされねばならない。明らかに、イメージのサブサンプリングは、アフィン変換の他の４つのパラメータに影響を及ぼさない。平均フィルタを用いる場合、サブサンプリング及び平滑化プロセスは、平均イメージ・ピラミッドに対応する（Ｔａｎｉｍｏｔｏ（１９８１））。ガウス・フィルタが平滑化のため用いられる場合、ガウス型イメージ・ピラミッドが得られる。
【００５０】
変換の空間が平行移動の空間又は固定変換の空間である場合、前述の方法は、既に最適な実行時間に近いであろう。変換の空間がより大きい、例えば、相似性又はアフィン変換の空間である場合、一般化されたハフ変換（Ｂａｌｌａｒｄ（１９８１））又はＲｕｃｋｌｉｄｇｅ（１９９７）で説明された方法のような方法を用いることにより探索を加速することが可能であり得て、その方法は、潜在的に変換空間の大きな部分を迅速に除いて、潜在的整合を最も粗いレベルの離散化空間においてより迅速に識別する。間違った整合の潜在性がこれらの方法により一層高いので、潜在的整合を離散化空間のレベルを通して検査し且つ追跡するため本明細書で開示の方法を用いることは本質的である。更に、潜在的整合の正確さが弱いので、事前処理ステップにより戻された姿勢は、本明細書で開示の方法に基づく真の整合が見つけられることを保証するのに十分な量だけ変換空間における領域に拡大されねばならない。
【００５１】
これらの原理の展開を用いて、好適な対象物認識方法を図６に示す。第１のステップ（１）において、その中にモデルが見つけられることとなるイメージが、外部装置、例えばカメラ又はスキャナから獲得される。
【００５２】
次いで、イメージは、探索空間の再帰的副分割と一致する表示に変換される（ステップ２）。好適な実施形態においては、ユーザは、パラメータｌ_maxを指定することにより探索空間の最も粗い副分割を選択する。次いで、ｌ_max個の一時的イメージが、元のイメージに加えて生成される。好ましくは、これらのｌ_max＋１個のイメージが次いで事前処理されて、元のイメージの平均イメージ・ピラミッドを増強し、それは、ピラミッドの各レベルｌにおけるイメージが次に低いピラミッド・レベルにおけるイメージの側長の半分を有することを意味し、そこにおいてグレー・レベルは、ピラミッドの次に低いレベルの適切な位置で２×２ブロックのグレー値を平均化することにより得られる。代替として、一時的イメージは、サブサンプリング・ステップを省略し且つ元のイメージについての各離散化されたレベルに対する適切なマスク・サイズを有する平均フィルタを用いることにより生成される。
【００５３】
このステップの後に、特徴抽出が、ｌ_max＋１個のイメージの各々で実行される（ステップ３）。特徴抽出は、例えば、エッジ又はライン・フィルタをイメージに適用することにより行って、イメージの中の方向ベクトルを得ることができる。そのようなフィルタ・オペレーションを用いる場合、セグメント化（２値化）オペレーションは実行されない。イメージ・ピラミッドを用いる場合、方向ベクトルもまた、任意の領域セグメント化手順、例えばイメージをしきい値処理することから得られることができ、そこにおいてしきい値は、例えば、ヒストグラム解析によりイメージから導出され、上記の任意の領域セグメント化手順には、セグメント化された領域の境界に対する法線を計算することが続き、例えば、特定の境界点の周りのある一定の数の境界点に適合する最小方形ラインを計算し且つその境界点の方向として当該ラインの法線を用いることが続く。
【００５４】
続いて、最も粗いレベルｌ_maxの離散化空間にわたり全数探索が実行される（ステップ４）。これは、パラメータ値の全ての組み合わせに対して、対応するパラメータ値を用いて変換されたモデルの整合メトリックが、前述の整合メトリックの１つにより計算されることを意味する。モデル発生についてのセクションにおいて後述されるように、変換されたモデルは、モデルが発生される時点に事前計算され得る。これが行われなかった場合、モデルは、このステップにおいて、アフィン変換パラメータをモデルの点に適用し且つ線形変換パラメータをモデルの方向ベクトルに適用することにより変換されねばならない。これは、パラメータ値の各あり得る組み合わせに対するスコアをもたらす。次いで、スコアは、ユーザ選択可能しきい値ｍ_minと比較される。このしきい値を超える全てのスコアは、探索空間内の領域の中に組み合わされる。これらの領域において、整合メトリックの極大が、ある一定の組のパラメータのスコアを隣接の変換パラメータのスコアと比較することにより計算される。結果として生じる極大は、探索空間の最も粗い離散化におけるモデルの見つけられたインスタンスに対応する。見つけられたこれらのインスタンスは、インスタンスのリストに挿入され、そのインスタンスのリストは、インスタンスのスコアにより分類される。
【００５５】
一旦最も粗い離散化レベルの徹底的な整合（全数整合）が完結すると、見つけられたインスタンスは、それらが最低レベルの離散化空間で見つけられるまで、より微細なレベルの離散化空間を通して追跡される（ステップ５）。その追跡は次のように実行される。即ち、第１の未処理モデル・インスタンスがモデル・インスタンスのリストから除去される。これは、インスタンスのリストがスコアにより分類されるので、最良のスコアを有する未処理インスタンスである。次いで、このインスタンスのポーズ・パラメータを用いて、次に低いレベルの離散化における探索空間を定義する。理想的には、モデルは、ポーズ・パラメータの適切な変換により与えられる位置に配置されるであろう。即ち、スケーリング・パラメータｓ_x及びｓ_y、並びに角度φ及びθが、次に微細なレベルの離散化において最も近いパラメータに丸められ、一方変換パラメータは、もしイメージ・ピラミッドを用いる場合２の係数によりスケーリングされるか、又はもしサブサンプリングを用いない場合無修正で通されるかのいずれかである。しかしながら、イメージが次に微細なレベルにおける量よりその２倍の量だけ平滑化されてしまった最も粗い離散化レベルにおいてインスタンスが見つけられたので、次に低いレベルの離散化において探索空間を形成するとき考慮されねばならないポーズ・パラメータにおける不確定性がある。探索空間に対する良好な選定は、伝搬される平行移動パラメータの周りにサイズ５×５の長方形を構成することにより得られる。更に、他の４つのパラメータに対する探索空間は、より微細なレベルにおける次に低い値及び次に高い値のパラメータを探索空間の中に含むことにより構成される。一例として、変換の空間が、固定変換から成ると仮定すると、そのイメージ・ピラミッドが用いられてしまい、そしてインスタンスは、次の姿勢、即ち（ｔ_x、ｔ_y）＝（３４，２７）、φ＝５５．０２０°を有するレベルｌ＝３の離散化において見つけられた。次いで、より微細なレベルｌ＝２における探索空間は、６６≦ｔ_x≦７０、５２≦ｔ_y≦５６、及び５２．７１６°≦φ≦５７．３００°により与えられる（上記の例において離散化ステップ長を有するテーブルを覚えているべきである。）。次いで、モデルは、最も粗い離散化についての徹底的な整合に対して前述したのと同じ要領で整合メトリックを計算することにより、全ての変換を用いてより微細なレベルにおける探索空間で探索される。探索空間内の最大スコアが識別される。対応する姿勢が探索空間の境界にある場合、探索空間は、最大スコアを有する姿勢が探索空間内に完全にあるようになるまで、即ち探索空間の境界にないようになるまで、その境界で反復的に拡大される。こうして得られた最大スコアがユーザ選択可能しきい値ｍ_minを超える場合、インスタンスは、そのスコアに従った適切な場所で、見つけられたインスタンスのリストに加えられる。
【００５６】
最も微細なレベルの離散化空間について、インスタンスがリストに挿入される時点に、見つけられたインスタンスが他のインスタンスとあまりに多く重なる場合、それら見つけられたインスタンスがチェックされる（ステップ６）。前述したように、インスタンス間の重なりは、各対のインスタンスの周りの任意の向きの最も小さい包囲長方形と、２つの長方形のうちの小さい方との交差面積の比として計算される。重なりがユーザにより供給された小部分より大きい場合、より良いスコアを有するインスタンスのみがリストの中に保持される。ユーザが見つけるべき最大数のインスタンスを指定しなかった場合、もし全ての見つけられたインスタンスが最も微細なレベルの離散化上にあるならば、モデルの再帰的追跡は停止する。ユーザが見つけるべき最大数ｏのインスタンスを指定した場合、もし最も微細な離散化レベルで見つけられたインスタンスの数がｏより小さいならば、且つもし全ての見つけられたインスタンスが最も微細なレベルの離散化にあるならば、即ち、ユーザにより指定された数よりイメージの中のインスタンスが少ないならば、モデルの再帰的追跡は停止する。代替として、ｏ個のインスタンスが最も微細なレベルの離散化で見つけられた場合、探索は停止する。次いで、この追跡方法は、全ての未処理のインスタンスをより粗いレベルの離散化でチェックすることにより、それらのスコアが最も微細なレベルで見つけられた最悪のインスタンスのスコアに十分に近接しているか否かを知る。それは、これらのインスタンスが、これまで見つけられたｏ個の最良のインスタンスより、一層微細なレベルの離散化でのより良いスコアに導くからである。未処理のインスタンスが最も微細なレベルで見つけられた最悪スコアに定数、例えば０．９を掛けたものより良いスコアを有する場合、このインスタンスはまた、ｏ個の最良の整合が見つけられることを保証するため、前述の要領で探索空間にわたり再帰的に追跡される。これは、全ての関係のないインスタンス、即ち、制限ｏを超えて見つけられた全てのインスタンスがこのステップ６で除去されることを意味する。
【００５７】
ユーザが、最も微細な離散化より一層良い解像度を用いて姿勢を戻すべきであると指定した場合、見つけられた各インスタンスに対応する最大の整合メトリックがサブピクセル解像度を用いて外挿される（ステップ７）。これは、例えば、選定された変換の空間のパラメータに関して整合メトリックの１次及び２次導関数を計算することにより行うことができる。１次及び２次導関数は、例えば、適切な１次及び２次導関数マスク、例えばｎ次元ファセット・モデル・マスク（ｎ−ｄｉｍｅｎｓｉｏｎａｌ ｆａｃｅｔ ｍｏｄｅｒｌ ｍａｓｋｓ）を用いた畳み込みにより最大スコアに隣接するスコアから得ることができる（Ｓｔｅｇｅｒ（１９９８）［Ｃａｒｓｔｅｎ Ｓｔｅｇｅｒ著「曲線構造の不偏検出器（Ａｎ ｕｎｂａｉｓｅｄ ｄｅｔｅｃｔｏｒ ｏｆ ｃｕｒｖｉｌｉｎｅａｒ ｓｔｒｕｃｔｕｒｅ）」、パターン解析及び機械知能のＩＥＥＥトランザクション（ＩＥＥＥ Ｔｒａｎｓｃｔｉｏｎ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ）、２０（２）：１１３−１２５頁、１９９８年２月発行］（これらのマスクの２次元バージョンに対するものである。それらは、直接的な方法でｎ次元に一般化する。）参照）。これは、離散的探索空間の最大スコア・セルにおけるテイラー多項式を導き、そのテイラー多項式から最大は、１組の１次方程式を解くことにより容易に計算することができる。
【００５８】
最後に、見つけられたインスタンスの抽出された姿勢は、ユーザに戻される（ステップ８）。
モデル発生
モデルは、前述の整合方法に従って発生されねばならない。モデル発生の心臓部に、モデルのポイント及び対応する方向ベクトルを計算する特徴抽出がある。これは、多数の異なるイメージ処理アルゴリズムにより行うことができる。本発明の一好適な実施形態においては、方向ベクトルはモデル・イメージの勾配ベクトルであり、それは、標準エッジ・フィルタ、例えば、ソーベル−キャニー・フィルタ（ｔｈｅ Ｓｏｂｅｌ，Ｃａｎｎｙ ｆｉｌｔｅｒ）（Ｃａｎｎｙ（１９８６）［Ｊｏｈｎ Ｃａｎｎｙ著「エッジ検出に対する計算的アプローチ（Ａ cｏｍｐｕｔａｔｉｏｎａｌ ａｐｐｒｏａｃｈ ｔｏ ｅｄｇｅ ｄｅｔｅｃｔｉｏｎ）」パターン解析及び機械知能のＩＥＥＥトランザクション（ＩＥＥＥＴｒａｎｓｃｔｉｏｎ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ）、８（６）：６７９−６９８頁、１９９６年６月発行］参照）、又はデリチェ・フィルタ（Ｄｅｒｉｃｈｅ ｆｉｌｔｅｒ）（Ｄｅｒｉｃｈｅ（１９８７）［Ｒａｃｈｉｄ Ｄｅｒｉｃｈｅ著「キャニー判定基準を用いた、再帰的に実行される最適エッジ検出器の導出（Ｕｓｉｎｇ Ｃａｎｎｙ’ｓ ｃｒｉｔｅｒｉａ ｔｏ ｄｅｒｉｖｅ ａ ｒｅｃｕｒｓｉｖｅｌｙ ｉｍｐｌｅｍｅｎｔｅｄ ｏｐｔｉｍａｌ ｅｄｇｅ ｄｅｔｅｃｔｏｒ）」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒａｎｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ、１：１６７−１８７頁、１９８７年参照］から得られることができる。イメージがセグメント化されない場合、ＲＯＩ内の全ての点は、モデルに加えられるであろう。方向情報は勾配の大きさが大きい範囲で最も正確で且つ最も信頼できるので、且つＲＯＩ内の点の数が通常非常に大きい（従って探索がゆっくりしている）ので、モデル・イメージ内のポイントの数は、勾配イメージの標準セグメント化アルゴリズム、例えば勾配の大きさのしきい値処理を用いることにより、又はヒステリシスしきい値処理、非最大抑制及びスケルトンの計算の組み合わせを用いることにより低減される（Ｃａｎｎｙ（１９８６））。別の好適な実施形態においては、方向ベクトルは、ライン検出アルゴリズム、例えば、イメージのヘッシアンマトリックス（２次偏微分から成るマトリックス）の最大強度の固有値に対応する固有ベクトルから得られることができる（Ｓｔｅｇｅｒ（１９９８）又はＢｕｓｃｈ（１９９４）［Ａｎｄｒｅａｓ Ｂｕｓｃｈ著「ユーザによる供給されるパラメータなしでのディジタル・イメージ内のラインの高速認識（Ｆａｓｔ ｒｅｃｏｇｎｉｔｉｏｎ ｏｆ ｌｉｎｅｓｉｎ ｄｉｇｉｔａｌ ｉｍａｇｅｓ ｗｉｔｈｏｕｔ ｕｓｅｒ−ｓｕｐｐｌｉｅｄ ｐａｒａｍｅｔｅｒｓ）」、写真測量及び遠隔検知の国際記録（Ｉｎｔｅｒｎａｔｉｏｎａｌ Ａｒｃｈｉｖｅｓ ｏｆ Ｐｈｏｔｏｇｒａｍｍｅｔｒｙ ａｎｄ Ｒｅｍｏｔｅ Ｓｅｎｓｉｎｇ）における、ＸＸＸ巻、パート３／１、９１−９７頁、１９９４年参照］参照）。２つの引用されたアルゴリズムは、既にイメージをセグメント化、即ち、エッジ検出で用いられる非最大抑制及びスケルトン動作に似て、１ピクセル幅ラインを生じることに注目されたい。本発明の別の好適な実施形態においては、方向情報は、コーナー検出器、例えばフェルストナー（Ｆｏｅｒｓｔｎｅｒ（以下、この文字の中の「ｏｅ」はドイツ文字のｏウムラウトを表す。））の方法（１９９４）［Ｗｏｌｆｇａｎｇ Ｆｏｅｒｓｔｎｅｒ著「低レベル特徴抽出のためのフレームワーク（Ａ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｌｏｗ ｌｅｖｅｌ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ）」、Ｊａｎ−Ｏｌｏｆ Ｅｋｌｕｎｄｈ編集、コンピュータ・ビジョンについての第３回ヨーロッパ会議でのコンピュータ科学における講演ノートの８０１巻、３８３−３９４頁、ベルリン、１９９４年、シュプリンガー出版社（Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ）発行］から得られることができる。この方法は、非常に少ないポイントがモデルに対して発生される利点を有する。本発明の別の好適な実施形態においては、セグメント化領域の境界に対する法線を計算すること、例えば、特定の境界点の周りのある一定数の境界点に適合される最小方形ラインを計算し、且つそのラインの法線をその境界点の方向として用いることが続く任意の領域セグメント化手順、例えばイメージのしきい値処理から、方向情報は得ることができる。
【００５９】
完全なモデル発生方法が図７に示されている。最初に、モデルとして用いられるべき対象物を含むイメージが、外部装置、例えば、カメラ又はスキャナから獲得される（ステップ１）。このステップは、イメージ内でモデルが存在する関心の領域の選択を含む。ＲＯＩは、ユーザにより対話的に指定されることができる。代替として、ＲＯＩは、自動的にイメージ処理プログラムにより、例えば、適切な方法、例えばしきい値オペレーションにより対象物をセグメント化することにより、且つ特徴抽出がＲＯＩ内の全ての関連対象物ポイントを見つけることを保証するため形態操作を用いてセグメント化領域を拡大することにより発生されることができる。
【００６０】
次に（ステップ２）、イメージは、探索空間の再帰的副分割と一致する表示に変換される。好適な実施形態においては、ユーザは、パラメータｌ_maxを指定することにより探索空間の最も粗い副分割を選択する。次いで、ｌ_max個の一時的イメージは、元のイメージに加えて生成される。次いで、これらｌ_max＋１個のイメージが事前処理され、元のイメージの平均イメージ・ピラミッドを増強する。代替として、一時的イメージは、サブサンプリング・ステップを省略し、且つ元のイメージについての各離散化レベルに対する適切なマスク・サイズを有する平均フィルタを用いることにより生成される。
【００６１】
この後で、離散化の各レベルに対して、適切なモデルが発生される（ステップ３）、即ち、図７のステップ（４）−（７）が各レベルの離散化に対して実行される。各レベルの離散化に対してモデルを発生する理由は、探索空間の各レベルにおける平行移動パラメータのステップ長に従ってデータ量を低減するためである。イメージ・ピラミッドがイメージを変換するためステップ（２）で用いられた場合、モデル内のポイントの数の低減は自動的に起こる。サブサンプリングが実行されなかった場合、データ点の数は、以下のステップ（６）における特徴抽出の後に低減される。
【００６２】
各レベルの離散化に対して、探索空間が、前述の対象物認識方法の説明に従って、次の線形変換パラメータについてユーザにより指定された境界を用いてサンプリングされる。
【００６３】
【数１５】

平行移動パラメータはサンプリングされない、即ち、固定の平行移動パラメータｔ_x＝ｔ_y＝０が用いられる。それは、平行移動パラメータは、モデルの形状を変えないからである。ステップ（５）−（７）が、現在レベルの離散化に対する、サンプリングされた探索空間からの各組のパラメータに対して実行される。探索空間をサンプリングする理由は、許容可能な変換の下でモデルの全てのあり得る形状を事前計算し且つそれをメモリに格納することにあり、結果として対象物認識段階における実行時間の著しい低減につながる。
【００６４】
ステップ（５）において、現在レベルの離散化の変換されたイメージ、即ち、現在レベルのピラミッドでのイメージ、又は適切に平滑化されたイメージ、これはステップ（２）で発生されたものであるが、このイメージは、現在の変換パラメータを用いて変換される。ここで、対象物が依然イメージ変換後にイメージ内に完全にあることに注意しなければならない。必要ならば、平行移動が、これを達成するためその変換に加えられ、それは、抽出されたモデル・ポイントがステップ（７）においてモデルに加えられるときにである。イメージは、適切なアンチエイリアシング方法を用いて、例えば双線形補間を用いて変換される。
【００６５】
イメージが変換された後に、選定された特徴抽出アルゴリズが、変換されたイメージに適用される（６）。前述のように、特徴抽出アルゴリズは、例えば、ライン、エッジ、又はコーナー検出、又は領域ベースのセグメント化アプローチであり得る。これは、特徴点及びそれらの対応する方向ベクトルのリストをもたらす。サブサンプリングが、現在レベルの離散化でイメージを発生するため用いられた場合、モデル・ポイントがここでサブサンプリングされる。これは、例えば、モデルの全てのｋ番目のポイントを選択することより行われる（ここで、ｋは現在レベルの離散化での平行移動パラメータのステップ長である。）。代替として、モデル・ポイントは、現在レベルの離散化での平行移動パラメータのステップ長に対応する、側長ｋの各正方形に入る点にグループ分けされることができる、即ち抽出された特徴点が碁盤目状にされる。次いで、少なくとも１つのモデル・ポイントを持つ各碁盤目状にされた正方形の中心に最も近いモデル・ポイントが、その正方形を表すモデル・ポイントとして選択される。モデル・ポイントの数は更に、対象物認識プロセスを後で加速するためこのステップで低減されることが任意にできる。これは、主に、特徴ピクセルのチェインを戻す特徴抽出器、例えば、ライン、エッジ、及び領域境界セグメント化手順に対して有効である。（必要ならば、サブサンプリングがステップ（２）において用いられなかった場合特徴点の碁盤目状の配列を考慮して、）１つのそのような方法は、例えば、抽出されたピクセルを接続されたピクセルのチェインにリンクさせることであり、その結果対象物の接続された輪郭を生じる。次いで、その輪郭は多角形で近似でき、それはデータ量を相当に低減する。モデル・ポイントは、このケースの場合多角形制御点である。代替として、対象物の輪郭がサブサンプリングされ、より少ないモデル・ポイントを有するモデルを発生することができる、即ち、輪郭の全てのｋ番目のポイントのみがモデルに加えられる。
【００６６】
最後に、ステップ（６）で得られたモデル・ポイントは、変換されたモデルを発生するため用いられた変換パラメータと共に、現在の離散化レベルでのモデルの収集に加えられる。欲張りな探索方法が用いられる場合に整合をよりロバストにするため、モデルの第１の数個のポイントがモデルにわたり良好に分布される程度にポイントをモデルに加えることが有効である。これは欲張りな方法では必要である。それは、モデルの第１の部分における全てのポイントがたまたまオクルージョンされ、一方全ての他のポイントが存在する場合、その整合方法はモデルのインスタンスを見つけないであろう。第１のモデル・ポイントの一様分布を達成するための最も単純な方法は、モデル・ポイントをモデルにランダム化された順序で加えることである。
【００６７】
前述のモデル発生方法は、大きい許容可能な変換の探索空間の非常に大きな数の事前計算されたモデルを発生し得る。これは、結局、事前計算されたモデルを格納することを要求されたメモリが非常に大きいことになり、それは、モデルがメモリ内に格納されることができないか、又は仮想メモリをサポートするシステム上のディスクにページングされねばならないかのいずれかを意味する。第２のケースにおいては、認識段階において必要とされるモデルの部分がディスクからメイン・メモリに戻すようにページングされねばならないので、対象物認識が遅くされるであろう。従って、事前計算されたモデルを格納するのに要求されるメモリが大きくなりすぎる場合、代替のモデル発生方法は、上記の方法のステップ（４）を省略し、そして代わりに、対象物を変更しないままにする、即ちｓ_x＝ｓ_y＝１及びφ＝θ＝０である変換パラメータに対応する、各レベルの離散化での対象物のただ１つの事前計算されたモデルを計算することとなる。このケースにおいては、モデルの変換は、モデルが対象物認識方法に対して前述したようにイメージと整合されるとき急いで行わなければならない。
【００６８】
上記のモデル発生方法は、各離散化レベルにおいて１組の変換の各許容可能な変換を用いてイメージを変換する。それは、その方法が特徴抽出器のあり得る異方性結果を考慮しようするから、即ち、特徴抽出器が戻す方向ベクトルがイメージの特徴の向きに偏倚される方法で依存し得ることを考慮するからである。たとえそれら方向ベクトルがイメージの中でどの向きに生じようとも、特徴抽出器が等方性である、即ち特徴抽出器が戻す方向ベクトルが正しいことが知られている場合、イメージ変換ステップを省略することができる。代わりに、抽出された特徴点及び方向ベクトルそれら自体は、変換されて、全てのあり得る変換に対して事前計算された１組のモデルを得る。このモデル発生方法が図８に示されている。代替モデル発生方法のステップ（１）−（３）は、図７の正常なモデル発生方法と同一である。相違は、特徴抽出がここでは全ての離散化レベルに対して１回だけ実行されることである（４）。次いで、ステップ（５）−（７）を用いて、モデル・ポイント及び方向ベクトルが、現在レベルの離散化のに対して全てのあり得る変換により変換され、メモリに格納される。
【００６９】
本発明の幾つかの特定の実施形態が詳細に説明されたが、好適な実施形態に対する種々の変更が本発明の範囲を離れることなく行うことができる。
【図面の簡単な説明】
【図１】 図１は、一般的アフィン変換のパラメータを示す。
【図２】 認識されるべき対象物のサンプル・イメージを示す。
【図３】 対象物のモデルがエッジ・フィルタを用いることにより発生されることを示す。
【図４】 対象物のモデルがライン抽出を用いて発生されることを示す。
【図５】 離散化長を導出するため用いられるパラメータと共に鍵のサンプル・モデルを示す。
【図６】 本発明に従った再帰的対象物認識方法の好適な実施形態を示す。
【図７】 本発明に従ったモデル発生方法の好適な実施形態を示す。
【図８】 本発明に従ったモデル発生方法の別の好適な実施形態を示す。

Claims (18)

1. （ａ）電子的メモリにモデル対象物のイメージを獲得するステップと、
   （ｂ）探索空間の第１のレベルの離散化を作成するために使用される、モデル・ポイントからイメージ・ポイントまでの最大距離からなるスケールへ、前記モデル対象物のイメージを変換するステップと、
   （ｃ）探索空間の前記第１のレベルの離散化に対して前記対象物の少なくとも１つの事前計算モデルを発生するステップと、前記事前計算されたモデルは、アフィン変換の変換部分に対応していない該アフィン変換の４つの自由度までの可能な範囲に対応し、各事前計算モデルは対応する方向ベクトルをもつ複数のポイントからなり、前記ポイントおよび方向ベクトルは少なくとも各モデル・ポイントに対して方向ベクトルを戻すイメージ処理オペレーションにより発生され、
   （ｄ）電子的メモリに現在のイメージを獲得するステップと、
   （ｅ）探索空間の第１のレベルの離散化を作成するために使用される、モデル・ポイントからイメージ・ポイントまでの最大距離からなるスケールへ現在のイメージを変換するステップと、
   （ｆ）前記第１のレベル表示の前記変換されたイメージの上で、前記イメージ内の各ポイントに対して方向ベクトルを戻すイメージ処理オペレーションを実行するステップと、
   （ｇ）探索空間の前記第１の離散化レベルにおけるモデルのアフィン姿勢の全ての可能な自由度に対してモデルの方向ベクトル及び変換されたイメージを用いる整合メトリックを計算するステップと、
   （ｈ）これらのモデル姿勢の整合メトリックがユーザ選択可能しきい値を超え且つ極大である当該これらのモデル姿勢を決定し、且つ探索空間の前記第１の離散化レベルにおけるモデルのインスタンスのリストを前記姿勢及び前記整合メトリックから発生するステップと、
   （ｉ）前記第１のレベルの離散化における前記対象物のインスタンスの姿勢を与えるステップと、
   を備え、対象物はアフィン変換により変換される、イメージ内の対象物を認識する方法。
2. （ｂ）探索空間の再帰的マルチレベルの粗から微細への副分割を作成するために使用される、モデル・ポイントからイメージ・ポイントまでの増加する最大距離からなるマルチレベル表示へ、前記モデル対象物のイメージを変換するステップと、
   （ｃ）探索空間の各レベルの離散化に対して前記対象物の少なくとも１つの事前計算モデルを発生するステップと、前記事前計算されたモデルは、アフィン変換の変換部分に対応していない該アフィン変換の４つの自由度までの可能な範囲に対応し、各事前計算モデルは対応する方向ベクトルをもつ複数のポイントからなり、前記ポイントおよび方向ベクトルは少なくとも各モデル・ポイントに対して方向ベクトルを戻すイメージ処理オペレーションにより発生され、
   （ｅ）探索空間の再帰的マルチレベルの粗から微細の副分割を作成するために使用される、モデル・ポイントからイメージ・ポイントまでの増加する最大距離からなるマルチレベル表示へ現在のイメージを変換するステップと、
   （ｆ）前記マルチレベル表示の前記変換されたイメージの上で、前記イメージ内の各ポイントに対して方向ベクトルを戻すイメージ処理オペレーションを実行するステップと、
   （ｇ）探索空間の最も粗い離散化レベルにおけるモデルのアフィン姿勢の全ての可能な自由度に対してモデルの方向情報及び変換されたイメージを用いる整合メトリックを計算するステップと、
   （ｈ）これらのモデル姿勢の整合メトリックがユーザ選択可能しきい値を超え且つ極大である当該これらのモデル姿勢を決定し、且つ探索空間の前記最も粗い離散化レベルにおけるモデルのインスタンスのリストを前記姿勢及び前記整合メトリックから発生するステップと、
   （ｉ）前記最も微細なレベルの離散化に達するまで、前記探索空間の最も粗い離散化レ ベルにおけるモデルのインスタンスを探索空間の前記再帰的副分割にわたり追跡するステップと、
   （ｊ）前記最も微細な離散化における前記対象物のインスタンスの姿勢を与えるステップと、
   を備え、請求項１のステップ（ｂ）、（ｃ）及び（ｅ）から（ｉ）までが上記ステップにより置き換えられる、請求項１に記載の方法。
3. ステップ（ｃ）において、ステップ（ｂ）に従った各レベルの離散化に対して、且つステップ（ｃ）に従った現在レベルの離散化での離散化探索空間における各変換に対して、
   （ｃ１）アンチエイリアス法を用いる現在の変換により、現在レベルの離散化のイメージを変換するステップと、
   （ｃ２）前記の変換されたイメージの特徴抽出を実行するステップと、
   （ｃ３）全てのセグメント化された特徴点をそれらの方向ベクトルと共に、変換されたモデルのリストに加えるステップと
   が実行される、請求項１または２に記載の方法。
4. ステップ（ｂ）に従った各レベルの離散化に対して、
   （ｃ１）現在レベルの離散化のイメージでの特徴抽出を実行するステップと、
   ステップ（ｃ）に従って現在レベルの離散化での離散化された探索空間における各変換に対して、
   （ｃ２）前記の抽出されたモデル・ポイント及び方向ベクトルを現在の変換により変換するステップと、
   （ｃ３）全ての変換されたモデル・ポイントをそれらの変換された方向ベクトルと共に変換されたモデルのリストに加えるステップと、
   が実行される、請求項１または２に記載の方法。
5. ステップ（ｉ）に、
   （ｉ′）重なっているモデル・インスタンスを捨てるステップが続く、請求項２から４のいずれかに記載の方法。
6. ステップ（ｉ′）に、
   （ｉｉ″）最も微細な離散化レベルより良い解像度に姿勢情報を微細化するステップが続く、請求項５に記載の方法。
7. ステップ（ｉｉ″）は、整合メトリックの最大を外挿するステップを備える、請求項６に記載の方法。
8. ステップ（ｃ）及び（ｆ）は、変換されたイメージ表示の特徴抽出を実行するステップを備える、請求項１から７の何れかに記載の方法。
9. ライン・フィルタリング、エッジ・フィルタリング、コーナー検出、又は領域ベースのセグメント化が、特徴抽出のため用いられる、請求項８に記載の方法。
10. ステップ（ｇ）において、変換されたモデルの方向ベクトルとイメージとのモデルの全ポイントにわたるドット積の和が前記整合メトリックを計算するため用いられる、請求項１から９の何れかに記載の方法。
11. 変換されたモデルの方向ベクトルとイメージとのモデルの全ポイントにわたる正規化されたドット積の和が前記整合メトリックを計算するため用いられる、請求項１から９の何れかに記載の方法。
12. 正規化されたドット積の和の絶対値が前記整合メトリックを計算するため用いられる、請求項１１記載の方法。
13. 正規化されたドット積の絶対値の和が前記整合メトリックを計算するため用いられる、請求項１１に記載の方法。
14. ステップ（ｇ）において、モデルにおける方向ベクトル及びイメージにおける方向ベクトルが囲む角度の絶対値の和が前記整合メトリックを計算するため用いられる、請求項１から９の何れかに記載の方法。
15. （ａ）電子的メモリにモデル対象物のイメージを獲得する手段と、
    （ｂ）探索空間の第１のレベルの離散化を作成するために使用される、モデル・ポイントからイメージ・ポイントまでの最大距離からなるスケールへ、前記モデル対象物のイメージを変換する手段と、
    （ｃ）探索空間の前記第１のレベルの離散化に対して前記対象物の少なくとも１つの事前計算モデルを発生する手段と、前記事前計算されたモデルは、アフィン変換の変換部分に対応していない該アフィン変換の４つの自由度までの可能な範囲に対応し、各事前計算モデルは対応する方向ベクトルをもつ複数のポイントからなり、前記ポイントおよび方向ベクトルは少なくとも各モデル・ポイントに対して方向ベクトルを戻すイメージ処理オペレーションにより発生され、
    （ｄ）電子的メモリに現在のイメージを獲得する手段と、
    （ｅ）探索空間の第１のレベルの離散化を作成するために使用される、モデル・ポイントからイメージ・ポイントまでの最大距離からなるスケールへ現在のイメージを変換する手段と、
    （ｆ）前記イメージ内の各ポイントに対して方向ベクトルを戻す前記第１のレベル表示の前記変換されたイメージにイメージ処理オペレーションを実行する手段と、
    （ｇ）探索空間の前記第１の離散化レベルにおけるモデルのアフィン姿勢の全ての可能な自由度に対してモデルの方向ベクトル及び変換されたイメージを用いる整合メトリックを計算する手段と、
    （ｈ）これらのモデル姿勢の整合メトリックがユーザ選択可能しきい値を超え且つ極大である当該これらのモデル姿勢を決定し、且つ探索空間の前記第１の離散化レベルにおけるモデルのインスタンスのリストを前記姿勢及び前記整合メトリックから発生する手段と、
    （ｉ）前記第１のレベルの離散化における前記モデルのインスタンスの姿勢を与える手段と、
    を備え、対象物はアフィン変換により変換される、イメージ内の対象物を認識するシステム。
16. （ａ）電子的メモリにモデル対象物のイメージを獲得する手段と、
    （ｂ）探索空間の再帰的マルチレベルの粗から微細への副分割を作成するために使用される、モデル・ポイントからイメージ・ポイントまでの増加する最大距離からなるマルチレベル表示へ、前記モデル対象物のイメージを変換する手段と、
    （ｃ）探索空間の各レベルの離散化に対して前記対象物の少なくとも１つの事前計算モデルを発生するス手段と、前記事前計算されたモデルは、アフィン変換の変換部分に対応していない該アフィン変換の４つの自由度までの可能な範囲に対応し、各事前計算モデルは対応する方向ベクトルをもつ複数のポイントからなり、前記ポイントおよび方向ベクトルは少なくとも各モデル・ポイントに対して方向ベクトルを戻すイメージ処理オペレーションにより発生され、
    （ｄ）電子的メモリに現在のイメージを獲得する手段と、
    （ｅ）探索空間の再帰的マルチレベルの粗から微細への副分割を作成するために使用される、モデル・ポイントからイメージ・ポイントまでの増加する最大距離からなるマルチレベル表示へ現在のイメージを変換する手段と、
    （ｆ）前記マルチレベル表示の前記変換されたイメージの上で、前記イメージ内の各ポイントに対して方向ベクトルを戻すイメージ処理オペレーションを実行する手段と、
    （ｇ）探索空間の最も粗い離散化レベルにおけるモデルのアフィン姿勢の全ての可能な自由度に対してモデルの方向情報及び変換されたイメージを用いる整合メトリックを計算する手段と、
    （ｈ）これらのモデル姿勢の整合メトリックがユーザ選択可能しきい値を超え且つ極大である当該これらのモデル姿勢を決定し、且つ探索空間の前記最も粗い離散化レベルにおけるモデルのインスタンスのリストを前記姿勢及び前記整合メトリックから発生する手段と、
    （ｉ）前記最も微細なレベルの離散化に達するまで、前記探索空間の最も粗い離散化レ ベルにおけるモデルのインスタンスを探索空間の前記再帰的副分割にわたり追跡する手段と、
    （ｊ）前記最も微細な離散化における前記対象物のインスタンスの姿勢を与える手段と、
    を備え、対象物はアフィン変換により変換される、イメージ内の対象物を認識するシステム。
17. コンピュータ読取可能媒体がコンピュータ上で動作するとき請求項１から１４の何れかの方法を実行するために、コンピュータ読取可能媒体上に格納されたプログラム・コード手段を備えるコンピュータ読取可能媒体。
18. コンピュータ・プログラムがコンピュータ上で動作するとき請求項１から１４の何れかに従った方法の全ステップを実行するプログラム・コード手段を備えるコンピュータ・プログラム。

Images