JP6612822B2 - モデルを修正するためのシステムおよび方法 - Google Patents

Description

発明の分野
本発明は、一般的に機械視覚システムに関し、より具体的に、画像内の対象物の視覚認識および連続画像内の対象物の視覚追跡に関する。

発明の背景
通常、画像における特定の２Ｄ対象物テンプレートの高速、ロバストおよび精確な位置特定は、多くのコンピュータ視覚応用、特に機械視覚応用の必要条件である。例えば、ピック＆プレース応用の場合、対象物認識方法は、撮影された対象物の位置を決定しなければならない。対象物の位置が得られた場合、撮影装置の既知の幾何学的配置に関連して、当該技術分野において周知の方法で、対象物のポーズを計算することができる。ポーズを取得した場合、ロボットは、例えばコンベヤベルトから対象物を掴むことができる。対象物を視覚追跡する場合、対象物認識方法は、連続画像内の対象物の位置を決定しなければならない。例えば、画像に基づく視覚サーボ制御の場合、対象物の位置を用いて、ロボットの動きを制御することができる。交通監視の場合、対象物認識方法は、ビデオストリームまたは連続画像内の交通関係者、例えば自動車または歩行者を検出しなければならない。

当該技術分野では、画像内の対象物の位置を決定するいくつかの方法が提案されている。これらの方法の大半は、可能なマッチングモデルポーズのセットと画像との間の類似性を比較する。類似性指標に対して閾値を超え且つ極大である位置が、対象物の位置として選択される。

使用された類似性指標に応じて、不良な撮影条件に対する一定の不変性が得られる。例えば、正規化相関を類似性指標として使用する場合、モデル画像と検索画像との間の線形濃淡値変化に対する不変性が得られる。

当該技術分野の多くの方法は、複数のモデル点からなるマッチングモデル、例えば、チャンファマッチング（Chamfer Matching）に基づく手法（Borgefors，１９８８）、ハウスドルフ距離（Hausdorff Distance）に基づく手法（Rucklidge，１９９７およびKwonら，２００１）、または幾何学ハッシング（geometric hashing）に基づく手法（LamdanおよびSchwartz，１９９０）に基づいた手法によって、対象物の２Ｄテンプレートを表す。モデル点は、エッジまたは角点などのような低密度の特徴点のセットもしくは２Ｄ対象物テンプレートを覆う高密度の特徴点のセットのいずれかである。可能なマッチングモデルポーズと画像との間の類似性は、マッチングモデル点のサブセットと画像との類似性に基づいて決定される。他の方法は、モデル点および方向を用いて、モデルと画像とのマッチングを行う。方向は、例えば方向ベクトルまたは角度によって表すことができる。当該技術分野において、方向を使用する対象物認識方法の一般的な例として、汎用化ハフ変換（Ballard，１９８１およびUlrichら，２００３）に基づく手法、または修正したハウスドルフ距離（OlsonおよびHuttenlocher，１９９７）に基づく手法が挙げられる。さらに、部分排除、クラッタおよび非線形明暗変化に対して不変である、画像の正規化された方向とモデル特徴との点乗積を類似性指標として使用する手法も挙げられる（ＥＰ１１９３６４２、ＥＰ１３９４７２７、ＥＰ２０８１１３３およびＥＰ２０４８５９９）。他の手法は、角度を用いてマッチングを行い、モデル点は、例えば個々の点の重みなどの他の属性をさらに含むことができる（例えば、ＵＳ６８５０６４６、ＵＳ７１９０８３４およびＵＳ７０１６５３９）。

一般的には、全てのポーズパラメータの徹底的な検索は、計算上非常に高価であり、殆どのリアルタイム応用に対して不可能である。従来技術の方法の大半は、モデルおよび検索画像の両方から画像ピラミッドを構築することによって、この速度制限を克服する（例えば、Tanimoto（１９８１）またはBrown（１９９２）を参照）。全検索範囲の類似性指標は、最高のピラミッドレベルのみで評価される。より低いレベルでは、最低のピラミッドレベルに達するまで、有望なマッチ候補のみが追跡される。

検索を高速化するもう１つの方法は、検索画像内でモデルに対して実行され得る可能な変換を制限することである。入力点（ｘ，ｙ）^Ｔを出力点（ｘ′，ｙ′）^Ｔにマッピングするアフィン変換は、幾何学的に意味のあるパラメータ表現で記述することができる。

これらのパラメータは、異なる換算係数Ｓ_ｘおよびＳ_ｙ、ｘ軸に対するｙ軸のスキュー変換、すなわち、ｘ軸を固定しながら角度θでｙ軸の回転、角度φで両軸の回転、およびベクトル（ｔ_ｘ，ｔ_ｙ）^Ｔでの並進を用いて、元のｘ軸およびｙ軸の拡大縮小を記述する。典型的には、対象物認識システムは、縮小したサブセット、例えば並進および回転のパラメータのみを評価する。さらに、パラメータは、ある程度に固定された範囲、例えば縮小した回転範囲に制限される。これによって、対象物認識システムが最高のピラミッドレベルでチェックしなければならない可能なポーズの区域を縮小して、検索を高速化する。場合によって、発見しなければならない対象物は、アフィン変換または部分アフィン変換よりも一般的な変換に従って変換される。このような変換の２つの例として、透視変換および非線形変形が挙げられる。

従来の対象物認識方法は、対象物の位置を特定するためのモデルが不変なものであると見なす。いくつかの手法は、モデル点のある程度の変化を許容するが（例えば、Cootes(1995)を参照）、捜索画像内の対象物の位置を特定した後にモデルを修正（adapt）しない。このような手法は、位置を特定する対象物が外観を変える場合に、いくつかの欠点がある。２つの共通のコンピュータ視覚応用および機械視覚応用は、一連の画像を通じて対象物の位置を特定する視覚追跡と、変形可能な対象物の位置特定とである。対象物の位置特定が成功した後のモデルの修正（adaption）は、将来の画像における位置特定の質を改善する。

