(57)【特許請求の範囲】
【請求項１】
一般的な非線形変形下にある画像中のオブジェクトを認識する方法であって、
（ａ）モデルオブジェクトの画像を、電子メモリに取得する工程と、
（ｂ）前記モデルオブジェクトの画像を、検索スペースの帰納的な細区分と一致し、少なくとも前記オブジェクトの画像を含む多重レベル表示に変換する工程と、
（ｃ）前記検索スペースの離散化の各レベルについて、前記モデルオブジェクトの、少なくとも１つの事前に計算されたモデルを生成する工程であって、前記事前に計算されたモデルが、対応する方向ベクトルを有する複数のモデル点からなり、前記モデル点および前記方向ベクトルが、前記各モデル点の方向ベクトルを返す画像処理操作によって生成される工程と、
（ｄ）複数の部分中に、前記複数のモデル点の細区分を生成する工程であって、前記部分を変換することにより、前記モデルの変形されたインスタンスが表わされる工程と、
（ｅ）検索画像を電子メモリに取得する工程と、
（ｆ）前記検索画像を、前記検索スペースの帰納的な細区分と一致し、少なくとも前記検索画像を含む多重レベル表示に変換する工程と、
（ｇ）少なくとも１つの事前に計算されたモデルが検索されるべき非線形変換範囲に対応する、前記検索画像中の画像点の部分集合の方向ベクトルを返す画像処理操作を、多重レベル表示の変換された各画像に対して行う工程と、
（ｈ）局所的測量の結果を組み合わせて、前記検索スペースの最も疎な離散化レベルでの各アフィンモデルポーズの広域的一致測量値を計算する工程であり、前記局所的測量のために、前記事前に計算されたモデルに近い、局所的アフィン変換の限定された範囲内において、前記モデルの前記部分を検索し、各部分の極大適合度を、前記部分の広域的一致測量値への寄与として取得する工程と、
（ｉ）一致測量値がユーザにより選択可能な閾値より大きく、局所的極大である、これらのモデルポーズを決定し、かつ、前記検索スペースの最も疎な離散化レベルにおける、少なくとも１つの事前に計算されたモデルのインスタンスのリストを、前記モデルポーズから作成する工程と、
（ｊ）前記部分の局所的変位を表わす非線形変形変換を計算する工程と、
（ｋ）前記検索スペースの前記最も疎な離散化レベルにおいて、前記検索スペースの帰納的な細区分を通じ、最も密な離散化レベルに至るまで、前記少なくとも１つの事前に計算されたモデルの前記インスタンスをトラックする工程と、
（ｌ）各レベルにおいて、前記非線形変形変換をそれぞれ計算し、かつ、前記変形変換を次のレベルに伝える工程と、
（ｍ）前記最も密な離散化レベルにおける前記モデルオブジェクトのインスタンスの非線形変形変換を定める工程とを含むことを特徴とする方法。
【請求項２】
前記部分の位置を、前記最も密な離散化レベルよりも高い解像度で決定する、請求項１に記載の方法。
【請求項３】
前提条件の最高のインスタンスの、前記ユーザにより選択可能な閾値から、ユーザにより選択可能な数の最大値までのみを、前記最も疎な離散化レベルにおいて可能な一致のリスト中に作成する、請求項２に記載の方法。
【請求項４】
各部分の前記局所的一致測量値のスコアが、ユーザにより選択可能な局所的閾値より大きくなければならず、それ以外の場合には、前記部分が遮蔽され、さらなる処理が行われないものとされる、請求項３に記載の方法。
【請求項５】
各部分が多数の点からなり、前記細区分が重複した点の集合を生成する、請求項４に記載の方法。
【請求項６】
各部分が多数の点からなり、前記点の集合が分離した集合である、請求項４に記載の方法。
【請求項７】
Ｋ−ｍｅａｎｓクラスタリング法または正規化カットを用いて細区分を行う、請求項６に記載の方法。
【請求項８】
前記計算された非線形変形変換が透視変換である、請求項４に記載の方法。
【請求項９】
前記モデルの生成が、イメージングデバイスの内部構造および前記モデルに関する情報を、入力された測量値として追加的に取得し、前記計算された非線形変形変換が三次元ポーズである、請求項４に記載の方法。
【請求項１０】
前記計算された非線形変形変換が、薄板スプライン、円筒変換、または調和補間である、請求項４に記載の方法。
【請求項１１】
前記変換されたモデル部分の方向ベクトル、および、前記検索画像の方向ベクトルの、正規化された内積の合計が、前記局所的スコア測量に用いられる、請求項４に記載の方法。
【請求項１２】
前記変換されたモデル部分の方向ベクトル、および、前記検索画像の方向ベクトルの、正規化された内積の合計の絶対値が、前記局所的スコア測量において用いられる、請求項４に記載の方法。
【請求項１３】
前記変換されたモデル部分の方向ベクトル、および、前記検索画像の方向ベクトルの、正規化された内積の絶対値の合計が、前記局所的スコア測量において用いられる、請求項４に記載の方法。
【請求項１４】
一般的な非線形変形下にある画像中のオブジェクトを認識するシステムであって、
（ａ）モデルオブジェクトの画像を、電子メモリに取得する手段と、
（ｂ）前記モデルオブジェクトの画像を、検索スペースの帰納的な細区分と一致し、少なくとも前記オブジェクトの画像を含む多重レベル表示に変換する手段と、
（ｃ）前記検索スペースの離散化の各レベルについて、前記モデルオブジェクトの、少なくとも１つの事前に計算されたモデルを生成する手段であって、前記事前に計算されたモデルが、対応する方向ベクトルを有する複数のモデル点からなり、前記モデル点および前記方向ベクトルが、前記各モデル点の方向ベクトルを返す画像処理操作によって生成する手段と、
（ｄ）複数の部分中に、前記複数のモデル点の細区分を生成する手段であって、前記部分を変換することにより、前記モデルの変形されたインスタンスが表わされる手段と、
（ｅ）検索画像を電子メモリに取得する手段と、
（ｆ）前記検索画像を、前記検索スペースの帰納的な細区分と一致し、少なくとも前記検索画像を含む多重レベル表示に変換する手段と、
（ｇ）少なくとも１つの事前に計算されたモデルが検索されるべき非線形変換範囲に対応する、前記検索画像中の画像点の部分集合の方向ベクトルを返す画像処理操作を、多重レベル表示の変換された各画像に対して行う手段と、
（ｈ）局所的測量の結果を組み合わせて、前記検索スペースの最も疎な離散化レベルでの各アフィンモデルポーズの広域的一致測量値を計算する手段であり、前記局所的測量のために、前記事前に計算されたモデルに近い、局所的アフィン変換の限定された範囲内において、前記モデルの前記部分を検索し、各部分の極大適合度を、前記部分の広域的一致測量値への寄与として取得する手段と、
（ｉ）一致測量値がユーザにより選択可能な閾値より大きく、局所的極大である、これらのモデルポーズを決定し、かつ、前記検索スペースの最も疎な離散化レベルにおける、
少なくとも１つの事前に計算されたモデルのインスタンスのリストを、前記モデルポーズから作成する手段と、
（ｊ）前記部分の局所的変位を表わす非線形変形変換を計算する手段と、
（ｋ）前記検索スペースの前記最も疎な離散化レベルにおいて、前記検索スペースの帰納的な細区分を通じ、最も密な離散化レベルに至るまで、前記少なくとも１つの事前に計算されたモデルの前記インスタンスをトラックする手段と、
（ｌ）各レベルにおいて、前記非線形変形変換をそれぞれ計算し、かつ、前記変形変換を次のレベルに伝える手段と、
（ｍ）前記モデルポーズ、および、前記最も密な離散化レベルにおける前記モデルオブジェクトのインスタンスの非線形変形変換を定める手段とを含むことを特徴とするシステム。
【請求項１５】
請求項１〜１３のいずれか一項に記載の方法をコンピュータに実行させる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広くはマシン視覚システムに関し、具体的には、部分遮蔽、クラッタまたは非線形対比変化によって非線形に変換されたオブジェクトの視覚的認識に関する。
【背景技術】
【０００２】
画像中における、既定の二次元オブジェクトテンプレートの高速で強く正確な位置測定は、多くのコンピュータ視覚アプリケーション、特に、マシン視覚アプリケーションにとって必要不可欠である。例えば、ピックアンドプレース・アプリケーションのためには、オブジェクト認識方法によって、画像化されたオブジェクトの位置を決定しなければならない。イメージングデバイスの既知の配置と共に、その位置が定まると、当該技術における周知の方法により、オブジェクトのポーズを計算できる。このポーズが定まると、ロボットが、例えば、ベルトコンベヤーからオブジェクトを掴むことが可能となる。様々な検査作業において、オブジェクトの位置を抽出することにより、画像中の検出領域の歪みが平らになり、光学式文字認識（ＯＣＲ）を行ったり、例えば、起こり得る製造ミスを検出するために、画像の原型と比較することが容易になる。
【０００３】
当該技術においては、画像中のオブジェクトの位置を決定するために、幾つかの方法が提案されている。その殆どの方法において、一組の可能なオブジェクトのポーズの類似性と、画像とを比較している。閾値を超え、この類似性測定について極大となる位置が、オブジェクトの位置として選択される。
【０００４】
用いられる類似性測定によっては、不利なイメージング条件に対して、特定の不変性が実現される。例えば、類似性測定としての規格化された対応関係を用いて、モデル画像と検索画像との間における、線形の濃淡値変化に対する不変性が実現される。特に本発明と関連するのは、部分遮蔽、クラッタまたは非線形対比変化に対して不変である類似性測定である。この類似性測定は、米国特許第７，０６２，０９３号明細書、欧州特許第１，１９３，６４２号明細書、特許第３７７６３４０号公報に記載されている。前記測量の一般概念は、画像の規格化された方向の内積、および、モデルと画像との類似性の測定値としてのモデル特性を利用することである。
【０００５】
一般的に、ポーズの全てのパラメータを徹底的に捜索することは、電子計算上非常に高コストであり、リアルタイムで適用する殆どの場合において、費用が掛かりすぎる。先行技術の殆どの方法においては、モデルおよび検索画像の両方から画像・ピラミッドを作成することにより、この速度制限を克服している（例えば、Ｔａｎｉｍｏｔｏ（１９８１）〔Ｓｔｅｖｅｎ  Ｌ．Ｔａｎｉｍｏｔｏ  Ｔｅｍｐｌａｔｅ  ｍａｔｃｈｉｎｇ  ｉｎ  ｐｙｒａｍｉｄｓ．Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ  ａｎｄ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ、１６：３５６−３６９、１９８１〕、または、Ｂｒｏｗｎ（１９９２）〔Ｌｉｓａ  Ｇｏｔｔｅｓｆｅｌｄ  Ｂｒｏｗｎ．Ａ  ｓｕｒｖｅｙ  ｏｆ  ｉｍａｇｅ  ｒｅｇｉｓｔｒａｔｉｏｎ  ｔｅｃｈｎｉｑｕｅｓ．ＡＣＭ  Ｃｏｍｐｕｔｉｎｇ  Ｓｕｒｖｅｙｓ、２４（４）：３２５−３７６、１９９２年１２月〕参照）。そして、最高ピラミッドレベルにおいてのみ、全検索範囲について類似性測定値が求められる。それよりも低いレベルにおいては、最低ピラミッドレベルに至るまで、一致する見込みのある候補のみをトラックする。ここで、用いられるピラミッドレベルの数は、オブジェクト認識方法のランタイムを直接左右するため、この数の決定は重要である。一般的には、ピラミッドレベルの数は、最高ピラミッド画像におけるオブジェクトの極小の大きさに基づいて選択される。当該画像において、オブジェクトが非常に小さい場合は、例えばクラッタからオブジェクトを区別するのは難しい。その場合、評価しなければならない、一致する可能性のある候補が多くなりすぎる。十分なピラミッドレベルが選択されなければ、最高ピラミッドレベルにおける検索が、非常に遅くなる。
【０００６】
検索速度を上げるための他の方法は、検査中のオブジェクトの運動パラメータを、線形アフィン変換によって近似できると仮定することである。線形アフィン変換は、入力点（ｘ，ｙ）Tから出力点（ｘ’，ｙ’）Tを、下記式に基づいてマッピングする。
【０００７】
【数１】
0004825253.tif 000002
【０００８】
この一般式は、さらに、幾何学的に意味のあるパラメータに分解することが可能である。
【０００９】
【数２】
0004825253.tif 000003
【００１０】
前記パラメータは、異なるスケーリングファクターｓxおよびｓyによって、最初のｘ軸およびｙ軸に対してスケーリングを行い、ｘ軸に対してｙ軸を非対称変換し、すなわち、ｘ軸を固定した状態でｙ軸を角度θだけ回転し、両軸を角度φだけ回転し、最後にベクトル（ｔx，ｔy）Tによって変換することを表わす。通常、オブジェクト認識システムは、より狭い部分集合、例えば、変換および回転のためだけに、これらのパラメータを評価する。さらに、パラメータは、特定の固定された範囲、例えば、より狭い回転範囲に限定される。これにより、オブジェクト認識システムが、最高ピラミッドレベルにおいて確認しなければならない、可能なポーズの空間が縮小されるため、検索速度が向上する。
【００１１】
しかしながら、様々な状況下において、検出しなければならないオブジェクトは、線形アフィン変換よりもさらに一般的な変換、もしくはその部分集合によって変換される。このような変換の一つとして、下記式により、異なるカメラ位置から撮影された平面オブジェクトのマッピングを表わす透視変換がある。
【００１２】
【数３】
0004825253.tif 000004
【００１３】
この点につき、Ｈａｒｔｌｅｙ  ａｎｄ  Ｚｉｓｓｅｒｍａｎ（２０００）〔Ｒｉｃｈａｒｄ  Ｈａｒｔｌｅｙ  ａｎｄ  Ａｎｄｒｅｗ  Ｚｉｓｓｅｒｍａｎ，Ｍｕｌｔｉｐｌｅ  Ｖｉｅｗ  Ｇｅｏｍｅｔｒｙ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｖｅｒｓｉｏｎ．Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，２０００〕参照。９つのパラメータが、スケールに規定され、自由度は８となる。
【００１４】
オブジェクト認識システムの最終作業が画像の修正のみである場合と、オブジェクトのポーズを決定しなければならない場合とが、明確に区別される。前者においては、透視変換が決定されれば十分である。ここでは、画像を修正するために、逆透視変換を用いる。
【００１５】
オブジェクトの三次元ポーズを決定する必要があり、カメラの内部のパラメータが与えられている場合において、ポーズを表わすのに十分な自由度は、高々６である（３は変換のため、３は回転のためである）。実際のポーズを得るためには、透視変換の８つのパラメータに対して、付加的に２つの非線形の束縛が働かなければならないため、透視変換は、常にポーズに直接変換可能であるわけでないことは、重要な留意点である（Ｂｅｒｔｈｏｌｄ  Ｋ．Ｐ．Ｈｏｒｎ，Ｐｒｏｊｅｃｔｉｖｅ  Ｇｅｏｍｅｔｒｙ  ｃｏｎｓｉｄｅｒｅｄ  Ｈａｒｍｆｕｌ，１９９９）。一旦有効な透視変換が得られれば、当該技術における既知の方法により、三次元ポーズに直接分解することが可能である（例えば、Ｏｌｉｖｅｒ  Ｆａｕｇｅｒａｓ、Ｔｈｒｅｅ−ｄｉｍｅｎｓｉｏｎａｌ  ｃｏｍｐｕｔｅｒ  ｖｉｓｉｏｎ：ａ  ｇｅｏｍｅｔｒｉｃ  ｖｉｅｗｐｏｉｎｔ．Ｔｈｅ  ＭＩＴ  Ｐｒｅｓｓ，２００１，ｃｈａｐｔｅｒ  ７．５）。好ましい方法は、三次元ポーズのパラメータについて直接検索することであり、まず透視変換を決定した後、それをポーズに分解することではない。
【００１６】
線形変換が不十分である他の例としては、オブジェクトの画像が非線形に変形される場合がある。これは、事前に補正することができないカメラレンズシステムによって引き起こされた歪みによるものであろう。さらなる例としては、湯気や水中における画像のように、不規則な歪みを生む媒体の中で、イメージングが行われる場合がある。その他の非線形変換の原因としては、オブジェクト自体が変形可能である場合、例えば、曲げられたり、しわのある表面上に印刷されたりする場合がある。ここでは、ポーズだけではなく、モデルの変形も同時に定めなければならない。非固定変形量の数学的表記においては、下記式によって点が変換されるよう、歪みＷ（ｘ，ｙ）が加えられる。
【００１７】
【数４】
0004825253.tif 000005
【００１８】
【数５】
0004825253.tif 000006
【００１９】
もし、上記式（数５）を満たすとすれば、周知の薄板スプライン関数（Ｆｒｅｄ  Ｌ．Ｂｏｏｋｓｔｅｉｎ，“Ｐｒｉｎｃｉｐａｌ  Ｗａｒｐｓ：Ｔｈｉｎ−ｐｌａｔｅ  Ｓｐｌｉｎｅｓ  ａｎｄ  ｔｈｅ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｏｆ  Ｄｅｆｏｒｍａｔｉｏｎｓ”，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ｐａｔｔｅｒｎ  ａｎａｌｙｓｉｓ  ａｎｄ  ｍａｃｈｉｎｅ  ｉｎｔｅｌｌｉｇｅｎｃｅ，Ｖｏｌ  １１，  Ｎｏ．６，５６７−５８５  １９８９）が得られる。ここで、歪みはアンカー点Ｐiおよび係数ｗiによってパラメータ化される。結果として得られた歪みは、アンカー点の間の曲率を最小化する。
【００２０】
非線形オブジェクト認識に関する先行技術の手法の殆どは、オブジェクト全体が変形された場合であっても、画像中でモデルの十分に小さい部分が、変形後においてもほぼ同様のままであることを前提としている。
【００２１】
しかしながら、この前提をオブジェクト認識システムの効率的な検索方法にどのように取り入れるかが、未解決の問題である。一つの手法（米国特許第７，２３９，９２９号明細書、米国特許第７，１９０，８３４号明細書参照）においては、モデルの分解された部分を階層的に編成する。ここでは、一つの部分を、細区分のルート部分として選択する。このルート部分から、他のオブジェクトがツリー状の構造に編成される。次の検索においては、このルートのオブジェクトが単独で検索されることに留意すべきである。一旦このルート部分が検出されると、前記オブジェクトの変形の前提条件に基づいて、次の部分が取りうる位置が狭められる。結果として、他の部分の検索も簡単になる。
【特許文献１】米国特許第７，０６２，０９３号明細書
【特許文献２】欧州特許第１，１９３，６４２号明細書
【特許文献３】特許第３７７６３４０号公報
【特許文献４】米国特許第７，２３９，９２９号明細書
【特許文献５】米国特許第７，１９０，８３４号明細書
【非特許文献１】Ｓｔｅｖｅｎ  Ｌ．Ｔａｎｉｍｏｔｏ  Ｔｅｍｐｌａｔｅ  ｍａｔｃｈｉｎｇ  ｉｎ  ｐｙｒａｍｉｄｓ．Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ  ａｎｄ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ、１６：３５６−３６９、１９８１
【非特許文献２】Ｌｉｓａ  Ｇｏｔｔｅｓｆｅｌｄ  Ｂｒｏｗｎ．Ａ  ｓｕｒｖｅｙ  ｏｆ  ｉｍａｇｅ  ｒｅｇｉｓｔｒａｔｉｏｎ  ｔｅｃｈｎｉｑｕｅｓ．ＡＣＭ  Ｃｏｍｐｕｔｉｎｇ  Ｓｕｒｖｅｙｓ、２４（４）：３２５−３７６、１９９２年１２月
【非特許文献３】Ｒｉｃｈａｒｄ  Ｈａｒｔｌｅｙ  ａｎｄ  Ａｎｄｒｅｗ  Ｚｉｓｓｅｒｍａｎ，Ｍｕｌｔｉｐｌｅ  Ｖｉｅｗ  Ｇｅｏｍｅｔｒｙ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｖｅｒｓｉｏｎ．Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，２０００
【非特許文献４】Ｂｅｒｔｈｏｌｄ  Ｋ．Ｐ．Ｈｏｒｎ，Ｐｒｏｊｅｃｔｉｖｅ  Ｇｅｏｍｅｔｒｙ  ｃｏｎｓｉｄｅｒｅｄ  Ｈａｒｍｆｕｌ，１９９９
【非特許文献５】Ｏｌｉｖｅｒ  Ｆａｕｇｅｒａｓ、Ｔｈｒｅｅ−ｄｉｍｅｎｓｉｏｎａｌ  ｃｏｍｐｕｔｅｒ  ｖｉｓｉｏｎ：ａ  ｇｅｏｍｅｔｒｉｃ  ｖｉｅｗｐｏｉｎｔ．Ｔｈｅ  ＭＩＴ  Ｐｒｅｓｓ，２００１，ｃｈａｐｔｅｒ  ７．５
【非特許文献６】Ｆｒｅｄ  Ｌ．Ｂｏｏｋｓｔｅｉｎ，“Ｐｒｉｎｃｉｐａｌ  Ｗａｒｐｓ：Ｔｈｉｎ−ｐｌａｔｅ  Ｓｐｌｉｎｅｓ  ａｎｄ  ｔｈｅ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｏｆ  Ｄｅｆｏｒｍａｔｉｏｎｓ”，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ｐａｔｔｅｒｎ  ａｎａｌｙｓｉｓ  ａｎｄ  ｍａｃｈｉｎｅ  ｉｎｔｅｌｌｉｇｅｎｃｅ，Ｖｏｌ  １１，  Ｎｏ．６，５６７−５８５  １９８９
【発明の開示】
【発明が解決しようとする課題】
【００２２】
しかしながら、この先行技術の手法には、明らかな問題点が幾つかある。問題点の一つとしては、そもそも一つの部分に含まれる情報量が少ないため、一般的に一つの部分の検索の認識性が、オブジェクト全体の検索よりも低い、という点がある。この問題点が誤った一致を引き起こし、また、一致の前提条件をさらに評価する必要性が生じるため、検索速度が低下する。さらなる限定は、一つの部分の大きさが、モデル全体の大きさよりも小さいということであり、したがって、画像中のモデルが、特徴に基づく検索方法で用いられなくなる程、相対的に小さくなるまでには、少数のピラミッドレベルしか用いることが出来ない、ということである。
【００２３】
本発明の目的は、前記不変の一致測量、モデルの部分への分解、および、全ての部分の全ての検索結果を同時に計算する検索方法の、それぞれの利点を組み合わせた、変形可能なオブジェクトの検出のための全体論的な手法である。モデルが下位区分に分解されるにも関わらず、最高ピラミッドレベルにおける検索に用いられる、当該モデルの関係する大きさは減少しない。したがって、本発明によれば、先行技術の方法における、ピラミッドレベルの数の減少による速度制限の問題が回避できる。
【課題を解決するための手段】
【００２４】
本発明は、部分遮蔽、クラッタまたは非線形対比変化に強く、透視またはより一般的な変形によって変換された場合であっても、オブジェクトを認識する、オブジェクト認識のためのシステムおよび方法を提供する。
【００２５】
本発明は、一般的な非線形変形下にある画像中のモデルオブジェクトを認識する方法であって、
（ａ）モデルオブジェクトの画像を、電子メモリに取得する工程と、
（ｂ）前記モデルオブジェクトの画像を、検索スペースの帰納的な細区分と一致し、少なくとも前記オブジェクトの画像を含む多重レベル表示に変換する工程と、
（ｃ）前記検索スペースの離散化の各レベルについて、前記モデルオブジェクトの、少なくとも１つの事前に計算されたモデルを生成する工程であって、前記事前に計算されたモデルが、対応する方向ベクトルを有する複数のモデル点からなり、前記モデル点および前記方向ベクトルが、方向ベクトルを前記各モデル点に戻す画像処理操作によって生成する工程と、
（ｄ）複数の部分中に、前記複数のモデル点の細区分を生成する工程であって、前記部分を変換することにより、前記モデルの変形されたインスタンスが表わされる工程と、
（ｅ）検索画像を電子メモリに取得する工程と、
（ｆ）前記検索画像を、前記検索スペースの帰納的な細区分と一致し、少なくとも前記検索画像を含む多重レベル表示に変換する工程と、
（ｇ）少なくとも１つの事前に計算されたモデルが検索されるべき変換範囲に対応する、前記検索画像中のモデル点の部分集合に、方向ベクトルを戻す画像処理操作を、多重レベル表示の変換された各画像に対して行う工程と、
（ｈ）局所的測量の結果を組み合わせて、グローバル一致測量値を計算する工程であり、前記局所的測量のために、前記事前に計算されたモデルに近い変換の制限された範囲内において、前記モデルの前記部分を検索し、各部分の極大適合度を、グローバル一致測量値に対する、前記部分の寄与として取得する工程と、
（ｉ）一致測量値がユーザにより選択可能な閾値より大きく、局所的極大である、これらのモデルポーズを決定し、かつ、前記検索スペースの最も疎な離散化レベルにおける、少なくとも１つの事前に計算されたモデルのインスタンスのリストを、前記モデルポーズから作成する工程と、
（ｊ）前記部分の局所的変位を表わす変形変換値を計算する工程と、
（ｋ）前記検索スペースの前記最も疎な離散化レベルにおいて、前記検索スペースの帰納的な細区分を通じ、最も密な離散化レベルに至るまで、前記少なくとも１つの事前に計算されたモデルの前記インスタンスをトラックする工程と、
（ｌ）各レベルにおいて、前記変形変換値をそれぞれ計算し、かつ、前記変形変換値を次のレベルに伝える工程と、
（ｍ）前記モデルポーズ、および、前記最も密な離散化レベルにおける前記モデルオブジェクトのインスタンスの変更変換値を定める工程とを含むことを特徴とする方法を含む。
【００２６】
発明の好ましい態様は、従属クレームにおいて規定している。
【００２７】
本発明は、一般的な非線形変形下にある画像中のモデルオブジェクトを認識するシステムであって、
（ａ）モデルオブジェクトの画像を、電子メモリに取得する手段と、
（ｂ）前記モデルオブジェクトの画像を、検索スペースの帰納的な細区分と一致し、少なくとも前記オブジェクトの画像を含む多重レベル表示に変換する手段と、
（ｃ）前記検索スペースの離散化の各レベルについて、前記モデルオブジェクトの、少なくとも１つの事前に計算されたモデルを生成する手段であって、前記事前に計算されたモデルが、対応する方向ベクトルを有する複数のモデル点からなり、前記モデル点および前記方向ベクトルが、方向ベクトルを前記各モデル点に戻す画像処理操作によって生成する手段と、
（ｄ）複数の部分中に、前記複数のモデル点の細区分を生成する手段であって、前記部分を変換することにより、前記モデルの変形されたインスタンスが表わされる手段と、
（ｅ）検索画像を電子メモリに取得する手段と、
（ｆ）前記検索画像を、前記検索スペースの帰納的な細区分と一致し、少なくとも前記検索画像を含む多重レベル表示に変換する手段と、
（ｇ）少なくとも１つの事前に計算されたモデルが検索されるべき変換範囲に対応する、前記検索画像中のモデル点の部分集合に、方向ベクトルを戻す画像処理操作を、多重レベル表示の変換された各画像に対して行う手段と、
（ｈ）局所的測量の結果を組み合わせて、グローバル一致測量値を計算する手段であり、前記局所的測量のために、前記事前に計算されたモデルに近い変換の制限された範囲内において、前記モデルの前記部分を検索し、各部分の極大適合度を、グローバル一致測量値に対する、前記部分の寄与として取得する手段と、
（ｉ）一致測量値がユーザにより選択可能な閾値より大きく、局所的極大である、これらのモデルポーズを決定し、かつ、前記検索スペースの最も疎な離散化レベルにおける、少なくとも１つの事前に計算されたモデルのインスタンスのリストを、前記モデルポーズから作成する手段と、
（ｊ）前記部分の局所的変位を表わす変形変換値を計算する手段と、
（ｋ）前記検索スペースの前記最も疎な離散化レベルにおいて、前記検索スペースの帰納的な細区分を通じ、最も密な離散化レベルに至るまで、前記少なくとも１つの事前に計算されたモデルの前記インスタンスをトラックする手段と、
（ｌ）各レベルにおいて、前記変形変換値をそれぞれ計算し、かつ、前記変形変換値を次のレベルに伝える手段と、
（ｍ）前記モデルポーズ、および、前記最も密な離散化レベルにおける前記モデルオブジェクトのインスタンスの変更変換値を定める手段とを含むことを特徴とするシステムを含む。
【００２８】
認識されるオブジェクトのモデルは、対応する方向ベクトルを持つ複数の点から構成され、標準的な画像処理アルゴリズム、例えば、エッジ検出法または線検出法によって得られる。モデル生成時には、点の集合は、複数の部分に分割される。検索の間、これらの部分は、元の位置を基準に移動可能であり、したがって、前記モデルの形が柔軟に変化する。好ましい態様において、前記モデルの各部分は、１つのモデル点のみからなる。他の好ましい態様において、各部分は、互いに対して固定された、幾つかの隣接する点からなる。
【００２９】
検索の間、元のモデルは、例えば、一般的なアフィンポーズ範囲にインスタンス化される。各位置においては、狭い範囲の変換において各部分を独立に変換することにより、モデルのインスタンスを変形する。各部分について、この制限された範囲における各変換において、一致測量値を計算する。好ましい態様において、前記一致測量値は、前記部分の方向ベクトルと、前処理された検索画像の方向ベクトルとの、正規化された内積である。前記モデル全体の一致測量値は、変形された変換における、極大適合部の正規化された総和である。好ましい態様において、一致測量値に対するスコアが閾値よりも小さい部分は、遮蔽されるため、さらなる処理が行われないものとされる。一致測量値が極大である部分の変換により、元の位置に対する当該部分の変形が決まる。この変位は、事前に選択された変形モデルを計算するために用いられる。好ましい態様において、非線形変形のモデルは透視変換である。他の態様においては、例えば、スプライン関数、または、点集合を補間または近似するための、当該技術における他の既知の方法を用いても良い。この変換関数が一旦計算されると、検出された画像領域の変形が反転し、修正された画像が生成される。
【００３０】
本発明は、下記の詳細な説明および添付図面により、十分に理解されるであろう。
【発明を実施するための最良の形態】
【００３１】
本発明は、遮蔽、クラッタおよび非線形対比変化に強い、可変オブジェクト認識方法を提供する。
【００３２】
また、本発明は、図１〜６を参照して以下に説明される方法としても実施可能であるが図８に示すようなコンピュータを利用して、図７に示すような機能的構成を有するオブジェクト認識システムとしても実施可能である。
【００３３】
図１は、方法の工程の概略を示す。当該方法は、オブジェクトのモデルが生成されるオフライン段階と、前記オブジェクトのモデルが検索画像中で検出されるオンライン段階とに分かれる。モデルを生成するために、未変形のオブジェクトを示すサンプル画像を入力する。図２に、家のような形のサンプルオブジェクト２０２の画像を示す。対象領域２０１により、画像中のオブジェクトの位置が制限される。一般的に、この領域は、オフライントレーニング段階において、オブジェクト認識システムのユーザが規定する。オブジェクト認識システムのユーザが、検索画像中のオブジェクトを事後的に修正することのみに関心がある場合には、前記オブジェクトの小さな部分だけが、後の処理における特定の対象となることがある。例えば、パッケージから文字を読み取らなければならないような利用において、その後に歪みが平らにされるモデル２０３を基準とした領域の位置や大きさを規定する、付加的な対象領域を特定することができる。オブジェクト検出システムが、完全なオブジェクトからの情報を利用する間、当該オブジェクトの特定の対象となる部分のみを、修正しなければならない。このことにより、特にオブジェクトの小さな部分のみが対象となる場合には、速度が向上する。
【００３４】
アプリケーションによっては、例えば、ロボットマニピュレータのピックアンドプレイス・アプリケーションにおいては、オブジェクト認識システムのユーザが、オブジェクトの姿勢（ポーズ）に関心がある場合がある。しかしながら、画像中の対象領域２０１は、画像中の位置や大きさだけを特定するにすぎない。オブジェクトの測量ポーズを決定するためには、イメージングデバイスの内部構造をシステムに提供しなければならない。一般的に、イメージングデバイス３００（図３ａ参照）の内部構造は、その焦点距離と、画像中の主点の位置と、行および列方向における画素の大きさと、レンズによって生じるピンクッション型または筒型の歪みを表わす歪み係数とによって表わされる。オブジェクト認識システムを有するロボットマニピュレータを制御するためには、ワールド座標系におけるカメラのポーズのように、さらなる情報が必要となる。ワールド座標系におけるカメラおよびロボットマニピュレータの位置を取得することにより、ポーズについて、カメラの局所的座標系から、ロボットマニピュレータの座標フレームへの変換、もしくはその逆の変換がなされる。したがって、カメラ座標系におけるポーズ情報を、制御作業に変換することができ、ロボットマニピュレータが直接実行されうる。カメラの内部および外部のパラメータは、先行技術における様々な既知の方法（例えば、ＭＶＴｅｃ  Ｓｏｆｔｗａｒｅ  ＧｍｂＨ、ＨＡＬＣＯＮ  ８．０  Ｄｏｃｕｍｅｎｔａｔｉｏｎ，Ｓｏｌｕｔｉｏｎ  Ｇｕｉｄｅ  ■−Ｆ，３ｄ  Ｍａｃｈｉｎｅ  Ｖｉｓｉｏｎ，２００７参照）によって
、事前に定めることができる。
【００３５】
これらのパラメータが一旦決定されると、オブジェクトの相対的なポーズを推定するために、カメラ座標系における、モデルオブジェクト３０１の対象領域の相対的なポーズが必要となる（図３および４参照）。通常、これは、画像化されたオブジェクトの測量情報を事前に入手できない場合や、例えば、オブジェクトが、小さくてカメラの近くにあるのか、または、大きいがカメラから離れているのかを判別することができない場合に重要である。ここでは、これら２つの状況が、同じ画像をもたらす可能性がある。この測量情報を提供する一般的な方法は、例えば、ワールド座標の点と画像座標の点との対応関係を手動で特定し、かつ、画像座標およびワールド座標の両方における位置を測定することであり、それにより、画像処理のスケールが明確になる。
【００３６】
しかしながら、この手法は、点の対応を手動で定める作業に時間を費やすため、誤差を生みやすく、オブジェクト認識システムの使用を煩雑にする。好ましい態様においては、既に測定された平面較正板３０３を、対象オブジェクトの上方に配置し、較正板を表わす画像を取得する（図３ｂ参照）。この概略図において、較正板３０３は、点の対応を規定する黒丸を有する。較正板の大きさと、点の正確な測量位置とが既知であるため、カメラ座標系における較正板の相対的なポーズが決まる。そして、較正板をオブジェクトから取り除き、較正板と同じ位置にある、オブジェクトを表わす第２の画像を取得する（図３ａ参照）。較正板のポーズと、モデル生成のためのオブジェクトのポーズとが、ワールド座標系および画像座標系の両方において同一であるため、オブジェクトに対応するポーズが自動的に決まる。較正板３０３の領域は、モデル生成のためのオブジェクトの画像と組み合わせられて、直接用いられる。この手法によれば、ユーザが画像中のオブジェクトの領域を特定する必要がないため、システムの使用が簡単になる。あるいは、ユーザが、一旦オブジェクトの上に較正グリッドを配置し、画像を取得し、その後較正板を取り除けば、オブジェクトの第２の画像が得られる。さらに好ましい態様においては、較正板によって規定された四角形の対象領域を、較正グリッドの四角形ではなく、任意の形状の平面のオブジェクトと合うように手動で調整することができる。ここでは、モデルを規定する対象領域が、較正板と同一の平面上にある限り、較正板によって得られた点の対応関係を用いることができる。さらに、当業者であれば誰でも、この方法を非平面オブジェクトにも応用することができる。例えば、対象領域および平面の下部構造の測量情報を、ループ内に集め、これらの部分をオブジェクトの三次元表示に組み立てるであろう。
【００３７】
オブジェクト認識システムは、モデル生成の画像を、元の画像の滑らかな副試料バージョンを含む、帰納的な細区分に変換する。下記の説明において、帰納的な細区分、多重レベル表示および画像ピラミッドが、同時に用いられる。好ましい態様において、帰納的な細区分は、平均的な画像ピラミッドである。他の好ましい態様においては、ガウスの画像ピラミッドが適用される。モデルの位置を規定する対象領域から、同一の多重レベル表示が生じる。各多重レベル表示について、モデル生成により、画像の前記領域からエッジ点が抽出される。エッジ検出の結果を、図４に示す。ここで、エッジ検出は、強いコントラスト変化の位置だけでなく、方向も抽出する。エッジ検出としては、例えば、ソーベルフィルタ、カニーエッジ検出フィルタ、または、指定された特徴点を画像から抽出する技術において既知である、その他のフィルタが用いられる。本発明は、エッジの特徴に限定されず、当業者によって、線の特徴や、対象点の特徴にまで拡大されうるであろう。分かりやすくするために、以下の記載においては、エッジ点に限定して説明を行う。図４ａの小さい矢印４００は、エッジ点の位置および方向を表わす。抽出されたエッジ点は、モデル座標フレーム（円４０１として図示）に変換され、各モデル点について、メモリに記憶される。したがって、前記システムは、画像化されたオブジェクトの幾何的表示を得る。
【００３８】
一般的に、モデルの原点を規定するモデル座標フレーム４０１は、点の集合の重力の中心を得ることにより計算される。座標フレームの向きは、画像の向きと同じである。したがって、テンプレート画像座標フレーム中にモデル座標フレームをマッピングする変換は、単純な変換である。さらに好ましい態様において、ユーザは、異なる点をモデルの原点とする。原点を手動で設定するための一般的な適用においては、当該適用における特定の対象となるオブジェクト上の位置、例えば金属部分のボアホールの中心を検出するべきである。一般的に、この位置は、明らかにモデルの中心に対応しない。この中心モデル点は、特定の対象となる。何故なら、オブジェクト認識システムは、この点がオブジェクトの位置を示すと仮定するので、オブジェクト認識システムにより、ポーズがこの点に戻るためである。
【００３９】
モデル座標フレームから画像座標フレームへの、一般的なアフィン変換マッピングを適用することにより、モデルの異なるインスタンスを画像中に投写することができる。しかしながら、これまでモデルインスタンスは固定されている。
【００４０】
非線形モデル変形を継続的に行うために、複数のエッジポイントをまとめ、サブ・プルーラリティーとする。局所的にサブ・プルーラリティーを変換することにより、互いのサブ・プルーラリティーに対する空間的関係が変化し、オブジェクト全体の形状の非線形の変化が起こる。ここで、それぞれのサブ・プルーラリティーに適用される局所的変換は、十分小さいアフィン変換、または、固定された変換や転換といった部分集合である。モデルの細区分の例を図４ｂに示す。部分を生成するために、特徴抽出により事前に生じたエッジポイント４００の集合が入力される。
【００４１】
一旦エッジポイントが抽出されると、部分生成の作業として、これらの点をグループ化し、空間的に整合性のある構造４０３とする。ここで、本発明においては、空間的に相関関係のある構造が、変形後もなお同一性を保つと仮定する。本発明の一つの特徴は、このクラスタリングを手動で行うことである。ここで、ユーザは、同様のままであると分かっている部分を、一つのグループとして選択する。本発明の他の態様においては、自動的な方法によってクラスタリングが行われる。一つの直接的な方法としては、固定された細区分をモデルに設定し、細区分の一つのセル中の点を、一つの部分に属させる方法がある。他の手法としては、モデル点の付近のグラフを計算し、一つの部分に入るように、最も近い点を固定数だけ選択する方法がある。他の方法としては、点の集合の構造的分解の適用がある。当該技術において、構造的分解方法としては、例えば、Ｋ−ｍｅａｎｓ法クラスタリングまたは正規化カット（Ｊｉａｎｂｏ  Ｓｈｉ、および、Ｊｉｔｅｎｄｒａ  Ｍａｌｉｋ，Ｎｏｒｍａｌｉｚｅｄ  ｃｕｔｓ  ａｎｄ  ｉｍａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ．Ｉｎ  ＩＥＥＥ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ，ｐｐ．７３１−７３７，１９９７）が知られている。本発明が、異なるサブ・プルーラリティーが分離した集合である、という事実に限定されないことは、重要な留意点である。好ましい態様において、それぞれの点およびそれに最も近い近傍の点について、サブ・プルーラリティーが生成される。用いられた細区分方法とは別に、モデル点が、それぞれｋi個のモデル点を含むｎ個の部分に分けられる。その後の計算時間を短縮するために、それぞれの部分にモデル点の指数ｎijが含まれるデータ構造を用いる。ここで、指数ｉは、１からｎの範囲であり、どの部分が選択されたかを規定する。ｊは、１からｋiの範囲であり、当該部分の点を規定する。例えば、それぞれの部分のモデル点の数が同じである場合には、それぞれの行が部分を表わし、それぞれの列がこの部分の指数を表わす、行列表示が用いられる。
【００４２】
このような細区分を規定した後、例えば、それぞれの点の集合の重力の中心を検出することにより、それぞれの部分４０３の中心４０２を計算する。部分の中心とモデル４０１の原点との間の変換値４０４が、モデルに記憶される。したがって、モデルの座標フレームを部分の座標フレームに変換するユークリッド変換のように、部分の中心の相対位置が、変換値に換算される。これらの変換により、モデル点の位置および方向について、部分の座標フレームからモデルの座標フレームへの変換、またはその逆の変換がされる。例えば、ｘ軸およびｙ軸に沿った少しの移動、または、部分の中心を回転中心とした回転によって、モデルと部分との間で相対変換４０４が変化することにより、モデルの変形されたバージョンがインスタンス化される。ｘ方向およびｙ方向における小さな変換に起因するサンプル変換が、図４ｃに図示されている。
【００４３】
本発明の特徴は、部分遮蔽、クラッタおよび非線形照射変化が存在する画像中に固定されたオブジェクトの検出について既知である、方法およびシステムを拡張することである（米国特許第７，０６２，０９３号明細書参照）。
【００４４】
規定されたモデルの点の集合は、検索画像の密度勾配方向フィールドと比較される。勾配振幅に伝わる大幅な非線形照射変化によっても、勾配方向は変化しない。さらに、検索画像においては、ヒステリシス閾値や非最大抑制が完全に防止され、任意の照射変化に対する真の不変性が得られる。部分遮蔽、ノイズおよびクラッタが、検索画像におけるランダム勾配方向を生じさせる。これらの効果は、この測量に対するスコアの最大値を低くするが、その位置を変えることはない。スコア値は、一致する複数のモデル点の分割を意味する。
【００４５】
有効な検索の概念は、オブジェクト認識システムが、一般的なアフィン変換またはその部分集合のみを包括的にインスタンス化することである。部分を局所的に移動し、最適値として極大応答を検出することにより、明確にではないが、はるかに高いクラスの非線形変換が、検索によって評価される。これが図５に示されており、この中に、モデルの２つの変形されたインスタンスを有する検索画像が図示される。左側には、モデルの透視変換されたインスタンス５００が示されている。右側には、さらに複雑な任意の変形５０１が図示されている。図に示されるように、局所的に適応された部分４０３により、検索画像中のオブジェクトが近似される。それぞれの部分の、固定された位置と局所的に適応された位置との間における局所的変換値の変化により、モデルの外観の多様性が表わされる。
【００４６】
重要なことは、画像をピラミッド表示に変換することにより、それぞれのレベルにおける変形量が、少しだけ補正されなければならないということである。例えば、最低ピラミッドレベルにおけるオブジェクトの変換が複雑であったとしても、最高ピラミッドレベルにおける外観はさほど変わらない。一方、オブジェクトの変形量が大きい場合には、最高レベルにおいて補正されることが可能である。本発明において、変形量は、画像ピラミッドの下方に向かって帰納的に伝えられる。より高い全てのレベルの変形量が、より高いピラミッドレベルにおいて補正されるとすれば、それぞれのレベルにおいて起こるオブジェクトの外観の変化は比較的小さい。
【００４７】
したがって、本発明によると、検索測量をグローバル（広域的）部分ｓgおよび局所的部分ｓlに分けることにより、変形可能なオブジェクトを検出するための測量が拡張される。分かりやすくするために、それぞれの行ｒおよび列ｃのみについてスコアの計算を行うための変換式を示す。この式を、一般的なアフィンパラメータにまで直接拡張する。上述したとおり、モデルは、それぞれがｋi個のモデル点を含む、ｎ個の部分に分割される。
【００４８】
グローバル測量は、下記式によって既定され、
【００４９】
【数６】
0004825253.tif 000007
【００５０】
これは、指数ｉにより規定された各部分について計算された、局所的一致スコア値の組み合わせを意味する。
【００５１】
局所的一致測量値は、下記式によって既定される。
【００５２】
【数７】
0004825253.tif 000008
【００５３】
ここで、ｉｊの組は、どのモデル点がどの部分の中にあるかを示す指数を規定し、各部分はｋi個の点を有する。ｒijおよびｃijは、モデル座標系における各モデル点の行および列の変位である。局所的変換値Ｔlは、モデルの形を変えるために用いられる。一般的に、これらは、小さな効果、例えば、各方向における１画素の変換を有するユークリッド変換である。上付き文字ｍおよびｓは、ｄが、モデルの方向ベクトルであるか、または、検索画像におけるそれぞれの位置の方向ベクトルであるかを規定している。
【００５４】
各ポーズの取りうる位置において、各部分は、米国特許第７，０６２，０９３号明細書に記載された測量と同様の測量によって得られた、独立のスコア値を有する。測量値は、各部分について、元のアフィン位置近傍の範囲に対して評価される。局所的近傍における最大スコアが、その部分の最適値として取得される。グローバル測量値は、各部分におけるモデル点の数によって正規化された、局所的測量値の結果を、合計することによって得られる。発明の範囲において、前記測量値から異なる様々な測量値が導出される。発明の様々な形態として、各部分について、その部分より大きくならないように閾値が設定されうる。それ以外の場合には、前記部分は遮蔽され、その結果、さらなる処理が行われないものとされる。
【００５５】
【数８】
0004825253.tif 000009
【００５６】
他の好ましい態様は、部分の大きさがそれぞれ異なる場合である。ここでは、各部分に含まれるモデル点の量により、各部分の影響を測定する。
【００５７】
一般的なアフィン変換の集合についてのグローバルスコア値により、厳密な変形量が既知でない場合においても、オブジェクトのおおよその位置が定まる。さらに、対比の反転に対して不変とするために、局所的スコア測量値からの極性情報を採用しないこともある。この場合には、モデルの方向ベクトルおよび局所的測量における画像点の方向ベクトルの、正規化された内積の合計の絶対値または絶対値の合計を用いる。
【００５８】
各部分の最適値を得たことにより、スコア値だけでなく変形量の推定値も得られる。これらは、最大局所的スコアを規定する、局所的変換値Ｔlである。各部分について局所的変位を得た後、各非線形モデルを適合させる。モデル点がない位置についても、滑らかな変形量を計算することができる。変形の一例を図６に示す。部分４０２の中心を、位置６０３の近傍に移動する。これらの点について非線形変換を行い、元の固定された空間（グリッド６０１として概略的に図示）を、変形された空間６０２に変換する。
【００５９】
これが、当該技術における周知の問題であり、関数補間や近似による様々な解決策が提案されてきた。ここで、本発明の一つの特徴は、関数点や適合度、例えば、各点についての透視変換として、各部分の局所的変位のみを用いることである。これは、例えば、直接的線形変換方法によって行われる（Ｈａｒｔｌｅｙ  ａｎｄ  Ｚｉｓｓｅｒｍａｎ  ２０００）。モデルが固定されていると仮定すれば、リーベンバーグ・マルカルト・アルゴリズムのような強い反復非線形最小化により、三次元ポーズを直接適合できる。変形可能なモデルの場合、スプライン関数は、変位によって規定される。このスプライン関数は、たとえば、Ｂスプライン関数または薄板スプライン関数である。これらの関数の係数は、直接的な方法によって計算される。しかしながら、例えば、薄板スプライン関数を用いた場合、歪みの係数を得るためには、非常に大きな線形システムを反転させなければならない。したがって、他の好ましい態様においては、モデル点の変形によって規定される、調和補間法が用いられる。ここで、モデル点の変位は、行方向および列方向における歪みを表わす、２つの画像中に挿入される。その後、モデル点が位置しない領域について、調和修復と呼ばれる方法によって変形が修復される（Ａｕｂｅｒｔ，Ｇ  ａｎｄ  Ｋｏｒｎｐｒｏｂｓｔ，Ｐ．，Ｍａｔｈｅｍａｔｉｃａｌ  Ｐｒｏｂｌｅｍｓ  ｉｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ：Ｐａｒｔｉａｌ  Ｄｉｆｅｒｅｎｔｉａｌ  Ｅｑｕａｔｉｏｎｓ  ａｎｄ  ｔｈｅ  Ｃａｌｃｕｌｕｓ  ｏｆ  Ｖａｒｉａｔｉｏｎｓ（ｓｅｃｏｎｄ  ｅｄｉｔｉｏｎ），ｖｏｌｕｍｅ  １４７  ｏｆ  Ａｐｐｌｉｅｄ  Ｍａｔｈｅｍａｔｉｃａｌ  Ｓｃｉｅｎｃｅｓ．Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ．２００６）。歪みを非常に滑らかにするためには、変位を、モデル点の元の領域中に伝え戻す。したがって、補間関数だけでなく近似関数も得られる。この方法の利点は、実行時間が、オブジェクトの大きさに対して一次的にのみ依存し、例えば、薄板スプラインに関するアンカー点の数に対して三次的には依存しないことである。
【００６０】
特に厳密な変形については、１つのステップで変形量を抽出できないことがしばしばある。変形マッピングを得ると、全てのモデル点とそれぞれの方向とが、変換される。この変換されたモデルによって、今度は、局所的変位について、モデルのそれぞれのサブ・プルーラリティーが独立的に再度検索される。これにより、小さな変位が定まり、収束に至るまで評価されたモデルを適合する、ループが得られる。一般的に、収束の判断は、変位が既定の閾値未満になったかどうかを調べることにより、行われる。
【００６１】
閾値より大きく、極大値であるグローバルインスタンスの既定範囲について、位置、スコアおよび変位情報と共に、オブジェクトの前提条件をリストに入力し、より低いピラミッドレベルにおいて、これらをさらに評価する。好ましい態様においては、グローバルスコア値の閾値だけでなく、最高ピラミッドレベルにおいて生成した前提条件の最大数も設定する。ここで、すべての前提条件が、それらのスコア値に基づいて分類され、さらに処理に供される最も一致する固定数の候補のみが、前提条件のリスト中に入力される。
【００６２】
特定のピラミッドレベルにおける、モデルの厳密な位置および変位が一旦定まると、変形量は、ピラミッドの下方の次のピラミッドレベルに伝えられなければならない。これは、より低いレベルにおいて、局所的変形量の小さな検索範囲だけを評価するために重要である。好ましい態様においては、より低いレベルからの元のアフィンモデルは、帰納的細区分により、より高いピラミッドレベルに変換される。すでに抽出された、より高いレベルの変形量はモデルに適用され、現在変換された、より低いレベルからのモデルは、逆に、元のピラミッドレベルに変換される。このレベルにおける検索は、より高いピラミッドレベルの変形量に応じて変換された、モデルのインスタンスによって開始される。
【００６３】
この前提条件の画像ピラミッドの下方へのトラッキングは、最低ピラミッドレベルに達するまで行われる。最低ピラミッドレベルにおいて、元の画像より高い解像度でも変位が定まる。したがって、前記部分は画素以下の精度の位置でインスタンス化され、対応する極大エッジの振幅は画像内に定まる。ここで、前記部分の変位は、勾配方向によってではなく、勾配振幅によって既定される。前記手法の後、非常に高い精度まで変形関数を適合させるために、小さな変位が用いられる。一旦最低レベルにおいて前記オブジェクトが検出されると、位置、ポーズおよび変形関数が戻される。さらに、グローバルスコア関数の値が戻され、オブジェクトがどれだけうまく検出されたかの目安が、ユーザに与えられる。
【００６４】
なお、上述の方法は、図７に示すような構成を有するコンピュータシステムによって実施することもできる。図７に示すシステムは、コンピュータによって構成されるシステムであって、
（ａ）モデルオブジェクトの画像を、電子メモリ（７０２）に取得する手段（７０１）と、
（ｂ）前記モデルオブジェクトの画像を、検索スペースの帰納的な細区分と一致し、少なくとも前記オブジェクトの画像を含む多重レベル表示に変換する手段（７０３）と、
（ｃ）前記検索スペースの離散化の各レベルについて、前記モデルオブジェクトの、少なくとも１つの事前に計算されたモデルを生成する手段であって、前記事前に計算されたモデルが、対応する方向ベクトルを有する複数のモデル点からなり、前記モデル点および前記方向ベクトルが、方向ベクトルを前記各モデル点に戻す画像処理操作によって生成する手段（７０４）と、
（ｄ）複数の部分中に、前記複数のモデル点の細区分を生成する手段であって、前記部分を変換することにより、前記モデルの変形されたインスタンスが表わされる手段（７０５）と、
（ｅ）検索画像を電子メモリに取得する手段（７０６）と、
（ｆ）前記検索画像を、前記検索スペースの帰納的な細区分と一致し、少なくとも前記検索画像を含む多重レベル表示に変換する手段（７０７）と、
（ｇ）少なくとも１つの事前に計算されたモデルが検索されるべき変換範囲に対応する、前記検索画像中のモデル点の部分集合に、方向ベクトルを戻す画像処理操作を、多重レベル表示の変換された各画像に対して行う手段（７０８）と、
（ｈ）局所的測量の結果を組み合わせて、グローバル一致測量値を計算する手段であり、前記局所的測量のために、前記事前に計算されたモデルに近い変換の制限された範囲内において、前記モデルの前記部分を検索し、各部分の極大適合度を、グローバル一致測量値に対する、前記部分の寄与として取得する手段（７０９）と、
（ｉ）一致測量値がユーザにより選択可能な閾値より大きく、局所的極大である、これらのモデルポーズを決定し、かつ、前記検索スペースの最も疎な離散化レベルにおける、少なくとも１つの事前に計算されたモデルのインスタンスのリストを、前記モデルポーズから作成する手段（７１０）と、
（ｊ）前記部分の局所的変位を表わす変形変換値を計算する手段（７１１）と、
（ｋ）前記検索スペースの前記最も疎な離散化レベルにおいて、前記検索スペースの帰納的な細区分を通じ、最も密な離散化レベルに至るまで、前記少なくとも１つの事前に計算されたモデルの前記インスタンスをトラックする手段（７１２）と、
（ｌ）各レベルにおいて、前記変形変換値をそれぞれ計算し、かつ、前記変形変換値を次のレベルに伝える手段（７１３）と、
（ｍ）前記モデルポーズ、および、前記最も密な離散化レベルにおける前記モデルオブジェクトのインスタンスの変更変換値を定める手段（７１４）と、
（ｎ）検出領域を平坦化する手段（７１５）とを含む。
【００６５】
本発明の幾つかの特定の態様が、詳細に記載されているのに対し、好ましい態様については、発明の範囲内で様々な改変を行うことができる。したがって、特許請求の範囲において示された発明以外が、上記内容によって制限されることを意図しない。
【図面の簡単な説明】
【００６６】
【図１】図１は、本発明の好ましい態様における、方法の工程を示すフローチャートである。
【図２】図２は、オブジェクトの画像、および、モデル生成にかかるオブジェクト周辺の対象領域を示す図である。
【図３ａ】図３ａは、オブジェクトが平坦な表面上にある場合における、モデル生成を示す図である。
【図３ｂ】図３ｂは、オブジェクトが較正板によって遮蔽された場合における、モデル生成を示す図である。
【図４ａ】図４ａは、エッジフィルターにより生成したモデル点の群の図である。
【図４ｂ】図４ｂは、モデル点を複数の部分に細区分する例を示す図であり、モデルの中心、および、モデルの中心への部分の相対的な変換を表わす。
【図４ｃ】図４ｃは、部分の近傍する局所的な移動による、モデルの典型的な変形を示す図である。
【図５】図５は、オブジェクトの変形された２つのインスタンスと、モデルの検出された２つのインスタンスによるオブジェクト検出の結果とを含む、現在の画像を示す図である。
【図６】図６は、変形マッピングのサンプル点が部分の中心にある場合における、変形関数の適合により生成した、固定されたテンプレートと変形されたテンプレートとの間における、変形マップを示す図である。
【図７】図７は、図１〜６の方法を実施するオブジェクト認識システムの、概略ブロック図である。
【図８】図８は、図１〜６の方法を実施するために、コンピュータ可読媒体を用いた、コンピュータの概略ブロック図である。
【図１】
0004825253.tif 000010
【図２】
0004825253.tif 000011
【図３ａ】
0004825253.tif 000012
【図３ｂ】
0004825253.tif 000013
【図４ａ】
0004825253.tif 000014
【図４ｂ】
0004825253.tif 000015
【図４ｃ】
0004825253.tif 000016
【図５】
0004825253.tif 000017
【図６】
0004825253.tif 000018
【図７】
0004825253.tif 000019
【図８】
0004825253.tif 000020