(57)【要約】  認識タスクにおける認識アルゴリズムに合う適切な特徴点を選ぶことができ、また、重要な特徴点が最終的に選択した特徴点の集合から漏れにくくすることができる特徴点選択システムを提供する。特徴点セット選択手段５１は、特徴点候補から特徴点セットを複数選択する。認識誤差算出手段５２は、特徴点セット毎に認識誤差を算出する。特徴点選択手段５３は、特徴点セット毎の認識誤差の最小値が、特徴点候補を用いたときの認識誤差より大きい場合に、特徴点セット毎に、特徴点候補を用いたときの認識誤差からの認識誤差の増加量の指数関数の逆数を計算し、その計算結果に応じて、一つの特徴点セットを選択し、特徴点セット選択手段が特徴点セットを選択する際の特徴点数を更新する。特徴点セット選択手段５１は、その特徴点セットに基づいて、再度、特徴点セットを複数選択する。
2012032747.tif 000002
【特許請求の範囲】
【請求項１】
認識タスクに適した特徴点の候補となる点の集合である特徴点候補から、特徴点の集合である特徴点セットであって、定められた特徴点数の特徴点を含む特徴点セットを複数選択する特徴点セット選択手段と、
前記特徴点セット選択手段に選択された特徴点セット毎に、特徴点セットに含まれる特徴点を用いて前記認識タスクを実行した場合における認識誤差を算出する認識誤差算出手段と、
前記特徴点セット選択手段に選択された特徴点セット毎の認識誤差の最小値が、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差より大きい場合に、特徴点セット毎に、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差からの認識誤差の増加量の指数関数の逆数を計算し、その計算結果の値の大きさに応じて、一つの特徴点セットを選択し、特徴点セット選択手段が特徴点セットを選択する際の特徴点数を更新し、所定の条件が成立したときに前記認識タスクに適した特徴点を選択する特徴点選択手段とを備え、
特徴点セット選択手段は、特徴点選択手段が特徴点セットを選択したときに、当該特徴点セットに基づいて特徴点候補を定め、再度、特徴点セットを複数選択する
ことを特徴とする特徴点選択システム。
【請求項２】
認識タスクは、個体の姿勢推定であり、
認識誤差算出手段は、更新前の特徴点数の特徴点を含む特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータ、およびそれらの微分値を用い、更新後の特徴点数に基づいて選択された特徴点セットに含まれる特徴点を用いた場合の認識誤差を近似的に算出する
請求項１に記載の特徴点選択システム。
【請求項３】
認識タスクは、個体の姿勢推定であり、
特徴点セット選択手段は、特徴点選択手段が特徴点セットを選択したときに、
特徴点選択手段が選択した特徴点セットに含まれる特徴点に関して、前記特徴点セットから削除した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した除外確率に応じて、前記特徴点を前記特徴点セットから除外し、
特徴点選択手段が選択した特徴点セットに含まれないが、最初の特徴点候補に含まれる特徴点に関して、前記特徴点セットに追加した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した追加確率に応じて、前記特徴点を前記特徴点セットに追加することにより、特徴点候補を定める
請求項１または請求項２に記載の特徴点選択システム。
【請求項４】
特徴点選択手段は、選択した特徴点セットの特徴点数が所定数まで減少したこと、または、選択した特徴点セットにおける認識誤差が前回選択した特徴点セットにおける認識誤差から一定量以上増加したこと、または、選択した特徴点セットにおける認識誤差が予め定めた閾値以上になったことを所定の条件として、前記所定の条件が成立したときに、その時に定められていた特徴点数に基づいて選択された複数の特徴点セットのうち、認識誤差が最小になる特徴点セットに含まれる特徴点群を、認識タスクに適した特徴点として選択する
請求項１から請求項３のうちのいずれか１項に記載の特徴点選択システム。
【請求項５】
認識タスクに適した特徴点の候補となる点の集合である特徴点候補から、特徴点の集合である特徴点セットであって、定められた特徴点数の特徴点を含む特徴点セットを複数選択し、
選択した特徴点セット毎に、特徴点セットに含まれる特徴点を用いて前記認識タスクを実行した場合における認識誤差を算出し、
選択した特徴点セット毎の認識誤差の最小値が、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差より大きい場合に、特徴点セット毎に、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差からの認識誤差の増加量の指数関数の逆数を計算し、その計算結果の値の大きさに応じて、一つの特徴点セットを選択し、複数の特徴点セットを選択する際の特徴点数を更新し、所定の条件が成立したときに前記認識タスクに適した特徴点を選択し、
前記一つの特徴点セットを選択したときに、当該特徴点セットに基づいて特徴点候補を定め、再度、特徴点セットを複数選択する
ことを特徴とする特徴点選択方法。
【請求項６】
認識誤差を算出するときに、更新前の特徴点数の特徴点を含む特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータ、およびそれらの微分値を用い、更新後の特徴点数に基づいて選択された特徴点セットに含まれる特徴点を用いた場合の認識誤差を近似的に算出する
請求項５に記載の特徴点選択方法。
【請求項７】
前記一つの特徴点セットを選択した場合、再度、特徴点セットを複数選択するときに、
前記一つの特徴点セットに含まれる特徴点に関して、前記特徴点セットから削除した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した除外確率に応じて、前記特徴点を前記特徴点セットから除外し、
前記一つの特徴点セットに含まれないが、最初の特徴点候補に含まれる特徴点に関して、前記特徴点セットに追加した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した追加確率に応じて、前記特徴点を前記特徴点セットに追加することにより、特徴点候補を定める
請求項５または請求項６に記載の特徴点選択方法。
【請求項８】
コンピュータに、
認識タスクに適した特徴点の候補となる点の集合である特徴点候補から、特徴点の集合である特徴点セットであって、定められた特徴点数の特徴点を含む特徴点セットを複数選択する特徴点セット選択処理、
前記特徴点セット選択処理で選択された特徴点セット毎に、特徴点セットに含まれる特徴点を用いて前記認識タスクを実行した場合における認識誤差を算出する認識誤差算出処理、および、
前記特徴点セット選択処理で選択された特徴点セット毎の認識誤差の最小値が、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差より大きい場合に、特徴点セット毎に、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差からの認識誤差の増加量の指数関数の逆数を計算し、その計算結果の値の大きさに応じて、一つの特徴点セットを選択し、特徴点セット選択処理で特徴点セットを選択する際の特徴点数を更新し、所定の条件が成立したときに前記認識タスクに適した特徴点を選択する特徴点選択処理を実行させ、
特徴点選択処理で特徴点セットを選択させたときに、特徴点セット選択処理で、当該特徴点セットに基づいて特徴点候補を定め、再度、特徴点セットを複数選択させる
ための特徴点選択プログラム。
【請求項９】
コンピュータに、
認識誤差算出処理で、更新前の特徴点数の特徴点を含む特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータ、およびそれらの微分値を用い、更新後の特徴点数に基づいて選択された特徴点セットに含まれる特徴点を用いた場合の認識誤差を近似的に算出させる
請求項８に記載の特徴点選択プログラム。
【請求項１０】
コンピュータに、
特徴点選択処理で特徴点セットを選択させたときに、特徴点セット選択処理で、
特徴点選択処理で選択した特徴点セットに含まれる特徴点に関して、前記特徴点セットから削除した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した除外確率に応じて、前記特徴点を前記特徴点セットから除外し、特徴点選択処理で選択した特徴点セットに含まれないが、最初の特徴点候補に含まれる特徴点に関して、前記特徴点セットに追加した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した追加確率に応じて、前記特徴点を前記特徴点セットに追加することにより、特徴点候補を定めさせる
請求項８または請求項９に記載の特徴点選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元形状モデル上の複数の特徴点の中から好ましい特徴点を選択する特徴点選択システム、特徴点選択方法および特徴点選択プログラムに関する。
【背景技術】
【０００２】
画像に示された物体やその物体の状態を認識する処理を認識タスクと呼ぶ。認識タスクの例として、個体（例えば人の顔）の画像から、その個体の向き（以下、姿勢と記す。）を推定したり、その個体を識別したりする処理が挙げられる。物体の姿勢推定を例にして認識タスクの例を示す。まず、予め物体の３次元形状モデルにおける特徴点の３次元位置を記憶しておく。一般に、システム稼働後に認識対象の個体が新たに登録されるシステムにおいて、特徴点位置は全個体で共通とされる。特徴点の記憶後、認識対象の画像（本例では、姿勢推定しようとする物体が表された画像）から、特徴点の位置を検出し、予め記憶していた特徴点の３次元位置と対応付ける。そして、認識対象画像における特徴点の位置と、３次元形状モデル上における特徴点の位置との対応関係から物体の姿勢推定を行う。この対応関係から物体の姿勢を推定する方法は、透視ｎ点問題の解法として知られている。【０００３】
上記のような処理において、予め記憶される３次元形状モデル上の特徴点は、予め認識対象物体の一部であり画像の中で位置を特定することが容易であること、および、認識タスクにおいてその部位の位置が重要であると考えられることを考慮して人手で定められていた。人手による特徴点決定について、より詳細に説明する。姿勢推定等の認識アルゴリズムは、一般に、用いる特徴点の数が多いほど認識性能を向上できる。しかし、多数の特徴点を用いると、認識タスクの計算量は増大する。さらに、認識対象画像から特徴点を抽出するための計算量も増大する。そのため、特徴点の数を絞り込むことが実用上重要である。少数の特徴点で認識タスクにおける認識性能を向上させるためには、以下のような条件を満たす特徴点を決めておく必要がある。第１条件として、認識タスクにおいて重要な特徴点であること（換言すれば、精度に与える影響が大きいこと）が必要である。さらに、第２条件として、画像から特徴点として精度良く抽出できることが必要である。一般的に、第１条件および第２条件を両方とも満たす特徴点が３次元形状モデル上の点から人手で決められている。【０００４】
３次元モデル上の特徴点を自動的に決定する手法としては、例えば、非特許文献１に、エントロピーに基づいて特徴点を生成する方法が記載されている。しかしながら、上記の第１条件・第２条件を考慮し、認識タスクにとって有用な少数の特徴点に絞り込むことができなかった。このため、認識タスクに使用する特徴点の定義は人手によって決定されていた。【０００５】
また、認識対象画像からの特徴点抽出は、認識対象画像から各部分をそれぞれ切り出し、予め学習しておいた判定用パターンと比較し、最も特徴点らしいと判定された位置を特徴点位置と決定することにより行う。【０００６】
非特許文献２には、画像間の対応点を求めるために必要な特徴点を、ＳＩＦＴ（Scale-Invariant Feature Transform ）アルゴリズムによって抽出する技術が記載されている。ＳＩＦＴアルゴリズムは、多重解像度解析による塊検出と、濃淡勾配のヒストグラムを利用した画像間の対応付けを可能とする。ＳＩＦＴアルゴリズムでは、特徴点の特徴量も算出する。予め学習において与えられた判定用パターンの特徴量を記憶しておき、認識対象の画像から抽出された特徴点の特徴量と比較することで、特徴点かどうかの判定を行い、その位置を抽出することができる。【０００７】
また、この判定を行う技術として、多くのパターン識別法を利用することもできる。その一例として、一般化学習ベクトル量子化（ＧＬＶＱ：Generalized Learning Vector Quantization）を用いることが非特許文献３に記載されている。非特許文献３では顔のパターン検出を行っているが、パターンを顔から特徴点に置き換えれば特徴点の検出を行うことができる。また、機械学習の手法としてＳＶＭ（Support Vector Machine）も知られている。【０００８】
認識対象画像上に表される特徴点の見え方は、物体の姿勢や照明条件によって変化する。画像から切り出された部分が特徴点に該当するか否かを正しく判断するためには、判定用パターンを学習しておく必要がある。そのため、様々な条件で物体の学習用画像を多数撮影しておき、その多数の学習用画像それぞれにおいて正しい特徴点の位置を人手で入力して判定用パターンを学習させていた。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Joshua Cates, Miriah Meyer, P.Thomas Fletcher, Ross Whitaker, “Entropy-Based Particle Systems for Shape Correspondence”,Proceedings of the MICCAI,２００６年
【非特許文献２】藤吉弘亘、「Ｇｒａｄｉｅｎｔベースの特徴抽出  −ＳＩＦＴとＨＯＧ−」、情報処理学会研究報告  ＣＶＩＭ１６０、pp.211-224、２００７年
【非特許文献３】細井利憲、鈴木哲明、佐藤敦、「一般化学習ベクトル量子化による顔検出」、Technical report of IEICE. PRMU，Vol.102,No.651(20030213),pp.47-52
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記の第１条件における重要度や第２条件における特徴点抽出の精度は、認識対象物体の種類（形状や見え方）、画像から特徴点を抽出する方法の特性、認識タスク（姿勢推定や個体識別等）に用いる手法の特性、認識対象画像の撮影条件等の様々な要因に依存する。そのため、認識タスクを行うシステムを作り上げて稼働させるまで、第１条件における重要度や第２条件における特徴点抽出の精度は定量化することが難しかった。そのため、そのような重要度や精度をシステム開発者が主観的に見積もっていた。従って、熟達した開発者でなければ、３次元形状モデル上から、上記の第１条件および第２条件を満たす適切な特徴点を選択することが困難であり、認識タスクのアルゴリズム自体が持つ最大限の認識性能を得ることが困難であった。【００１１】
また、特徴点選択方法として、以下に示す方法が考えられる。すなわち、３次元形状モデルおよびその３次元形状モデル上の複数の特徴点候補が指定されると、その３次元形状モデルから、特徴点抽出器における判定用データの学習に用いる学習用画像と、認識タスクの評価に用いる評価用画像とを生成する。そして、特徴点に該当する局所領域および特徴点に該当しない局所領域を学習用画像から切り出し、特徴点に該当する局所領域および特徴点に該当しない局所領域により、判定用データを学習する。さらに、学習により得られた判定用データを用いて評価用画像から特徴点位置を抽出する。その特徴点位置に基づいて、認識タスクを実行したときの認識誤差を表す関数（コスト関数）を計算し、その関数の値が小さくなる特徴点を、抽出された複数の特徴点位置の中から選択する。この方法により、特徴点が得られる。【００１２】
また、抽出された特徴点位置の中から、認識誤差が少なくなる特徴点の集合を選択し、さらに、その特徴点の集合の中から、選択する特徴点の数を少なくして（換言すれば、一部の特徴点を除外して）、認識誤差が少なくなる特徴点の集合を選択することを繰り返す方法が考えられる。このように、逐次的に特徴点の数を、最終的に選択したい特徴点の数にまで逐次的に減らしていき、最終的に選択したい数の特徴点を選択する方法も考えられる。さらに、ある特徴点の集合から、一部の特徴点を除外したときの認識誤差を予測することも考えられる。【００１３】
しかし、認識誤差が少なくなる特徴点の集合を探索するようにして、逐次的に特徴点の数を減らしながら特徴点を決定した場合、特徴点の集合の最適化の初期段階（すなわち、選択する特徴点の数がまだ多数残っている状態）で、適切な特徴点を除外してしまって、適切な特徴点を除外したまま、特徴点を逐次的に減らしていってしまう場合が生じる。例えば、比較的重要度が低い点が多数残っている場合には、重要度を高く評価することができないような特徴点に関しては、最適化の初期段階で、特徴点の重要度の優劣の差が現れにくいために、選択することが困難となり、除外されてしまう場合がある。すると、最終的に選択したい数の特徴点を選択したときに、初期段階で重要度を高く評価できなかった特徴点が特徴点の集合から漏れてしまう。【００１４】
そこで、本発明は、認識タスクにおける認識アルゴリズムに合う適切な特徴点を選ぶことができ、また、重要な特徴点（認識タスクの精度に影響を与える特徴点）が最終的に選択した特徴点の集合から漏れにくくすることができる特徴点選択システム、特徴点選択方法および特徴点選択プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明による特徴点選択システムは、認識タスクに適した特徴点の候補となる点の集合である特徴点候補から、特徴点の集合である特徴点セットであって、定められた特徴点数の特徴点を含む特徴点セットを複数選択する特徴点セット選択手段と、特徴点セット選択手段に選択された特徴点セット毎に、特徴点セットに含まれる特徴点を用いて認識タスクを実行した場合における認識誤差を算出する認識誤差算出手段と、特徴点セット選択手段に選択された特徴点セット毎の認識誤差の最小値が、特徴点候補を用いて認識タスクを実行した場合における認識誤差より大きい場合に、特徴点セット毎に、特徴点候補を用いて認識タスクを実行した場合における認識誤差からの認識誤差の増加量の指数関数の逆数を計算し、その計算結果の値の大きさに応じて、一つの特徴点セットを選択し、特徴点セット選択手段が特徴点セットを選択する際の特徴点数を更新し、所定の条件が成立したときに認識タスクに適した特徴点を選択する特徴点選択手段とを備え、特徴点セット選択手段が、特徴点選択手段が特徴点セットを選択したときに、当該特徴点セットに基づいて特徴点候補を定め、再度、特徴点セットを複数選択することを特徴とする。【００１６】
また、本発明による特徴点選択方法は、認識タスクに適した特徴点の候補となる点の集合である特徴点候補から、特徴点の集合である特徴点セットであって、定められた特徴点数の特徴点を含む特徴点セットを複数選択し、選択した特徴点セット毎に、特徴点セットに含まれる特徴点を用いて認識タスクを実行した場合における認識誤差を算出し、選択した特徴点セット毎の認識誤差の最小値が、特徴点候補を用いて認識タスクを実行した場合における認識誤差より大きい場合に、特徴点セット毎に、特徴点候補を用いて認識タスクを実行した場合における認識誤差からの認識誤差の増加量の指数関数の逆数を計算し、その計算結果の値の大きさに応じて、一つの特徴点セットを選択し、複数の特徴点セットを選択する際の特徴点数を更新し、所定の条件が成立したときに認識タスクに適した特徴点を選択し、その一つの特徴点セットを選択したときに、当該特徴点セットに基づいて特徴点候補を定め、再度、特徴点セットを複数選択することを特徴とする。【００１７】
また、本発明による特徴点選択プログラムは、コンピュータに、認識タスクに適した特徴点の候補となる点の集合である特徴点候補から、特徴点の集合である特徴点セットであって、定められた特徴点数の特徴点を含む特徴点セットを複数選択する特徴点セット選択処理、特徴点セット選択処理で選択された特徴点セット毎に、特徴点セットに含まれる特徴点を用いて認識タスクを実行した場合における認識誤差を算出する認識誤差算出処理、および、特徴点セット選択処理で選択された特徴点セット毎の認識誤差の最小値が、特徴点候補を用いて認識タスクを実行した場合における認識誤差より大きい場合に、特徴点セット毎に、特徴点候補を用いて認識タスクを実行した場合における認識誤差からの認識誤差の増加量の指数関数の逆数を計算し、その計算結果の値の大きさに応じて、一つの特徴点セットを選択し、特徴点セット選択処理で特徴点セットを選択する際の特徴点数を更新し、所定の条件が成立したときに認識タスクに適した特徴点を選択する特徴点選択処理を実行させ、特徴点選択処理で特徴点セットを選択させたときに、特徴点セット選択処理で、当該特徴点セットに基づいて特徴点候補を定め、再度、特徴点セットを複数選択させることを特徴とする。
【発明の効果】
【００１８】
本発明によれば、認識タスクにおける認識アルゴリズムに合う適切な特徴点を選ぶことができ、また、重要な特徴点が最終的に選択した特徴点の集合から漏れにくくすることができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の第１の実施形態の特徴点選択システムの例を示すブロック図である。
【図２】特徴点選択手段が特徴点セット毎のＰｉに応じた確率で、特徴点セットを選択する処理を模式的に表す説明図である。
【図３】第１の実施形態の処理経過の例を示すフローチャートである。
【図４】認識タスクの総実行時間と認識誤差との関係を示す説明図である。
【図５】本発明の第２の実施形態の特徴点選択システムの例を示すブロック図である。
【図６】第２の実施形態の処理経過の例を示すフローチャートである。
【図７】本発明の最小構成の例を示すブロック図である。
【発明を実施するための形態】
【００２０】
以下、本発明の実施形態を図面を参照して説明する。
【００２１】
実施形態１．
図１は、本発明の第１の実施形態の特徴点選択システムの例を示すブロック図である。第１の実施形態の特徴点選択システムは、特徴点抽出学習・評価データ生成手段４１（以下、特抽学習・評価データ生成手段４１と記す。）と、特徴点抽出器学習手段４５と、特徴点位置検出手段４６と、特徴点セット選択手段５１と、認識誤差算出手段５２と、特徴点選択手段５３とを備える。また、特抽学習・評価データ生成手段４１は、学習データ生成手段４２と、学習パターン生成手段４３と、評価データ生成手段４４とを有する。
【００２２】
特抽学習・評価データ生成手段４１は、３Ｄ形状モデルと、その３Ｄ形状モデル上の複数の特徴点を指定する情報と、認識タスクで用いられるテンプレート（局所領域）の大きさとが入力される。また、テンプレートの大きさをテンプレートサイズと記す。３Ｄ形状モデルにはテクスチャが貼り付けられているものとする。特抽学習・評価データ生成手段４１は、入力された３Ｄ形状モデルの姿勢（向き）や、３Ｄ形状モデルに対する照明の位置等を様々に変更した画像（学習データおよび評価データ）をＣＧ（Computer Graphics ）画像として生成する。
【００２３】
ここで、特徴点抽出器と、学習データおよび評価データとについて説明する。特徴点抽出器は、あるパターンが入力されたときにそのパターンが特徴点であるか否かを判定する。また、特徴点抽出器は、そのような判定を行うための内部データを予め学習しておく。特徴点抽出器には様々なパターン識別法や特徴抽出演算子を利用可能である。
【００２４】
一例として、非特許文献２に記載のＳＩＦＴ特徴量を用いることができる。この場合、学習の際、学習データの特徴点に該当する位置に対してＳＩＦＴ特徴抽出演算子を適用し、ＳＩＦＴ特徴量を抽出する。そして、そのＳＩＦＴ特徴量を内部データとして記憶しておく。認識タスク等において、ある認識対象となる画像が入力されると、その画像からＳＩＦＴ特徴量を抽出し、内部データを比較することにより、そのテンプレートが特徴点に該当するか否かを判定する。また、別の方法として、非特許文献３に記載のＧＬＶＱのようなパターン識別法を用いることもできる。本実施形態では、これらの方法について詳しく説明する。学習においては、特徴点に該当するテンプレートと、特徴点に該当しないテンプレートをそれぞれ複数入力され、そのテンプレートから内部データを生成する。そして、特徴点抽出器は、認識タスク等において、あるテンプレートが入力されると、内部データと比較することにより、そのテンプレートが特徴点に該当するか否かを判定する。特徴点抽出器が内部データを学習するためのテンプレートを切り出すために用いられる画像を学習データと記す。また、内部データ学習後の特徴点抽出器が入力されたテンプレートに対する判定を適切に行うか否かを評価するために用意される画像を評価データと記す。
【００２５】
特抽学習・評価データ生成手段４１の学習データ生成手段４２は、上記の学習データを生成する。また、特抽学習・評価データ生成手段４１の評価データ生成手段４４は、上記の評価データを生成する。学習データ生成手段４２および評価データ生成手段４４は、いずれも、３Ｄ形状モデルの姿勢（向き）や、３Ｄ形状モデルに対する照明の位置等を様々に変更した画像をＣＧ（Computer Graphics ）画像として生成する。ただし、３Ｄ形状モデルの姿勢（向き）や３Ｄ形状モデルに対する照明の位置等の条件は、学習データ生成時と評価データ生成時で異なるようにする。学習データ生成手段４２および評価データ生成手段４４は、画像生成時の条件が異なる点を除き、同様の処理を行ってそれぞれＣＧ画像（学習データ、評価データ）を生成する。学習データや評価データは複数生成されてもよい。
【００２６】
また、学習データ生成手段４２は、入力された情報によって指定される特徴点に対応する特徴点を学習データ中から特定する。同様に、評価データ生成手段４４は、入力された情報によって指定される特徴点に対応する特徴点を評価データ中から特定する。
【００２７】
特抽学習・評価データ生成手段４１の学習パターン生成手段４３は、学習データから、特徴点に該当するテンプレートと、特徴点に該当しないテンプレートを複数切り出す。特徴点に該当するテンプレートとして、学習データにおける特徴点やその近辺の点を中心とし、テンプレートサイズによって決まるテンプレートを学習データから複数切り出せばよい。また、特徴点に該当しないテンプレートとして、その特徴点の周囲の点を中心とするテンプレートであって特徴点を含まないテンプレートを学習データから複数切り出せばよい。このとき、学習データ中の特徴点として、学習データ生成手段４２が特定した特徴点を用いればよい。
【００２８】
特徴点抽出器学習手段４５は、特徴点抽出器の内部データを学習する。すなわち、与えられるパターンが特徴点であるか否かを判定するための特徴点抽出器の内部データを生成する。特徴点抽出器学習手段４５は、特徴点に該当する複数のテンプレートおよび特徴点に該当しない複数のテンプレートを参照して内部データを学習する。
【００２９】
特徴点位置検出手段４６は、特徴点抽出器学習手段４５で学習した内部データを用いて、評価データ生成手段４４が生成した評価データから特徴点の位置を抽出し、その特徴点位置の情報を特徴点セット選択手段５１に入力する。具体的には、特徴点位置検出手段４６は、特徴点抽出器が特徴点であるか否かを判定するテンプレートサイズの画像を評価データの各位置から切り出す。そして、特徴点抽出器学習手段４５が学習した内部データを用いて、そのテンプレートサイズの画像が特徴点に該当するか否かを判定することによって、どこに特徴点があるのかを決定する。
【００３０】
特徴点位置検出手段４６によって判定された特徴点位置における特徴点群の中から、最適な特徴点の集合が定められる。なお、３Ｄ形状モデルの入力時に指定される特徴点の数と、特徴点位置検出手段４６によって判定された特徴点位置における特徴点の数は同数である。以下、特徴点位置検出手段４６によって判定された特徴点位置における特徴点群を初期特徴点候補と記す場合がある。
【００３１】
特徴点セット選択手段５１は、特徴点位置検出手段４６によって判定された特徴点位置における特徴点群を特徴点の候補とし、その特徴点の候補の中から一部の特徴点を選択する。この特徴点の候補から選択される複数の特徴点を特徴点セットと記す。特徴点セットに含める特徴点の数が定められると、特徴点セット選択手段５１は、その数の特徴点を含む特徴点セットを一組だけでなく、選び得る各通り選択する。
【００３２】
認識誤差算出手段５２は、特徴点セット選択手段５１が定めた各特徴点セットについて、特徴点セットに含まれる特徴点の位置を用いて認識タスクを実行したときの認識誤差を算出する。認識タスクの種類は特に限定されない。例えば、認識誤差算出手段５２は、認識タスクとして、姿勢推定を行っても、あるいは、顔識別等の個体識別を行ってもよい。また、例えば、認識タスクとして、顔画像に対する表情認識処理（表情推定）や年齢推定処理を行ってもよい。
【００３３】
認識誤差算出手段５２は、例えば、認識タスクを実行するコンピュータのＣＰＵによって実現される。また、特徴点抽出器学習手段４５が内部データを学習する処理、および、認識誤差算出手段５２がテンプレートと内部データとを比較してテンプレートが特徴点に該当するか否かを判定する処理は、特徴点抽出器としての動作である。特徴点抽出器学習手段４５および認識誤差算出手段５２は、例えば、認識タスクにおいて用いられる特徴点抽出器として動作するコンピュータのＣＰＵによって実現される。
【００３４】
認識誤差算出手段５２は、特徴点セットを用いて認識タスクを行う毎に、その認識タスクの認識結果で生じた認識誤差を求める処理も行う。認識誤差は、認識タスクで得られた認識結果と、正解との差である。例えば、認識タスクが姿勢推定であるとすると、認識誤差算出手段５２は、評価データに対して特徴点セットを用いて姿勢推定を行った結果得た姿勢（向き）と正解となる姿勢との差を認識誤差として計算すればよい。また、認識タスクとして顔識別を行う場合、複数の人物について３Ｄ形状モデルおよびその３Ｄ形状モデル上の複数の特徴点を指定する情報を入力しておき、各人物の評価データを作成しておく。そして、その評価データに対して特徴点セットを用いて顔認識を行った結果、顔認識に失敗した人物の割合を認識誤差として計算してもよい。
【００３５】
特徴点選択手段５３は、特徴点セットが定めた特徴点セットの中から、各特徴点セットの認識誤差を用いて、一つの特徴点セットを定める。
【００３６】
特徴点セット選択手段５１は、特徴点選択手段５３によって定められた一つの特徴点セットを特徴点の候補として、その特徴点の候補の中から一部の特徴点を選択する。すなわち、特徴点セットを選択する。このときにも、特徴点セット選択手段５１は、特徴点セットを一組だけでなく、選び得る各通り選択する。
【００３７】
この結果、特徴点セット選択手段５１による複数の特徴点セットの選択、認識誤差算出手段５２による特徴点セット毎の認識誤差の算出、特徴点選択手段５３による、その複数の特徴点セットの中からの一つの特徴点セットの選択が繰り返されることになる。そして、特徴点選択手段５３が複数の特徴点セットから一つの特徴点セットを選択したときに、その特徴点セットに含まれる特徴点数が最終的にユーザの所望する特徴点数になっていれば、特徴点選択手段５３は、その特徴点セットに含まれる特徴点群を、認識タスクにおける認識アルゴリズムに合う適切な特徴点として決定する。なお、上記の繰り返し処理は、後述のステップＳ２１〜Ｓ２６（図３参照）の繰り返し処理に相当する。
【００３８】
そして、特徴点選択手段５３は、複数の特徴点セットの中からの一つの特徴点セットを選択したときに、次に、特徴点セット選択手段５１が特徴点セットを選択する際にその特徴点セットに含めるべき特徴点の数を定める。例えば、複数の特徴点セットの中からの一つの特徴点セットを選択したときに、その特徴点セットに含まれる特徴点数から一定数を減算した値を、次に特徴点セット選択手段５１が特徴点セットに含める特徴点数として定める。この減算する一定数の値は、予め定めておけばよい。
【００３９】
ただし、特徴点セット選択手段５１は、一定の確率で、特徴点選択手段５３が選択した一つの特徴点セットに対して、その特徴点セットには含まれていないが、初期特徴点候補に含まれる特徴点を含めるようにする。例えば、特徴点選択手段５３が選択した一つの特徴点セットに対して、初期特徴点候補に含まれる特徴点を追加してもよい。あるいは、特徴点選択手段５３が選択した一つの特徴点セット内の一部の特徴点を、初期特徴点候補に含まれる特徴点に入れ替えてもよい。特徴点選択手段５３が選択した一つの特徴点セットに対して、一定の確率で新たに含めるようにする特徴点の個数は、例えば、予め定めておけばよい。また、特徴点選択手段５３が選択した一つの特徴点セットに対して、一定の確率で新たに特徴点を含める場合、その特徴点は、特徴点選択手段５３が選択した特徴点セットには含まれていないが初期特徴点候補に含まれる特徴点の中からランダムに選択すればよい。また、特徴点選択手段５３が選択した一つの特徴点セット内の一部の特徴点を他の特徴点に入れ替える場合にも、入れ替える特徴点はランダムに選択すればよい。このように、特徴点選択手段５３が選択した一つの特徴点セットに対して、ランダムに特徴点を含めるようにした場合には、特徴点セット選択手段５１は、その特徴点を含めた特徴点セットの中から、その一部の特徴点群を特徴点セットとして選択していく。以下の説明では、特徴点選択手段５３が選択した一つの特徴点セットに対して、特徴点セット選択手段５１が一定の確率で特徴点を追加する場合を例にして説明する。
【００４０】
例えば、９０個の特徴点を含む複数の特徴点セットの中から、特徴点選択手段５３が、１つの特徴点セットを選択し、次に特徴点セット選択手段５１が特徴点セットを選択する場合、８９個の特徴点を含む特徴点を選択すると定めたとする。特徴点セット選択手段５１は、その１つの特徴点セット（特徴点数は９０個）から、８９個の特徴点からなる特徴点セットを各通り選択していけばよい。ただし、特徴点セット選択手段５１は、毎回このような動作をするのではなく、一定の確率で、その１つの特徴点セット（上記の例では特徴点数は９０個）に対して、初期特徴点候補からランダム選択した特徴点（例えば、５個の特徴点）を追加する。そして、特徴点セット選択手段５１は、その特徴点を追加した後の特徴点セット（本例では９５個の特徴点を含む特徴点セット）を特徴点の候補とし、その特徴点候補の中から、その一部の特徴点群を特徴点セットとして選択していく。
【００４１】
また、このように、一定の確率のもとで、特徴点セット選択手段５１が、選択された特徴点セットに対して特徴点を追加した場合には、特徴点選択手段５３が次回の特徴点セット選択時における特徴点数として定めた数も、増加させてもよい。この特徴点数の増加数は、例えば、予め定めておけばよい。例えば、上記の例のように、特徴点セット選択手段５１が、９０個の特徴点からなる特徴点セットに特徴点を追加した場合には、特徴点セット選択手段５１は、特徴点選択手段５３が定めた特徴点数（８９個）も増加させて、例えば、９２個とし、９５個の特徴点候補の中から、９２個の特徴点を含む特徴点セットを各通り選択していけばよい。以下の説明では、このように、特徴点セット選択手段５１が、選択された特徴点セットに対して特徴点を追加した場合には、特徴点選択手段５３が次回の特徴点セット選択時における特徴点数として定めた数も増加させる場合を例にして説明する。
【００４２】
また、特徴点セット選択手段５１は、選択された特徴点セットに対して特徴点を追加するか否かを、以下のように判定すればよい。例えば、上記の「一定の確率」がＫ（０＜Ｋ＜１）であるとすると、特徴点セット選択手段５１は、０より大きく１未満の範囲で乱数を発生させ、その値がＫ以下であれば、特徴点選択手段５３に選択された一つの特徴点セットに対して特徴点を追加し、特徴点追加後の特徴点セットを新たな特徴点候補とすればよい。また、発生させた乱数がＫより大きい値であれば、特徴点選択手段５３に選択された一つの特徴点セットをそのまま新たな特徴点候補とすればよい。なお、このように乱数を用いる方法は、特徴点選択手段５３に選択された特徴点セットに対して一定の確率で特徴点を追加する方法の一例であり、他の方法を用いてもよい。
【００４３】
また、上記の説明では、特徴点セット選択手段５１、認識誤差算出手段５２および特徴点選択手段５３による繰り返し処理を行い、特徴点選択手段５３が複数の特徴点セットから一つの特徴点セットを選択したときに、その特徴点セットに含まれる特徴点数が最終的にユーザの所望する特徴点数になっていれば、特徴点選択手段５３は、その特徴点セットに含まれる特徴点群を、認識タスクにおける認識アルゴリズムに合う適切な特徴点として決定するものとして説明した。特徴点セット選択手段５１は、最初に複数の特徴点セットを選択するときに、特徴点位置検出手段４６によって判定された特徴点位置における特徴点群の中から、ユーザの所望する数の特徴点を含む特徴点セットを選び得る各通り選択してもよい。
【００４４】
ただし、多数の初期特徴点候補の中から、一度の処理で少数の特徴点からなる特徴点セットを選択すると、選択し得る特徴点セットの数が膨大になる。例えば、初期特徴点候補の数をＮとし、ユーザの所望の特徴点数をＭとすると、選択し得る特徴点セットの数は、ＮＣＭとなる。ここで、ＭがＮに比べて小さいと、ＮＣＭの値は膨大となり、現実的な計算時間でユーザの所望数の最適な特徴点を決定することが困難になる。よって、既に説明したように、初期特徴点候補から、段階的に特徴点数を削減しながら、特徴点セットを選択していき、ユーザの所望数の特徴点を決定することが好ましい。
【００４５】
次に、特徴点選択手段５３について、より詳細に説明する。特徴点選択手段５３は、特徴点セット選択手段５１がある個数の特徴点からなる特徴点セットを選び得る各通り選択した場合、その特徴点セットの中から、認識誤差が最小となる特徴点セットを選択する。ただし、その最小となる認識誤差が、特徴点選択手段５３が前回選択した特徴点セットを用いて認識タスクを行ったときの認識誤差（特徴点選択手段５３が初回に特徴点セットを選択する場合には、初期特徴点候補を用いて認識タスクを行ったときの認識誤差）よりも大きくなる場合には、以下のように特徴点セットを選択する。すなわち、各特徴点セットｉについて、認識誤差の増加分ａｉを求める。認識誤差の増加分ａｉは、特徴点セットｉを用いて認識タスクを行ったときの認識誤差から、特徴点選択手段５３が前回選択した特徴点セットを用いて認識タスクを行ったときの認識誤差（特徴点選択手段５３が初回に特徴点セットを選択する場合には、初期特徴点候補を用いて認識タスクを行ったときの認識誤差）を減算した値である。そして、特徴点選択手段５３は、各特徴点セットｉについて求めた認識誤差の増加分ａｉを用いて、以下に示す式（１）で算出される値Ｐｉを計算する。
【００４６】
【数１】
2012032747.tif 000003
【００４７】
式（１）から分かるように、Ｐｉは、認識誤差の増加量ａｉの指数関数の逆数である。また、後述するように、このＰｉは、特徴点セットｉの選択確率を所定数倍したものである。
【００４８】
そして、特徴点選択手段５３は、各特徴点セットのＰｉに応じた確率で、特徴点セットを一つ選択する。図２は、特徴点選択手段５３が特徴点セット毎のＰｉに応じた確率で、特徴点セットを選択する処理を模式的に表す説明図である。図２に示す例では、説明を簡単にするため、特徴点セットが特徴点セット１〜３の３つであり、特徴点セット毎にＰ１，Ｐ２，Ｐ３を求めた場合を示している。特徴点選択手段５３は、例えば、０より大きくＰ１＋Ｐ２＋Ｐ３以下の範囲で乱数を発生させる。そして、特徴点選択手段５３は、その乱数値が０より大きくＰ１以下であれば特徴点セット１を選択し、乱数値がＰ１より大きくＰ１＋Ｐ２以下であれば特徴点セット２を選択し、乱数値がＰ１＋Ｐ２より大きくＰ１＋Ｐ２＋Ｐ３以下であれば、特徴点セット３を選択する。このように選択することで、各特徴点セットのＰｉに比例した確率で、特徴点セットを一つ選択することができる。このように、特徴点選択手段５３は、Ｐｉの値が大きいほど選択されやすく、Ｐｉの値が小さいほど選択されにくくするという条件のもとで、特徴点セットを一つ選択する。ここでは、乱数を用いた場合を例に説明したが、他の方法で、特徴点セットを選択してもよい。
【００４９】
上記の特徴点セット毎に算出したＰｉは、特徴点セットの選択確率を所定数倍した値である。すなわち、特徴点セットｉの選択確率をｐｉとすると、特徴点セット毎の選択確率ｐｉの総和は１となるので、ｐｉ＝（１／ΣＰｉ）Ｐｉである。よって、式（１）のＰｉは、特徴点セットの選択確率ｐｉをΣＰｉ倍した値である。ここで、ΣＰｉは、特徴点セット毎に算出したＰｉの総和である。
【００５０】
また、式（１）におけるＴの値は、例えば、特徴点選択手段５３が特徴点セットを選択する処理の回数が増えていき、選択される特徴点セットに含まれる特徴点数の数が、最終的にユーザが所望する特徴点数に近づくにつれて小さくしていけばよい。例えば、特徴点選択手段５３が特徴点セットを選択する処理の回数がｔ回目の時におけるＴの値をＴｔと表すことにする。この場合、特徴点選択手段５３が特徴点セットを選択する処理の回数がｔ＋１回目になったときのＴｔ＋１は、以下に示す式（２）によって求めればよい。
【００５１】
Ｔｔ＋１＝γ・Ｔｔ                  式（２）
【００５２】
式（２）において、γは１以下の定数であり、特に、１未満とすることが好ましい。具体的には、γは０．８〜０．９程度の定数とすることが好ましい。
【００５３】
上記の変数Ｔは、シミュレーテッドアニーリング（Simulated Annealing ）による最適化（ここでは特徴点セットの最適化）における温度に相当するということが言え、以下、変数Ｔを温度と称する場合がある。また、式（２）は、シミュレーテッドアニーリングによる最適化における冷却関数に相当するということが言え、以下、式（２）を冷却関数と称する場合がある。
【００５４】
ただし、特徴点セット選択手段５１が選択する特徴点セットに含まれる特徴点数が多いときには、温度Ｔが高いと、不適切な特徴点を選択する可能性が高くなりすぎる。そこで、特徴点セット選択手段５１が選択する特徴点セットに含まれる特徴点数がある程度小さくなるまでは（すなわち、特徴点数に関して予め定めた閾値より小さくなるまでは）、特徴点選択手段５３は、最小となる認識誤差が、特徴点選択手段５３が前回選択した特徴点セットを用いて認識タスクを行ったときの認識誤差より大きい場合であっても、認識誤差が最小となる特徴点セットを選択することが好ましい。そして、特徴点セット選択手段５１が選択する特徴点セットに含まれる特徴点数が閾値より小さくなっていて、最小となる認識誤差が、特徴点選択手段５３が前回選択した特徴点セットを用いて認識タスクを行ったときの認識誤差より大きい場合には、各特徴点セットのＰｉに応じた確率で、特徴点セットを一つ選択することが好ましい。最小となる認識誤差が、特徴点選択手段５３が前回選択した特徴点セットを用いて認識タスクを行ったときの認識誤差以下ならば、特徴点選択手段５３は、認識誤差が最小となる特徴点セットを選択する。
【００５５】
特抽学習・評価データ生成手段４１（学習データ生成手段４２、学習パターン生成手段４３および評価データ生成手段４４）、特徴点抽出器学習手段４５、特徴点位置検出手段４６、特徴点セット選択手段５１、認識誤差算出手段５２、特徴点選択手段５３は、例えば、特徴点選択プログラムに従って動作するコンピュータのＣＰＵによって実現される。例えば、ＣＰＵが、特徴点選択システムの記憶装置（図示せず。）から特徴点選択プログラムを読み込み、そのプログラムに従って、上記の各手段として動作してもよい。あるいは、各手段がそれぞれ別々の専用回路によって実現されていてもよい。
【００５６】
次に、動作について説明する。
図３は、第１の実施形態の処理経過の例を示すフローチャートである。特抽学習・評価データ生成手段４１に３Ｄ形状モデルと、その３Ｄ形状モデル上の複数の特徴点を指定する情報と、テンプレートサイズが入力されると、学習データ生成手段４２は、その３Ｄ形状モデルの姿勢や、３Ｄ形状モデルに対する照明の位置を様々に変化させた複数の画像をＣＧ画像として生成することにより、複数の学習データを生成する（ステップＳ１１）。ステップＳ１１で生成する複数の画像が学習データ群である。また、ステップＳ１１で入力される３Ｄ形状モデルは、一つの個体の３Ｄ形状モデルであっても、複数の個体の３Ｄ形状モデルであってもよい。例えば、一人の人物の顔の３Ｄ形状モデルが入力されても、複数の人物の顔の３Ｄ形状モデルが入力されてもよい。また、ここでは、顔の３Ｄ形状モデルを例示したが、３Ｄ形状モデルは顔以外のモデルであってもよい。なお、入力された情報によって指定される特徴点の数は、例えば１００００個以上等のように多数であってもよい。また、このような特徴点として、例えば、エッジが強く現れている点等を指定すればよい。
【００５７】
次に、学習データ生成手段４２は、入力された情報によって指定される各特徴点に対応する学習データ中の各特徴点を特定する（ステップＳ１２）。続いて、学習パターン生成手段４３が、学習データ群から、特徴点に該当するテンプレートおよび特徴点に該当しないテンプレートをそれぞれ複数切り出す（ステップＳ１３）。学習パターン生成手段４３は、ステップＳ１２で特定された各特徴点およびその近辺の点を中心とするテンプレートを、特徴点に該当するテンプレートとして切り出す。また、ステップＳ１２で特定された各特徴点の周囲の点を中心とし特徴点を含まないテンプレートを、特徴点に該当しないテンプレートとして切り出す。いずれのテンプレートの大きさも、テンプレートサイズによって指定された大きさである。
【００５８】
次に、特徴点抽出器学習手段４５は、ステップＳ１３で切り出された「特徴点に該当する複数のテンプレート」および「特徴点に該当しない複数のテンプレート」を参照して、特徴点毎に、特徴点抽出器の内部データを学習する（ステップＳ１４）。
【００５９】
また、評価データ生成手段４４は、特抽学習・評価データ生成手段４１に入力された３Ｄ形状モデルの姿勢や、３Ｄ形状モデルに対する照明の位置を様々に変化させた複数の画像をＣＧ画像として生成することにより、複数の評価データを生成する（ステップＳ１５）。ステップＳ１４で生成する複数の画像が評価データ群である。ステップＳ１５では、３Ｄ形状モデルの姿勢や、照明位置の条件を学習データ生成時（ステップＳ１１）とは変えて評価データを生成する。
【００６０】
特徴点位置検出手段４６は、評価データ生成手段４４に生成された評価データからテンプレートを切り出し、テンプレートと内部データとを比較して、そのテンプレートが特徴点に該当するか否かを判定する。この判定により、評価データにおけるどの部分が特徴点であるかを判定する（ステップＳ１６）。
【００６１】
ステップＳ１６で特徴点位置検出手段４６によって判定された特徴点位置における特徴点群が、初期特徴点候補であり、以降の処理で、初期特徴点候補から、認識アルゴリズムに合う適切な特徴点が選択される。
【００６２】
また、特抽学習・評価データ生成手段４１に対して指定された複数の特徴点の数と、ステップＳ１６で判定される特徴点位置の数は同数となる。
【００６３】
なお、本実施形態では、学習データ生成手段４２および評価データ生成手段４４が３Ｄ形状モデルからＣＧ画像として学習データや評価データを生成する場合を例に説明しているが、その３次元形状モデルを撮影した実際の画像が入手可能な場合には、その実際の画像を学習データや評価データとして用いてもよい。その場合、特徴点選択システムは、学習データ生成手段４２や評価データ生成手段４４を備えていなくてよい。さらに、認識タスクで用いる特徴点の位置データを特徴点選択システムの外部の特徴点抽出器から取得して利用してもよい。すなわち、外部の特徴点抽出器が検出した特徴点の位置データを取得して、その位置データに対応する特徴点群を初期特徴点候補としてもよい。この場合、特徴点選択システムは、特徴点抽出器学習手段４５および特徴点位置検出手段４６を備えていなくてもよい。なお、本実施形態では、ステップＳ１６で判定した特徴点位置における特徴点を初期特徴点候補として、以降の処理を行う場合を例にして説明する。
【００６４】
特徴点選択システムは、ステップＳ１６までの処理を行った後、以下の処理を行う。まず、特徴点セット選択手段５１は、特徴点位置検出手段４６によって判定された特徴点位置における特徴点群を特徴点の候補とし、その特徴点の候補から特徴点セットを選択する（ステップＳ２１）。最初にステップＳ２１に移行した場合には、特徴点セット選択手段５１は、初期特徴点候補となる特徴点数から一定数を減算した数を求め、その数の特徴点を含む特徴点セットを選択する。
【００６５】
なお、特徴点セット選択手段５１は、特徴点数が定められているという条件のもとで、特徴点セットを選び得る各通り選択するが、特徴点セット選択手段５１は、ステップＳ２１に移行する毎に、１つずつ特徴点セットを選択する。後述するように、ステップＳ２１、Ｓ２２，Ｓ２３のループ処理を未選択の特徴点セットがなくなるまで繰り返し、この繰り返し処理でステップＳ２１に複数回移行することで、特徴点セット選択手段５１は、特徴点セットを選び得る各通り選択する。このステップＳ２１〜Ｓ２３の繰り返し処理において選択される各特徴点セットの特徴点数は共通である。
【００６６】
本実施形態では、特徴点セット選択手段５１が、特徴点セットを選び得る各通り選択する場合を例に説明する。このように、特徴点セットを各通り選択することが好ましいが、特徴点セットの数が多くなり計算量が多くなるのであれば、特徴点セット選択手段５１は、定められた特徴点数のもとで選択し得る各通りの特徴点セットの中から、一部の特徴点セットをランダムに複数個選択してもよい。望ましい方法は、第２の実施形態で説明するように、現在の候補から特定の点を除去した組み合わせにした場合に、認識誤差の増大量が多い特徴点を優先的に除外するように、特徴点を選択する確率に重みを付けて特徴点毎に特徴点セットに含めるかどうかを決定することがこのましい。なお、第１の実施形態では、上述のように、選び得る各通りの特徴点セットを選択する場合を例にする。
【００６７】
また、既に説明したように、特徴点セット選択手段５１は、最初に複数の特徴点セットを選択するときに（すなわち、最初にステップＳ２１〜Ｓ２３の繰り返し処理を行うときに）、初期特徴点候補の中から、ユーザの所望する数の特徴点を含む特徴点セットを選び得る各通り選択してもよい。しかし、例えば、初期特徴点候補の数が１００００個等のように多く、一方、ユーザの所望する特徴点数が初期特徴点候補に対して大幅に少ない場合（例えば、１０個等）、特徴点セットの数が膨大になる。すると、ステップＳ２１〜Ｓ２３の繰り返し処理の回数も膨大となり、処理時間がかかりすぎてしまう。そこで、最初にステップＳ２１〜Ｓ２３の繰り返し処理を行う場合には、初期特徴点候補の数よりも僅かに少ない数の特徴点を含む特徴点セットを各通り選択すればよい。また、後述のステップＳ２６では、ステップＳ２４で選択される特徴点セットに含まれる特徴点数より僅かに少ない数の特徴点数を、更新後の特徴点数として定めればよい。この特徴点数の減少量は、予め定めておけばよい。
【００６８】
ステップＳ２１で特徴点セットが選択されると、認識誤差算出手段５２は、その特徴点セットに属する各特徴点を用いて、ステップＳ１５で生成された評価データに対して認識タスクを実行する（ステップＳ２２）。認識タスクの種類は、本発明による特徴点選択が確定した後に、その特徴点を用いて実行する認識タスクであればよい。例えば、姿勢推定、個体識別、表情推定、年齢推定等が挙げられるが、他の認識タスクを行ってもよい。認識タスクの処理過程において、評価データから得られるテンプレートと、ステップＳ１４で学習された特徴点抽出器の内部データとにより、そのテンプレートが特徴点に該当するか否かを判定する。認識タスクの処理の例については後述する。
【００６９】
また、認識タスク実行手段５２は、認識タスクを実行するとともに、ステップＳ２１で選択された特徴点セットについて認識誤差も計算する。
【００７０】
続いて、特徴点セット選択手段５１は、特徴点の候補から特徴点セットとして選択されていない特徴点の組み合わせがあるか否かを判定する（ステップＳ２３）。すなわち、未だ選択されておらず、ステップＳ２２で認識誤差が計算されていない特徴点セットがあるか否かを判定する。未選択の特徴点セットがあれば（ステップＳ２３におけるＹｅｓ）、特徴点セット選択手段５１および認識誤差算出手段５２は、ステップ２１〜Ｓ２３の処理を繰り返す。この結果、選び得る各通りの特徴点セットについて認識誤差が算出される。
【００７１】
ステップＳ２３において、未選択の特徴点セットがなければ（ステップＳ２３におけるＮｏ）、特徴点選択手段５３は、認識誤差が最小となる特徴点セットを選択する（ステップＳ２４）。ステップＳ２４で選択された特徴点セットの認識誤差が、ステップＳ２１で選択された各特徴点セットの中で最小となっているので、その特徴点セットが認識タスクの認識アルゴリズムにとって好ましいと言うことができる。
【００７２】
ただし、一般に、認識タスクに用いる特徴点の数を削減すると、認識誤差は大きくなる。従って、ステップＳ２１で選択した各特徴点セットの中で最小の認識誤差であっても、特徴点数を削減する前の特徴点セットを用いた場合の選択誤差よりも大きくなる。ステップＳ２４では、認識誤差が最小となる特徴点セットを選択することを原則とするが、その最小となる認識誤差が、特徴点選択手段５３が前回のステップＳ２４で選択した特徴点セットを用いて認識タスクを行ったときの認識誤差（特徴点選択手段５３が最初にステップＳ２４に移行して特徴点セットを選択する場合には、初期特徴点候補を用いて認識タスクを行ったときの認識誤差）よりも大きい場合には、ステップＳ２１で選択した各特徴点セットについて認識誤差の増加分ａｉを計算し、前述の式（１）で算出される値Ｐｉを計算する。なお、ａｉは、前回のステップＳ２４で選択した特徴点セットについて算出した認識誤差（最初にステップＳ２４に移行した場合には初期特徴点候補を用いて認識タスクを行ったときの認識誤差）から、着目している特徴点セットについて算出した認識誤差への増加量である。また、Ｐｉは、既に説明したように、Ｐｉに対応する特徴点セットｉの選択確率ｐｉを所定数倍（ΣＰｉ倍）した値である。
【００７３】
また、既に説明したように、特徴点選択手段５３が特徴点セットを選択する処理（ステップＳ２４）に移行した回数がｔ回目のときのＴの値をＴｔと表すこととし、ステップ２４に移行した回数がｔ＋１回目のときのＴの値をＴｔ＋１とし、γを１以下の定数（１未満であることが好ましい）とすると、式（１）における温度Ｔは、例えば、前述の式（２）によって、ステップＳ２４の実行時毎に計算すればよい。
【００７４】
また、特徴点セット選択手段５１が選択する特徴点セットに含まれる特徴点数が多いときには、温度Ｔが高いと、不適切な特徴点を選択する可能性が高くなりすぎる。よって、特徴点セット選択手段５１が選択する特徴点セットに含まれる特徴点数が予め定めた閾値より小さくなるまでは、各特徴点セットの認識誤差のうち最小となる認識誤差が、ステップＳ２１〜Ｓ２６の繰り返し処理における前回のステップＳ２４で選択した特徴点セットで認識タスクを行ったときの認識誤差より大きい場合であっても、認識誤差が最小となる特徴点セットを選択することが好ましい。
【００７５】
ステップＳ２４の後、特徴点選択手段５３は、ステップＳ２４で選択した特徴点セットに属する特徴点の数が、ユーザの所望の特徴点数（換言すれば、最終的に選択する特徴点数）になったか否かを判定する（ステップＳ２５）。ステップＳ２４で選択した特徴点セットに属する特徴点の数がユーザの所望の特徴点数になっていれば（ステップＳ２５におけるＹｅｓ）、特徴点選択手段５３は、その特徴点セットに属する特徴点を、認識アルゴリズムに適した特徴点として決定し、処理を終了する。このとき、その特徴点群の情報を出力してもよい。なお、ユーザの所望の特徴点数は、例えば、予め特徴点選択手段５３が記憶していてもよい。あるいは、ステップＳ１１以降の処理の開始前に、事前に外部から入力されていてもよい。
【００７６】
このように、ステップＳ２４で選択した特徴点セットに属する特徴点の数がユーザの所望の特徴点数になった場合、特徴点選択手段５３は、ステップＳ２１〜Ｓ２６の繰り返し処理を停止して、処理を終了する。このとき、特徴点選択手段５３は、直近のステップＳ２１〜Ｓ２３の繰り返し処理で選択された複数の特徴点セットのうち、認識誤差が最小となる特徴点セットに属する特徴点を認識アルゴリズムに適切な特徴点として決定してもよい。
【００７７】
ステップＳ２４で選択した特徴点セットに属する特徴点の数がユーザの所望の特徴点数になっていなければ（具体的には、ユーザの所望の特徴点数よりも多ければ）、特徴点選択手段５３は、ステップＳ２１に戻ったときに特徴点セット選択手段５１が特徴点セットに含める特徴点の数を更新する（ステップＳ２６）。ステップＳ２６では、特徴点選択手段５３は、ステップＳ２４で選択した特徴点セットに属する特徴点の数から一定数を減算した値を、新たな特徴点数として定めればよい。この減算する値は予め定めておけばよい。
【００７８】
ステップＳ２６の後、特徴点選択システムは、ステップＳ２１以降の処理を繰り返す。ステップＳ２６からステップＳ２１に戻ったときには、特徴点セット選択手段５１は、ステップＳ２４で選択された一つの特徴点セットを特徴点の候補として、その特徴点の候補の中から、ステップＳ２６で更新された特徴点数の特徴点を含む特徴点セットを選択する。そして、認識誤差算出手段５２が、その特徴点セットに属する特徴点を用いて評価データに対する認識タスクを実行し、そのときの認識誤差を算出する（ステップＳ２２）。ステップＳ２６で更新された特徴点数の特徴点を含む特徴点セットが全て選択された否かを判定し（ステップＳ２３）、その特徴点セットが全て選択し、各特徴点セットについて認識誤差を算出するまで、ステップＳ２１〜２３の繰り返し処理を行う。
【００７９】
ただし、ステップＳ２６からステップＳ２１に戻ったときに、特徴点セット選択手段５１は、一定の確率で、ステップＳ２４で特徴点選択手段５３が選択した特徴点セットに対して、その特徴点セットには含まれていないが、初期特徴点候補に含まれる特徴点を含める。本例では、特徴点セット選択手段５１は、ステップＳ２４で選択された特徴点セットに対して、その特徴点セットには含まれていないが、初期特徴点候補に含まれる特徴点をランダムに追加する処理を、一定の確率で実行する。追加する特徴点の個数は、予め定めておけばよい。また、このように、ステップＳ２４で選択された特徴点セットに対して、特徴点を追加する場合、特徴点セット選択手段５１は、ステップＳ２６で更新された特徴点数（次の特徴点セット選択時に特徴点セットに含める特徴点の数）も増加させてよい（本例では増加させるものとする）。ただし、この特徴点数は、特徴点を追加後の特徴点セットに得する特徴点数よりも小さくなるようにする。ステップＳ２６からステップＳ２１に戻ったときに、ステップＳ２４で選択された特徴点セットに対して特徴点セット選択手段５１が特徴点を追加するか否かは、既に説明したように、例えば、乱数を用いて決定すればよい。
【００８０】
なお、ここでは、ステップＳ２４で選択された特徴点セットに対して、一定の確率で特徴点を追加する場合を例にしているが、ステップＳ２４で選択された特徴点セット内の一部の特徴点を他の特徴点に入れ替えてもよい。
【００８１】
上記の一定の確率のもとで、特徴点セット選択手段５１が特徴点セットに特徴点を追加した場合は、特徴点セット選択手段５１は、ステップＳ２１〜Ｓ２３の繰り返し処理において、特徴点が追加された特徴点セットを特徴点の候補として、その特徴点の候補の中から、定めた特徴点数分の特徴点を含む特徴点セットをそれぞれ選択していく。また、ステップＳ２６からステップＳ２１に戻ったときに、特徴点セット選択手段５１が、上記のような特徴点セットに対する特徴点追加処理を行わない場合には、特徴点セット選択手段５１は、ステップＳ２１〜Ｓ２３の繰り返し処理において、前のステップＳ２４で選択された特徴点セットを特徴点候補として、その特徴点の候補の中から、ステップＳ２６で更新された特徴点数分の特徴点を含む特徴点セットをそれぞれ選択していく。
【００８２】
ステップＳ２３で、未選択の特徴点がないと判定したときには、ステップＳ２４に移行し、既に説明した動作と同様の動作を行えばよい。そして、ステップＳ２４で選択した特徴点セットに属する特徴点の数が、最終的に選択しようとする特徴点数まで減少したならば（ステップＳ２５におけるＹｅｓ）、処理を終了する。
【００８３】
次に、ステップＳ２２において、認識誤差算出手段５２が実行する認識タスクの実行例を説明する。ここでは、認識タスクとして姿勢推定を行う場合を例にして説明する。姿勢推定は、「画像から抽出された特徴点の位置」と「３Ｄ形状モデル上の特徴点から計算される、ある姿勢における画像上の特徴点の位置」との間の誤差（再投影誤差）が最小となるような姿勢を計算する処理である。再投影誤差をεａとすると、再投影誤差εａは、以下に示す式（３）で表される。
【００８４】
【数２】
2012032747.tif 000004
【００８５】
式（３）において、ｘｉは特徴点抽出器の学習済みの内部データを用いて画像（評価データ）から抽出された特徴点の位置である。また、Ｘｉはその特徴点に対応する３Ｄ形状モデル上の特徴点の位置である。また、透視カメラモデルＰｐを以下の式（４）のように定義すると、式（３）におけるｐ１，ｐ２，ｐ３は、Ｐｐ＝［ｐ１  ｐ２  ｐ３］Ｔとなる値である。ｐ１，ｐ２，ｐ３から姿勢を計算することができるので、εａが最小となるようなｐ１，ｐ２，ｐ３を求めることが姿勢推定であるということができる。
【００８６】
【数３】
2012032747.tif 000005
【００８７】
ただし、Ａは、カメラの内部パラメータ行列であり、カメラの内部パラメータ行列として現実的な値に定めておけばよい。また、特徴点確定後に実際に画像を撮影して認識タスクを行うときに、その画像を撮影するカメラの内部パラメータ行列をＡとして用いてもよい。Ｍは、以下の式（５）で表される対象物体の姿勢パラメータ行列である。式（５）において、Ｒは対象の回転を表しており、Ｔは物体の３次元位置を表している。
【００８８】
【数４】
2012032747.tif 000006
【００８９】
また、アフィンカメラモデルＰａを以下の式（６）のように定義する。
【００９０】
【数５】
2012032747.tif 000007
【００９１】
このアフィン変換モデルＰａにより、３Ｄ形状モデル上の特徴点Ｘは画像上の特徴点ｘとして投影される。
【００９２】
【数６】
2012032747.tif 000008
【００９３】
式（７）において、チルダを付したｘは、ｘの斉次表現である。式（７）ではベクトルの第３要素が常に一定であるため、Ｐａの上２行を持つ部分行列Ｐａ２を用いて、以下に示す式（８）のように表すことができる。
【００９４】
ｘ＝Ｐａ２Ｘ          式（８）
【００９５】
Ｐａ２は８の要素を持つため、４点以上の特徴点が与えられれば、Ｐａ２を最小二乗法で計算できる。また、求められたＰａ２から姿勢パラメータＭを計算することができる。認識誤差算出手段５２は、Ｘ（３Ｄ形状モデル上の特徴点の位置）およびｘ（評価データから抽出される特徴点の位置）および式（８）を用いて行列Ｐａ２を計算する。そして、そのＰａ２および式（６）とにより、姿勢パラメータ行列Ｍにおける回転Ｒおよび物体の３次元位置Ｔ）を求め、これを初期値とする。
【００９６】
また、式（４）に示す透視カメラモデルＰｐを用いて、３Ｄ形状モデル上の特徴点Ｘは画像上の特徴点ｘとして投影される。
【００９７】
【数７】
2012032747.tif 000009
【００９８】
ここで、λは定数倍の不定性を表すスカラ量である。
【００９９】
認識誤差算出手段５２は、式（３）で表される再投影誤差εａを繰り返し法により最適化することで、姿勢推定を行う。ｊ回目の反復結果により得られる姿勢パラメータを用いて計算されるカメラ行列をＰＰｊとする。このとき、各姿勢パラメータの更新値を、Δφ，Δθ，Δψ，Δｔｘ，Δｔｙ，Δｔｚを用いて、以下の式（１０）が成立する。認識誤差算出手段５２は、式（１０）によりΔφ，Δθ，Δψ，Δｔｘ，Δｔｙ，Δｔｚを計算する。
【０１００】
【数８】
2012032747.tif 000010
【０１０１】
認識誤差算出手段５２は、３組以上の対応点組を用い、最小二乗法を用いて更新パラメータを求め、その更新パラメータを用いて、以下の式（１１）によりカメラ行列を更新する。
【０１０２】
【数９】
2012032747.tif 000011
【０１０３】
式（１１）において、Ｐは各パラメータよりカメラ行列を計算する関数である。前述の初期値から更新パラメータが十分に小さくなるまで、認識誤差算出手段５２は、式（１０）、式（１１）の計算を繰り返すことにより、再投影誤差εａを最小にするような姿勢を表す投影行列Ｐｐ（換言すればｐ１，ｐ２，ｐ３）を求めればよい。このεａが認識誤差である。ステップＳ２４において、特徴点選択手段５３は、εａが最小となる特徴点セットを選択する。ただし、最小となるεａが、前回のステップＳ２４で選択した特徴点セットにおけるεａより増加していれば、既に説明したように特徴点セット毎に、式（１）でＰｉを計算し、Ｐｉに応じて確率的に特徴点セットを選択する。
【０１０４】
上記の例では、認識誤差算出手段５２は、認識誤差としてεａを計算したが、認識誤差としてεａ以外の値を計算してもよい。例えば、認識誤差算出手段５２は、認識誤差として、以下の式（１２）のε１を計算してもよい。
【０１０５】
【数１０】
2012032747.tif 000012
【０１０６】
式（１２）においてハット記号を付したＸは、Ｘの真値であり、Ｒ，Ｔは姿勢推定により得られた測定結果である。式（１２）においてｉで示す特徴点に関する各項の積算を行う際に、ｉで示す特徴点の特徴点抽出誤差を利用し、誤差の大きい特徴点の重みを小さくすることによって、認識性能を向上させることもできる。この場合、各項に特徴点抽出誤差の分散の逆数を用いることが一般的である。なお、特徴点抽出誤差とは、評価データから切り出したテンプレートに基づいて求めた特徴点の位置と、３Ｄ形状モデル上の指定された特徴点に対応する正しい特徴点の位置との差である。
【０１０７】
本実施形態によれば、特徴点セット毎に実際に認識タスクを実行し、その結果得られる認識結果と正解との差（認識誤差）や、認識誤差の増加量ａｉ（式（１）参照）を利用して、ステップＳ２４で特徴点セットを選択していく。よって、実際に特徴点を用いて実行する認識タスクの認識アルゴリズムに適切な複数の特徴点を選ぶことができる。
【０１０８】
また、仮に、図３に示すフローチャートのステップＳ２４において、常に、認識誤差が最小となる特徴点セットを選択するものとし、ステップＳ２６からステップＳ２１に戻ったときに特徴点セットに対する特徴点の追加を行うことがないとする。すると、ステップＳ２４で選択された特徴点セットに属さない特徴点は、その後の処理で選択されることはない。このため、特徴点セットに属する特徴点数が多い初期段階で重要度を高く評価することができないような特徴点は、早い段階で選択候補から漏れてしまいやすい。
【０１０９】
一方、本実施形態では、ステップＳ２４において、各特徴点セットについての認識誤差のうち最小となる認識誤差が、前回のステップＳ２４で選択した特徴点セットについての認識誤差より大きい場合、前述の式（１）によりＰｉを特徴点セット毎に計算し、Ｐｉの値が大きいほど選択されやすく、Ｐｉの値が小さいほど選択されにくくするという条件のもとで、特徴点セットを一つ選択する。Ｐｉの値が小さい特徴点セットに関しては、選択されにくいものの、選択される余地を残しているので、特徴点数が多い初期段階で重要度を高く評価することができないような特徴点を漏れにくくすることができる。
【０１１０】
また、ステップＳ２６からステップＳ２１に戻ったときに、特徴点セット選択手段５１は、一定の確率で、ステップＳ２４で選択された特徴点セットに対して、その特徴点セットに含まれていない特徴点を含ませるようにする。そして、ステップＳ２１〜Ｓ２３の繰り返し処理におけるステップＳ２１では、その特徴点セットを特徴点の候補として、その特徴点の候補の中から特徴点セットを各通り選択していく。従って、特徴点数が多い初期段階で重要度を高く評価することができないような特徴点がステップＳ２４で選択される特徴点セットから漏れてしまったとしても、ステップＳ２１でそのような特徴点を含む特徴点セットを再度選択することができる。換言すれば、一旦漏れてしまった重要な特徴点を再度復活させるようにして、重要な特徴点を最終的な選択結果に残しやすくすることができる。
【０１１１】
また、上記の例では、ステップＳ２６で特徴点数を削減しながら、ステップＳ２１〜Ｓ２６の繰り返し処理を行う。よって、一定の確率で特徴点数が増加することもあるが、特徴点セットに含める特徴点数を逐次的に減少させるようにして、最終的に選択する特徴点を決定する。このようにすることで、最終的に選択する特徴点を決定するまでの計算量を抑えることができる。
【０１１２】
また、一つの個体の３Ｄ形状モデルおよびその３Ｄ形状モデル上の複数の特徴点を指定することによって、特定の個体にとって適切な特徴点を選択したり、特徴点抽出器の内部データを生成したりすることができる。
【０１１３】
また、本実施形態では、３Ｄ形状モデルから生成した学習データから切り出したテンプレートに基づいて、３Ｄ形状モデル上の指定された各特徴点について内部データ（特徴点抽出器の内部データ）を学習する。そして、３Ｄ形状モデルから生成した評価データを用いて、その内部データによる特徴点判定を行って認識タスクを実行したときの認識誤差を評価することができ、特徴点判定および認識タスクの両者を通じて、精度よく認識タスクを実行することができる特徴点を得ることができる。
【０１１４】
また、一般に、システム稼働後に認識対象の個体が新たに登録されるシステムにおいて、特徴点位置は全個体で共通とされていたが、本実施形態では、個体毎に適した特徴点を選択することができる。一般的なシステムでは、個体毎に特徴点抽出器の内部データを学習するためには、事前に個体毎の特徴点を決めておかなければならなかったため、認識対象となる個々の個体毎に好ましい特徴点を定めるために、事前に特徴点を定める必要が生じてしまう。すなわち、目的とする事項そのものが事前に必要となってしまう。そのため、個体毎に好ましい特徴点を選択することや、個体毎に特化した特徴点抽出器の学習は行えなかった。それに対し、本発明では、一つの個体の３Ｄ形状モデルおよびその３Ｄ形状モデル上の複数の特徴点を指定すれば、その３Ｄ形状モデルから学習データおよび評価データを作成し、学習データに基づいて特徴点抽出器の内部データの学習を行うことができる。そして、評価データを用いて認識タスクを実行し認識誤差を利用してステップＳ２４で特徴点セットを選択していくことを繰り返すことによって、一つの個体に関して、適切な特徴点を選択することができる。また、その特徴点の内部データは学習できている。よって、本発明によれば、個体毎に、適切な特徴点を選択したり、特徴点抽出器の学習を行ったりすることができる。例えば、ある人物に固有の黒子を特徴点とすれば、その人物の姿勢推定や個体識別（顔識別）の精度を高められると考えられるが、本発明によればそのような個体固有の特徴点を、好ましい特徴点として選択することができる。
【０１１５】
また、複数の個体の３Ｄ形状モデルやその３Ｄ形状モデル上における複数の特徴点を指定することによって、個体に特化した特徴点ではなく、複数の個体において共通に重要である特徴点を選択したり、共通で利用可能な特徴点抽出器の学習を行ったりすることもできる。この場合、例えば、各個体間で類似しているものとして対応付けられている特徴点を指定して、本発明の動作を実行させればよい。
【０１１６】
また、個体毎に特徴点を選択する処理を行い、個体毎の特徴点のうち、共通の特徴点（個体間で類似する特徴点）を選択してもよい。また、各個体間で類似する特徴点をしておき、その特徴点により特徴点抽出器の内部データを学習させ、評価データを用いた評価は、個体毎に個別に行うこととしてもよい。この点は、後述の実施形態でも同様である。
【０１１７】
次に、本実施形態の変形例について説明する。
初期特徴点候補の数をＮとし、最初にステップＳ２１に移行したときに定める特徴点数をｍとすると、ステップＳ２１〜Ｓ２３の繰り返し処理をＮＣｍ回行うことになる。そして、ステップＳ２１〜Ｓ２６の処理を繰り返して、最終的に得る特徴点セットの精度を高めるためには、処理の開始時に指定する特徴点の数Ｎを大きくしておく必要があるが、そうするとステップＳ２１〜Ｓ２３の繰り返し数が多くなり、処理時間が長くなってしまう。
【０１１８】
そこで、ステップＳ１６からステップＳ２１に移行したときや、ステップＳ２６からステップＳ２１に移行したときに、その後に行うステップＳ２１〜Ｓ２３の繰り返し処理の回数を固定回数（ここではＰ回とする。）に定めておいてもよい。そして、ステップＳ２１〜Ｓ２３の繰り返し処理をＰ回実行したときに、特徴点選択手段５３がステップＳ２４を実行してもよい。この場合、特徴点セット選択手段５１によってＰ個の特徴点セットが選択されているので、特徴点選択手段５３は、そのＰ個の特徴点セットの中から一つの特徴点セットを選択すればよい。
【０１１９】
また、上記のステップＳ２１〜Ｓ２３の処理の繰り返し回数Ｐを以下のように決定してもよい。ステップＳ２１〜Ｓ２３の繰り返し数Ｐに応じた認識タスクの総実行時間と、認識誤差の関係は、図４に示すようになる。すなわち、繰り返し数Ｐの値を増やすと認識タスクの総実行時間が増えるが、実行時間の増加につれて認識誤差は減少し、ある程度まで減少すると認識誤差は収束する。従って、認識誤差が収束するときのＰを定めておくことにより、処理時間をできるだけ短くしつつ、できるだけ認識誤差を少なくすることができる。このＰは、予め想定して決定してもよい。あるいは、特徴点選択システムが繰り返し数決定手段（図示せず）を備えていてもよい。この場合、特徴点選択システムがＰを変化させて、それぞれのＰについて図３に示すフローチャートを実行し、繰り返し数決定手段（図示せず）が、認識誤差が収束するときのＰを決定する。その後、特徴点を選択する処理を行うときには、図３に示すフローチャート中のステップＳ２１〜Ｓ２３の繰り返し処理を、決定された回数だけ実行すればよい。
【０１２０】
また、特徴点セット選択手段５１は、予め定められた特徴点が固定的に特徴点セットの中に含まれるようにして、特徴点セットを選択してもよい。すなわち、ステップＳ２１で選択される特徴点セットに属する特徴点の数をｍ個とし、予め固定的に特徴点セットに含められると定められた特徴点の数をＺとすると、ｍ−Ｚ個の特徴点を、特徴点候補の中から選択し、ｍ個の特徴点を含む特徴点セットを定めればよい。ただし、ｍ＞Ｚである。また、ｍは、ステップＳ２６で減少するように更新され、ステップＳ２６からステップＳ２２１に戻ったときには、一定の確率で増加するように定められる。特徴点セットに固定的に含まれる特徴点は、ユーザが重要な特徴点であると予測し、ユーザが人手で設定しておけばよい。この設定態様は限定されない。このように、特徴点セットに固定的に含めるＺ個の特徴点を定めておき、残りのｍ−Ｚ個の特徴点をステップＳ２１で選択して、ステップＳ２１〜Ｓ２３の繰り返し処理をＰ回繰り返してもよい。あるいは、固定的でないｍ−Ｚ個の特徴点の組み合わせが全て選択されるまでステップＳ２１〜Ｓ２３の繰り返し処理を行ってもよい。
【０１２１】
また、上記の実施形態では、ステップＳ２４で選択した特徴点セットに属する特徴点の数が、最終的に選択しようとする特徴点数（ユーザの所望の特徴点数）まで減少したときに（ステップＳ２５におけるＹｅｓ）、処理を終了する場合を説明した。ステップＳ２１〜Ｓ２６の繰り返し処理を停止して、処理を終了する基準として他の基準を用いてもよい。以下、処理を終了する他の基準について説明する。
【０１２２】
上記の例において、ステップＳ２１〜Ｓ２６の繰り返し処理では、ステップＳ２６からステップＳ２１に戻ったときに、選択する特徴点セットに含める特徴点数を一定の確率で増加することがある、ステップＳ２６に移行する毎に、特徴点セットに含める特徴点数を値が小さくなるように更新する。従って、全体としては、ステップＳ２１〜Ｓ２６の処理の繰り返し数が増えると、選択される特徴点セットに属する特徴点の数は減少していく傾向になる。そして、特徴点セットに属する特徴点の数が少なくなると、その特徴点セットに属する特徴点を用いて認識タスクを実行したときの認識誤差が増加していく傾向がある。そこで、ステップＳ２５において、特徴点選択手段５１は、直近のステップＳ２１〜Ｓ２３の繰り返し処理で計算された特徴点セット毎の認識誤差の最小値が、予め定められた閾値（認識誤差に関する閾値）以上になった場合、ステップＳ２６に移行せずに、処理を終了すると決定してもよい。この場合、特徴点選択手段５１は、直近のステップＳ２１〜Ｓ２３の繰り返し処理で選択された複数の特徴点セットのうち、認識誤差が最小となる特徴点セットに属する特徴点を認識アルゴリズムに適切な特徴点として決定し、処理を終了する。また、このとき、直近のステップＳ２４で選択した特徴点セットに属する特徴点を認識アルゴリズムに適切な特徴点として決定してもよい。
【０１２３】
また、あるいは、特徴点選択手段５１は、前回のステップＳ２１〜Ｓ２３の繰り返し処理で計算された特徴点セット毎の認識誤差の最小値に対する、直近のステップＳ２１〜Ｓ２３の繰り返し処理で計算された特徴点セット毎の認識誤差の最小値の増加量を計算し、その増加量が予め定められた閾値（認識誤差の増加量に関する閾値）以上になった場合、ステップＳ２６に移行せずに、処理を終了すると決定してもよい。この場合にも、特徴点選択手段５１は、直近のステップＳ２１〜Ｓ２３の繰り返し処理で選択された複数の特徴点セットのうち、認識誤差が最小となる特徴点セットに属する特徴点を認識アルゴリズムに適切な特徴点として決定し、処理を終了する。また、このとき、直近のステップＳ２４で選択した特徴点セットに属する特徴点を認識アルゴリズムに適切な特徴点として決定してもよい。
【０１２４】
実施形態２．
第１の実施形態では、特徴点候補から特徴点を除外した特徴点セットの全てについて、姿勢推定等の認識タスクを実行し、認識誤差を計算していた。これに対し、第２の実施形態では、特徴点セット毎に認識タスクを実行するのではなく、認識誤差を評価しようとしている特徴点セットを選択する元になった、前回の繰り返し処理で認識誤差が既に評価された特徴点セットの認識誤差の値を利用して、その特徴点セットから任意の特徴点を除外した特徴点セットでの認識誤差の値を推定する技術を利用する。このように特徴点セットの認識誤差を推定することで、計算量を少なくすることができる。
【０１２５】
また、第１の実施形態では、特徴点候補から特徴点セットを選択する特徴点セット選択手段５１は、特徴点セットに対して特徴点を追加したり、特徴点候補から特徴点を除外して特徴点セットを選択したりする際に、それらの特徴点をランダムに選択する。これに対し、第２の実施形態では、特徴点候補全てを用いたときの認識誤差およびその微分値に基づいて、所定の特徴点を特徴点候補から除外または追加して生成される特徴点セットを認識タスクに用いたときの認識誤差を推定する。そして、特徴点候補の各特徴点の重要度を予め予測しておくことにより、重要度の高い特徴点を優先して選択した特徴点セットを生成する。この方式により、より適切な特徴点を選択することができる。
【０１２６】
図５は、本発明の第２の実施形態の特徴点選択システムの例を示すブロック図である。図６は、第２の実施形態の処理経過の例を示すフローチャートである。
【０１２７】
第２の実施形態の特徴点選択システムは、第１の実施形態の構成要素に加えて、特徴点重要度推定手段５４を備える。また、第２の実施形態では、特徴点セット選択手段５１が行うステップＳ２１の処理内容と、認識誤差算出手段５２が行うステップＳ２２の処理内容がそれぞれ第１の実施形態と異なる。図６に示すステップＳ２１，Ｓ２２，Ｓ３１以外の処理は、第１の実施形態（図３参照）と同様である。
【０１２８】
第２の実施形態においても、認識タスクとして姿勢推定を行う場合、第１の実施形態で説明した認識誤差εａの最小化計算（式（１０）および式（１１）の繰り返し計算）により姿勢推定を行える。ただし、第２の実施形態では、εａの最小化計算にＨｅｓｓｉａｎ近似法を適用し、式（１０）および式（１１）の繰り返し計算を行わずに、前回の繰り返し処理において計算した認識誤差の値を用いて、そのときの特徴点セットから任意のｑ点を除いた特徴点セットにおけるεａの値を計算する。この結果、εａの最小化の計算量を少なくすることができる。
【０１２９】
第１の実施形態で説明したεａの最小化計算を用いると、認識誤差算出手段５２は、現在の特徴点セット（ここでは特徴点数がｍ個とする。）からｑ個の特徴点を削減する際に、この最小化計算をｍＣｑ回繰り返すことになる。例えば、ｍ＝１００００であり、ｑ＝１であるとすると、１００００個から１つの特徴点を削減する際に１００００回最小化計算を行うこととなり、ｑ≧２のときにはさらに計算量が増える。Ｈｅｓｓｉａｎ近似法を適用することでこの計算量を削減することができる。Ｈｅｓｓｉａｎ近似法は、特徴点セットに含める特徴点の数をｑ個ずつ減少させる場合でも、ｑ個ずつ増加させる場合でも適用できるが、ここでは特徴点の数をｑ個ずつ削減する場合を例にして説明する。
【０１３０】
以下、式（１０）で示したΔφ，Δθ，Δψ，Δｔｘ，Δｔｙ，Δｔｚをベクトルとして並べて表した姿勢パラメータをθとする。姿勢推定は、認識誤差関数εａを最小化する姿勢パラメータθを求める処理である。これは一般に非線形最適化となり、Gauss-Newton法、Levenberg-Marquard 法等の一般的な方法で最小化を行う。また、これらの手法では、εａの１次・２次微分値を計算に用いている。第２の実施形態では、認識誤差算出手段５２は、最終的にεａを最小化したときのεａ，θ、および１次・２次微分値を使って、特徴点を削減した後のεａを計算し、姿勢推定を行わずにどの特徴点を削減すればよいのかを予見する。
【０１３１】
現在の特徴点セット（前回のステップＳ２４で選択された特徴点セット）内の特徴点の数をｍとし、削減しようとしている特徴点の数をｑとする。ただし、ｑはｍに比べて小さい数であり、具体的には２，３を想定する。また、現在の特徴点セットであり、既に姿勢推定が行われεａが計算済みとなっている特徴点セットをＳｍとし、その特徴点セットＳｍからｑ個の特徴点を除いた特徴点のセットをＳｍ−ｑとする。そして、除こうとしているｑ個の特徴点のセットをＳｑとする。認識誤差算出手段５２は、ｍ個の特徴点を含む特徴点セットＳｍを、ｍ−ｑ個の特徴点を含む特徴点セットＳｍ−ｑとｑ個の特徴点を含む特徴点セットＳｑとに分ける。Ｓｍ−ｑ⊂Ｓｍである。
【０１３２】
また、現在の特徴点セットＳｍによる姿勢推定の認識誤差εａをコスト関数ｆ＋と表すこととする。すると、このコスト関数は式（１３）のように分解する。
【０１３３】
【数１１】
2012032747.tif 000013
【０１３４】
式（１３）において、チルダを付したｚｉは、学習済みの特徴点抽出器によって判定した特徴点ｉの画像上の位置である。また、ｚｉ（θ）は、姿勢がθであるときの、３Ｄ形状モデル上の特徴点ｉから計算される画像上での特徴点ｉの位置であり、姿勢θにおける特徴点ｉの正解位置に該当する。なお、これらの画像は評価データ生成手段４４に生成された評価データである。
【０１３５】
また、Σｉは、特徴点ｉの特徴点抽出誤差の分散を対角成分とする行列である。なお、特徴点抽出誤差は、例えば、特徴点位置検出手段４６が計算すればよい。
【０１３６】
また、式（１３）は以下の式（１４）のように表すことができる。
【０１３７】
ｆ＋＝ｆ−＋δｆ          式（１４）
【０１３８】
ｆ＋は、現在の特徴点セットＳｍの全特徴点の分の認識誤差（εａの値）である。ｆ−は、ｑ個の特徴点を取り除いた後のコスト関数であり、以下の式（１５）のように表される。ｆ−は、ｑ点を除いた特徴点セットＳｍ−ｑの分の認識誤差（εａの積算をｑ点を除いた特徴点についてのみ行った値）である。
【０１３９】
【数１２】
2012032747.tif 000014
【０１４０】
δｆは、取り除くｑ個の点に対応するコスト関数であり、以下の式（１６）のように表される。δｆは、除いたｑ点の分の認識誤差（εａの積算をｑ点の特徴点についてのみ行った値）である。
【０１４１】
【数１３】
2012032747.tif 000015
【０１４２】
式（１４）の各項のＨｅｓｓｉａｎをＨ＋，Ｈ−，δＨで表すと、以下の式（１７）がが得られる。Ｈｅｓｓｉａｎは、ｆのθによる２次微分を表す行列である。
【０１４３】
Ｈ＋＝Ｈ−＋δＨ          式（１７）
【０１４４】
ｆ＋における姿勢の推定値が得られているとする。このとき、以下の式（１８）が成立する。ただし、ｇ＋（・）＝ｄｆ＋／ｄθである。
【０１４５】
【数１４】
2012032747.tif 000016
【０１４６】
そして、以下に示す式（１９）が成立する。
【０１４７】
【数１５】
2012032747.tif 000017
【０１４８】
式（１９）において、ｇはεａのθによる１次微分である。また、ハット記号を付したθ＋は、現在のｍ個の特徴点を含む特徴点セットＳｍで姿勢推定したときの姿勢パラメータ（既に計算した姿勢パラメータ）である。ハット記号を付したθ−は、ｑ個の特徴点を除いた特徴点セットＳｍーｑで姿勢推定したときの姿勢パラメータであり、処理時間を削減するために計算の対象外としようとするものである。
【０１４９】
また、ハット記号付きのｆ−（θ−）は、ｑ個の特徴点を除いた特徴点セットＳｍ−ｑで姿勢推定したときの認識誤差εａであり、処理時間を削減するために計算の対象外としようとするものである。
【０１５０】
ハット記号付きのδｇ（θ＋）は、現在のｍ個の特徴点を含む特徴点セットＳｍで姿勢推定したときの姿勢パラメータの値における、認識誤差の１次微分値であり、この値は姿勢推定処理の過程ですでに計算されているものである。
【０１５１】
また、Ｈ−−１は、ｑ個の特徴点を除いた特徴点セットＳｍ−ｑで姿勢推定したときの姿勢パラメータの値における、認識誤差の２次微分値の逆行列である。この値は、計算しないことが好ましいが、特徴点数ｍがｑに比べて十分に大きい場合にはＨ＋で近似しても（すなわち置き換えても）大差ないことが知られている。そして、Ｈ＋は姿勢推定処理の過程で既に計算されているものである。ハット記号を付したθ＋の計算にGauss-Newton法やMarquardt 法を利用するとＨ＋は計算済みとなる。
【０１５２】
Ｈ−をＨ＋に置き換えると、以下の手続により、εａを最小化しなくてもＳｑを取り除いた後のコスト関数値を近似的に計算することができる。認識誤差算出手段５２は、以下の処理を行うことで、最小化処理を行う。
【０１５３】
（１）認識誤差算出手段５２は、ＳｑをｍＣｑ通り変化させつつ以下の処理を実行する。
【０１５４】
（２）認識誤差算出手段５２は、以下の式（２０）を計算する。
【０１５５】
【数１６】
2012032747.tif 000018
【０１５６】
（３）次に、認識誤差算出手段５２は、以下の式（２１）を計算する。
【０１５７】
【数１７】
2012032747.tif 000019
【０１５８】
（４）次に、認識誤差算出手段５２は、ｆ−（θ−）が最小となるＳｑを取り除いて、Ｓｍ−ｑを作成する。
【０１５９】
（５）次に、認識誤差算出手段５２は、実際にｆ−を最小化して、ハット記号付きのθ−を求める。
【０１６０】
上記の（３）の手続では、ｆの最小化によってハット記号付きのθ−を計算することなく、右辺の
【数１８】
2012032747.tif 000020
の値を評価する。
【０１６１】
このように、本実施形態においてＨｅｓｓｉａｎ近似法を適用することで、認識誤差の最小値計算量を削減する効果が得られる。
【０１６２】
以上の説明では、特徴点の数をｑ個ずつ削減する場合を例にしたが、特徴点の数をｑ個ずつ増加させていく場合には、ｇ−（・）＝ｄｆ−／ｄθであり、式（１９）の代わりに、以下に示す式（２２）が成立する。この場合には、追加するＳｑを定めていけばよい。
【０１６３】
【数１９】
2012032747.tif 000021
【０１６４】
以下、式（１９）の導出について説明する。まず、ｆ＋（θ＋）は、式（２３）のように定義される。
【０１６５】
【数２０】
2012032747.tif 000022
【０１６６】
ｄｆ＋／ｄθ＝ｇ＋等のように書くこととする。ｇ＋（θ＋）＝０より、以下の計算が成り立つ。
【０１６７】
【数２１】
2012032747.tif 000023
【０１６８】
上記の式において、ｇ−（θ−）＝０であり、よって、式（２４）が得られる。
【０１６９】
【数２２】
2012032747.tif 000024
【０１７０】
また、以下の計算式が成立し、式（２４）を代入することで、以下に示す式（２５）（式（１９）と同様の式）が得られる。
【０１７１】
【数２３】
2012032747.tif 000025
【０１７２】
【数２４】
2012032747.tif 000026
【０１７３】
特徴点セットの認識誤差を推定する処理の他に、本実施形態では、特徴点セット選択手段５１によるステップＳ２１の処理の前に、特徴点重要度推定手段５４が、以下の処理を行う。すなわち、ステップＳ２１の前に、特徴点セットに含める特徴点としてどの特徴点を選択するかに関する確率を、現在の特徴点候補（ここでは、前回のステップＳ２４で選択された特徴点セット）から特徴点を除外したり追加したりしたときの認識誤差の増減量に基づいて決定する（ステップＳ３１）。換言すれば、特徴点重要度推定手段５４は、前回のステップＳ２４で選択された特徴点セットに特徴点を追加したり除外したり場合における、特徴点セット以外の特徴点が特徴点セットに追加される確率や、特徴点セットに属する特徴点が除外される確率を、特徴点の追加や除外後の認識誤差の増減量に基づいて決定する。
【０１７４】
以下、本実施形態における特徴点重要度推定手段５４および特徴点セット選択手段５１の動作（ステップＳ３１，Ｓ２１。図６参照。）について説明する。
【０１７５】
初期特徴点候補の各特徴点が、現在の特徴点セット（前回のステップＳ２４で選択された特徴点セット）に属する特徴点として選択されているか否かを“１”または“０”の値で表し、その値を並べたベクトルをｗと表すこととする。また、このベクトル、およびこのベクトルの要素を「重み」と記す場合がある。特徴点全体に着目して「重み」と記す場合には、ベクトルを指し、個々の特徴点に着目して「重み」と記す場合には、ベクトルの要素を指す。ランダムにベクトルｗの要素の値を“０”または“１”に変化させても、認識誤差の削減に有効な新たな重み（特徴点セットを規定するベクトル）が得られる確率は低い。現在の特徴点セットを表すベクトルをｗａとし、ｗａの近傍空間を、認識誤差関数（コスト関数）ｆの削減度を指標に、効率的に探索したうえで、新たな重み（ベクトルｗｂとする。）を決定することが好ましい。
【０１７６】
そこで、現在の重みｗａを近傍の重みｗｂへ変化させる際に、逐次予測法（認識誤差を予測する前述の方法）で用いた認識誤差関数の近似解を利用する。この近似解を用いることにより、現在の特徴点セットに含まれている各特徴点に対し、それらの特徴点を取り除いたときの認識誤差関数ｆの変化量を推定できる。また、現在の特徴点セットに含まれておらず、ベクトルの要素の値が“０”となっている各特徴点に対して、それらを復活させたとき（すなわち、重みの値を“１”に変化させたとき）の認識誤差関数ｆの変化量を推定できる。なお、復活させるとは、一旦、特徴点セットから漏れた特徴点を、特徴点セットに含めることを意味する。特徴点セット選択手段５１は、これらの推定値（認識誤差関数ｆの変化量の推定値）に基づき、認識誤差関数ｆの値がより小さくなるように、確率的に重みをつけて、各特徴点の重みの変化、すなわち、各特徴点を特徴点セットに含めるか否かを決定する（ステップＳ２１）。
【０１７７】
初期特徴点候補の数をＮ個とし、現在の特徴点セットに属する特徴点の数をＭ個とする。この場合、ベクトルの要素はＮ個である。そして、現在の特徴点セットを表すベクトルｗａでは、その特徴点セットに属する特徴点に対応するＭ個の要素の値が“１”となっている。現在の特徴点セットに属するＭ個の特徴点のうち、Ｋ個の特徴点を排除し、その代わりに現在選択されていないＮ−Ｍ個の特徴点の中からＫ個の特徴点を復活させることを想定する。特徴点セットからＫ個の特徴点を排除するということは、特徴点の入れ替え後の特徴点セットを表すベクトルｗｂにおいて、その特徴点に対応するＫ個の要素の値を“０”にすることを意味する。また、選択されていないＮ−Ｍ個の特徴点の中からＫ個の特徴点を復活させるということは、ベクトルｗｂにおいて、その特徴点に対応するＫ個の要素の値を“１”にすることを意味する。特徴点セット選択手段５１は、このとき入れ替える特徴点の数Ｋを、１〜Ｍ／２の乱数で決定する。すなわち、１〜Ｍ／２の範囲で乱数を発生させ、発生させた乱数の値を、入れ替える特徴点の数として決定する。
【０１７８】
特徴点セット選択手段５１は、排除する特徴点を以下の式（２６）に示す確率分布で決定する。
【０１７９】
Ｐ（ｗｉ（ｔ＋１）＝０｜ｗｉ（ｔ）＝１）＝１／Ｚｆｉ−−１          式（２６）
【０１８０】
式（２６）におけるｉは、ベクトル要素の順番（換言すれば特徴点の順番）を表す。また、ｗｉ（ｔ）は、図６におけるステップＳ３１〜Ｓ２６の繰り返し処理におけるｔ回目のステップＳ２４で選択された特徴点セットを表すベクトルのｉ番目の要素である。ｗｉ（ｔ＋１）＝０は、その特徴点セットに対して特徴点の入れ替えを行った後のベクトルのｉ番目の要素を表す。そして、Ｐ（ｗｉ（ｔ＋１）＝０｜ｗｉ（ｔ）＝１）は、現在、特徴点セットに含まれているｗｉ（ｔ）に対応する特徴点を排除する（すなわち、要素の値を０にする）確率を表している。
【０１８１】
また、式（２６）におけるＺは、ΣｉＰ（ｗｉ（ｔ＋１）＝０｜ｗｉ（ｔ）＝１）となるように正規化する正規化定数である。
【０１８２】
また、ｆｉ−は、ｉ番目の特徴点（ここでは、現在の特徴点セットに含まれている特徴点）を排除した際の認識誤差関数の近似値であり、特徴点重要度推定手段５４が、前述の式（１９）から導出する。特徴点重要度推定手段５４はさらに、ｆｉ−を用いてＰ（ｗｉ（ｔ＋１）＝０｜ｗｉ（ｔ）＝１）を計算する。特徴点重要度推定手段５４がＰ（ｗｉ（ｔ＋１）＝０｜ｗｉ（ｔ）＝１）を計算する動作は、ステップＳ３１（図６参照）に該当する。
【０１８３】
特徴点セット選択手段５１は、現在の特徴点セットに含まれる特徴点に関して、ステップＳ３１で計算された確率Ｐ（ｗｉ（ｔ＋１）＝０｜ｗｉ（ｔ）＝１）に基づいて、特徴点セットから除外するか否かを決定する。具体的には、０〜１の範囲で乱数を発生させ、その乱数値が確率Ｐ（ｗｉ（ｔ＋１）＝０｜ｗｉ（ｔ）＝１）以下ならば、要素ｗｉの値を“１”から“０”にする。すなわち、ｗｉに対応する特徴点を特徴点セットから除外する。特徴点セット選択手段５１は、ステップＳ２１において、この処理を現在の特徴点セットに含まれる各特徴点に関して行う。
【０１８４】
式（２６）の確率分布は、現在の特徴点セットから取り除いた場合に認識誤差関数が小さくなる特徴点では高い確率となり、取り除いた場合に認識誤差関数が大きくなる特徴点では低い確率となる。従って、式（２６）に従うことにより、特徴点セット選択手段５１は、取り除いた場合に認識誤差関数が小さくなる特徴点を積極的に取り除く。また、そうでない特徴点は、特徴点セットから除去されにくくなる。
【０１８５】
また、特徴点セット選択手段５１は、特徴点セットの入れ替えで復活させる特徴点を以下の式（２７）に示す確率分布に従って選択する。
【０１８６】
Ｐ（ｗｉ（ｔ＋１）＝１｜ｗｉ（ｔ）＝０）＝１／Ｙｆｉ＋−１          式（２７）
【０１８７】
ｗｉ（ｔ＋１）やｗｉ（ｔ）の意味は式（２６）と同様である。そして、式（２７）において、Ｐ（ｗｉ（ｔ＋１）＝１｜ｗｉ（ｔ）＝０）は、現在、特徴点セットに含まれていないｗｉ（ｔ）に対応する特徴点を特徴点セットに復活させる（すなわち、要素の値を１にする）確率を表している。
【０１８８】
また、式（２７）におけるＹは、ΣｉＰ（ｗｉ（ｔ＋１）＝１｜ｗｉ（ｔ）＝０）となるように正規化する正規化定数である。
【０１８９】
また、ｆｉ＋は、ｉ番目の特徴点（ここでは、現在の特徴点セットに含まれていない特徴点）を復活させた際の認識誤差関数の近似値である。特徴点重要度推定手段５４がｆｉ＋を以下の式（２８）の計算によって計算する。
【０１９０】
【数２５】
2012032747.tif 000027
【０１９１】
特徴点重要度推定手段５４は、さらに、ｆｉ＋を用いてＰ（ｗｉ（ｔ＋１）＝１｜ｗｉ（ｔ）＝０）を計算する。特徴点重要度推定手段５４がＰ（ｗｉ（ｔ＋１）＝１｜ｗｉ（ｔ）＝０）を計算する動作は、ステップＳ３１（図６参照）に該当する。
【０１９２】
ここで、ｆ−は、逐次予測法の場合と異なり、ｉ番目の特徴点を特徴点セットに加える前のコストであり、θ−は、特徴点を復活させる前の推定パラメータである。上式により、特徴点セットに加えたときのコストが小さい点が積極的に特徴点セットに加えられ、そうでない点は特徴点セットに選択されにくくなる。
【０１９３】
特徴点セット選択手段５１は、現在の特徴点セットに含まれていない特徴点に関して、ステップＳ３１で計算された確率Ｐ（ｗｉ（ｔ＋１）＝１｜ｗｉ（ｔ）＝０）に基づいて、特徴点セットに復活させるか否かを決定する。具体的には、０〜１の範囲で乱数を発生させ、その乱数値が確率Ｐ（ｗｉ（ｔ＋１）＝１｜ｗｉ（ｔ）＝０）以下ならば、要素ｗｉの値を“０”から“１”にする。すなわち、ｗｉに対応する特徴点を復活させ、特徴点セットに含める。特徴点セット選択手段５１は、ステップＳ２１において、この処理を現在の特徴点セットに含まれていない各特徴点に関して行う。
【０１９４】
本実施形態では、特徴点重要度推定手段５４がステップＳ３１において、ｆｉ−およびｆｉ＋を計算し、さらに、式（２６）、式（２７）の左辺に示す確率を計算する。そして、ステップＳ３１の後のステップＳ２１において、特徴点セット選択手段５１が、その確率を用いて、上記のように、現在の特徴点セットに含まれている特徴点を除外したり、現在の特徴点セットに含まれていない点を復活させたりする処理を行う。
【０１９５】
以上の第１の実施形態および第２の実施形態において、温度Ｔが、特徴点の最適化における局所解を避けるためのシミュレーテッドアニーリングのパラメータである。既に説明したように、Ｔの設定方法として、前述の式（２）（すなわち、冷却関数Ｔｔ＋１＝γ・Ｔｔ）を用いて設定する方法がある。
【０１９６】
例えば、一定の温度でｄ回近傍の探索を行い、その後、上記の冷却関数で温度Ｔを下げることが好ましい。また、例えば、γは０．８〜０．９程度の定数とする。また、一旦、特徴点の最適解を選択し、その特徴点の最適解におけるコストが導出されている場合には、初期温度Ｔ０の値を、その最適解のコストの１０％以下の値とすればよい。まだ、特徴点の最適解を選択する処理を行っていない場合には、初期温度Ｔ０の値を、例えば、ａ０の１０％以下の値とすればよい。
【０１９７】
高い温度Ｔから開始し、Ｔをゆっくり下げていくことで、特徴点の局所解を避けられる可能性が高くなる。しかし、処理時間は長くなる。特に、初期特徴点候補が多い状態から、高い温度で処理を開始すると、処理時間が長くなる。そこで、第１の実施形態によってある程度、特徴点の数を削減し、その結果得られた特徴点セットを元に、第２の実施形態の処理を実行してもよい。
【０１９８】
次に、本発明の特徴点選択システムの最小構成について説明する。図７は、本発明の最小構成の例を示すブロック図である。本発明の特徴点選択システムは、特徴点セット選択手段５１と、認識誤差算出手段５２と、特徴点選択手段５３とを備える。
【０１９９】
特徴点セット選択手段５１は、認識タスクに適した特徴点の候補となる点の集合である特徴点候補から、特徴点の集合である特徴点セットであって、定められた特徴点数の特徴点を含む特徴点セットを複数選択する。
【０２００】
認識誤差算出手段５２は、特徴点セット選択手段５１に選択された特徴点セット毎に、特徴点セットに含まれる特徴点を用いて認識タスクを実行した場合における認識誤差を算出する。
【０２０１】
特徴点選択手段５３は、特徴点セット選択手段５１に選択された特徴点セット毎の認識誤差の最小値が、特徴点候補を用いて認識タスクを実行した場合における認識誤差より大きい場合に、特徴点セット毎に、特徴点候補を用いて認識タスクを実行した場合における認識誤差からの認識誤差の増加量の指数関数の逆数を計算し、その計算結果の値の大きさに応じて、一つの特徴点セットを選択し、特徴点セット選択手段が特徴点セットを選択する際の特徴点数を更新し、所定の条件が成立したときに認識タスクに適した特徴点を選択する。
【０２０２】
そして、特徴点セット選択手段５１は、特徴点選択手段５３が特徴点セットを選択したときに、その特徴点セットに基づいて特徴点候補を定め、再度、特徴点セットを複数選択する。
【０２０３】
そのような構成により、認識タスクにおける認識アルゴリズムに合う適切な特徴点を選ぶことができ、また、重要な特徴点が最終的に選択した特徴点の集合から漏れにくくすることができる。
【０２０４】
上記の実施形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０２０５】
（付記１）認識タスクに適した特徴点の候補となる点の集合である特徴点候補から、特徴点の集合である特徴点セットであって、定められた特徴点数の特徴点を含む特徴点セットを複数選択する特徴点セット選択手段と、前記特徴点セット選択手段に選択された特徴点セット毎に、特徴点セットに含まれる特徴点を用いて前記認識タスクを実行した場合における認識誤差を算出する認識誤差算出手段と、前記特徴点セット選択手段に選択された特徴点セット毎の認識誤差の最小値が、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差より大きい場合に、特徴点セット毎に、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差からの認識誤差の増加量の指数関数の逆数を計算し、その計算結果の値の大きさに応じて、一つの特徴点セットを選択し、特徴点セット選択手段が特徴点セットを選択する際の特徴点数を更新し、所定の条件が成立したときに前記認識タスクに適した特徴点を選択する特徴点選択手段とを備え、特徴点セット選択手段は、特徴点選択手段が特徴点セットを選択したときに、当該特徴点セットに基づいて特徴点候補を定め、再度、特徴点セットを複数選択することを特徴とする特徴点選択システム。
【０２０６】
（付記２）認識タスクは、個体の姿勢推定であり、認識誤差算出手段は、更新前の特徴点数の特徴点を含む特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータ、およびそれらの微分値を用い、更新後の特徴点数に基づいて選択された特徴点セットに含まれる特徴点を用いた場合の認識誤差を近似的に算出する付記１に記載の特徴点選択システム。
【０２０７】
（付記３）認識タスクは、個体の姿勢推定であり、特徴点セット選択手段は、特徴点選択手段が特徴点セットを選択したときに、特徴点選択手段が選択した特徴点セットに含まれる特徴点に関して、前記特徴点セットから削除した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した除外確率に応じて、前記特徴点を前記特徴点セットから除外し、特徴点選択手段が選択した特徴点セットに含まれないが、最初の特徴点候補に含まれる特徴点に関して、前記特徴点セットに追加した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した追加確率に応じて、前記特徴点を前記特徴点セットに追加することにより、特徴点候補を定める付記１または付記２に記載の特徴点選択システム。
【０２０８】
（付記４）特徴点選択手段は、選択した特徴点セットの特徴点数が所定数まで減少したこと、または、選択した特徴点セットにおける認識誤差が前回選択した特徴点セットにおける認識誤差から一定量以上増加したこと、または、選択した特徴点セットにおける認識誤差が予め定めた閾値以上になったことを所定の条件として、前記所定の条件が成立したときに、その時に定められていた特徴点数に基づいて選択された複数の特徴点セットのうち、認識誤差が最小になる特徴点セットに含まれる特徴点群を、認識タスクに適した特徴点として選択する付記１から付記３のうちのいずれかに記載の特徴点選択システム。
【０２０９】
（付記５）認識タスクに適した特徴点の候補となる点の集合である特徴点候補から、特徴点の集合である特徴点セットであって、定められた特徴点数の特徴点を含む特徴点セットを複数選択し、選択した特徴点セット毎に、特徴点セットに含まれる特徴点を用いて前記認識タスクを実行した場合における認識誤差を算出し、選択した特徴点セット毎の認識誤差の最小値が、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差より大きい場合に、特徴点セット毎に、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差からの認識誤差の増加量の指数関数の逆数を計算し、その計算結果の値の大きさに応じて、一つの特徴点セットを選択し、複数の特徴点セットを選択する際の特徴点数を更新し、所定の条件が成立したときに前記認識タスクに適した特徴点を選択し、前記一つの特徴点セットを選択したときに、当該特徴点セットに基づいて特徴点候補を定め、再度、特徴点セットを複数選択することを特徴とする特徴点選択方法。
【０２１０】
（付記６）認識誤差を算出するときに、更新前の特徴点数の特徴点を含む特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータ、およびそれらの微分値を用い、更新後の特徴点数に基づいて選択された特徴点セットに含まれる特徴点を用いた場合の認識誤差を近似的に算出する付記５に記載の特徴点選択方法。
【０２１１】
（付記７）前記一つの特徴点セットを選択した場合、再度、特徴点セットを複数選択するときに、前記一つの特徴点セットに含まれる特徴点に関して、前記特徴点セットから削除した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した除外確率に応じて、前記特徴点を前記特徴点セットから除外し、前記一つの特徴点セットに含まれないが、最初の特徴点候補に含まれる特徴点に関して、前記特徴点セットに追加した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した追加確率に応じて、前記特徴点を前記特徴点セットに追加することにより、特徴点候補を定める付記５または付記６に記載の特徴点選択方法。
【０２１２】
（付記８）選択した複数の特徴点セットにおける特徴点数が所定数まで減少したこと、または、選択した特徴点セットにおける認識誤差が前回選択した特徴点セットにおける認識誤差から一定量以上増加したこと、または、選択した特徴点セットにおける認識誤差が予め定めた閾値以上になったことを所定の条件として、前記所定の条件が成立したときに、その時に定められていた特徴点数に基づいて選択された複数の特徴点セットのうち、認識誤差が最小になる特徴点セットに含まれる特徴点群を、認識タスクに適した特徴点として選択する付記５から付記７のうちのいずれか１項に記載の特徴点選択方法。
【０２１３】
（付記９）コンピュータに、認識タスクに適した特徴点の候補となる点の集合である特徴点候補から、特徴点の集合である特徴点セットであって、定められた特徴点数の特徴点を含む特徴点セットを複数選択する特徴点セット選択処理、前記特徴点セット選択処理で選択された特徴点セット毎に、特徴点セットに含まれる特徴点を用いて前記認識タスクを実行した場合における認識誤差を算出する認識誤差算出処理、および、前記特徴点セット選択処理で選択された特徴点セット毎の認識誤差の最小値が、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差より大きい場合に、特徴点セット毎に、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差からの認識誤差の増加量の指数関数の逆数を計算し、その計算結果の値の大きさに応じて、一つの特徴点セットを選択し、特徴点セット選択処理で特徴点セットを選択する際の特徴点数を更新し、所定の条件が成立したときに前記認識タスクに適した特徴点を選択する特徴点選択処理を実行させ、特徴点選択処理で特徴点セットを選択させたときに、特徴点セット選択処理で、当該特徴点セットに基づいて特徴点候補を定め、再度、特徴点セットを複数選択させるための特徴点選択プログラム。
【０２１４】
（付記１０）コンピュータに、認識誤差算出処理で、更新前の特徴点数の特徴点を含む特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータ、およびそれらの微分値を用い、更新後の特徴点数に基づいて選択された特徴点セットに含まれる特徴点を用いた場合の認識誤差を近似的に算出させる付記９記載の特徴点選択プログラム。
【０２１５】
（付記１１）コンピュータに、特徴点選択処理で特徴点セットを選択させたときに、特徴点セット選択処理で、特徴点選択処理で選択した特徴点セットに含まれる特徴点に関して、前記特徴点セットから削除した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した除外確率に応じて、前記特徴点を前記特徴点セットから除外し、特徴点選択処理で選択した特徴点セットに含まれないが、最初の特徴点候補に含まれる特徴点に関して、前記特徴点セットに追加した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した追加確率に応じて、前記特徴点を前記特徴点セットに追加することにより、特徴点候補を定めさせる付記９または付記１０に記載の特徴点選択プログラム。
【０２１６】
（付記１２）コンピュータに、特徴点選択処理で、選択した特徴点セットの特徴点数が所定数まで減少したこと、または、選択した特徴点セットにおける認識誤差が前回選択した特徴点セットにおける認識誤差から一定量以上増加したこと、または、選択した特徴点セットにおける認識誤差が予め定めた閾値以上になったことを所定の条件として、前記所定の条件が成立したときに、その時に定められていた特徴点数に基づいて選択された複数の特徴点セットのうち、認識誤差が最小になる特徴点セットに含まれる特徴点群を、認識タスクに適した特徴点として選択させる付記９から付記１１のうちのいずれか１項に記載の特徴点選択プログラム。
【０２１７】
（付記１３）認識タスクに適した特徴点の候補となる点の集合である特徴点候補から、特徴点の集合である特徴点セットであって、定められた特徴点数の特徴点を含む特徴点セットを複数選択する特徴点セット選択部と、前記特徴点セット選択部に選択された特徴点セット毎に、特徴点セットに含まれる特徴点を用いて前記認識タスクを実行した場合における認識誤差を算出する認識誤差算出部と、前記特徴点セット選択部に選択された特徴点セット毎の認識誤差の最小値が、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差より大きい場合に、特徴点セット毎に、前記特徴点候補を用いて前記認識タスクを実行した場合における認識誤差からの認識誤差の増加量の指数関数の逆数を計算し、その計算結果の値の大きさに応じて、一つの特徴点セットを選択し、特徴点セット選択部が特徴点セットを選択する際の特徴点数を更新し、所定の条件が成立したときに前記認識タスクに適した特徴点を選択する特徴点選択部とを備え、特徴点セット選択部は、特徴点選択部が特徴点セットを選択したときに、当該特徴点セットに基づいて特徴点候補を定め、再度、特徴点セットを複数選択することを特徴とする特徴点選択システム。
【０２１８】
（付記１４）認識タスクは、個体の姿勢推定であり、認識誤差算出部は、更新前の特徴点数の特徴点を含む特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータ、およびそれらの微分値を用い、更新後の特徴点数に基づいて選択された特徴点セットに含まれる特徴点を用いた場合の認識誤差を近似的に算出する付記１３に記載の特徴点選択システム。
【０２１９】
（付記１５）認識タスクは、個体の姿勢推定であり、特徴点セット選択部は、特徴点選択部が特徴点セットを選択したときに、特徴点選択部が選択した特徴点セットに含まれる特徴点に関して、前記特徴点セットから削除した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した除外確率に応じて、前記特徴点を前記特徴点セットから除外し、特徴点選択部が選択した特徴点セットに含まれないが、最初の特徴点候補に含まれる特徴点に関して、前記特徴点セットに追加した場合の認識誤差を、前記特徴点セットについて計算した姿勢推定の認識誤差および姿勢パラメータおよびそれらの微分値を用いて近似的に計算し、当該認識誤差の逆数を用いて計算した追加確率に応じて、前記特徴点を前記特徴点セットに追加することにより、特徴点候補を定める付記１３または付記１４に記載の特徴点選択システム。
【０２２０】
（付記１６）特徴点選択部は、選択した特徴点セットの特徴点数が所定数まで減少したこと、または、選択した特徴点セットにおける認識誤差が前回選択した特徴点セットにおける認識誤差から一定量以上増加したこと、または、選択した特徴点セットにおける認識誤差が予め定めた閾値以上になったことを所定の条件として、前記所定の条件が成立したときに、その時に定められていた特徴点数に基づいて選択された複数の特徴点セットのうち、認識誤差が最小になる特徴点セットに含まれる特徴点群を、認識タスクに適した特徴点として選択する付記１３から付記１５のうちのいずれかに記載の特徴点選択システム。
【０２２１】
この出願は、２０１０年９月６日に出願された日本特許出願２０１０−１９９２２８を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【０２２２】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記の実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用の可能性】
【０２２３】
本発明は、個体の姿勢推定や個体識別等の認識タスクを行う装置等で用いられる特徴点を決定するシステムに好適に適用される。
【符号の説明】
【０２２４】
４１  特抽学習・評価データ生成手段
４２  学習データ生成手段
４３  学習パターン生成手段
４４  評価データ生成手段
４５  特徴点抽出器学習手段
４６  特徴点位置検出手段
５１  特徴点セット選択手段
５２  認識誤差算出手段
５３  特徴点選択手段
５４  特徴点重要度推定手段
【図１】
2012032747.tif 000028
【図２】
2012032747.tif 000029
【図３】
2012032747.tif 000030
【図４】
2012032747.tif 000031
【図５】
2012032747.tif 000032
【図６】
2012032747.tif 000033
【図７】
2012032747.tif 000034
【国際調査報告】
2012032747.tif 000035
2012032747.tif 000036
2012032747.tif 000037
2012032747.tif 000038