視覚追跡のシナリオにおいて、殆どの対象物は３Ｄであり、３Ｄ空間における対象物の動きおよび回転は、一般に、多くの２Ｄ対象物認識手法の前提とするアフィン変換で対応できない。位置を特定する対象物の点に基づくマッチングモデルを、アフィン変換または部分アフィン変換よりもより一般的な変換に修正することは、未解決の問題である。

EP1193642: System and method for object recognition EP1394727: Hierarchical component-based object recognition EP2081133: System and method for deformable object recognition EP2048599: System and method for 3D object recognition US6850646: Fast high-accuracy multi-dimensional pattern inspection US7190834: Methods for finding and characterizing a deformed pattern in an image US7016539: Method for fast, robust, multi-dimensional pattern recognition

D. H. Ballard: Generalizing the Hough transform to detect arbitrary shapes. Pattern Recognition, 13(2): 111-122, 1981. G. Borgefors: Hierarchical chamfer matching: A parametric edge matching algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(6): 849-865, Nov., 1988. Brown, Lisa Gottesfeld. "A survey of image registration techniques." ACM computing surveys (CSUR) 24(4): 325-376 (1992). Cootes, Timothy F., et al. "Active shape models-their training and application."Computer vision and image understandin 61.1 (1995): 38-59. O.-K. Kwon, D.-G. Sim, R.-H. Park: Robust Hausdorff distance matching algorithms using pyramidal structures. Pattern Recognition, 34: 2005-2013, 2001. Y. Lamdan, J.T. Schwartz, H.J. Wolfson: Affine invariant model-based object recognition. IEEE Transactions on Robotics and Automation, 6(5): 578-589, Oct. 1990. O. F. Olson, D. P. Huttenlocher: Automatic target recognition by matching oriented edge pixels. IEEE Transactions on Image Processing, 6(1): 103-113, Jan. 1997. W. J. Rucklidge: Efficiently locating objects using the Hausdorff distance. International Journal of Computer Vision, 24(3): 251-270, 1997. Tanimoto, Steven L. "Template matching in pyramids."Computer Graphics and Image Processing 16.4 (1981): 356-369. M. Ulrich, C. Steger, and A. Baumgartner: Real-time object recognition using a modified generalized Hough transform, Pattern Recognition, 36(11): 2557-2570, 2003. Carsten Steger, Markus Ulrich, Christian Wiedemann: Machine Vision Algorithms and Applications. Wiley-VCH, Weinheim, 2007.

本発明の目的は、対象物の外観が変化しても、ロバスト認識を保証するように、点に基づくマッチングモデルを修正するための一般的な手法を提供することである。

発明の概要
本発明は、特許請求の範囲に記載される。本発明は、画像内の対象物のポーズを決定するために使用することができるマッチングモデルを修正（adapt）するための方法および装置に関する。モデルの修正（adaption）は、画像内の対象物の外観に基づく。本発明はまた、記載の方法を実行および／または実施するシステムまたは装置に関連する。

本発明は、対象物のマッチングモデルを用いて電子画像内の対象物を探し出し、元のマッチングモデルと画像の検出結果との間の差に基づいてマッチングモデルを修正するためのシステムおよび方法を提供する。例えば、対象物の外観が経時的に変化し得る場合、このような方法を用いて、ビデオシーケンスの複数のフレームに亘って、対象物を追跡することができる。対象物の外観は、対象物の変形、照明の変化、視点の変化などの複数の理由によって変化する可能性がある。これらの変化によって、元のマッチングモデルは、最初のフレーム内の対象物を良く表現できるが、後のフレームによく表現できなくなる場合がある。対象物の外観の変化が常に事前に予測できないため、ユーザは、全てのフレームに亘って対象物の外観を表すマッチングモデルを提供できない場合がある。したがって、外観は、最初のフレームしか与えられない。本発明は、前のフレームの結果に基づいてマッチングモデルを動的に調整する方法を提供する。これによって、対象物の外観が変化しても、後のフレーム内の対象物を探し出すことができる。

好ましくは、この方法は、４つの主な段階、すなわち、マッチング段階、変換段階、対応検索段階、および修正段階を含む。

マッチング段階では、複数の点からなる対象物のマッチングモデルおよび対象物を含む電子画像が与えられた場合、マッチングモデルを用いて、電子画像内の対象物のポーズを決定する。変換段階では、決定されたポーズを用いて、マッチングモデルを変換することによって、変換後モデルを生成する。対応検索段階では、電子画像において、変換後モデルの少なくとも１つの点に対応する対応点を決定する。修正段階では、少なくとも１つの決定された対応点に従って、モデルを修正する。

第１態様によれば、本発明は、請求項１に記載の方法を提供する。
好ましくは、修正段階では、マッチングモデルの複数の点の位置が修正される。

好ましくは、マッチング段階では、マッチングモデルの複数の点を用いて、対象物のポーズを決定する。

上述した第１態様の特徴と任意に組み合わせることができるさらに好ましい実施形態において、マッチングモデルは、複数の点および方向からなり、修正段階におけるマッチングモデルの修正は、マッチングモデルの複数の点の位置および方向を修正することを含む。好ましい実施形態において、方向は、方向ベクトルによって表される。さらに好ましい実施形態において、方向は、角度によって表される。代替の実施形態において、方向は、離散的な方向または角度範囲のビットマップによってまたは他の手段によって表すことができる。

上述した第１態様の特徴および上述した好ましい実施形態の特徴と任意に組み合わせることができるさらに好ましい実施形態において、マッチング段階では、方向の表示に関わらず、マッチングモデルの複数の点および方向を用いて、対象物のポーズを決定する。

