(57)【要約】  二次元画像において、三次元クラスモデルを用いて、クラスのインスタンスを認識するためのシステムと方法、および、二次元画像において、三次元クラスモデルを用いて、物体のインスタンスを認識するためのシステムと方法。本発明は、クラス部分の集まりを備える三次元データベースを構築するためのシステムと方法を提供する。ここで、各クラス部分は、部分アピアランスと、部分ジオメトリを含む。本発明はまた、二次元画像の一部を三次元クラスモデルにマッチングさせるためのシステムと方法を提供する。本方法は、二次元画像中で画像特徴を認識するステップ、クラスモデルと画像との間の配置変換を計算するステップ、配置変換の下でクラスモデルのクラス部分を画像特徴と比較するステップを備える。比較においては、部分アピアランスと部分ジオメトリの両方が用いられる。【選択図】図１
2008547094.tif 000002
【特許請求の範囲】
【請求項１】
二次元画像においてクラスインスタンスを認識するための方法であって、
（ａ）三次元クラスモデルのデータベースを構築するステップと、
（ｂ）二次元画像において一以上の画像特徴を特定し、特定された画像特徴を前記三次元クラスモデルに属するクラス部分と比較することにより、前記二次元画像に現れるクラスインスタンスを、前記三次元クラスモデルにマッチングするステップと、
を備える方法。
【請求項２】
前記三次元クラスモデルのデータベースを構築するステップはさらに、
（ａ）前記クラスに属するサンプルオブジェクトの三次元画像を取得するステップと、
（ｂ）各サンプルオブジェクトについて、オブジェクトモデルを構築するステップと、
（ｃ）前記オブジェクトモデルを正準ジオメトリ形式に設定するステップと、
（ｄ）正準ジオメトリ形式においてオブジェクトモデルを合成するステップと、
を備える請求項１の方法。
【請求項３】
前記オブジェクトモデルを構築するステップはさらに、
一以上の関心点を特定するステップと、
各関心点において、正準アピアランス記述子を計算するステップと、
を備える請求項２の方法。
【請求項４】
前記正準ジオメトリ形式オブジェクトモデルを合成するステップはさらに、
（ａ）オブジェクトモデル中の対応要素の集合であって、各集合があるオブジェクトモデルの一の要素と、他のオブジェクトモデルの一以上の対応要素とを備える集合を特定するステップと、
（ｂ）各対応要素の集合について、クラス部分を構築するステップと、
を備える請求項２の方法。
【請求項５】
前記各対応要素の集合について、クラス部分を構築するステップはさらに、
（ａ）部分ジオメトリを計算するステップと、
（ｂ）部分アピアランスを計算するステップと、
を備える請求項４の方法。
【請求項６】
前記二次元画像に現れるクラスインスタンスを、前記三次元クラスモデルにマッチングするステップはさらに、
（ａ）二次元画像において、各々、特徴位置と特徴アピアランスを有する一以上の画像特徴を特定するステップと、
（ｂ）各々が、クラスモデルと特徴部分マッチの集合とを有する一以上の対応仮説を構築するステップと、
（ｃ）各対応仮説を用いて、クラスモデルの二次元画像への配置変換を計算するステップと、
（ｄ）クラススコアを計算することにより、前記配置変換の下で対応仮説を評価するステップと、
（ｅ）対応仮説のうち、そのクラススコアが選択された受け入れ基準を満たす対応仮説を選択するステップと、
を備える請求項１のシステム。
【請求項７】
前記対応仮説を構築するステップはさらに、
（ａ）初期対応仮説を選択するステップと、
（ｂ）可能性のある追加の特徴部分マッチを特定するステップと、
（ｃ）各追加特徴部分マッチについて、前記特徴部分マッチで補強された対応仮説のクラススコアを評価するステップと、
（ｄ）クラススコアを高める特徴部分を有する対応仮説を拡張するステップと、
（ｅ）クラススコアを高める新たな特徴部分マッチが見つからなくなるまで、上記（ｂ）から（ｄ）までのステップを繰り返すステップと、
を備える請求項６のシステム。
【請求項８】
前記初期対応仮説を選択するステップはさらに、
（ａ）クラスモデルと、
特徴アピアランスと部分アピアランスを備える各特徴部分マッチの中から、特徴アピアランスの成分を部分アピアランスの成分と比較することにより選択される初期特徴部分マッチと、
を選択するステップと、
（ｂ）初期特徴部分マッチのベクトルを形成するステップと、
を備える請求項７のシステム。
【請求項９】
各追加特徴部分マッチについて、前記特徴部分マッチで補強された対応仮説のクラススコアを評価するステップはさらに、
（ａ）補強された対応仮説を用いて、クラスモデルから画像への配置変換を計算するステップと、
（ｂ）前記配置変換の下で、クラス部分と画像特徴を比較するステップと、
を備える請求項７の方法。
【請求項１０】
前記配置変換の下で、クラス部分と画像特徴を比較するステップはさらに、
（ａ）前記配置変換の下で、ジオメトリの比較を計算するステップと、
（ｂ）前記配置変換の下で、アピアランスの比較を計算するステップと、
（ｃ）前記ジオメトリの比較の結果と、前記アピアランスの比較の結果とを結合するステップと、
を備える請求項９の方法。
【請求項１１】
前記配置変換の下でジオメトリの比較を計算するステップはさらに、クラス部分ジオメトリの位置成分を、対応する二次元画像位置に投影するステップを備える請求項１０の方法。
【請求項１２】
前記配置変換の下でジオメトリの比較を計算するステップはさらに、画像特徴位置を、対応する三次元モデル位置に投影するステップを備える請求項１０の方法。
【請求項１３】
前記配置変換の下でアピアランス比較を計算するステップはさらに、画像特徴アピアランスの一部の成分を、対応する三次元モデルアピアランスに投影するステップを備える請求項１０の方法。
【請求項１４】
前記配置変換の下でアピアランス比較を計算するステップはさらに、クラス部分のアピアランスの一部の成分を、対応する二次元画像アピアランスに投影するステップを備える請求項１０の方法。
【請求項１５】
局所領域において、二次元画像を正面に配置するステップをさらに含む請求項１の方法。
【請求項１６】
前記局所領域において二次元画像を正面配置するステップは、面について、可能性のある一以上の方向を仮定し、面の各方向について前記面がその方向を向いているものとして、局所画像アピアランスを計算することにより、実行される請求項１５の方法。
【請求項１７】
（ａ）各三次元クラスモデルは、複数のクラス部分を備え、
（ｂ）各クラス部分は部分ジオメトリと部分アピアランスを備え、
（ｃ）各部分アピアランスは、二次元情報から計算される第一の部分アピアランス記述子を備える、
三次元クラスモデルのデータベース。
【請求項１８】
各部分アピアランスはさらに、姿勢不変である第二の部分アピアランス記述子を備える請求項１７のシステム。
【請求項１９】
（ａ）前記各三次元クラスモデルは、クラスに属するサンプルオブジェクトの集合を表し、
（ｂ）前記各サンプルオブジェクトは複数の要素を備え、
（ｃ）各サンプルオブジェクトの複数の要素は、ほかのサンプルオブジェクトに対応要素を有し、
（ｄ）各要素は要素ジオメトリと要素アピアランスを備え、
（ｅ）各クラス部分はサンプルオブジェクト中の対応要素の集合を表し、
（ｆ）前記部分ジオメトリは、対応要素の要素ジオメトリの集合を表し、
（ｇ）前記部分アピアランスは、対応要素の要素アピアランスの集合を表す、
請求項１８のシステム。
【請求項２０】
前記部分ジオメトリは、対応要素の正準ジオメトリを表す請求項１９のシステム。
【請求項２１】
第二の部分アピアランス記述子は、対応要素の正準アピアランスを表す請求項１９のシステム。
【請求項２２】
三次元クラスモデルのデータベースを用いた二次元画像におけるクラスインスタンスの認識方法であって、
（ａ）二次元画像中において、特徴位置と特徴アピアランスを有する一以上の画像特徴を特定するステップと、
（ｂ）クラスモデルと特徴部分マッチの集合とを備える一以上の対応仮説を構築するステップと、
（ｃ）各対応仮説を用いて、クラスモデルの二次元画像への配置変換を計算するステップと、
（ｄ）クラススコアを計算することにより、前記配置変換の下で、各対応仮説を評価するステップと、
（ｅ）対応仮説のうち、そのクラススコアが選択された受け入れ基準を満たす対応仮説を選択するステップと、
を備える認識方法。
【請求項２３】
二次元画像においてクラスインスタンスを認識するためのシステムであって、
（ａ）三次元クラスモデルのデータベースと、
（ｂ）二次元画像の画像特徴を特定し、前記画像特徴を三次元クラスモデルに属するクラス部分と比較することにより、二次元画像に現れるクラスインスタンスを三次元クラスモデルにマッチングさせるように構成されたコンピュータと、
を備えるシステム。
【請求項２４】
前記三次元クラスモデルのデータベースにおいては、
（ａ）各三次元クラスモデルは、複数のクラス部分を備え、
（ｂ）各クラス部分は、部分ジオメトリと部分アピアランスを備え、
（ｃ）各部分アピアランスは、二次元情報から計算される第一のアピアランス記述子と、姿勢不変である第二の部分アピアランス記述子とを備える、
請求項２３のシステム。
【請求項２５】
（ａ）三次元クラスモデルデータベースを構築するステップと、
（ｂ）二次元画像において一以上の画像特徴を特定し、特定された画像特徴を前記三次元クラスモデルに属するクラス部分と比較することにより、前記二次元画像に現れるクラスインスタンスを、前記三次元クラスモデルにマッチングするステップと、
を実行するための情報を格納するコンピュータ読みとり可能な媒体。
【請求項２６】
（ａ）部分ジオメトリと、
二次元情報から計算される第一の部分アピアランス記述子と、姿勢不変である第二の部分アピアランス記述子を備える部分アピアランスと、
を備える複数のオブジェクトクラス部分を備える三次元オブジェクトクラスモデルのデータベースを構築するステップと、
（ｂ）二次元画像において一以上の画像特徴を特定し、特定された画像特徴を前記三次元オブジェクトクラスモデルに属するオブジェクトクラス部分と比較することにより、前記二次元画像に現れるオブジェクトインスタンスを、前記三次元オブジェクトクラスモデルにマッチングするステップと、
を備える二次元画像におけるオブジェクトの認識方法。
【請求項２７】
前記三次元オブジェクトクラスモデルを構築するステップはさらに、
（ａ）様々なサンプル状態にあるオブジェクトの三次元画像を取得するステップと、
（ｂ）各サンプル状態について、オブジェクトモデルを構築するステップと、
（ｃ）オブジェクトモデルを正準形式に設定するステップと、
（ｄ）正準形式オブジェクトモデルを合成するステップと、
を備える請求項２６の方法。
【請求項２８】
前記特定された画像特徴を三次元オブジェクトクラスモデルに属するオブジェクトクラス部分と比較するステップはさらに、
（ａ）各々が、オブジェクトクラスモデルと特徴部分マッチとを有する一以上の対応仮説を、構築するステップと、
（ｂ）各対応仮説を用いて、オブジェクトクラスモデルから二次元画像への配置変換を計算するステップと、
（ｃ）クラスモデルスコアを計算することにより、前記配置変換の下で各対応仮説を評価するステップと、
（ｄ）対応仮説のうち、そのクラススコアが選択された受け入れ基準を満たす対応仮説を選択するステップと、
を備える請求項２６の方法。
【請求項２９】
（ａ）前記一以上の対応仮説を構築するステップは、第一のアピアランス記述子を用いて特徴部分マッチを特定するステップを備え、
（ｂ）前記クラススコアを計算するステップは、第二の部分アピアランス記述子を用いて、前記配置変換の下でアピアランス比較を計算するステップを備える、
請求項２８の方法。
【請求項３０】
二次元画像における変形可能なオブジェクトの認識方法であって、
（ａ）変形によるオブジェクトの多様性をモデル化するオブジェクトの部分ジオメトリと、
二次元情報から計算される第一の部分アピアランス記述子と、姿勢不変である第二の部分アピアランス記述子とを備える部分アピアランスと、
を備える複数のオブジェクトクラス部分を備える三次元オブジェクトクラスモデルのデータベースを構築するステップと、
（ｂ）二次元画像において一以上の画像特徴を特定し、画像特徴を前記三次元オブジェクトクラスモデルに属する前記オブジェクトクラス部分と比較することにより、前記二次元画像に現れるオブジェクトインスタンスを前記三次元オブジェクトクラスモデルにマッチングするステップと、
を備える方法。
【請求項３１】
二次元画像において、複数のアピアランス状態を有するオブジェクトを認識する方法であって、
（ａ）部分ジオメトリと、
二次元情報から計算される第一のアピアランス記述子と、姿勢不変である第二の部分アピアランス記述子と、
を備える部分アピアランスと、
を備える複数のオブジェクトクラス部分を備える三次元オブジェクトクラスモデルのデータベースを構築するステップと、
（ｂ）二次元画像において一以上の画像特徴を特定し、画像特徴を前記三次元オブジェクトクラスモデルに属するオブジェクトクラス部分と比較することにより、前記二次元画像に現れるオブジェクトインスタンスを、前記三次元オブジェクトクラスモデルにマッチングするステップと、
を備え、
一以上の前記部分アピアランス記述子が、オブジェクトの複数のアピアランス状態をモデル化する方法。
【請求項３２】
二次元画像においてクラスインスタンスを認識するためのシステムであって、
（ａ）部分ジオメトリと、
二次元情報から計算される第一のアピアランス記述子と、姿勢不変である第二の部分アピアランス記述子とを備える部分アピアランスと、
を備える複数のオブジェクトクラス部分を備える三次元クラスモデルのデータベースと、
（ｂ）二次元画像において一以上の画像特徴を特定し、特定された画像特徴を前記三次元オブジェクトクラスモデルに属するオブジェクトクラス部分と比較することにより、前記二次元画像に現れるオブジェクトインスタンスを、前記三次元オブジェクトクラスモデルにマッチングするように構成されたコンピュータと、
を備えるシステム。
【請求項３３】
（ａ）部分ジオメトリと、
二次元情報から計算される第一の部分アピアランス記述子と、姿勢不変である第二の部分アピアランス記述子とを備える部分アピアランスと、
を備える複数のオブジェクトクラス部分を備える三次元オブジェクトクラスモデルのデータベースを構築するステップと、
（ｂ）二次元画像において一以上の画像特徴を特定し、特定された画像特徴を前記三次元オブジェクトクラスモデルに属するオブジェクトクラス部分と比較することにより、前記二次元画像に現れるオブジェクトインスタンスを、前記三次元オブジェクトクラスモデルにマッチングするステップと、
を実行するための情報を格納するコンピュータ読みとり可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２００５年６月１６日に提出した特許文献１の利益を主張し、その全てを本願明細書に援用する。
【特許文献１】U.S. Provisional Patent Application Serial No. 60/691,732, filed June 16, 2005, entitled "System and Method for Object Recognition Using 3D Range and Intensity Models,”
【０００２】
本発明は、概してコンピュータビジョンに関し、特に、ビジュアルクラスのインスタンスの認識に関する。
【背景技術】
【０００３】
［従来技術の記述］
クラス認識は、シーン中の、クラスインスタンスの認識に関する。この文脈で用いられるとき、「クラス」とは、共通の視覚的特徴を有し、他のクラスのオブジェクトと視覚的特徴において異なるオブジェクトの集まりである。
【０００４】
クラス認識における第一段階は、既知のクラスのデータベースを構築することである。クラス認識における第二段階は、画像中に観測される新たなインスタンスを、データベース中に表現されるインスタンスとマッチングすることである。
【０００５】
クラス認識は多くの課題を提示する。まず第一に、特定のオブジェクトを認識するという課題を提示する。一のオブジェクトは、異なる観点から見たとき、状況が異なるとき、または照明の条件が異なるとき、非常に異なって見える可能性がある。オブジェクト認識の問題に加えて、クラス認識は、さらにクラス内の多様性に関する課題を提示する。一のクラスの各インスタンスは、その形やその視覚的外観の一部において異なる可能性がある。クラス認識器は、このさらなる多様性を取り扱うことができなければならず、また、そのクラスの共通の特徴に基づいて、クラスを構成するオブジェクトを検出することができなければならない。
【０００６】
従来、これらの課題を全面的に満たす解決方法は存在しなかった。相当数の研究がクラス認識に捧げられてきたが、多岐にわたるクラスのインスタンスを、様々な視点と距離にわたって認識できるものは存在しなかった。
［従来の学術研究］
【０００７】
相当数の研究が、オブジェクト認識のより単純な問題に捧げられてきたが、多岐にわたるオブジェクトを、様々な視点と距離において認識できるオブジェクト認識システムは存在しなかった。クラス認識は、さらに、かなり難しい問題である。オブジェクト認識は、その一部である。オブジェクト認識システムは、特定のオブジェクトのために設計され、その特定のオブジェクトを認識できさえすればよい。これに対して、クラス認識システムは、以前に見たことのないオブジェクトを、あるクラスに共通な特徴との類似性に基づいて、クラスインスタンスとして認識しなければならない。
【０００８】
クラス認識における研究方針のひとつにおいては、クラスを、各部分の順不同な集合で代表する。各部分が、その部分の局所アピアランスについてのモデルで表現され、そのクラスの全てのインスタンスについて一般化される。部分間の空間的関係は無視され、アピアランス情報のみが用いられる。この手法をとる文献のひとつに非特許文献１がある。この手法を拡張した同じ著者による後の文献に、非特許文献２がある。この文献はまた、非特許文献３としても提供されている。この一般的手法には、いくつかの難しい点がある。最も重要な点は、各部分相互のジオメトリ関係が表現されないため、重要な情報がかなり失われるという点である。各部分をランダムに配置した支離滅裂な寄せ集めが、これらの部分をそれぞれ適切な場所に配置したオブジェクトと混同されうる。
【非特許文献１】Dorko and Schmid, "Selection of Scale-Invariant Parts for Object Class Recognition", International Conference on Computer Vision, 2003, pp. 634-640
【非特許文献２】Dorko and Schmid,"Object Class Recognition using Discriminative Local Features," IEEE Transactions on Pattern Analysis and Machine Intelligence
【非特許文献３】Dorko and Schmid,"Object Class Recognition using Discriminative Local Features,"Technical Report RR-5497, INRIA - Rhone-Alpes - February 2005
【０００９】
クラス認識における別の研究方針においては、クラスを二次元構造の部分群として表現する。この手法を採用する文献のうちの二つを非特許文献４と非特許文献５に挙げる。これらの方針に沿った別の文献に、非特許文献６がある。この種の二次元モデルを用いることには、二つの困難な点が伴う。第一は、各部分の局所アピアランスが、カメラに対するオブジェクトの姿勢の変化について、不変ではないということである。第二は、各部分は二次元画像中にのみ生ずる部分として、部分間の関係が取得され、モデル化されるということである。その根底にある三次元の空間的関係は観察されず、計算されず、またモデル化もされない。
【非特許文献４】Burl et al., "A probabilistic approach to object recognition using local photometry and global geometry", Proc. European Conference on Computer Vision (ECCV) 1998, pp 628-641
【非特許文献５】Fergus et al., "Object Class Recognition by Unsupervised Scale-Invariant Learning", Computer Vision and Pattern Recognition, 2003, pp 264-271
【非特許文献６】Helmer and Lowe, "Object Class Recognition with Many Local Features", IEEE Computer Vision and Pattern Recognition Workshops, 2004 (CVPRW'04), pp. 187 ff
【００１０】
［他の先行技術］
本発明者による特許文献２は、これらの問題に対処する技術について述べる。この文献は、画像の濃淡度と距離の組み合わせを用いて、モデルのデータベースとシーンの双方が得られたとき、各クラスのオブジェクトとインスタンスを認識する方法と装置を開示する。ここでは、モデルと取得した画像の両方が三次元である。
【特許文献２】HAGER GREGORY D; WEGBREIT ELIOT L U.S. Patent Application 11/159,660, filed June 22, 2005,"System and Method for 3D Object Recognition Using Range and Intensity,"
【非特許文献７】K. Mikolajczyk et al., "A Comparison of Affine Region Detectors" International Journal of Computer Vision, Volume 65, Number 1-2, November 2005, pp. 43-72
【非特許文献８】K. Mikolajczyk et al, "A Performance Evaluation of Local Descriptors", IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 27, Issue 10, Oct. 2005, pp. 1615-1630
【非特許文献９】Duda, Hart, and Stork, Pattern Classification, John Wiley, 2001
【非特許文献１０】C-P. Lu, G. Hager and E. Mjolsness, "Fast and Globally Convergence Pose Estimation from Video Images", IEEE Trans, on Pattern Analysis and Machine Intelligence, June 2000, pp. 610-622
【非特許文献１１】Kaplan, Advanced Calculus, Addison-Wesley, 1993
【非特許文献１２】S. Hutchinson, G. Hager and P. Corke, "A Tutorial Introduction to Visual Servo Control," IEEE Traits, on Robotics and Automation, 12(5) pp. 651-670, 1996
【非特許文献１３】G. Hager, "A Modular System for Robust Hand-Eye Coordination Using Feedback from Stereo Vision." IEEE Trans, on Robotics and Automation, 13(4) pp. 582-595, 1997
【非特許文献１４】Trucco and Verri, Introductory Techniques for 3-D Computer Vision, Prentice Hall, 1998, Section 7.3.7
【非特許文献１５】A. Johnson and M. Hebert in "Using spin images for efficient object recognition in cluttered 3D scenes," IEEE Trans, on Pattern Analysis and Machine Intelligence, 21(5) pp. 433-449, 1999
【非特許文献１６】S. Lazebnik et al. "A Sparse Texture Representation Using Local Affine Regions," IEEE Trans, on Pattern Analysis and Machine Intelligence, 27(8) pp. 1265-1278, 2005
【非特許文献１７】Moakher, "Means and Averaging in the Group of Rotations", SIAM Journal on Matrix Analysis and Applications, Vol. 24, Issue 1, pp 1-16, 2002
【非特許文献１８】Eberly, 3D Game Engine Design, Morgan Kaufmann, 2001
【非特許文献１９】F. Rothganger et al., "3D Object Modeling and Recognition Using Local Affine-Invariant Image Descriptors and Multi-View Spatial Constraints," International Journal of Computer Vision, vol. 66, no. 3, pp. 231-259, 2006
【非特許文献２０】Forsyth and Ponce, Computer- Vision, Prentice Hall, 2003
【発明の開示】
【発明が解決しようとする課題】
【００１１】
距離と濃淡度の組み合わせを用いて画像を取得するためには、例えば、ステレオシステムや、カメラとレーザ距離計の組み合わせなどの特別の装置が必要である。データベース構築は制御された条件の下でなされるため、たいていの場合、クラスモデルのデータベースはこの方法で構築される。しかしながら認識段階では、距離情報が得られないような状況が多く存在する。言い換えると、濃淡度情報は例えば単純なカメラなどで容易に取得できるが、そのシーンについて高精度の距離情報を取得することは難しい。
【００１２】
したがって、画像の濃淡度情報のみを有する二次元画像において、ジオメトリとアピアランスについての三次元情報を用いて、クラス認識を行うことのできるシステムと方法が求められている。さらに、先行技術の制約を克服するオブジェクト認識システムと方法が求められている。
【課題を解決するための手段】
【００１３】
［発明の概要］
本発明は、三次元クラスモデルを用いて二次元画像中の各クラスのインスタンスを認識するシステムと方法を提供する。
【００１４】
本発明は、部分アピアランスと部分ジオメトリを含む、各クラス部分の集まりを備える三次元クラスモデルのデータベースを構築するシステムと方法を提供する。
【００１５】
本発明は、さらに、二次元画像の一部を、三次元クラスモデルにマッチングするシステムと方法を提供する。この方法は、二次元画像中で各画像特徴を特定するステップ、クラスモデルと画像との配置変換を計算するステップ、その配置変換の下で、クラスモデルのクラス部分と画像特徴とを比較するステップを備える。この比較においては、部分アピアランスと部分ジオメトリの両方を用いる。
【００１６】
そのシステムと、その方法の様々な実施形態、そして他の幾つかの別の実施形態もまた開示される。第一の実施形態は、クラス認識を実行する。第二の実施形態は、オブジェクト認識を実行する。第一および第二の実施形態両方において、三次元モデルの性質を有利に使用し、本発明の認識手法を有利に用いている。
【００１７】
本発明はまた、その方法ステップを実行するためのプログラム命令を備えるコンピュータ読み取り可能な媒体を提供する。
【図面の簡単な説明】
【００１８】
添付されている図は、以下のとおりである。
【００１９】
【図１】本発明の一実施形態にかかる、クラス認識を実行するシステムの主要な構成要素を象徴的に示す図である。
【００２０】
【図２】本発明の一実施形態にかかる、クラスデータベースを構築するシステムの主要な構成要素を象徴的に示す図である。
【００２１】
【図３】本発明の一実施形態にかかる、クラスモデルを構築するシステムの主なステップを示すフローチャートである。
【００２２】
【図４】本発明の一実施形態にかかる、認識プロセスを示すフローチャートである。
【００２３】
【図５】本発明の一実施形態において、認識中に実行される探索手法を示すフローチャートである。
【発明を実施するための最良の形態】
【００２４】
［発明の詳細な説明］
本発明は、観測されたシーンの二次元濃淡画像中のクラスインスタンスを認識するため、三次元距離と濃淡度アピアランス情報の両方を含むモデルを用いることにより、クラス認識を実行する。
【００２５】
本発明はさらに、観測されたシーンの二次元濃淡画像中のオブジェクトを認識するため、三次元距離と濃淡度アピアランス情報の両方を含むモデルを用いることにより、オブジェクト認識を実行する。
［概要］
【００２６】
図１は、本発明の一実施形態にかかる、クラス認識を実行するシステムの主要な構成要素を象徴的に示す図である。データベース１０１は、三次元クラスモデルを含む。カメラ１０２は、シーンの二次元濃淡画像を取得すべく設けられる。コンピュータ１０３は、シーンに現れるクラスインスタンスを三次元クラスモデルにマッチングさせるべく構成される。
【００２７】
ここで、「シーン」とは、三次元世界の一部をいう。一方、「二次元画像」または「画像」とは、撮像装置により取得された一以上の濃淡度値を投影したものをいう。二次元濃淡画像を得る撮像装置は、「カメラ」という。典型的には、濃淡度は光の強度である。この場合、画像は、グレースケール、またはカラー画像であるが、これに限られるものではない。濃淡画像は、レーダ、超音波、その他の多くの撮像手段によっても形成されうる。本願発明は、様々な濃淡発生源による二次元画像に適用することができる。
【００２８】
「ビジュアルクラス」とは、類似するアピアランスかつ／またはジオメトリを有するオブジェクトの集まりである。「三次元クラスモデル」は、ビジュアルクラスのモデルである。ここでビジュアルクラスは、クラスに属するオブジェクトのアピアランスと三次元ジオメトリ表現を含む。
【００２９】
三次元クラスモデルのデータベースは、いわゆる「三次元画像」から構築される。三次元画像は、シーンの二次元濃淡度イメージと、それに対応する三次元記述を取得することにより、構築される。三次元記述を、「距離画像」という。この距離画像は、濃淡画像と対応付けられ、位置合わせがなされた距離濃淡画像を生成する。これを、「三次元画像」という。三次元画像における各画像位置は、一以上の濃淡度値と、対応する三次元座標を有する。三次元座標によって、空間における各画像位置が与えられる。
【００３０】
本発明において、クラスモデルは二次元濃淡画像でクラスインスタンスを識別するために用いられ、三次元画像は、クラスモデルを有利に構築するために用いられる。これを理解するために、オブジェクトの姿勢の変化が、オブジェクトの二次元画像の局所特徴のアピアランスにどう影響するかを考える。オブジェクトの姿勢の変化としては、六種類の変化が考えられる。そのうちの二は、カメラの画像面に平行な並進運動であり、一は、カメラの光軸まわりの回転であり、一は、カメラとオブジェクトとの間の距離の変化であり、二は、カメラに対するオブジェクトのスラント（ｓｌａｎｔ）とティルト（ｔｉｌｔ）の変化である。
【００３１】
オブジェクトの位置のカメラの画像面に平行な移動は、画像中での特徴の移動のみをもたらすため、画面中で特徴の位置について補正がなされれば、そのアピアランスには影響しない。オブジェクトのカメラの光軸まわりの回転は、画像中では特徴の回転と並進運動と、になる。これらの変化を説明する、特徴の位置の特定および表現方法には様々な方法がある。
【００３２】
本発明は、残りの三つの、距離、スラントおよびティルトにおける変化に代表される困難に対処する。本発明は、位置合わせがなされた距離および濃淡度情報とを用いて、三次元クラスモデルを作ることにより、困難に対処する。この三次元モデルは、（１）特徴アピアランスの表現における姿勢の多様性を説明し、（２）認識過程において、二次元画像特徴に配置することができる。
【００３３】
クラス認識の全プロセスには、二つのフェーズがある。（１）三次元データベースの構築と、（２）そのデータベースを用いた、二次元画像の認識である。
【００３４】
図２は、本発明の一実施形態にかかる、クラスデータベースを構築するシステムの主要な構成要素を象徴的に示す図である。三次元撮像システム２０１は、オブジェクト２０２の、既知の高さの水平面２０３における、三次元画像を取得する。コンピュータ２０４は、その画像を用いて三次元クラスモデルを構築し、そのクラスモデルをデータベース２０５に格納する。データベースは、管理された条件の下で構築されてもよい。特に、三次元モデルを構築するために、位置合わせがなされた距離と濃淡度情報が用いられる。
【００３５】
認識過程においては、非管理条件下で、二次元濃淡画像が得られる。これに関連付けられた三次元距離情報は存在しない。一のシーンには、既知のクラスのインスタンスが、０個、１個、または１個以上含まれてもよい。あるクラスのインスタンスが存在するとき、それは、１回、または１回以上存在してもよい。あるインスタンスは、部分的に隠蔽され、シーンの他のオブジェクトと接触していてもよい。クラス認識のゴールは、二次元画像において、データベース中の三次元クラスモデルにマッチングするオブジェクトを見つけることである。
【００３６】
以下に述べるように、本発明においては、データベース中の三次元クラスモデルを有利に用いる。また、三次元クラスモデルの特性と、三次元面とその二次元画像への投影との間の必須の関係と、を有利に用いる。これらにより、本発明において、二次元濃淡画像中のクラスインスタンスが認識される。
【００３７】
本発明には様々な実施形態が存在する。便宜上、本発明を以下の順序で記述する。すなわち、まず本発明の原理、次に第一および第二の実施形態、そして様々な別の実施形態の順である。様々な実施形態の中からの選択は、ある程度は適用分野に基き、特に、認識すべきクラスに基づいて行われる。
［本発明の原理］
［関心点の検出］
【００３８】
本発明は、画像の関心点を利用する。画像の関心点とは、ある画像中での特質的な位置である。関心点の検出が、クラス認識の開始点となる。関心点の検出方法は、「関心点演算子」、「関心点検出器」または「アフィン領域検出器」と呼ばれる。このような方法の幾つかは、非特許文献７に記述されている。
【００３９】
関心点は、あるスケールで検出される。スケールは、その画像の関連付けられた局所領域の範囲として、ピクセルで表現されうる。スケールの違いは、撮像されている面への距離の変化、面上のパターンの物理的な寸法の変化、またはこの両方により生じる。本発明の様々な実施形態において、選択された演算子が以下の要求を満たす限りにおいて、様々な関心点演算子を用いてよい。すなわち、（１）その演算子が計算する位置が、視線方向、光軸まわりの回転、そしてスケールの変化に、比較的影響を受けないこと、（２）その演算子が、視線方向、光軸まわりの回転、そしてスケールの変化に比較的影響を受けない範囲の関心点周囲の局所領域について計算すること、（３）その演算子が、視線方向やスケールの変化に比較的影響を受けない光軸方向を特定する二つの直行軸を計算すること、である。これらの要求を満たす幾つかの演算子についてもまた同様に、非特許文献７に記述されている。
［関心点の表現］
【００４０】
関心点演算子により検出された画像の局所領域をＰとする。局所領域の記述Ａは、局所領域の濃淡画像の関数として計算される。このような記述は、当該技術分野において、「アピアランス記述子」「局所特徴」「局所記述子」など、様々な呼び方で呼ばれる。このような幾つかの記述子については、非特許文献８において述べられている。本発明の様々な実施形態において、様々な記述子演算子が用いられてよい。
【００４１】
画像について参照するとき、便宜上、関心点の二次元位置を「特徴位置」と、関心点における局所アピアランスの記述を「特徴アピアランス」と、これらの組み合わせを「画像特徴」と呼ぶ。
【００４２】
クラスデータベースの構築過程において、局所領域Ｐに関連付けられた距離データが存在する。この距離データにより、関心点の三次元位置と、関心点の面の法線を計算することができる。さらに、あたかも任意に選択した視点方向から取得したかの如く見えるように、局所領域における濃淡画像をリサンプリングすることができる。特徴が検出されたスケールによって、さらに、その領域が正準スケールにサンプリングされうる。ここでもスケールは、その領域が占める範囲として、ピクセルで表現される。ある特徴が正準スケールにおいてリサンプリングされる場合、そのピクセルで表された領域は、視点からの距離に関わらず等しい。画像パッチを正準な視点方向とスケールについてリサンプリングした結果は、「正準アピアランス」と呼ばれる。この正準アピアランスは、視点であるカメラに対する姿勢について不変であり、「姿勢不変」といわれる。クラスデータベースの構築過程において、姿勢不変なアピアランスの記述を構築する機能は、本発明の有利な点のひとつである。
【００４３】
典型的な実施形態においては、視点の方向は正面であるように選択される。つまり、法線に沿った方向である。正準スケールは、特徴のアピアランスを適切に表現するために充分な解像度となるように、選択される。このリサンプリングの実行方法は、特許文献２に記述されている。その記述の全てをここに援用する。
【００４４】
正準なアピアランスにおいて、その画像パッチの主要な勾配の方向は、表面法線に対するそのパッチの方向を定義するために使うことができる。表面法線と、表面法線に対する方向は共に、三次元空間における関心点の向きを定義する。三次元方向は、三次元位置と共に、関心点の「姿勢」を定義する。
【００４５】
データベースを構築する過程において、局所領域Ｐのアピアランス記述子は、正準アピアランスから計算できる。したがって、スラント、ティルト、面までの距離、そして局所アピアランスの領域の大きさの影響が除去される。各関心点について、姿勢を特定する三次元ジオメトリ記述子と、一以上のアピアランス記述子とからなる記述子が計算される。
【００４６】
認識処理においては、データベース構築に用いられたものと同じ関心点記述子を用いて、画像中の関心点が検出される。ただし距離データはないため、二次元濃淡度情報のみ使用可能である。画像の特徴記述子は、二次元画像の位置と、一以上の濃淡画像から計算されたアピアランス記述子から構成される。
［クラスモデル］
【００４７】
三次元クラスを表現するために、統計的なデータモデルが用いられる。クラスモデルは、オブジェクトの集合から計算される。オブジェクトの集合は、そのクラスのインスタンスの代表的なサンプルを提供する。本発明に関して述べたように、クラスを記述するためには、統計的なモデルを用いることが可能である。これにより、代表的なサンプル中のオブジェクトに類似するオブジェクトの二次元画像が、類似するものとして認識されうる。統計的なモデルを用いて、データベースの代表的なサンプルを、一般化することができる。これにより、認識フェーズにおいて、二次元画像中の、以前に見たことのないクラスインスタンスを識別することができる。
【００４８】
クラスの代表的なサンプルを提供するオブジェクトを、「サンプルオブジェクト」と呼ぶ。各サンプルオブジェクトは、共通の視覚的特徴を有する。特に各サンプルオブジェクトは、似たような局所アピアランスを有する関心点を似たような位置に有する。便宜上、サンプルオブジェクトの関心点を「要素」と呼び、似たような位置にある似たような局所アピアランスを「対応要素」と呼ぶ。これらの対応要素は、クラスの共通の特徴を記述する。それぞれの対応要素の集合は、クラスモデルの中で、「クラス部分」として、表現される。
【００４９】
要素は、「要素ジオメトリ」とよばれるジオメトリを有し、「要素アピアランス」と呼ばれるアピアランスを有する。ジオメトリは、位置と、関連する性質とを記述し、アピアランスは、局所的な外観上の特徴を記述する。これらは、クラスモデル中で、統計的データモデルを用いて、「部分ジオメトリ」と、「部分アピアランス」によって代表される。
【００５０】
本発明は、スケーリング演算または他のジオメトリに関する正規化によって、要素ジオメトリを標準化する。その結果、要素は、「正準ジオメトリ」を有することになる。要素ジオメトリを標準化する特定の手法については第一の実施形態において述べ、他の手法については別の実施形態において述べる。クラスモデルが、正準ジオメトリにおけるサンプルオブジェクトから構築されるとき、そのクラス部分ジオメトリは、対応要素の正準ジオメトリを表す。
【００５１】
本発明はまた、要素アピアランスを、正準化した視点方向とスケールにリサンプリングすることにより標準化し、その結果、「正準アピアランス」とする。リサンプリングの特定の一の手法については第一の実施形態において、別の手法については別の実施形態において述べる。クラスモデルが、正準アピアランスによってサンプルオブジェクトから構築されるとき、クラス部分アピアランスは、対応要素の正準アピアランスを表す。特に、クラスモデルの部分アピアランスは、二つのアピアランスの記述子を有する。一方は姿勢不変であり、三次元情報を用いて構築される。他方は三次元情報を用いずに、二次元画像から計算される。
［データの統計的モデリング］
【００５２】
データベクトルの組ｘ１，ｘ２，．．．ｘｄが与えられたとき、データ要素の値の経験的な分布は、様々な方法により計算することができる。一般的な方法においては、データベクトルの平均と共分散を計算し、その分布を多変数ガウス分布としてモデル化する。文献においては、ガウス分布はしばしば、「正規分布」と呼ばれる。
【００５３】
以下の、記述上の慣習を用いると便利である。ｘが確率変数であるならば、その平均は、μｘと表記される。その共分散は、Λｘと表記される。そしてこれらを合わせて、Ｘと表記され、Ｘ＝（μｘ，Λｘ）である。従ってＸは、確率変数ｘの分布である。
【００５４】
ｎを、ｘの成分の数とする。ｙがガウス分布Ｘのサンプルベクトルであるなら、このモデルを与えられたｙの確率密度は以下のように表される。
Ｐ（ｙ｜μｘ，Λｘ）＝ｅｘｐ（−（ｙ−μｘ）ＴΛｘ−１（ｙ−μｘ）／２）／((２π）ｎ／２｜Λｘ｜1／２）
ここで、（ｙ−μｘ）Ｔ は、（ｙ−μｘ）の転置を表し、｜Λｘ｜1／２は、ΛＸの行列式の平方根を表す。上記の方程式の右辺を、よりコンパクトな形、Ｇ（ｙ;μｘ，Λｘ）で記述すると都合がよい。すなわち、Ｇ（ｙ;μｘ，Λｘ）は、以下のように定義される。
Ｇ（ｙ；μｘ，Λｘ）＝ｅｘｐ（−（ｙ−μｘ）ＴΛｘ−１（ｙ−μｘ）／２）／((２π）ｎ／２｜Λｘ｜1／２）        （１）
【００５５】
ある場合には、サンプルデータの値が十分でなかったり、また、与えられた値が線形のサブ空間内に存在したりする。これらの場合においては、可逆な、すなわち最大階数の共分散行列Λｘを計算することは不可能である。したがって、上記の方程式の値を評価することはできない。このような場合には、データについて、次元縮退を施してもよい。次元縮退の実行方法、そして関連するこの形の統計的モデルは、例えば非特許文献９などの様々な教科書において議論されている。これに代えて、近似的として、各次元の分散が独立に計算されてもよい。この場合には、Λｘは、対角行列となる。
【００５６】
データがガウス分布モデルに従わない場合も考えられる。例えば、データは、実は、マルチプルガウス分布モデルから採られたものかもしれない。後者の場合、その分布の主要なモードを識別するために、そのデータについてクラスタリングを実行することができる。クラスタリングを実行する一つの方法においては、ｋ個のクラスタ中心の集合を選ぶ（例えば、無作為にｋ個のデータ要素を選ぶことによって）。そして、それぞれのデータ要素を、最も近いクラスタに関連付ける。一旦これが行われると、クラスタ中心は、関連づけられたデータ要素の平均として再計算され、この処理が繰り返されうる。この手順は、ｋ平均クラスタリングと呼ばれる。一旦この方法により、クラスタが定められると、それぞれのクラスタのガウス分布は、上述のようにして、再び計算することができる。データセット全体についての分布は、これらのガウス分布の「混合」である。ここで、ｎ個のクラスタがあり、それぞれデータモデル（μｉ，Λｉ）に関連付けられていると仮定する。混合分布は、θ＝｛（μｉ，Λｉ，ｍｉ）｝，ｉ＝１．．．ｎとして、表現できる。ここで、ｍｉは、ｉ番目のクラスタと関連付けられている点の数である。ガウス分布の混合におけるｙの確率は、
Ｐ（ｙ｜θ）＝Σｉ（ｍｉ／Ｍ）Ｇ（ｙ；μｉ，Λｉ）
である。ただし、Ｍ＝Σｉｍｉである。
【００５７】
より一般的には、ガウス分布の混合は、いわゆる、「期待値最大化」により、計算することができる。これら、そして他の関連する方法は、標準的な教科書、例えば、非特許文献９などに記述されている。
【００５８】
一般的には、統計的なモデル化の方法がどんなものであったとしても、モデル変数の集合θを計算することができ、そのデータの統計的な分布を特徴づけることができる。そして、観測されたデータ要素ｙの尤度は、Ｐ（ｙ｜θ）と記される。
［配置変換の下での三次元ジオメトリの推定と投影］
【００５９】
クラス認識においては、二次元画像で検出された特徴をもとに、三次元クラスモデルの配置を計算する。そして、検出された特徴の位置には配置されたモデルが与えられ、その尤度が評価される。
【００６０】
配置に関して、３以上のモデルの位置と、対応する二次元画像の位置が与えられたとする。三次元モデルを二次元画像位置に関連付ける「配置変換」γを計算することができる。そのための手法の一つに、非特許文献１０に記述されるアルゴリズムがある。配置変換γは、（ｔ，ｒ）の形式を有する。ここでｔは、三次元並行移動ベクトルであり、ｒは、三次元回転行列である。この配置変換は、三次元モデル点の位置と、マッチングする画像特徴の観測された位置との、マッチング誤差を最小化することにより、計算できる。ここでは、配置変換の下で、特徴の観測された位置をモデルに投影するものとして計算する。これに代えて、配置変換を計算するための他の手法を用いることもできる。
【００６１】
配置変換と姿勢は、両方とも並行移動と回転を特定する。すなわち両者とも、同じ情報を有する。ここで、「配置変換」という用語は、その情報により、三次元クラスモデルが二次元画像に関係付けられるときに、用いられる。「姿勢」という用語は、三次元クラス部分のジオメトリの仕様を示し、認識されたクラスインスタンスを記述するときにも用いられる。
【００６２】
クラス認識において、推定された配置変換の統計的特性に関する、以下の二つの演算が用いられる。（１）配置γについての、相対的な確実性の計算。これは、共分散行列ΛΓで表現される。（２）付加的なモデル位置の、画像中への投影。ここでは、モデル位置の統計的な分布およびモデル位置の不確実性が考慮される。投影された各位置は、推定値ｖと共分散ΛＶで表される。
【００６３】
両方の演算は、まず、配置変換γの下での、三次元位置ｘの二次元画像位置ｖへのカメラ投影πの特性を考慮することにより、理解されうる。γ＝（ｔ，ｒ）とする。三次元位置ｘは、以下の配置変換により三次元位置ｙにマッピングすることができる。
ｙ＝Ｔ（γ，ｘ）＝ｔ＋ｒｘ
そのｙの位置は、下記のカメラ投影ρにより、二次元位置ｖに投影される。
ｖ＝ρ（ｙ）＝λ＊（ｙ１／ｙ３，ｙ１／ｙ３）
ここで、スケーリングファクタλは、問題となっているカメラに関する定数である。これらをまとめると、配置変換γの下でのｘの投影は、以下のように、コンパクトにかける。
ｖ＝π（γ，ｘ）＝ρ（Ｔ（γ，ｘ））
【００６４】
γとｘは、統計Γ＝（μΓ，ΛΓ）と、Ｘ＝（μＸ，ΛＸ）の、多変数ガウス分布確率変数であるとする。一次のオーダで、投影された二次元位置の平均は、μＶ＝π（μΓ，μＸ）である。
【００６５】
二つのよく知られた、ガウス分布の特性が、以下で用いられる。第一に、二つの独立な正規分布に従う確率変数の和の共分散は、それぞれの変数の共分散の和である。第二に、ｐを、共分散がΛＰである正規分布であるとし、ｑは、線型方程式ｑ＝Ａｐで定義されるものとする。ただし、Ａは行列である。そうすると、ｑは正規分布しており、その共分散ΛＱは、以下の式で表される。
ΛＱ＝ＡΛＰＡＴ        （２）
【００６６】
投影された二次元位置の共分散ΛＶを計算するためには、投影πの線形化されたバージョンを考えると都合がよい。ＪΓ＝Ｊγ（μΓ，μＸ）を、γについての、πのヤコビアン行列であるとし、ＪＸ＝ＪＸ（μΓ，μＸ）を、ｘについての、πのヤコビアン行列であるとする。両方とも、μΓとμＸにおいて、評価されている。ヤコビアン行列については、非特許文献１１のような標準的な教科書において議論されている。ヤコビアンのカメラ投影の問題への適用については、非特許文献１２そしてまた非特許文献１３に見出すことができる。
【００６７】
連鎖法則を用いて、Ｔとρについてのヤコビアンから、これらのヤコビアン行列が直接的に導かれる。γについてのＴの偏微分係数行列は３×６のヤコビアンであり、ブロック形式で以下のように表される。
ＪＴ（γ，ｘ）＝［Ｉ３−ｒ＊ｓｋ（ｘ）］
ここで、Ｉ３は、３×３の単位行列であり、ｓｋ（ｘ）は、以下に定義される交代行列である。
【数１】
2008547094.tif 000003
【００６８】
直接微分することにより、Ｊρ（ｙ）は、下記の２×３行列となる。
【数２】
2008547094.tif 000004
【００６９】
この結果、以下のようになる。
ＪＸ＝ＪＸ（μΓ，μＸ）＝Ｊρ（Ｔ（μΓ，μＸ））＊ｒ
ＪΓ＝Ｊγ（μΓ，μＸ）＝Ｊρ（Ｔ（μΓ，μＸ））＊ＪＴ（μΓ，μＸ）        （３）
【００７０】
一次のオーダで、投影された画像の位置の変化Δｖは、以下の式で与えられる。
Δｖ＝ＪΓΔγ＋ＪＸΔｘ
【００７１】
式（２）を適用し、ｘとγが、独立な確率変数であると仮定すると、二次元位置共分散は以下の式で与えられることが導かれる。
ΛＶ＝ＪΓΛΓ（ＪΓ）Ｔ＋ＪＸΛＸ（ＪＸ）Ｔ        （４）
位置共分散ΛΓは、６×６の次元、ΛＸは、３×３の次元、ΛＶは、２×２の次元を有することに注意されたい。
【００７２】
したがって、クラス部分の三次元位置についての正規分布Ｘと、配置変換Γについての正規分布を所与として、配置変換の下で三次元位置を投影して得られる二次元位置の分布の統計的表現Ｖ＝（μＶ，ΛＶ）を計算することができる。
【００７３】
配置変換Γの共分散ΛΓは、次のように計算できる。の三次元位置ｘｉと、対応する二次元画像特徴ｖｉとの対がｎ個あると仮定する。ここでｎは、少なくとも３である。一次のオーダでは、ｉ番目の画像の位置の変化は、以下の式で与えられる。
Δｖｉ＝ＪΓｉΔγ＋ＪＸｉΔｘｉ
ここで、ＪΓｉは、ｘｉで評価されたヤコビアンＪΓであり、ＪＸｉは、ｘｉで評価されたヤコビアンＪＸである。このような方程式がｎ個存在する。
【００７４】
この方程式の集合は、以下のように、さらにコンパクトに表記することができる。すなわち、行列ＪΓｉをまとめて新しい行列ＪΓを生成し、行列ＪＸｉからブロック対角行列ＪＸを生成し、ｖｉとｘｉの値をまとめてベクトルｖとｘをそれぞれ生成することによって、コンパクトに表記できる。後者の共分散行列はΛＶとΛＸであり、これらは、対応する成分共分散行列から構築されたブロック対角行列である。
【００７５】
この結果、以下の式となる。
Δｖ＝ＪΓΔγ＋ＪＸΔｘ
したがって、
ＪΓΔγ＝Δｖ−ＪＸΔｘ
である。
【００７６】
Ｍ＝（ＪΓＴＪΓ）−１ＪΓＴ  であるとする。上記の方程式は、Δγについて解くことができ、
Δγ＝Ｍ（Δｖ−ＪＸΔｘ）
となる。
【００７７】
方程式（２）を適用することにより、配置変換の共分散が以下の式で与えられることが導かれる。
ΛΓ＝Ｍ（ΛＶ＋ＪＸΛＸＪＸＴ）ＭＴ          （５）
ΛＶの表現は、幾つかの方法により取得することができる。それは経験的に定めることもでき、また、センサの特質から計算されてもよい。また、三次元位置共分散ΛＸに比べて小さいときには０と近似しうる。
【００７８】
まとめると、対応する三次元位置と二次元画像位置の集合を与えられたとき、配置変換μΓとその共分散ΛΓを推定することが可能である。そしてこれらの値を用いて、推定された配置変換の下で、三次元位置を投影した二次元画像特徴位置について分布を計算することができる。
【００７９】
後の展開のため、以下の表記が有用である。ｕを観測された二次元画像特徴位置とし、Ｘを、対応する三次元クラスモデル位置の分布であるとする。πを配置変換Γについてのカメラ投影式であるとする。ｖπ＝ｖπ（Ｘ，Γ）を、Ｘが投影された位置の平均値とし、Λπ＝Λπ（Ｘ，Γ）を、式（４）で計算されるように、共分散であるとする。Ｘと配置変換Γを所与として、ｕの確率は、以下の式で表される。
Ｐ（ｕ｜Ｘ，Γ）＝Ｇ（ｕ；ｖπ，Λπ）
ｆを、位置ｕにおける画像特徴と仮定し、ｃを、位置分布がＸであるクラス部分であるとする。便宜上、上記の確率を、クラス部分ｃと配置変換Γを所与としたときの画像特徴ｆの「ジオメトリ尤度」という。これは以下のように表記することができる。
ＭＸ（ｆ，ｃ，Γ）＝Ｐ（ｕ｜Ｘ，Γ）＝Ｇ（ｕ；ｖπ，Λπ）        （６）
この計算は、配置変換の下で、クラス部分ｃと画像特徴ｆとを比較する場合の例である。この場合、この比較は、ジオメトリの位置に基づく比較であり、クラス部分位置を画像に投影することにより実行される。以下に述べるように、配置変換の下でクラス部分ｃを画像特徴ｆと比較する方法には、他の方法もある。また、以下に述べるように、別の実施形態においては、依存関係を考慮してもよい。依存関係は、配置変換を計算するにあたって用いられる特徴部分マッチの尤度を評価するときに、導入される。
［配置変換の下でのアピアランスの投影］
【００８０】
上述のように、局所表面パッチのアピアランスは、あたかも正準な三次元姿勢において、正準なスケールで観測されたかのように、リサンプリングすることができる。配置変換γの下で、二次元関心点が、姿勢φである三次元クラス部分にマッチングされたと仮定する。クラス部分の姿勢によって、クラス部分の局所座標系における三次元点が、そのクラスモデルの座標系に関連づけられる。配置変換によって、そのクラスモデルの座標系の三次元点が、観測されたカメラ座標の座標系に関連づけられる。したがって、これらの合成は、クラス部分の局所フレームの中の点をカメラ画像座標に移す。
【００８１】
したがって、画像中の関心点付近の局所画像パッチを、あたかも正準な姿勢において観測されたかのように、（位置、方向、スケールについて補正をして）リサンプリングすることが可能となる。このリサンプリングされた画像パッチは、三次元クラス部分のアピアランス要素と、完全に位置あわせされる。この処理全体は、「変換γの下での、画像パッチの、姿勢φにおけるクラス部分への配置」と呼ばれる。以下に、詳細を述べる。
【００８２】
アピアランス分布がＡ＝（μＡ，ΛＡ）であり、姿勢分布がΦ＝（μΦ，ΛΦ）であるクラス部分を考える。ｐは、二次元関心点付近の画像パッチを記述するものとする。クラスモデルと画像との間の配置変換の分布を、Γ＝（μΓ，ΛΓ）とする。
【００８３】
二次元画像パッチを三次元クラス部分に配置するにあたり、二次元画像パッチをリサンプリングするために、クラス部分座標における三次元点の格子が特定される。そして、これらの点は、配置変換γとクラス部分の姿勢φを用いて、画像座標に変換される。変換された点は、次に、二次元位置を計算するための透視投影の式を用いて、画像に投影される。そして、姿勢φであるクラス部分への配置γの下で、pのアピアランスを計算するために、投影された二次元画像位置における濃淡度値が、サンプリングされる。
【００８４】
その位置についてのアピアランス情報が記憶されている位置に対応するクラス部分ｃの三次元位置を、ｙ１，ｙ２，．．．，ｙＬとする。ｙ０を、その部分の中心の位置であるとする。それは、また、クラス座標系の中の部分位置でもある。Ｔ（φ，ｙｉ）を、クラス部分姿勢φによるｙｉの変換を表すものとする。
【００８５】
ｐ（ｖ）は、位置ｖにおける画像パッチｐの濃淡度値を表すものとする。そのパッチについての座標系は、そのパッチの関心点の座標が（０，０）となるように選択される。ｙｉにおける濃淡度値の単純なリサンプリングは、
q（ｙｉ）＝ｐ（π（γ，Ｔ（φ，ｙｉ）））
であろう。
【００８６】
本発明は、以下の事実を用いる。マッチングされたときに、クラス部分の中心ｙ０は関心点の二次元位置にマッピンクされなければならない。これに対応するために、
ｖ０＝π（γ，Ｔ（φ，ｙ０））
の投影が計算され、センタリング補正が施される。これにより、リサンプリングの式は、
ｑ（ｙｉ）＝ｐ（π（γ，Ｔ（φ，ｙｉ））−ｖ０）        （７）
となる。
【００８７】
全ての位置ｙｉについて、この演算を繰り返すことにより、リサンプリングされた画像パッチｑを形成することができる。ｑは、配置変換γの下における、画像パッチｐの、姿勢φであるクラス部分への配置である。
【００８８】
第一の、そして第二の実施形態は、三次元格子点を平面であるように取る。この場合、リサンプリング過程は、「画像調整」または、「ホモグラフィ下でのリサンプリング」として知られ、例えば、非特許文献１４のようなコンピュータビジョンの標準的な教科書において説明されている。別の実施形態においては、局所表面ジオメトリを二次曲面、スプライン、または三次元点の束縛されない集合として、モデル化してもよい。
【００８９】
ｑ＝Ｗ（ｐ，γ，φ）は、ｙの全てのＬの値について、式（７）によって特定されるマッピングを表すものとする。したがってＷは、変換γの下で、画像パッチｐの、姿勢φであるクラス部分への配置を計算するために必要な、全てのリサンプリング演算を表す。
【００９０】
式（７）から、ＫΓ（μΓで評価されたγについてのＷのヤコビアン）と、ＫΦ（μΦで評価されたφについてのＷのヤコビアン）を計算することができる。ＫΓについては、一度に一行ずつ計算される。ｉ番目の行は、ｙｉにおいて評価された、γについてのＷの偏導関数であるＫΓ，ｉである。位置ｙｉについて、式（３）は、２×６の行列
ＪΓｉ＝ＪΓ（μΓ，Ｔ（φ，ｙｉ））
を記述する。これは、γについてのπのヤコビアンである。ここで、
ＪΓ０＝ＪΓ（μΓ，Ｔ（φ，ｙ０））
とする。１×２の行ベクトル∇ｐ（ｖ）は、画像パッチｐの、位置ｖにおける、空間的勾配を表記するものとする。さらに、∇ｐｉは、∇ｐ（ｖｉ）をあらわすものとする。ただし、
ｖｉ＝（π（μΓ，Ｔ（φ，ｙｉ））−ｖ０）
である。画像の空間勾配を計算する方法については、例えば、非特許文献１４のようなコンピュータビジョンの標準的な教科書に取り上げられている。連鎖法則を式（７）に適用することにより、ＫΓのｉ番目の行は、
ＫΓ，ｉ＝∇ｐｉ（ＪΓｉ−ＪΓ０）
となる。この量を全てのｉについて計算することで、Ｌ行６列のＫΓが生成される。
【００９１】
ＫΦを計算するにあたって、φは、回転ｒと並行移動ｔの合成であることに注意されたい。ｙｉに作用するφ＝（ｔ，ｒ）についてのＴの偏導関数の行列は、３×６のヤコビアンであり、ブロック形式で、Ｋｉ＝［Ｉ３−ｒ＊ｓｋ（ｙｉ）］で与えられる。ここでＩ３は、３×３の単位行列であり、ｓｋ（ｙｉ）は、３×３の交代行列を表す。ＪＸは、二番目の独立変数に関してπのヤコビアンであったことを思い出されたい。このヤコビアンは、μΓと、位置Ｔ（μΦ，ｙｉ）で評価される。連鎖法則により、ＫΦのｉ番目の行は、以下の式で表される。
ＫΦ，ｉ＝∇ｐｉ（ＪＸ（μΓ，Ｔ（μΦ，ｙｉ））＊Ｋｉ−ＪＸ（μΓ，Ｔ（μΦ，ｙ０））＊Ｋ０）
この量を全てのｉの値について計算することで、Ｌ行６列のＫΦが形成される。  
【００９２】
これらの量が確立されると、一次のオーダでは、配置されたクラス部分アピアランスの平均と分散は、以下の式で表される。
μＱ＝Ｗ（ｐ，μΓ，μΦ）            （８）
ΛＱ＝ＫΦΛΦＫΦＴ＋ＫΓΛΓＫΓＴ        （９）
【００９３】
画像特徴アピアランスＱ＝（μＱ，ΛＱ）が所与であるとき、μＱがμＡとマッチングするかを判定することを考える。このテストにおいては、差μＡ−μＱを計算し、その結果を分散ΛＡ＋ΛＱであるゼロ平均確率変数としてモデル化することにより、近似できる。その結果、確率は、上述の計算で得たμＱとΛＱを用いて、以下のように書くことができる。
Ｐ（ｐ｜Ａ，Ｑ）＝Ｇ（μＡ−μＱ；０，ΛＡ＋ΛＱ）
この確率を計算する別の近似方法は、［別の実施形態］の節において与えられる。
【００９４】
ｆを、リサンプリングの後は分布Ｑで表現されるアピアランスｐの画像特徴であるとする。ｃを、アピアランス分布がＡであるクラス部分であると仮定する。便宜上、上記の確率を、画像特徴ｆ、所与のクラス部分ｃ、そして配置Γの「アピアランス尤度」と記す。これは、以下の式で書くことができる。
ＭＡ（ｆ，ｃ，Γ）＝Ｐ（ｐ｜Ａ，Ｑ）＝Ｇ（μＡ−μＱ；０，ΛＡ＋ΛＱ）        （１０）
この計算は、配置変換の下での、クラス部分ｃと画像特徴ｆの比較する例である。この場合、該比較はアピアランスの比較であり、該比較は画像特徴のアピアランスをリサンプリングすることで実行される。
【００９５】
様々な実施形態において、この確率の近似にあたって別の方法を選んでもよいし、また、他の統計的または非統計的な方法を用いて、配置変換の下でのアピアランスマッチの確率や質について計算してもよい。
【００９６】
幾つかの実施形態においては、以下の事実を考慮すると有利かもしれない。その事実とは、濃淡度パッチの中心のピクセル間では、パッチの端のピクセル間におけるよりも、ばらつきが少なくみられることである。これは、パッチの姿勢または配置変換の不確実性のためである。これは、パッチを様々な解像度で、すなわち、パッチの中心から高解像度で始めて、パッチの境界の近傍ではサンプリング解像度を落としてサンプリングすることにより、説明されるだろう。
［二次元画像特徴の三次元クラス部分へのマッチングによる認識］
【００９７】
クラスインスタンス認識の最終ステップにおいては、クラス部分を画像の特徴と比較し、認識決定をするために、上述の手法が用いられる。クラスインスタンスを認識すること、とは漠然とした課題である。ビジュアルクラスは、視覚的特徴を共有するが、一部の画像においては、視覚的特徴については本質的に曖昧な解釈に陥りがちである。さらに、オクルージョンにより、オブジェクトの一部のみが画像中に見える状態で描画されるかもしれない。その部分が、曖昧な解釈に陥りやすい部分かもしれない。曖昧である場合には、認識したほうがよいか（間違って認識する恐れがある）、または認識しないほうがよいか（間違って認識しない恐れがある）、決定しなければならない。本発明の様々な実施形態は、これらの決定がどのようになされるかにおいて、特別な選択肢を採用している。
【００９８】
ある実施形態において、ある選択肢を採用する方法の一つは、特徴の集合が、クラスのインスタンスであるか否かを決定するために、関数を用いるものである。この関数は、クラスモデルと画像特徴と集合との一致点を、スコアとして記録するために用いられる。この関数を、「クラススコア」と呼ぶ。Ｃをクラスモデルとする。Ｆを二次元特徴の集合であるとする。クラススコアは、Ｓ（Ｆ，Ｃ）と書かれてもよい。本発明の様々な実施形態において、クラススコアは、いろいろな方法で定義される。
【００９９】
一部の実施形態においては、クラススコアを、下記に定義される「クラスの尤度比」であると定義する。この方法は、特徴の集合ＦをクラスＣのインスタンスとして認識するにあたって、（Ｆ，Ｃ）が非常に優勢な証拠によって裏付けられ、別のクラスには、非常に優勢な証拠がないときに好適である。別の実施形態では、クラススコアを、ＦとＣの間の個別のマッチング尤度の、ある関数であると定義する。この方法は、特徴の集合ＦをクラスＣのインスタンスとして認識するにあたって、（Ｆ，Ｃ）が非常に優勢な証拠によって裏付けられているときに好適である。この方法では、他のクラスについては直接的に考慮しない。また別の実施形態では、クラススコアを、ＦとＣの対応箇所の数であると定義する。この方法は、特徴の集合ＦをクラスＣのインスタンスとして認識するにあたって、証拠を支持する箇所の数が多いときに好適である。別の実施形態においては、また別のクラススコアの定義が用いられてもよい。
【０１００】
クラススコアＳ（Ｆ，Ｃ）が、閾値τＣよりも大きいならば、クラスＣのインスタンスは、その画像に存在すると考えられる。閾値τＣは、例えばクラスやマッチングする特徴の数など、様々な要素の関数であってよい。経験から決定されてもよい。経験から決定するにあたっては、既知のラベルを有するテストケースを取得し、特定の基準での認識結果を最大とするように、τＣの値が選ばれる。これを実行するため特別な手法の一つは、［第一の実施形態］において記述される。別の手法は、［別の実施形態］において記述される。
【０１０１】
取りうるクラススコアの様々な選択肢は、しばしば同じ結果をもたらす。しかしながら、結果が異なる状況も存在する。本発明の様々な実施形態においては、クラススコアについて異なる定義を用いられてよく、その選択は、ある程度、意図する用途に基づいてなされる。
【０１０２】
Ｃをクラスモデルとする。Ｆを画像中の二次元特徴の集まりであるとする。クラス尤度比は、以下の式で定義される。
Ｌ（Ｆ，Ｃ）＝Ｐ（Ｆ｜Ｃ）／Ｐ（Ｆ｜〜Ｃ）
ここで、Ｐ（Ｆ｜Ｃ）は、クラスＣのいくつかのインスタンスが画像中に存在すると仮定したときの、画像特徴Ｆの確率である。Ｐ（Ｆ｜〜Ｃ）は、クラスＣのいくつかのインスタンスが画像中に存在しないと仮定したときの、画像特徴Ｆの確率である。以下に述べる第一の実施形態においては、クラススコアはクラス尤度比であると定義されている。
【０１０３】
クラス尤度比は、二つの変数を所与として計算される。第一の変数は、仮定される関連づけの集合である。すなわち、画像特徴と、共通のクラスモデルに属するクラス部分との、いわゆる、「特徴部分マッチ」である。特徴部分マッチの集合と、そのクラスモデルは、「対応仮説」と呼ばれ、ｈで表示される。第二の変数は、三次元クラスモデルを画像中のそのクラスのインスタンスと対応づける配置変換Γである。これら、二つの付加的な変数の関数として、クラス尤度比は、Ｌ（Ｆ，Ｃ，Γ，ｈ）の形式を有する。
【０１０４】
クラス尤度比は、アピアランス尤度比ＬＡ、ジオメトリ尤度比ＬＸ、そしてディスカウントファクタＬＤを用いて、近似される。これらは、対応仮説ｈと、配置変換Γに依存する。「アピアランス尤度比」は、以下のように書くことができるだろう。
ＬＡ（Ｆ，Ｃ，ｈ，Γ）＝Ｐ（ＦＡ｜Ｃ，ｈ，Γ）／Ｐ（ＦＡ｜〜Ｃ）
ジオメトリ尤度比は、以下のように書くことができるだろう。
ＬＸ（Ｆ，Ｃ，ｈ，Γ）＝Ｐ（ＦＸ｜Ｃ，ｈ，Γ）／Ｐ（ＦＸ｜〜Ｃ）
ディスカウントファクタＬＤは、マッチングの数と、予測されたマッチングの数の比較に基づいて、結果に重みをつけるために用いられる。以下に述べる第一の実施形態では、このファクタは１に設定されている。１以外のディスカウントファクタの使用については、［別の実施形態］の節に記述される。
【０１０５】
シーンのクラス認識における目的は、三次元シーン中の各クラスインスタンスの姿勢を計算して、クラスインスタンスを認識することである。姿勢は、配置変換の平均として、与えられる。それぞれの計算において、全ての考えられる対応仮説ｈの確率の和をとりつつ、最大尤度法で姿勢を選択することが要求される。実際には、極めて確実な結果をもたらすことがゴールである。この場合には、一の対応仮説ｈが、他のすべてより優勢となる。結果として、ｈについての和は、最大値で近似できる。したがって、クラス尤度は、以下の近似式で計算してもよい。
Ｌ（Ｆ，Ｃ）＝ｍａｘｈｍａｘΓＬＡ（Ｆ，Ｃ，ｈ，Γ）ＬＸ（Ｆ，Ｃ，ｈ，Γ）ＬＤ（Ｃ，ｈ，Γ）
もしも、この式の結果が閾値を超えるならば、クラスＣのインスタンスが存在すると判断される。
【０１０６】
別の実施形態においては、クラス尤度以外のクラススコアが用いられてよいが、基本的な方法は同様である。該方法によると、対応仮説と、配置変換にもとづいて計算されたクラススコアの計算が課される。該方法によると、そのスコアが受け入れ基準を満たす対応仮説が選択される。クラススコアを最大とする対応仮説ｈの値によって、特徴部分対応が特定される。クラススコアを最大とする配置変換Γの値によって、そのシーンのクラスインスタンスの位置と方向が特定される。
【０１０７】
該認識方法においては、対応の集合を用いて、クラスモデルを画像データに配置し、姿勢不変な特徴記述子を使用し、対応を評価する。また、該認識方法においては、配置のジオメトリを用いて、アピアランスとジオメトリの特徴部分マッチの結合尤度を評価する。さらに、該認識方法においては、付加的な特徴部分マッチを評価するために、結合尤度を用いる。これら全てが、本発明の利点である。
【実施例】
【０１０８】
［第一の実施形態］
第一の実施形態について、以下に、（１）データベース構築、（２）画像中の認識、の順に記載する。
［第一の実施形態におけるデータベース構築］
【０１０９】
クラスデータベースは、クラスモデルの集合で構成される。図３は、クラスモデルを構築する際の主なステップを示す。ステップ３０１において、クラスに属するサンプルオブジェクトの三次元画像が取得される。ステップ３０２において、それぞれのサンプルオブジェクトについて、オブジェクトモデルが構築される。ステップ３０３において、オブジェクトモデルが正準ジオメトリ形式に設定される。ステップ３０４において、正準ジオメトリ形式において各オブジェクトモデルが合成されて、クラスモデルが形成される。
［三次元画像の取得］
【０１１０】
制御された状況の下で、サンプルオブジェクトを複数の視点から見た複数のサンプル画像が得られる。これらを便宜上、オブジェクトの「ビュー」と呼ぶ。シーンは、既知の高さの水平な平面上にある、一の前景のオブジェクトを含む。背景は、既知の姿勢における一様な色およびテクスチャの平面の、単純なあつまりである。ステレオシステムが、三次元画像を取得する。
【０１１１】
ステレオシステムの一の実施形態においては、あるパターンの光を、シーンに投射する投影機、画像を取得する二以上のカメラの組、ステレオ対応を用いてシーン中の点の三次元位置を計算するコンピュータを用いる。このステレオシステムの実施形態は、ここでその全てを援用する特許文献３に開示される。他の実施形態は、［別の実施形態］の節に記述される。
【０１１２】
それぞれの三次元画像について、関心点の位置が特定される。そして、記述子が、それぞれの関心点について計算される。関心点は、非特許文献７に記述されるように、ハリス・ラプラス関心点検出器を計算することにより、位置が特定される。一旦検出されると、ハリス・ラプラス関心点演算子によって計算された主要な勾配方向は、関心点の面の法線に関する回転を決定するために用いられる。関心点における面の法線は、主要な勾配の方向と共に、特徴の姿勢を計算するために用いられる。
【０１１３】
第一アピアランス記述子は、局所アピアランスをリサンプリングし、それによって、正準アピアランス記述子を計算するために、特徴姿勢と特徴のスケールを用いて構築される。これは、Ａ型記述子と呼ばれる。これは、三次元距離情報を用いて、スケール、スラント、ティルト、距離に対して不変であるように計算される。すなわち、Ａ型記述子は、姿勢不変である。別の実施形態においては、他の方法で、姿勢不変であるＡ型の特徴記述子を計算してもよい。
【０１１４】
さらに、第二のアピアランス記述子も構築される。これは、非特許文献１５によって導入された、スピン画像手法に基づく。この手法は、非特許文献１６によって提案されたように、濃淡画像に作用するように修正されている。この結果えられる濃淡スピン記述子は、Ｂ型記述子と呼ばれる。これは、二次元濃淡度情報のみを用いて計算されるため、姿勢に対して不変ではない。別の実施形態においては、他の、二次元濃淡度情報のみを用いるアピアランス記述子を用いてもよい。
【０１１５】
Ａ型とＢ型の両方のアピアランス記述子において、輝度やコントラストなどの変化のような光度の効果は、濃淡度値の平均値を差し引き、標準偏差で割ることにより除去される。これらの、または他の光度のばらつきの影響を減少させ、または除去する方法は、当該技術分野において当業者によく知られている。
【０１１６】
このようにして、オブジェクトの各三次元画像は、オブジェクトの「要素」の集合と、関連付けされる。それぞれの関心点について、一の要素が関連付けられる。それぞれの要素は、＜φ，ａ，ｂ＞の形式を有する。ここで、φは検出された特徴の三次元姿勢、成分ａは、Ａ型アピアランス記述子、そして  成分ｂは、Ｂ型アピアランス記述子である。本願発明の革新的な点の一つは、これらの二つのアピアランス記述子の構築と使用である。これらの、クラス構築及び認識における使用について、以下に述べる。そこでは、これらの用途がより明確になるであろう。
【０１１７】
三次元画像は、制御された条件下で撮られる。そうすると、各三次元画像が、付加的に、関連するビュー姿勢を有することになる。このビュー姿勢は、固定されたベースの座標系に相対的に表現される。このビュー姿勢を用いて、要素は、共通の座標系に変換される。共通座標系における要素の集合は、オブジェクトモデルを形作る。
［オブジェクトモデルの正準ジオメトリ形式への設定］
【０１１８】
次のステップは、それぞれの、オブジェクトモデルを正準ジオメトリ形式へ設定することである。その結果のモデルは、「正準ジオメトリ」を有するといわれる。処理は以下のとおりである。
１  オブジェクトの三次元要素位置の集合のセントロイドが計算される。ｆｉ＝＜ｘｉ，ａｉ，ｂｉ＞およびｘｉ＝＜ｔｉ，ｒｉ＞の形式のオブジェクト要素ｆ１，ｆ２，．．．ｆｎについてのセントロイドは、下記の三次元位置の平均である。
μＯ＝（１／ｎ）Σｉｔｉ
２  オブジェクトのスケールは、以下のように計算される。
σＯ＝（１／ｎ）Σｉ||ｔｉ−μＯ||
３  それぞれの要素ｔｉ＝（ｘｉ，ｙｉ，ｚｉ）Ｔについて、正準位置ｔ’ｉが、中心を差し引き、オブジェクトのスケールで割ることにより、計算される。
ｔ’ｉ＝（ｔｉ−μＯ）／σＯ
４  新たなオブジェクトの要素ｆ’ｉが作られる。
ｆ’ｉ＝＜ｙｉ，ａｉ，ｂｉ＞
ただしｙｉ＝＜ｔ’ｉ，ｒｉ＞である。
【０１１９】
このプロセスの結果、要素ｆ’１，ｆ’２，．．．ｆ’ｎによるオブジェクトモデルが得られる。本実施形態においては、オブジェクトのジオメトリを同型の位置とスケールに標準化し、オブジェクト要素のアピアランスを保存する。他の実施形態においては、［別の実施形態］の節で記述されるように、他の方法で標準化することが可能である。幾つかのケースでは、標準化は、次に述べるステップでインタリーブされてもよい。一般的に、この結果は、正準ジオメトリによるオブジェクトモデルとなり、「正準オブジェクトモデル」と呼ばれる。
［正準オブジェクトモデルからのクラスモデルの構築］
【０１２０】
データベースは、それぞれのクラスについての一つずつの三次元クラスモデルの集合である。それぞれのクラスモデルは、他のクラスモデルから、独立に構築される。それぞれのクラスモデルは、そのクラスを構築するのに用いられるサンプルオブジェクトの統計的記述である。
【０１２１】
クラスモデルは、クラス部分の集まりである。それぞれのクラス部分が、サンプルオブジェクトの対応要素の統計的モデルである。クラス部分は、＜Φ，Ａ，Ｂ，η＞の形式を有する。分布Φ＝（μΦ，ΛΦ）は、オブジェクト中心ジオメトリ参照系で表現された、対応要素の三次元姿勢の平均と共分散である。分布Ａ＝（μＡ，ΛＡ）は、対応要素の正準アピアランスの平均と共分散である。これは、クラス部分のＡ型のアピアランス記述子で、姿勢不変である。分布Ｂ＝（μＢ，ΛＢ）は、対応要素のＢ型のアピアランスの平均と共分散である。これは、クラス部分のＢ型のアピアランス記述子である。部分アピアランスは、分布ＡとＢからなる。それぞれの分布は、「分布アピアランスの成分」の一つであるといわれる。値ηは、そのクラス部分に寄与した要素と、そのクラス中のサンプルオブジェクトの総数との比である。
【０１２２】
クラスモデルは、まず、そのクラスに属するすべての正準オブジェクトモデルの要素の三次元位置を考慮することにより、作られる。常に検出されるオブジェクトの要素は、正準モデルにおいて、三次元位置のクラスタを形成するだろう。ｋ平均クラスタリング手法が、これらの位置クラスタの位置を特定するために、用いられる。ｋの値は、モデル化処理の間に、経験的かつ相互作用的に決定される。それぞれの位置クラスタは、対応要素の集合を特定し、そしてクラス部分の基礎として用いられる。それぞれの位置クラスタについて、平均と共分散が計算され、部分ジオメトリの「位置成分」として、記憶される。これは、Ｘ＝（μＸ，ΛＸ）で指定される。
【０１２３】
部分ジオメトリはまた、「回転成分」を有する。ある特定の位置クラスタにおいて、ｎ個の要素があると仮定する。ここで、位置クラスタの回転は、ｒ１，．．．，ｒｎであり、それぞれが３×３の回転行列として表される。クラス部分の平均回転は、以下のように計算される。はじめに、和が作られる。
ｒｓｕｍ＝Σｉｒｉ
次に、ｒｓｕｍの特異値分解が計算される。これにより、ｒｓｕｍはＵＳＶＴとして表現される。ただし、ＵとＶは直行行列であり、Ｓは対角行列である。平均回転は、以下の式で計算される。
ｒｍｅａｎ＝ＵＶＴ
平均回転のこの形式は、ときおり、文献で「投影された算術平均」と呼ばれる。平均回転を計算するためには、非特許文献１７に記述されるように、他の手法もある。このような手法は、別の実施形態で用いられてもよい。
【０１２４】
回転ｒｉであるクラスタのｉ番目の要素について考える。ｑｉを平均からのｒｉの偏差を表現する回転であるとする。すなわち、ｒｉ＝ｒｍｅａｎ＊ｑｉであり、したがって、
ｑｉ＝ｒｍｅａｎＴｒｉ
である。
【０１２５】
統計的分散を計算するために、それぞれのｑｉは、非冗長形式で３次元ベクトルとして、表現されている。ｑｉに対応する傾斜軸は、非特許文献１８に記述されるように、四元数に、そして次に角度に変換することにより、計算される。その結果、単位ベクトルｋと、角度θで表される、ｋについての回転を表す回転軸が得られる。非冗長的な表現を得るために、ｋにθをかけることで、三つの量ｋＸθ、ｋＹθ、ｋＺθが生ずる。ｖｉを、このｉ番目の要素の三次元ベクトルであるとする。クラス部分回転の共分散は、ｖｉの共分散
ΛＲ＝（１／ｎ）Σｉｖｉ（ｖｉ）Ｔ
から構成される。回転平均と共分散は、クラス部分ジオメトリの「回転成分」を構成する。
【０１２６】
したがって、クラス部分の姿勢の分散は、Φ＝（μΦ，ΛΦ）である。ここで、μΦ＝（μＸ，ｒｍｅａｎ）であり、ΛΦは、ΛＸとΛＲで構成されるブロック対角行列である。これはまた、Φ＝＜Ｘ，Ｒ＞と書くこともできる。ここで、Ｘは、三次元位置の分布であり、Ｒは、回転についての分布である。
【０１２７】
オブジェクト要素｛ｅ１，．．．ｅｎ｝のクラスタである位置クラスタが上記のように計算されたと仮定する。それぞれの要素は、二つのアピアランス記述子ａｉと、ｂｉを有する。これらの、アピアランス記述子は、二つの平均と、二つの共分散行列を用いてモデル化することができる。一つは要素のａｉアピアランスであり、もう一つは、ｂｉアピアランスである。アピアランス記述子は、高次数であるため、二つの共分散行列はそれぞれ、それぞれのアピアランス記述子データ要素の独立分散を含む対角行列として、近似される。
【０１２８】
別の実施形態においては、アピアランスについての統計的モデルを計算する前に、アピアランス記述子について次元縮退を施してもよい。別の実施形態においては、また、ガウス分布の混合をアピアランスについての表現であるとして、計算してもよい。これは、例えば、いくつかのクラスにおいて、二以上の異なるように見えるクラス部分があり、クラス中のオブジェクトの集合において、空間的に同じ位置を占めているような用途において有用である。
【０１２９】
最後に、各クラス部分について、部分に寄与するオブジェクト要素の数が表にされ、比ηが計算される。その結果、得られるクラス部分ｃは、以下の通りである。
ｃ＝＜Φ，Ａ，Ｂ，η＞＝＜μΦ，ΛΦ，μＡ，ΛＡ，μＢ，ΛＢ，η＞
【０１３０】
二つの異なるアピアランス記述子の使用は、本発明の利点の一つである。認識において、Ｂ型のアピアランス記述子が、二次元濃淡画像の特徴と、三次元クラス部分との間の可能性のある対応の位置を特定するために用いられる。これらの対応の集合を用いて、本認識方法においては、クラスモデルが画像に配置される。そして、その対応の確率についてのより正確な評価を提供するために、Ａ型の姿勢不変な特徴記述子が用いられる。
【０１３１】
上述のように、三次元クラスモデルは、クラス部分の集まりで構成される。クラスデータベースは、三次元クラスモデルの集合から構成される。さらに、データベースは、認識において用いられる閾値の集合も含む。これらの閾値は、以下の通りである。
（１）τｐａｉｒ  初めに、もっともらしい特徴部分マッチを見つけたとき、特徴部分マッチ＜ｆ，ｃ＞を保持するためのスコア値についての最小限の閾値。
（２）τｍｉｎＨ，τｍａｘＨ  初期対応仮説における、特徴部分マッチの数の最小値と最大値。
（３）τｉｎｉｔ（ｓ）  初期対応仮説を、拡張する仮説として受け入れるための仮説のスコアについての最小限の閾値。これは、初期の対応仮説の長さｓの関数である。
（４）τＣ  クラスのインスタンスがそのシーンで認識されたことを決定するための、クラス尤度比の最小の閾値。
これらの閾値は、三次元クラスデータベースが、構築されたときに、計算される。しかしながら、便宜上、まず認識におけるこれらの使用について記述し、続いてその計算方法について説明する。
【０１３２】
さらに、別の実施形態は、特別な性質を有するクラス部分について、より早く位置が特定されるように、クラスデータベースにおいて、様々な指標を含んでもよい。
［第一の実施形態における認識］
［概要］
【０１３３】
基本的に、クラスインスタンスの認識は、好適な対応仮説の探索である。直感的に、認識には、画像の一部とクラスモデルとの対応の発見が伴う。認識処理は、図４に示すように、この直感を反映する。ステップ４０１において、画像の特徴が、特定される。ステップ４０２において、対応する仮説が構築される。ステップ４０３において、配置変換が計算される。ステップ４０４において、対応する仮説が評価される。ステップ４０５において、クラススコアが受け入れ基準を満たす対応仮説が選択される。
【０１３４】
この処理においては、好適な対応仮説を見つけることが要請される。好適な対応仮説を見つけることは、探索の問題である。対応仮説は、複数の特徴と部分の対応を有するため、探索は組み合わせの問題である。問題は、探索木として視覚化される。探索木は、広範に研究されている。多くの探索手法があり、各手法について、多くのバリエーションと改良版がある。本発明の様々な実施形態において、様々な探索手法が用いられる。
【０１３５】
第一の実施形態で用いられる探索手法の主なステップが、図５に示される。ステップ５０１において、もっともらしい画像特徴とクラス部分のマッチが決定される。ステップ５０２において、複数の初期対応仮説が構築される。ステップ５０３において、対応仮説の下でのクラス尤度比を計算することにより、初期対応仮説が採点される、すなわちスコアがつけられる。ステップ５０４において、一以上の初期対応仮説について、さらなる検討のために受け入れるか否かのテストが行われる。もし、受容される仮説が存在しなければ、ここで手順は終了する。ステップ５０５において、最適な初期対応仮説が拡張されるべく選択される。ステップ５０６において、対応仮説が、さらなる画像特徴とクラス部分とのマッチを用いて拡張され、最終的には、最終対応仮説となる。ステップ５０７において、最終対応仮説を用いて、そのシーンでクラスインスタンスを認識できたか否かのテストが行われる。認識できたならば、それは、認識されたクラスインスタンスの集合に加えられる。ステップ５０８において、また別の初期対応仮説を探索するために、処理はステップ５０３に戻り、探索が継続される。
［画像特徴とクラス部分との、もっともらしいマッチングの決定］
【０１３６】
シーンの二次元画像が取得され、関心点を、ハリス・ラプラス関心点検出器を用いて、認識するため処理がなされる。それぞれの関心点について、特徴記述子ｆ＝（ｕ，ｐ，ｂ）が構築される。値ｕは、二次元画像位置であり、値ｐは、その位置ｕを囲む画像パッチであり、そしてｂは、Ｂ型のアピアランス記述子である。このＢ型のアピアランス記述子は、クラス部分のＢ型部分アピアランス構築に用いられたスピン画像手法を用いて計算される。クラスデータベース構築に用いられのと同じ光度の正規化が、アピアランス記述子に適用される。三次元ジオメトリ情報は、二次元画像上では利用できないため、Ａ型アピアランス記述子は、計算できないことに注意されたい。
【０１３７】
それぞれの画像特徴について、クラス部分とのもっともらしいマッチングが、アピアランス尤度を計算することにより、決定される。ｆ＝（ｕ，ｐ，ｂ）を画像特徴とし、ｃ＝（Φ，Ａ，Ｂ，η）をクラス部分であるとする。Ｂ型のアピアランス記述子ｂを用いて、画像特徴ｆの確率は、クラス部分ｃを所与として、以下のアピアランス尤度ＭＢ（ｆ，ｃ）で与えられる。
ＭＢ（ｆ，ｃ）＝Ｐ（ｆ｜ｃ）＝Ｇ（ｂ；μＢ，ΛＢ）
ここで、Ｇ（ｂ；μＢ，ΛＢ）は、式（１）で定義される。それぞれの画像特徴ｆについて、ＭＢ（ｆ，ｃ）の値は、データベース中の全てのクラス部分ｃについて計算される。
ＭＢ（ｆ，ｃ）≧τｐａｉｒ        （１１）
である特徴部分マッチ＜ｆ，ｃ＞が保持される。ＭＩＮＩＴは、このような対すべての集合を表すものとする。
【０１３８】
便宜上、クラス部分ｃが属するクラスＣを「ｃのクラス」と呼ぶ。また、便宜上、その閾値テストの下で保持された対をクラスごとにまとめるほうが都合がよい。適応する画像特徴を有する各クラスについて、その集合Ｓ（Ｃ）が以下のように構築される。
Ｓ（Ｃ）＝｛＜ｆ，ｃ＞｝        （１２）
ここで、ｃのクラスはＣであり、＜ｆ，ｃ＞∈ＭＩＮＩＴである。
【０１３９】
後述するように、別の実施形態においては、全ての特徴ｆとクラス部分ｃについてのＭＢ（ｆ，ｃ）を計算することおよびテストすることを避けてもよい。これは、効率的な検索を支援する情報、および、可能なクラス部分ｃの集合が与えられた画像特徴ｆについてのみ考慮されるよう制限する情報を含む、付加的なデータ構造を格納することにより、行われる。
［初期対応仮説の集合の構築］
【０１４０】
次のステップは初期対応仮説の集合Ｈ０の構築である。一般的に、Ｈ０は、複数の対応仮説を含むでろう。複数であることには、二つの理由がある。第一に、複数のクラスインスタンスがシーンの中にあるかもしれない。それぞれについて、少なくとも一の対応する仮説が必要である。第二に、画像の一部について、クラスインスタンスとして、複数の解釈が可能な場合があり、それぞれの解釈が対応仮説を有する。
【０１４１】
初期対応仮説の集合Ｈ０は、いくばくかの、対応する画像特徴を有する各クラスを考慮することにより構築される。Ｃをそのようなクラスであるとする。Ｓ（Ｃ）＝｛＜ｆ，ｃ＞｝を式（１２）で定義されるように計算されるものとする。Ｃに関連づけられた初期対応仮説は、それぞれの集合が、τｍｉｎＨと、τｍａｘＨの間の成分を有し、同じ第一の成分をもつ二つの対がないような、すべての特徴と部分のマッチングの集合である。各そのような集合が初期対応仮説に組み込まれる。少なくとも、配置変換が計算できるように、三つの成分が要求される。初期対応仮説の配置変換の分散を制御するために、閾値τｍｉｎＨ≧３のものには課される。そのような仮説の数を制限するために、閾値τｍａｘＨが課される。したがって、初期仮説ｈ０は、［＜ｆ１，ｃ１＞＜ｆ２，ｃ２＞，．．．＜ｆｄ，ｃｄ＞］の形式をもつ。ここで、ｄ∈［τｍｉｎＨ，τｍａｘＨ］、ｉ＝ｊのときのみ、ｆｉ＝ｆｊである。ｃｉの共通のクラスは、「仮説のクラス」と呼ばれる。別の実施形態においては、他の方法で初期仮説を選択してもよい。
［クラス尤度比の計算による初期対応仮説のスコア］
【０１４２】
各初期仮説ｈ０について、配置変換Γが画像とクラスモデルの間で計算される。特に、上記の非特許文献１０の方法が、二次元画像位置ｕの集合と、三次元クラス部分の平均位置μＸの集合に適用され、平均の配置変換μΓが生成される。姿勢の共分散ΛΓが、式（５）で述べたように、計算される。配置変換の仮説に対する関数依存性をΓ（ｈ）と示すことが便利な場合もある。
【０１４３】
三次元クラスモデルと、画像特徴の集合の間の初期のマッチの集合から、配置変換の分布を計算することができる。そして、これは本発明の利点の一つである。その分布は、後述のように、次々と、幾つかの重要な量を計算することを可能にする。
【０１４４】
＜ｆ，ｃ＞を初期対応仮説ｈ０の対であるとする。ここで、ｆ＝（ｕ，ｐ，ｂ）であり、ｃ＝（Φ，Ａ，Ｂ，η）である。Γ＝（μΓ，ΛΓ）を配置変換であるとする。Γを用いて、リサンプリング後の画像パッチｐのアピアランスについて、Ｑ＝（μＱ，ΛＱ）が計算される。平均は、式（８）で述べたように、パッチをリサンプリングして、μＱ＝Ｗ（ｐ，μΓ，μΦ）を生成することにより、計算される。共分散ΛＱは、式（９）で述べたように計算される。ΓについてのμＱとΛＱの関数依存性をμＱ（Γ）およびΛＱ（Γ）と書いて示す方が便利な場合もある。
【０１４５】
「配置アピアランス尤度」ＭＡ（ｆ，ｃ，Γ）は、式（１０）で計算される。
ＭＡ（ｆ，ｃ，Γ）＝Ｐ（Ｑ｜Ａ）＝Ｇ（μＡ−μＱ（Γ）；０，ΛＡ＋ΛＱ（Γ））
配置されたアピアランス尤度は、配置変換Γをもちいて、画像特徴ｆのパッチを投影する。これにより、画像特徴のアピアランスにおける、ティルトとスラントの影響が考慮される。対応仮説ｈが真である場合、配置変換Γ（ｈ）は、真である。そして、投影することにより、関連するアピアランスの変化についての補正を正確に行うことができる。これは、配置変換の下でのアピアランス比較の例であり、別の実施形態においては、他の方法による配置変換の下で、アピアランスの比較してもよい。配置変換の下でのアピアランスの比較を、対応仮説から計算することができる事実は、本発明の利点の一つである。
【０１４６】
ｈ０においてマッチングされた対＜ｆ，ｃ＞それぞれのジオメトリ尤度もまた、計算される。ｆ＝（ｕ，ｐ，ｂ）であるとする。ｃ＝（Φ，Ａ，Ｂ，η）であるとする。Φ＝＜Ｘ，Ｒ＞であるとする。ここで、Ｘは、三次元位置の分布である。（４）において計算されるように、μπ＝μπ（Ｘ，Γ）を、Ｘの投影された位置の平均値であるとし、Λπ＝Λπ（Ｘ，Γ）を分散であるとする。ＭＸ（ｆ，ｃ，Γ）はジオメトリ尤度Ｐ（ｆ｜ｃ，Γ）を表記するものとする。Ｐ（ｆ｜ｃ，Γ）は、評価された変換Γの下でのクラス部分ｃの位置の画像への投影を所与として、位置ｕにおいてｆを観測した確率密度値である。ＭＸ（ｆ，ｃ，Γ）は、（６）によって計算される。
ＭＸ（ｆ，ｃ，Γ）＝Ｐ（ｕ｜Ｘ，Γ）＝Ｇ（ｕ；μπ，Λπ）
配置変換Γを所与として、特徴ｆにマッチングするクラス部分ｃ＝（Φ，Ａ，Ｂ，η）の結合尤度は、以下の通りである。
ＭＪ（ｆ，ｃ，Γ）＝η＊ＭＸ（ｆ，ｃ，Γ）＊ＭＡ（ｆ，ｃ，Γ）
【０１４７】
対＜ｆ，ｃ＞の結合アピアランスジオメトリ尤度比は、以下のとおりである。
Ｌ（ｆ，ｃ，Γ）＝ＭＪ（ｆ，ｃ，Γ）／（ｒ＊ｍａｘｋＭＢ（ｆ，ｋ））
スカラーｒは、画像中の、どこかに現れる特徴の尤度を示す定数である。ｒの値は、１／Ｎｐｉｘｅｌとなるように取られる。ここで、Ｎｐｉｘｅｌは、画像中のピクセルの数である。クラス部分ｋは、＜ｆ，ｋ＞∈ＭＩＮＩＴ 、であるが、ｋはＳ（Ｃ）に含まれないという条件を満たすべく、制限される。ここで、Ｃは、ｃのクラスである。すなわち、ｋは、ｃのクラスと異なるクラスに由来するアピアランスに関しての最適なマッチング部分である。もしも、そのようなｋが存在しない場合、ｍａｘｋＭＢ（ｆ，ｋ）の代わりにτｐａｉｒの値が用いられる。
【０１４８】
対応仮説の尤度は、その全ての特徴部分マッチの確率の積である。これは、「仮説の下でのクラス尤度比」と呼ばれる。これは、以下のように計算される。
Ｌ（ｈ）＝ΠｉＬ（ｆｉ，ｃｉ，Γ（ｈ））        （１３）
ただし、＜ｆｉ，ｃｉ＞∈ｈである。
これが、第一の実施形態で用いられるクラススコアの形である。別の実施形態では、他の方法でクラススコアを計算してもよい。
［拡張のための初期対応の選択］
【０１４９】
初期対応仮説ｈ０は、
Ｌ（ｈ０）≧τｉｎｉｔ（ｓ）        （１４）
であるときのみ、保持される。ここでｓは、ｈ０における対の数である。
【０１５０】
もし、一以上のクラス尤度比が、閾値τｉｎｉｔ（ｓ）よりも大きいならば、クラス尤度比が最も高い対応仮説が、拡張のために選択される。その仮説が処理された後は、下記のように、残った仮説の中でクラス尤度比が最も高い仮説と共に、このステップが繰り返される。この処理は、受け入れ可能である高いクラス尤度比を持つ全ての初期仮説が処理されるまで、繰り返される。最終的に、閾値τｉｎｉｔ（ｓ）よりも大きいクラス尤度比を有する仮説がなくなったときに、この処理は終了する。
［対応仮説の拡張］
【０１５１】
ｈ０を、拡張のために選択された、初期対応仮説であるとする。残っているマッチングされなかった画像特徴（これらは、ｈ０には現れない）は、これらが、対応仮説に加えられうるかどうか見るために、テストされる。作業中の対応仮説ｈは、ｈ０に初期化される。Ｃをｈのクラスであるとする。Ｓ（Ｃ）を、式（１２）で定義される特徴部分マッチの集合｛＜ｆ，ｃ＞｝であるとする。
【０１５２】
Ｓ（Ｃ）の中にあり、ｈにはまだない各対＜ｆ，ｃ＞を考える。これらの対のそれぞれは、関連付けられたＢ型のアピアランス尤度をもつ。各対をｈに加えることにより、クラス尤度比が増加するかどうか見るために、アピアランス尤度が最も大きい対から始めて、アピアランス尤度が小さい対へと、テストが進められる。すなわち、試験的仮説ｈｔがｈｔ＝［ｈ，＜ｆ，ｃ＞］として構築される。ここで、＜ｆ，ｃ＞は、まだテストされていない対の中で最大のアピアランスを持つ対である。配置変換は、Γ（ｈｔ）として、再計算される。そして、ｈｔと、式（１３）のΓ（ｈｔ）とを用いて、その仮説の下でのクラス尤度比が計算される。もしも、クラス尤度比が、先の値よりも増加したならば、対＜ｆ，ｃ＞は、ｈ＝ｈｔと設定することにより、ｈに加えられる。
【０１５３】
新たな特徴部分マッチを適応仮説処理に加える処理は、その仮説の下で、クラス尤度比を増加させる新たな特徴部分マッチが見つからなくなるまで繰り返される。
［クラスインスタンスのテスト］
【０１５４】
作業中の対応仮説に、新たな特徴部分マッチが加えることができないときには、そのクラス尤度比は、式（１３）を用いて評価される。これは、閾値τＣと比較される。
Ｌ（ｈ）≧τＣ        （１５）
この比がτＣを超えないときは、その仮説は、無効であるとされ、廃棄される。クラス尤度比が、τＣを超えるならば、クラスＣは、画像に存在すると宣言される。このようにして、第一の実施形態においては、対応仮説のうちから、そのクラススコアが受け入れ基準を満たす対応仮説を選択する。最終的な配置変換Γ（ｈ）は、三次元シーン中の、クラスインスタンスの位置と方向を方向を特定する。そのクラスと配置変換が、認識処理の出力である、認識されたクラスインスタンスの集合に加えられる。
［探索の続行］
【０１５５】
画像中には、複数のクラスインスタンスが存在しうる。したがって、処理は、続行する。もしも、最終的な対応仮説が受容されたならば、そのすべての画像特徴は、以降、検討対象から除かれる。なぜならば、それらは説明されたからである。これは、以下のステップを伴う。該画像特徴は、他のすべての対応仮説から削除される。そのように影響を受けた各対応仮説について、まだ、少なくともτｍｉｎＨの特徴部分マッチを有するか否かチェックされる。もしも、有さない場合、その対応仮説は削除される。対応仮説が、少なくともτｍｉｎＨの対を有するときは、残された対についての新たな配置変換が計算される。そして新たな配置変換の下で、クラス尤度比が再計算される。
【０１５６】
探索は続行される。残っている初期対応仮説のうち、クラス尤度比の最も高い仮説が選択される。前述のように、それは拡張され、クラスインスタンスとして認識されうる。この処理は、閾値τｉｎｉｔ（ｓ）を超えるクラス尤度を有する全ての初期対応仮説が検討されるまで、続行する。この結果、認識されたクラスインスタンスの集合ができる。
【０１５７】
第一の実施形態においては、認識に際して幾つかの閾値を用いる。これは、三次元クラスデータベースが構築されるときに計算される。しかし、便宜上、この構築についてここで述べる。なぜならこの構築においては、認識フェーズにおいて、定義された幾つかの式が用いられるからである。
【０１５８】
多くの用途においては、使用される前にクラスデータを検証するほうが望ましい。この検証を行う一つの方法は、既知の姿勢の既知のオブジェクトを含む三次元シーンのテストセットを採用することである。これは、「基礎真実」と呼ばれる。シーン中の画像が取得され、認識が実行され、そして結果が、基礎真実と比較される。この比較により、的確に動作しているか検証され、実験的に認識率が出される。第一の実施形態においては、この検証処理は、修正され、認識に用いられる閾値を計算するために拡張される。
【０１５９】
基礎真実を生成し、取得するために、一般的に、「除外法」が用いられる。これは、前述の非特許文献９のような教科書に記述されている。第一の実施形態においては、この方法のバリエーションが用いられる。クラスデータベースの、幾つかの特別なバージョンが構築される。各バージョンにおいて、各オブジェクトのビューのごく一部がランダムに選択されて、データベース構築から留保される。しかしながら、これらのビューにおいて検出された特徴は、まだ近傍のビューとマッチングされている。近傍のビューにおいて、マッチングする特徴が、どのクラス部分に関与するのか、を観察することにより、留保された各ビューの中の各オブジェクト要素を、非常に正確に、その正しいクラス部分ラベルと関連付けすることが可能となる。第一の実施形態において、これが実行され、その結果、留保されたオブジェクトの集合ができる。その各要素は、クラスとクラス部分で、ラベル付けされている。
【０１６０】
これに加えて、認識されるべきクラスに属するオブジェクトが存在しない他のシーンも処理され、特徴が検出される。これらの特徴は、背景をモデル化するために用いられ、「背景特徴」と呼ばれる。
【０１６１】
第一の実施形態においては、以下のステップに従うことによって、クラスインスタンスを含む、シミュレーションされたシーンから、特徴のセットＦを構築する。
（１）一以上のクラスがデータベースから選択される。ｎをデータベース中のクラスの数であるとする。各クラスｉについて、数ｍｉがジオメトリの分布から、パラメータｐ＝１／ｎによって、サンプリングされる。
（２）各クラスｉについて、クラスからｍｉ個のオブジェクトインスタンスがランダムかつ均一に選択される。
（３）各オブジェクトインスタンスについて、留保されたビューが、ランダムかつ均一に選択される。
（４）各ビューについて、そのビューにおいて、検出された特徴が、確率ｑで、それぞれを独立に選択することにより、サンプリングされる。ここでｑは、特徴検出器の繰り返し可能性と整合する検出確率である。
（５）背景特徴の数Ｂが、パラメータＮとｐの二項分布からサンプリングされる。ここで、Ｎは、使用可能な背景特徴の総数である。そしてｐの値は、平均Ｎ＊ｐが典型的なシーンの画像において検出される背景特徴の数の平均と等しくなるように、選択される。
（６）最後に、Ｂ個の特徴が、均一に、かつ、全ての使用可能な背景特徴の集合から非復元的に、サンプリングされる。
このプロセスの結果、合成された特徴の集合ができる。この集合は、一以上のオブジェクトインスタンスのビューと、背景特徴の集合を含む。
【０１６２】
第一の実施形態においては、この処理を繰り返し、基礎真実が既知である合成された特徴の集合の大きい集合を作る。その結果得られるラベル付けされたデータの集合を、Ｇで表すものとする。
【０１６３】
計算すべき閾値は、認識において様々なテストで用いられる。一般的に、そのテストによって生じうる二種類の誤りがある。
（１）偽であるべきなのに、テスト結果は真となる（偽陽性）。
（２）真であるべきなのに、テスト結果は偽となる（偽陰性）。
τを、選択されるべき閾値であるとする。Ｆが、特徴の集合を表すものとする。テストが、偽陽性を与えるときは、ＦＰ（Ｆ，τ）は、１であると定義する。そして、その他の場合は、０であると定義する。ＦＮ（Ｆ，τ）は、テストが、偽陰性を与えるとき、１であると定義し、その他の場合は０であると定義する。α∈［０，１］は、犯しうる誤りである偽陽性と偽陰性との間のトレードオフをパラメータ化する。これにより、特徴の集合Ｆについての閾値τのペナルティまたはコストは、下記の式で表される。
ＣＦ（Ｆ，τ，α）＝αＦＰ（Ｆ，τ）＋（１−α）ＦＮ（Ｆ，τ）
これは、重み付けされた誤りのコストを測定する。したがって、値が小さい方が望ましい。αの値は、特定のテストと用途に基づく。それは、設計者によって選択される。特定の選択肢が以下に与えられるが、他のαの値も、正確性、メモリ、動作時間などについての特定の条件を達成するために用いられてよい。
【０１６４】
ｎ個の特徴の集合の集合、Ｇ＝｛Ｆ１，Ｆ２．．．Ｆｎ｝を所与とする。平均のコストは、
ＣＧ（Ｇ，τ，α）＝ΣｉＣＦ（Ｆｉ，τ，α）／ｎ
である。最適なτの値は、τ＊である。それはコストを最小化する。
τ＊＝argminτＣＧ（Ｇ，τ，α）＝argminτΣｉＣＦ（Ｆｉ，τ，α）／ｎ      （１６）
一般的に、τは、最適化されるべき、すべての閾値のベクトルである。本発明の様々な実施形態において、様々な方法で、式（１６）が計算され、また近似されてよい。
【０１６５】
第一の実施形態においては、順次的なステップで、閾値を計算することにより、計算上の近似をおこなう。それぞれのステップにおいて、考慮中であり、特定のテスト中である特定のτについて、式（１６）を評価することにより、一の閾値が、最適化される。閾値は、τｐａｉｒ、τｉｎｉｔ（ｓ）、τＣ、τｍｉｎＨの順に最適化される。最後に、下記のように、τｍａｘＨが選択される。
【０１６６】
閾値τｐａｉｒは、画像特徴とクラス部分のマッチを、いつ保持するか、決定する。上述のように、学習用の集合においては、正しいマッチは既知である。第一の実施形態においては、α＝０．０５で式（１６）を計算することにより、最適なτｐａｉｒの値が計算される。この場合、ＦＰと、ＦＮは、画像特徴のクラス部分へのマッチングを、式（１１）を用いて、τｐａｉｒの異なる値について評価する。この最適化により、τｐａｉｒの値が決定される。そして、この値は固定され、これに引き続く閾値最適化のステップと、認識ステップの両方のステップにおいて、用いられる。
【０１６７】
以下のように、τｉｎｉｔ（ｓ）の最適値を選択するために、同様のプロセスが実行される。τｍｉｎＨの値は、一時的に、３であるとする。τｍａｘＨの値は、一時的に閾値最適化に使用可能な時間によって制限される大きい値であるとする。各特徴の集合について、アピアランス尤度が、τｐａｉｒを超える対が、初期仮説に形作られ、配置が計算され、結合アピアランスと、ジオメトリ尤度比が計算される。初期仮説ベクトルのうち、どれが、正しい特徴とクラス部分のマッチに対応するか、は既知である。第一の実施形態においては、α＝０．０５で式（１６）を評価することにより、最適なτｉｎｉｔ（ｓ）の値が計算される。この場合、ＦＰと、ＦＮは式（１４）を用いて評価される。初期対応仮説の、それぞれの長さｓについて、別々に最適化がなされる。この最適化により、それぞれのｓの値について、τｉｎｉｔ（ｓ）の値が決定される。そして、この値は固定され、これに引き続く閾値最適化と、認識の両方のステップにおいて用いられる。
【０１６８】
最終対応仮説を受け入れるか、棄却するかに用いられる閾値τＣの最適値を選択するために、同様のプロセスが実行される。このステップにおいて、認識アルゴリズムは、画像中のクラスインスタンスの存在についての決定がなされるべき点に達する。第一の実施形態においては、α＝０．５で式（１６）を計算することにより、最適なτＣの値が計算される。この場合、ＦＰと、ＦＮは式（１５）を用いて認識の正確さを評価する。この最適化により、τＣの値が決定される。
【０１６９】
初期対応仮説の最小の長さであるτｍｉｎＨ（ｓ）の最適値を選択するために、同様のプロセスが実行される。このステップにおいて、認識アルゴリズムは、画像中のクラスインスタンスの存在についての決定がなされるべき点に達する。第一の実施形態においては、α＝０．５で式（１６）を計算することにより、最適なτｍｉｎＨの値が計算される。この場合、ＦＰと、ＦＮは式（１５）を用いる。この最適化により、τｍｉｎＨの値が決定される。
【０１７０】
最後のステップは、τｍａｘＨを決定することである。τｍａｘＨは、他の閾値を用いて、許容できる認識時間内で結果の出たもののうち、最も大きい値となるように選択される。
【０１７１】
本発明はまた、オブジェクト認識にも、用いることができる。実際に、オブジェクト認識と、クラス認識の混合にも利用することができる。しかしながら、説明の目的のため、混合した場合もまた実行可能であることを明白に理解した上で、便宜上、オブジェクト認識について述べる。
【０１７２】
本発明においては、オブジェクト認識は、非常にクラス認識に類似する。したがって、いずれかの主要な問題のみについて議論する方が都合がよい。
［第二の実施形態におけるデータベース構築］
【０１７３】
オブジェクト認識においては、三次元データベースモデルは、一の特殊なオブジェクのものである。多くのオブジェクトが、複数のジオメトリの状態に変形可能であるか、複数のアピアランス状態を有するか、または、複数の付属的な状態を有する。例えば、特定の人物の顔は、その人物の表情が変わるにつれて変形し、ヒゲを伸ばし、または剃るとアピアランスが変化する。アピアランスはまた、眼鏡の有無に応じても、さらに変化する。
【０１７４】
三次元データベースモデルの構築にあたって、第一のステップは、サンプル・ビューを取得することである。複数の状態を有するオブジェクトについては、各主要な状態について、サンプルオブジェクトを生成すると便利である。各サンプルは、同一の認識されるべきオブジェクトであるが、変形またはアピアランスの異なる状態にある。これらは、「サンプル状態」と呼ばれる。各サンプル状態は、オブジェクトのバリエーションであり、その多様性をモデル化するために用いられる。
【０１７５】
この種のオブジェクトは、ビジュアルクラスの統計的な性質を有し、適切な三次元データベースモデルは、三次元クラスモデルと同じである。従って、「オブジェクトクラスモデル」という語句は、オブジェクトの三次元データベースモデルを称し、「オブジェクトクラス部分」という語句は、その部分を称するのに用いられる。各オブジェクトクラスモデルは、関連するオブジェクトの多様性を表す。特に、オブジェクトクラス部分は、局所的な多様性を表す。多様性を包含するオブジェクトの三次元データベースモデルを構築し、また使用する機能は、本発明の利点の一つである。
【０１７６】
変形がなく、またアピアランスの変化がないオブジェクトは、別の実施形態に記述されるように、バリエーションが最小限である特別な状況である。
【０１７７】
オブジェクトクラスモデルを計算するに当たって、様々な調整がなされる。ある一の調整は、共分散の計算についてなされる。位置クラスタが計算されるとき、クラスタ内には、三次元位置が一個しか、在しないかもしれない。平均のジオメトリと、平均のアピアランスは、それぞれ、その一の値から計算される。共分散は、ビューを取得するのに用いられたセンサの特性から計算される。
【０１７８】
したがって、一般的に、オブジェクトクラスモデルはオブジェクトクラス部分の集まりを備える。そして、各部分は、部分ジオメトリと部分アピアランスを備える。各部分アピアランスは、二つのアピアランス記述子を備える。そのうちの一は、姿勢不変（Ａ型）であり、他方は、二次元情報のみから計算される（Ｂ型）。
［第二の実施形態における認識］
【０１７９】
オブジェクト認識においては、クラス認識と同じ手順が用いられる。手短にいうと、それは以下のように動作する。各Ｂ型アピアランス記述子は、二次元濃淡度情報から計算される。これらは、二次元画像特徴と、三次元オブジェクトクラス部分との可能性のある対応の位置を特定するために用いられる。これらより、初期対応の集合が構築される。対応仮説は、オブジェクトクラスと、画像の一部の間の配置変換を計算するのに用いられる。配置変換を用いて、Ａ型の姿勢不変特徴記述子を用いて、アピアランスが比較される。Ａ型の姿勢不変特徴記述子は、より正確な評価を提供する。ジオメトリとアピアランスは、対応仮説の下でのクラス尤度を評価するために、共に用いられる。
【０１８０】
クラス尤度が閾値を超えるならば、そのオブジェクトは認識される。このようにして、第二の実施形態においては、対応仮説のうち、そのクラススコアが受け入れ基準を満たす対応仮説が選択される。別の実施形態では、そのクラス尤度に代えて他の手段が用いられてもよい。一般的には、クラススコアがこの目的のために用いられる。
【０１８１】
本発明は、オブジェクト認識に複数の革新をもたらす。その一は、三次元データベースモデルの形式である。それは、オブジェクトのバリエーション提供する。他の点は、二つのアピアランス記述子をもちいることである。その一は、二次元画像データのみから計算され、他方は姿勢不変である。他の様々な革新が、これに付随する。
［別の実施形態と実装］
【０１８２】
以上においては、ある特定の実施形態と、実装を参照して、発明について記述されてきた。以下において、様々な別の実施形態と実装が説明される。以下の議論は、説明を意図するものであり、制限するものでないことは、理解されるであろう。
【０１８３】
本発明には様々な別の実施形態が存在し、特に、様々な手続き的ステップが存在する。そのうちのどれが、与えられた状況において好適であるかは、用途を含むいくつかの要因による。様々な用途が、適切なビジュアルクラスについて異なる性質、認識の正確さについての異なる基準、異なる計算スピードについての要請、コンピュータ機器についての異なる価格面の制限を有する。これら、そして他の点について検討することにより、他の方法内での選択が決定づけられる。
【０１８４】
上述のように、第一の実施形態においては、ステレオシステムを用いて、距離および同じ場所の画像の濃淡度情報を取得する。別の実施形態においては、距離および同じ場所の画像の濃淡度情報は、様々な方法により、取得されてよい。
【０１８５】
他のいくつかの実施形態においては、異なるステレオ取得システムが用いられてよい。構造光システムが用いられてもよい。また別の実施形態においては、一以上のカメラを移動させることにより、ステレオ計算のための複数の画像が得られる。この方法は、カメラの移動距離に対する有効なベースラインを増加させる点で、実用的に有利である。より大きなオブジェクトについては、この方法が最も有効にオブジェクトモデルを取得する方法である。
【０１８６】
また別の実施形態においては、異なるセンサにより、距離および濃淡度が取得され、位置合わせがなされて、距離および同じ場所の画像の濃淡度情報が提供されてよい。例えば、距離は、レーザ距離計によって、画像濃淡度はカメラによって取得されてもよい。
【０１８７】
画像は、赤外，可視領域、紫外など、電磁波スペクトルの任意の部分により作られてよい。また、超音波、ＭＲＩ、ＰＥＴなど、他の撮像手段によって取得されてもよい。撮像手段が組み合わせて用いられてもよい。
［サンプルオブジェクト］
【０１８８】
第一の実施形態においては、管理された状態の下で取得されたサンプルオブジェクトのビューから、クラスモデルが構築された。別の実施形態においては、より緩く管理された状態であってもよい。ビュー中には他のオブジェクトが存在してもよく、また、様々なビューにおけるサンプルオブジェクトの相対的な姿勢は既知でなくともよい。これらの場合、オブジェクトモデルを構築するためには、付加的な処理が必要となる。
【０１８９】
別の実施形態においては、より管理がなされた状態でサンプルオブジェクトが取得されてもよい。別の実施形態においては、オブジェクトの三次元アピアランスを合成するために、三次元ＣＡＤモデルと、その表面のテクスチャ・マップが用いられてもよい。それを、実行するために、コンピュータ・グラフィックの技術が採用されてもよい。合成されたビューをレンダリングするために、コンピュータ・ゲーム・ハードウェアが用いられてもよい。一部の実施形態では、合成されたオブジェクトが単独で用いられてもよい。別の実施形態では、合成されたオブジェクトと物理的に観測されたオブジェクトの組み合わせが用いられてもよい。
［変形可能なオブジェクトのクラス認識］
【０１９０】
第一の実施形態は、各クラスに属するオブジェクトが、剛体であるときの、クラス認識に最適化されていた。先に指摘したように、多くのオブジェクトが複数のジオメトリ状態に変形可能であったり、複数のアピアランス状態を有したり、複数の付属状態を有したりする。クラス認識のための別の実施形態においては、各クラスの各オブジェクトに、アピアランスの変化や、変形が伴うようなクラスモデルが構築されてもよい。このような実施形態においては、サンプルは、予想される変化を代表するように選択される。各クラスにおいて、オブジェクトの変化を許容する三次元クラスモデルを構築し、用いる機能は、本発明の特徴である。
［剛体についてのオブジェクト認識］
【０１９１】
第二の実施形態においては、オブジェクトが変形可能であるときの、オブジェクト認識が提供される。オブジェクトが剛体である特別な場合のオブジェクト認識のためには、別の実施形態が構築されてもよい。この場合には、オブジェクトクラスモデルが計算されるにあたって、様々な調整がなされる。ある調整は、共分散の計算においてなされる。オブジェクトが剛体であるならば、複数の観測は、同じアピアランスと位置情報を基礎とする、独立した観測を提供するものと仮定される。従って位置クラスタは、オブジェクト要素の観測されたインスタンスすべての平均値からなる。ΛＡ，ｎｏｍを、センサと関連する特性に基づくＡ型の記述子の名目上の共分散であるとする。ある特定の特徴を考える。ｎを、ある一のオブジェクトの幾つかのビューにおいて、それが観測される回数であるとする。そうすると、その特徴についての共分散ΛＡは、ΛＡ，ｎｏｍ＊（１／ｎ）に設定される。共分散ΛＢと、共分散ΛΦは、名目値ΛＡ，ｎｏｍと、ΛΦ，ｎｏｍから、センサと、関連する特性に基づいて、同様に計算できる。
［関心点演算子］
【０１９２】
第一の実施形態においては、上述のように、一の関心点演算子が用いられた。別の実施形態においては、別の関心点演算子が用いられてもよい。幾つかの可能な関心点演算子は、上記の［関心点の検出］の節で述べた。これらに加えて、他の関心点演算子が有利に用いられてもよい。例えば、ある一部の用途においては、関心点演算子を、特にその用途において重要なクラスを検出するために設計する法が望ましい場合がある。このような、カスタマイズされた関心点演算子は、機械学習技法や手動指示、または、これらの組み合わせにより設計されてもよい。
【０１９３】
別の実施形態では、複数の関心点記述子が用いられてよく、関心点は、その関心点演算子のうちのいずれかによって認識されれば、受け入れられてよい。別の実施形態では、複数の関心点記述子が用いられてよく、関心点は、複数の関心点演算子が、それぞれ、関心点を近傍において認識したときに受け入れられてよい。
［正準アピアランス］
【０１９４】
第一の実施形態において、サンプルオブジェクトのモデルが構築されるとき、三次元関心点の近傍の局所画像は、正面法線であるように、変換される。従って、サンプルオブジェクトの各要素において、要素アピアランスは、その要素が局所的な面の法線に沿ってビューされたかのようなアピアランスとなる。これは、「正準アピアランス」の一形態である。別の実施形態においては、他の標準的なビュー方向に沿ってビューされたかの如く見えるように、局所近傍が変換されてもよい。その結果、サンプルオブジェクト要素の正準アピアランスの他の形態となる。いずれの場合にも、サンプルオブジェクト要素の正準アピアランスは、クラス部分の正準アピアランスとなる。
［アピアランス記述子の次元の縮退］
【０１９５】
局所領域のアピアランスは、高次元の量である。別の実施形態においては、これを、より扱いやすい表現に縮減させるために、次元縮退が実施されうる。次元縮退については、広範な文献があり、様々な用途において、これらの文献から、様々な方法が採用されうる。
［アピアランス記述子］
【０１９６】
第一の実施形態においては、局所アピアランスは、上述のように表現された。別の実施形態においては、Ａ型とＢ型のアピアランス記述子のそれぞれについて、局所アピアランスの他の表現が用いられてよい。［関心点の表記］の節では、いくつかの可能な表現について、記述される。これに加えて、他のアピアランス記述子が、有利に用いられてもよい。
【０１９７】
Ｂ型のアピアランスは、距離データを用いることなく、二次元画像情報から計算される。
【０１９８】
Ａ型のアピアランス記述子は、距離データを用いて計算される。従って、姿勢不変に形成されうる。様々な形式の姿勢不変アピアランス記述子が用いられる。そのための手法のあるグループにおいては、適切なアピアランスパッチを正準形式に設定し、そして、アピアランス記述子を構築するための標準的な手法の一つを、その正準形式のパッチに適用する。
［別のＡ型アピアランス記述子の投影］
【０１９９】
第一の実施形態においては、Ａ型アピアランス記述子は、正準形式にリサンプリングされた局所アピアランスである。先に指摘したように、別の実施形態においては、別のＡ型アピアランス記述子が用いられてよい。これは、アピアランスの他の正準形式へのリサンプリングを含み、または、線形または非線形関数を用いた正準形式の投影を含み、または両方の組み合わせを含む。
【０２００】
別のＡ型アピアランス記述子が用いられるとき、クラス部分の構造、認識過程における配置変換の下でのアピアランスの投影処理にについて様々な調整がなされる。そのための幾つかの別の手法が、以下に記述される。
【０２０１】
所与のクラス部分について考える。Ａを、その部分の、正準形式であるようにリサンプリングされた局所アピアランスであるとする。これは、第一の実施形態と同様、リサンプリング関数Ｗを用いて計算される。Ψを、局所アピアランスを他の形式にさらに投影するための計算を行う関数であるとする。例えば、Ψは、入力データの線形次元縮退であってもよく、または、非線形強調のある形でもよい。ｑ＊を、この新たなアピアランスを表示するものとする。すなわち、ｑ＊＝Ψ（Ｗ（ｐ，γ，φ））である。Ｚ（ｐ，γ，φ）＝Ψ（Ｗ（ｐ，γ，φ））と定義する。
【０２０２】
クラス部分は、Ａ＊＝（μＡ＊，ΛＡ＊）を格納する。ここで、（μＡ＊，ΛＡ＊）は、Ｚをデータベース構築中に検出した画像パッチに適用した結果の統計的モデルである。それはまた、認識中に画像パッチをリサンプリングするのに用いる三次元点の格子を格納する。Ａ型アピアランス記述子は、Ａ＊である。
【０２０３】
認識においては、これらのＡ型記述子を用いる。ｆ＝（ｕ，ｐ，ｂ）を画像特徴とする。ただしｐは、画像パッチである。リサンプリングされたパッチの分布Ｑ＊＝（μＱ＊，ＡＱ＊）は、以下のように計算される。平均は、μＱ＊＝Ｚ（p，μΓ，μΦ）で与えられる。関数Ｚは微分可能であると仮定すると、第一の実施形態で述べたのと同様の手法を用いてΛＱ＊が算出される。［配置変換の下でのアピアランスの投影］の節で述べた方法が、ＷをＺとして、採用される。Ｋ＊ΦをφについてμΦで評価されたＺのヤコビアンであるとし、Ｋ＊ΓをγについてμΓで評価されたのＺのヤコビアンであるとする。そうすると、以下の式となる。
ΛＱ＊＝Ｋ＊ΦΛΦＫ＊ΦＴ＋Ｋ＊ΓΛΓＫ＊ΓＴ
アピアランス尤度を計算するために、分布Ｑ＊が分布Ａ＊と比較される。すなわち、式（１０）において、記述子Ａ＊とＱ＊が、ＡとＱの代わりに用いられる。
【０２０４】
また別の実施形態においては、Ψ（Ｗ（ｐ，γ，φ））に連鎖法則を適用し、先に計算されたＷのヤコビアンＫΦとＫΓを使用可能とすることで、ヤコビアンＫ＊ΦとＫ＊Γが有利に計算される。Ψが線形関数であるならば、それは行列であると見なすことができる。この場合、共分散ΛＱ＊は、三つの行列の積として
ΛＱ＊＝ΨΛＱΨＴ
と書くことができる。ただしΛＱは、（９）と同様に定義できる。
【０２０５】
別の実施形態においては、リサンプリング演算子Ｗを導入することなく、Ｚを直接的に画像濃淡度上に定義する方が有利な場合もある。
【０２０６】
また別の実施形態においては、正準アピアランス記述子Ａと一以上の投影Ａ＊と組み合わせて、結合アピアランス記述子が作られてもよい。
【０２０７】
別の実施形態においては、部分アピアランスと画像濃淡度の両方を投影し、第三の表現としてもよい。そのような別の手段の一つでは、第一の実施形態に記述されたＡ型記述子を格納するが、Ａと画像パッチの両方を、共通の表現に投影する。上記で用いられたのと同じ、一般的な手法が採用される。平均は、平均を投影することによって取得され、共分散行列は、適切なヤコビアンを用いて計算される。これらにより、式（１）を用いて尤度が計算される。
【０２０８】
一部の実施形態においては、サンプリングとの手法を採用し、標準的な形においては微分不可能である画像を表現することが有用かもしれない。この一例としては、ヒストグラムを利用したスピン画像表現がある。これらの場合においてはたいてい、表現を少し修正して微分可能であるようにすることができる。スピン画像の場合には、これを達成するために微分可能なカーネルを用いることで、カーネルで重みをつけたヒストグラムが用いられてもよい。
【０２０９】
本発明の有利な点の一つは、多様なＡ型アピアランス記述子の配置変換の下で、投影を計算し、クラス部分が与えられたとき、これらの様々なＡ型記述子を用いて画像特徴のアピアランス尤度を計算する機能である。
［アフィン不変］
【０２１０】
第一の実施形態において、Ｂ型特徴記述子はスピン画像手法を用いて計算された。別の実施形態においては、アフィン不変とするために、検出された画像の周辺領域について、付加的な計算を実行することが有用かもしれない。このようなアフィン不変領域を作る方法の一は、非特許文献７に述べられている。検出された画像領域は、検出された関心点の画像濃淡度の一階または二階微分の固有値を用いて正規化される。正規化は、上記の固有値が等しくなるように、画像領域をリサンプリングすることにより、実行される。その結果、画像領域は、近似的に三次元回転とスケーリングについて不変とされてもよい。その結果得られた、正規化された画像領域は、Ｂ型記述子として用いられてもよい。
【０２１１】
これに代えて、回転に対する不変性を増幅するために、スピン画像手法が、アフィン不変領域に適用されてもよい。このアプローチは、視点の変化の下で、領域の主要な勾配方向が安定していないような用途において、好都合であるかもしれない。
【０２１２】
また別の実施形態においては、非特許文献１９に述べられているように、上述の正規化処理が、その特徴についてのアフィン姿勢を計算するために用いられてもよい、という事実を活用することが好都合であるかもしれない。この場合、アフィン特徴姿勢の一貫性は、アフィンジオメトリ尤度関数に組み込まれてもよい。アフィンジオメトリ尤度関数は、どの対応仮説を拡張すべきかを選択する別の手段を提供してもよい。さらに、そのような実施形態は、オブジェクトクラス部分、またはクラス部分の三次元姿勢を、アフィン特徴姿勢に関係付けてもよい。この場合、初期の近似モデル配置は、わずか二つの特徴マッチから、計算されてもよく、したがって、初期対応仮説の長さの最小値を２に縮退させる。この初期配置はまた、第一の実施形態で述べた、三次元姿勢配置方法を初期化するために用いられてもよい。
［正準ジオメトリ］
【０２１３】
第一の実施形態においては、サンプルオブジェクトは、上述のように、正準ジオメトリを有するようにスケーリングされた。別の実施形態においては、正準ジオメトリは、他の方法で取得されてもよい。例えば、全体のスケールと、オブジェクトのセントロイドは、サンプルオブジェクト要素の位置についての，凸包を構築することにより、計算することができる。
【０２１４】
これに代えて、各座標軸は、独立にスケーリングすることもできる。または、データのアフィン変換を、実行することができる。使用されるであろう正準ジオメトリを作る可能な他の演算がたくさんある。
【０２１５】
また別の実施形態においては、クラスモデルを構築する際に、例えば、異なるクラスモデル軸に沿ったオブジェクトの大きさの比のような、ジオメトリ正規化値をモデル化してもよい。これらの値の分布は、学習中に計算することができる。そして、ジオメトリ尤度は、大局的ジオメトリによる項を含むように、調整されてもよい。これにより、この実施形態においては、アスペクト比や、他の同様なジオメトリ構成概念に基づいて、クラスをよりよく区別することができる。
［対応要素の識別］
【０２１６】
第一の実施形態においては、サンプルオブジェクトの集合中の対応要素は、正準ジオメトリ位置上でのクラスタリングにより、認識された。別の実施形態においては、付加的な情報が考慮されてもよく、異なる認識手法が用いられてもよい。
【０２１７】
例えば、対応する要素を認識する際には、要素アピアランスが考慮されてもよい。これは、対応要素の位置が多様であるときに好都合であるかもしれない。位置の多様性は、オブジェクトの変形によることもあり、また、クラス内での位置の多様性によるかもしれず、またその両方によるかもしれない。
【０２１８】
さらに、対応要素を識別する際には、位置と方向の両方が考慮されてもよい。方向が位置よりも、より安定であるときには、方向を用いることが、有益である。
【０２１９】
別の実施形態においては、他のアルゴリズム手法により、対応要素が認識されてもよい。例えば、正準オブジェクトモデルの、三次元位置を認識するために、ＥＭアルゴリズムが用いられてもよい。
【０２２０】
別の実施形態においては、補助的に、手動で介入がなされてもよい。例えば、対応要素の認識は、人間のオペレータによって、構築され、監督され、また検証されることも可能である。このアプローチの実施形態の一つにおいては、第一の実施形態と同様に、関心点が検出され、要素が計算され、そして、人間のオペレータが、適切なグラフィカル・ユーザ・インタフェースを用いて、対応要素を認識する。その用途においては、明白に検証された正確性を持って、クラスモデルを構築されることが要請されるようなときに、このような代替手段が好都合であるかもしれない。
［ビューの配置］
【０２２１】
第一の実施形態においては、サンプルオブジェクトについて、ビューが取得されるとき、各ビューには、手動で取得された、ビュー姿勢が関連付けされていた。このビュー姿勢を用いて、オブジェクト要素は、オブジェクトモデルを形成するために一般座標系に変換され、オブジェクトモデルは、正準ジオメトリ形式に設定される。別の実施形態においては、正準ジオメトリを取得するために、付加的な配置ステップを実行してもよい。例えば、クラス内に著しく異なるオブジェクトがあるとき、すべてのサンプルオブジェクトにわたって一貫したビュー姿勢を取得することは難しいかもしれない。よって、配置ステップが望まれ、または要求される。
【０２２２】
補助的な配置ステップは、次のように実行されてもよい。三次元位置のクラスタリングステップの後、クラスタの集合が存在する。そのそれぞれには、クラスタ中心がある。これらのクラスタ中心を用いて、各ビューが別個に処理され、適切なクラスタ中心と、最もよく対応するように、そのビューについて姿勢の調整が計算される。ビューの要素が、位置ｘ１，．．．，ｘｎにあるとする。位置ｘｉは、中心ｃｉのクラスタに属すると仮定する。位置の誤差ｅｉを、ｅｉ＝ｘｉ−ｃｉであると仮定する（もし、ある位置がどのクラスタにも対応しないときには、この処理においては、それは無視される）。一部のビューについては、要素のうちのＬ個がクラスタに属すると仮定する。ＪΦｉを、ciにおいて評価された、姿勢の変化に対する位置の偏導関数のヤコビアン行列であるとする。一次のオーダでは、ＪΦｉΔΦ＝ｅｉである。このような式がＬ個ある。ＪΦをＬ個の行列ＪΦｉをまとめて成るものとし、ｅをＬ個のベクトルｅｉをまとめて成るものとする。各ｅｉが、３行に寄与する。その結果、以下の３Ｌ行の方程式の決定系となる。
ＪΦΔΦ＝ｅ
これは、ΔΦについて最小二乗センスで、以下の線形システムを解くことにより、解くことが可能かもしれない。
（ＪΦＴＪΦ）ΔΦ＝ＪΦＴｅ
この方法で計算された姿勢の変化Δφは、二乗誤差の和を最小にする。それぞれの要素について、各ｘｉに姿勢の変化を適用することにより、新たな三次元位置が取得され、その結果、新たな位置ｙｉとなる。部分ジオメトリを構築するにあたって、新たな位置ｙｉが用いられる。これらは、可能である限りにおいて、各ビューの正しい姿勢に調整されているという意味において、ｘｉよりも好適である。
【０２２３】
別の実施形態においては、要素位置とクラスタ中心の誤差を最小化する他の手法を用いてもよい。例えば、Ｌ１ノルムが用いられてもよい。これに代えて、他の堅固な推定手法を用いてもよい。
【０２２４】
また別の実施形態においては、二のビューで観測された点の位置の差異の関数である誤差を最適化することによって、全てのビューを同時に調整することを選択してもよい。すなわち、ｘｊ，ｋは、ｋ番目のビューにおいて、点ｘｊの位置を表すとする。ｉ番目のビューにおいてもまた、ｘｊtが可視であるならば、誤差
ｅｉ，ｊ，ｋ＝Ｔ（γｉ，ｘｊ，ｉ）−Ｔ（γｋ，ｘｊ，ｋ）
は、ここで、上述の方法を用いて、二のうちの一は固定されているという条件でγｉとγｋについて最適化することができる。より一般的には、一のビューを固定しながら、ビューの全てのペアとビューのペア間で共有される全ての点について、ヤコビアンをまとめることにより、上記の手法を採用して全てのビューのパラメータを同時に最適化することができる。
［クラスデータベース構築のためのサンプルオブジェクトの結合］
【０２２５】
第一の実施形態においては、クラスモデルのデータベースは、サンプルオブジェクトの要素の位置をクラスタリングすることにより、構築された。別の実施形態においては、他の手法が用いられてもよい。例えば、クラスモデルは、インクリメント的（ｉｎｃｒｉｍｅｎｔａｒｙ）に構築されてもよい。クラスモデルは、例えば、正準形式のオブジェクトモデルの見本に、初期化される。各、残った正準オブジェクトモデルが、正準オブジェクト要素をマッチングするクラス部分に関連づけることにより、クラスモデルに加えられる。概略では、これは、認識処理に似ているが、幾つかの点で違いがある。（１）一のクラスのみが考慮される。（２）マッチングは、三次元要素と、姿勢についての初期推定が好適な三次元クラス部分と、に関する。（３）はじめは、部分共分散を計算するための経験的基礎がないため、推定値が用いられる。
［セグメント・クラス］
【０２２６】
第一の実施形態においては、上述のように、オブジェクトモデルが構築された。オブジェクトが、結合部によってつながれている複数の剛体セグメントから構成される場合、より典型的なモデルを構築することが可能である。別の実施形態においては、以下のようにして、代表するモデルを構築することが可能である。各剛体セグメントは、別個のものと見なされ、別個のサンプルオブジェクトとして、モデル化される。各セグメントについて、クラスが構築され、セグメントクラスとなる。認識においては、各セグメントが画像中で別個に識別され、シーン中の各セグメントクラスのインスタンスの位置と方向を特定する配置変換が計算される。
［構造のある三次元クラスモデル］
【０２２７】
第一の実施形態においては、クラスは、階層的な構造のない、単純な部分の集合から構成された。別の実施形態においては、クラスは、ジオメトリ的な構造を有してもよい。そうすると、クラスは、ユニット間でジオメトリ関係を有するユニットから構成されることになる。ジオメトリ関係は剛体的であってもよく、または、結合部として表現されてもよい。結合部の型は、プリズム的、単一の軸の周りの回転、複数の軸の周りの回転を含んでもよい。
【０２２８】
別の実施形態においては、ユニットを共通とするクラスモデルが構築されてもよい。これにより、データベース構築を迅速化することができる。なぜならば、以前に遭遇したユニットを、また新たなクラスを構築する際に、再使用することができるかもしれないからである。これにより、認識もまた、迅速化される。なぜならば、共通のユニットは、データベースに中に、複数回ではなく、一回のみ表現されるからである。
【０２２９】
第一の実施形態においてはデータベースは、一階層のクラスの集合からなる。別の実施形態においては、クラスがサブクラスを含む構造であってもよい。例えば、ヒゲのクラスは、黒ヒゲや、灰色ヒゲや、白ヒゲなどのサブクラスを含んでもよい。そのような実施形態においては、認識処理は、最も一般的なクラスから始められ、最も特殊なクラスへと、進められる。
［クラスモデルにおける部分アピアランス］
【０２３０】
上述のように第一の実施形態においては、部分アピアランスには二つの構成要素があった。別の実施形態においては、部分アピアランスは、これよりも少ない構成要素、または、付加的な構成要素、またはこれらに代わる構成要素を有してもよい。Ａ型の記述子は除かれてもよい。正準アピアランスから計算された他のアピアランス記述子が、Ａ型の記述子として用いられてもよい。このような複数の正準アピアランスから計算された記述子が用いられてもよい。複数のＢ型の記述子が用いられてもよい。
［部分ジオメトリのないクラス部分］
【０２３１】
幾つかの別の実施形態においては、ジオメトリ記述子はなくてもよい。このような場合、認識は、アピアランスに基づく。この場合についても、データベース構築において三次元ジオメトリが使用可能であるほうが便利である。これにより、各サンプルオブジェクト要素のアピアランスが正準形式に設定されることが可能となる。したがって、各クラス部分のアピアランスは、正準形式で計算される。
［アピアランス確率の計算］
【０２３２】
配置されたクラス部分アピアランスの平均と分散は、以下のように、式（８）と（９）で与えられた。
μＱ＝Ｗ（ｐ，μΓ，μΦ）
ΛＱ＝ＫΦΛΦＫΦＴ＋ＫΓΛΓＫΓＴ
第一の実施形態においては、パッチの尤度は、以下の式を評価することにより、計算された。
Ｐ（ｐ｜Ａ，Ｑ）＝Ｇ（μＡ−μＱ；０，ΛＡ＋ΛＱ）
この計算において、行列ΛＡ＋ΛＱは、反転されなければならない。一般的に、この行列は大きな次元を有する。したがって、ガウス分布の計算は、計算として集約的である。
【０２３３】
別の実施形態においては、次の別な手法が用いられてよい。そこでは、確率変数ｓを、以下の式で定義する。
ｓ＝（ＫΦＴＫΦ）−１ＫΦＴ（ａ−ｑ）
ここで、ＫΦは、姿勢φについての、Ｗのヤコビアンである。変数ｓは、以下の式で与えられる平均μＳのガウス分布である。
μＳ＝（ＫΦＴＫΦ）−１ＫΦＴ（μＡ−μＱ）
平均μＳは、長さ６のベクトルである。これは最小二乗法的な意味において、μＡとμＱの間のアピアランスの違いについて、最もよく説明できる姿勢の変化であると見なすことができる。共分散ΛＳは、以下の式で表現できる。
ΛＳ＝（ＫΦＴＫΦ）−１ＫΦＴ（ΛＡ＋ΛＱ）ＫΦ（ＫΦＴＫΦ）−Ｔ
ΛＳを計算するためには、行列の反転が必要であるが、ただし、小さい６×６行列についてのみである。パッチｐの尤度は、以下の式で近似される。
Ｐ（ｐ｜Ａ，Ｑ）＝Ｇ（μｓ；０，ΛＳ）
ΛＳの次元は、６×６であるので、このガウス分布を評価するにあたって、効率的に反転できる。
【０２３４】
別の実施形態においては、クラス部分を与えられた画像パッチの確率についての低次元評価を可能にする、他の投影が選択されてもよい。
【０２３５】
第一の実施形態においては、すべてのクラス部分が、等しく扱われた。実際には、一部のクラス部分は他にくらべて、その区別において、より特定的である。クラス部分の識別力は、様々な方法で、典型的にはアピアランスに基づいて計算することができる。例えば、データベース中の各部分アピアランスを互いに比べることで、計算できる。識別のある部分は、他のすべての部分のアピアランスと比類似な部分である。これに代えて、総合的に選択的である部分の集合を選ぶために、相互の情報が用いられてもよい。クラス部分の識別力の指標は、切捨てを課す為に用いられてもよい。すなわち、閾値以下の全ての部分がそのモデルから廃棄される。この代わりに、いくつかの実施形態においては、クラス部分の識別力は、重み付けファクタとして、用いられてもよい。
【０２３６】
第一の実施形態においては、サンプルオブジェクトから計算されたすべてのクラス部分が保持された。別の実施形態においては、少数のオブジェクトモデル要素によってのみ支持される部分は、廃棄されてもよい。多くの支持を有する部分のみ保持することで、有用な、クラスの一般化を提供することができる。クラス部分の数を減らすことで、認識処理も迅速化されるだろう。
［疎結合のアピアランスとジオメトリのクラスモデル］
【０２３７】
第一の実施形態においては、クラスモデルはそれぞれの部分がアピアランスとジオメトリを有する部分の集合である。別の実施形態においては、アピアランスとジオメトリが、単にゆるく結合されているクラスモデルを構築し、使用することが可能である。そのようなモデルは、局所アピアランスがクラスインスタンスにおいて、多数回現れる時に、有利に用いられるだろう。
【０２３８】
そのような、別の方法のひとつにおいては、三次元クラスモデルは、以下を備える。
１）サンプルオブジェクトの関心点の位置と関連する特徴についての、統計的な記述からなるジオメトリモデル。
２）サンプルオブジェクトの関心点におけるアピアランスの統計的記述からなるアピアランスモデル。
３）ジオメトリとアピアランスが同時に生じるモデル。
【０２３９】
クラスモデルの構築にあたって、混合ガウス分布モデルが位置について計算され、その結果、いわゆる「ジオメトリクラスタ」の集合となる。混合ガウス分布モデルがアピアランスについて計算され、その結果、いわゆる「アピアランスクラスタ」となる。共起モデルは、この二つを結合する。これは、ジオメトリクラスタとアピアランスクラスタの結合尤度の推定である。これは、クラスのサンプルオブジェクトの統計から計算することができる。総合的に、これら三つは、第一の実施形態におけるクラス部分と類似する役割を果たす。
【０２４０】
認識の間は、可能性のあるマッチが画像特徴とアピアランスクラスタの間で特定される。共起モデルは、可能性のあるジオメトリクラスタと、アピアランスクラスタとを関連付けて認識するために用いられる。このようにして認識されたジオメトリクラスタは、可能な配置変換を計算するために用いられる。配置変換は、画像特徴とジオメトリクラスタの間の付加的なマッチを特定するために、用いられる。結合尤度比は、アピアランス尤度と、ジオメトリ尤度と、共起モデルを用いて計算される。このようにして、このような別の実施形態においては、クラスジオメトリとアピアランスは、別個にモデル化されるが、認識の間に結合される。
[クラスデータベースの拡張]
【０２４１】
第一の実施形態においては、クラスデータベースは、サンプルオブジェクトの集合から、構築され、続いて、認識に用いられた。別の実施形態においては、クラスデータベースを、認識されたクラスインスタンスで拡張することが、可能である。二次元画像特徴Ｆが、クラスＣのインスタンスとして認識されたと仮定する。対応仮説は、Ｆの中の各画像特徴をＣの中のクラス部分にリンクする。配置変換と各部分の姿勢は、各画像特徴の三次元位置と、正準アピアランスを計算するために用いられてもよい。
【０２４２】
したがって、Ｆの各画像特徴は、標準統計推定手法を用いて、対応部分アピアランスを更新するために用いられてもよい。標準統計推定手法は、クラス部分アピアランスと、リサンプリングされた画像パッチの平均と共分散に適用される。
【０２４３】
部分位置は、以下の事実を用いて更新されてもよい。その事実とは、非特許文献１０の、姿勢構築方法は、クラス部分と一貫性のある最適な三次元特徴位置を計算する。この三次元位置は、計算された三次元特徴位置と、先のクラス部分位置の平均と共分散を用いて、再び、先のクラス部分位置に取り入れることができる。
【０２４４】
クラス部分アピアランスモデルをリサンプリングし、アフィン変換から三つのオリエンテーション成分を抽出し、部分オリエンテーションの統計的更新を実行した後、観測された部分アピアランスに関係する最もよくフィットする二次元アフィン変換を計算することにより、部分オリエンテーションを更新することができる。
【０２４５】
このような更新は、全ての認識されたクラスインスタンスについてなされてもよく、または特定のものについてなされてもよい。例えば、以下のような場合である。そのクラス認識が高い確信度を持っているとき、更新はデータベースに格納されている、付加的な情報を用いて、なされてもよい。その情報とは、例えば、特定の部分が観測された回数などである。パラメトリックまたは非パラメトリック統計的手法が用いられてもよい。その統計的手法は、存在する推定に新たな情報を組み込む。
【０２４６】
このようにしてクラスデータベースを更新する有用性は、用途に依存する。しかし、本質的にデータベースの流動性が許容されない場合には、この方法は望ましくない。一方、データベースが、変化する状況に適応しなければならないときは、この方法は非常に望ましい。
［二次元画像の局所正面配置］
【０２４７】
認識においては、観測結果は二次元画像として取得される。三次元シーンにおいては、面は、一般的に正面に配置されていない。したがって、二次元画像においても正面に配置されていない。第一の実施形態においては、これに対する明示的な補正はなされなかった。関心点を選択し、選択されたであろうものの近傍にある画像の各部分が正面に配置されている画像特徴を計算することが望ましい。別の実施形態においては、様々な手法を用いて、部分的に補正をし、局所領域において、画像を正面に配置することが可能である。
【０２４８】
これを実行する一つの方法は、以下のプロセスに記述される。三次元シーンの各点において、局所面の局所的スラントとティルトが存在する。対応する画像中の点のスラントとティルトが既知であるなら、局所非等方性スケーリングのため、補償されうる。実際には、スラントとティルトは、未知であり、点により異なる。別の実施形態のあるグループにおいては、画像全体Ｉ０は、Ｊ−Ｉの異なる非等方スケーリングのもとで変換され、Ｊ個の画像、Ｉ０，Ｉ１，．．．，ＩＪ−１となる。Ｊ個の画像のそれぞれが、特定のスラントとティルトを補正する。起こりうるスラントとティルトに対して一様な補償範囲を提供するべく選択された、多数のこのようなスケーリングが存在すると仮定する。そうすると、画像中の任意の点について、Ｉｋのような、画像が存在し、Ｉｋのスラントとティルトは、実際に見えるオブジェクト表面の点のスラントとティルトに非常に近い。ｋの選択は、点によって異なる。
【０２４９】
この手法による任意の実施形態において、スケーリングの数は、トレードオフに基づいて選択される。スケーリングの数が多いということは、各局所スラントとティルトが、それらのスケーリングのうちの一で、よりよく近似できるということを暗示する。しかしながら、スケーリングの数が多いということはまた、さらに多くの関心点が検出されるということをも暗示する。多くの場合において、適度な数のスケーリングが、有利に用いられるだろう。ある一の実施形態においては、非等方スケーリングが選択される。そして、三次元シーンの各オブジェクトの各観測可能な面の各点について、その点について、正面法線が２０度以内である画像が存在する。
【０２５０】
画像Ｉ０，Ｉ１，．．．，ＩＪ−１の集合の上で関心点が認識される。これらの関心点において、特徴が計算される。非等方的スケーリングによって、生成された複数の画像について考慮されているため、典型的には類似する関心点が、検出されるだろう。そして、複数の画像について、特徴が計算される。複数の画像中の特徴は、概念上、対応する特徴を構成要素とする集合にグループ分けされてもよい。各集合において、スラントとティルトが、実際のものに最も近いような特徴が、正面法線ビューに対して最も正確なアピアランス記述子を有することになる。一の画像について特徴が所与のとき、元の画像Ｉ０、そして、その局所領域の拡張において、関心点の位置に基づいて、他の画像中で、対応する特徴の集合を計算することができる。このようにして、計算された特徴の集合は、「等価特徴」と呼ばれる。
【０２５１】
この手法が用いられる別の例においては、これに続く処理において、等価性に基づく様々な処理がなされる。例えば、特徴の画像位置は元の画像Ｉ０の中の位置とされる。さらに、画像を選択することにより、大まかなティルトとスケールが提供されることに注意されたい。もしも、インスタンスとクラスの大きさが同じであるなら、回転は、関心点の局所領域から計算することができ、スケールもまた、関心点の局所領域から計算できることに、注意されたい（インスタンスとクラスは、オブジェクト認識においては同じ大きさであり、クラス認識における受け入れ可能な一次のオーダの近似においてもまたそうであろう）。このようにして、画像特徴のおおよその姿勢を計算することができる。その結果、一の特徴部分マッチを用いて、配置変換を計算することが可能となる。特徴が認識において、マッチングされ、以降の検討対象から除かれたときは、また、すべてのそれと等価な特徴が除かれる。この手法は、「仮説非等方スケーリング」による、視点のための画像調整と呼ばれる。
【０２５２】
別の実施形態においては、画像の正面配置領域のための、他の手法が用いられてもよい。例えば、ある用途においては、直線のへりを境界づけることにより、平面が認識される。適切な環境の下では、このような平面は、境界づけるへりを用いて、正面に配置される。
［クラス部分による画像特徴の有望なマッチングの決定］
【０２５３】
第一の実施形態においては、認識は、対＜ｆ，ｃ＞を見つけることで、開始された。ここで、ｆは、画像中の特徴であり、ｃは、ＭＢ（ｆ，ｃ）の値が大きいようなクラスである。別の実施形態においては、付加的データ構造を用いて、そのような対を見つけることで、処理を迅速化することができる。このような実施形態においては、各クラス部分は、これらのデータ構造において指標として用いられる付加的な「質的記述子」を含む。Ｂ型のアピアランスから導かれる様々な質的記述子を、この目的のために用いることができる。この例は、各方向への勾配の二乗平均、主要な成分解析の始めのＫ成分、アピアランス値のヒストグラムを含む。多くの他のものも選択されうる。一般的に、量的記述子は、複数の成分を有してもよい。
【０２５４】
量的記述子は、各サンプルオブジェクトの各要素について計算される。以下のように、量的記述子は、各クラス部分について、計算される。量的記述子のそれぞれの成分において、全ての対応オブジェクトモデル要素について、最小値と最大値が計算される。クラス部分のための量的記述子の成分が、二つの外部の値によって境界を示される区間によって、表現される。データベース中の指標は、これらの区間から構築される。こうするにあたって、量的記述子の各成分は別個に処理される。指標を構築するにあたって、明示的なポインタを用いたり、データ共有手法を用いたりして、データ記憶部分の量を最小化するための、様々な手法が用いられる。
【０２５５】
認識の最中は、各画像特徴アピアランスについて、量的記述子が計算される。ｆが認識において検討されている特徴であるならば、量的記述子は、これらの有望なマッチングを提供するクラス部分を検索するために用いられる。ｑを、量的記述子であるとする。ｑの各成分について、検索はその成分と整合するクラス部分の集合を返す。λｉを、ｉ番目の成分と整合する（クラス）部分の集合であるとする。全ての量的記述子と整合する部分は、論理的である。
【０２５６】
別の実施形態においては、区間を、適切な値の集合や、最も一般的な値の集合を記述するための、他のデータ構造で置き換えてもよい。検索を実行するために。様々なデータ構造が用いられてもよい。
［認識における対のフィルタリング］
【０２５７】
第一の実施形態においては、特徴部分マッチ＜ｆ，ｃ＞が、ＭＢ（ｆ，ｃ）＞τｐａｉｒのテストに基づいて保持された。別の実施形態においては、どの対を保持するか決定するために、他のフィルタが用いられてもよい。例えば、対＜ｆ，ｃ＞は、十分に特殊であるときに、好適なマッチングであるとみなされうる。すなわち、ある部分がその特徴に類似し、他の部分でその特徴に類似するものはないということである。特殊性は、以下の比で測ることができる。
ＭＢ（ｆ，ｃ）／ｍａｘｋＭＢ（ｆ，ｋ），ｋ≠ｃ
この比は、計算され、適切な閾値と比較されてもよい。別の実施形態においては、保持する対を選択するために、他の基準が用いられてもよい。
［初期対応仮説の集合の構築］
【０２５８】
第一の実施形態においては、上述のように、初期対応仮説の集合を構築した。別の実施形態においては、初期対応仮説は、他の方法で取得されてもよい。
【０２５９】
初期対応仮説を構築するための、別の一の手法は、初期対応仮説をインクリメント的に構築することである。例えば、まず始めに、正確に、τｍｉｎＨ対の初期対応仮説が検討され、次いで、正確に、τｍｉｎＨ＋１が検討される、などである。この処理は、ある最大上限数の対が到達したとき、または、初期対応仮説を構築するのに十分な対を有するクラスがなくなったときに、終了する。
【０２６０】
また別の実施形態は、対応を選択するための、異なるメカニズムを採用する。対応は、ランダムに選択されてもよく、またはある確率分布にしたがって選択されてもよい。これに代えて、確率分布が構築され、そして、可能な特徴対応からサンプリングするにあたって、ＲＡＮＳＡＣ法が採用されてもよい。ＲＡＮＳＡＣ法は、非特許文献２０のような、標準的な教科書に記述されている。
【０２６１】
別の方法においては、これに代えて、対応するグループ［＜ｆ１，ｃ１＞，．．．，＜ｆｎ，ｃｎ＞］が選択されてもよい。すなわち、画像特徴ｆｋが画像の近傍領域に存在し、シーンにおいて、全ての画像特徴ｆｋが同じオブジェクトに関連付けされている可能性を高めるために、選択されてもよい。画像特徴ｆｋを選択するためのランダムサンプリング手法において、画像の距離が、重み付け関数として用いられてもよい。この代えて、特定の用途において興味の対象である画像の特定の一部において、特徴が優先的に選択されてもよい。これらの手法については、様々なバリエーションが存在する。
【０２６２】
第一の実施形態においては、初期対応を選択するために、アピアランス情報のみが使用された。別の実施形態においては、このステップにおいて、位置情報が用いられてもよい。例えば、部分位置の分散が小さいものに、クラス部分が制限されてもよい。この選択性は、初期配置の信頼性を向上させる。
【０２６３】
第一の実施形態においては、初期対応仮説を構築するために用いられた特徴部分マッチの最小値および最大値がデータベース全体について、決定される。別の実施形態においては、その数は、各クラスについて、経験的に決定されてもよい。
［拡張する対応仮説の選択］
【０２６４】
第一の実施形態においては、それぞれについて、配置変換を計算し、仮説の元で、クラス比を計算し、最も大きいクラス比を持つものを選択することにより、拡張すべき初期対応仮説を選択した。別の実施形態においては、他の方法で選択がなされてもよい。例えば、初期対応仮説は、仮説中の全ての対＜ｆ，ｃ＞についての値ＭＢ（ｆ，ｃ）を用いてスコアをつけることができる。この方法は計算がより迅速であるため、一部の用途においては望ましいだろう。
［対応仮説の拡張における効率的な姿勢の計算］
【０２６５】
対応仮説を拡張するとき、最初から、配置変換を計算する必要はない。むしろ、配置変換の前の推定が、見当として用いられてもよい。これは、非特許文献１０のアルゴリズムによると、拡張の前に計算された配置変換において、姿勢最適化を始めることにより達成される。
［好適な対応仮説を見つける］
【０２６６】
認識は、好適な対応仮説を見つけることに関する。すなわち、探索の問題である。第一の実施形態においては、上記の探索方針を用いた。そして、別の実施形態においては、この探索方針を、上記のように、修正してもよい。
【０２６７】
しかしながら、別の実施形態においては、完全に異なる探索方針がもちいられてもよい。別の方針の例の二つは、以下のとおりである。（１）対応仮説を選択し、拡張する処理は、深さ位置の探索であることに、注意されたい。この代わりに、複数の対応仮説が同時に拡張される幅優先探索を用いることが可能である。幅優先探索には、様々なバリエーションがある。その一つにおいては、各拡張世代において、全ての動作中の対応仮説が同じ長さをもつように、拡張が実行される。他の変形例においては、各拡張の世代において、どの動作中の対応仮説を拡張するかを決定するために、メリット関数が用いられる。また他の変形例においては、多数の動作中の対応仮説とともに、探索が開始され、探索が進行するにつれ、セットが刈り込まれる。また他の変形例においては、探索が進行につれて、セットが成長する。（２）初期対応を構築し、展開する代わりに、完全な対応仮説を構築することも可能である。
［配置変換の下でのジオメトリマッチング］
【０２６８】
第一の実施形態においては、上記のように、配置変換の下で、ジオメトリ尤度が計算された。これにより、各クラス部分の三次元位置が画像に投影され、投影された位置を所与として、その場所に、対応する対応特徴を観測する確率が計算された。別の実施形態においては、二次元画像位置よりむしろ、三次元特徴位置の表現で、ジオメトリ尤度を計算する方が望ましい場合もある。
【０２６９】
これを実行するための一の方法は、以下の通りである。非特許文献１０に述べられているように、「オブジェクト空間誤差」を記述することが、可能である。このために、観測された二次元画像位置ｕが、三次元一様座標ｖで、二次元画像位置の値に値１を付加することによって表現される。配置変換γは、先に述べたように、回転行列ｒと、並行移動ベクトルｔで構成されるものとする。三次元特徴位置は、ベクトルｘで表現される。これらにより、オブジェクト空間誤差は、次の式で与えられる。
ｅ＝Ｅ（γ，ｘ，ｖ）＝（１／||ｖ||２）ｖｖＴ（ｒｘ＋ｔ）−（ｒｘ＋ｔ）
γと、対応するｘとｖが正しい値である場合、Ｅ（γ，ｘ，ｖ）＝０である。
【０２７０】
γ、ｘ、ｖが、ガウス分布確率変数である場合、一次のオーダでは、ｅはゼロ平均ガウス分布確率変数であり、その分散は、以下の式で表される。
Λｅ＝ＪΓΛΓＪΓＴ＋ＪＸΛＸＪＸＴ＋ＪＶΛＶＪＶＴ
ここで、ＪΓは、γについての、ｅのヤコビアンであり、ＪＸは、ｘについての、ｅのヤコビアンである。典型的な用途においては、ΛＶは、重要度が低いため、この項は、無視してもよい。
【０２７１】
したがって、平均位置μＸ、分散ΛＸのクラス部分、推定された配置μΓ、その分布ΛΓ、そして観測された画像位置ｖを所与として、近似式
Ｐ（ｖ｜μΓ，ΛΓ，μｐ，Λｐ）＝Ｇ（Ｅ（μΓ，μＸ，ｖ）；０，ＪΓΛΓＪΓＴ＋ＪＸΛＸＪＸＴ）
が、要素のジオメトリ尤度の計算に用いられる。
［配置変換の下でのアピアランスマッチング］
【０２７２】
第一の実施形態においては、配置変換の下でのアピアランス尤度は、上述のように計算された。これは、二次元画像特徴からパッチを取ることにより始められ、対応するクラス部分と配列するように、リサンプリングされた。別の実施形態においては、他の方向に進んでもよい。すなわち、そのクラス部分のアピアランスをとり、対応する画像特徴と配列するように、リサンプリングしてもよい。
【０２７３】
この場合、ワーピング関数Ｗは、クラス部分のアピアランスモデルに作用する。これは、クラス部分姿勢と配置変換を用いて、カメラフレームから、局所座標における特徴の姿勢への、座標変換を計算する。ある一の実施形態においては、これは、局所パッチを平面としてモデル化し、そして、平面ホモグラフィを計算する。平面ホモグラフィは、配置変換の下で、クラス部分アピアランスをカメラ画像に投影するために用いることができる。ｐ＝Ｗ’（ｑ，γ，φ）が、配置変換γの下での姿勢φについてのクラス部分アピアランスｑをリサンプリングを表すものとする。
【０２７４】
投影されたアピアランスの平均μＰは、ｑ、γ、φの分布の平均に適用されたＷ’である。クラス部分アピアランスΛＰの共分散は、ｑ、γ、φについての、ヤコビアンＷ’を用いて、計算することができる。そして、上記の配置変換手法を適用することによって、計算することができる。＜ｆ，ｃ＞を、特徴部分マッチであるとする。特徴ｆのＡ型アピアランスを、ｆａとする。ｃのＡ型アピアランスを、ｑであるとする。すると、与えられたｃについての、配置変換Γの下での、ｓのアピアランス尤度は、以下のように計算されてもよい。
Ｐ（ｆａ｜ｃ，Γ）＝Ｇ（ｆａ；μｐ，Λｐ）
［未検出特徴を見つける］
【０２７５】
第一の実施形態においては、画像中で特徴が検出され、クラス部分にマッチングされた。別の実施形態においては、対応仮説を拡張する処理が、以下の事実を用いてもよい。すなわち、クラスモデルの配置変換は、画像特徴の位置、特に、未検出の可能性のある画像特徴の位置を示唆する。これを用いるための二つの方法を以下に述べる。
【０２７６】
別の実施形態の一つにおいては、一旦、配置変換が対応仮説について計算されると、クラス部分の三次元位置は、濃淡画像に投影される。これらの、見えるけるどもマッチングする画像特徴のないクラス部分のために、対応する画像領域の周囲の位置が、ワーピング関数Ｗを用いてリサンプリングされる。そして、ワーピングされた画像特徴について、Ａ型アピアランス記述子が計算される。この画像アピアランス記述子は、その部分について、Ａ型アピアランス記述子と比較される。リサンプリングされた、濃淡の取り込みにより、対応する仮説の尤度関数が増加したならば、その特徴はも対応仮説を拡張するために用いられる。
【０２７７】
別の実施形態においては、上記のステップは、以下のように増やされる。一旦クラス部分が画像に投影されると、その特徴の周りの大きな部分が、ワーピング関数Ｗを用いて、リサンプリングされてよい。関心点演算子が、その大きな領域において評価され、関心点が存在するか、決定される。もし存在するならば、どの位置、そしてどのスケールで存在するか、決定される。関心点が検出されたならば、特徴が計算される。その特徴は、検出された特徴のリストに加えられてもよい。その特徴についての、可能なマッチングの集合が計算されてもよく、すべての適切な仮説が、この特徴について、更新される。この処理は、見えるけれどもマッチング画像特徴を有さない、全てのクラス部分について繰り返される。そして、計算は、以前のように進行する。
［ジオメトリ尤度の計算］
【０２７８】
第一の実施形態においては、特徴部分マッチに関連する確率が、独立ガウス分布確率変数として、評価された。しかしながら、画像特徴のマッチングを用いてクラスモデルの姿勢をクラス部分にフィッティングする処理は、データの自由度の数を縮退させる。そして、変数の間の依存性が導入される。別の実施形態においては、代わりに、検出された特徴の位置と、モデルによって、投影された位置のモハラノビス距離の確率を評価することによって、この事実を有利に利用する。ｎ個の特徴について、この分布は、２＊ｎ−６個の自由度を有する。したがって、モデルフィットへのデータの依存性が、適切に、説明されるだろう。
［作業中の対応仮説を拡張するための対の選択］
【０２７９】
第一の実施形態においては、上記のように、作業中の対応仮説を拡張するための試行対が選択された。別の実施形態においては、別の選択がなされてもよい。例えば、適切な各対が検討されてもよく、その対を拡張したものとしてクラス尤度が計算されてもよい。その結果最も高いクラス尤度を得た対が拡張のために選択される。
［クラス尤度比の計算］
【０２８０】
第一の実施形態においては、上記のように、クラス尤度比は、和を、最大値で置き換えることによって、計算された。別の実施形態においては、これらの尤度比は、付加的な項を考えることで、近似されてもよい。例えば、単一の最大値ではなく、最大の確率をもつＫ個の要素が用いられてもよい。Ｋは、正確さと、計算スピードのバランスで選択されてもよい。
［対数尤度と対数尤度比］
【０２８１】
第一の実施形態においては、尤度と尤度比が計算された。別の実施形態においては、対数尤度と対数尤度比を用いることにより、同等の結論を達成されてもよい。例えば、ガウス分布の場合には対数を用いることにより、ほとんどの計算を、計算された量の線形結合の和および差に、縮退される。これにより、指数関数を評価して、この方法の全体的な数値的安定性を向上させる必要性を回避することができる。
［ディスカウントファクタ］
【０２８２】
第一の実施形態においては、クラスが有するかもしれない特徴の数は、クラス認識において、考慮されていなかった。例えば、１０個の可視部分を有するクラスに１０個の特徴がマッチングされた場合、これは、１０個の特徴が１００の部分を有するオブジェクトにマッチングしたときよりも、より有望なマッチである。この識別性は、尤度関数中の第三番目の因数であるディスカウントファクタＬＤを用いて、モデル化することができる。
【０２８３】
第一の実施形態においては、ＬＤは、１であるとされた。しかしながら、別の実施形態においては、ほかのディスカウントファクタを用いることが選択されてもよい。例えば、別の実施形態においてはＬＤ（ｈ，Ｃ，γ）＝Ｐ（ｈ｜Ｃ，γ）であるＬＤを選択してもよい。これは、クラスの選択Ｃと、配置変換γを所与としたときの、仮説ｈの確率である。別の実施形態においては、このモデルは、以下のように計算されてもよい。与えられたＣのクラス部分が、配置変換γの下で確率を決定し、続いて可視のクラス部分の数の総計と、検出され、マッチングされた特徴の確率を用いて、特徴マッチングの数の二項分布を計算する。
［クラス尤度比が閾値を超えないときの認識］
【０２８４】
第一の実施形態においては、クラス尤度比が、閾値を超えないときは、画像特徴の集合と、クラス部分のマッチングは、初期マッチとしては、許容されなかった。別の実施形態においては、初期マッチは、一時的に認められず、他のマッチングが考慮される。許可されなかったマッチが存在し、認められていないマッチについてクラスインスタンスがマッチングされたとき、そのマッチは、再び許可され、認識処理は繰り返される。この別の実施形態は、部分的に隠蔽されているクラスインスタンスの検出を向上させるかもしれない。特に、Ｐ（ｈ｜Ｃ，γ）の計算は、Ｃを隠蔽しているかもしれない認識されたクラスインスタンスを考慮することができる。これにより、隠蔽されていたオブジェクトが認識された後のＣの尤度比を向上するかもしれない。
【０２８５】
別の実施形態の一つにおいては、クラスディスカウントファクタは、クラス内のオブジェクトの範囲を所与として、特徴を検出する確率を考慮するように、修正された。オブジェクトの広がりは、クラス中心を中心とする、位置の二次元配列として表現される。配列中の確率位置は、オブジェクトのビューについて、与えられたオブジェクト位置を隠蔽しているビューの比率を記憶する。異なるクラスモデル姿勢についての隠蔽の確率を表するために、いくつかの、このような配列が格納されることができる。検出されていないクラスインスタンスにおける特徴検出の確率は、すでに検出されたクラスインスタンスの確率マップを用いて、適切に、位置、スケール、方向を説明するために、リサンプリングされ、修正される。
［閾値の選択］
【０２８６】
認識フェーズにおいては、数個の閾値を用いる。第一の実施形態においては、閾値は上記のように選択された。別の実施形態においては、閾値は他の方法で選択されてもよい。トレードオフ変数αについての、異なる値が使用されてもよい。非線形トレードオフ関数が、誤差の、コストを計算するために、用いられてもよい。閾値は、続いて計算されて、摂動により、調整されてもよい。二以上の閾値は、順番にではなく、結合して計算されてもよい。
【０２８７】
第一の実施形態においては、そのクラスインスタンスが認識されたか決定するための、クラス尤度比についての、閾値τＣは、経験的に計算された定数であった。別の実施形態においては、これは、別の方法で取得されてもよい。幾つかの別の方法においては、評価されている最終対応仮説の長さの関数として、経験的に決定されてもよい。第一の実施形態において記述された手法と類似する、最終対応仮説の各長さについて、別個に最適化を実行するような手法が用いられてもよい。これにより正確性は向上するだろう。しかし、ラベル付けされた大きなデータが必要となり、時間も長くかかる。
【０２８８】
別の実施形態においては、受け入れるか否かのクラス尤度比の閾値は、各クラスについて、別個に決定されてもよい。ある用途においては、擬陽性と偽陰性との間の相対的なコストについての、各クラスについて、異なる選択を出すことが、望ましいかもしれない。例えば、データベースが、（間違った警告のコストがあるとしても）見逃してはならない危険なオブジェクトのクラスをデータベースが含むと仮定する。閾値を決定するために、最適化処理が実行されるとき、擬陽性のコストは減らされ、対応して偽陰性のコストがその特定のクラスについて増やされる。一般的に、クラス尤度比の閾値は、用途によって特定の目的を達成するために、計算される。したがって、これらは、「選択された受け入れ基準」と呼ばれる。
［決定基準］
【０２８９】
第一の実施形態においては、確率と、確率の近似を計算し、クラス尤度比に対する近似を用いて、画像中にクラスインスタンスが存在するか、判断した。すなわち、第一の実施形態においては、クラス尤度比を、いわゆる「クラススコア」であるとした。
【０２９０】
別の実施形態においては、クラススコアの別の定義が用いられてもよい。例えば、個々の特徴と部分のマッチングの尤度の関数を「クラススコア」としてもよい。また別の実施形態においては、特徴と部分のマッチングの数を「クラススコア」としてもよい。
【０２９１】
さらに、決定のためには他の根拠が用いられてもよい。例えば、ある姿勢においてクラスのアピアランスを学習するために、サポートベクタマシンがもちいられてもよい。第一の実施形態に述べられた手法が、クラスと姿勢についての仮説を構築するために用いられてもよく、そして、画像、クラス、姿勢にサポートベクタマシンが適用され、仮説が正しいか、決定されてもよい。これに代えて、他の機械学習手法が、決定をなすために用いられてもよい。
【０２９２】
これらの全ては、クラススコアが受け入れ基準を満たす対応仮説の選択処理についての実施形態である。
［手続きステップの実施］
【０２９３】
幾つかの実施形態における手続きステップについて、上に述べた。これらのステップは、Ｃ＋＋、Ｃ、Ｊａｖａ（登録商標）、Ａｄａ、Ｆｏｒｔｒａｎ、このほかの一般的な目的のプログラム言語など、様々なプログラム言語で実現できる。これらの実装は、特定のコンピュータの機械語にコンパイルされてもよく、インタープリトされてもよい。
【０２９４】
本方法は、コンピュータ可読である媒体に格納したプログラム命令を実行するコンピュータにおいて実現されてもよい。
【０２９５】
手続きステップはまた、プログラミング可能な専用プロセッサによって実現されてもよい。このような専用ハードウェアには、例えば  デジタルシグナルプロセッサ（ＤＳＰ）、グラフィックプロセッサ（ＧＰＵ）、セルプロセッサ、メディアプロセッサ、ストリーミングプロセッサなどが含まれてもよい。
【０２９６】
手続きステップはまた、この課題のために設計された電子機器によって実現されてもよい。特に、集積回路がもちいられてもよい。集積回路の例には、フィールド・プログラマブル・ゲートアレイ（ＦＰＧＡ）、ゲートアレイ、標準セル、フル・カスタム（ｆｕｌｌ  ｃｕｓｔｏｍ）などが含まれてもよい。
【０２９７】
本発明で開示された方法を用いる実装はまた、逐次的ではなく、並行な手続きステップで実行されてもよい。
［ロボット工学への適用］
【０２９８】
その他の応用例として、本発明は、ロボット操作に適用されてもよい。オブジェクトは、本発明で述べたように認識される。いったんクラスインスタンスが認識されると、ロボット操作にふさわしい性質がデータベースで調べられる。これらに性質には、重み、重心、安全に適用できる握力の制限などを含む。これらの多くは統計的分布により記述される。他の、操作における制限などは、クラスの全てのインスタンスについて共通であってもよい。
［顔認識への適用］
【０２９９】
その他の応用例として、本発明は、顔認識に適用されてもよい。顔認識における従来の手法は、アピアランスモデルか三次元モデルが用いられ、またはこれらが別個に実行された後で、初めてその結果を結合された。上述のように、位置合わせされた距離濃淡画像を取得し、姿勢不変である特徴に基いてモデルを構築し、認識に用いることで、顔認識は有利に実行されるだろう。このような用途においては、性別、年齢、民族性、または独特な顔の特徴に基づいて、三次元クラスモデルが構築されるであろう。
【０３００】
顔認識はまた、オブジェクト認識として実行することもできる。この場合、オブジェクトは特定の個人である。特に、本発明によると、故意か否かアピアランスが変化した個人は、バリエーションを有するオブジェクトとして扱われる。このように扱うことによる恩恵は、当業者にとって明らかであろう。
［他の用途］
【０３０１】
本発明の適用は、上に列挙された用途に限られない。本発明はまた、検査、組み立て、物流など、他の多くの分野に適用しうる。このリストは、本発明を制限するものではなく、説明のためのものであり、本発明は様々な目的のために使用されうることは、理解されるところである。
［結論、効果、作用領域］
【０３０２】
本発明は、三次元クラスモデルを用いて二次元画像中のクラスインスタンスを認識するシステムと方法、また、三次元オブジェクトクラスモデルを用いて二次元画像中のオブジェクトインスタンスを認識するシステムと方法、を提供する。
【０３０３】
先の明細書において、本発明は特定の実施形態を参照して記述されたが、本発明がこれらの実施形態に限られるものでないことは、当業者に理解されるところである。上述の本発明の様々な特徴や観点は、個別にまたは結合して用いられてもよい。さらに本発明は、本明細書のより広い精神および作用範囲から外れることなく、ここで記述された環境や用途を超える任意の数の環境や用途で使用されうる。従って、本明細書と図は、制限するものではなく、説明のためであると見なされる。特に、ここで用いられる、「備える」、「有する」、「含む」の言葉は、拡張可能な言葉として読まれることを意図するものである。
【図１】
2008547094.tif 000005
【図２】
2008547094.tif 000006
【図３】
2008547094.tif 000007
【図４】
2008547094.tif 000008
【図５】
2008547094.tif 000009
【国際調査報告】
2008547094.tif 000010