有界三次元対象物の分類と空間ローカライゼーションのためのコンピュータ視覚システム
本発明は、有界三次元対象物の認識、分類、および空間ローカライゼーションのためのシステムと方法に関する。特には、対象物の認識、分類、およびローカライゼーションのためのコンピュータ化された方法に関する。本方法は、カメラにより記録された、または対象物のＣＡＤ表現を使用して構築された多数のトレーニング図に基づいて、トレーニングデータベースを生成することを含む。特徴的曲線は、トレーニング図から導出され、曲線のプリミティブが検出される。フィーチャの本質的および非本質的記述子が、対象物のクラスおよび図の姿勢状態に関するデータと共にデータベースに格納される。最終的には、認識は二段階で行われる。最初は、認識図の本質的記述子がデータベースの記述子と比較される。二番目に、最良の整合フィーチャから、どのフィーチャが、同じ姿勢状態にある同じ対象物クラスであることを示唆するという意味で、相互に一致するかが調べられる。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
本発明は、コンピュータ視覚システムにおける対象物認識のための方法に関し、特に、本方法は、有界三次元対象物の分類と空間ローカライゼーションに関する。
【背景技術】
【０００２】
発明の背景
製造工程の自動化における障害（ボトルネック）は、部品および半製品を、加工、組立て、塗装、および梱包などのために自動システムに供給することにある。今日では、１）振動ボール（皿）、２）設備、および３）コンピュータ視覚システムの３種類のシステムが利用可能である。振動ボールは小寸法（約５ｃｍ未満）の部品に対してのみ適している。内部格納全体が設備に基づかなければならないので、設備は高価である。この二つのシステムは共に新しい部品が導入されると再設計および再製造しなければならない。これまで開発されてきたコンピュータ視覚システムには重大な欠陥があった。容認できないほどの処理速度のシステムがあったり、汎用性に欠けているシステムであったりしていた。今日利用できる、高速かつ汎用性のあるシステムでは、対象物を平坦な搬送ベルト上で分散して置く必要があり、対象物とカメラの距離は、対象物の高さに比べて遥かに大きくなくてはならない。この後者の制限は、使用される認識モデルが、カメラの三次元と二次元の間の変換における、透視法効果を含まないために、現在のシステムにとっては基本的である。このように、５ｃｍ〜１０ｃｍ以上の高さの部品に対しては、標準のコンピュータ視覚システムは、不便なほど遠隔に配置するカメラを必要とする。更に、標準コンピュータ視覚システムは、箱やパレットにランダムな方向に向けて積まれた部品を構造的に把握させるようにロボットを導くことはできない。
【０００３】
リサイクル部品が、リサイクル工場に運ばれてきて分類されるときにも、別の障害が存在する。消費者製品、特に自動車で使用されている部品の再構築は、環境および資源の面からの理由により将来、増加すると予測されている。再構築工程の前に、分類が必要となる。
【０００４】
現在における技術が不十分な分野の三番目の例は、構造化環境における自走ロボットの高速ナビゲーションである。カメラに基づくナビゲーションシステムは、構造物要素、固定家具などの認識を必要とする。これらのセグメントは有界三次元対象物と考えられる。
【０００５】
更に、本システムは自動車や建物の特定および分類のために衛星に適用して使用することができる。
【発明の開示】
【課題を解決するための手段】
【０００６】
発明の概要
本発明の良好な実施形態によれば、対象物の認識および／またはローカライゼーションは対象物の認識画像において特定されるプリミティブに基づいている。このように、第１の態様において、本発明は、デジタル画像において、輪郭、好ましくはレベル輪郭とプリミティブを決定する方法であって、
デジタル画像の勾配を生成し、
絶対勾配の一つまたは二つ以上の極大値を求め、
一つまたは二つ以上の極大値を、輪郭を生成するためのシード（種）として使用し、ここにおいて各シードに対する輪郭の生成は、デジタル画像内にあり、輪郭に属する場所を表現する点の順序リストを決定することを含み、
すべての場所に対して、輪郭の、好ましくはｄθ／ｄｓ、好ましくは画素単位で決定される曲率を決定し、
決定された曲率から、プリミティブを輪郭上の、または輪郭のセグメント上の特徴点として決定するステップを含む方法である。
【０００７】
トレーニング画像から導出されたプリミティブに基づいて、対象物の認識および／またはローカライゼーションは、好ましくは本発明の第２態様による方法により実行される。第２態様は、三次元対象物の分類および／またはローカライゼーションのような認識方法であり、一つまたは二つ以上の対象物は、前記対象物の二次元デジタル画像である認識画像を提供するように画像化され、本方法は、フィーチャ（特徴）の本質的および非本質的特性である数値記述子が多数のトレーニング画像に対して格納されたデータベースを利用し、本方法は、
画像に対して、プリミティブの予め定義されたセットであるフィーチャを特定し、
フィーチャの数値記述子を抽出し、ここにおいて数値記述子は、
画像中のフィーチャの位置および方位のようなフィーチャの非本質的特性と、
フィーチャに適用される同形変換後に導出されるフィーチャの本質的特性の二種類があり、
特性をデータベースに格納された特性と整合し、整合物が見つかれば、データベース内で整合した特性に対応する対象物を、認識すべき対象物の対象物に類似していると割り当てる認識方法である。
【０００８】
第３態様においては、本発明は、三次元対象物の位置決めおよび／または分類に関連して有効なデータベースの生成方法に関し、対象物は、対象物の二次元デジタル画像を提供するように画像化され、本方法は、対象物の二次元デジタル画像のプリミティブを決定するために本発明の第１および／または第２態様による方法を利用し、本方法は、
一つまたは二つ以上の対象物の多数のデジタル画像において、プリミティブの予め定義されたセットであるフィーチャを特定し、画像は、一つまたは二つ以上の対象物の異なるローカライゼーションを表わし、
フィーチャの数値記述子を、データベースから抽出して格納し、数値記述子は、
画像中のフィーチャの位置および方位である、フィーチャの非本質的特性と、
フィーチャに適用される同形変換後に導出されるフィーチャの本質的特性の二種類あることを含む方法である。
【０００９】
本発明は、このようにシステムが対象物を認識し、分類し、位置決めすることを可能にする。
【００１０】
本発明は、既に定義された輪郭近傍で特定される潜在シード点を削除するステップを更に含んでよい。これは、好ましくは、既存の輪郭に近すぎる輪郭の生成を避けるために行われる。
【００１１】
更に、輪郭の生成は、各点がシードの値に共通に割り当てられた値を有する、デジタル画像内の場所を表現する点リストを割り当てることを含んでよい。
【００１２】
更に、輪郭の生成は、各点において、最大勾配の方向に続く点を含む点の順序リストを決定することと定義してよい。
【００１３】
更に、輪郭の生成は、各点において、ある輪郭方向に直交すると検出された最大または最小勾配の方向に続く点のリストを割り当てることを含んでよい。どちらの勾配に続くかは選択された勾配の方向に従って決定してよい。
【００１４】
更に、輪郭の生成は、シードの値を超える、またはそれ未満の値を有する画素リスト、およびシードの値未満の、またはその値を超える値を有する一つまたは二つ以上の隣接する画素を割り当てることを含んでよい。
【００１５】
画素リストは、好ましくは所定の方法で、デジタル画像内を移動することにより確立される。確立されたリストは、リストの検索速度を増すと考えられる画素の順序リストであってよく、これは、最大値または最小値のようなある値は、例えば、リストの最上部と最下部にそれぞれ位置することがあるためである。しかし、他のソリューションを適用してもよい。
【００１６】
更に、輪郭は画素のリストに基づく内挿法により決定してもよい。これは、好ましくはより滑らかな輪郭を得るために実行される。
【００１７】
勾配図の作成は、隣接する画素に割り当てられた数値間の差を計算することにより勾配を決定して達成してもよい。このように勾配図が得られ、そこから更なる情報が抽出される。
【００１８】
勾配は、各要素が好ましくは第１画像内の特別な場所に対応し、特別な場所における第１画像の色調の勾配値を表わす数値であるアレイに格納してよい。
【００１９】
プリミティブ生成のために使用される曲率は、θを輪郭上の１点における接線方向とし、ｓを基準点から測定される弧の長さとしたときに、好ましくは、κ＝ｄθ／ｄｓとして確立される。
【００２０】
上記の第１、第２、および第３態様で記述したプリミティブは、好ましくは下記の特徴、
直線のセグメント、
相対的に大きな半径の円のセグメント、
変曲点、
曲率の最大数値の、好ましくは角部として割り当てられた点、
曲率の非常に小さな、および非常に大きな数値の部分を分離する点、および
輪郭により囲まれた小さな領域のエンティティ、
を一つまたは二つ以上備える。
【００２１】
上記の生成された輪郭に対して、下記のプリミティブ、
所定のレベルより高い曲率の絶対値の値を有する輪郭の領域またはその上の点である変曲点、
曲率の正のピークを有する輪郭の領域またはその上の点である凹状角部、
曲率の負のピークを有する輪郭の領域またはその上の点である凸状角部、
ゼロの曲率を有する輪郭のセグメントである直線セグメント、および／または
一定曲率を有する輪郭のセグメントである円形セグメント、
の一つまたは二つ以上が検索される。
【００２２】
認識方法に関する本発明の第２態様によれば、整合付けステップは更に、認識画像を、データベースに格納されたトレーニング画像と整合することを含み、整合付けの方法は、各トレーニング画像に対して、
トレーニング画像のフィーチャと同一の認識画像のフィーチャをもたらす変換のロール、チルト、およびパンの値を決定し、
変換により決定されたロール、チルト、およびパンの値により定義されるパラメータ空間におけるクラスタを特定し、および
予め定義された強度を有するクラスタを、対象物のタイプおよびローカライゼーションに対応するものとして特定するステップを備えてもよい。
【００２３】
データベースは各画像に対して、それぞれがその本質的特性およびその非本質的特性を有するフィーチャを表わす一つまたは二つ以上のレコードを備えてよい。
【００２４】
更に、整合付けは、
ロール、チルト、およびパンパラメータ空間をリセットし、
認識画像における各フィーチャに対して、認識画像の特性をデータベースに格納されている特性と整合付け、
整合する場合、データベースから、および認識画像からの非本質的特性に基づいてロール、チルト、およびパンを決定し、
パラメータ空間を更新し、
クラスタリングをテストし、トレーニング画像のインデックスを有する十分に高い密度／母集団のクラスタの座標を格納するステップを含み、
このステップを認識画像のすべてのフィーチャの整合付けが終了するまで繰り返すことを含んでよい。
【００２５】
ロール、チルト、およびパンの決定は、好ましくは、データベース内の本質的特性と比較して類似のまたは同一の本質的特性を有するフィーチャに対してのみ行われる。このようにして、大量の計算時間が節約される。
【００２６】
更に、整合付けは、認識画像の本質的記述子と、データベースに格納されている本質的記述子と比較し、それにより整合するフィーチャを選択することを含んでよい。
【００２７】
第３態様で記述したデータベースの生成は、下記に記述されるステップとフィーチャによって更に生成されてもよい。
【００２８】
好ましくは、非本質的特性は基準点と基準方向を備える。一方、本質的特性は、好ましくはフィーチャの数値量を備える。
【００２９】
対象物は少なくとも二台の撮像装置を使用する方法で画像化されてもよく、それにより対象物の少なくとも二つの認識画像を生成し、整合付けの方法が各認識画像に適用され、各認識画像に対して見出された整合物が比較されてもよい。
【００３０】
更に、二台の撮像装置を使用する方法は、
各撮像装置に対して、対象物の三次元基準点に対する推定値を提供し、
各撮像装置に対して、撮像装置のピンホールから推定された基準点までの直線を計算し、
少なくとも二つまたは三つ以上の直線が提供された場合は、
二つまたは三つ以上の直線が三次元で実質的に交差しない場合は、推定値を破棄し、
二つまたは三つ以上の直線が実質的に交差する場合は、
各撮像装置から得られた直線の間の擬似交点に基づいて、基準点のグローバルポジションを推定するステップを含んでよい。
【００３１】
以下、本発明と、特にその良好な実施形態を、添付図と関連してより詳細に呈示する。
【発明を実施するための最良の形態】
【００３２】
発明の詳細な説明
ここで記載される発明は、発明の背景の節で記載したすべての状況を対象としている。焦点は下記の特性、
トレーニング情報の簡単な生成、
トレーニング情報の合理的な少量、
透視法効果の正確な処理、
対象物の形状および見た目に関しての汎用性、例えば鋭い三次元エッジやランドマークは不要、
画像間の大規模な二次元整合または三次元再構築なしの高速認識、に置かれる。
機能
コンピュータ視覚システムは、別個のクラスに属する有界三次元対象物を分類および／または位置決めするために使用される。システムは一つまたは二つ以上のカメラで構成され、その画像は、１）三次元対象物のクラスと、２）その空間的位置および方位（姿勢状態）に関して解釈される。その機能は、他の対象物による可能性のある部分的遮蔽と、画像の効果的でないセグメント化からはある程度独立している。対象物は特徴的な装飾や鋭いエッジを有する必要はない。この機能は、カメラの位置と、対象物とカメラの間の距離に対する対象物のサイズには依存しない。画像の解釈は速度が最適化され、これはデジタルカメラの使用、画像データの迅速な電子的伝送、および最適化コードを意味する。更に、本システムで使用されるカメラは必ずしも、光学カメラである必要はなく、カメラは、熱カメラのような他の種類であってもよい。
定義
図１４に示すカメラのピンホールモデル：カメラのフレーム（座標系）は軸ｕ、ｖ、ｗにより定義される。焦点は座標（ｕ、ｖ、ｗ）＝（０、０、ｆ）を有し、ｆはカメラの焦点距離である。好ましくは、ｕ、ｖ、ｆは画素単位であるとよい。実際のカメラは負のｆ値を有する。適切な同形変換はチルト軸（ｕ軸に平行）とパン軸（ｖ軸に平行）の周りの連続的な二回転により記述できる。
【００３３】
カメラはピンホール、つまり、透視法三次元−二次元変換の中心と画像面を有する撮像装置である。光軸はピンホールを通り直線であり、実質的に画像面に直交している。カメラの光軸の画像は、焦点と呼ばれ、図１４に示されている。画像は二つの軸、垂直（ｖ）軸と水平（ｕ）軸を有する。
【００３４】
好ましくは、対象物の見た目の下記の二次元特性、
１）外部輪郭（常に存在する）、
２）外部輪郭内に現れる輪郭、
３）輪郭の内部に現れる対象物の鋭い三次元エッジの画像、および
４）装飾物における二次元エッジ、が考慮される。
【００３５】
これらの特性は、画像では（一次元の）直線または曲線として現れる。下記においては、これらのフィーチャを、特徴曲線と呼ぶ。特徴曲線の特別なフィーチャをプリミティブと呼ぶ。プリミティブは点状（変曲点、最大曲率点など）または一次元（直線セクション、一定曲率のセクションなど）であってよい。プリミティブの特別な対、三つの組合わせ、またはそれ以上の数のセットをフィーチャと呼ぶ。フィーチャの最も有効なタイプはプリミティブの対である。これらのうちのいくつかを図２ａと図２ｂに示す。
【００３６】
単一で特別な対象物で、かつ既知の対象物−カメラ間の姿勢状態を有し、特別なカメラで撮影した画像をトレーニング図と呼ぶ。システムにより解釈される場面の画像を認識図と呼ぶ。
【００３７】
数値記述子はフィーチャの本質的特性と非本質的特性を記述する。本質的特性はフィーチャの回転不変記述子により記述され、非本質的特性は画像におけるフィーチャの位置と回転により記述される。
【００３８】
好ましくは、フィーチャは三つの非本質的記述子を有し、それはフィーチャの基準点の二つの座標と同形変換後の基準方向である。
【００３９】
レベル輪郭：好ましくは、レベル輪郭は、一定グレイトーン値ｇに対応する画像座標の順序リストである。座標は、一つはｇより大きいグレイトーンを有し、他方はｇより小さいグレイトーンを有する二つの画素間の線形内挿法により得られる。
【００４０】
エッジ輪郭：好ましくは、エッジ輪郭は、デジタル画像における場所を表わし、輪郭に属している点の順序リストである。好ましくは、点は、現在の運動方向に直交する勾配を計算し、最大勾配の方向に移動させることにより前点から得られる。輪郭点の副画素座標は、各輪郭点からある距離後ろ、または前に離れた（整数）画素の場所にわたる平均グレイトーンを計算することにより得られる。この平均グレイトーンは、考慮している点のシフトされた場所という結果になる内挿法のための基準として使用される。
【００４１】
図／画像または図／画像のセクションには二次元変換を実行できる。ここで考慮されている変換は、カメラの、そのピンホールの周りの仮想回転により特徴付けられる。これらの変換は、同形変換として示される。同形変換は、特別な軸の周りの連続するカメラの回転により指定できる。共通の記述法では、チルトは水平画像軸に平行な軸の周りの回転であり、パンは垂直画像軸に平行な軸の周りの回転であり、ロールは光軸の周りの回転である。これらの回転を図１４に示す。Ωを画像または画像セクションとする。変換された画像または画像セクションは、シンボルΩ’＝Ｈ（Ω）を有し、ここでＨは同形変換である。画像における任意の点Ｑは、点Ｑが焦点に変換されるという特性を有する同形変換のクラスを定義する。そのような変換の後の画像または画像セクションは、シンボルＨQ（Ω）を有する。この変換ＨQのクラスの一つのメンバーは、ロールがなく、パンが続くチルトにより特徴付けられる。この変換は、チルト・パン変換ＨQ、tpと呼ぶ。このクラスには他の多くのメンバーが存在する。好ましくは、それらのメンバーが良好に定義されたアルゴリズムを有する。
【００４２】
図１にチルト−パン同形変換を示す。変換前の原画像は上の図である。下の図はチルト−パン同形変換後の画像であり、ドームの頂点は焦点に移動されている。
【００４３】
好ましくは、同じクラスの対象物は幾何学形状に関して一様であり、これが装飾物に関してもある程度当てはまり、対象物の遮蔽されていない部分は、十分な特徴曲線を有する。特徴曲線を最善の状態で検出するためには、この場面の照明がかなり一定していることが好ましい。
方法の概説
認識は多数のトレーニング図の分析に基づく。これらのトレーニング図は、実際の対象物に向けられているカメラにより記録されるか、または対象物のＣＡＤ表現を使用して構築される。特徴曲線はトレーニング図から導出され、曲線のプリミティブが検出される。フィーチャの本質的および非本質的記述子は、図の対象物クラスと姿勢状態についてのデータと共にデータベースに格納される。上記のトレーニングに関する動作はオフラインで行われる。
【００４４】
認識の間、類似の画像分析が行われる。認識の残りの部分は二つの段階で行われる。第１に、認識図の本質的記述子はデータベースの記述子と比較される。第２に、最も整合するフィーチャの中から、同じ姿勢状態の同じ対象物クラスを示すという意味で、どのフィーチャが相互に一致しているかが調べられる。
トレーニング図数の削減方法
剛体は６の自由度を有するため、図の多様性は非常に大きい。トレーニング量を削減するために二つの方法が採用される。第１に、非本質的記述子は、チルト−パンにより同形に変換された画像から導出される。あるフィーチャに対して使用される変換はＨQ、tpであり、ここでＱは実際のフィーチャの基準点である。第２に、整合検索に使用される本質的記述子は、カメラのロールと等価である画像の回転に対して不変である。上記の二つの方法は、トレーニング図の量は、剛体が６の自由度を有するという事実にも拘わらず、３の自由度に制限できるということを示唆している。好ましくは、各フィーチャに対してトレーニングデータベースは下記の、
ａ）チルト−パンによる同形変換とロール操作に対して不変な記述子、
ｂ）画像軸に関する角度の二次元方位に対する回転記述子、
ｃ）チルト−パン同形変換に関連するチルトとパンの角度、を含む。
【００４５】
項目ａ）は、基準点をフィーチャに割り当てることができることを必要とする。
【００４６】
項目ｂ）は、基準方向をフィーチャに割り当てることができることを必要とする。
【００４７】
トレーニングセッションでは、基準方向と基準点はユーザーにより手動で割り当てられる。
【００４８】
トレーニングに関連する３の自由度は、対象物フレームにおけるピンホールの球座標（ρ、φ、θ）として選択できる（図１６参照）。トレーニング中、光軸は対象物フレームの原点を通り、カメラのロール角はゼロである。このように、ρ、φ、θは、対象物フレームの原点およびピンホールからのベクトルの、それぞれ長さ、方位角、および水平角である。トレーニングステップでは、ユーザーが対象物フレームの原点を割り当てる。ρ、φ、およびθの間隔とステップサイズは、アプリケーションによってはトレーニングの必要がある。適度な、または弱い透視法に場合は、フィーチャの直線寸法が近似的にρに反比例するため、少数のρの数値のみが、トレーニングの必要がある。
認識：変換、整合検索、逆変換、およびクラスタ分析
認識の第１ステップにおいては、認識図の分析され、変換されたフィーチャの記述子が導出され、適切な数の記述子間の最良整合が、認識図とデータベース（レーニング図数の削減方法）の節における（項目ａ））の認識図から見出される。第２ステップにおいては、認識図とデータベースの整合レコードに属する、（トレーニング図数の削減方法）の節の項目ｂ）とｃ）を考慮する。これらのデータは適切な逆変換に使用され、それにより、実際のフィーチャにより示唆される完全な三次元姿勢状態を計算する。六次元構成空間（各対象物クラスに対して一つの空間）における候補（票）のクラスタは、実際の対象物として解釈される。このクラスタ分析は、間違ったフィーチャ、つまり異なる対象物に属するプリミティブの検出された組み合わせを除去するためには重要である。
特徴曲線のプリミティブとフィーチャ
認識のための良好なプリミティブの例
１）直線のセグメント
２）相対的に大きな半径の円のセグメント
３）変曲点
４）最大曲率点
５）非常に低い曲率と非常に高い曲率の部分を分離する点
６）小さな領域を囲む曲線の場合：この領域の二次元的重心
図２は、上記の（特徴曲線のプリミティブとフィーチャ）節で記述したプリミティブを示す。図２ａはプリミティブの例を示し、図２ｂはプリミティブの対と、それらの基準点（細い円）と、それらの基準方向（矢印）を示している。図２ｃは角度を示し、ここで角度ｒは回転により不変であり、角度ｄは回転を記述する記述子である。
【００４９】
このシステムで使用されるプリミティブのセットは、好ましくは、下記の特性、
−基準点、
−基準方向（１８０度の不明性なしで）、
−一つまたは二つ以上の整合検索に適した回転不変記述子、を有するべきである。
【００５０】
これらの条件を満たす二つまたは三つ以上の任意の組み合わせを採用することができる。図２ｂは基準点と基準方向を含むプリミティブの適切な対の例を示している。フィーチャに、直線または円のセグメントが関連する場合は、フィーチャの部分的遮蔽を可能にする認識は、好ましくは適切な不規則性を含むべきである。
【００５１】
プリミティブの対の回転不変記述子は、例えば、点状のプリミティブ間の距離、直線部分の間の角度、接線と点状のプリミティブを結ぶ線の間の角度などである。図２ｃは回転不変角度と、（トレーニング図数の削減方法）の節の（項目ｂ）の回転記述角の例を示している。
二台または三台以上のカメラを使用する利点
単一カメラ適用例における姿勢状態の不確定要素はρ、つまり、ピンホールと対象物の基準点との間の距離である。エラーは、画素の分離化、カメラノイズ、および変動する対象物寸法により起こる。不確定性は、下記のように二台または三台以上のカメラからの検出結果の相関を取ることで大幅に減少できる。各カメラは対象物の三次元基準点に対する推定値を与える。不確定性ρを伴って、各カメラは、基準点の場所に対する高い確率を有する三次元の線を定義する。そのような線の間の擬似交点は対象物の基準点の最も可能性ある場所である。これは図１３に示されている。
【００５２】
この方法は、ステレオビジョンに関連する。従来のステレオビジョンには、短すぎるベースライン（ピンホールの間の距離）は不正確な深度の決定という結果になり、大きすぎるベースライン（そして、光軸間の大きな角）は対応する点／フィーチャの特定を困難にするため、根本的な制限がある。マルチビューデータベースのフィーチャと整合しているフィーチャを使用する、現在導入されている方法においては、画像における対応する点を見つける必要がない。従って、本発明のマルチカメラバージョンにより達成される深度の推定は、通常のステレオビジョンを使用するよりもより正確である。
【００５３】
二台以上のカメラを使用して得られる他の利点は、間違った分類と間違った姿勢状態の推定値の除去である。この除去は、弱い透視法により見たときの対称面を有する対象物の場合は、特に重要である。
トレーニング量と認識回数の推定
典型的な適用例においては、φ−θ空間におけるステップサイズは４度である。これは、制限のない角度範囲に対しては、ρの値当り約３，０００画像を意味する。ほとんどの適用例は３から４個の異なるρ値のみを必要とし、総計で約１０，０００画像を与える。各トレーニング図におけるプリミティブの一般的なセット数は５０であり、各データベースレコードにおける４バイトの浮動小数点エンティティの一般的な数は８である。そして、データベースの総量は一つの対象物クラスに対して１６メガバイトのオーダーである。このデータベースにおける速度最適化整合検索は、１ＧＨｚのＣＰＵ上では対象物クラス当り１秒に満たない時間だけ続くと予測される。対象物の姿勢状態が（ρ、φ、θ）−空間のより小さな部分に限られることが予め知られている適用例においては、上記の数はそれなりに削減することができる。
【００５４】
ここで記述される実施形態は、コンピュータ視覚システムにおいて使用される好ましいステップを含む。本システムは、一台または二台以上のコンピュータ視覚カメラの前にランダムに置かれた三次元対象物を分類および位置決めすることができる。本システムの発明の概要で述べた通り、好ましくは、認識は下記に基づく。
−トレーニング画像および認識画像における特徴曲線の決定
−フィーチャ記述子の導出（プリミティブおよびプリミティブ対）
−三次元解釈で使用される認識工程
使用される特徴曲線は、グレイトーン画像におけるエッジである。この記述において、「エッジ」はレベル輪郭（一定グレイトーンの曲線）またはエッジ輪郭（高勾配の曲線）として定義される。レベル輪郭を導出する方法は、（グレイトーン画像からのレベル輪郭の導出）の節で記述し、例示している。副画素により定義された輪郭を使用することにより、（輪郭からのプリミティブとフィーチャの導出）の節で概要を示したように、信頼できる特徴的な輪郭プリミティブ（直線のセグメント、変曲点、角部など）を導出できる。トレーニング画像および認識画像から導出されたプリミティブを使用する三次元の解釈は、（三次元解釈のステップ）の節で記述し、例示している。
グレイトーン画像からの輪郭の導出
この節では、レベル輪郭およびエッジ輪郭を導く画像分析を記述する。レベル輪郭の定義：図１５ａの右上の部分におけるフレームのグレイトーンの俯瞰図が図１５ｂに示されている。好ましくは、レベル輪郭は一定グレイトーン値ｇに対応する画像座標の順序リストである。座標は、一つはｇを超えるグレイトーンを有し、他方はｇ未満のグレイトーンを有する二つの画素間における直線内挿法により得られる。いくつかの定義の説明を下記に示す。
【００５５】
１．グレイトーン画像はグレイトーンの二次元アレイＧ［ｘ、ｙ］から構成される。各アレイメンバーは画素である。
【００５６】
２．各画素は画像面において整数座標を有する。
【００５７】
３．俯瞰図との類似において、グレイトーンは、グレイトーン俯瞰図における高さと考えられ、これは図１５ａと図１５ｂに示されている。
【００５８】
４．適切な内挿法により、グレイトーンは連続画素座標の関数と考えられる。
【００５９】
５．画像面において、共通のグレイトーンｇを有する点を通る曲線をレベル輪郭と呼ぶ。レベル輪郭は、好ましくはお互いに交差しないことに留意されたい。
【００６０】
６．点（ｘ、ｙ）における「勾配」は、最大値（｜Ｇ［ｘ、ｙ−１］−Ｇ［ｘ、ｙ＋１］｜、｜Ｇ［ｘ−１、ｙ］−Ｇ［ｘ＋１、ｙ］｜）と定義される。
【００６１】
７．高勾配を有するレベル輪郭の各部分は「エッジ状」である。
【００６２】
意味のあるレベル輪郭を導出する効率的な方法を記述するのがこの節の目的である。画像分析の結果は、レベル輪郭のセグメントのリストであり、各レベル輪郭のセグメントは画素位置のリストである。
輪郭に対するシードの導出
最初のステップにおいて、「勾配画像」は、グレイトーンが原画像の勾配に等しい画像として導出される。潜在シードは、勾配画像における極大値として定義される。潜在シードのリストが形成される。閾値以下の勾配を有する極大値はシードとして使用されない。シードのリストはグレイトーン、勾配、および画素座標を含む。このリストは勾配の大きさによりソートされる。図３は、シードの導出となる画像分析の例を示している。図３のウィンドウ１は原画像を示しており、図３のウィンドウ２は、勾配図を示している。図３のウィンドウ３は、潜在シードを示している。図３のウィンドウ４は、導出された輪郭を示している。
輪郭の導出
生成される最初のレベル輪郭は、最大勾配のシードを使用する。標準的な輪郭検索は、シードのグレイトーンに等しいグレイトーン閾値を使用して適用される。輪郭は、下記の停止条件の少なくとも一つが満たされるまで続く。
１）画像の境界に達する。
２）同じシードに再び到達する（閉じた輪郭）、または
３）次の輪郭点における勾配の絶対値が閾値未満になる。
【００６３】
輪郭が閉じていない限り、輪郭検索は、好ましくは双方向で行われる。導出された輪郭に１−２画素以上接近している潜在シードは機能停止／除去される。
【００６４】
すべての輪郭における画素の位置は、各輪郭に特徴的なグレイトーンの値を使用する直線内挿法に従って、シフトされる。結果は図４に示されている。
【００６５】
図４におけるウィンドウは、図３の画像の右上隅における輪郭を示している。図４の上方のウィンドウは副画素の正確性を有する輪郭を示しているが、図４の下方のウィンドウは、輪郭の整数画素位置を示している。
【００６６】
次の輪郭は、最大勾配を有する、機能停止されていないシードを使用して生成される。そして、新しい輪郭が、シードのリストが尽きるまで繰り返し生成される。図３のウィンドウ４は、導出された輪郭の例を示している。この例において、輪郭セクションの数は９である。示されたものより弱い輪郭は、シードの最低勾配に対して、より小さな値を選択することにより生成できる。
【００６７】
好ましくは、下記の手順と制約が適用される。
ａ）レベル輪郭は、シード点からスタートして描かれる。
ｂ）潜在シードは、勾配の大きさの極大値を有する画素である。
ｃ）レベル輪郭は、シードの勾配の減少する勾配の大きさの連続により導出される。最大勾配を有するシードからスタートする。
ｄ）レベル輪郭の位置は、初期の段階では、値ｇを超えるグレイトーンを有する整数画素の位置と、少なくとも一つの、値ｇ未満のグレイトーンを有する隣接する画素として見出される。内挿された画素の位置は、各（整数）画素の位置を、内挿法により導出された新しい位置へシフトすることにより得られる。各レベル輪郭における位置のリストは、リストにおける隣接するインデックスが、画像内の隣接する位置に対応するように順序付けられる。
ｅ）位置のインデックスが増加する方向に沿って移動するとき、ｇより高いグレイトーンを有する領域は、好ましくは右側にある。
【００６８】
第２実施例においては、いわゆるエッジ輪郭が生成される。この場合、上記の手順および制約は、ステップｄにおいて変更して適用してもよく、新しいステップｄを下記のように実行してもよい。
【００６９】
エッジ輪郭位置は、シード（第１画素）からスタートする画素の位置として見出され、現在の輪郭方向に直交する最大勾配を有する次の画素に向かって移動し、これらのステップを停止条件の一つが満たされるまで繰り返す。エッジ輪郭点の副画素の位置は、好ましくは、各輪郭位置の後ろ、および前のいくつかの画素の平均グレイトーンを計算することにより導出される。この平均グレイトーンは、内挿の基準として使用してもよい。
輪郭からのプリミティブとフィーチャの導出
プリミティブとは、曲線の特徴的な動きを伴う輪郭、またはそのセグメント上の点である（図２ａ参照）。発明の概要でリストされたプリミティブは、
ａ）直線のセグメント、
ｂ）相対的に大きな半径の円のセグメント、
ｃ）変曲点、
ｄ）曲率の最大数値の点（角部）、
ｅ）曲率の非常に小さな、および非常に大きな数値の部分を分離する点、
ｆ）輪郭により囲まれた小さな領域のエンティティ、である。
【００７０】
指定された特徴を有する二つまたは三つ以上のプリミティブのセットをフィーチャと呼び、図２ｂに示されている。
【００７１】
上記のように、有効なフィーチャに対してはいくつかの要求事項がある。
１）フィーチャは、好ましくは基準点を有するべきである。
２）フィーチャは、好ましくは画像においてユニークな方向を有するべきである。
３）フィーチャは、好ましくは一つまたは二つ以上の回転不変記述子を有するべきである。そのような記述子により記述される特性は、本質的特性と呼ばれる。
【００７２】
要求条件３）は厳格ではない。本質的特性がないと、整合検索は異なったものになる。この場合、トレーニング画像と認識画像の本質的フィーチャ間の比較はキャンセルされ、認識は、クラスタ検索のみに基づく。
【００７３】
対象物の画像が、一種類の少数のフィーチャのみを含むときは、付加的なフィーチャタイプが分析に含まれるべきである。
【００７４】
この節の目的は、プリミティブとフィーチャが、輪郭からどのように導出されるかを記述し、例示することである。
曲率対輪郭の長さ
プリミティブを生成するための良好なツールは、曲率対輪郭に沿う弧の長さを記述する機能である。輪郭上の点における接線方向を、角度θとし、ｓを、任意の基準点から測定された輪郭に沿う弧の長さとする。このとき、曲率はｄθ／ｄｓとなる。曲率関数κ（ｓ）＝ｄθ／ｄｓ対ｓは、プリミティブを定義するために有効である。このように、κ（ｓ）におけるゼロと、｜ｄκ／ｄｓ｜のかなり高い値は、変曲点である。κ（ｓ）の正のピークは、凹状の角部であり、κ（ｓ）の負のピークは、凸状の角部である（または、バックグラウンドと、フォアグランドの定義によっては反対となる）。輪郭の直線セクションは、ｓの範囲では、κ（ｓ）≒０である。半径Ｒを有する円のセクションは、ｓの範囲においてκ（ｓ）＝＋／−１／Ｒを有する。
【００７５】
画素分離化により、関数θ（ｓ）とκ（ｓ）は、微分を差で置換することにより導出できる。これが意味を持つためには、正確性を高めることと、効率的なノイズ削減に取り組むことが好ましい。輪郭の副画素定義は重要であり（図４参照）、画像がぼやけることも、カメラのノイズを削減するためには、しばしば必要である。プリミティブを導出する前に輪郭関数κ（ｓ）を平滑化することも有効である。
【００７６】
図５は、図３の画像の外輪郭の場合の、曲率関数κ（ｓ）の動きを示している。図６には、図５の曲線を使用して検出可能な直線セクションと角部に対するシンボルが示されている。κ（ｓ）におけるゼロと変曲点の間には、類似の対応関係がある（図示せず）。
【００７７】
プリミティブを生成するアルゴリズムは、曲率に対するある閾値を必要とする。例えば、直線は、ｓの範囲において、｜κ（ｓ）｜＜κaにより特徴付けられ、ここにおいてκaは曲率の閾値であり、範囲にわたる積分∫κｄｓもまた、∫κｄｓが接線の角度の変動を表すので、十分に小さく（角度の閾値未満）でなければならない。別の閾値κbは、正または負のピークが角部かただのノイズなのかを決定するのに適している。従って、角部の基準値は、［κ（ｓ）＞κbかつκ（ｓ）は極大値である］または、［κ（ｓ）＜−κbかつκ（ｓ）は極小値である］。
【００７８】
図５は、図３のウィンドウ４の輪郭の一つに沿う弧の長さｓ（画素単位）の関数として、曲率κ（ｓ）（ラジアン／画素単位）を示している。シンボルは対応関係を示すために使用される（図６参照）。図６は、図３に示す画像に対して見出された外輪郭を示している。特徴的なフィーチャに使用されるシンボルは、図５に与えられたものに対応する。
三次元的解釈におけるステップ
下記の（トレーニング工程）の項において、多数のトレーニング画像が生成されるトレーニング工程が記述される。下記の（認識工程）の項において、認識工程におけるステップの概論が記述される、つまり、トレーニング工程で導出されたフィーチャが、認識対象のフィーチャとどのように比較されるかの概論が記述される。（フィーチャとして直線セグメント対の場合の認識工程）の節で、フィーチャとして直線セグメント対の特別な場合の認識工程のステップが記述される。対象物とカメラの間の姿勢状態における距離パラメータρの特別な状態と、一台または二台以上のカメラの使用法が、（パラメータρの特別な状態、二台のカメラの使用法）の節で検討される。
トレーニング工程
トレーニング工程においては、対象物とカメラの間の姿勢状態が既知の場合の対象物の画像が多数生成される。これは、ＣＡＤシステムにおける構築またはカメラを使用して実行できる。
【００７９】
トレーニング幾何学的配置は図１６に示されており、対象物のフレームが、軸ｘ、ｙ、ｚにより与えられている。カメラの光軸は、対象物フレームの原点を通る。カメラの水平ｕ軸は、好ましくは、対象物フレームのｘ−ｙ平面に平行である（図１６参照）。トレーニングパラメータはρ、φ、θである。
【００８０】
対象物に対して、カメラの異なる姿勢状態（位置と方位）に対応する多数のトレーニング画像を生成する必要がある。下記の
１）認識中の同形変換、および
２）回転不変本質的記述子
の使用のため、トレーニングはわずか３の自由度のみに関連する。自由度のレベルは、対象物のフレームにおけるカメラのピンホールの球座標（ρ、φ、θ）として選択される。カメラの角度に関する姿勢状態は、対象物フレームの原点を通る光軸と、対象物フレームにおける指定された平面に平行な水平画像軸により特徴付けられる（「チルト−パン同形変換を使用する認識」の節参照）。トレーニングに使用されるカメラの姿勢状態はρ、φ、θ空間において適切に分布される。通常は、選択された姿勢状態は、この空間において規則的な格子を形成する。φとθの分離化ステップは、好ましくは２〜５度のオーダーである。ρの範囲と、異なるρの値の数は、状況に依存する。ここにおいては、トレーニングの姿勢状態のρ、φ、θ空間における分布については、詳細は触れない。単独のインデックスｉが、このインデックスと、対象物に関してのトレーニングカメラの対応する姿勢状態の間のよく知られた関係を仮定して、トレーニングの姿勢状態に使用される。
【００８１】
図１１のフローチャートは、トレーニングの処理を記述している。
認識工程
あるフィーチャタイプを考える。各トレーニング画像は、多数のフィーチャを含む。これらのフィーチャを、Пi、jとし、ここにおいてｉはトレーニング画像のインデックスであり、ｊは画像におけるフィーチャのインデックスである。ここで、πjを認識画像におけるフィーチャｊとする。各フィーチャは次の特性を有する。つまり、１）基準点Ｑ、２）角度γにより定義される基準方向、および３）一つまたは二つ以上の数値量から構成される本質的特性である。我々は、ベクトルΛにより、本質的特性を示す。γとΛの成分は、点Ｑを画像の中間点に移動するチルト−パン同形変換（「チルト−パン同形変換を使用する認識」の節を参照）から導出されなければならないということに留意されたい。
【００８２】
整合検索は、１）Λ（πj）とΛ（Пi、j）の比較と、２）潜在的認識対象物の姿勢状態を記述するパラメータ空間におけるクラスタ検索を含む。Λ（πj）がΛ（Пi、j）に十分類似していれば、本質的パラメータとの関連において整合が存在する。すべての本質的整合に対してｉ、Ｑ（Пi、j）、γ（Пi、j）、Ｑ（Пj）、およびγ（Пj）から導出される認識姿勢状態が算出され、クラスタ検索に使用される。ここで、トレーニング姿勢状態を定義するインデックスｉにより、認識姿勢状態の３自由度が与えられるが、他の３自由度は、適切な同形変換におけるチルト、パン、およびロールである。このステップの数学的詳細は、（チルト−パン同形変換を使用する認識）の節で記述される。
【００８３】
容認された各クラスタは、物理的対象物を表現していると考えられる。しかし、クラスタ検索の後に、推測される姿勢状態の間の三次元的オーバーラップのチェックを追加的に実行すべきである。トレーニング用の（ρ、φ、θ）構成空間は、必然的に分離化しなければならず、これほど単純な認識手順でも、分離化ステップの半分のオーダーのエラーを生じる。このエラーは、隣接するトレーニング画像からの結果の間に、内挿法を適用することで削減できる。
【００８４】
図１７と図１８は、トレーニング画像から導出される記述子のデータベースの構造と、認識画像から導出される記述子の構造を示している。ρi、φj、θkは、トレーニングパラメータの分離された値である。表中の各レコード（行）は、フィーチャから導出される。本例においては、各フィーチャは、三つの本質的記述子を有している。本質的記述子の数は、好ましくは３である。つまり、フィーチャの基準点の二つの座標と、同形変換後の基準方向である。データベースのレコードのいかなる非本質的記述子と、認識レコードのいかなる非本質的記述子も共に、認識フィーチャをトレーニングフィーチャと一致させるチルト−パン−ロール変換を定義する。そして、チルト−パン−ロールパラメータ空間における対応する点での増大化を実行できる。本質的認識記述子が、データベースの本質的記述子と十分に異なっている場合は、対応するフィーチャ対は考慮されない。この省略により、間違った対応関係によるノイズが削減される。
【００８５】
この認識工程における多数の重要な詳細が次の節の例で示される。
【００８６】
認識フローチャートは図１２に示されている。
フィーチャとして直線セグメント対の場合の認識工程
下記の例においては、認識に使用されるフィーチャは直線セクションの対であり、対象物は、三つの箱形状の要素から構成される「三つ組レンガ」である（図７参照）。図７は、姿勢状態決定の例において取り扱う三次元対象物を示している。
【００８７】
直線セクションは、好ましくはトレーニング写真の輪郭から導出される。各トレーニング画像における直線セクションのすべての対は、フィーチャと考えられる。直線対の交点は点Ｑであり、角度γは水平画像軸と、直線対の二等分線の方向との間の角度である。本質的記述子は、１）直線間の角度Ｖと、２）交点と直線セクションの終点との間の距離である。同形変換後、本質的フィーチャの両タイプが導出される。
【００８８】
直線セグメントの部分的な遮蔽は、誤った距離を生成するので、交点と終点の間の距離を、整合検索において直接使用すべきではない。
【００８９】
下記の検討は、角度に関する記述子のみに基づく検索に焦点を絞っている。
【００９０】
図８は、三つ組レンガ構造のレゴモデルのトレーニング写真を示している。
【００９１】
図９は、図８Ａの輪郭に沿う、弧の長さ（画素単位）の関数としてのラジアン／画素単位の曲率を示している。
【００９２】
図９から分かるように、直線セクションの位置を決めることは容易である。この例では、１２の直線セクションがある。直線の適切な対を導出すると、いくつかの対は省略される、つまり、直線間の角度が０または１８０度に近いものは省略される。このように、図８Ａにおいては、約９０対が考慮される。
【００９３】
図１０は、トレーニング画像と認識画像を組み合わせた図である。Ｐは焦点の中心である。トレーニング直線対ａｂは、ＱabがＰに移動するように同形変換される。これにより直線対ａ’ｂ’が生じる。量γabは、水平方向と二等分線ｍabの間の角度である。ａｂ直線対の本質的記述子は、ａ’とｂ’の間の角度Ｖabである。同様な定義が、認識画像の直線対ｃｄから導出される量についても成り立つ。角度Ｖ以外の本質的記述子は図示していない。
【００９４】
図１０は、トレーニング画像と認識画像を組み合わせた図である。例において、位置ＱabとＱcd、および二等分線ｍcdとｍabの間の角度γcdとγabは、トレーニング姿勢状態と認識姿勢状態の間のチルト−パン−ロール変換を定義する。特別なトレーニング画像の直線対に関連する認識画像の直線対はこのように、チルト−パン−ロールパラメータ空間の点を定義する。図１０の右上部分に示す直線対ｅｆは、ａｂ直線対とほぼ同じ角度記述子を有する。そして、アルゴリズムにおいては、この直線対の比較によって、パラメータ空間の「間違った」点が生成される。しかし、対応しないプリミティブがパラメータ空間において非常に分散された点を生成することは特徴的であり、一方、対応する直線対は、パラメータ空間においてクラスタを与える。他のトレーニング画像を、図１０の認識画像と整合させようとしても、整合する直線対のクラスタリングを得ることはない。
【００９５】
対象物の遮蔽と不十分な画像のセグメント化は、パラメータ空間における間違った点のバックグラウンドが、真の整合物のクラスタにより形成される信号と匹敵する程度にならない限り、認識工程に悪影響を与えることはないということは明白である。
【００９６】
間違った整合数が、クラスタ検索に混乱を与えるときは、上記の追加的な本質的記述子（直線セクションの終点と、交点の間の距離）を含む不規則性を設定することができる。そのような不規則性により、認識直線は部分的にしか見えなくなるが、認識直線が、トレーニング直線の範囲外に存在するセクションを有することを防止できる。
【００９７】
フィーチャπjを有する認識画像に対しては、アルゴリズムは下記のように動作する。
For each training image index i do
｛
Reset roll, tilt, pan parameter space;
For all valid indices j and J' compareΛ(Πi,j) and Λ(nj') do
｛
In case of intrinsic match
｛
Derive roll r, tilt t, pan p, from Q(Πi,j), γ(Πi,j), Q(nj'), γ(nj');
Update parameter space accordingly;
｝
｝
Test for clustering and store coordinates of clusters with sufficiently high
Density/population along with the index i of the training image.
｝
上記の「本質的整合」は、角度Ｖの類似性と、距離に関する不規則性の実現に基づいている。「パラメータ空間の更新」という用語は、パラメータ空間の関連する点における票を増加することである。
【００９８】
弱い透視法の場合は、単一の対象物は、いくつかのトレーニング画像を有するクラスタを生成する、つまり、同じφ値およびθ値を有するものを生成するが、ρ値は異なる。これらのρ値の一つのみが実際の対象物に対応するので、直線状の本質的記述子を使用する特別なアルゴリズムを使用すべきである。
【００９９】
推定されたトレーニングインデックスｉと、チルト−パン−ロール空間におけるクラスタ点を使用する逆変換は、（チルト−パン同形変換を使用する認識）の節で記述されている。この逆変換は、カメラに関しての認識対象物の姿勢状態（またはその逆）を定義するので、認識工程はこれで完了する。
パラメータρの空間状態、二台のカメラの使用
対象物とカメラの間の姿勢状態は、６個のパラメータで記述される。つまり、ａ）対応するトレーニング画像のρ、φ、θと、ｂ）認識姿勢状態とトレーニング姿勢状態の間の変換の（ロール、チルト、パン）である。弱い透視法の場合、プリミティブの無次元の記述子（例えば、角度）はρにはほとんど依存せず、直線記述子は、１／ρにほぼ比例する。従って、弱い、または適度な透視法に対しては、トレーニングを小数の異なるρ値に制限することが可能で、適切な内挿法を使用することができる。好ましくは、認識は二つの部分に分割される。最初の部分は、５個の角度パラメータの検出に集中し、二番目の部分は、内挿法を使用してρ値を導出する。
【０１００】
ρの最終値の正確性は、フィーチャの直線記述子の品質と、トレーニングに関連する、異なるρ値の数に依存する。内挿法を使用しても、ρの相対的な不確定性は、画像点間の距離を含む本質的記述子の相対的な不確定性よりも小さくはないことが好ましい。増大された正確性は、三次元三角測量が下記のように実行できるので、二台（または三台以上）のカメラを使用して得ることができる。
【０１０１】
カメラ１とカメラ２を考える（図１３）。カメラ１の分類と姿勢状態の推定結果を（ｉｃ1、ρ1、φ1、θ1、ｔ1、ｐ1、ｒ1）で特徴付け、ここにおいて、ｉｃ1は、対象物のタイプのインデックスで、残りのパラメータは姿勢状態を定義する。ρ1がまったく不確定であれば、残りの姿勢状態パラメータは、対象物基準点に対する直線Ｌ1を定義する（図１３参照）。同様に、カメラ２の推定（ｉｃ2、ρ2、φ2、θ2、ｔ2、ｐ2、ｒ2）は、直線Ｌ2を定義する。グローバルなカメラの姿勢状態が分かっているため、直線Ｌ1とＬ2は、グローバルフレームにおいて表現できる。ｉｃ1とｉｃ2とが等しい場合は、Ｌ1とＬ2は実質的に交差し、従って、推定の対は実際の対象物を表現していると思われる。更に、二つの以前は不確定であったパラメータρ1とρ2は、高い正確性で、擬似交点（図１３）によって決定できる。このように、姿勢状態の推定の正確性を高めるとともに、誤って解釈され、間違った信号−カメラの結果を回避できる。
【０１０２】
下記において、チルト−パン同形変換を使用する認識が、更に詳細に記述される。
チルト−パン同形変換を使用する認識
下記の表記を使用する。
【０１０３】
【数１】
【０１０４】
Ｒマトリックスは、ｔ（チルト）、ｐ（パン）、ｒ（ロール）を介する回転を記述する。マトリックスＫは、焦点距離ｆの透視法変換を記述する。我々は、下記のように定義される複合回転Ｒ（ｔ、ｐ、ｒ）を使用する。
【０１０５】
R(t,p,r)=Rz(r)Ry(p)Rx(t) (2)
ここにおいて、マトリックスの連続する掛け算は、右から左へ進む。Ｒ-1（ｔ、ｐ、ｒ）＝Ｒx（−ｔ）Ｒy（−ｐ）Ｒz（−ｒ）は、逆変換である。
【０１０６】
Ｒ（ｔ、ｐ、ｒ）の要素は、
【０１０７】
【数２】
【０１０８】
我々は、対象物フレームに関するカメラの回転と並進移動の組み合わせは、Ｒ（ｔ、ｐ、ｒ）｜Ｄで定義され、ここにおいて、Ｄは対象物フレームにおいて表現される並進移動ベクトルである。点が、対象物フレームにおいて座標（ｘo、ｙo、ｚo）で表現され、同じ点がカメラフレームにおいて座標（ｘc、ｙc、ｚc）で表現されるとすると、下記が得られる。
【０１０９】
【数３】
【０１１０】
対象物フレームにおいて表現されるカメラフレームの座標軸は、Ｒ（ｔ、ｐ、ｒ）の行ベクトルである。従って、カメラのｚ軸は、グローバルな方向、（ｓｉｎｐ、−ｃｏｓｐｓｉｎｔ、ｃｏｓｐｃｏｓｔ）を有することになる。
【０１１１】
ここで我々は、カメラのトレーニング姿勢状態を定義する。ピンホールの位置が、Ｄ＝（−ρｓｉｎφ、ρｃｏｓφｓｉｎθ、−ρｃｏｓφｓｉｎθ）によって与えられるとする。トレーニングカメラの角度（ｔ、ｐ、ｒ）を（θ、φ、π／２）と等しいように選択する。これは、光軸が、対象物の原点を通ることを意味する。ｒ＝π／２を選択したことは、カメラのｘc軸が、対象物フレームのｙｚ平面に平行であることを意味する。
【０１１２】
対象物とカメラの間の変換をＴCameraObjectとする。この変換は下記のように、二つに分割すべきである。
【０１１３】
【数４】
【０１１４】
ここにおいて、Ｏはゼロベクトルである。トレーニングカメラの姿勢状態は、１）対象物フレームの原点に向かうような方位を有する光軸と、２）対象物ｙｚ平面に平行なカメラのｘc軸により特徴付けられる。角度ｔ、ｐ、ｒは、トレーニングカメラの方位から認識方位への変換ＴCameraTrainingCameraを特徴付ける、チルト、パン、およびロール角である。トータルな変換ＴCameraObjectは、ρと、５個の角度ｒ、ｔ、ｐ、θ、およびφから導出できることに留意されたい。
【０１１５】
Ω（ρ、φ、θ、ｒ、ｐ、ｔ）を、（ρ、φ、θ、ｒ、ｐ、ｔ）により与えられる姿勢状態を有するカメラにより記録された画像とする。共通のピンホールの位置を有する同形の間の関係、つまり、Ω（ρ、φ、θ、ｒ、ｐ、ｔ）とΩ（ρ、φ、θ、０、０、０）の関係は、ここでは、下記の同次座標を使用して表現される二次元変換であり、ここで（ｕ、ｖ）と（ｕ’、ｖ’）は画像の座標である。
【０１１６】
【数５】
【０１１７】
画像座標の原点は、焦点位置としている。
【０１１８】
我々は、変換ＫＲ（ｔ、ｐ、０）Ｋ-1（ゼロロール角）に焦点を当てる。その理由は、ＫとＲは交換可能であるため、ロールは画像回転と考えられるからである。Ｈ（ｔ、ｐ）≡ＫＲ（ｔ、ｐ、０）Ｋ-1により定義される同形（２Ｄ）演算Ｈ（ｔ、ｐ）は、次のように記述できる。
【０１１９】
【数６】
【０１２０】
演算Ｈ（ｔ、ｐ）は、画像全体と同時に、画像の点に対しても可能であることに留意されたい。特別な点Ｑ＝（ｕQ、ｖQ）を原点（焦点）に移動する変換は、下記のパンとチルト角により与えられる。
【０１２１】
【数７】
【０１２２】
逆変換は、次の式で与えられる。
【０１２３】
【数８】
【０１２４】
関連画像において１）基準二次元の点Ｑと、２）ｕ軸との、方向角γを有するフィーチャを考える。このフィーチャは、トレーニング画像Ｑtrにおけるパラメータ（Ｑtr、γtr）と、認識画像Ｑrecにおける（Ｑrec、γrec）を有している。このように、ＱtrとＱrecは、対応する点であり、角γtrとγrecの方向もまた対応している。二つの画像を比較することは興味深い。
【０１２５】
【数９】
【０１２６】
これらの二つの画像は、お互いが、それぞれを回転したものであり、Ω’recに対する
Ω’trの回転角は、γrec−γtrとなる。両者は、ＱtrとＱrecに画像化されている、三次元の点Ｑを通る光軸に対する姿勢状態に対応する。トレーニング姿勢状態に対する認識姿勢状態の、チルト、パン、およびロール角、ｔ、ｐ、およびｒは次の式で与えられることを証明できる。
【０１２７】
【数１０】
【０１２８】
トレーニング画像の処理は下記のように行われる。つまり、画像はフィーチャ（単一固定点、固定点群、複合フィーチャ）に関して分析される。各フィーチャのＱrecとγrecの値と、他の種々の本質的数値記述子が導出され、データベースに格納される。速度最適化のために、マトリックスＲ-1（ｔo（Ｑtr）、ｐo（Ｑtr）、γtr）もまた算出されて格納される。
【０１２９】
認識の間、認識画像中の全フィーチャの本質的数値記述子は、データベース中の全類似フィーチャと比較される。整合が十分である場合は、回転ＴCameraTrainingCameraのパラメータｔ、ｐ、およびｒは（９）から導出される。ｔ、ｐ、ｒの結果の値と、整合トレーニング画像のパラメータρ、φ、θは共に、変換ＴCameraObjectを定義するので、三次元対象物の姿勢状態の６個のパラメータの推定値を形成する。六次元の姿勢状態におけるクラスタは、対応する姿勢状態で位置する実際の対象物により引き起こされたとされている。
【０１３０】
弱い、または適度な透視法の場合は、パラメータρの異なる値の数は、長さフィーチャが、近似的にρ-1に等しいρ依存性を有するので、非常に少なくするように選択できる。この場合、スケール不変の記述子に、五次元のｒ、ｐ、ｔ、φ、θ空間における関連する点を決定させることを推奨する。スケール不変の記述子のその後の分析により、関連するρ値が決定される。
【０１３１】
トータルな、対象物とカメラの間の変換は、次のように表わせる。
【０１３２】
【数１１】
【図面の簡単な説明】
【０１３３】
【図１】チルト−パン同形変換を示している。
【図２】プリミティブ、プリミティブ対、および角度を示している。
【図３】四つの異なるウィンドウにおける画像の例を示している。
【図４】図３の画像の上部右隅の輪郭を示している。図４の上部のウィンドウは、副画素の正確性を有する輪郭を示し、図４の下のウィンドウは輪郭の整数画素位置を示している。
【図５】図３のウィンドウ４の輪郭の一つに沿う弧の長さ（画素単位）の関数として、曲率κ（ｓ）（ラジアン／画素）を示している。シンボルは対応関係を示すために使用される（図６参照）。
【図６】図３に示す画像に対して見出された外部の輪郭を示している。特徴的フィーチャに使用されるシンボルは、図５に与えられたものに対応する。
【図７】姿勢状態決定のための例において処理される、三次元三つ組レンガを示している。
【図８】三つ組みレンガ構造のレゴモデルのトレーニング写真を示している。
【図９】図８Ａの輪郭に沿う弧の長さ（画素単位）の関数として、ラジアン／画素の曲率を示している。
【図１０】トレーニング画像と、認識画像の組み合わせ図を示している。
【図１１】トレーニングに対する処理を記述するフローチャートを示している。
【図１２】認識に対する処理を記述するフローチャートを示している。
【図１３】二台のカメラ操作を示している。
【図１４】カメラのピンホールモデルを示している。
【図１５】画像から導出されたグレイトーン俯瞰図を示している。
【図１６】トレーニング用幾何学的配置を示している。
【図１７】トレーニング画像から導出された記述子のデータベースの構造を示している。
【図１８】認識画像から導出された記述子の構造を示している。
【技術分野】
【０００１】
発明の分野
本発明は、コンピュータ視覚システムにおける対象物認識のための方法に関し、特に、本方法は、有界三次元対象物の分類と空間ローカライゼーションに関する。
【背景技術】
【０００２】
発明の背景
製造工程の自動化における障害（ボトルネック）は、部品および半製品を、加工、組立て、塗装、および梱包などのために自動システムに供給することにある。今日では、１）振動ボール（皿）、２）設備、および３）コンピュータ視覚システムの３種類のシステムが利用可能である。振動ボールは小寸法（約５ｃｍ未満）の部品に対してのみ適している。内部格納全体が設備に基づかなければならないので、設備は高価である。この二つのシステムは共に新しい部品が導入されると再設計および再製造しなければならない。これまで開発されてきたコンピュータ視覚システムには重大な欠陥があった。容認できないほどの処理速度のシステムがあったり、汎用性に欠けているシステムであったりしていた。今日利用できる、高速かつ汎用性のあるシステムでは、対象物を平坦な搬送ベルト上で分散して置く必要があり、対象物とカメラの距離は、対象物の高さに比べて遥かに大きくなくてはならない。この後者の制限は、使用される認識モデルが、カメラの三次元と二次元の間の変換における、透視法効果を含まないために、現在のシステムにとっては基本的である。このように、５ｃｍ〜１０ｃｍ以上の高さの部品に対しては、標準のコンピュータ視覚システムは、不便なほど遠隔に配置するカメラを必要とする。更に、標準コンピュータ視覚システムは、箱やパレットにランダムな方向に向けて積まれた部品を構造的に把握させるようにロボットを導くことはできない。
【０００３】
リサイクル部品が、リサイクル工場に運ばれてきて分類されるときにも、別の障害が存在する。消費者製品、特に自動車で使用されている部品の再構築は、環境および資源の面からの理由により将来、増加すると予測されている。再構築工程の前に、分類が必要となる。
【０００４】
現在における技術が不十分な分野の三番目の例は、構造化環境における自走ロボットの高速ナビゲーションである。カメラに基づくナビゲーションシステムは、構造物要素、固定家具などの認識を必要とする。これらのセグメントは有界三次元対象物と考えられる。
【０００５】
更に、本システムは自動車や建物の特定および分類のために衛星に適用して使用することができる。
【発明の開示】
【課題を解決するための手段】
【０００６】
発明の概要
本発明の良好な実施形態によれば、対象物の認識および／またはローカライゼーションは対象物の認識画像において特定されるプリミティブに基づいている。このように、第１の態様において、本発明は、デジタル画像において、輪郭、好ましくはレベル輪郭とプリミティブを決定する方法であって、
デジタル画像の勾配を生成し、
絶対勾配の一つまたは二つ以上の極大値を求め、
一つまたは二つ以上の極大値を、輪郭を生成するためのシード（種）として使用し、ここにおいて各シードに対する輪郭の生成は、デジタル画像内にあり、輪郭に属する場所を表現する点の順序リストを決定することを含み、
すべての場所に対して、輪郭の、好ましくはｄθ／ｄｓ、好ましくは画素単位で決定される曲率を決定し、
決定された曲率から、プリミティブを輪郭上の、または輪郭のセグメント上の特徴点として決定するステップを含む方法である。
【０００７】
トレーニング画像から導出されたプリミティブに基づいて、対象物の認識および／またはローカライゼーションは、好ましくは本発明の第２態様による方法により実行される。第２態様は、三次元対象物の分類および／またはローカライゼーションのような認識方法であり、一つまたは二つ以上の対象物は、前記対象物の二次元デジタル画像である認識画像を提供するように画像化され、本方法は、フィーチャ（特徴）の本質的および非本質的特性である数値記述子が多数のトレーニング画像に対して格納されたデータベースを利用し、本方法は、
画像に対して、プリミティブの予め定義されたセットであるフィーチャを特定し、
フィーチャの数値記述子を抽出し、ここにおいて数値記述子は、
画像中のフィーチャの位置および方位のようなフィーチャの非本質的特性と、
フィーチャに適用される同形変換後に導出されるフィーチャの本質的特性の二種類があり、
特性をデータベースに格納された特性と整合し、整合物が見つかれば、データベース内で整合した特性に対応する対象物を、認識すべき対象物の対象物に類似していると割り当てる認識方法である。
【０００８】
第３態様においては、本発明は、三次元対象物の位置決めおよび／または分類に関連して有効なデータベースの生成方法に関し、対象物は、対象物の二次元デジタル画像を提供するように画像化され、本方法は、対象物の二次元デジタル画像のプリミティブを決定するために本発明の第１および／または第２態様による方法を利用し、本方法は、
一つまたは二つ以上の対象物の多数のデジタル画像において、プリミティブの予め定義されたセットであるフィーチャを特定し、画像は、一つまたは二つ以上の対象物の異なるローカライゼーションを表わし、
フィーチャの数値記述子を、データベースから抽出して格納し、数値記述子は、
画像中のフィーチャの位置および方位である、フィーチャの非本質的特性と、
フィーチャに適用される同形変換後に導出されるフィーチャの本質的特性の二種類あることを含む方法である。
【０００９】
本発明は、このようにシステムが対象物を認識し、分類し、位置決めすることを可能にする。
【００１０】
本発明は、既に定義された輪郭近傍で特定される潜在シード点を削除するステップを更に含んでよい。これは、好ましくは、既存の輪郭に近すぎる輪郭の生成を避けるために行われる。
【００１１】
更に、輪郭の生成は、各点がシードの値に共通に割り当てられた値を有する、デジタル画像内の場所を表現する点リストを割り当てることを含んでよい。
【００１２】
更に、輪郭の生成は、各点において、最大勾配の方向に続く点を含む点の順序リストを決定することと定義してよい。
【００１３】
更に、輪郭の生成は、各点において、ある輪郭方向に直交すると検出された最大または最小勾配の方向に続く点のリストを割り当てることを含んでよい。どちらの勾配に続くかは選択された勾配の方向に従って決定してよい。
【００１４】
更に、輪郭の生成は、シードの値を超える、またはそれ未満の値を有する画素リスト、およびシードの値未満の、またはその値を超える値を有する一つまたは二つ以上の隣接する画素を割り当てることを含んでよい。
【００１５】
画素リストは、好ましくは所定の方法で、デジタル画像内を移動することにより確立される。確立されたリストは、リストの検索速度を増すと考えられる画素の順序リストであってよく、これは、最大値または最小値のようなある値は、例えば、リストの最上部と最下部にそれぞれ位置することがあるためである。しかし、他のソリューションを適用してもよい。
【００１６】
更に、輪郭は画素のリストに基づく内挿法により決定してもよい。これは、好ましくはより滑らかな輪郭を得るために実行される。
【００１７】
勾配図の作成は、隣接する画素に割り当てられた数値間の差を計算することにより勾配を決定して達成してもよい。このように勾配図が得られ、そこから更なる情報が抽出される。
【００１８】
勾配は、各要素が好ましくは第１画像内の特別な場所に対応し、特別な場所における第１画像の色調の勾配値を表わす数値であるアレイに格納してよい。
【００１９】
プリミティブ生成のために使用される曲率は、θを輪郭上の１点における接線方向とし、ｓを基準点から測定される弧の長さとしたときに、好ましくは、κ＝ｄθ／ｄｓとして確立される。
【００２０】
上記の第１、第２、および第３態様で記述したプリミティブは、好ましくは下記の特徴、
直線のセグメント、
相対的に大きな半径の円のセグメント、
変曲点、
曲率の最大数値の、好ましくは角部として割り当てられた点、
曲率の非常に小さな、および非常に大きな数値の部分を分離する点、および
輪郭により囲まれた小さな領域のエンティティ、
を一つまたは二つ以上備える。
【００２１】
上記の生成された輪郭に対して、下記のプリミティブ、
所定のレベルより高い曲率の絶対値の値を有する輪郭の領域またはその上の点である変曲点、
曲率の正のピークを有する輪郭の領域またはその上の点である凹状角部、
曲率の負のピークを有する輪郭の領域またはその上の点である凸状角部、
ゼロの曲率を有する輪郭のセグメントである直線セグメント、および／または
一定曲率を有する輪郭のセグメントである円形セグメント、
の一つまたは二つ以上が検索される。
【００２２】
認識方法に関する本発明の第２態様によれば、整合付けステップは更に、認識画像を、データベースに格納されたトレーニング画像と整合することを含み、整合付けの方法は、各トレーニング画像に対して、
トレーニング画像のフィーチャと同一の認識画像のフィーチャをもたらす変換のロール、チルト、およびパンの値を決定し、
変換により決定されたロール、チルト、およびパンの値により定義されるパラメータ空間におけるクラスタを特定し、および
予め定義された強度を有するクラスタを、対象物のタイプおよびローカライゼーションに対応するものとして特定するステップを備えてもよい。
【００２３】
データベースは各画像に対して、それぞれがその本質的特性およびその非本質的特性を有するフィーチャを表わす一つまたは二つ以上のレコードを備えてよい。
【００２４】
更に、整合付けは、
ロール、チルト、およびパンパラメータ空間をリセットし、
認識画像における各フィーチャに対して、認識画像の特性をデータベースに格納されている特性と整合付け、
整合する場合、データベースから、および認識画像からの非本質的特性に基づいてロール、チルト、およびパンを決定し、
パラメータ空間を更新し、
クラスタリングをテストし、トレーニング画像のインデックスを有する十分に高い密度／母集団のクラスタの座標を格納するステップを含み、
このステップを認識画像のすべてのフィーチャの整合付けが終了するまで繰り返すことを含んでよい。
【００２５】
ロール、チルト、およびパンの決定は、好ましくは、データベース内の本質的特性と比較して類似のまたは同一の本質的特性を有するフィーチャに対してのみ行われる。このようにして、大量の計算時間が節約される。
【００２６】
更に、整合付けは、認識画像の本質的記述子と、データベースに格納されている本質的記述子と比較し、それにより整合するフィーチャを選択することを含んでよい。
【００２７】
第３態様で記述したデータベースの生成は、下記に記述されるステップとフィーチャによって更に生成されてもよい。
【００２８】
好ましくは、非本質的特性は基準点と基準方向を備える。一方、本質的特性は、好ましくはフィーチャの数値量を備える。
【００２９】
対象物は少なくとも二台の撮像装置を使用する方法で画像化されてもよく、それにより対象物の少なくとも二つの認識画像を生成し、整合付けの方法が各認識画像に適用され、各認識画像に対して見出された整合物が比較されてもよい。
【００３０】
更に、二台の撮像装置を使用する方法は、
各撮像装置に対して、対象物の三次元基準点に対する推定値を提供し、
各撮像装置に対して、撮像装置のピンホールから推定された基準点までの直線を計算し、
少なくとも二つまたは三つ以上の直線が提供された場合は、
二つまたは三つ以上の直線が三次元で実質的に交差しない場合は、推定値を破棄し、
二つまたは三つ以上の直線が実質的に交差する場合は、
各撮像装置から得られた直線の間の擬似交点に基づいて、基準点のグローバルポジションを推定するステップを含んでよい。
【００３１】
以下、本発明と、特にその良好な実施形態を、添付図と関連してより詳細に呈示する。
【発明を実施するための最良の形態】
【００３２】
発明の詳細な説明
ここで記載される発明は、発明の背景の節で記載したすべての状況を対象としている。焦点は下記の特性、
トレーニング情報の簡単な生成、
トレーニング情報の合理的な少量、
透視法効果の正確な処理、
対象物の形状および見た目に関しての汎用性、例えば鋭い三次元エッジやランドマークは不要、
画像間の大規模な二次元整合または三次元再構築なしの高速認識、に置かれる。
機能
コンピュータ視覚システムは、別個のクラスに属する有界三次元対象物を分類および／または位置決めするために使用される。システムは一つまたは二つ以上のカメラで構成され、その画像は、１）三次元対象物のクラスと、２）その空間的位置および方位（姿勢状態）に関して解釈される。その機能は、他の対象物による可能性のある部分的遮蔽と、画像の効果的でないセグメント化からはある程度独立している。対象物は特徴的な装飾や鋭いエッジを有する必要はない。この機能は、カメラの位置と、対象物とカメラの間の距離に対する対象物のサイズには依存しない。画像の解釈は速度が最適化され、これはデジタルカメラの使用、画像データの迅速な電子的伝送、および最適化コードを意味する。更に、本システムで使用されるカメラは必ずしも、光学カメラである必要はなく、カメラは、熱カメラのような他の種類であってもよい。
定義
図１４に示すカメラのピンホールモデル：カメラのフレーム（座標系）は軸ｕ、ｖ、ｗにより定義される。焦点は座標（ｕ、ｖ、ｗ）＝（０、０、ｆ）を有し、ｆはカメラの焦点距離である。好ましくは、ｕ、ｖ、ｆは画素単位であるとよい。実際のカメラは負のｆ値を有する。適切な同形変換はチルト軸（ｕ軸に平行）とパン軸（ｖ軸に平行）の周りの連続的な二回転により記述できる。
【００３３】
カメラはピンホール、つまり、透視法三次元−二次元変換の中心と画像面を有する撮像装置である。光軸はピンホールを通り直線であり、実質的に画像面に直交している。カメラの光軸の画像は、焦点と呼ばれ、図１４に示されている。画像は二つの軸、垂直（ｖ）軸と水平（ｕ）軸を有する。
【００３４】
好ましくは、対象物の見た目の下記の二次元特性、
１）外部輪郭（常に存在する）、
２）外部輪郭内に現れる輪郭、
３）輪郭の内部に現れる対象物の鋭い三次元エッジの画像、および
４）装飾物における二次元エッジ、が考慮される。
【００３５】
これらの特性は、画像では（一次元の）直線または曲線として現れる。下記においては、これらのフィーチャを、特徴曲線と呼ぶ。特徴曲線の特別なフィーチャをプリミティブと呼ぶ。プリミティブは点状（変曲点、最大曲率点など）または一次元（直線セクション、一定曲率のセクションなど）であってよい。プリミティブの特別な対、三つの組合わせ、またはそれ以上の数のセットをフィーチャと呼ぶ。フィーチャの最も有効なタイプはプリミティブの対である。これらのうちのいくつかを図２ａと図２ｂに示す。
【００３６】
単一で特別な対象物で、かつ既知の対象物−カメラ間の姿勢状態を有し、特別なカメラで撮影した画像をトレーニング図と呼ぶ。システムにより解釈される場面の画像を認識図と呼ぶ。
【００３７】
数値記述子はフィーチャの本質的特性と非本質的特性を記述する。本質的特性はフィーチャの回転不変記述子により記述され、非本質的特性は画像におけるフィーチャの位置と回転により記述される。
【００３８】
好ましくは、フィーチャは三つの非本質的記述子を有し、それはフィーチャの基準点の二つの座標と同形変換後の基準方向である。
【００３９】
レベル輪郭：好ましくは、レベル輪郭は、一定グレイトーン値ｇに対応する画像座標の順序リストである。座標は、一つはｇより大きいグレイトーンを有し、他方はｇより小さいグレイトーンを有する二つの画素間の線形内挿法により得られる。
【００４０】
エッジ輪郭：好ましくは、エッジ輪郭は、デジタル画像における場所を表わし、輪郭に属している点の順序リストである。好ましくは、点は、現在の運動方向に直交する勾配を計算し、最大勾配の方向に移動させることにより前点から得られる。輪郭点の副画素座標は、各輪郭点からある距離後ろ、または前に離れた（整数）画素の場所にわたる平均グレイトーンを計算することにより得られる。この平均グレイトーンは、考慮している点のシフトされた場所という結果になる内挿法のための基準として使用される。
【００４１】
図／画像または図／画像のセクションには二次元変換を実行できる。ここで考慮されている変換は、カメラの、そのピンホールの周りの仮想回転により特徴付けられる。これらの変換は、同形変換として示される。同形変換は、特別な軸の周りの連続するカメラの回転により指定できる。共通の記述法では、チルトは水平画像軸に平行な軸の周りの回転であり、パンは垂直画像軸に平行な軸の周りの回転であり、ロールは光軸の周りの回転である。これらの回転を図１４に示す。Ωを画像または画像セクションとする。変換された画像または画像セクションは、シンボルΩ’＝Ｈ（Ω）を有し、ここでＨは同形変換である。画像における任意の点Ｑは、点Ｑが焦点に変換されるという特性を有する同形変換のクラスを定義する。そのような変換の後の画像または画像セクションは、シンボルＨQ（Ω）を有する。この変換ＨQのクラスの一つのメンバーは、ロールがなく、パンが続くチルトにより特徴付けられる。この変換は、チルト・パン変換ＨQ、tpと呼ぶ。このクラスには他の多くのメンバーが存在する。好ましくは、それらのメンバーが良好に定義されたアルゴリズムを有する。
【００４２】
図１にチルト−パン同形変換を示す。変換前の原画像は上の図である。下の図はチルト−パン同形変換後の画像であり、ドームの頂点は焦点に移動されている。
【００４３】
好ましくは、同じクラスの対象物は幾何学形状に関して一様であり、これが装飾物に関してもある程度当てはまり、対象物の遮蔽されていない部分は、十分な特徴曲線を有する。特徴曲線を最善の状態で検出するためには、この場面の照明がかなり一定していることが好ましい。
方法の概説
認識は多数のトレーニング図の分析に基づく。これらのトレーニング図は、実際の対象物に向けられているカメラにより記録されるか、または対象物のＣＡＤ表現を使用して構築される。特徴曲線はトレーニング図から導出され、曲線のプリミティブが検出される。フィーチャの本質的および非本質的記述子は、図の対象物クラスと姿勢状態についてのデータと共にデータベースに格納される。上記のトレーニングに関する動作はオフラインで行われる。
【００４４】
認識の間、類似の画像分析が行われる。認識の残りの部分は二つの段階で行われる。第１に、認識図の本質的記述子はデータベースの記述子と比較される。第２に、最も整合するフィーチャの中から、同じ姿勢状態の同じ対象物クラスを示すという意味で、どのフィーチャが相互に一致しているかが調べられる。
トレーニング図数の削減方法
剛体は６の自由度を有するため、図の多様性は非常に大きい。トレーニング量を削減するために二つの方法が採用される。第１に、非本質的記述子は、チルト−パンにより同形に変換された画像から導出される。あるフィーチャに対して使用される変換はＨQ、tpであり、ここでＱは実際のフィーチャの基準点である。第２に、整合検索に使用される本質的記述子は、カメラのロールと等価である画像の回転に対して不変である。上記の二つの方法は、トレーニング図の量は、剛体が６の自由度を有するという事実にも拘わらず、３の自由度に制限できるということを示唆している。好ましくは、各フィーチャに対してトレーニングデータベースは下記の、
ａ）チルト−パンによる同形変換とロール操作に対して不変な記述子、
ｂ）画像軸に関する角度の二次元方位に対する回転記述子、
ｃ）チルト−パン同形変換に関連するチルトとパンの角度、を含む。
【００４５】
項目ａ）は、基準点をフィーチャに割り当てることができることを必要とする。
【００４６】
項目ｂ）は、基準方向をフィーチャに割り当てることができることを必要とする。
【００４７】
トレーニングセッションでは、基準方向と基準点はユーザーにより手動で割り当てられる。
【００４８】
トレーニングに関連する３の自由度は、対象物フレームにおけるピンホールの球座標（ρ、φ、θ）として選択できる（図１６参照）。トレーニング中、光軸は対象物フレームの原点を通り、カメラのロール角はゼロである。このように、ρ、φ、θは、対象物フレームの原点およびピンホールからのベクトルの、それぞれ長さ、方位角、および水平角である。トレーニングステップでは、ユーザーが対象物フレームの原点を割り当てる。ρ、φ、およびθの間隔とステップサイズは、アプリケーションによってはトレーニングの必要がある。適度な、または弱い透視法に場合は、フィーチャの直線寸法が近似的にρに反比例するため、少数のρの数値のみが、トレーニングの必要がある。
認識：変換、整合検索、逆変換、およびクラスタ分析
認識の第１ステップにおいては、認識図の分析され、変換されたフィーチャの記述子が導出され、適切な数の記述子間の最良整合が、認識図とデータベース（レーニング図数の削減方法）の節における（項目ａ））の認識図から見出される。第２ステップにおいては、認識図とデータベースの整合レコードに属する、（トレーニング図数の削減方法）の節の項目ｂ）とｃ）を考慮する。これらのデータは適切な逆変換に使用され、それにより、実際のフィーチャにより示唆される完全な三次元姿勢状態を計算する。六次元構成空間（各対象物クラスに対して一つの空間）における候補（票）のクラスタは、実際の対象物として解釈される。このクラスタ分析は、間違ったフィーチャ、つまり異なる対象物に属するプリミティブの検出された組み合わせを除去するためには重要である。
特徴曲線のプリミティブとフィーチャ
認識のための良好なプリミティブの例
１）直線のセグメント
２）相対的に大きな半径の円のセグメント
３）変曲点
４）最大曲率点
５）非常に低い曲率と非常に高い曲率の部分を分離する点
６）小さな領域を囲む曲線の場合：この領域の二次元的重心
図２は、上記の（特徴曲線のプリミティブとフィーチャ）節で記述したプリミティブを示す。図２ａはプリミティブの例を示し、図２ｂはプリミティブの対と、それらの基準点（細い円）と、それらの基準方向（矢印）を示している。図２ｃは角度を示し、ここで角度ｒは回転により不変であり、角度ｄは回転を記述する記述子である。
【００４９】
このシステムで使用されるプリミティブのセットは、好ましくは、下記の特性、
−基準点、
−基準方向（１８０度の不明性なしで）、
−一つまたは二つ以上の整合検索に適した回転不変記述子、を有するべきである。
【００５０】
これらの条件を満たす二つまたは三つ以上の任意の組み合わせを採用することができる。図２ｂは基準点と基準方向を含むプリミティブの適切な対の例を示している。フィーチャに、直線または円のセグメントが関連する場合は、フィーチャの部分的遮蔽を可能にする認識は、好ましくは適切な不規則性を含むべきである。
【００５１】
プリミティブの対の回転不変記述子は、例えば、点状のプリミティブ間の距離、直線部分の間の角度、接線と点状のプリミティブを結ぶ線の間の角度などである。図２ｃは回転不変角度と、（トレーニング図数の削減方法）の節の（項目ｂ）の回転記述角の例を示している。
二台または三台以上のカメラを使用する利点
単一カメラ適用例における姿勢状態の不確定要素はρ、つまり、ピンホールと対象物の基準点との間の距離である。エラーは、画素の分離化、カメラノイズ、および変動する対象物寸法により起こる。不確定性は、下記のように二台または三台以上のカメラからの検出結果の相関を取ることで大幅に減少できる。各カメラは対象物の三次元基準点に対する推定値を与える。不確定性ρを伴って、各カメラは、基準点の場所に対する高い確率を有する三次元の線を定義する。そのような線の間の擬似交点は対象物の基準点の最も可能性ある場所である。これは図１３に示されている。
【００５２】
この方法は、ステレオビジョンに関連する。従来のステレオビジョンには、短すぎるベースライン（ピンホールの間の距離）は不正確な深度の決定という結果になり、大きすぎるベースライン（そして、光軸間の大きな角）は対応する点／フィーチャの特定を困難にするため、根本的な制限がある。マルチビューデータベースのフィーチャと整合しているフィーチャを使用する、現在導入されている方法においては、画像における対応する点を見つける必要がない。従って、本発明のマルチカメラバージョンにより達成される深度の推定は、通常のステレオビジョンを使用するよりもより正確である。
【００５３】
二台以上のカメラを使用して得られる他の利点は、間違った分類と間違った姿勢状態の推定値の除去である。この除去は、弱い透視法により見たときの対称面を有する対象物の場合は、特に重要である。
トレーニング量と認識回数の推定
典型的な適用例においては、φ−θ空間におけるステップサイズは４度である。これは、制限のない角度範囲に対しては、ρの値当り約３，０００画像を意味する。ほとんどの適用例は３から４個の異なるρ値のみを必要とし、総計で約１０，０００画像を与える。各トレーニング図におけるプリミティブの一般的なセット数は５０であり、各データベースレコードにおける４バイトの浮動小数点エンティティの一般的な数は８である。そして、データベースの総量は一つの対象物クラスに対して１６メガバイトのオーダーである。このデータベースにおける速度最適化整合検索は、１ＧＨｚのＣＰＵ上では対象物クラス当り１秒に満たない時間だけ続くと予測される。対象物の姿勢状態が（ρ、φ、θ）−空間のより小さな部分に限られることが予め知られている適用例においては、上記の数はそれなりに削減することができる。
【００５４】
ここで記述される実施形態は、コンピュータ視覚システムにおいて使用される好ましいステップを含む。本システムは、一台または二台以上のコンピュータ視覚カメラの前にランダムに置かれた三次元対象物を分類および位置決めすることができる。本システムの発明の概要で述べた通り、好ましくは、認識は下記に基づく。
−トレーニング画像および認識画像における特徴曲線の決定
−フィーチャ記述子の導出（プリミティブおよびプリミティブ対）
−三次元解釈で使用される認識工程
使用される特徴曲線は、グレイトーン画像におけるエッジである。この記述において、「エッジ」はレベル輪郭（一定グレイトーンの曲線）またはエッジ輪郭（高勾配の曲線）として定義される。レベル輪郭を導出する方法は、（グレイトーン画像からのレベル輪郭の導出）の節で記述し、例示している。副画素により定義された輪郭を使用することにより、（輪郭からのプリミティブとフィーチャの導出）の節で概要を示したように、信頼できる特徴的な輪郭プリミティブ（直線のセグメント、変曲点、角部など）を導出できる。トレーニング画像および認識画像から導出されたプリミティブを使用する三次元の解釈は、（三次元解釈のステップ）の節で記述し、例示している。
グレイトーン画像からの輪郭の導出
この節では、レベル輪郭およびエッジ輪郭を導く画像分析を記述する。レベル輪郭の定義：図１５ａの右上の部分におけるフレームのグレイトーンの俯瞰図が図１５ｂに示されている。好ましくは、レベル輪郭は一定グレイトーン値ｇに対応する画像座標の順序リストである。座標は、一つはｇを超えるグレイトーンを有し、他方はｇ未満のグレイトーンを有する二つの画素間における直線内挿法により得られる。いくつかの定義の説明を下記に示す。
【００５５】
１．グレイトーン画像はグレイトーンの二次元アレイＧ［ｘ、ｙ］から構成される。各アレイメンバーは画素である。
【００５６】
２．各画素は画像面において整数座標を有する。
【００５７】
３．俯瞰図との類似において、グレイトーンは、グレイトーン俯瞰図における高さと考えられ、これは図１５ａと図１５ｂに示されている。
【００５８】
４．適切な内挿法により、グレイトーンは連続画素座標の関数と考えられる。
【００５９】
５．画像面において、共通のグレイトーンｇを有する点を通る曲線をレベル輪郭と呼ぶ。レベル輪郭は、好ましくはお互いに交差しないことに留意されたい。
【００６０】
６．点（ｘ、ｙ）における「勾配」は、最大値（｜Ｇ［ｘ、ｙ−１］−Ｇ［ｘ、ｙ＋１］｜、｜Ｇ［ｘ−１、ｙ］−Ｇ［ｘ＋１、ｙ］｜）と定義される。
【００６１】
７．高勾配を有するレベル輪郭の各部分は「エッジ状」である。
【００６２】
意味のあるレベル輪郭を導出する効率的な方法を記述するのがこの節の目的である。画像分析の結果は、レベル輪郭のセグメントのリストであり、各レベル輪郭のセグメントは画素位置のリストである。
輪郭に対するシードの導出
最初のステップにおいて、「勾配画像」は、グレイトーンが原画像の勾配に等しい画像として導出される。潜在シードは、勾配画像における極大値として定義される。潜在シードのリストが形成される。閾値以下の勾配を有する極大値はシードとして使用されない。シードのリストはグレイトーン、勾配、および画素座標を含む。このリストは勾配の大きさによりソートされる。図３は、シードの導出となる画像分析の例を示している。図３のウィンドウ１は原画像を示しており、図３のウィンドウ２は、勾配図を示している。図３のウィンドウ３は、潜在シードを示している。図３のウィンドウ４は、導出された輪郭を示している。
輪郭の導出
生成される最初のレベル輪郭は、最大勾配のシードを使用する。標準的な輪郭検索は、シードのグレイトーンに等しいグレイトーン閾値を使用して適用される。輪郭は、下記の停止条件の少なくとも一つが満たされるまで続く。
１）画像の境界に達する。
２）同じシードに再び到達する（閉じた輪郭）、または
３）次の輪郭点における勾配の絶対値が閾値未満になる。
【００６３】
輪郭が閉じていない限り、輪郭検索は、好ましくは双方向で行われる。導出された輪郭に１−２画素以上接近している潜在シードは機能停止／除去される。
【００６４】
すべての輪郭における画素の位置は、各輪郭に特徴的なグレイトーンの値を使用する直線内挿法に従って、シフトされる。結果は図４に示されている。
【００６５】
図４におけるウィンドウは、図３の画像の右上隅における輪郭を示している。図４の上方のウィンドウは副画素の正確性を有する輪郭を示しているが、図４の下方のウィンドウは、輪郭の整数画素位置を示している。
【００６６】
次の輪郭は、最大勾配を有する、機能停止されていないシードを使用して生成される。そして、新しい輪郭が、シードのリストが尽きるまで繰り返し生成される。図３のウィンドウ４は、導出された輪郭の例を示している。この例において、輪郭セクションの数は９である。示されたものより弱い輪郭は、シードの最低勾配に対して、より小さな値を選択することにより生成できる。
【００６７】
好ましくは、下記の手順と制約が適用される。
ａ）レベル輪郭は、シード点からスタートして描かれる。
ｂ）潜在シードは、勾配の大きさの極大値を有する画素である。
ｃ）レベル輪郭は、シードの勾配の減少する勾配の大きさの連続により導出される。最大勾配を有するシードからスタートする。
ｄ）レベル輪郭の位置は、初期の段階では、値ｇを超えるグレイトーンを有する整数画素の位置と、少なくとも一つの、値ｇ未満のグレイトーンを有する隣接する画素として見出される。内挿された画素の位置は、各（整数）画素の位置を、内挿法により導出された新しい位置へシフトすることにより得られる。各レベル輪郭における位置のリストは、リストにおける隣接するインデックスが、画像内の隣接する位置に対応するように順序付けられる。
ｅ）位置のインデックスが増加する方向に沿って移動するとき、ｇより高いグレイトーンを有する領域は、好ましくは右側にある。
【００６８】
第２実施例においては、いわゆるエッジ輪郭が生成される。この場合、上記の手順および制約は、ステップｄにおいて変更して適用してもよく、新しいステップｄを下記のように実行してもよい。
【００６９】
エッジ輪郭位置は、シード（第１画素）からスタートする画素の位置として見出され、現在の輪郭方向に直交する最大勾配を有する次の画素に向かって移動し、これらのステップを停止条件の一つが満たされるまで繰り返す。エッジ輪郭点の副画素の位置は、好ましくは、各輪郭位置の後ろ、および前のいくつかの画素の平均グレイトーンを計算することにより導出される。この平均グレイトーンは、内挿の基準として使用してもよい。
輪郭からのプリミティブとフィーチャの導出
プリミティブとは、曲線の特徴的な動きを伴う輪郭、またはそのセグメント上の点である（図２ａ参照）。発明の概要でリストされたプリミティブは、
ａ）直線のセグメント、
ｂ）相対的に大きな半径の円のセグメント、
ｃ）変曲点、
ｄ）曲率の最大数値の点（角部）、
ｅ）曲率の非常に小さな、および非常に大きな数値の部分を分離する点、
ｆ）輪郭により囲まれた小さな領域のエンティティ、である。
【００７０】
指定された特徴を有する二つまたは三つ以上のプリミティブのセットをフィーチャと呼び、図２ｂに示されている。
【００７１】
上記のように、有効なフィーチャに対してはいくつかの要求事項がある。
１）フィーチャは、好ましくは基準点を有するべきである。
２）フィーチャは、好ましくは画像においてユニークな方向を有するべきである。
３）フィーチャは、好ましくは一つまたは二つ以上の回転不変記述子を有するべきである。そのような記述子により記述される特性は、本質的特性と呼ばれる。
【００７２】
要求条件３）は厳格ではない。本質的特性がないと、整合検索は異なったものになる。この場合、トレーニング画像と認識画像の本質的フィーチャ間の比較はキャンセルされ、認識は、クラスタ検索のみに基づく。
【００７３】
対象物の画像が、一種類の少数のフィーチャのみを含むときは、付加的なフィーチャタイプが分析に含まれるべきである。
【００７４】
この節の目的は、プリミティブとフィーチャが、輪郭からどのように導出されるかを記述し、例示することである。
曲率対輪郭の長さ
プリミティブを生成するための良好なツールは、曲率対輪郭に沿う弧の長さを記述する機能である。輪郭上の点における接線方向を、角度θとし、ｓを、任意の基準点から測定された輪郭に沿う弧の長さとする。このとき、曲率はｄθ／ｄｓとなる。曲率関数κ（ｓ）＝ｄθ／ｄｓ対ｓは、プリミティブを定義するために有効である。このように、κ（ｓ）におけるゼロと、｜ｄκ／ｄｓ｜のかなり高い値は、変曲点である。κ（ｓ）の正のピークは、凹状の角部であり、κ（ｓ）の負のピークは、凸状の角部である（または、バックグラウンドと、フォアグランドの定義によっては反対となる）。輪郭の直線セクションは、ｓの範囲では、κ（ｓ）≒０である。半径Ｒを有する円のセクションは、ｓの範囲においてκ（ｓ）＝＋／−１／Ｒを有する。
【００７５】
画素分離化により、関数θ（ｓ）とκ（ｓ）は、微分を差で置換することにより導出できる。これが意味を持つためには、正確性を高めることと、効率的なノイズ削減に取り組むことが好ましい。輪郭の副画素定義は重要であり（図４参照）、画像がぼやけることも、カメラのノイズを削減するためには、しばしば必要である。プリミティブを導出する前に輪郭関数κ（ｓ）を平滑化することも有効である。
【００７６】
図５は、図３の画像の外輪郭の場合の、曲率関数κ（ｓ）の動きを示している。図６には、図５の曲線を使用して検出可能な直線セクションと角部に対するシンボルが示されている。κ（ｓ）におけるゼロと変曲点の間には、類似の対応関係がある（図示せず）。
【００７７】
プリミティブを生成するアルゴリズムは、曲率に対するある閾値を必要とする。例えば、直線は、ｓの範囲において、｜κ（ｓ）｜＜κaにより特徴付けられ、ここにおいてκaは曲率の閾値であり、範囲にわたる積分∫κｄｓもまた、∫κｄｓが接線の角度の変動を表すので、十分に小さく（角度の閾値未満）でなければならない。別の閾値κbは、正または負のピークが角部かただのノイズなのかを決定するのに適している。従って、角部の基準値は、［κ（ｓ）＞κbかつκ（ｓ）は極大値である］または、［κ（ｓ）＜−κbかつκ（ｓ）は極小値である］。
【００７８】
図５は、図３のウィンドウ４の輪郭の一つに沿う弧の長さｓ（画素単位）の関数として、曲率κ（ｓ）（ラジアン／画素単位）を示している。シンボルは対応関係を示すために使用される（図６参照）。図６は、図３に示す画像に対して見出された外輪郭を示している。特徴的なフィーチャに使用されるシンボルは、図５に与えられたものに対応する。
三次元的解釈におけるステップ
下記の（トレーニング工程）の項において、多数のトレーニング画像が生成されるトレーニング工程が記述される。下記の（認識工程）の項において、認識工程におけるステップの概論が記述される、つまり、トレーニング工程で導出されたフィーチャが、認識対象のフィーチャとどのように比較されるかの概論が記述される。（フィーチャとして直線セグメント対の場合の認識工程）の節で、フィーチャとして直線セグメント対の特別な場合の認識工程のステップが記述される。対象物とカメラの間の姿勢状態における距離パラメータρの特別な状態と、一台または二台以上のカメラの使用法が、（パラメータρの特別な状態、二台のカメラの使用法）の節で検討される。
トレーニング工程
トレーニング工程においては、対象物とカメラの間の姿勢状態が既知の場合の対象物の画像が多数生成される。これは、ＣＡＤシステムにおける構築またはカメラを使用して実行できる。
【００７９】
トレーニング幾何学的配置は図１６に示されており、対象物のフレームが、軸ｘ、ｙ、ｚにより与えられている。カメラの光軸は、対象物フレームの原点を通る。カメラの水平ｕ軸は、好ましくは、対象物フレームのｘ−ｙ平面に平行である（図１６参照）。トレーニングパラメータはρ、φ、θである。
【００８０】
対象物に対して、カメラの異なる姿勢状態（位置と方位）に対応する多数のトレーニング画像を生成する必要がある。下記の
１）認識中の同形変換、および
２）回転不変本質的記述子
の使用のため、トレーニングはわずか３の自由度のみに関連する。自由度のレベルは、対象物のフレームにおけるカメラのピンホールの球座標（ρ、φ、θ）として選択される。カメラの角度に関する姿勢状態は、対象物フレームの原点を通る光軸と、対象物フレームにおける指定された平面に平行な水平画像軸により特徴付けられる（「チルト−パン同形変換を使用する認識」の節参照）。トレーニングに使用されるカメラの姿勢状態はρ、φ、θ空間において適切に分布される。通常は、選択された姿勢状態は、この空間において規則的な格子を形成する。φとθの分離化ステップは、好ましくは２〜５度のオーダーである。ρの範囲と、異なるρの値の数は、状況に依存する。ここにおいては、トレーニングの姿勢状態のρ、φ、θ空間における分布については、詳細は触れない。単独のインデックスｉが、このインデックスと、対象物に関してのトレーニングカメラの対応する姿勢状態の間のよく知られた関係を仮定して、トレーニングの姿勢状態に使用される。
【００８１】
図１１のフローチャートは、トレーニングの処理を記述している。
認識工程
あるフィーチャタイプを考える。各トレーニング画像は、多数のフィーチャを含む。これらのフィーチャを、Пi、jとし、ここにおいてｉはトレーニング画像のインデックスであり、ｊは画像におけるフィーチャのインデックスである。ここで、πjを認識画像におけるフィーチャｊとする。各フィーチャは次の特性を有する。つまり、１）基準点Ｑ、２）角度γにより定義される基準方向、および３）一つまたは二つ以上の数値量から構成される本質的特性である。我々は、ベクトルΛにより、本質的特性を示す。γとΛの成分は、点Ｑを画像の中間点に移動するチルト−パン同形変換（「チルト−パン同形変換を使用する認識」の節を参照）から導出されなければならないということに留意されたい。
【００８２】
整合検索は、１）Λ（πj）とΛ（Пi、j）の比較と、２）潜在的認識対象物の姿勢状態を記述するパラメータ空間におけるクラスタ検索を含む。Λ（πj）がΛ（Пi、j）に十分類似していれば、本質的パラメータとの関連において整合が存在する。すべての本質的整合に対してｉ、Ｑ（Пi、j）、γ（Пi、j）、Ｑ（Пj）、およびγ（Пj）から導出される認識姿勢状態が算出され、クラスタ検索に使用される。ここで、トレーニング姿勢状態を定義するインデックスｉにより、認識姿勢状態の３自由度が与えられるが、他の３自由度は、適切な同形変換におけるチルト、パン、およびロールである。このステップの数学的詳細は、（チルト−パン同形変換を使用する認識）の節で記述される。
【００８３】
容認された各クラスタは、物理的対象物を表現していると考えられる。しかし、クラスタ検索の後に、推測される姿勢状態の間の三次元的オーバーラップのチェックを追加的に実行すべきである。トレーニング用の（ρ、φ、θ）構成空間は、必然的に分離化しなければならず、これほど単純な認識手順でも、分離化ステップの半分のオーダーのエラーを生じる。このエラーは、隣接するトレーニング画像からの結果の間に、内挿法を適用することで削減できる。
【００８４】
図１７と図１８は、トレーニング画像から導出される記述子のデータベースの構造と、認識画像から導出される記述子の構造を示している。ρi、φj、θkは、トレーニングパラメータの分離された値である。表中の各レコード（行）は、フィーチャから導出される。本例においては、各フィーチャは、三つの本質的記述子を有している。本質的記述子の数は、好ましくは３である。つまり、フィーチャの基準点の二つの座標と、同形変換後の基準方向である。データベースのレコードのいかなる非本質的記述子と、認識レコードのいかなる非本質的記述子も共に、認識フィーチャをトレーニングフィーチャと一致させるチルト−パン−ロール変換を定義する。そして、チルト−パン−ロールパラメータ空間における対応する点での増大化を実行できる。本質的認識記述子が、データベースの本質的記述子と十分に異なっている場合は、対応するフィーチャ対は考慮されない。この省略により、間違った対応関係によるノイズが削減される。
【００８５】
この認識工程における多数の重要な詳細が次の節の例で示される。
【００８６】
認識フローチャートは図１２に示されている。
フィーチャとして直線セグメント対の場合の認識工程
下記の例においては、認識に使用されるフィーチャは直線セクションの対であり、対象物は、三つの箱形状の要素から構成される「三つ組レンガ」である（図７参照）。図７は、姿勢状態決定の例において取り扱う三次元対象物を示している。
【００８７】
直線セクションは、好ましくはトレーニング写真の輪郭から導出される。各トレーニング画像における直線セクションのすべての対は、フィーチャと考えられる。直線対の交点は点Ｑであり、角度γは水平画像軸と、直線対の二等分線の方向との間の角度である。本質的記述子は、１）直線間の角度Ｖと、２）交点と直線セクションの終点との間の距離である。同形変換後、本質的フィーチャの両タイプが導出される。
【００８８】
直線セグメントの部分的な遮蔽は、誤った距離を生成するので、交点と終点の間の距離を、整合検索において直接使用すべきではない。
【００８９】
下記の検討は、角度に関する記述子のみに基づく検索に焦点を絞っている。
【００９０】
図８は、三つ組レンガ構造のレゴモデルのトレーニング写真を示している。
【００９１】
図９は、図８Ａの輪郭に沿う、弧の長さ（画素単位）の関数としてのラジアン／画素単位の曲率を示している。
【００９２】
図９から分かるように、直線セクションの位置を決めることは容易である。この例では、１２の直線セクションがある。直線の適切な対を導出すると、いくつかの対は省略される、つまり、直線間の角度が０または１８０度に近いものは省略される。このように、図８Ａにおいては、約９０対が考慮される。
【００９３】
図１０は、トレーニング画像と認識画像を組み合わせた図である。Ｐは焦点の中心である。トレーニング直線対ａｂは、ＱabがＰに移動するように同形変換される。これにより直線対ａ’ｂ’が生じる。量γabは、水平方向と二等分線ｍabの間の角度である。ａｂ直線対の本質的記述子は、ａ’とｂ’の間の角度Ｖabである。同様な定義が、認識画像の直線対ｃｄから導出される量についても成り立つ。角度Ｖ以外の本質的記述子は図示していない。
【００９４】
図１０は、トレーニング画像と認識画像を組み合わせた図である。例において、位置ＱabとＱcd、および二等分線ｍcdとｍabの間の角度γcdとγabは、トレーニング姿勢状態と認識姿勢状態の間のチルト−パン−ロール変換を定義する。特別なトレーニング画像の直線対に関連する認識画像の直線対はこのように、チルト−パン−ロールパラメータ空間の点を定義する。図１０の右上部分に示す直線対ｅｆは、ａｂ直線対とほぼ同じ角度記述子を有する。そして、アルゴリズムにおいては、この直線対の比較によって、パラメータ空間の「間違った」点が生成される。しかし、対応しないプリミティブがパラメータ空間において非常に分散された点を生成することは特徴的であり、一方、対応する直線対は、パラメータ空間においてクラスタを与える。他のトレーニング画像を、図１０の認識画像と整合させようとしても、整合する直線対のクラスタリングを得ることはない。
【００９５】
対象物の遮蔽と不十分な画像のセグメント化は、パラメータ空間における間違った点のバックグラウンドが、真の整合物のクラスタにより形成される信号と匹敵する程度にならない限り、認識工程に悪影響を与えることはないということは明白である。
【００９６】
間違った整合数が、クラスタ検索に混乱を与えるときは、上記の追加的な本質的記述子（直線セクションの終点と、交点の間の距離）を含む不規則性を設定することができる。そのような不規則性により、認識直線は部分的にしか見えなくなるが、認識直線が、トレーニング直線の範囲外に存在するセクションを有することを防止できる。
【００９７】
フィーチャπjを有する認識画像に対しては、アルゴリズムは下記のように動作する。
For each training image index i do
｛
Reset roll, tilt, pan parameter space;
For all valid indices j and J' compareΛ(Πi,j) and Λ(nj') do
｛
In case of intrinsic match
｛
Derive roll r, tilt t, pan p, from Q(Πi,j), γ(Πi,j), Q(nj'), γ(nj');
Update parameter space accordingly;
｝
｝
Test for clustering and store coordinates of clusters with sufficiently high
Density/population along with the index i of the training image.
｝
上記の「本質的整合」は、角度Ｖの類似性と、距離に関する不規則性の実現に基づいている。「パラメータ空間の更新」という用語は、パラメータ空間の関連する点における票を増加することである。
【００９８】
弱い透視法の場合は、単一の対象物は、いくつかのトレーニング画像を有するクラスタを生成する、つまり、同じφ値およびθ値を有するものを生成するが、ρ値は異なる。これらのρ値の一つのみが実際の対象物に対応するので、直線状の本質的記述子を使用する特別なアルゴリズムを使用すべきである。
【００９９】
推定されたトレーニングインデックスｉと、チルト−パン−ロール空間におけるクラスタ点を使用する逆変換は、（チルト−パン同形変換を使用する認識）の節で記述されている。この逆変換は、カメラに関しての認識対象物の姿勢状態（またはその逆）を定義するので、認識工程はこれで完了する。
パラメータρの空間状態、二台のカメラの使用
対象物とカメラの間の姿勢状態は、６個のパラメータで記述される。つまり、ａ）対応するトレーニング画像のρ、φ、θと、ｂ）認識姿勢状態とトレーニング姿勢状態の間の変換の（ロール、チルト、パン）である。弱い透視法の場合、プリミティブの無次元の記述子（例えば、角度）はρにはほとんど依存せず、直線記述子は、１／ρにほぼ比例する。従って、弱い、または適度な透視法に対しては、トレーニングを小数の異なるρ値に制限することが可能で、適切な内挿法を使用することができる。好ましくは、認識は二つの部分に分割される。最初の部分は、５個の角度パラメータの検出に集中し、二番目の部分は、内挿法を使用してρ値を導出する。
【０１００】
ρの最終値の正確性は、フィーチャの直線記述子の品質と、トレーニングに関連する、異なるρ値の数に依存する。内挿法を使用しても、ρの相対的な不確定性は、画像点間の距離を含む本質的記述子の相対的な不確定性よりも小さくはないことが好ましい。増大された正確性は、三次元三角測量が下記のように実行できるので、二台（または三台以上）のカメラを使用して得ることができる。
【０１０１】
カメラ１とカメラ２を考える（図１３）。カメラ１の分類と姿勢状態の推定結果を（ｉｃ1、ρ1、φ1、θ1、ｔ1、ｐ1、ｒ1）で特徴付け、ここにおいて、ｉｃ1は、対象物のタイプのインデックスで、残りのパラメータは姿勢状態を定義する。ρ1がまったく不確定であれば、残りの姿勢状態パラメータは、対象物基準点に対する直線Ｌ1を定義する（図１３参照）。同様に、カメラ２の推定（ｉｃ2、ρ2、φ2、θ2、ｔ2、ｐ2、ｒ2）は、直線Ｌ2を定義する。グローバルなカメラの姿勢状態が分かっているため、直線Ｌ1とＬ2は、グローバルフレームにおいて表現できる。ｉｃ1とｉｃ2とが等しい場合は、Ｌ1とＬ2は実質的に交差し、従って、推定の対は実際の対象物を表現していると思われる。更に、二つの以前は不確定であったパラメータρ1とρ2は、高い正確性で、擬似交点（図１３）によって決定できる。このように、姿勢状態の推定の正確性を高めるとともに、誤って解釈され、間違った信号−カメラの結果を回避できる。
【０１０２】
下記において、チルト−パン同形変換を使用する認識が、更に詳細に記述される。
チルト−パン同形変換を使用する認識
下記の表記を使用する。
【０１０３】
【数１】
【０１０４】
Ｒマトリックスは、ｔ（チルト）、ｐ（パン）、ｒ（ロール）を介する回転を記述する。マトリックスＫは、焦点距離ｆの透視法変換を記述する。我々は、下記のように定義される複合回転Ｒ（ｔ、ｐ、ｒ）を使用する。
【０１０５】
R(t,p,r)=Rz(r)Ry(p)Rx(t) (2)
ここにおいて、マトリックスの連続する掛け算は、右から左へ進む。Ｒ-1（ｔ、ｐ、ｒ）＝Ｒx（−ｔ）Ｒy（−ｐ）Ｒz（−ｒ）は、逆変換である。
【０１０６】
Ｒ（ｔ、ｐ、ｒ）の要素は、
【０１０７】
【数２】
【０１０８】
我々は、対象物フレームに関するカメラの回転と並進移動の組み合わせは、Ｒ（ｔ、ｐ、ｒ）｜Ｄで定義され、ここにおいて、Ｄは対象物フレームにおいて表現される並進移動ベクトルである。点が、対象物フレームにおいて座標（ｘo、ｙo、ｚo）で表現され、同じ点がカメラフレームにおいて座標（ｘc、ｙc、ｚc）で表現されるとすると、下記が得られる。
【０１０９】
【数３】
【０１１０】
対象物フレームにおいて表現されるカメラフレームの座標軸は、Ｒ（ｔ、ｐ、ｒ）の行ベクトルである。従って、カメラのｚ軸は、グローバルな方向、（ｓｉｎｐ、−ｃｏｓｐｓｉｎｔ、ｃｏｓｐｃｏｓｔ）を有することになる。
【０１１１】
ここで我々は、カメラのトレーニング姿勢状態を定義する。ピンホールの位置が、Ｄ＝（−ρｓｉｎφ、ρｃｏｓφｓｉｎθ、−ρｃｏｓφｓｉｎθ）によって与えられるとする。トレーニングカメラの角度（ｔ、ｐ、ｒ）を（θ、φ、π／２）と等しいように選択する。これは、光軸が、対象物の原点を通ることを意味する。ｒ＝π／２を選択したことは、カメラのｘc軸が、対象物フレームのｙｚ平面に平行であることを意味する。
【０１１２】
対象物とカメラの間の変換をＴCameraObjectとする。この変換は下記のように、二つに分割すべきである。
【０１１３】
【数４】
【０１１４】
ここにおいて、Ｏはゼロベクトルである。トレーニングカメラの姿勢状態は、１）対象物フレームの原点に向かうような方位を有する光軸と、２）対象物ｙｚ平面に平行なカメラのｘc軸により特徴付けられる。角度ｔ、ｐ、ｒは、トレーニングカメラの方位から認識方位への変換ＴCameraTrainingCameraを特徴付ける、チルト、パン、およびロール角である。トータルな変換ＴCameraObjectは、ρと、５個の角度ｒ、ｔ、ｐ、θ、およびφから導出できることに留意されたい。
【０１１５】
Ω（ρ、φ、θ、ｒ、ｐ、ｔ）を、（ρ、φ、θ、ｒ、ｐ、ｔ）により与えられる姿勢状態を有するカメラにより記録された画像とする。共通のピンホールの位置を有する同形の間の関係、つまり、Ω（ρ、φ、θ、ｒ、ｐ、ｔ）とΩ（ρ、φ、θ、０、０、０）の関係は、ここでは、下記の同次座標を使用して表現される二次元変換であり、ここで（ｕ、ｖ）と（ｕ’、ｖ’）は画像の座標である。
【０１１６】
【数５】
【０１１７】
画像座標の原点は、焦点位置としている。
【０１１８】
我々は、変換ＫＲ（ｔ、ｐ、０）Ｋ-1（ゼロロール角）に焦点を当てる。その理由は、ＫとＲは交換可能であるため、ロールは画像回転と考えられるからである。Ｈ（ｔ、ｐ）≡ＫＲ（ｔ、ｐ、０）Ｋ-1により定義される同形（２Ｄ）演算Ｈ（ｔ、ｐ）は、次のように記述できる。
【０１１９】
【数６】
【０１２０】
演算Ｈ（ｔ、ｐ）は、画像全体と同時に、画像の点に対しても可能であることに留意されたい。特別な点Ｑ＝（ｕQ、ｖQ）を原点（焦点）に移動する変換は、下記のパンとチルト角により与えられる。
【０１２１】
【数７】
【０１２２】
逆変換は、次の式で与えられる。
【０１２３】
【数８】
【０１２４】
関連画像において１）基準二次元の点Ｑと、２）ｕ軸との、方向角γを有するフィーチャを考える。このフィーチャは、トレーニング画像Ｑtrにおけるパラメータ（Ｑtr、γtr）と、認識画像Ｑrecにおける（Ｑrec、γrec）を有している。このように、ＱtrとＱrecは、対応する点であり、角γtrとγrecの方向もまた対応している。二つの画像を比較することは興味深い。
【０１２５】
【数９】
【０１２６】
これらの二つの画像は、お互いが、それぞれを回転したものであり、Ω’recに対する
Ω’trの回転角は、γrec−γtrとなる。両者は、ＱtrとＱrecに画像化されている、三次元の点Ｑを通る光軸に対する姿勢状態に対応する。トレーニング姿勢状態に対する認識姿勢状態の、チルト、パン、およびロール角、ｔ、ｐ、およびｒは次の式で与えられることを証明できる。
【０１２７】
【数１０】
【０１２８】
トレーニング画像の処理は下記のように行われる。つまり、画像はフィーチャ（単一固定点、固定点群、複合フィーチャ）に関して分析される。各フィーチャのＱrecとγrecの値と、他の種々の本質的数値記述子が導出され、データベースに格納される。速度最適化のために、マトリックスＲ-1（ｔo（Ｑtr）、ｐo（Ｑtr）、γtr）もまた算出されて格納される。
【０１２９】
認識の間、認識画像中の全フィーチャの本質的数値記述子は、データベース中の全類似フィーチャと比較される。整合が十分である場合は、回転ＴCameraTrainingCameraのパラメータｔ、ｐ、およびｒは（９）から導出される。ｔ、ｐ、ｒの結果の値と、整合トレーニング画像のパラメータρ、φ、θは共に、変換ＴCameraObjectを定義するので、三次元対象物の姿勢状態の６個のパラメータの推定値を形成する。六次元の姿勢状態におけるクラスタは、対応する姿勢状態で位置する実際の対象物により引き起こされたとされている。
【０１３０】
弱い、または適度な透視法の場合は、パラメータρの異なる値の数は、長さフィーチャが、近似的にρ-1に等しいρ依存性を有するので、非常に少なくするように選択できる。この場合、スケール不変の記述子に、五次元のｒ、ｐ、ｔ、φ、θ空間における関連する点を決定させることを推奨する。スケール不変の記述子のその後の分析により、関連するρ値が決定される。
【０１３１】
トータルな、対象物とカメラの間の変換は、次のように表わせる。
【０１３２】
【数１１】
【図面の簡単な説明】
【０１３３】
【図１】チルト−パン同形変換を示している。
【図２】プリミティブ、プリミティブ対、および角度を示している。
【図３】四つの異なるウィンドウにおける画像の例を示している。
【図４】図３の画像の上部右隅の輪郭を示している。図４の上部のウィンドウは、副画素の正確性を有する輪郭を示し、図４の下のウィンドウは輪郭の整数画素位置を示している。
【図５】図３のウィンドウ４の輪郭の一つに沿う弧の長さ（画素単位）の関数として、曲率κ（ｓ）（ラジアン／画素）を示している。シンボルは対応関係を示すために使用される（図６参照）。
【図６】図３に示す画像に対して見出された外部の輪郭を示している。特徴的フィーチャに使用されるシンボルは、図５に与えられたものに対応する。
【図７】姿勢状態決定のための例において処理される、三次元三つ組レンガを示している。
【図８】三つ組みレンガ構造のレゴモデルのトレーニング写真を示している。
【図９】図８Ａの輪郭に沿う弧の長さ（画素単位）の関数として、ラジアン／画素の曲率を示している。
【図１０】トレーニング画像と、認識画像の組み合わせ図を示している。
【図１１】トレーニングに対する処理を記述するフローチャートを示している。
【図１２】認識に対する処理を記述するフローチャートを示している。
【図１３】二台のカメラ操作を示している。
【図１４】カメラのピンホールモデルを示している。
【図１５】画像から導出されたグレイトーン俯瞰図を示している。
【図１６】トレーニング用幾何学的配置を示している。
【図１７】トレーニング画像から導出された記述子のデータベースの構造を示している。
【図１８】認識画像から導出された記述子の構造を示している。
【特許請求の範囲】
【請求項１】
デジタル画像において、輪郭、好ましくはレベル輪郭と、プリミティブを決定する方法であって、前記方法は、
前記デジタル画像の勾配を生成し、
前記絶対勾配の一つまたは二つ以上の極大値を求め、
前記一つまたは二つ以上の極大値を、輪郭を生成するためのシードとして使用し、ここにおいて各シードに対する前記輪郭の生成は、前記デジタル画像内にあり、輪郭に属する場所を表現する点の順序リストを決定することを含み、
前記すべての場所に対して、前記輪郭の、好ましくはｄθ／ｄｓ、好ましくは画素単位で決定される曲率を決定し、
前記決定された曲率から、プリミティブを前記輪郭上の、または前記輪郭のセグメント上の特徴点として決定するステップを含む方法。
【請求項２】
既に定義された輪郭近傍で特定される潜在シード点を削除するステップを更に含む請求項１に記載の方法。
【請求項３】
前記輪郭の生成は、各点が前記シードの値と共通に割り当てられる値を有する、前記デジタル画像内の場所を表現する点のリストを割り当てることを含む請求項１または２に記載の方法。
【請求項４】
前記輪郭の生成は、各点において、輪郭方向に直交すると検出された最大または最小勾配の方向に続く点のリストを割り当てることを含む請求項１または２に記載の方法。
【請求項５】
前記輪郭の生成は、前記シードの値を超える、またはそれ未満の値を有する点のリスト、および前記シードの値未満の、またはその値を超える値を有する一つまたは二つ以上の隣接する画素を割り当てることを含む請求項１または２に記載の方法。
【請求項６】
前記画素リストは、所定の方法で前記デジタル画像内を移動することにより確立される請求項１から請求項５のいずれか１項に記載の方法。
【請求項７】
前記輪郭は、前記画素リストに基づく内挿法により決定される請求項２から請求項６のいずれか１項に記載の方法。
【請求項８】
前記リストは、画素の順序リストである請求項２から請求項７のいずれか１項に記載の方法。
【請求項９】
前記勾配は、隣接画素に割り当てられた数値間の差を計算することにより決定される請求項１から請求項８のいずれか１項に記載の方法。
【請求項１０】
前記勾配は、各要素が第１画像内の特別な場所に対応し、前記特別な場所における前記第１画像の色調の勾配値を表わす数値であるアレイに格納される請求項１から請求項９のいずれか１項に記載の方法。
【請求項１１】
前記曲率は、θを輪郭上の１点における接線方向とし、ｓを基準点から測定された弧の長さとしたときに、κ＝ｄθ／ｄｓとして確立される請求項１から請求項１０のいずれか１項に記載の方法。
【請求項１２】
前記プリミティブは、下記の特徴、
直線のセグメント、
相対的に大きな半径の円のセグメント、
変曲点、
前記曲率の最大数値の、好ましくは角部として割り当てられた点、
前記曲率の非常に小さな、および非常に大きな数値の部分を分離する点、および
輪郭により囲まれた小さな領域のエンティティ、
を一つまたは二つ以上備える請求項１から請求項１１のいずれか１項に記載の方法。
【請求項１３】
各輪郭に対して、下記のプリミティブ、
所定のレベルより高い曲率の絶対値の値を有する輪郭の領域またはその上の点である変曲点、
曲率の正のピークを有する前記輪郭の領域またはその上の点である凹状角部、
曲率の負のピークを有する前記輪郭の領域またはその上の点である凸状角部、
０の曲率を有する前記輪郭のセグメントである直線セグメント、および／または
一定曲率を有する前記輪郭のセグメントである円形セグメント、
の一つまたは二つ以上を検索する請求項１から請求項１２のいずれかに記載の方法。
【請求項１４】
三次元対象物の分類および／またはローカライゼーションのような認識方法であり、前記一つまたは二つ以上の対象物は、前記対象物の二次元デジタル画像である認識画像を提供するように画像化され、前記方法は、フィーチャの本質的および非本質的特性である数値記述子が多数のトレーニング画像に対して格納されたデータベースを利用し、前記方法は、
前記画像に対して、プリミティブの予め定義されたセットであるフィーチャを特定し、
前記フィーチャの数値記述子を抽出し、ここにおいて前記数値記述子は、
前記画像中の前記フィーチャの位置および方向のような前記フィーチャの非本質的特性と、
前記フィーチャに適用される同形変換後に好ましくは導出される前記フィーチャの本質的特性の二種類あり、
前記特性を前記データベースに格納された特性と整合し、整合物が見つかれば、前記データベース内で整合した特性に対応する前記対象物を、認識すべき前記対象物の前記対象物に類似していると割り当てる認識方法。
【請求項１５】
認識画像を、前記データベースに格納されたトレーニング画像と整合し、整合付けは各トレーニング画像に対して、
前記トレーニング画像の前記フィーチャと同一の前記認識画像の前記フィーチャをもたらす変換のロール、チルト、およびパンの値を決定し、
前記変換により決定されたロール、チルト、およびパンの値により定義される前記パラメータ空間におけるクラスタを特定し、および
予め定義された強度を有するクラスタを、対象物のタイプおよびローカライゼーションに対応するものとして特定する、
ステップを含む請求項１４に記載の方法。
【請求項１６】
前記データベースは各画像に対して、それぞれがその本質的特性およびその非本質的特性を有するフィーチャを表わす一つまたは二つ以上のレコードを備える請求項１４または請求項１５に記載の方法。
【請求項１７】
前記整合付けは、
ロール、チルト、およびパンパラメータ空間をリセットし、
前記認識画像における各フィーチャに対して、前記認識画像の特性を前記データベースに格納されている特性と整合付け、
整合する場合、前記データベースから、および前記認識画像からの前記非本質的特性に基づいてロール、チルト、およびパンを決定し、
パラメータ空間を更新し、および
クラスタリングをテストし、前記トレーニング画像のインデックスを有する十分に高い密度／母集団のクラスタの座標を格納するステップを含み、
前記ステップを前記認識画像中のすべてのフィーチャの整合付けが終了するまで繰り返す、
ことを含む請求項１６に記載の方法。
【請求項１８】
前記ロール、チルト、およびパンの決定は、前記データベース内の前記本質的特性と比較して類似のまたは同一の本質的特性を有するフィーチャに対してのみ行われる請求項１７に記載の方法。
【請求項１９】
前記整合付けは、前記認識画像の前記本質的記述子と、前記データベースに格納されている前記本質的記述子と比較し、それにより整合するフィーチャを選択することを含む請求項１７に記載の方法。
【請求項２０】
前記データベースは、請求項２１から請求項１４のいずれかに従って生成される請求項１４または請求項１９に記載の方法。
【請求項２１】
三次元対象物の位置決めおよび／または分類に関連して有効なデータベースの生成方法であり、前記対象物は、前記対象物の二次元デジタル画像を提供するように画像化され、 前記方法は、前記対象物の前記二次元デジタル画像のプリミティブを決定するために請求項１から請求項２０のいずれかの方法を利用し、前記方法は、
一つまたは二つ以上の対象物の多数のデジタル画像において、プリミティブの予め定義されたセットであるフィーチャを特定し、前記画像は、前記一つまたは二つ以上の対象物の異なるローカライゼーションを表わし、
前記フィーチャの数値記述子を、前記データベースから抽出して格納し、前記数値記述子は、
前記画像中の前記フィーチャの位置および方位であり、前記フィーチャの非本質的特性と、
前記フィーチャに適用される同形変換後に導出される前記フィーチャの本質的特性の二種類である、
ことを含む方法。
【請求項２２】
前記非本質的特性は、基準点と基準方向を備える請求項１４から請求項２１のいずれかに記載の方法。
【請求項２３】
前記本質的特性は、フィーチャの数値量を備える請求項１４から請求項２２のいずれかに記載の方法。
【請求項２４】
前記対象物は少なくとも二台の撮像装置で画像化され、それにより前記対象物の少なくとも二つの認識画像を生成し、請求項１２から請求項１８のいずれかに記載の方法が各認識画像に適用され、各認識画像に対して見出された前記整合物が比較される請求項１４から請求項２０のいずれかに記載の方法。
【請求項２５】
前記方法は、
各撮像装置に対して、前記対象物の前記三次元基準点に対する推定値を提供し、
各撮像装置に対して、前記撮像装置のピンホールから前記推定された基準点までの直線を計算し、
少なくとも二つまたは三つ以上の直線が提供された場合は、
前記二つまたは三つ以上の直線が三次元で実質的に交差しない場合は、前記推定値を破棄し、
前記二つまたは三つ以上の直線が実質的に交差する場合は、
各撮像装置から得られた前記直線の間の擬似交点に基づいて、前記基準点のグローバルポジションを推定する請求項２４に記載の方法。
【請求項１】
デジタル画像において、輪郭、好ましくはレベル輪郭と、プリミティブを決定する方法であって、前記方法は、
前記デジタル画像の勾配を生成し、
前記絶対勾配の一つまたは二つ以上の極大値を求め、
前記一つまたは二つ以上の極大値を、輪郭を生成するためのシードとして使用し、ここにおいて各シードに対する前記輪郭の生成は、前記デジタル画像内にあり、輪郭に属する場所を表現する点の順序リストを決定することを含み、
前記すべての場所に対して、前記輪郭の、好ましくはｄθ／ｄｓ、好ましくは画素単位で決定される曲率を決定し、
前記決定された曲率から、プリミティブを前記輪郭上の、または前記輪郭のセグメント上の特徴点として決定するステップを含む方法。
【請求項２】
既に定義された輪郭近傍で特定される潜在シード点を削除するステップを更に含む請求項１に記載の方法。
【請求項３】
前記輪郭の生成は、各点が前記シードの値と共通に割り当てられる値を有する、前記デジタル画像内の場所を表現する点のリストを割り当てることを含む請求項１または２に記載の方法。
【請求項４】
前記輪郭の生成は、各点において、輪郭方向に直交すると検出された最大または最小勾配の方向に続く点のリストを割り当てることを含む請求項１または２に記載の方法。
【請求項５】
前記輪郭の生成は、前記シードの値を超える、またはそれ未満の値を有する点のリスト、および前記シードの値未満の、またはその値を超える値を有する一つまたは二つ以上の隣接する画素を割り当てることを含む請求項１または２に記載の方法。
【請求項６】
前記画素リストは、所定の方法で前記デジタル画像内を移動することにより確立される請求項１から請求項５のいずれか１項に記載の方法。
【請求項７】
前記輪郭は、前記画素リストに基づく内挿法により決定される請求項２から請求項６のいずれか１項に記載の方法。
【請求項８】
前記リストは、画素の順序リストである請求項２から請求項７のいずれか１項に記載の方法。
【請求項９】
前記勾配は、隣接画素に割り当てられた数値間の差を計算することにより決定される請求項１から請求項８のいずれか１項に記載の方法。
【請求項１０】
前記勾配は、各要素が第１画像内の特別な場所に対応し、前記特別な場所における前記第１画像の色調の勾配値を表わす数値であるアレイに格納される請求項１から請求項９のいずれか１項に記載の方法。
【請求項１１】
前記曲率は、θを輪郭上の１点における接線方向とし、ｓを基準点から測定された弧の長さとしたときに、κ＝ｄθ／ｄｓとして確立される請求項１から請求項１０のいずれか１項に記載の方法。
【請求項１２】
前記プリミティブは、下記の特徴、
直線のセグメント、
相対的に大きな半径の円のセグメント、
変曲点、
前記曲率の最大数値の、好ましくは角部として割り当てられた点、
前記曲率の非常に小さな、および非常に大きな数値の部分を分離する点、および
輪郭により囲まれた小さな領域のエンティティ、
を一つまたは二つ以上備える請求項１から請求項１１のいずれか１項に記載の方法。
【請求項１３】
各輪郭に対して、下記のプリミティブ、
所定のレベルより高い曲率の絶対値の値を有する輪郭の領域またはその上の点である変曲点、
曲率の正のピークを有する前記輪郭の領域またはその上の点である凹状角部、
曲率の負のピークを有する前記輪郭の領域またはその上の点である凸状角部、
０の曲率を有する前記輪郭のセグメントである直線セグメント、および／または
一定曲率を有する前記輪郭のセグメントである円形セグメント、
の一つまたは二つ以上を検索する請求項１から請求項１２のいずれかに記載の方法。
【請求項１４】
三次元対象物の分類および／またはローカライゼーションのような認識方法であり、前記一つまたは二つ以上の対象物は、前記対象物の二次元デジタル画像である認識画像を提供するように画像化され、前記方法は、フィーチャの本質的および非本質的特性である数値記述子が多数のトレーニング画像に対して格納されたデータベースを利用し、前記方法は、
前記画像に対して、プリミティブの予め定義されたセットであるフィーチャを特定し、
前記フィーチャの数値記述子を抽出し、ここにおいて前記数値記述子は、
前記画像中の前記フィーチャの位置および方向のような前記フィーチャの非本質的特性と、
前記フィーチャに適用される同形変換後に好ましくは導出される前記フィーチャの本質的特性の二種類あり、
前記特性を前記データベースに格納された特性と整合し、整合物が見つかれば、前記データベース内で整合した特性に対応する前記対象物を、認識すべき前記対象物の前記対象物に類似していると割り当てる認識方法。
【請求項１５】
認識画像を、前記データベースに格納されたトレーニング画像と整合し、整合付けは各トレーニング画像に対して、
前記トレーニング画像の前記フィーチャと同一の前記認識画像の前記フィーチャをもたらす変換のロール、チルト、およびパンの値を決定し、
前記変換により決定されたロール、チルト、およびパンの値により定義される前記パラメータ空間におけるクラスタを特定し、および
予め定義された強度を有するクラスタを、対象物のタイプおよびローカライゼーションに対応するものとして特定する、
ステップを含む請求項１４に記載の方法。
【請求項１６】
前記データベースは各画像に対して、それぞれがその本質的特性およびその非本質的特性を有するフィーチャを表わす一つまたは二つ以上のレコードを備える請求項１４または請求項１５に記載の方法。
【請求項１７】
前記整合付けは、
ロール、チルト、およびパンパラメータ空間をリセットし、
前記認識画像における各フィーチャに対して、前記認識画像の特性を前記データベースに格納されている特性と整合付け、
整合する場合、前記データベースから、および前記認識画像からの前記非本質的特性に基づいてロール、チルト、およびパンを決定し、
パラメータ空間を更新し、および
クラスタリングをテストし、前記トレーニング画像のインデックスを有する十分に高い密度／母集団のクラスタの座標を格納するステップを含み、
前記ステップを前記認識画像中のすべてのフィーチャの整合付けが終了するまで繰り返す、
ことを含む請求項１６に記載の方法。
【請求項１８】
前記ロール、チルト、およびパンの決定は、前記データベース内の前記本質的特性と比較して類似のまたは同一の本質的特性を有するフィーチャに対してのみ行われる請求項１７に記載の方法。
【請求項１９】
前記整合付けは、前記認識画像の前記本質的記述子と、前記データベースに格納されている前記本質的記述子と比較し、それにより整合するフィーチャを選択することを含む請求項１７に記載の方法。
【請求項２０】
前記データベースは、請求項２１から請求項１４のいずれかに従って生成される請求項１４または請求項１９に記載の方法。
【請求項２１】
三次元対象物の位置決めおよび／または分類に関連して有効なデータベースの生成方法であり、前記対象物は、前記対象物の二次元デジタル画像を提供するように画像化され、 前記方法は、前記対象物の前記二次元デジタル画像のプリミティブを決定するために請求項１から請求項２０のいずれかの方法を利用し、前記方法は、
一つまたは二つ以上の対象物の多数のデジタル画像において、プリミティブの予め定義されたセットであるフィーチャを特定し、前記画像は、前記一つまたは二つ以上の対象物の異なるローカライゼーションを表わし、
前記フィーチャの数値記述子を、前記データベースから抽出して格納し、前記数値記述子は、
前記画像中の前記フィーチャの位置および方位であり、前記フィーチャの非本質的特性と、
前記フィーチャに適用される同形変換後に導出される前記フィーチャの本質的特性の二種類である、
ことを含む方法。
【請求項２２】
前記非本質的特性は、基準点と基準方向を備える請求項１４から請求項２１のいずれかに記載の方法。
【請求項２３】
前記本質的特性は、フィーチャの数値量を備える請求項１４から請求項２２のいずれかに記載の方法。
【請求項２４】
前記対象物は少なくとも二台の撮像装置で画像化され、それにより前記対象物の少なくとも二つの認識画像を生成し、請求項１２から請求項１８のいずれかに記載の方法が各認識画像に適用され、各認識画像に対して見出された前記整合物が比較される請求項１４から請求項２０のいずれかに記載の方法。
【請求項２５】
前記方法は、
各撮像装置に対して、前記対象物の前記三次元基準点に対する推定値を提供し、
各撮像装置に対して、前記撮像装置のピンホールから前記推定された基準点までの直線を計算し、
少なくとも二つまたは三つ以上の直線が提供された場合は、
前記二つまたは三つ以上の直線が三次元で実質的に交差しない場合は、前記推定値を破棄し、
前記二つまたは三つ以上の直線が実質的に交差する場合は、
各撮像装置から得られた前記直線の間の擬似交点に基づいて、前記基準点のグローバルポジションを推定する請求項２４に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公表番号】特表２００７−５０２４７３（Ｐ２００７−５０２４７３Ａ）
【公表日】平成１９年２月８日（２００７．２．８）
【国際特許分類】
【出願番号】特願２００６−５２３５２５（Ｐ２００６−５２３５２５）
【出願日】平成１６年８月１３日（２００４．８．１３）
【国際出願番号】ＰＣＴ／ＤＫ２００４／０００５４０
【国際公開番号】ＷＯ２００５／０１７８２０
【国際公開日】平成１７年２月２４日（２００５．２．２４）
【出願人】（５０６０５３６０７）スカーペ アクティーゼルスカブ (1)
【Ｆターム（参考）】
【公表日】平成１９年２月８日（２００７．２．８）
【国際特許分類】
【出願日】平成１６年８月１３日（２００４．８．１３）
【国際出願番号】ＰＣＴ／ＤＫ２００４／０００５４０
【国際公開番号】ＷＯ２００５／０１７８２０
【国際公開日】平成１７年２月２４日（２００５．２．２４）
【出願人】（５０６０５３６０７）スカーペ アクティーゼルスカブ (1)
【Ｆターム（参考）】
[ Back to top ]