さらに好ましくは、方向ベクトルで方向を表す場合、マッチング段階では、マッチングモデルの複数の点および方向ベクトルを使用して、方向ベクトルの点乗積を計算することによって、対象物のポーズを決定する。

修正段階においてマッチングモデルの複数の点の位置を修正する場合、好ましくは、マッチングモデルの複数のモデル点の位置を対応点の位置に設定する。代替の実施形態において、マッチングモデルの複数のモデル点の位置を、マッチングモデルの点の位置と対応点の位置との関数である位置に設定することができる。

マッチングモデルが複数の点および方向からなり、修正段階におけるマッチングモデルの修正がマッチングモデルの複数の点の位置および方向を修正することを含む場合、好ましくは、マッチングモデルの複数の点の位置および方向を修正する時に、マッチングモデルの複数の点および方向は、対応点の位置および方向に設定される。代替の実施形態において、マッチングモデルの複数のモデル点の位置および方向は、マッチングモデルの位置および方向と対応点の位置および方向との関数である位置および方向に設定される。

上述した第１態様の特徴と任意に組み合わせることができる別の好ましい実施形態において、マッチング段階、変換段階、対応検索段階および修正段階は、少なくとも２回の反復で繰り返して実行され、修正段階から得られた修正後マッチングモデルは、次の反復のマッチングモデルとして機能する。

上述した第１態様の特徴および上述した好ましい実施形態の特徴と任意に組み合わせることができる別の好ましい実施形態において、複数のモデルレベルにより構成され、各モデルレベルは、複数の点、および必要に応じて複数の方向により構成される。マッチング段階では、電子画像の画像ピラミッドが生成され、この画像ピラミッドは、複数の画像レベルにより構成される。対象物のポーズは、より低い解像度を有するピラミッドレベル（画像ピラミッドの画像レベル）に対応するモデルレベルを用いて、より低い解像度を有するピラミッドレベルで決定される。より低い解像度を有するピラミッドレベルで決定された対象物のポーズは、より高い解像度有するピラミッドレベルに対応するモデルレベルを用いて、より高い解像度で精緻化される。変換段階、対応検索段階および修正段階は、各ピラミッドおよびモデルレベルに対して別々に実行され、修正後マッチングモデルを生成する。

上述した第１態様の特徴および上述した好ましい実施形態の特徴と任意に組み合わせることができる別の好ましい実施形態において、対象物のマッチングモデルは、複数のモデルレベルにより構成されたモデルであり、各モデルレベルは、複数の点、および必要に応じて複数の方向により構成される。マッチング段階では、電子画像の画像ピラミッドが生成され、この画像ピラミッドは、複数の画像レベルにより構成される。対象物のポーズは、より低い解像度を有するピラミッドレベルに対応するモデルレベルを用いて、より低い解像度を有するピラミッドレベルで決定される。より低い解像度を有するピラミッドレベルで決定された対象物のポーズは、より高い解像度有するピラミッドレベルに対応するモデルレベルを用いて、高い解像度で精緻化される。変換段階、対応検索段階および修正段階は、より高い解像度を有するピラミッドレベルで実行され、より高い解像度を有するモデルレベルの修正を生成する。方法は、以下の追加のステップ、すなわち、より高い解像度を有するモデルレベルの修正をより低い解像度を有するモデルレベルに供給することによって、各レベルで修正後マッチングモデルを生成するステップを含む。

上述した第１態様の特徴および上述した好ましい実施形態の特徴と任意に組み合わせることができる別の好ましい実施形態において、上述した実施形態のいずれかに基づいて、対応検索段階は、電子画像において、変換後モデルの少なくとも１つの点の近隣区域内で対応点を検索することを含む。

上述した第１態様の特徴および上述した好ましい実施形態の特徴と任意に組み合わせることができる別の好ましい実施形態において、上述した実施形態のいずれかに基づいて、対応検索段階は、電子画像において、変換後モデルの少なくとも１つの点の近隣区域内で対応点を検索することを含み、近隣区域は、点の方向によって決定される。

上述した第１態様の特徴および上述した好ましい実施形態の特徴と任意に組み合わせることができる別の好ましい実施形態において、修正段階は、決定された対応点のサブセットに従って、マッチングモデルを修正することを含む。

上述した第１態様の特徴および上述した好ましい実施形態の特徴と任意に組み合わせることができる別の好ましい実施形態において、マッチング段階、変換段階、対応検索段階、および修正段階は、少なくとも２回の反復で繰り返して実行され、修正段階では、マッチングモデルは、少なくとも１回の過去の反復または現在の反復に決定された少なくとも１つの対応点に従って修正され、修正段階から得られた修正後マッチングモデルは、次の反復で入力マッチングモデルとして機能する。

本発明は、添付の図面と併せて、以下の詳細な説明からより完全に理解されるであろう。

マッチングモデルの点を示す図である。 対象物の電子画像を示す図である。 変換後モデルの点を示す図である。 電子画像において、変換後モデルの点の近隣区域内の対応点の決定を示す図である。 変換後モデルの全ての点に対応する電子画像内の対応点を示す図である。 マッチングモデルのモデル点の位置を対応点の位置に設定した後の修正後マッチングモデルを示す図である。 マッチングモデルのモデル点の位置を、マッチングモデルの点の位置および対応点の位置の関数（ここでは、関数は、線形補間を記述する）である位置に設定した後の修正後マッチングモデルを示す図である。 マッチングモデルの点および方向を示す図である。 変換後モデルの点および方向を示す図である。 電子画像において、変換後モデルの点の近隣区域（近隣区域は、点の方向によって決定される）内の対応点の決定を示す図である。 変換後モデルの全ての点に対応する電子画像内の対応点および方向を示す図である。 モデル点の位置および方向を対応点の位置および方向に設定した後の修正後マッチングモデルを示す図である モデル点の位置および方向を、マッチングモデルの点の位置および方向と対応点の位置および方向との関数（ここでは、関数は、線形補間を記述する）である置および方向に設定した後の修正後マッチングモデルを示す図である。

