(57)【要約】【課題】画像上の特徴点を精度良く検出する画像処理装置を提供する。【解決手段】入力画像から複数の基準点を抽出する基準点設定部１４と、基準点の近傍のパターンを抽出するパターン抽出部１６と、学習画像から抽出した、基準点の近傍パターンと基準点から検出すべき特徴点へのベクトルの両者を持つ特徴セット群を保持する特徴セット保持部１８と、前記基準点から抽出した近傍パターンと前記特徴セット群とを比較し、最も似ているパターンを持つ特徴セットである最近傍特徴セットを選択するマッチング部２０と、前記選択された最近傍特徴セットが持つ基準点から特徴点へのベクトルに基づいて最終的な特徴点位置を計算する特徴点検出部２２とを具備する。【選択図】      図１
2009129237.tif 000002
【特許請求の範囲】
【請求項１】
画像が入力される入力部と、
前記入力画像に対し複数の基準点を設定する基準点設定部と、
前記入力画像中の前記各基準点の近傍パターンをそれぞれ抽出するパターン抽出部と、
学習画像に設定された複数の基準点毎に予め抽出したものであって、前記学習画像における前記基準点の近傍パターンと、前記基準点から検出すべき特徴点へのベクトルとを含む特徴セットを保持するセット保持部と、
前記入力画像の前記基準点から抽出した前記近傍パターンと、前記各特徴セットが含む近傍パターンとをそれぞれ比較し、前記入力画像の前記近傍パターンと最も類似する近傍パターンを持つ特徴セットを最近傍特徴セットとして、前記入力画像の前記基準点毎に選択するマッチング部と、
前記入力画像の前記基準点毎に選択した前記最近傍特徴セットが含む前記ベクトルに基づいて、前記入力画像中の前記特徴点の位置を計算する特徴点検出部と、
を有する画像処理装置。
【請求項２】
前記入力画像中の仮の特徴点と前記最近傍特徴セットが含む前記ベクトルに基づいて、前記ベクトルが前記入力画像中の前記仮の特徴点の方向を指しているか否かを表す適合度を計算し、前記適合度が第１の閾値より低い前記ベクトルを除去する除去部をさらに有し、
前記特徴点検出部は、前記除去されなかった残りの前記ベクトルに基づいて前記入力画像中の前記特徴点の位置を計算する、
請求項１記載の画像処理装置。
【請求項３】
前記最近傍特徴セットが含む前記近傍パターンと前記入力画像の前記近傍パターンとの類似度を計算し、前記類似度が第２の閾値より低い前記最近傍特徴セットを除去する除去部をさらに有し、
前記特徴点検出部は、前記除去されなかった残りの前記ベクトルに基づいて前記入力画像中の前記特徴点の位置を計算する、
請求項１記載の画像処理装置。
【請求項４】
前記除去部は、
前記ベクトル毎に得られる前記適合度に基づいて、前記入力画像中の前記特徴点を検出できる可能性を表す信頼度を計算し、前記信頼度が第３の閾値以下の場合は、前記特徴点検出部において、前記入力画像中の前記特徴点の位置を計算しないように制御する、
請求項２記載の画像処理装置。
【請求項５】
前記信頼度が前記第３の閾値以下の前記特徴点とは異なる他の前記特徴点の位置検出で用いた複数の前記最近傍特徴セットを利用して、前記入力画像中の前記第３の閾値以下の前記特徴点の位置を推定する推定部をさらに有する、
請求項４記載の画像処理装置。
【請求項６】
前記入力画像中の前記特徴点の一部を参照点として入力する外部入力部をさらに有し、
前記除去部は、前記参照点を前記仮の特徴点に設定し、前記仮の特徴点の位置に基づいて前記ベクトルの前記適合度を計算する、
請求項２記載の画像処理装置。
【請求項７】
前記除去部は、前記各ベクトルの適合度に応じて前記各ベクトルの重みをそれぞれ計算し、
前記特徴点検出部は、前記各ベクトル及び前記各ベクトルの重みに基づいて前記入力画像中の前記特徴点の位置の計算する、
請求項２記載の画像処理装置。
【請求項８】
前記セット保持部は、前記基準点の近傍パターンと前記ベクトルに加えて、前記特徴点付近のパターンを表す特徴点パターンも保持し、
前記マッチング部において選択された前記最近傍特徴セットに含まれる前記ベクトルが指し示す座標の周囲から、前記特徴点パターンとの類似度が最も高くなる点を探索して、前記探索により見つかった点を指し示すように前記ベクトルを修正する、
請求項１記載の画像処理装置。
【請求項９】
画像が入力される入力ステップと、
前記入力画像に対し複数の基準点を設定する基準点設定ステップと、
前記入力画像中の前記各基準点の近傍パターンをそれぞれ抽出するパターン抽出ステップと、
学習画像に設定された複数の基準点毎に予め抽出したものであって、前記学習画像における前記基準点の近傍パターンと、前記基準点から検出すべき特徴点へのベクトルとを含む特徴セットを保持するセット保持ステップと、
前記入力画像の前記基準点から抽出した前記近傍パターンと、前記各特徴セットが含む近傍パターンとをそれぞれ比較し、前記入力画像の前記近傍パターンと最も類似する近傍パターンを持つ特徴セットを最近傍特徴セットとして、前記入力画像の前記基準点毎に選択するマッチングステップと、
前記入力画像の前記基準点毎に選択した前記最近傍特徴セットが含む前記ベクトルに基づいて、前記入力画像中の前記特徴点の位置を計算する特徴点検出ステップと、
を有する画像処理方法。
【請求項１０】
前記入力画像中の仮の特徴点と前記最近傍特徴セットが含む前記ベクトルに基づいて、前記ベクトルが前記入力画像中の前記仮の特徴点の方向を指しているか否かを表す適合度を計算し、前記適合度が第１の閾値より低い前記ベクトルを除去する除去ステップをさらに有し、
前記特徴点検出ステップは、前記除去されなかった残りの前記ベクトルに基づいて前記入力画像中の前記特徴点の位置を計算する、
請求項９記載の画像処理方法。
【請求項１１】
前記最近傍特徴セットが含む前記近傍パターンと前記入力画像の前記近傍パターンとの類似度を計算し、前記類似度が第２の閾値より低い前記最近傍特徴セットを除去する除去ステップをさらに有し、
前記特徴点検出ステップは、前記除去されなかった残りの前記ベクトルに基づいて前記入力画像中の前記特徴点の位置を計算する、
請求項９記載の画像処理方法。
【請求項１２】
前記除去ステップは、
前記ベクトル毎に得られる前記適合度に基づいて、前記入力画像中の前記特徴点を検出できる可能性を表す信頼度を計算し、前記信頼度が第３の閾値以下の場合は、前記特徴点検出ステップにおいて、前記入力画像中の前記特徴点の位置を計算しないように制御する、
請求項１０記載の画像処理方法。
【請求項１３】
前記信頼度が前記第３の閾値以下の前記特徴点とは異なる他の前記特徴点の位置検出で用いた複数の前記最近傍特徴セットを利用して、前記入力画像中の前記第３の閾値以下の前記特徴点の位置を推定する推定ステップをさらに有する、
請求項１２記載の画像処理方法。
【請求項１４】
前記入力画像中の前記特徴点の一部を参照点として入力する外部入力ステップをさらに有し、
前記除去ステップは、前記参照点を前記仮の特徴点に設定し、前記仮の特徴点の位置に基づいて前記ベクトルの前記適合度を計算する、
請求項１０記載の画像処理方法。
【請求項１５】
前記除去ステップは、前記各ベクトルの適合度に応じて前記各ベクトルの重みをそれぞれ計算し、
前記特徴点検出ステップは、前記各ベクトル及び前記各ベクトルの重みに基づいて前記入力画像中の前記特徴点の位置の計算する、
請求項１０記載の画像処理方法。
【請求項１６】
前記セット保持ステップは、前記基準点の近傍パターンと前記ベクトルに加えて、前記特徴点付近のパターンを表す特徴点パターンも保持し、
前記マッチングステップにおいて選択された前記最近傍特徴セットに含まれる前記ベクトルが指し示す座標の周囲から、前記特徴点パターンとの類似度が最も高くなる点を探索して、前記探索により見つかった点を指し示すように前記ベクトルを修正する、
請求項９記載の画像処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力画像中に含まれる特徴点を頑健かつ高速に検出する画像処理装置及びその方法に関する。
【背景技術】
【０００２】
画像から、人間の顔や車などのある一定の形状を有する物体上の特徴点を検出することは、それら物体の検出のみならず認識する際にも非常に有用である。しかし、顔や車などの物体の見えや形状は特徴的な部分は共通しているものの、局所的な見えや変形は個々の物体に応じて様々であり、このような物体の多様な変動を柔軟に吸収し、精度良く物体上の特徴点を検出することが重要な課題となっている。
【０００３】
良く知られる一般化ハフ変換では、物体のエッジ点上の特徴点において、エッジ勾配をキーとして予め学習してあるテーブルから検出すべき参照点への位置情報を取り出し、投票を行うことで参照点を検出する。
【０００４】
また、非特許文献１では、エッジ勾配の代わりに特徴点の近傍パターンをキーとしてテーブルを参照し、特徴点から検出すべき参照点の存在確率を画像上の座標に投票し、最も確率の高い場所を検出結果とする方法が提案されている。
【０００５】
しかし、これら投票に基づいて最終的な特徴点位置を求める方法では、次の問題点がある。
【０００６】
第１の問題点は、物体の部分変形があった場合に投票先が一致しない点である。
【０００７】
第２の問題点は、正確な位置を求めるためには投票空間を細かく区切る必要があるが、その分投票空間が疎になり不安定な結果となる点である。
【０００８】
第３の問題点は、投票空間で表現すべきパラメータ数（スケールや、検出対象の特徴点数など）を増やすと投票空間は軸数が増えるために指数的に増加し、計算時間や投票の安定性に影響が出る点である。
【非特許文献１】B. Leibe and B. Schiele., 「Interleaved Object Categorization and Segmentation」, in British Machine Vision Conference （BMVC'03）, Norwich, UK, Sept. 9-11, 2003.
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上記したように、従来技術には、検出すべき特徴点の位置を投票に基づいて決定していたため、部分的な変形を含むような場合にうまく検出できない問題点があった。
【００１０】
そこで本発明は、上記従来技術の問題点を解決するためになされたものであって、検出すべき特徴点の位置を直接投票する方法を用いることなく、入力画像中に含まれる特徴点を頑健かつ高速に検出する画像処理装置及びその方法に関する。
【課題を解決するための手段】
【００１１】
本発明は、画像が入力される入力部と、前記入力画像に対し複数の基準点を設定する基準点設定部と、前記入力画像中の前記各基準点の近傍パターンをそれぞれ抽出するパターン抽出部と、学習画像に設定された複数の基準点毎に予め抽出したものであって、前記学習画像における前記基準点の近傍パターンと、前記基準点から検出すべき特徴点へのベクトルとを含む特徴セットを保持するセット保持部と、前記入力画像の前記基準点から抽出した前記近傍パターンと、前記各特徴セットが含む近傍パターンとをそれぞれ比較し、前記入力画像の前記近傍パターンと最も類似する近傍パターンを持つ特徴セットを最近傍特徴セットとして、前記入力画像の前記基準点毎に選択するマッチング部と、前記入力画像の前記基準点毎に選択した前記最近傍特徴セットが含む前記ベクトルに基づいて、前記入力画像中の前記特徴点の位置を計算する特徴点検出部と、を有する画像処理装置である。
【発明の効果】
【００１２】
本発明によれば、入力画像中に含まれる特徴点を頑健かつ高速に検出できる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施形態の画像処理装置１０について図面を参照して説明する。
【００１４】
（第１の実施形態）
以下、本発明に係わる第１の実施形態の画像処理装置１０について図１〜図４に基づいて説明する。
【００１５】
（１）画像処理装置１０の構成
画像処理装置１０の構成について図１のブロック図に基づいて説明する。
【００１６】
本実施形態の画像処理装置１０は、検出対象となる物体を含んだ画像（入力画像）を入力する画像入力部１２と、入力画像から複数の基準点を抽出する基準点設定部１４と、基準点の近傍のパターンを抽出するパターン抽出部１６と、予め学習画像から抽出しておいた基準点の近傍パターンと基準点から検出すべき特徴点へのベクトルの両者を持つ特徴セット群を保持する特徴セット保持部１８と、基準点から抽出した近傍パターンと特徴セット群とを比較し、最も似ているパターンを持つ特徴セットである最近傍特徴セットを選択するマッチング部２０と、前記選択された最近傍特徴セットが持つ基準点から特徴点へのベクトルに基づいて最終的な特徴点位置を計算する特徴点検出部２２を備えている。
【００１７】
次に、各部１２〜２０の動作について説明する。
【００１８】
（２）画像入力部１２
まず、画像入力部１２は、検出対象となる物体を含んだ入力画像を入力する。
【００１９】
画像入力部１２を構成する装置の一つの例として、ＵＳＢカメラやデジタルカメラなどが挙げられる。
【００２０】
また、予め撮影、保存された顔画像データを保持している記録装置やビデオテープ、ＤＶＤなどを用いてもよいし、スキャナやその他の特殊な機材で撮影してもよい。ネットワーク等を経由して画像を入力してもかまわない。
【００２１】
画像入力部１２より得られた入力画像は逐次、基準点設定部１４に送られる。
【００２２】
（３）基準点設定部１４
基準点設定部１４では、入力画像に対し検出すべき特徴点の方向を示すベクトルの相対的な位置の基準となる基準点を設定する。
【００２３】
この基準点は、特にどのような点を用いなければならないという制限はなく、これまで提案されているどのような検出方法を用いてもよい。
【００２４】
例えば、入力画像の基準点を検出する方法としてHarrisらのコーナー点検出方法（C. Harris and M. Stephens, 「A combined corner and edge detector」, Proc. of Alvey Vision Conference, pp. 147-151, 1988.）が提案されている。これは画像中のエッジ勾配に基づいてコーナー度を計算し、コーナー度が大きい画素をコーナー点として用いる。
【００２５】
また、Difference-of-Gaussian（ＤｏＧ）と呼ばれる異なるスケールの平滑化画像の差分により計算される値が極値となる点を基準点として用いてもよい。
【００２６】
また、輝度分布に対してインポータンスサンプリングと呼ばれるような方法を適用して選択された点を基準点として用いてもよい。
【００２７】
また、入力画像中にランダムに基準点を配置しても構わない。
【００２８】
本実施形態では、入力画像中に簡単のため格子状に基準点を配置させた場合について説明する。しかし、他の基準点の設定方法を用いたとしても、以下の処理は全て同様に扱うことができる。
【００２９】
図２に、入力画像である顔画像に対して格子状に基準点を配置した場合の例を示す。図２中の四角で示す点が基準点である。
【００３０】
また、必須ではないが、基準点抽出の前処理として、対象の物体が大まかに検出されている方が処理速度の面で好適である。例えば、入力画像中の顔から瞳を検出したい場合に、予め顔検出器を用いて顔の位置を大まかに検出しておく、などが考えられる。
【００３１】
（４）パターン抽出部１６
パターン抽出部１６では、基準点設定部１４で抽出された基準点を基準として、入力画像中におけるその近傍のパターンを抽出する。
【００３２】
パターンは、入力画像の輝度値をそのまま用いてもよい。また、画像処理フィルタなどの特徴変換を用いて特徴量に変換してもよい。
【００３３】
また、基準点の位置とパターンの位置関係も、基準点がパターンの中心である必要はなく、任意のオフセットを持たせてもよい。
【００３４】
また、パターンの変化に対応するために、スケールを変えたパターンや回転させたパターンも同時に抽出することも可能であるし、スケールや回転に対して不変な特徴量を用いてもよい。
【００３５】
ここでは、非特許文献（N. Dalal and B. Triggs，「Histograms of Oriented Gradients for Human Detection」, IEEE Computer Vision and Pattern Recognition, pp. 886-893，2005.）で述べられている画素のエッジ勾配方向のヒストグラム（Histogram of Oriented Gradients: ＨｏＧ）特徴を用いた場合について説明する。
【００３６】
まず、基準点を中心として縦横Ｍ×Ｎピクセルの矩形パターンを切り出してＨｏＧ特徴に変換する。このＨｏＧ特徴を以後、基準点における近傍パターン（または単にパターン）と呼ぶこととする。
【００３７】
そして、パターン抽出部１６では、入力画像中の近傍パターンを全ての基準点に対して計算して処理完了となる。
【００３８】
（５）特徴セット保持部１８
特徴セット保持部１８では、予め学習画像から抽出しておいた近傍パターンと検出すべき特徴点へのベクトルを組にした特徴セット群を保持する。
【００３９】
（５−１）特徴点セット
特徴セットについて図３を用いて説明する。
【００４０】
まず、学習画像に対して、上記した基準点抽出とパターン抽出を行い、基準点とその近傍パターンを抽出しておく。
【００４１】
そして、学習画像には、検出すべき特徴点の位置を予め手作業により入力するなどして教示されているとする。すると、基準点からこの特徴点を結ぶベクトルを定義することができる。図３では、図３中の左上の基準点に対し、Ｘ印で表した左瞳特徴点へのベクトルを矢印で表す。この左上の基準点における近傍パターンと、特徴点へのベクトルの両者を組にしたものを特徴セットとする。
【００４２】
（５−２）複数の特徴点の場合
検出すべき特徴点の数はいくつあっても構わない。
【００４３】
特徴点が複数（Ａ個）存在する場合には、基準点からそれぞれの特徴点へのＡ本のベクトルが定義できる。このときの特徴セットは、基準点における近傍パターンとＡ本のベクトルの組として定義することができる。
【００４４】
（５−３）物体と背景が区別可能な場合
物体の輪郭線などが入力されており、物体と背景が区別可能な場合で、背景上に設定された基準点にはベクトルではなく背景であることを示すフラグを設定してもよい。
【００４５】
背景フラグを設定することで、後段のマッチング部２０で入力画像から不要な背景を除去することが可能である。
【００４６】
（５−４）ＨｏＧ特徴の利用
上記したＨｏＧ特徴をパターンとして用いる場合には、近傍パターンでのエッジ方向がヒストグラム化されているため、エッジの主方向と特徴点へのベクトルとを関連付けることも可能である。
【００４７】
つまり、ベクトルを基準点から特徴点へのベクトルとして定義するのではなく、近傍パターンのエッジ方向から特徴点方向へ角度θ回転したベクトルとして相対的に定義することにより、近傍パターンの回転に対してベクトルは不変となる。
【００４８】
このようなベクトルの回転に対して不変となる定義はＨｏＧ特徴によらず、パターン内の主となる方向成分が定義できるような特徴量であれば、どのような特徴を用いても構わない。
【００４９】
（５−５）まとめ
特徴セット保持部１８は、以上の処理を、全ての学習画像中の全ての基準点に対して行い、特徴セット群を計算して保持する。
【００５０】
なお、この特徴セット群は全てを保持してそのまま利用してもよいが、似ている特徴セット同士（近傍パターンとベクトルが両方とも類似している）はまとめて１つの特徴セットにしてもよいし、平均や主成分分析、クラスタリング方法などを用いて複数の類似特徴セット同士を統合し、特徴セット群を記憶するメモリの使用量を削減させてもよい。
【００５１】
（６）マッチング部２０
マッチング部２０では、入力画像から抽出した近傍パターンと特徴セット群を比較し、最も似ている特徴セットを選択する。
【００５２】
まず、基準点設定部１４とパターン抽出部１６により、入力画像から基準点と各基準点における近傍パターンが抽出されているとする。
【００５３】
次に、ある基準点の近傍パターンに対して、特徴セット保持部１８が保持する特徴セット群とパターンマッチングを行い、最も似ているパターンを持つ特徴セットを選択する。
【００５４】
このパターンマッチングはどのような方法を用いても構わない。例えばよく知られる最近傍探索などが利用できる。最も単純な最近傍探索は、登録されているデータ全てに対してパターン同士の距離を計算し、最も距離が近くなるパターンを出力する。
【００５５】
この他にも高速化のため近似的に計算を行う近似最近傍探索（S. Arya, D. Mount, R. Silverman and A. Y. Wu: 「An optimal algorithm for approximate nearest neighbor searching」, Journal of the ACM, 45, 6, pp. 891_923, 1998.）や、ハッシュ表を用いた近似最近傍探索（M. Datar, Ｎ. Immorlica, P. Indyk and V. Mirrokni: 「Locality-sensitive hashing scheme based on p-stable distributions」, Proc. of the 20th Annual Symposium on Computational Geometry, pp. 253_262, 2004.）などが提案されている。
【００５６】
これらの方法を使う際には、予め保持している特徴セット群のツリー構造化や、特徴セット群に対するハッシュ表を定義しておけばよい。
【００５７】
また、最近傍探索以外にも、これまで提案されているいかなるマッチング方法を適用してもよい。
【００５８】
ここで、ある近傍パターンに対して選択された最も似ている特徴セットのことを「最近傍特徴セット」と呼ぶこととする。これを入力画像中の全ての基準点（近傍パターン）に対して計算し、対応する最近傍特徴セットをそれぞれ求めておく。
【００５９】
（７）特徴点検出部２２
特徴点検出部２２では、基準点毎に求められた最近傍特徴セットが持つベクトルに基づいて、検出すべき特徴点の位置を計算する。
【００６０】
マッチング部２０により、入力画像上の各基準点には対応する最近傍特徴セットが求められている。それぞれの最近傍特徴セットは、ベクトルを持つので、これを基準点から検出すべき特徴点へのベクトルとして利用する。
【００６１】
図４に基準点毎に求めた最近傍特徴セットのベクトルの例を示す。なお、図３と同様に左瞳特徴点を検出する場合の例である。
【００６２】
マッチングにより近傍パターンに対して適切な最近傍特徴セットが選択された場合、基準点から特徴点へのベクトルを得ることができる。
【００６３】
なお、近傍パターン内のエッジ方向に対する相対的な角度でベクトルが定義されている場合は、ここで近傍パターンのエッジ方向を用いて画像内の絶対的な方向を示すベクトルに変換しておく。
【００６４】
（７−１）特徴点位置を計算する方法
以下、基準点からのベクトルが求められた場合に、幾何学的な関係から特徴点位置を計算する方法の一例を示す。
【００６５】
まず、基準点が全部でｎ個のとき、ｉ番目の基準点の座標を（ｘｉ，ｙｉ）、求めたベクトルを（ｕｉ，ｖｉ）とすると、（ｘｉ，ｙｉ）を通り（ｕｉ，ｖｉ）方向に進む直線ｌｉを式（１）のように表す。
【数１】
2009129237.tif 000003
【００６６】
このとき、任意の点（ｘ，ｙ）から直線ｌｉへの距離ｄｉは式（２）のようになる。以後、単に「点とベクトルの距離」と述べた場合は、この基準点を通りベクトル方向に進む直線と点との距離ｄｉのことを指すとする。
【数２】
2009129237.tif 000004
【００６７】
従って、点（ｘ，ｙ）と全ての基準点における直線との距離の総和Ｅは、式（３）のようになる。
【数３】
2009129237.tif 000005
【００６８】
この距離の総和Ｅが最も小さくなる点（ｘ'，ｙ'）を、最終的な特徴点の位置とすればよい。
【００６９】
（７−２）複数個の特徴点の場合
なお、検出すべき特徴点の数が複数個存在する場合においても、特徴点検出部２２の動作を複数回実行することで、同様に処理することが可能である。
【００７０】
複数個の特徴点を検出する場合には、特徴セットは各特徴点に対応するベクトルをそれぞれ持つので、特徴点の種類別に基準点とベクトルで表される直線と点（ｘ，ｙ）との距離の総和を計算し、特徴点（ｘ’，ｙ’）を求めていけばよい。
【００７１】
（８）効果
このように本実施形態に係わる画像処理装置１０によれば、検出すべき特徴点の位置を投票するのではなく、画像中の複数の基準点から検出すべき特徴点へのベクトルを求め、ベクトル群に対して最も距離が小さくなる幾何学的な計算に基づいて最終的な特徴点位置を計算できる。
【００７２】
（第２の実施形態）
以下、本発明に係わる第２の実施形態の画像処理装置１０について図５と図６に基づいて説明する。
【００７３】
第１の実施形態の画像処理装置１０は、特徴点検出部２２において全てのベクトルを用いて特徴点の計算を行った。しかし、本実施形態では、予め外れ値を除去した後に特徴点を計算する。
【００７４】
（１）画像処理装置１０の構成
第２の実施形態の画像処理装置１０について図５のブロック図に基づいて説明する。
【００７５】
本実施形態の画像処理装置１０は、第１の実施形態とマッチング部２０までは同一であるが、マッチング部２０で得られたベクトルの外れ値の除去を外れ値除去部２４において行う点が異なる。
【００７６】
（２）外れ値除去部２４
以下、マッチング部２０まで処理が完了し、基準点毎に最近傍特徴セット（ベクトル）が得られたものとし、後段の外れ値除去部２４の動作について説明する。
【００７７】
図４の例に示すように、マッチング部２０では、特徴点があるべき位置に対して大きく外れたベクトルを持つ最近傍特徴セットが誤って選択されてしまう可能性がある。このような外れ値となるベクトルは、特徴点の計算において誤差の原因となるため、外れ値除去部２４により予め除去することで、特徴点検出精度を向上させることができる。
【００７８】
図６に外れ値除去の例を示す。図６中の点線で描かれた矢印が外れ値として除去された例を示している。外れ値の除去に関してはこれまで数多くの研究がなされており、いかなる方法を用いても構わない。以下、その方法を例示する。
【００７９】
（２−１）第１の方法
第１の方法として、ロバスト推定により外れ値を除去することができる。そこで、ＬＭｅｄＳ（Least Median of Squares）と呼ばれるロバスト推定法により外れ値を除去する方法について説明する。
【００８０】
まず、基準点をランダムにＦ個選択し、選択された基準点におけるＦ本のベクトルを用いて仮の特徴点座標を計算する。このベクトルから特徴点座標の計算は、上記の特徴点検出部２２での方法と同じである。
【００８１】
次に、この仮の特徴点座標を用いて全ての基準点におけるベクトルとの誤差（距離）ｄｉを計算する。この距離ｄｉが、ベクトルを評価する適合度であり、この距離ｄｉが小さいほど適合度が高くなる。そして、式（４）で表すＬＭｅｄＳ基準を用いて仮の特徴点座標を評価する。
【数４】
2009129237.tif 000006
【００８２】
但し、ｍｅｄは全ての距離ｄｉの中央値を取るオペレータである。
【００８３】
次に、この処理を必要な回数繰り返し、最もＬＭｅｄＳ評価値が小さくなる最良の特徴点座標を計算する。
【００８４】
次に、得られた最良の特徴点の座標をこのまま最終的な出力する。
【００８５】
また、この特徴点との距離が、ある閾値を超えるベクトルを外れ値として除去し、その後に特徴点座標を再度求める方がより精度良く特徴点座標を求めることができる。その閾値は、式（５）で表される距離の標準偏差σに基づいて決定できる。
【数５】
2009129237.tif 000007
【００８６】
但し、Ｃは誤差を補正する係数、ｎは基準点の数である。
【００８７】
このσの定数倍（例えば２．５倍）を閾値として、それより大きな距離ｄｉを持つようなベクトルを外れ値として除去する。
【００８８】
そして、後段の特徴点検出部２２では、外れ値として除去されずに残ったベクトルを用いて、第１の実施形態の説明で述べたように特徴点の計算を行えばよい。
【００８９】
必要なら、さらに得られた特徴点を仮の特徴点として外れ値除去部２４に戻り外れ値除去を行うなど、外れ値除去と特徴点検出を複数回繰り返しても構わない。
【００９０】
（２−２）第２の方法
第２の方法として、マッチング部２０で求めた最近傍特徴セットと近傍パターンの類似度を利用する方法がある。
【００９１】
マッチングの際に、近傍パターンに最も適した特徴セットを選択する。その際にマッチングの度合いとして距離や類似度などが得られる。
【００９２】
ある基準点で選択された最近傍特徴セットが、他の基準点で選択された最近傍特徴セットと比較して類似度が閾値より小さい（類似度が低い）場合は、誤って選択された可能性が高いため、外れ値として除外する。
【００９３】
（３）効果
本実施形態によれば、マッチング部２０で求めたベクトルのうち、特徴点の検出に悪影響を及ぼす可能性がある外れ値を除去し、その後に特徴点を改めて計算することにより、精度良く特徴点の計算ができる。
【００９４】
（第３の実施形態）
第３の実施形態の画像処理装置１０について図６、図７、図８に基づいて説明する。
【００９５】
第２の実施形態において、外れ値除去を行った結果、多数のベクトルが外れ値と判断され除外されると、特徴点の計算に用いるベクトル数が減り、その特徴点の計算結果は不安定になる可能性が高くなり、特徴点検出精度の信頼性が低いと判断できる。
【００９６】
そこで、本実施形態の画像処理装置１０には、そのような検出の信頼度が低い特徴点は検出不可能（リジェクト）とし、他の特徴点検出結果を利用してリジェクトされた特徴点を推定することもできる。
【００９７】
（１）画像処理装置１０の構成
図７に本実施形態に係わる画像処理装置１０の構成を表す。
【００９８】
本実施形態の画像処理装置１０は、第２の実施形態とマッチング部２０までは同一であり、外れ値除去部２４の外れ値除去処理、特徴点検出部２２の処理は同じであるが、特徴点推定部２６において、外れ値除去部２４で除去されたベクトル数に応じて信頼度を計算し、必要があれば特徴点推定部２６で特徴点の推定を行う点が異なる。
【００９９】
（２）信頼度Ｔの計算
以下、外れ値除去部２４において外れ値除去の処理が完了したものとし、特徴点検出の信頼度の計算と、後段の特徴点推定部２６について説明する。
【０１００】
外れ値除去部２４において、基準点の数をｎ、外れ値として除去された基準点の数をｎ’とすると、外れ値除去を行った結果の特徴点計算の信頼度Ｔを式（６）で定義する。
【数６】
2009129237.tif 000008
【０１０１】
信頼度Ｔがある一定の閾値以下であれば、基準点の数に対して外れ値が多いため、マッチング部２０で選択されたベクトル群は規則性が少なく、特徴点付近で収束する可能性は低いと判断できる。このような状況で特徴点を計算しても計算に用いるベクトル数が少なく、計算結果が不安定になるため特徴点検出部２２をスキップし、検出不可能（リジェクト）として扱う。
【０１０２】
検出すべき特徴点数が１点のみの場合にリジェクトが発生した際（または、検出すべき全ての特徴点がリジェクトと判断された場合）は、リカバリする手段がないので、そこで検出処理は終了となる。
【０１０３】
（３）特徴点推定部２６
一方、複数の特徴点を検出する場合に一部の特徴点がリジェクトされた際には、特徴点推定部２６において、検出に成功した特徴点の情報を利用してリジェクトされた特徴点を推定する。
【０１０４】
例えば図６では、一部のベクトルは外れ値として除去されているが、残りは正しく特徴点の方向を指し示している。このとき、正しく特徴点方向を指し示しているベクトルを持つ特徴セットは、与えられた近傍パターンに対し、特徴セット群から適切に選択されたと考えられる。
【０１０５】
このような特徴セットはある特徴点に対するベクトルだけでなく、他の特徴点に対するベクトルも正しく特徴点の方向を指し示すことが期待できる。
【０１０６】
したがって、リジェクトされずに検出できた特徴点で用いられた特徴セットを利用してリジェクトされた特徴点の計算を行えば、精度良く特徴点の位置を推定できる。
【０１０７】
（４）具体例
具体的には以下の手順で特徴点の推定を行う。図８は特徴点推定を含む特徴点検出のフローチャートである。
【０１０８】
ステップ１〜３において、外れ値除去部２４で外れ値の除去を行い、リジェクトされずに特徴点検出部２２で特徴点の検出を行った場合、特徴点の計算に利用した特徴セットに設定したカウンタをインクリメントする。
【０１０９】
ステップ４において、この特徴点検出を全ての特徴点に対して行い、ステップ５において、リジェクトした特徴点が無ければ検出成功として処理終了となる。
【０１１０】
ステップ６において、リジェクトした特徴点がある場合は、各基準点の特徴セット毎のカウンタを調べ、カウンタ値が閾値以上（例えば、特徴点数の５０％）であれば、その特徴セットは信頼できるとする。
【０１１１】
ステップ７において、信頼できる特徴セット数を調べ、これが閾値以下（例えば、基準点の数の３０％以下）であれば、信頼できる特徴点数が不足していると判断し、推定は行わずにリジェクトされた特徴点については検出失敗とする。
【０１１２】
ステップ７において、一定以上のカウンタ値を持つ特徴セットが十分存在する場合は、ステップ８において、これらの特徴セットを用いて特徴点座標を特徴点検出部２２で述べた方法により計算する。
【０１１３】
リジェクトされた特徴点に対しては全て共通の特徴セットを用いてもよいし、特徴点座標の位置（事前確率などで予想される位置）に応じて、特徴点位置に近い基準点の特徴セットのみを用いてもよい。
【０１１４】
ステップ９において、全ての特徴点において推定ができたら検出成功として処理を終了する。
【０１１５】
（４）効果
本実施形態によれば、外れ値除去部２４で信頼度を計算し、信頼度が低い特徴点に対しては、他の信頼度の高い特徴点検出結果に基づいて推定することで、より精度良く特徴点の検出できる。
【０１１６】
（変更例）
本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【０１１７】
以下、変更例について説明する。
【０１１８】
（１）変更例１
画像処理装置１０の変更例１について、図９に基づいて説明する。
【０１１９】
（１）画像処理装置１０の概要
第２の実施形態において、検出すべき特徴点を全て計算していたが、一部の特徴点を人間、あるいは別の検出方法により検出しておき、その別途検出された特徴点（以後、区別のため参照点と呼ぶ）を参考にしてベクトルの外れ値を計算し、適切なベクトルを選択あるいはベクトルを適切に修正することも可能である。
【０１２０】
特徴点入力手段が別途存在するとし、この特徴点入力手段により検出すべき特徴点の一部が参照点として入力され、参照点は人手で入力されるなど、精度が高く信頼できる点であると仮定する。
【０１２１】
外れ値除去部２４では、仮に設定した特徴点とベクトルとの距離を適合度として計算し、それらの距離の和を基準として外れ値を判断していたが、この仮の特徴点の代わりに参照点を用いて外れ値を判定することを考える。
【０１２２】
参照点は正しいと仮定しているので、参照点とベクトルの距離が大きいもの、すなわち適合度が低いものほど外れ値と判定すればよい。
【０１２３】
複数の参照点が得られている場合は、参照点毎のベクトルとの距離を計算してその平均などから外れ値を判断してもよいし、参照点を基準としてベクトルを補正した後に距離を計算してもよい。
【０１２４】
（２）補正方法
ベクトルの補正の方法について、図９を用いて説明する。
【０１２５】
図９では、参照点として左瞳と左口端が入力されており、各参照点に対して、基準点におけるベクトル（特徴セット）が得られているとする（図９左参照）。
【０１２６】
このとき、そのまま参照点とベクトルとの距離を計算して外れ値の判定をするのではなく、参照点とベクトルの距離が最小となるように変換した後に外れ値の判定を行う（図９右参照）。
【０１２７】
変換は、基準点を中心としてベクトルを回転させてもよいし、他のいかなる変換を用いても構わないが、参照点とベクトルとの距離が必ずゼロになるような変換（例えば、参照点が２点しか得られない状態で２本のベクトルにアフィン変換を適用すると、必ずベクトルは参照点方向を指すように変換できてしまう）は除くこととする。
【０１２８】
ここでは参照点とベクトルとの距離を最小とするような、基準点を中心とする回転変換Ｒを適用したとすると、この基準点における特徴セットが外れ値かどうかは、回転変換Ｒを適用した後のベクトルと参照点の距離によって判断する。
【０１２９】
他の基準点についても同様に参照点との距離を最小化するような回転変換を求め、外れ値かどうか判定すればよい。
【０１３０】
なお、この変換は参照点の数が多い方が変換後のベクトルの確からしさが増し、好適である。そのため、参照点の数が少ない場合には変換量を制限するなどの工夫を行ってもよい。
【０１３１】
また、例えば左瞳が参照点として与えられている場合に左目尻を検出するというように、参照点付近の特徴点を検出する場合には、複数の参照点が得られていても特徴点に近い参照点を基準としてベクトルを変換してもよい。
【０１３２】
特徴点検出部２２で特徴点を計算する際には、それぞれのベクトルに事前に上記した変換を施す以外は全て同様に処理すればよい。
【０１３３】
（２）変更例２
画像処理装置１０の変更例２について説明する。
【０１３４】
（２−１）第２の実施形態の変更例
第２の実施形態において、ベクトルの外れ値を計算し、閾値を超えるものを除去した後に特徴点の計算を行ったが、外れ値の除去の方法は除去されたベクトルを特徴点検出部２２でベクトルを一切使わないというだけでなく、外れ値の度合いに基づいて重みを設定し、この重みに従って特徴点の計算を行うことも可能である。
【０１３５】
外れ値除去部２４では、設定した特徴点とベクトルの距離ｄｉに基づいて外れ値を判断する。この距離ｄｉに従ってｄｉがゼロなら１、ｄｉが大きくなるほどゼロに近づくような重みｗｉを設定すればよい。第２の実施形態で述べた距離の閾値で外れ値を判断するのは、閾値を超えたらｗｉ＝１、閾値以下でｗｉ＝０と定義した場合と同一となる。
【０１３６】
特徴点検出部２２では得られた重みに従って式（７）の誤差Ｅｗを最小化するような特徴点を求めればよい。
【数７】
2009129237.tif 000009
【０１３７】
（２−２）第３の実施形態の変更例
第３の実施形態で述べた特徴点の推定に関する信頼度の計算についても、重みを利用して式（８）のように変更することもできる。
【数８】
2009129237.tif 000010
【０１３８】
信頼度Ｔｗが得られれば、後の特徴点検出は上で述べた方法により計算することができる。
【０１３９】
（３）変更例３
第１の実施形態において、点（ｘ，ｙ）とベクトルとの距離を点と直線の距離で表現したが、その他の尺度を用いても構わない。
【０１４０】
例えば、基準点（ｘｉ，ｙｉ）と点（ｘ，ｙ）を結ぶベクトル（ｘ−ｘｉ，ｙ−ｙｉ）と、基準点（ｘｉ，ｙｉ）とベクトル（ｕｉ，ｖｉ）で表現されるベクトル（ｘｉ＋ｕｉ，ｙｉ＋ｖｉ）の角度θを用いてもよい。また、点（ｘ，ｙ）と基準点（ｘｉ，ｙｉ）とベクトル（ｕｉ，ｖｉ）で表現される点（ｘｉ＋ｕｉ，ｙｉ＋ｖｉ）との距離ｄ’ｉを用いてもよい。
【数９】
2009129237.tif 000011
【０１４１】
特徴点検出部２２での計算方法については、これらの角度や距離に基づく尺度（以下、「距離尺度」という）において、その緩和が最小となる特徴点を求めればよく、全ての議論は同様に成り立つ。
【０１４２】
また、複数の距離尺度で特徴点を求めた後に、重み付け加算などで統合してもよい。
【０１４３】
また、部分変形が大きいことが予め予想されれば点と直線の距離ｄｉ、部分変形が少ないことが予想されれば点と点との距離ｄ’ｉなど、特徴点毎に距離尺度を適応的に変えてもよい。
【０１４４】
例えば、検出された特徴点位置に対して上記した距離ｄ’ｉを全ての基準点に対して求め、その和を収束度とする。収束度は理想的な条件下ではゼロとなり、対象の部分的な変形やパターンのマッチング誤りなどに応じて大きくなる量である。この収束度が小さければ距離ｄ’ｉを用いて特徴点を計算し、収束度が大きければ距離ｄｉを用いて特徴点を計算する。
【０１４５】
また、収束度に応じて両者の計算結果の重みづけ和をとれば、部分変形に応じた適応的な特徴点検出が可能となる。
【０１４６】
（４）変更例４
画像処理装置１０の変更例４について、図１０に基づいて説明する。
【０１４７】
（４−１）第１の実施形態の変更例
第１の実施形態において、マッチング部２０で選択されたベクトルを特徴点パターンによって修正することも可能である。
【０１４８】
図１０に示すように、学習画像を用いて基準点における特徴セットを学習する際に、近傍パターンとベクトルと一緒に特徴点付近のパターンである特徴点パターンも記録しておく（図１０左参照）。
【０１４９】
入力画像から特徴点を検出する際は、マッチング部２０で基準点に対応する特徴セットを選択し、特徴セットが持つベクトルが指し示す座標の周囲を上記した特徴点パターンでマッチングを行って探索する（図１０右参照）。
【０１５０】
探索した結果、最も特徴点パターンとの類似度が高い場所を指すようにベクトルを修正する。入力画像上の全ての基準点に対して同様にベクトルの修正を行った後に、特徴点検出部２２で特徴点の位置の計算を行う。
【０１５１】
（４−２）第２の実施形態の変更例
また、この特徴点パターンは第２の実施形態で述べた外れ値除去部２４で利用することもできる。
【０１５２】
図１０右のように、入力画像上の近傍点に対して特徴セットが選択されていたとすると、基準点からこの特徴セットが持つベクトルが指し示す座標におけるパターンと特徴点パターンとのマッチングを行い、ベクトルが指し示す地点の特徴点らしさを評価する類似度を求める。
【０１５３】
この類似度を基準としてベクトルが外れ値かどうかを判定する。
【０１５４】
なお、第２の実施形態で述べた距離を基準とする外れ値判定と、特徴点パターンとの類似度による外れ値判定の両者を組み合わせてもよい。
【０１５５】
（５）変更例５
上記各実施形態では、特徴点を検出する画像としては、顔画像を用いたが、これに限らず心臓などの臓器が写った医療画像、または、車などが写った画像から特徴点を抽出する場合についても適用できる。
【図面の簡単な説明】
【０１５６】
【図１】本発明の第１の実施形態に係わる構成を示すブロック図である。
【図２】基準点の設定方法に関する図である。
【図３】学習画像上の基準点における近傍パターンとベクトルの設定に関する図である。
【図４】入力画像上の基準点に対して得られたベクトルの説明に関する図である。
【図５】本発明の第２の実施形態に係わる構成を示すブロック図である。
【図６】ベクトルの外れ値除去の説明に関する図である。
【図７】本発明の第３の実施形態に係わる構成を示すブロック図である。
【図８】本発明の第３の実施形態の特徴点推定に係わるフローチャートである。
【図９】参照点を利用したベクトルの補正に関する図である。
【図１０】特徴点パターンによるベクトルの補正に関する図である。
【符号の説明】
【０１５７】
１０    画像処理装置
１２    画像入力部
１４    基準点設定部
１６    パターン抽出部
１８    特徴セット保持部
２０    マッチング部
２２    特徴点検出部
２４    外れ値除去部
２６    特徴点推定部
【図１】
2009129237.tif 000012
【図２】
2009129237.tif 000013
【図３】
2009129237.tif 000014
【図４】
2009129237.tif 000015
【図５】
2009129237.tif 000016
【図６】
2009129237.tif 000017
【図７】
2009129237.tif 000018
【図８】
2009129237.tif 000019
【図９】
2009129237.tif 000020
【図１０】
2009129237.tif 000021