好ましい実施形態の詳細な説明
以下のデータは、全て電子形式、好ましくはデジタル形式で入手可能であると想定されている。記載された方法およびアルゴリズムは、電子形式であって、コンピュータで実施できるものと見なされる。

本発明は、画像内の対象物のポーズを決定するために使用することができるマッチングモデルを修正するための方法および装置に関する。モデルの修正は、画像内の対象物の外観に基づく。

本発明は、マッチングモデル（図１を参照）が提供されていると見なす。このマッチングモデルは、いくつかの利用可能なマッチング手法のうちの１つを使用することによって、電子画像内の対象物のポーズを決定することができる。ポーズは、例えば、画像内の対象物の位置（例えば、行座標および列座標）であってもよい。対象物が異なる向きで現れる場合、ポーズは、画像内の対象物の向き（例えば、角度）を含む。さらに、画像内の対象物の規模が未知の場合、ポーズは、対象物の規模（例えば、倍率）を含む。場合によって、対象物のアスペクト比が変更できる場合、ポーズは、２つの異なる倍率を含む。最後に、いくつかの応用において、ポーズは、一般的なアフィン変換のパラメータ、または最も一般的な場合の射影変換のパラメータを含んでもよい。

本発明の好ましい実施形態において、マッチングモデルは、複数のモデル点（１０１）により構成される。モデル点は、例えば、対象物の境界もしくは対象物上の紋様または構造物の濃淡値エッジまたは色彩エッジを記述することができる。エッジは、典型的には、濃淡値エッジまたは色彩エッジを抽出する元となる対象物のモデル画像から計算される。このために、異なるエッジ抽出方法を使用することができる（例えば、Stegerら、２００７、章３．７を参照）。他の応用において、モデル点は、対象物のＣＡＤモデルから抽出される。図１は、正方形の対象物のモデル点を示している。

また、本発明は、対象物の電子画像（２０１）が提供されていると見なす。本発明の好ましい実施形態において、カメラを用いて、画像を取得する。図２の画像には、対象物は、マッチングモデルとは異なる向きで現れる。この具体的な図示例において、ポーズは、画像内の対象物の位置（行、列）および向き（角度）を含む。また、留意すべきことは、画像内の対象物の形状は、マッチングモデルに比べて僅かに変化していることである。本発明の第１ステップにおいて、画像内の対象物（２０２）のポーズが決定される。この目的のために、本発明の好ましい実施形態において、モデル点を用いてマッチングを行うマッチング手法が適用される。点より構成されたマッチングモデルに基づいて画像内の対象物のポーズを決定することができるいくつかのマッチング手法が利用可能である（Stegerら，２００７，章３．１１．５）。いくつかの選択例は、チャンファマッチング（Chamfer Matching）（Borgefors，１９８８）、ハウスドルフ距離（Hausdorff Distance）（Rucklidge，１９９７またはKwonら，２００１）および幾何学ハッシング（geometric hashing）（Lamdan，１９９０）を含む。マッチングが成功した場合、マッチング手法は、画像内の対象物のポーズを返す。

本発明の次のステップにおいて、マッチングモデルは、マッチング手法によって返されたポーズに従って変換される（図３を参照）。図示された応用例において、ポーズに従って、モデル点に並進および回転を適用することによって、モデル点（１０１）を変換して、変換後モデルの点（３０２）を生成する。説明の目的のために、図３および以下の図において、画像内の対象物の境界エッジ（３０１）のみは視覚化される。本発明の他の応用例において、モデル点は、画像内の対象物に適用できる変換に応じて、例えば倍率、アフィン変換、または射影変換を適用することによって変換される。

本発明の次のステップにおいて、変換後モデルの点（３０２）に対応する画像（２０１）内の対応点（４０４）を決定する。本発明の１つの好ましい実施形態は、図４に示される。変換後モデルの例示的な選択点（４０１）に対応する画像内の対応点（４０４）が、変換後モデルの点（４０１）の近隣区域内で検索される。１つの好ましい実施形態において、近隣区域は、点（４０１）を中心とする正方形領域（４０２）によって記述される。別の実施形態において、近隣区域は、選択点を中心とする円形領域によって記述される。本発明の範囲から逸脱することなく、他の形状および位置の近隣区域も可能である。本発明の好ましい実施形態において、近隣区域内で対応点の検索は、画像の近隣区域内のエッジ振幅を計算し、近隣区域内で最も大きいエッジ振幅を有する検索画像の点を選択することによって、実施される。代替の実施形態において、非最大排除を実行することによって、検索画像においてエッジ振幅の極大値を持たない点を排除する。別の実施形態において、変換後モデルの点に最も近く、特定の閾値を超えるエッジ振幅を有する近隣区域の点が、選択される。別の代替の実施形態において、変換後モデルの点と最も高い類似性を示す近似領域の点が、選択される。類似性は、例えば、モデル内で濃淡値または色彩情報が利用できない場合に幾何学的特徴、もしくはモデル点に追加の濃淡値または色彩情報を含む場合に濃淡値または色彩特徴に基づいた周知の類似性指標のうちの１つを用いて、評価される。さらに、異なる類似性指標および基準を組み合わせて、対応点を決定することができる。

好ましい実施形態において、変換後モデルの全ての点に対して、画像内の対応点を検索する。代替の実施形態において、検索は、変換後モデルの点のサブセットに制限される。このステップの結果として、複数の対応点が得られる。変換後モデルのいくつかの点に対して、対応点が得られない可能性がある。その理由は、検索が変換後モデルの点のサブセットに限定されているため、もしくは近隣区域に対応点が発見できず、すなわち、閾値を超えるエッジ振幅を有する点または特定の閾値を超える類似性を有する点が発見できなかったためである。図５に図示された応用例において、変換後モデルの各点（例えば、（４０１）、（５０１）および（５０３））に対して、発見された対応点（例えば、（４０４）、（５０２）、および（５０４））は、画像に表示されている。

本発明の最後のステップにおいて、マッチングモデルは、決定された対応点に従って修正される。このために、変換後モデルを得るためにマッチングモデルに適用した変換の逆変換を適用することによって、対応点をマッチングモデルの座標系に変換する。逆変換された対応点（例えば、（６０１）、（７０１））は、図６および７に視覚化される。本発明の好ましい実施形態において、マッチングモデルを修正するために、モデルの点は、（逆変換された）対応点の位置に設定される。得られた修正後マッチングモデルの点（例えば、（６０２））は、図６に視覚化される。本発明の別の好ましい実施形態において、モデルの点は、マッチングモデルの１つ以上の点の位置と（逆変換された）１つ以上の対応点の位置との関数である位置に設定される。得られた修正後マッチングモデルの点（例えば、（７０２））は、図７に視覚化される。好ましい実施形態において、上記関数は、モデル点の位置および（逆変換された）対応点の位置を線形補間する。０〜１の間の浮動値である補間係数を用いて、モデルの修正度合いを制御することができる。補間係数が０の場合、モデルの修正は、行われない。補間係数が１の場合、モデルの点は、（逆変換された）対応点の位置に設定される。例えば、補間係数が０．５の場合、モデルの点は、元のモデル点の位置と（逆変換された）対応点の位置との中心に設定される。代替的に、本発明の範囲から逸脱することなく、他の補間関数を適用することができる。

本発明の代替の実施形態において、マッチングモデルの点のサブセットおよび対応点のサブセットのみを用いて、修正後マッチングモデルの点の位置を計算する。例えば、マッチングモデルの点のサブセットおよび対応点のサブセットを用いて、反り関数のパラメータを計算することができる。反り関数の入力は、マッチングモデルの点の位置であり、反り関数の出力は、修正後マッチングモデルの対応点の位置である。反り関数を用いて、修正後マッチングモデルの全ての点の位置またはサブセットの点の位置を計算することができる。

本発明の別の好ましい実施形態において、マッチングモデルは、複数のモデル点（８０１）および方向（８０２）により構成される。方向は、例えば、方向ベクトル、正規化された方向ベクトルまたは角度によって表すことができる。これらの方向は、典型的には、濃淡値または色彩エッジを抽出する対象物のモデル画像から計算される。その後、抽出されたエッジのエッジ方向または勾配方向から、方向を取得する。このために、エッジ方向または勾配方向を直接計算することのできる異なるエッジ抽出方法を使用することができる（例えば、Stegerら，２００７，章３．７を参照）。代替的には、そのような計算を行うことがないエッジ抽出方法を使用することもできる。この場合、エッジ方向または勾配方向は、後処理ステップで、隣接するエッジ点を連結することによって計算することができる。連結されたエッジ点は、エッジ方向を定義する。他の応用において、モデル点は、対象物のＣＡＤモデルから抽出される。この場合、ＣＡＤモデルから方向を計算することもできる。この場合に、方向は、ＣＡＤモデルに格納されている輪郭の方向から取得される。図８に示され応用例において、方向は、正規化された勾配ベクトル（８０２）によって表される。

本発明の別の好ましい実施形態において、画像（２０１）内の対象物（３０１）のポーズを決定するために使用されたマッチング手法は、モデル点および方向を使用して、マッチングを行う。点より構成されたマッチングモデルに基づいて画像内の対象物のポーズを決定することができるいくつかのマッチング手法が利用可能である（Stegerら，２００７，章３．１１．５）。いくつかの選択例は、一般化ハフ変換（Ballard，１９８１およびUlrich，２００３）、方向を計算に入れることのできる修正したハウスドルフ距離（OlsonおよびHuttenlocher，１９９７）、方向ベクトルの点乗積に基づく手法（ＥＰ１１９３６４２、ＥＰ１３９４７２７、ＥＰ２０８１１３３およびＥＰ２０４８５９９）、およびＵＳ６８５０６４６、ＵＳ７１９０８３４およびＵＳ７０１６５３９に記載されているように角度を使用してマッチングを行う手法を含む。マッチングが成功した場合、マッチング手法は、画像内の対象物のポーズを返す。

本発明の次のステップにおいて、点および方向を含むマッチングモデルは、マッチング手法によって返されたポーズに従って変換される（図９を参照）。図示された応用例において、ポーズに従って、モデル点に並進および回転を適用することによって、マッチングモデルの点（８０１）および方向（８０２）を変換して、変換後モデルの点（３０２）および方向（９０１）を生成する。本発明の他の応用例において、点および方向は、画像内の対象物に適用できる変換に応じて、例えば倍率、アフィン変換、または射影変換を適用することによって変換される。

本発明の次のステップにおいて、点および方向を含む変換後モデルの点（１００１）に対応する画像（２０１）内の対応点を決定する。本発明の一実施形態において、対応点の決定は、上述したものと同様に、図４に示すように実行される。変換後モデルの例示的な選択点（４０１）に対応する画像内の対応点（４０４）が、変換後モデルの点（４０１）の近隣区域内で検索される。１つの好ましい実施形態において、近隣区域は、点（４０１）を中心とする正方形領域（４０４）によって記述される。別の実施形態において、近隣区域は、選択点を中心とする円形領域によって記述される。本発明の範囲から逸脱することなく、他の形状および位置の近隣区域も可能である。本発明の好ましい実施形態において、近隣区域内で対応点の検索は、画像の近隣区域内のエッジ振幅を計算し、近隣区域内で最も大きいエッジ振幅を有する検索画像の点を選択することによって、実行される。代替の実施形態において、非最大排除を実行することによって、検索画像においてエッジ振幅の極大値を持たない点を排除する。別の実施形態において、変換後モデルの点に最も近く、特定の閾値を超えるエッジ振幅を有する近隣区域の点が、選択される。別の代替の実施形態において、変換後モデルの点と最も高い類似性を示す近似領域の点が、選択される。類似性は、例えば、モデル内で濃淡値または色彩情報が利用できない場合に幾何学的特徴、もしくはモデル点に追加の濃淡値または色彩情報を含む場合に濃淡値または色彩特徴に基づいた周知の類似性指標のうちの１つを用いて、評価される。マッチングモデルが方向を含む場合、例えば、ＥＰ１１９３６４２、ＥＰ１３９４７２７、ＥＰ２０８１１３３およびＥＰ２０４８５９９に記載された手法のうつの１つに従って、方向を用いて、類似性を計算することができる。この場合、方向は、検索画像の近隣区域で計算される。さらに、異なる類似性指標および基準を組み合わせて、対応点を決定することができる。

図１０に示す代替の実施形態において、変換後モデルの点（１００１）の位置および方向（１００２）を用いて、近隣区域（１００３）を計算する。１つの好ましい実施形態において、近隣区域は、変換後モデルの点（１００１）を中心とし、変換後モデルの方向（１００２）によって決定された向きを有する矩形区域（１００３）によって記述される。代替の実施形態において、近隣区域は、点（１００１）を中心とし、変換後モデルの方向（１００２）によって決定された向きを有する楕円形区域によって記述される。本発明の範囲から逸脱することなく、他の形状および位置の近隣区域も可能である。

近隣区域（１００３）内の対応点（１００４）の検索は、上述した方法のうち１つを用いて実行される。その結果、変換後モデルの点（１００１）に対応する対応点（１００４）が得られる。マッチングモデルが点および方向を含む場合、点（１００１）およびその方向（１００２）に対応する対応点（１００４）およびその方向（１００５）が得られる。

別の好ましい実施形態において、変換後モデルの全ての点および方向に対して、画像内の対応点および方向を検索する。代替の実施形態において、検索は、変換後モデルの点のサブセットに制限される。このステップの結果として、複数の対応点および方向が得られる。変換後モデルのいくつかの点に対して、対応点が得られない可能性がある。その理由は、検索は、変換後モデルの点のサブセットに限定されているため、または近隣区域に対応点が発見できず、すなわち、閾値を超えるエッジ振幅を有する点または特定の閾値を超える類似性を有する点が発見できなかったためである。モデルが方向を含む場合、変換後モデル点の方向および画像内の潜在的な対応点の方向を比較することができる。両者の差が大きすぎる場合、潜在的な対応点は、拒否され、対応点として採用しない。図１１に図示された応用例において、変換後モデルの各点（例えば、（１００１）および（１１０６））および方向（例えば、（１００２）および（１１０７））に対して、発見された対応点（例えば、（１００４）および（１１０８））および対応方向（例えば、（１００５）および（１１０９））は、表示される。

本発明の最後のステップにおいて、点および方向を含むマッチングモデルは、決定された対応点および方向に従って修正される。このために、変換後モデルを得るためにマッチングモデルに適用した変換の逆変換を適用することによって、対応点および方向をマッチングモデルの座標系に変換する。逆変換された対応点（例えば、（１００４））および方向（例えば、（１００４））は、図１２および１３に視覚化される。本発明の好ましい実施形態において、マッチングモデルを修正するために、マッチングモデルの点は、（逆変換された）対応点の位置に設定され、モデルの方向は、（逆変換された）対応点の方向に設定される。得られた修正後マッチングモデルにおける点（例えば、（１２０１））および方向（例えば、（１２０２））は、図１２に視覚化される。

本発明の別の好ましい実施形態において、モデルの点は、マッチングモデルの１つ以上の点の位置と（逆変換された）１つ以上の対応点の位置との関数である位置に設定される。さらに、モデルの方向は、マッチングモデルの１つ以上の点の方向と（逆変換された）１つ以上の対応点の方向との関数である方向に設定される。得られた修正後マッチングモデルの点（例えば、（１３０１））および方向（例えば、（１３０２））は、図１３に視覚化される。好ましい実施形態において、上記関数は、モデル点の位置および（逆変換された）対応点の位置を線形補間する。０〜１の間の浮動値である補間係数を用いて、モデルの修正度合いを制御することができる。補間係数が０の場合、モデルの修正は、行われない。補間係数が１の場合、モデルの点および方向は、（逆変換された）対応点の位置および方向に設定される。例えば、補間係数が０．５の場合、モデルの点は、元のモデル点の位置と（逆変換された）対応点の位置との中心に設定され、モデルの方向は、元のモデル点の方向と（逆変換された）対応点の方向の中間方向に設定される。代替的に、本発明の範囲から逸脱することなく、他の補間関数を適用することができる。

本発明の別の実施形態において、マッチングモデルの点および方向のサブセットおよび対応点および方向のサブセットのみを用いて、修正後マッチングモデルにおける点の位置および方向を計算する。例えば、マッチングモデルの点および方向のサブセットおよび対応点および方向のサブセットを用いて、２つの反り関数、すなわち、位置に関する１つの反り関数および方向に関する１つの反り関数のパラメータを計算することができる。第１反り関数の入力は、マッチングモデルの点の位置であり、第１反り関数の出力は、修正後マッチングモデルの対応点の位置である。第２反り関数の入力は、マッチングモデルの点の方向であり、第２反り関数の出力は、修正後マッチングモデルの対応点の方向である。代替的には、入力がマッチングモデルの点の位置および方向であり、出力が修正後マッチングモデルの対応点の位置および方向である単一の関数を使用することもできる。反り関数を用いて、修正後マッチングモデルの全ての点の位置および方向もしくはサブセット点の位置および方向を計算することができる。

本発明の好ましい実施形態において、修正後マッチングモデルを用いて、後続の画像における対象物のポーズを決定する。修正後マッチングモデルは、モデル修正の第２反復において、入力マッチングモデルとして機能することができる。したがって、一実施形態において、マッチングモデルは、後続の画像に基づいて、および上述の方法のうちの１つを使用することによって再び修正される。別の実施形態において、マッチングモデルは、対象物のポーズを決定する全ての画像において修正ず、各第２または第３画像において修正される。別の代替の実施形態において、モデルは、一定期間が経過した後に修正される。別の代替の実施形態において、マッチングモデルは、一定の基準が満たされた場合、例えばマッチング手法が特定の閾値を下回るマッチングの品質指標を返した場合に、修正される。

本発明の別の代替の実施形態において、マッチング手法は、画像内の対象物の検索を高速化するために、多重解像度法を使用する。多重解像度法の１つの周知実現は、入力画像の画像ピラミッドを生成することである。画像ピラミッドは、複数の画像レベルにより構成され、画像レベルが増加すると、画像の解像度が低下する。この場合、マッチングモデルは、複数のモデルレベルにより構成され、各モデルレベルは、複数の点もしくは複数の点および方向からなる。より高いモデルレベルは、より低い解像度の対象物を表す。一般的には、画像レベルの解像度に対応するモデルレベルを用いて、より高いピラミッドレベル（画像ピラミッドの画像レベル）でマッチングを実行して、対象物のポーズを決定することによって、マッチング候補のポーズを生成する。その後、マッチング候補のポーズは、より低い画像レベルの解像度に対応するモデルレベルを用いて、（より高い解像度を有する）より低いピラミッドレベルで精緻化される。本発明の一実施形態において、モデルの修正は、各ピラミッドレベルで、したがって各モデルレベルに対して別々に実行される。したがって、上述したモデルを修正する方法は、各モデルレベルに適用される。本発明の代替の実施形態において、上述したように、モデルの修正は、（最も高い解像度を有する）最も低いピラミッドレベルのみで実行される。その結果、最高解像度を有するモデルレベルのみが修正される。したがって、最高解像度のモデルレベルの修正は、後続のステップにおいて、より低い解像度のモデルレベルに供給される。異なる解像度レベルにモデルの修正を供給するために、例えばＥＰ２０８１１３３に記載されているように、補間関数を使用することができる。

いくつかの応用において、複数の後続の画像に亘って矛盾しない場合に限り、モデルの修正を適用することが望ましい。これによって、雑音および関連値の異常値に対するロバスト性が増加する。したがって、本発明の代替の実施形態において、修正後マッチングモデルは、モデル修正の複数の後続反復において、入力マッチングモデルとして機能する。しかしながら、マッチングモデルは、潜在的な修正が複数の画像に亘って矛盾しない場合に限り、修正される。例えば、モデル点の対応点が少なくとも２つの連続する画像において右にシフトされた場合に限り、このモデル点を右にシフトする。

図面および前述の説明において、本発明を詳細に例示および説明してきたが、これらの例示および説明は、例示的なものであり、限定的なものではないと考えられるべきである。理解すべきことは、当業者なら、添付の特許請求の範囲内において、変更および修正を行うことができることである。特に、本発明は、記載された異なる実施形態の特徴の組合わせを含むさらなる実施形態を包含する。換言すれば、本発明のいくつかの特定の実施形態を詳細に説明したが、本発明の精神および範囲から逸脱することなく、好ましい実施形態に対するさまざまな変更を行うことができる。したがって、上記の説明は、添付の特許請求の範囲に示された本発明を限定するものではない。

また、特許請求の範囲において、用語「含む」は、他の要素またはステップを除外せず、単数形のものは、複数形のものを排除しない。単一のユニットは、特許請求の範囲に記載されたいくつかの特徴の機能を実行することができる。特許請求の範囲に使用された参照符号は、請求の範囲を限定するものとして解釈されるべきではない。

Claims (18)

1. 対象物のマッチングモデルを修正するための方法であって、
   （ａ）前記対象物の電子画像を提供するステップと、
   （ｂ）前記対象物のマッチングモデルを提供するステップとを含み、前記マッチングモデルは、複数のモデルレベルにより構成されたモデルであり、各モデルレベルは、複数の点、および必要に応じて複数の方向により構成され、
   前記方法は、さらに、
   （ｃ）前記マッチングモデルを使用するマッチング手法を用いて、前記電子画像内の前記対象物のポーズを決定するステップを含み、
   前記ステップ（ｃ）は、
   （ｃ１）前記電子画像の画像ピラミッドを生成するステップを含み、前記画像ピラミッドは、複数の画像レベルにより構成され、
   前記ステップ（ｃ）は、さらに、
   （ｃ２）より低い解像度を有する画像ピラミッドの画像レベルに対応するモデルレベルを用いて、前記より低い解像度を有する画像ピラミッドの画像レベルで前記対象物の前記ポーズを決定するステップと、
   （ｃ３）より高い解像度を有する画像ピラミッドの画像レベルに対応するモデルレベルを用いて、前記より高い解像度を有する画像ピラミッドの画像レベルで前記対象物の前記ポーズを精緻化するステップとを含み、
   前記方法は、さらに、
   （ｄ）前記ポーズに従って、前記マッチングモデルを変換することによって、変換後モデルを生成するステップと、
   （ｅ）前記電子画像において、前記変換後モデルの少なくとも１つの点に対応する対応点を決定するステップと、
   （ｆ）前記決定された少なくとも１つの対応点に従って、前記マッチングモデルを修正するステップとを含み、
   前記ステップ（ｄ）〜（ｆ）は、修正対象である各モデルレベルに対して別々に実行され、修正後マッチングモデルを生成する、方法。
2. 対象物のマッチングモデルを修正するための方法であって、
   （ａ）前記対象物の電子画像を提供するステップと、
   （ｂ）前記対象物のマッチングモデルを提供するステップとを含み、前記マッチングモデルは、複数のモデルレベルにより構成されたモデルであり、各モデルレベルは、複数の点、および必要に応じて複数の方向により構成され、
   前記方法は、さらに、
   （ｃ）前記マッチングモデルを使用するマッチング手法を用いて、前記電子画像内の前記対象物のポーズを決定するステップを含み、
   前記ステップ（ｃ）は、
   （ｃ１）前記電子画像の画像ピラミッドを生成するステップを含み、前記画像ピラミッドは、複数の画像レベルにより構成され、
   前記ステップ（ｃ）は、さらに、
   （ｃ２）より低い解像度を有する画像ピラミッドの画像レベルに対応するモデルレベルを用いて、前記より低い解像度を有する画像ピラミッドの画像レベルで前記対象物の前記ポーズを決定するステップと、
   （ｃ３）より高い解像度を有する画像ピラミッドの画像レベルに対応するモデルレベルを用いて、前記より高い解像度を有する画像ピラミッドの画像レベルで前記対象物の前記ポーズを精緻化するステップとを含み、
   前記方法は、さらに、
   （ｄ）前記ポーズに従って、前記マッチングモデルを変換することによって、変換後モデルを生成するステップと、
   （ｅ）前記電子画像において、前記変換後モデルの少なくとも１つの点に対応する対応点を決定するステップと、
   （ｆ）前記決定された少なくとも１つの対応点に従って、前記マッチングモデルを修正するステップとを含み、
   前記ステップ（ｄ）〜（ｆ）は、画像ピラミッドの第１画像レベルで実行され、前記第１画像レベルに対応する第１モデルレベルの修正を生成し、
   前記方法は、以下の追加のステップ、すなわち、
   （ｇ）前記第１モデルレベルの修正を第２モデルレベルに供給することによって、修正後マッチングモデルを生成するステップを含む、方法。
3. 前記マッチングモデルを修正するステップ（ｆ）は、前記マッチングモデルの複数の点の位置を修正することを含む、請求項１または２に記載の方法。
4. 前記ステップ（ｃ）における前記マッチング手法は、前記マッチングモデルの複数の点を用いて、前記対象物の前記ポーズを決定する、請求項１〜３のいずれか１項に記載の方法。
5. 前記マッチングモデルは、複数の点および方向により構成され、
   前記マッチングモデルを修正するステップ（ｆ）は、前記マッチングモデルの複数の点の位置および方向を修正することを含む、請求項１〜４のいずれか１項に記載の方法。
6. 前記方向は、方向ベクトルによって表される、請求項５に記載の方法。
7. 前記方向は、角度によって表される、請求項５に記載の方法。
8. 前記ステップ（ｃ）における前記マッチング手法は、前記マッチングモデルの複数の点および方向を用いて、前記対象物の前記ポーズを決定する、請求項５〜７のいずれか１項に記載の方法。
9. 前記ステップ（ｃ）における前記マッチング手法は、前記マッチングモデルの複数の点および方向ベクトルを使用して、前記方向ベクトルと前記電子画像内の対応方向との点乗積を計算することによって、前記対象物の前記ポーズを決定する、請求項６に記載の方法。
10. 前記マッチングモデルの複数の点の位置の修正は、前記マッチングモデルの複数のモデル点の位置を前記対応点の位置に設定することを含む、請求項３〜９のいずれか１項に記載の方法。
11. 前記マッチングモデルの複数の点の位置の修正は、前記マッチングモデルの複数のモデル点の位置を、前記マッチングモデルの前記点の位置および前記対応点の位置の関数である位置に設定することを含む、請求項３〜９のいずれか１項に記載の方法。
12. 前記マッチングモデルの複数の点の位置および方向の修正は、前記マッチングモデルの複数のモデル点の位置および方向を前記対応点の位置および方向に設定することを含む、請求項５〜９のいずれか１項に記載の方法。
13. 前記マッチングモデルの複数の点の位置および方向の修正は、前記マッチングモデルの複数のモデル点の位置および方向を、前記マッチングモデルの位置および方向と前記対応点の位置および方向との関数である位置および方向に設定することを含む、請求項５〜９のいずれか１項に記載の方法。
14. 前記ステップ（ａ）〜（ｆ）は、少なくとも２回の反復で繰り返して実行され、
    前記ステップ（ｆ）から得られた修正後マッチングモデルは、次の反復におけるステップ（ｂ）の入力マッチングモデルとして機能する、請求項１〜１３のいずれか１項に記載の方法。
15. 前記ステップ（ｅ）は、前記電子画像において、前記変換後モデルの前記少なくとも１つの点の近隣区域内で対応点を検索することを含む、請求項１〜１４のいずれか１項に記載の方法。
16. 前記ステップ（ｅ）は、前記電子画像において、前記変換後モデルの前記少なくとも１つの点の近隣区域内で対応点を検索することを含み、
    前記近隣区域は、前記点の方向によって決定される、請求項５〜１４のいずれか１項に記載の方法。
17. 前記ステップ（ｆ）は、前記決定された対応点のサブセットに従って、前記マッチングモデルを修正することを含む、請求項１〜１６のいずれか１項に記載の方法。
18. 前記ステップ（ａ）〜（ｆ）は、少なくとも２回の反復で繰り返して実行され、
    前記ステップ（ｆ）は、
    （ｆ）少なくとも１回の過去の反復または現在の反復に決定された少なくとも１つの対応点に従って、前記マッチングモデルを修正するステップによって置換され、
    前記ステップ（ｆ）から得られた修正後マッチングモデルは、次の反復におけるステップ（ｂ）の入力マッチングモデルとして機能する、請求項１〜１７のいずれか１項に記載の方法。