(57)【特許請求の範囲】
【請求項１】
複数の弱判別器がカスケード接続された弱判別器列が分岐し、分岐後の各々の枝に弱判別器列が接続する構造のパターン識別器を生成するパターン識別器生成方法であって、
評価手段が、評価データのセットを前記弱判別器列に入力して得られる処理結果に基づいて、分岐後の弱判別器列が接続すべき段数に到達したか否かを評価する評価工程と、
決定手段が、前記評価工程の評価に基づき、前記弱判別器列を非分岐で接続すべき弱判別器の段数を決定する決定工程と
を有することを特徴とするパターン識別器生成方法。
【請求項２】
前記評価データのセットには、検出対象となる画像の変動カテゴリに分類されたデータが含まれ、
前記カスケード接続の分岐後の各枝は、前記分類された前記変動カテゴリに対応することを特徴とする請求項１に記載のパターン識別器生成方法。
【請求項３】
前記弱判別器の各々は、
入力された前記評価データのセットに対する判別結果としてスコア値を算出し、前段の弱判別器で出力された出力値に当該スコア値を加算した累積スコア値を後段の弱判別器に出力することを特徴とする請求項１に記載のパターン識別器生成方法。
【請求項４】
前記評価データのセットには、非検出対象パターンの集合で構成されるデータが含まれ、
前記弱判別器の各々は、前記累積スコア値が予め定められた閾値をこえる場合に処理の打ち切りを決定することを特徴とする請求項３に記載のパターン識別器生成方法。
【請求項５】
前記評価工程では、前記評価データのセットを前記分岐後の各々の前記弱判別器列に入力し、前記弱判別器列を構成する前記弱判別器の各々が出力する前記累積スコア値に基づいて、前記弱判別器列が接続すべき段数に到達したか否かを評価することを特徴とする請求項３に記載のパターン識別器生成方法。
【請求項６】
前記決定工程では、前記評価工程の評価に基づき前記分岐後の各々の前記弱判別器列における前記累積スコア値の差分が予め定められた値以上になる段数を、非分岐で前記弱判別器を接続すべき段数として決定することを特徴とする請求項５に記載のパターン識別器生成方法。
【請求項７】
前記決定工程では、前記評価工程の評価に基づき前記分岐後の前記弱判別器列の数が３以上となる場合には、全ての前記弱判別器列のうち２つの前記弱判別器列の組合せで算出した前記累積スコア値の差分を求め、全ての前記弱判別器列の組合せについて前記差分を統合した値が予め定められた値以上になる段数を、非分岐で前記弱判別器を接続すべき段数として決定することを特徴とする請求項５に記載のパターン識別器生成方法。
【請求項８】
分岐選択手段が、前記累積スコア値に基づき、前記評価データのセットに対して処理を継続すべき分岐枝を選択する分岐選択工程を更に備えることを特徴とする請求項３に記載のパターン識別器生成方法。
【請求項９】
前記分岐選択工程では、前記選択された分岐枝に入力された前記評価データのセットに対して、分類された変動カテゴリが一致するか否かを判定し、当該変動カテゴリの一致しないデータの割合を誤り率として算出することを特徴とする請求項８に記載のパターン識別器生成方法。
【請求項１０】
前記評価工程では、前記分岐選択工程により算出された前記誤り率に基づいて、選択された分岐枝における弱判別器列が接続すべき段数に到達したか否かを評価することを特徴とする請求項９に記載のパターン識別器生成方法。
【請求項１１】
前記決定工程では、前記評価工程の評価に基づき、前記誤り率が予め定められた値以下になる段数を、非分岐で弱判別器を接続すべき段数として決定することを特徴とする請求項１０に記載のパターン識別器生成方法。
【請求項１２】
複数の弱判別器がカスケード接続された弱判別器列が分岐し、分岐後の各々の枝に弱判別器列が接続する構造のパターン識別器を生成するパターン識別器生成方法を実行する情報処理装置であって、
評価データのセットを前記弱判別器列に入力して得られる処理結果に基づいて、分岐後の弱判別器列が接続すべき段数に到達したか否かを評価する評価手段と、
前記評価手段の評価に基づき、前記弱判別器列を非分岐で接続すべき弱判別器の段数を決定する決定手段と
を備えることを特徴とする情報処理装置。
【請求項１３】
前記評価データのセットには、検出対象となる画像の変動カテゴリに分類されたデータが含まれ、
前記カスケード接続の分岐後の各枝は、前記分類された前記変動カテゴリに対応することを特徴とする請求項１２に記載の情報処理装置。
【請求項１４】
前記弱判別器の各々は、
入力された前記評価データのセットに対する判別結果としてスコア値を算出し、前段の弱判別器で出力された出力値に当該スコア値を加算した累積スコア値を後段の弱判別器に出力することを特徴とする請求項１２に記載の情報処理装置。
【請求項１５】
前記評価データのセットには、非検出対象パターンの集合で構成されるデータが含まれ、
前記弱判別器の各々は、前記累積スコア値が予め定められた閾値をこえる場合に処理の打ち切りを決定することを特徴とする請求項１４に記載の情報処理装置。
【請求項１６】
前記評価手段は、前記評価データのセットを前記分岐後の各々の前記弱判別器列に入力し、前記弱判別器列を構成する前記弱判別器の各々が出力する前記累積スコア値に基づいて、前記弱判別器列が接続すべき段数に到達したか否かを評価することを特徴とする請求項１４に記載の情報処理装置。
【請求項１７】
前記決定手段は、前記評価手段の評価に基づき前記分岐後の各々の前記弱判別器列における前記累積スコア値の差分が予め定められた値以上になる段数を、非分岐で前記弱判別器を接続すべき段数として決定することを特徴とする請求項１６に記載の情報処理装置。
【請求項１８】
前記決定手段は、前記評価手段の評価に基づき前記分岐後の前記弱判別器列の数が３以上となる場合には、全ての前記弱判別器列のうち２つの前記弱判別器列の組合せで算出した前記累積スコア値の差分を求め、全ての前記弱判別器列の組合せについて前記差分を統合した値が予め定められた値以上になる段数を、非分岐で前記弱判別器を接続すべき段数として決定することを特徴とする請求項１６に記載の情報処理装置。
【請求項１９】
前記累積スコア値に基づき、前記評価データのセットに対して処理を継続すべき分岐枝を選択する分岐選択手段を更に備えることを特徴とする請求項１４に記載の情報処理装置。
【請求項２０】
前記分岐選択手段は、前記選択された分岐枝に入力された前記評価データのセットに対して、分類された変動カテゴリが一致するか否かを判定し、当該変動カテゴリの一致しないデータの割合を誤り率として算出することを特徴とする請求項１９に記載の情報処理装置。
【請求項２１】
前記評価手段は、前記分岐選択手段により算出された前記誤り率に基づいて、選択された分岐枝における弱判別器列が接続すべき段数に到達したか否かを評価することを特徴とする請求項２０に記載の情報処理装置。
【請求項２２】
前記決定手段は、前記評価手段の評価に基づき、前記誤り率が予め定められた値以下になる段数を、非分岐で弱判別器を接続すべき段数として決定することを特徴とする請求項２１に記載の情報処理装置。
【請求項２３】
コンピュータを、請求項１２乃至２１のいずれか１項に記載の情報処理装置の各手段として機能させるためのプログラム。
【請求項２４】
請求項２３に記載のプログラムを格納したコンピュータ可読の記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データや音声データ等に含まれる特定のデータパターンを識別、抽出する技術に関する。
【背景技術】
【０００２】
近年、パターン認識の分野において、弱判別器をカスケード接続することにより識別器を構成し、画像中の人の顔などの特定物体を検出する処理を高速に実行する手法が注目を集めている。
【０００３】
例えば、非特許文献１においてViolaとJonesが開示する方法では、まず矩形特徴を抽出する弱判別器を所定数カスケード接続し、ステージと呼ばれる強判別器を構成する。この弱判別器はブースティング学習アルゴリズム（特許文献１等に開示）により生成される。さらに、このステージを複数カスケード接続した構成のパターン識別器が提案されている。強判別器単位で打ち切り判定（画像中のある検出対象位置に対する処理の終了）を行いながら処理を進めることにより、早期に検出対象でないと判断された入力に対する以後の演算が行われなくなるので、全体として高速な処理が可能となる。以下にこのパターン識別法についての詳細を説明する。
【０００４】
非特許文献１のパターン識別器は、図８に示すように、ある特定の大きさの矩形領域（処理ウインドウ８０１）を処理対象となる画像８００内で移動させ、各移動先の処理ウインドウ８０１内に人物の顔が含まれるか否かを判定する。
【０００５】
図９は、各移動先位置における処理ウインドウ８０１において、非特許文献１で行われている顔検出処理の流れを示す図である。ある処理ウインドウ内における顔検出処理は、複数のステージによって実行される。各ステージには、異なる組合せの弱判別器が割り当てられており、これらがカスケード接続で処理されることによって、強判別器となっている。各弱判別器はいわゆるHaar-like特徴を検出するもので、矩形フィルタの組合せで構成されている。図９に示すように、各ステージに割り当てられる弱判別器の数も異なっている。また、ステージ単位でもカスケード接続構成となっており、各ステージは接続された順番に従って判定処理を行う。即ち、例えば図９において、第１ステージの次に第２ステージが判定を実施し、その次に第３ステージが判定を実施する。
【０００６】
各ステージでは、割り当てられたパターンの弱判別器を順に用いて、処理ウインドウ内に人物の顔が含まれるか否かを判定する。あるステージにおいて、処理ウインドウ内に人物の顔が含まれないと判定された場合、それ以降のステージでは、この位置における処理ウインドウについての判定処理は実施されない。すなわち、カスケード処理は打ち切られる。そして、最後の順番のステージで人物の顔が含まれると判定された場合に、この位置における処理ウインドウ内に人物の顔が含まれるとの判定が確定する。
【０００７】
次に、図１０のフローチャートを用いて、顔検出処理の流れを詳細に説明する。
【０００８】
顔検出処理では、まず処理の対象となる処理ウインドウ８０１が顔検出対象となる画像８００上に配置される（Ｓ１００１）。基本的には、この処理ウインドウは、図８に示されるように顔検出対象の画像８００の端から一定間隔で縦方向及び横方向へスキャンすることによって順に網羅的に移動して選択される。例えば、顔検出対象の画像８００をラスタスキャンすることによって処理ウインドウが選択される。
【０００９】
次に、選択された処理ウインドウについて、処理ウインドウに人物の顔が含まれるか否かの判定が実施される。この判定は、上で図９を用いて説明したように、複数のステージを用いて実施される。このため、まず判定を実施するステージが第一のものから順に選択される（Ｓ１００２）。
【００１０】
次に、選択されたステージによって判定処理が実施される（Ｓ１００３）。このステージの判定において、累積得点（累積スコア）（説明は後述）がステージごとに予め決められている閾値を超えなかった場合（Ｓ１００４−ＮＯ）、処理ウインドウに人物の顔が含まれないと判定され（Ｓ１００８）、Ｓ１００７以降の処理が実行される。Ｓ１００７以降の処理については後述する。
【００１１】
一方、累積スコアがステージごとにあらかじめ決められている閾値を超えた場合（Ｓ１００４−ＹＥＳ）、その判定処理（Ｓ１００３の判定処理）が最終ステージによる処理であったか否かが判断される。最終ステージでなかった場合（Ｓ１００５−ＮＯ）、Ｓ１００２の処理に戻り次のステージが選択され、新たに選択されたステージによって判定処理が実施される。一方、最終ステージであった場合（Ｓ１００５−ＹＥＳ）、現在の処理ウインドウに人物の顔が含まれるという最終的な判定がなされる（Ｓ１００６）。この時点で、この処理ウインドウに人物の顔が含まれると判断したことになる。
【００１２】
次に、判定の対象となっていた処理ウインドウが、顔検出対象画像の中で最後の処理ウインドウであったか否かを判断する。最後の処理ウインドウではなかった場合（Ｓ１００７−ＮＯ）、Ｓ１００１の処理に戻り、次の処理ウインドウが選択され、Ｓ１００２以降の処理が実行される。一方、最後の処理ウインドウであった場合、この顔検出対象の入力画像に対する顔検出処理は終了する。
【００１３】
次に、各ステージにおける判定の処理内容について説明する。
【００１４】
各ステージには、１以上のパターンの弱判別器が割り当てられている。この割り当ては学習処理において、ＡｄａＢｏｏｓｔ等のアンサンブル学習アルゴリズムによって実施される。各ステージは、自身に割り当てられたパターンの弱判別器に基づいて、処理ウインドウ内に顔が含まれるか否かの判定を行う。
【００１５】
各ステージでは、各ステージに割り当てられた各パターンの弱判別器に基づいて、処理ウインドウ内の複数の矩形領域における特徴量がそれぞれ算出される。このとき用いられる特徴量は、各矩形領域内の画素値の合計値やその平均値等、即ち矩形領域内の画素値の総和値（矩形領域内総和値）を用いて算出される値である。この矩形領域内総和値は、入力画像に対する累積画像情報（Summed Area Table（SAT）或いはIntegral Imageと呼ばれる）を用いることにより高速に計算可能である。
【００１６】
図１１はＳＡＴの一例を説明する図である。図１１(ａ)は元の入力画像１１０１を示し、左上を原点（０，０）としている。入力画像１１０１の座標位置（ｘ、ｙ）の画素値をＩ（ｘ、ｙ）としたとき、ＳＡＴの同位置（ｘ、ｙ）の成分Ｃ（ｘ、ｙ）を（１）式として定義する。
【００１７】
【数１】
0004948379.tif 000002
【００１８】
図１１(ｂ)に示すように、入力画像１１０１の原点位置（０，０）と位置（ｘ、ｙ）の画素を対角とする長方形内の画素の総和値が位置（ｘ、ｙ）の値Ｃ（ｘ、ｙ）となる。入力画像１１０１の任意の矩形領域内の画素値Ｉ(x, y)の和は、（２）式を用いることにより、例えば、図１２に示すような４点を参照することで求めることができる。
【００１９】
【数２】
0004948379.tif 000003
【００２０】
次に、算出された特徴量の相対値（例えば比や差分値。ここでは特徴量の差分値が算出されると想定する）としての差分値が算出され、この差分値に基づいて処理ウインドウに人物の顔が含まれるか否かの判定が実施される。具体的には、算出された差分値が、判定に用いられているパターンの弱判別器に設定された閾値よりも大きいか否か又は小さいか否かが判定される。そして、この判定の結果に応じて、処理ウインドウにおける人物の顔の存否が判定される。
【００２１】
ただし、この時点での判定は、各パターンの弱判別器それぞれに基づいた判定であり、ステージによる判定ではない。このように、各ステージでは、割り当てられた全てのパターンの弱判別器それぞれに基づいて個別に判定が実施され、それぞれの判定結果が得られる。
【００２２】
次に、ステージにおける累積スコアを算出する。各パターンの弱判別器にはそれぞれ個別の信頼度重み（スコア）が割り当てられている。この信頼度重みとは、その弱判別器単独での「判断の確からしさ」、すなわち、単独の信頼度を示す固定値である。処理ウインドウに人物の顔が含まれると判定されると、そのとき使用されたパターンの弱判別器に対応するスコアが参照され、ステージの累積スコアに加算される。このようにして、加算された個別のスコアの総計が、ステージにおける累積スコアとして算出される。つまり、この累積スコアとは、そのステージ全体での判断の確からしさ（ステージ全体信頼度）を示す値となる。そして、ステージ全体信頼度が予め定められた閾値（ステージ全体信頼度閾値）を超えた場合に、このステージでは処理ウインドウに人物の顔が含まれる可能性有りと判定し、処理を継続して次のステージに移る。一方、このステージにおけるステージ全体信頼度が閾値を超えない場合、処理ウインドウに人物の顔が含まれないと判定し、以後のカスケード処理を打ち切る。
【００２３】
非特許文献１では、このような手順により、顔検出に代表される高速なパターン識別を実現している。尚、図９、１０の検出器は、予め適正な学習を行っておけば、顔以外のパターン識別器として用いることも可能である。
【００２４】
また、特許文献２および３も、非特許文献１の考え方に基づくパターン識別方法や装置に関する発明を開示している。このような弱判別器を一列にカスケード接続した構造を持つパターン識別器は、特に画像中から、良く似たパターン（検出対象パターン）とそれ以外のパターン（非検出対象パターン）を分離する場合には、高速かつ十分な識別性能を発揮する。
【００２５】
しかしながら、検出対象パターンが、例えば、顔画像であるような場合、正面方向を向いたままであっても、左または右に数十度ほど傾ければ（面内回転と呼ぶ）、元の正立した正面顔に対して「良く似た」パターンとは言えなくなる。さらに横顔に近いような軸方向の回転（奥行き回転または横方向奥行き回転と呼ぶ）が加わると、全く異なった二次元画像パターンとなる。このような変動の大きいパターンを、一列のカスケード接続で識別するのにはそもそも無理があり、処理時間の増大や検出精度劣化の要因となっている。弱判別器のカスケード接続構造は、識別すべき検出対象パターンとは似ていない非検出対象パターンを少しずつ除外してゆくためのものであるから、識別すべきパターン同士は互いに良く似ていることが前提となっているのである。
【００２６】
面内回転のみであれば、正立に近い正面顔を検出する識別器に、入力画像を順次少しずつ回転させてから入力すれば、３６０度どの角度の顔であっても識別することは可能ではある。しかし、この方法では、回転回数に応じて処理時間が増大してしまうし、そもそも奥行き回転が加わる場合には対応することができない。
【００２７】
そこで、非特許文献２においては、Coarse to Fine戦略に基づく階層状のピラミッド構造の識別器を提案している。この識別器においては、まず第１階層では、検出したい全ての顔向き変動を含む学習画像パターンを入力して、一つのステージを学習する。第２階層では、顔向き変動を所定の範囲毎に分割し、それぞれ分割された範囲の変動のみを含む学習画像パターンにより、複数のステージを学習する。次の階層ではさらに狭い範囲の変動毎に分割して、さらに数を増やした複数のステージを学習する。このように、階層を進めるにつれて、徐々にロバスト性を下げた強判別器（ステージ）を、徐々に数を増やしながら、ピラミッドのように構成してゆく。尚、本文献における識別器では、横方向奥行き回転の顔向き変動のみを分割して対応している。±90度の全奥行き回転範囲を、第２階層で３分割、第３階層で９分割しており、面内回転に関しては分割していない。
【００２８】
本識別器の検出処理時は、入力されたサブウィンドウが第1階層のステージをパスしたならば、第２階層の各ステージを順に実行し、どれか一つでもパスしたら次の階層のステージに進む。このように、粗い検出から始めて徐々に精度の高い検出を行っていくことにより、全ての変動の顔パターンを精度よく検出可能な識別器を構成している。
【００２９】
特許文献４でも同様の考え方に基づき、ロバスト性の大きい検出器から徐々に枝分かれしてロバスト性の低い検出器となる、ツリー構造を持った識別器を構成する方法を開示している。この識別器は、ツリーの各枝のノード（ステージ）は、親ノードの受け持つ変動範囲を分割した一部変動範囲を受け持つように学習させている。特許文献４で開示されている実施形態が対応する顔の変動は、横方向奥行き回転だけでなく、顔が正面から上下を向いた方向となる縦方向奥行き回転も含んでいる。また、各ノードの弱判別器段数は、人が経験的に定めて学習させている。
【００３０】
検出処理時には、全ての縦横奥行き回転変動を含む第１ノードの検出処理を行った後、まずは正面顔と左右それぞれの方向の奥行き回転顔の３つの変動に分岐する。そして次の階層で縦方向奥行き回転別にさらに３つに分岐する。正面顔の縦方向回転中央の変動の分岐のみは、さらに次の階層で３分岐する構成となっている。このような分岐構造を予め決めた上で、それぞれの変動に対応するサンプルデータを多数入力して、各分岐を学習させるようにしている。非特許文献２とは異なり、上位層ノードで打ち切られた変動に含まれる下位層ノードの演算を行う必要がなくなるため、高速性が実現できるとしている。尚、特許文献４における弱判別器は、矩形差分ではなくピクセル差分を用いているが、弱判別器のカスケード接続により強判別器を構成するという考え方は同様である。
【００３１】
非特許文献３では、特許文献４と同様のツリー構造の識別器の別の学習方法を提案している。本文献に記載されている識別器が対応する変動は、面内回転と横方向奥行き変動である。全変動を含む第１階層のノードから、横方向奥行き回転を２段階で５分岐させ、然る後に第４階層において回転変動を３分岐させる構造を定めている。この構造に従って、学習を進めるのは、上述の文献と同様である。また、各ノードの弱判別器段数を予め人が経験的に定めて学習させる点も同様である。
【００３２】
但し、最終分岐に到達する前に学習される各ノードの判別器の出力は、上述の文献と異なりスカラー値ではなく、そのノードの次の層の分岐数と一致した要素数のベクトル値である。すなわち分岐前の各ノード検出器は、非顔画像の打ち切りだけでなく、次の層の分岐選択も行う機能を持つ。検出時において、各ノードの出力ベクトルの値が１に近い要素に対応する分岐のみが起動されることにより、不要な演算を行う必要がなくなり、高速性が確保されるとしている。
【非特許文献１】P. Viola, M. Jones, “Rapid Object Detection using a Boosted Cascade of Simple Features”, Proc. IEEE Conf. on Computer Vision and Pattern Recognition, Vol. 1, pp.511-518, December 2001.
【非特許文献２】Z. Zhang, L. Zhu, S. Z. Li, H. Zhang, “Real-Time Multi-View Face Detection”, Proceedings of the Fifth IEEE International Conference on Automatic Face and Gesture Recognition (FGR’02)
【非特許文献３】C. Huang, H. Ai, Y. Li, S. Lao, “Vector Boosting for Rotation Invariant Multi-View Face Detection”, Tenth IEEE International Conference on Computer Vision (ICCV2005), Volume 1, 17-21 Oct. 2005, pp.446-453
【特許文献１】特開平８-３２９０３１号公報
【特許文献２】特開２００４-１８５６１１号公報
【特許文献３】特開２００５-０４４３３０号公報
【特許文献４】特開２００５-２８４４８７号公報
【発明の開示】
【発明が解決しようとする課題】
【００３３】
非特許文献２、３や特許文献４のような従来技術では、学習に先んじて、Coarse to Fine戦略或いはツリー構造による変動範囲の分割方法（すなわち分岐構造）を決める。そして、分割された各ノード（ステージ）それぞれの弱判別器段数は、機械学習処理を実施する人が経験的（或いは直感的）に定めた所定段数としている。例えば特許文献４では、各分岐の枝ノードの弱判別器の数を１００個などするものと定めており、非特許文献２においてはT回の繰り返し処理により一つずつ（すなわちＴ段の）ベクトル出力を行う弱判別器を生成している。
【００３４】
これらのように、人が経験などから定めた弱判別器段数は、必ずしも最適なものであるとは言えない。分岐構造（あるいはピラミッド型）のパターン識別器においては、後段のノードになるほど、識別対象とするパターンのロバスト性は小さくなる。従って、他の背景等のパターンから対象パターンを分離するために必要な処理段数（すなわち速度）や精度は、後段になるほど向上する。従来技術で経験的に定めている処理段数は、後段のノードの処理に突入するか否かを決定するには十分な段数であると考えられるが、必要最小限な処理段数ではない。後段ほどロバスト性が低くなることから、本来は、できるだけ早く最終分岐後のノードに到達した方が、処理速度の向上を期待できる。しかしながら、上述の従来技術においては、各分岐ノードにおいて最小限必要な処理段数を判別する手段がなかった。
【００３５】
本発明はこのような問題点を解決するためになされたものであり、分岐構造のパターン識別器を学習する上で、各分岐で最小限必要な処理段数を判別可能にする技術の提供を目的とする。
【課題を解決するための手段】
【００３６】
上記課題を解決するために、本発明にかかるパターン識別器生成方法は、複数の弱判別器がカスケード接続された弱判別器列が分岐し、分岐後の各々の枝に弱判別器列が接続する構造のパターン識別器を生成するパターン識別器生成方法であって、
評価手段が、評価データのセットを前記弱判別器列に入力して得られる処理結果に基づいて、分岐後の弱判別器列が接続すべき段数に到達したか否かを評価する評価工程と、
決定手段が、前記評価工程の評価に基づき、前記弱判別器列を非分岐で接続すべき弱判別器の段数を決定する決定工程と
を有することを特徴とする。
【００３７】
あるいは、本発明にかかる情報処理装置は、複数の弱判別器がカスケード接続された弱判別器列が分岐し、分岐後の各々の枝に弱判別器列が接続する構造のパターン識別器を生成するパターン識別器生成方法を実行する情報処理装置であって、
評価データのセットを前記弱判別器列に入力して得られる処理結果に基づいて、分岐後の弱判別器列が接続すべき段数に到達したか否かを評価する評価手段と、
前記評価手段の評価に基づき、前記弱判別器列を非分岐で接続すべき弱判別器の段数を決定する決定手段と
を備えることを特徴とする。
【発明の効果】
【００３８】
本発明によれば、各分岐で最小限必要な処理段数を判別して、分岐構造のパターン識別器を学習することが可能となる。
【発明を実施するための最良の形態】
【００３９】
以下、図面を参照して、本発明の好適な実施形態を例示的に詳しく説明する。ただし、この実施の形態に記載されている構成要素はあくまで例示であり、本発明の技術的範囲は、特許請求の範囲によって確定されるのであって、以下の個別の実施形態によって限定されるわけではない。
【００４０】
（第１実施形態）
（ブロック図の説明）
図２は本発明の一実施形態にかかる情報処理装置の構成を示すブロック図である。画像入力部２０１は、パターン識別処理対象となる入力画像データや、学習用サンプル画像データを装置内に取り込む機能を持つ。画像入力部２０１には、例えば、光学系、ＣＣＤセンサー等の光電変換デバイス、ドライバー回路、ＡＤコンバーター、各種画像補正を司る信号処理回路、フレームバッファ等により構成される撮像装置が含まれる。或いは、画像入力部２０１には、後述の通信Ｉ/Ｆ２０６とハードウェアを共用し、Ｉ/Ｆに接続されるネットワーク等の所定の通信経路を介して外部装置から画像データを受信するＩ/Ｆ装置が含まれる。
【００４１】
前処理部２０２は、検出処理を効果的に行うための各種前処理を実行する。具体的には色変換処理、コントラスト補正処理、ＳＡＴ（Sammed Area Table）データの生成等、各種画像データ変換をハードウェアで処理する。判別処理部２０３は前処理部２０２の出力を参照して所定のオブジェクト・パターンの有無を識別する機能を有する。判別処理部２０３は学習によって生成したパラメータに基づいてブースティング判別処理を実行する。尚、前処理部２０２および判別処理部２０３の機能（または一部機能）は、後述するＣＰＵ２０８で実行されるソフトウェア・プログラムによる処理として実装することも可能である。
【００４２】
ＤＭＡＣ(Direct Memory Access Controller)２０４は、ＣＰＵバス２０５上の各処理部やＲＡＭ２１０とＲＯＭ２０９と間のデータ転送等を司る。
【００４３】
通信インターフェース２０６は、外部装置から本装置に所定の動作を指令したり、学習のために必要なデータ群を外部の装置から後述の大容量記憶部２１１に転送することができる。
【００４４】
ユーザ・インターフェース（User I/F）２０７は、例えば、操作者が装置の動作を指定する為の押しボタン・スイッチやキーボード、操作者に情報を提示するためのディスプレイ・パネル等、入出力デバイスで構成される。
【００４５】
ＣＰＵ（Central Processing Unit）２０８は、本発明に係る処理を実行すると共に、ＣＰＵバス２０５を介して接続される本装置全体の各部の動作を制御する。ＲＯＭ２０９は、ＣＰＵ２０８の動作を規定する命令を格納する。ＲＡＭ２１０はＣＰＵ２０８の動作に必要な作業メモリとして使用される。 ＲＡＭ２１０は、ＤＲＡＭ(Dynamic RAM)等の比較的容量の大きいメモリで構成される。大容量記憶部２１１は、ハードディスクやフラッシュメモリ等の大容量データ記憶装置である。例えば、学習のために必要なサンプル画像等の大量データセットは、大容量記憶部２１１に格納される。
【００４６】
情報処理装置は図２に示すように、ＣＰＵバス２０５に全ての構成要素が接続される構成を取る。この構成の他、例えば、画像入力部２０１、前処理部２０２、判別処理部２０３、ＤＭＡＣ２０４を別のバス（画像バス）に接続し、画像バスとＣＰＵバスの間をブリッジで接続する構成とすることも可能である。このようにバスを分離することで、ハードウェアによる処理部（画像入力部２０１、前処理部２０２、判別処理部２０３）とＣＰＵ２０８は並列動作が可能となる。
【００４７】
（変動カテゴリ）
本実施形態の情報処理装置では、図５に示す３つの変動カテゴリで分類される顔画像を検出対象パターンとする、分岐構造のパターン識別を学習する。
【００４８】
変動カテゴリ（i）は面内回転変動である。正立状態（図中中央）から時計周り(＋とする)／反時計回りにそれぞれ45度回転した顔画像までを検出対象の変動範囲とする。本実施形態では、この±45°の範囲を３分割するものとし、-45°〜-15°の範囲をａ、正立を含む-15°〜+15°の範囲をｂ、+15°〜+45°の範囲をｃとラベル付けしている。
【００４９】
変動カテゴリ（ii）は左右方向の奥行き回転変動である。本実施形態では、正面顔から左右向きの横顔までを対象の変動範囲として、この範囲を３分割している。右向きの横顔からほぼ両目の写る直前までの顔（-90°〜-30°）をＡ、正面顔含む両目の写る顔（-30°〜+30°）をＢ、左向きの横顔からほぼ両目の写る直前までの顔（+30°〜+90°）をＣとラベル付けする。
【００５０】
変動カテゴリ（iii）はサイズ変動である。本実施形態では、面内回転0°のときの両目と口の高さの差の画素数で顔サイズを規定する。最小顔サイズは１６、最大顔サイズは２２で、この範囲を２分割して小を１、大を２とラベル付けする。尚、この範囲外の顔は、入力画像を拡大・縮小したチャネル処理によって検出される。
【００５１】
本実施形態では、これら３つのカテゴリによる変動が入り混じった顔画像を検出対象としている。これに上下方向の奥行き回転変動を加えても良いし、それぞれの変動の分割数をさらに増やして、検出精度の向上を図ることも可能であるが、説明を簡明にするため割愛する。
【００５２】
また、各変動カテゴリに隣接する分類とのオーバーラップ領域を設けて、どちらの分類にも所属するパターンが存在するようにしてもよい。例えば、変動カテゴリ(i)について、-45°〜-12.5°の範囲をａ、正立を含む-17.5°〜+17.5°の範囲をｂ、+12.5°〜+45°の範囲をｃとすることもできる。この場合、オーバーラップ領域に属する例えば+15.0°の回転データは、ｂだけでなくｃとしても分類される。
【００５３】
後述の識別器において、分岐先の一つは上記変動カテゴリのいずれかに対応し、分岐の各枝の弱判別器列は、対応する変動カテゴリの変動範囲を分割した１つの分類を検出すべき担当範囲とする。すなわち、各分岐における枝の数は対応する変動カテゴリの変動範囲の分割数と一致する。
【００５４】
学習する際に分類にオーバーラップ領域を設けるとは、すなわち、分岐の２本の枝どちらでも検出可能な変動範囲を設けるということである。このようにすると、隣接分類の境目に相当するパターンが取りこぼされにくくなり、より検出精度を高める効果が期待できる。
【００５５】
（分岐構造）
本実施形態のパターン識別器は、分岐構造を持っており、各分岐の枝にそれぞれ、弱判別器ノードを複数個カスケード接続した弱判別器列が配置されている。これら弱判別器列の処理は、判別処理部２０３を用いて実行される。
【００５６】
図３(ａ)は、分岐構造を持ったパターン識別器の一例である。３０１、３０２等の図中の円で示されるノード（弱判別器ノード）は、各々一つの弱判別器を含んでいる。本実施形態の識別器では、非特許文献１のような各ノードが多数の弱判別器を持つステージ構成ではなく、各ノードは一つのみの弱判別器を含む。すなわち弱判別器一つずつで打ち切り判定が行われるようになっているが、各ノードはステージ構成を取っても、本発明の本質には影響しない。
【００５７】
図３(ａ)は、分岐型パターン識別器の一例を示す図である。１段目の弱判別器３０１から開始して、所定段非分岐で弱判別器がカスケード接続されている。そして、弱判別器３０２で２分岐し、弱判別器３０３および３０４から始まる弱判別器のカスケード接続列に分かれる。さらに各分岐の枝で所定段弱判別器が連続した後、弱判別器３０５で各枝がそれぞれ３分岐し、計６本となった分岐の枝それぞれが所定段弱判別器を連続させた後、最終段の弱判別器３０６に到達する。弱判別器３０１から３０６までの各弱判別器では、それぞれ打ち切り判定処理が入っており、打ち切られた場合は以降の弱判別器の処理は行われない。最終段の弱判別器３０６まで到達した出力は、最終判定部３０７に入力されて統合処理され、ここで受け入れ判定されて、受け入れられれば対象オブジェクト・パターンであると判断されたことになる。
【００５８】
図３(ｂ)は、本実施形態における分岐型パターン識別器の構造を示す図である。本実施形態では、図５で説明した３つの変動カテゴリに基づく分岐構造をとる。分岐の順序は、予備学習等によって予め決定されており、本実施形態の場合には、カテゴリ(i)の面内回転、カテゴリ(iii)のサイズ変動、カテゴリ(ii)の奥行き回転の順に分岐する。すなわち、図３(ｂ)に示すように、第一分岐は３分岐（ａ,ｂ,ｃ）、第二分岐は２分岐（１，２）、第三分岐は３分岐（Ａ,Ｂ,Ｃ）という分岐構造になる。分岐間の弱判別器列の長さの決定の詳細は後述する。
【００５９】
このようなツリー構造識別器において、分岐処理の実行方法はいくつかのバリエーションが考えられる。
【００６０】
第一には全起動であって、全ての分岐を実行する方法である。この場合、途中で打ち切られずに最終段の弱判別器３０６までたどり着いた分岐の出力は、すべて最終判定部３０７に入力される。最終判定部３０７は各分岐の出力座標や判別の信頼度に応じて、所定の統合処理を行った後に閾値処理して、受け入れるかどうか判定する。この方法のメリットは、精度が良いことであり、また、検出と同時に変動カテゴリによる分類を比較的正確に行えることである。デメリットとしては処理時間がかかることである。
【００６１】
第二の方法は全探索起動である。この場合は、例えば、上の分岐（図３(ａ)の弱判別器３０３と弱判別器３０４では弱判別器３０３側）から順に、打ち切られるまで検出処理を実行する。検出処理が打ち切られた場合には、直前の分岐（例えば弱判別器３０２）まで戻って、直下のノード（兄弟ノード、３０４）を実行する。最終段にたどり着いた分岐があれば、そこで最終判定を行い受け入れられれば処理完了とする。受け入れられない場合は直前の分岐に戻って継続する。この方法のメリットは、実装容易でかつある程度速度向上することである。デメリットとしては、分岐の実行順序に依存するため正確な分類は行えないことである。
【００６２】
第三の方法としては、分岐選択起動である。途中のノードの処理結果に基づき、どの分岐を起動するか選択する。メリットは高速性であり、第二の方法よりもさらに高速になることが期待できる。また、選択方法にも依存するが、分類を比較的正確にすることもできる。デメリットは処理が若干複雑になることで、例えば非特許文献３のような分岐選択可能なノードを生成するようにしたり、他の分岐選択方法を実装する必要がある。
【００６３】
本実施形態では、最も高速な処理速度が期待できる第三の方法を採用している。分岐選択の方法は、非特許文献３の分岐前に選択する方式とは異なり、一旦、分岐した後の枝を全て起動し、各枝の処理結果に基づいて残す枝を選択するという方式（分岐後選択方式）を取っている。本実施形態での分岐選択方法の詳細については、後述する。
【００６４】
（基本検出処理）
ここで、本実施形態のパターン識別器における基本的な検出処理について、図４および図７を用いて説明する。図４は弱判別器ノードの内部構造を表すブロック図であり、図７は各弱判別器ノードで行われるノード内判別処理の流れを説明するフローチャートである。
【００６５】
図４において、ノード４０１、４０２はそれぞれ１つの弱判別器と、その周辺回路（これらを合わせてノード或いは弱判別器ノードと呼んでいる）を示している。図４では２つのノード間の論理的な接続状態を例示しているが、パターン識別器全体としては、図３に示したように、さらに多くのノードがカスケードに、あるいは途中分岐して接続されている。これらのノードは、物理的には１つの処理回路で構成され、時分割にパラメータを切り替えて使用することにより、論理的に多数のノードを実現している。高速化を目的として、複数個のノードを物理的に独立な回路として実装し、並列に処理を割り振るようにしても良い。
【００６６】
パラメータレジスタ４１１、４１２はそれぞれ一つ弱判別器を構成するためのパラメータ情報を格納するレジスタである。これらレジスタに格納されるパラメータ情報は、判別処理部２０３内のパラメータメモリ４５１上に、全ての弱判別器ノード分がまとめて保持されている。パラメータメモリ４５１は判別処理部２０３外のＣＰＵ２０８やＤＭＡＣ２０４からアクセス可能で、検出処理実行前にパラメータ情報が設定されるようになっている。
【００６７】
本実施形態の弱判別器は、非特許文献１と同様の矩形特徴を用いるものであるので、検出時に、矩形数・矩形座標・フィルタ係数・フィルタ閾値・信頼度重み（＝スコア）・識別閾値がパラメータとして必要である。図１７は、パラメータメモリ４５１上に格納された各弱判別器ノードのパラメータを例示しており、これらに加えて自身のＩＤと、前段の弱判別器ノードのＩＤである前段ＩＤおよび後段にある複数の弱判別器ノードのＩＤである複数の後段ＩＤを、弱判別器ノード毎に保持できるようになっている。
【００６８】
ここで自身のＩＤおよび前段ＩＤ、後段ＩＤは、一種の双方向リストとなっており、これによってノードの接続構造（＝分岐構造）を表すことができるようになっている。図１７で先頭のブロック（弱判別器ノード１）は、図３(ｂ)の識別器における最初のノードを示しているので、前段ＩＤは無し、後段ＩＤは一つのみ格納されている状態となる。尚、本実施形態では、後段ＩＤ領域は固定サイズであって、すなわち上限数がある。つまり、一つのノードに対するパラメータブロックのサイズは固定である。分岐直前ノードにおいては、後段ＩＤは分岐数に一致する数だけ格納される。実行時には、この双方向リスト部分を辿ることにより、弱判別器の実行順序を特定することが可能である。ノードのＩＤは一定のルール（後述）に従って付けられており、開始ノードが最も若いＩＤとなる。パラメータメモリには、若いＩＤのパラメータブロックから順に格納されるので、先頭ブロックは常に開始ノードであり、また、所望のＩＤに対応するパラメータを読み出す処理は、アドレス・デコーダにより容易に実現できる。
【００６９】
上記のパラメータの中で、「矩形数」とは検出ウインドウ内における矩形の数を指定する情報であり、例えば、図９に示した第１および第２ステージの弱判別器のようなフィルタの場合、矩形数が２となる。また図９の第ｎステージ第ｍ弱判別器の場合は、矩形数３となる。同図では、白矩形、黒矩形が一つずつの矩形である。弱判別器４２１は、それぞれの矩形内総和値（またはその平均値）に矩形毎に設定される「フィルタ係数」を乗じた値の合計を「フィルタ閾値」を用いて閾値処理する。閾値条件（(３)式）を満たすとき、弱判別器４２１は"１"を出力し、満たさない場合"-１"を出力する。
【００７０】
【数３】
0004948379.tif 000004
【００７１】
矩形領域の形状・位置や数、またフィルタ係数ＣI及びフィルタ閾値ＷTh_tは、学習時に決定するパラメータである。本実施形態の弱判別器では、ＣIは必ず１または-1のどちらかの値となっている。つまり、式(３)の左辺は複数の矩形領域内の画素総和値Ｓiの差分値を求める処理に相当する。この差分値が所定のフィルタ閾値ＷTh_tより大であるとは、この弱判別器に限れば入力データは識別対象パターンであると判断されたことに相当する。
【００７２】
矩形領域内総和値Ｓiは先に説明した通り、ＳＡＴデータを参照することで極めて高速に算出することが可能である。ＳＡＴメモリ４５０は、前処理部２０２により検出処理の開始前に算出した１枚の入力画像データに対するＳＡＴデータを格納している。ＳＡＴメモリ４５０は、ＲＡＭ２１０内に設けても良いが、高速化のためには判別処理部２０３に内蔵RAMとして持つ構成が望ましい。弱判別器４２１は、ＳＡＴメモリ４５０から検出ウインドウ位置の値を参照してＳiを計算し、式（３）の判定を行っている。
【００７３】
「矩形座標」は矩形領域それぞれの位置を表す座標情報である。「フィルタ係数」は、正または負の係数である。「信頼度重み（スコア）」とは、対象とするノードの弱判別器単独での信頼度を表す値である。ブースティング判別は、第ｔノード以前に処理された各ノード個別のスコアの、符号付き総和値（累積スコアと呼ぶ）をもって判別を行う。すなわち、ここで言う累積スコアは、第1ノードから第ｔノードまでをカスケード接続した識別器全体の判別の確からしさ、すなわち全体の信頼度を示す値となる。「識別閾値」は、この累積スコア値をもってブースティング判別器で判定を行うための閾値である。
【００７４】
カスケード接続のｋ段目のノードの弱判別器（４２１相当）の判定結果をｈk(x)(x：入力データ)、信頼度をαk、t段目のノードの識別閾値をＴgh_tとした場合、t段目の打切り判定部（４６１相当）の打切り判定は式（４）のようになる。ここでｈk(x)の値は、各弱判別器単独で検出対象オブジェクトと判断した場合（＝式（３）のフィルタ閾値条件を満たすとき）１、非検出対象オブジェクトと判断した場合（＝フィルタ閾値条件を満たさないとき）-1である。
【００７５】
【数４】
0004948379.tif 000005
【００７６】
(４)式を満足しなければ処理を打ち切り、満足するならば処理を継続し、次ノードへ累積スコア（全体信頼度）を出力する。最終ノードでこの判別条件を満たせば、検出対象パターンであると判断する。尚、信頼度αｔと識別閾値Ｔgh_tは、ｔ段目のノード学習時に決定されるパラメータである。
【００７７】
信頼度αkは、ノードに対応するパラメータレジスタ（４１１、４１２相当）から読み出され、乗算器（４３１相当）で弱判別器（４２１相当）の出力ｈk(x)と乗じられる。そして加算器（４４１相当）で前段ノードから出力されてくる累積スコアと加算される。打ち切り判定部（４６１相当）では、弱判別器に対応するパラメータレジスタ（４１１相当）から読み出した識別閾値Ｔgh_tを使用して、ここまでの累積スコアに対する(4)式の判定を行う。
【００７８】
累積スコアが識別閾値（（４）式の右辺）より大きければ、処理継続となり次段のノードへ累積スコアが出力される。尚、当該ノードが分岐ノードであって、次段のノードが複数存在する場合には、すべての次段のノード（＝兄弟ノード）に、同じ累積スコア値を出力する。
【００７９】
以上の各弱判別器ノードにおける処理の流れをフローチャートとして示すと、図７のようになる。同図で、ステップS701は特徴量算出処理であって、式(３)の左辺を計算する処理である。ステップＳ７０２はフィルタ閾値による判定処理であり、式(３)の判別処理であって、処理中のノードがｔ段目としたときの式(４)のｈｔ(x)に対応する値を1または-1に設定する。これが弱判別器４２１の出力である。
【００８０】
ステップＳ７０３は、処理中の弱判別器ノード単独のスコア値算出処理であって、式(4)のαｔｈｔ(x)に対応する値を計算する。信頼度αｔは上述したようにパラメータレジスタ４１１，４１２から読み出される値である。
【００８１】
そしてステップＳ７０４において前段からの出力値にスコア値を加算した累積加算値（累積スコア値）を算出する。累積スコア値の算出には、式(４)の左辺を計算する。前段までの累積スコア値は、前段ノードの処理実行完了時に、前段ノードのＩＤと関連付けられて内部メモリに保持されている。
【００８２】
前段ＩＤは、実行中のノードのパラメータレジスタに格納されているので、前段ＩＤを用いて、前段までの累積スコア値をメモリから取り出すことができる。従って、ここでの処理はステップＳ７０３で計算した値をメモリから取り出した値に加算するだけでよい。
【００８３】
そして、ステップＳ７０５において式（４）に相当する判別処理を行う。これは打ち切り判定部４６１で行われる処理である。ステップＳ７０５で打ち切りと判定された場合には、ステップＳ７０７にて打ち切り設定（フラグを立てる等）し、以後の段の処理が行われないようにする。打ち切らないと判定された場合には、ステップＳ７０６以後の段のノード処理で使用可能なように、累積スコア値をノードＩＤと関連付けて不図示の内部メモリに保持する。尚、ステップＳ７０６において、累積スコア以外の処理結果値、例えば単独のスコア値等も保持するようにすることも可能である。以上が、判別処理部２０３で実行される弱判別器ノードの処理である。
【００８４】
打ち切られなかった全ての弱判別器ノードの実行が完了すると、それらの累積スコア値は、図３の最終判定部３０７に入力される。ここで、打ち切られずに残った累積スコア値に対して統合処理を行った後に、最終識別閾値で閾値処理する。後述する分岐選択において同時に複数の枝の選択を許すならば、最終判定部３０７には同時に複数の累積スコア値の出力が到達する場合が生ずる。このような場合、統合処理として、例えば到達した全ての累積スコア値を加算する処理にしても良いし、最大値や平均値を用いる処理としてもよい。一つの枝の選択しか許さない場合には、最終判定部が行う処理は打ち切り判定部４６１が行うのと同様の単純な閾値処理であるので、最終段の弱判別器３０６の打ち切り判定部に処理を代替させるようにしてもよい。
【００８５】
（ノードＩＤ）
各弱判別器ノードには、図３(ｂ)に示すようなノードＩＤがついている。このノードＩＤは、分岐枝ＩＤ部と固有ＩＤ部に分かれる。固有ＩＤ部は、ノード毎に一意に付けられる番号であって、開始ノードを０番とし、処理段数が進むにつれて一つずつ増加させる。分岐後は、１つの枝について次の分岐に到達するまでを連番とし、到達したら次の枝の先頭ノードにその次の番号を割り当てる、というように与える。つまり固有ＩＤが同じノードは存在せず、固有ＩＤ番号にブロックサイズを乗ずることにより、容易にパラメータメモリ上のノードに対応するパラメータ・ブロックのアドレスを算出することができる。
【００８６】
分岐枝ＩＤ部は、分岐番号と枝番号の２つの番号より構成される。分岐番号は、開始の非分岐状態のところでは０であり、以後分岐する毎に１つずつ増加する。枝番号は、分岐する毎に０からスタートし、各枝に１つずつインクリメントさせた番号を割り当てている。
【００８７】
以上のルールに従うと、例えば、分岐前の処理段数をｎ0とすると、開始ノードのＩＤは00_0であり、第一分岐直前ノードのＩＤは00_＜ｎ0-1＞となる。さらに、第一分岐後第二分岐直前までの処理段数をｎ１とすると、第一分岐の第一の枝の先頭ノードのＩＤは10_＜ｎ0＞となる。また、同枝の弱判別器列の第二分岐直前のノードのＩＤは10_＜ｎ0 +ｎ１-1＞となって、第二の枝の先頭ノードのＩＤは10_＜ｎ0 +ｎ１＞などとなる。
【００８８】
（分岐選択付き検出処理）
次に、サブウィンドウ（図８の画像８００相当）単位の画像が投入されたときに、分岐選択しながら実行する場合の検出処理の流れについて、図１５を用いて説明する。この処理は図２におけるＣＰＵ２０８の指令により、判別処理部２０３を含む各部を用いて行う処理である。
【００８９】
まず、ステップＳ１５０１において、実行予定キューの初期設定を行う。この処理は、実行する予定のノードのＩＤを、実行する順序でキューに挿入する処理である。先に説明したＩＤでは、先頭ノードのＩＤは00_0に決まっているので、まずはこれが挿入される。そしてパラメータメモリの双方向リスト部分のＩＤを辿って、ノードの接続構造に従って処理する順にＩＤを挿入してゆく。ここでは、第一分岐の後、所定段数（ｍ1とする）までを実行するものとして設定する。つまり、まず分岐前のＩＤ: 00_0からＩＤ: 00_＜ｎ0−１＞までを挿入後、第一分岐第一枝のＩＤ: 10_＜ｎ0＞からＩＤ: 10_＜ｎ0+ｍ１-1＞を挿入する。そして、次に第二枝のＩＤ: 11_＜n0ｎ0+n1ｎ１＞からＩＤ: 11_＜ｎ0+ｎ１+ｍ１-1＞、第二枝のＩＤ: 12_＜ｎ0+2ｎ１＞からＩＤ: 12_＜ｎ0+2ｎ１+ｍ１-1＞まで挿入したところで、処理を打ち切る。
【００９０】
ここで所定段数ｍ１とは、後述の学習時に決定される第一分岐で最低限継続すべき非分岐継続段数であって、第一分岐から第二分岐までの継続段数ｎ１と一致していても構わない（ｍ１≦ｎ１）。本判別器は後述するように、第一分岐の全ての枝の弱判別器列をｍ１段まで処理した結果に基づき、処理を継続する枝を決定する。従って、実行予定キューに挿入された上記ＩＤ: 12_＜ｎ0+2ｎ１ +ｍ１-1＞までのノードによる処理は、各枝途中で打ち切りが発生しない限り必ず実行されることになる。つまり、第一分岐ｍ１段目のノードとは、第一分岐についての分岐選択ノードである。以後、ｍ２、ｍ３についても同様にそれぞれ第二分岐、第三分岐についての分岐選択ノードであるものとする。
【００９１】
続いてステップＳ１５０２において、実行予定キューに格納されている先頭のＩＤを一つ取り出す。そして、取り出したＩＤのノードに関し、ステップＳ１５０３のノード内判定処理を実行する。ノード内判定処理の詳細は、上記で図７を用いて説明した通りである。
【００９２】
そしてステップＳ１５０４において、ノード内判別処理結果が打ち切り判定であったかどうかをチェックする。このとき打ち切りであった場合は、実行中のノードが第一分岐より前の弱判別器列の中の一つであれば、以後の処理を全く行う必要がなくなる。また、実行中のノードが分岐のいずれかの枝に弱判別器列の中の一つであるならば、以後の段のその枝の判別器と、その枝から分岐する全ての枝の判別器を実行する必要がなくなる。
【００９３】
これらの実行する必要の無くなったノードのＩＤを全て実行予定キューから取り除く処理が、ステップＳ１５０５である。この処理では、まず打ち切り判定されたノードのＩＤの分岐枝ＩＤ部をチェックする。そして実行予定キューを先頭からスキャンし、分岐枝ＩＤが一致するＩＤを全て取り除く。最後に取り除いたＩＤに関しては、保持しておき、同一分岐枝のＩＤが無くなった時点で、最後のＩＤを用いてパラメータメモリからその後段ＩＤを調べる。そして、再び実行予定キューをスキャンし、調べた後段ＩＤの分岐枝ＩＤ部と一致するＩＤを全て取り除く。これを繰り返すことにより、打ち切り判定されたノードに続く全てのノードのＩＤを実行予定キューから取り除くことができる。
【００９４】
次にステップＳ１５０６において、実行予定キュー内に、その他のノードのＩＤが残っているかをチェックする。もし打ち切られたのが、第一分岐前のノードであるならば、この時点でキュー内に他のＩＤは残っていないはずである。第一分岐後のいずれかの枝のノードであるならば、他の枝のＩＤが残っている可能性があるので、残っている場合にはステップＳ１５０２に戻って、再び一つずつＩＤを取り出して判別処理を実行してゆく。
【００９５】
実行予定キュー内にＩＤが残っていなければ、ステップＳ１５０７に進み、打ち切られた枝とは別の継続中の枝があるかどうかをチェックする。このチェックは、後述の継続中ＩＤが保持されているか否かで判別する。継続中の枝があれば、後述のステップＳ１５１１に進む。継続中の枝が無ければ全ての枝が打ち切られたことになり、そのサブウィンドウは顔ではないと判定されて処理終了となる。
【００９６】
ステップＳ１５０４の判定で打ち切りでなかった場合、ステップＳ１５０８に進み、実行したノードがキュー内に収められている終端ノードであったかどうかを判定する。実行予定キューをスキャンし、キュー内に同一の枝の後続ノードのＩＤが格納されていなければ、キュー内終端ノードであったと判定される。そして、ステップＳ１５０９において今回実行したノードＩＤを継続中ＩＤとして、メモリの所定領域に保持する。終端ノードでなかった場合は、ステップＳ１５０９の処理はスキップされる。
【００９７】
次にステップＳ１５１０において、実行予定キュー内に他のＩＤが残っているかを調べる。残っていれば、Ｓ１５０６と同様それらを実行すべく、ステップＳ１５０２に戻って処理を繰り返す。
【００９８】
実行予定キュー内のＩＤが全て無くなったら、ステップＳ１５１１に進み、未実効ノードの有無を調べる。先の処理の結果、継続中のノードＩＤはステップＳ１５０９でメモリの所定領域に保持されているので、このＩＤを用いてパラメータメモリ４５１の双方向リスト部分にアクセスし、後段ＩＤがセットされているかどうかを調べてセットされていれば未実行ノード有りと判断される。
【００９９】
未実行ノード有りの場合は、ステップＳ１５１２に進み、分岐選択処理を実行する。本実施形態の分岐選択処理は、処理する分岐の全ての枝の、所定段位置の弱判別器の処理結果を用いる。従って、ステップＳ１５１２に入る前に、全ての枝で所定段数以上の弱判別器処理が完了している必要がある。先の説明で、実行予定キューに格納するＩＤは、各枝の所定段数までと述べたが、所定段数以上であればいくつでも構わない。
【０１００】
本実施形態における分岐選択処理は、図１６のフローチャートに示す極めてシンプルなものとなっている。まずステップＳ１６０１において継続中の分岐選択ノードの累積スコア値を取得する。先に述べたとおり、継続中ＩＤは保持されており、過去のＩＤは実行予定キューに格納されていた終端ノードであるので、分岐選択段（ｍ１またはｍ２またはｍ３段目）で処理が打ち切られていないノードのＩＤとなっている。累積スコアは、図７のステップＳ７０６として説明されたとおりＩＤと関連付けられて保持されているので、継続中ＩＤを用いて値を取得することができる。
【０１０１】
そしてステップＳ１６０２において、累積スコアが最大となっているノードのＩＤを、継続するＩＤとして選択する。つまり選択したＩＤの分岐枝ＩＤ部が、選択された分岐の枝を示すことになる。尚、ここで、新たな閾値を用い、累積スコア値が最大値のものだけでなく、閾値の範囲の複数のＩＤを残すようにしても良い。このようにすると、以後処理する分岐の枝は増えるが、処理速度とのトレードオフで精度の向上を図ることができる。
【０１０２】
説明を図１５に戻し、ステップＳ１５１３において、実行予定キューの再設定を行う。この処理は、まず分岐選択処理ステップＳ１５１２の結果、残った分岐の継続中ノードＩＤを用い、パラメータメモリ４５１の双方向リスト部を参照する。そして、継続中ノードが属する分岐枝の残りノード全てと、次の分岐の各枝の所定段の分岐選択ノードまでを、実行予定キューに格納する。先に説明したとおり、ここでの所定段とは、第二分岐についてはｍ２、第三分岐についてはｍ３段までであり、後述の学習時に決定されている。また、ここで、以後の分岐がない場合、双方向リストで継続中ノードＩＤに続くノードのＩＤは、終端まで全て実行予定キューに格納される。
【０１０３】
そしてステップＳ１５１４において、保持していた継続中ＩＤをクリアし、ステップＳ１５０２に戻って、再びノード毎の処理を繰り返す。
【０１０４】
ステップＳ１５１１において、未実行ノードが無いと判断された場合、ステップＳ１５１５の統合処理を行う。この統合処理は、継続中ノードとして残ったＩＤの出力値を統合する処理で、平均値や合計値あるいは最大値を算出して最終的な顔らしさを判別する信頼度スコア値とする。さらにここで、たどり着いた分岐の枝に基づく、顔の変動の推定も行うようにすることもできる。
【０１０５】
そしてステップＳ１５１６において、算出した信頼度スコア値を最終閾値処理して、顔であるか否かの判別を行う。これは図３(ａ)の最終判定部３０７の処理に相当する。
【０１０６】
（基本学習処理）
次に図６を用いて、本実施形態に関わるブースティング型のパターン識別器を機械学習処理により生成する基本的な方法について説明する。図6は、非分岐の一列の弱判別器列のみで構成されるパターン識別器を生成するための機械学習処理のフローチャートであるが、分岐の各枝に相当する各弱判別器列を学習する際にも、基本的に同じアルゴリズムが用いられる。但し、各枝に用いられる学習データセットの顔データは、それぞれの枝が担当とすべき変動範囲の分類となるものである。
【０１０７】
尚、以下に説明する機械学習処理は、図２におけるＣＰＵ２０８が学習処理プログラムを動作させることにより実行されるものである。
【０１０８】
また、ここで説明する学習処理に先立ち、大容量記憶部２１１には学習に必要なデータ群がカテゴリに従って分類されて格納されている。これらのデータ群は、図８で説明した処理ウィンドウサイズのデータ８０１に切り出された顔または非顔パターンである。もしくは都度切り出しするようにしてもよい。そして、学習しようとする弱判別器列に対応する変動カテゴリの変動範囲で分類される変動を持つ検出対象データと、背景等の非検出対象データを、それぞれ多数用いることが可能になっている。例えば、図５で説明したラベルaB1の変動範囲を担当する第三分岐後の枝の弱判別器列の学習においては、同ラベルaB1に分類される大容量記憶部２１１に保持された顔画像データの、全てまたはその１部が検出対象データとして用いられる。非分岐の枝については全カテゴリの変動を含むデータが用いられ、第一分岐の枝の学習時には、カテゴリ(ii)と(iii)は全ての変動を含むデータが、第二分岐の枝の学習時には、カテゴリ(iii)は全ての変動を含むデータが用いられる。
【０１０９】
以下、ＡｄａＢｏｏｓｔと呼ばれるアンサンブル学習アルゴリズムに従って弱判別器を学習させる。基本的な学習アルゴリズムは非特許文献１に記載の手法と同一である。
【０１１０】
まず、ステップＳ６０１で、大容量記憶部２１１に保持する学習データから、今回の学習に使用するデータを選択する。ここでは検出対象パターンである顔データと非検出対象パターンである非顔データを、所定の比率の数となるように取り出す。
【０１１１】
予備識別器または本識別器の分岐には、それぞれ担当すべき変動カテゴリの組合せによる分類があるので、当該分類に所属する顔データが検出対象パターンとして選ばれる。非検出対象パターンとしては非顔データが用いられるが、さらに非検出対象パターンとして、担当しない変動カテゴリ組合せで分類される顔パターンを追加して学習することも可能である。このようにすると、各予備識別器或いは分岐は、より選択性の高い検出処理を行うようになることが期待できる。
【０１１２】
ステップＳ６０２では、取り出した学習データセットに対する重み係数を初期化する。学習データの総数がｍ個の場合、全ての重み係数ｗt,j（t：ノード番号、i：学習データ番号）を以下の式(５)で初期化する。
【０１１３】
【数５】
0004948379.tif 000006
【０１１４】
つまり、第１ノード学習時には、全ての学習データに対して共通の重みを与えている。次のステップＳ６０３で式(６)に従って重み係数を正規化する処理を行う。
【０１１５】
【数６】
0004948379.tif 000007
【０１１６】
最初にこのステップＳ６０３に入ってきたときは、重み係数ｗ１, jはステップＳ６０２（式（５））で設定された値になっているので、すでに式(６)を満たす状態となっている。従って、このステップＳ６０３は、第２ノード以降の学習時に重み係数ｗt, jが変更された場合に、その総和が１となるように正規化するための処理である。
【０１１７】
続いて、ステップＳ６０３〜Ｓ６１０で１つの弱判別器を学習する。
【０１１８】
まず、ステップＳ６０４で矩形フィルタ群の中から１つの矩形フィルタを選択する。矩形フィルタ群とは、予め定めた形状の基本矩形フィルタに対して、その大きさや検出ウインドウ内の位置に応じた変形を有する複数の矩形フィルタ候補である。例えば、図９の第１弱判別器に例示した上下の隣接矩形領域の差分フィルタの場合であっても、その矩形領域の大きさや縦横比、検出ウインドウ内の位置に応じて複数の変形が考えられる。矩形フィルタ群としては、予め定めたいくつかの基本矩形フィルタを基準にして、その変形も含めた全ての組合せを用意しておく。用意された矩形フィルタ夫々に通し番号を振って、これをフィルタ番号とする。本ステップは用意したこれら矩形フィルタ候補を一つずつ順に選択する処理を行う。
【０１１９】
次に、ステップＳ６０５で選択した矩形フィルタ候補を用いて、全ての学習データに対するこの矩形フィルタの判別性能評価を行う。まず、全ての学習データ各々に対して、この矩形フィルタ出力値を算出し、検出対象と非検出対象を分離する閾値を決定する。このときフィルタ出力値の算出は判別処理部２０３を利用してハードウェアで処理する。閾値の決定は矩形フィルタ出力値のヒストグラムを利用して行う。
【０１２０】
図１３は全学習データに対する検出対象データのヒストグラム１３０２と非検出対象データのヒストグラム１３０１を示す。横軸はフィルタ出力置（矩形差分値）で縦軸はその値となった学習データの数を表す。ヒストグラムを使用して検出対象と非検出対象を最も良く分離する閾値ＦTh_ｔ, j（誤り率最小となるもの、t：学習中のノード番号、j：フィルタ候補番号）を決定する。更に、ステップＳ６０５では、決定した閾値ＦTh_ｔ, jを用いて全ての学習データに対する検出誤り率を算出する。式(７)は全ての学習データに対する重み付き誤り率である。
【０１２１】
【数７】
0004948379.tif 000008
【０１２２】
ここで、ｈt, j(xi)は矩形フィルタ候補jによる学習データ番号iの判定出力であり、前記閾値ＦTh_ｔ, jを使用して入力対象データｘiが検出対象であると判定した場合１を出力し、検出対象を含まないと判定した場合０を出力する。yiは正解ラベル（教示ラベル）であり入力学習データiが検出対象であるか否かによって、それぞれ１又は０が割り当てられている。ステップＳ６０６による繰り返し処理で、以上の処理（ステップＳ６０４、Ｓ６０５）を全ての矩形フィルタ候補に対して実施しそれぞれの重み付き誤り率Et, jを求める。
【０１２３】
全ての重みつき誤り率Et, jの算出が終了すると（ステップＳ６０６）、この中で最も重み付き誤り率Et, jの小さい矩形フィルタ候補ｊ（即ち最も判別性能が高い矩形フィルタ）を探して、これを弱判別器として選択する(ステップＳ６０７)。このときの重み付き誤り率をEtとする。また、このフィルタで用いられた閾値ＦTh_ｔ, jをフィルタ閾値WTh_ｔとする。
【０１２４】
そして、式(８)により弱判別器に対する信頼度αtを算出する(ステップＳ６０８)。
【０１２５】
【数８】
0004948379.tif 000009
【０１２６】
算出した信頼度αtやフィルタ閾値WTh_ｔ、矩形フィルタの矩形領域の形状、位置、矩形数、フィルタ係数は、ＲＡＭ２１０に学習中のノードｔのパラメータとして記録する。
【０１２７】
次に、ステップＳ６０９において、打ち切り閾値を決定する。ここでも矩形フィルタの判定閾値を決定した手法と同様に、検出対象データに対する累積スコアのヒストグラムと、非検出対象データに対する累積スコアのヒストグラムから閾値を決定することができる。図１４は打切り閾値の決定法を説明するための累積ヒストグラムの例を模式的に説明する図である。１４０１は非検出対象データに対する累積スコアのヒストグラムであり、１４０２は検出対象データに対する累積スコアのヒストグラムである。打ち切り閾値は、検出対象データに対する打ち切り割合（検出対象データの打切り数／検出対象データ数）が所定以下の許容範囲になるように決定される。検出対象データの打切り数とはすなわち、ヒストグラム１４０２の累積スコアが、ここで定めた閾値以下になるデータの総数である。非検出対象データに関しては打ち切られる程良いので、ここでは考慮しなくてよい。ここで定めた閾値が、図４の打切り判定部４６１で用いられる打切り閾値パラメータＴｇｈ_ｔとなる。
【０１２８】
更にステップＳ６１０では、各学習データに対する重み係数を下記演算式(９)で更新する。
【０１２９】
【数９】
0004948379.tif 000010
【０１３０】
但し、式(９)で更新する重み係数ｗt, jは正しく検出できた学習データiの係数のみである。即ち、正しく検出された学習データ（検出対象データ、非検出対象データ共）の重みは、小さくなる様に更新される。従って、ステップＳ６１０では、検出を誤った学習データに対する重みを、相対的に大きくしていくことになる。
【０１３１】
ここまでの処理（ステップＳ６０３〜Ｓ６１０）で1つの弱判別器を生成した後、ステップＳ６１１では所定の完成条件を満たすブースティング判別器が生成された否かを判定する。ここで所定の条件とは、第一には弱判別器数が予め設定した上限数に到達した際に満たされる。あるいは、式(７)で計算した重み付き誤り率Et, jが所定の値を下回るか、別途設けた性能測定手段により識別器全体の識別性能が学習を開始する際の所望の性能を達成できたと判定された場合に満たされる。条件が満たされない場合は、ステップＳ６０３に戻って続く弱判別器の生成処理を継続する。
【０１３２】
（学習および評価用データセット）
本実施形態においては、学習に先んじて、サンプルデータの入力と分類処理を行っている。これは学習処理と学習処理中の評価処理に用いる検出対象のオブジェクト画像データ（本実施形態では顔画像データ）を装置に入力する処理であり、対象とするカテゴリの変動を全て含んだ十分な数のデータが必要である。学習用データと評価用データは別々に分けて入力しても良いし、多量の顔画像データ群を入力しておき、学習処理時と評価処理時に、それぞれサンプリングして用いるようにしても良い。
【０１３３】
また、検出対象のオブジェクトでない物体や背景等の非検出対象パターンの集合、すなわち本実施形態では非顔データの集合も装置に入力され、学習および評価処理で用いることができる。
【０１３４】
これらデータの入力は、図２の画像入力部２０１によって行われる。画像入力部２０１が撮像装置で構成される場合には、撮影によって収集された顔画像に、ユーザがUser I/F２０７を介して必要な付随情報（目や口の位置座標等）を入力することによりデータは蓄積される。あるいは画像入力部２０１と共用の通信Ｉ/Ｆ２０６を介して、外部装置より予め収集された顔画像を付随する情報と共に入力することもできる。入力された学習データ及び評価データは、大容量記憶部２１１に保持される。
【０１３５】
入力・保持された顔画像データは、付随する情報を用いて、識別器が対応しようとする全ての変動カテゴリで分類（ラベル付け）される。例えば、「反時計回りに30°面内回転した左側10°の奥行き回転方向を向いたサイズ１８の顔」は、図５に示したラベルで「aB1」と分類される。
【０１３６】
本実施形態において、顔データには、両目座標・口座標・奥行き回転角度の３つの情報が付随する。User I/F２０７でこれらの情報を入力する場合には、ディスプレイ上に表示された顔画像に対し、マウス等のポインティング・デバイスを用いて目や口の座標を入力する。また、キーボードにより（主観的な）奥行き回転角度を入力する。外部装置より学習用および評価用データが送られてくる場合には、すでに入力済みのこれら付随情報も合わせて送られてくる。
【０１３７】
本実施形態において、カテゴリ(i)の面内回転角度は、両目を結ぶ線分の角度により算出される。この線分が画像中で水平の場合が面内回転０°であり、これを基準として時計回り方向の回転を＋とする。また、カテゴリ(iii)のサイズ変動は、両目を結んだ線分と口位置までの高さの差の画素数により計算する。横顔で片目しか見えていない場合には、別途頭の真上を示す頭頂方向を付随情報として入力し、これによって面内回転とサイズを計算できる。尚、片目の目尻目頭、耳位置、鼻孔位置等、特徴点位置を示す付随情報を増やして、これらから頭頂方向を推定計算するようにしても良い。
【０１３８】
この学習および評価用データの入力・分類処理は、学習開始前のどのタイミングで行っても構わない。次に説明する学習と評価で用いるデータが異なる場合には、それぞれの開始前までに完了して、大容量記憶部２１１に保持されていればよい。
【０１３９】
或いは、学習処理中に、通信Ｉ/Ｆ２０６を介して外部装置に蓄積された分類済みデータを逐次、取得するように実装することも可能である。
【０１４０】
また、以下に説明する分岐の各枝の弱判別器列の検出対象とする顔データは、分岐枝が担当する変動カテゴリの分割された変動範囲の組合せで分類される顔データである。例えば、図５のaB1のラベルで示される分類に対応する第三分岐後の枝の弱判別器列は、同ラベルの付いた顔画像のみを検出対象データとして学習する。最終分岐に到達する前の枝では、到達していない変動カテゴリによる分類は任意であって、全ての変動範囲を各枝が担当する。例えば、第一分岐の担当範囲を示すラベルはa**, b**, c**のいずれかであって、始まっていない分岐が対応すべき変動カテゴリに関しては、アスタリスクでラベルを表すものとする。また、非検出対象の非顔データは、いずれの枝用であっても共通で、特にラベルは無いものとする。
【０１４１】
（最小継続段数判定付きの学習フロー）
図１は、本発明の特徴的な処理であるパターン識別器生成方法の一例を示すフローチャートである。この処理では、分岐型パターン識別器における分岐の各枝の非分岐継続段数の決定を行う。尚、同図において、ステップＳ１０１、 Ｓ１０３, Ｓ１０７の弱判別器生成処理は、図６で説明した基本的な学習処理方法と同等の処理である。
【０１４２】
ステップＳ１０１において、分岐前の一列の弱判別器列を生成する。この処理における図６のステップＳ６１１に相当する完成条件の判別は、予め経験的に定めた所定段数とする。もしくは、評価用データセットとして多数の非顔データを用い、１段生成するごとに検出処理（図７および１５）を実行して、その累積的な打ち切り率を調べ、所定の非顔累積打ち切り率を達成するところまでを所定段数として決定する。１段毎の非顔打ち切り率は、図２４に示すように、必ずしも単調に減少するとは限らず、例えば、同図３段目と４段目のように、ほとんど打ち切られなかった次に多く打ち切られたりする現象が見られる場合もある。このような場合、３段目まで継続させるより４段目まで継続させた方が、打ち切り効率が良くなる可能性がある。さらに顔データの打ち切り率を考慮するようにしても良い。例えば、顔データ打ち切り率が所定の容認顔打ち切り率以内であることを継続条件に加えても良い。この考え方は、以下に説明する分岐後の各枝の非分岐継続段数決定にも、用いることができる。
【０１４３】
所定段の弱判別器生成が完了したところで、ステップＳ１０２において分岐点を設定する。最初のステップＳ１０２の処理としては、分岐構造は図３(ｂ)に示した通りであるので、カテゴリ（i）の変動範囲を３分割するａ、ｂ、ｃに対応した３分岐である。
【０１４４】
次のステップＳ１０３では、各分岐の枝それぞれの弱判別器列を所定段ずつ生成する。ここでの所定段は、分岐後初回の実行時では、明らかに最低限必要な非分岐継続段数（最低継続段数）が予め経験等により分かっている場合は、その段数を設定すればよい。不明である場合や分岐後２回目以降の実行では、所定段は１段ずつとする。また各分岐枝に用いる学習用データは、それぞれカテゴリ（i）のａ、ｂ、ｃの変動を持つデータであり、それぞれカテゴリ(ii)および(iii)の変動に関しては全変動範囲のデータを含むものである。それぞれの分岐枝の弱判別器列は、識別器の先頭の分岐前の弱判別器から継続しているものと見なす。このとき図６のステップＳ６０２の重み係数初期化に相当する処理は上述とは少々異なる。本処理では、それぞれの分岐枝用の学習用データセットを生成済みの分岐前の弱判別器列に投入して、各段の処理でフィルタやその他の係数は変更せずに、ステップＳ６０３やステップＳ６１０の重み係数更新のみ行って得られる重みにする。
【０１４５】
ステップＳ１０４において、生成された分岐枝の弱判別器列を評価比較し、最低限継続すべき段数に到達したか否かを調べる。本実施形態においては、評価用のパラメータとして、図１８に示す累積スコアを用いた評価を行っている。
【０１４６】
図１８において、まずステップＳ１８０１で、今回評価する分岐に対応する変動カテゴリについて、一つの分類（すなわち分割された変動範囲の一つ）を選び、予め用意されている評価データの中から変動範囲に分類される変動を持つデータセットを選択する。
【０１４７】
例えば、第一分岐の評価処理としては、カテゴリ（ｉ）のａ、ｂ、ｃいずれかの変動範囲に分類されるデータ群が評価用データセットとして選択される。これらのデータセットは、他のカテゴリ（ii）,（iii）については全ての変動範囲のデータを含んでいる。このようなデータの分類ラベルを、便宜上、「a**」「b**」のように、確定している変動カテゴリ以外を表す桁はアスタリスクで記述するものとする。
【０１４８】
次にステップＳ１８０２で、分岐した枝を一つ選択する。各枝はそれぞれカテゴリ(i)のa, b, cいずれかの変動範囲を担当とする弱判別器列である。
【０１４９】
そしてこの選択した枝の弱判別器列に対し、ステップＳ１８０１で選択した評価データを投入し、ステップＳ１８０３において、検出処理を実行する。この検出処理は、非分岐の先頭の弱判別器から選択した枝の生成済み弱判別器までを一列の弱判別器列と見なして実行する検出処理であって、図１５のような分岐選択処理（ステップＳ１５１２）は行わない。図７の処理のみを、弱判別器ノード段数分繰り返す処理であって、ステップＳ７０７で打ち切られた場合は以後の段の処理は行わない。
【０１５０】
ステップＳ１８０４においては、全ての分岐枝に関して、選択されている変動の評価データに対する検出処理を実行したかどうかをチェックし、実行していなければステップＳ１８０２に戻って、全分岐枝分の処理を実行する。
【０１５１】
ステップＳ１８０５においては、評価中の分岐に関する全ての分類の評価データで検出処理を行ったかどうかを確認し、行っていなければステップＳ１８０１に戻って次の分類を選択する。
【０１５２】
このようにして、各弱判別器列に各変動データを投入する全ての組合せの検出処理結果が得られる。例えば第一分岐では、ａ、ｂ、ｃの弱判別器列それぞれに、ａ、ｂ、ｃのデータを投入した９通りの検出処理結果が得られることになる。
【０１５３】
全ての組合せの検出処理が完了したら、ステップＳ１８０６において累積スコア差分算出処理を行う。この処理は、まず、ある変動範囲データセットを一つの分岐枝に投入した際の累積スコア値の平均値をそれぞれ求め、その分岐枝間差分値を比較する処理を行う。
【０１５４】
図１９(ａ)は、a**変動データセットを第一分岐後の３本の分岐枝に投入した際の、弱判別器１段ずつの累積スコア値の遷移を示す図である。この例では、非分岐の弱判別器は１段のみであり、１段目の出力は同じ値となっている。２段目から３分岐してそれぞれの枝に異なった弱判別器を生成している。処理段数が進むにつれて、徐々に累積スコアの差が開いていくことが分かる。a**変動データセットは、本来a**対応の分岐枝で検出されるべき変動であるので、a**分岐の出力が最も高くなっている。また、a**は図５に示したように左面内回転であるので、a**に比較的近い変動範囲を担当とするb**分岐の出力が次に高くなっており、c**分岐は最も低い累積スコア値となっている。
【０１５５】
図１９(ｂ)は、同様に、b**変動データセットを３本の分岐枝に投入した際の平均累積スコアと遷移を示す図である。b**変動範囲は、ほぼ正立の面内回転範囲を示しているので、a**にもc**にも同程度近い変動範囲である。従って、本来担当すべきb**分岐が最も高い累積スコア値を示すが、a**分岐とc**分岐は、ほぼ同程度の値となっている。
【０１５６】
このように、３以上の分岐枝がある分岐の場合、ステップＳ１８０６ではこれらの平均累積スコア値の差分を計算し、それらを統合する処理を行う。統合処理としては、累積スコア差の値の平均を求めてもよいし、最小値を選択するようにしてもよい。最小値を選択するようにすると、分岐の選択性は高まることが期待されるが、その分長い継続段数が必要になる可能性が高くなる。
【０１５７】
そして、ステップＳ１８０７において、統合した差分値が予め定めてある所定値以上となったところを、最低継続段数として判定する。ここでの所定値は、差分値そのもので定めても良いが、より汎用的に評価しようとしている段の平均累積スコア最大値に対する割合で定義しても良い。
【０１５８】
本実施形態の検出時における分岐選択処理は、図１６で説明したように、分岐後の各枝の累積スコア値に基づいて、その累積スコア値が最も高いノードの属する枝を選択するものである。従って、投入した評価データセットに対する平均的な累積スコア差が開けば開くほど、正しく担当する分岐の枝が選択される率が高まるものと期待できる。平均累積スコアの差だけでなく、例えば、分散も加味するような非分岐継続段数決定アルゴリズムを用いても構わない。
【０１５９】
ステップＳ１８０７で各枝の平均累積スコアの差分が所定差（予め定められた差分値）以上になったと判別されたら、ステップＳ１８０８において、今回評価した段が、最低継続段数であると決定される。所定差以上でなければ、ステップＳ１８０９において、まだ最低継続段数に達していないものと決定される。
【０１６０】
説明を図１に戻し、ステップＳ１０５で、最低継続段数に到達したかどうかを判断する。実際にはステップＳ１８０７と一体化して構わないが、説明しやすさからここにも記述している。ここで最低継続段数に到達したと判定された場合（ステップＳ１０５−Ｙｅｓ）、決められたのはあくまで「最低限必要な」非分岐継続段数であるので、実際に継続させる段数は非分岐継続段数以上であればいくつでも構わない。従って、次のステップＳ１０６に進む前にさらに追加で所定段の弱判別器を生成するようにすることもできる。
【０１６１】
ステップＳ１０６では、次の分岐予定が残っているかを確認する。例えば、第一分岐後の最初の処理であれば、次に第二分岐を行うべく、ステップＳ１０２に戻って処理を再開する。第三分岐までの処理が完了しており、残りの分岐がないならば、ステップＳ１０７に進む。
【０１６２】
ステップＳ１０７では、生成した各分岐の枝の弱判別器列に対し、残りの弱判別器を所定段あるいは所定条件を満たすまで生成してゆき、全分岐について生成完了したときに処理は完了となる。
【０１６３】
以上説明したように、本実施形態のパターン識別器生成方法によれば、特定の変動の評価用データに対する分岐の各枝の累積スコア差を評価することにより、良好な分岐選択を実現するために最低限必要な非分岐継続段数を決定することができる。
【０１６４】
（第２実施形態）
第１実施形態では、累積スコアの差分値を用いて、最低限必要な非分岐継続段数を決定する方法について説明したが、第２実施形態では、評価用データを投入した際の分岐の選択誤り率に基づき、最低継続段数を決定する方法について説明する。
【０１６５】
本実施形態において、第１実施形態と説明の重複を避けるため、第１実施形態との違いについてのみ説明する。生成した各分岐枝の弱判別器列を評価しながら学習を進める基本的な処理の流れは、図１に示した第１実施形態と同様である。本実施形態では、ステップＳ１０４において説明した生成済み弱判別器列評価処理は、図２０に示すように行われる。
【０１６６】
図２０の評価処理では、評価用データセットとして、評価しようとしている分岐に関する、全ての変動カテゴリの分類の組合せの変動を持つ顔データ群が用いられる。これは第一分岐であれば、全てのラベルの顔データ群であり、第一分岐ラベルが「a」である枝の第二分岐を評価しようとしているのであれば、「a**」とのラベルの付いた顔データ群が用いられる。ここで、「**」は、カテゴリ(i)および(iii)の全てのラベルの組合せである。ステップＳ２００１では、これらの評価用データの中から、一つの顔データを選択する。
【０１６７】
そして、ステップＳ２００２において、生成されている段までの分岐構造のパターン識別器に対して、選択した顔データを投入し、図１５および図１６に示した分岐選択付きの検出処理を実行する。この結果、生成中の分岐のいずれかの枝が選択される。各評価用顔データには、先に説明した通りの分類ラベルが付いている。また、各分岐の枝にも、担当すべき分類ラベルがついている。図１６の選択処理を行った結果、このラベルが、評価中のカテゴリの桁に関して一致していれば、正しい選択が行われたことになる。ステップＳ２００３において、ステップＳ２００２の検出処理で正しい選択が行われたかどうかを判別する。選択が正しくなかった場合（ステップＳ２００３−Ｙｅｓ）、処理をステップＳ２００４に進める。Ｓ２００４において、選択誤りカウントをインクリメントする。
【０１６８】
一方、ステップＳ２００３の判定処理で、分岐選択が誤りでない場合（ステップＳ２００３−No）、処理はステップＳ２００５に進められる。
【０１６９】
ステップＳ２００５において、評価すべきデータに対する検出処理および選択誤り判定処理が完了したかどうかをチェックし、完了していなければ残りのデータを評価すべく、ステップＳ２００１に戻る。
【０１７０】
全ての評価データに対する処理が完了したら、ステップＳ２００６において、選択を誤った率（選択誤り率）を算出する。これは選択誤りカウントを評価したデータの総数で除算する処理である。
【０１７１】
そしてステップＳ２００７において、この誤り率が所定値以下であるかどうかを判別し、所定値以下であれば、生成済みの段を最低継続段数に到達したと判定し（ステップＳ２００８）、そうでなければ未達として判定（ステップＳ２００９）する。以後の処理は図１で説明した通りである。
【０１７２】
選択誤り率は、図２１に示すように、処理段数が進むにつれて減少して行くことが期待できる。これは第１実施形態で説明した処理段数が進むにつれて累積スコア差が開いてゆくことと関係する。
【０１７３】
本実施形態によれば、検出時に行う分岐選択処理を評価時にも行って、その誤り率で分岐後の枝の最低継続段を決定している。従って第１実施形態に比べて、パターン識別器に対して、より直接的に期待する性能を実現させることが可能になる。尚、処理段数を増加させても、必ずしも選択誤り率が下がらない場合は、継続段数に上限を設ける等、他の手段と併用することも可能である。
【０１７４】
（第３実施形態）
第１および第２実施形態では、分岐後の所定段における累積スコア値を用いて、分岐選択を行う場合について説明したが、他の分岐選択方法を用いることも可能である。
【０１７５】
図２２の２２０１は、ある分岐における分岐選択判別器を示している。パターン識別器は、分岐選択判別器２２０１が出力する分岐選択判別結果に基づいて、各分岐で残すべき枝の選択を行う。
【０１７６】
分岐選択判別器２２０１は、分岐選択処理対象の弱判別器列の各ノードが算出する特徴量を入力として、分岐方向の選択を行う。この判別は、線形判別分析やＳＶＭ（Support Vector Machine）等の公知の判別処理を用いればよく、それらの識別手法に必要となるパラメータはあらかじめ学習させて、求めておく必要がある。
【０１７７】
分岐枝の選択のために分岐選択判別器２２０１へ入力されるのは、弱判別器ノードの通常の判別処理（図７）で算出される量（ここでは特徴量）であり、分岐選択のために特別に算出するものではない。したがって、選択のために必要となるオーバーヘッドは、弱判別器の処理とは無関係な全く新たな量を算出して、分岐選択判別器２２０１に入力する場合に比較して、軽微なものですむ。
【０１７８】
分岐選択判別器２２０１への入力として用いる値は、特徴量だけでなく、フィルタ閾値による判定結果や単独スコア、累積スコア等、図７の判別処理で算出される如何なる値をもちいても構わない。使用する値は、ノードＩＤと関連付けて、メモリ内に保持するようにしておく。
【０１７９】
また、図２２は２分岐の場合を図示しているが、３分岐以上の場合にも適用可能である。３分岐の場合に、２分岐と同様のＳＶＭのような２クラス判別器を用いる場合には、３分岐中の全ての２分岐の組合せに関して２クラス判別器を接続し、それらのスコアを比較する方法を取っても良い。
【０１８０】
この分岐選択判別器２２０１を用いた分岐選択処理は、図２３のようになる。まずステップＳ２３０１において、各分岐枝の生成済み最終段のノードＩＤから、図１７のパラメータメモリ上の双方向リスト部を参照し、分岐後のノードからの全てのＩＤを取得する。
【０１８１】
そしてステップＳ２３０２において、取得した全てのＩＤに対応する分岐選択処理で用いる特徴量等の値をメモリから取得し、ステップＳ２３０３において分岐選択判別器２２０１に入力して判別処理を実行する。ステップＳ２３０４においては、得られた判別結果に基づき、選択する分岐のＩＤを決定して処理完了となる。
【０１８２】
図２３の分岐選択処理を用いて、図２０の選択誤り率評価処理を行う場合、評価に先んじて、分岐選択判別器２２０１の再学習を行っておく必要がある。なぜなら、弱判別器ノードが１段生成される毎に、分岐選択判別器２２０１へ入力される特徴量の数は増加するため、前回評価時に用いた分岐選択判別器２２０１とは、入力次元数の異なった判別器が必要となるからである。分岐選択判別器２２０１の学習時においても、選択時と同様に入力となるノードのＩＤを双方向リストから取得しておく。そして、分岐選択判別器２２０１学習用データセットのデータ各々に検出処理を行って、そのときの各分岐の判別器出力を得ると共に、学習データの正解ラベルに基づき、所定のＳＶＭなどの学習処理を実施する。
【０１８３】
このような分岐選択判別器２２０１を用いると、最終段の累積スコア値のみを用いて判定していた場合に比べ、より精度の良い分岐選択が期待できるようになる。また、分岐選択判別器２２０１を用いても、第２実施形態のような選択誤り率による最低処理段数決定処理に適用することが可能なのは言うまでもなく、より性能の良いパターン識別器が得られることが期待できる。但し、上述したように、段弱判別器を一段生成する毎に、分岐選択判別器２２０１を学習し直す必要があるため、識別器の学習時間のトータルは長くなる。
【０１８４】
（他の実施形態）
以上説明してきた各種処理方法を、組み合わせて適用することも可能である。例えば、第１実施形態で説明した第一分岐前の継続段数決定方法として非顔あるいは顔データの打ち切り率を用いる方法を、分岐後の継続段数決定時の１条件として加えることも可能である。
【０１８５】
あるいは、第１実施形態で非分岐継続段数を決定して学習したパターン識別器に対して、第３実施形態で説明した分岐選択判別器を用いる分岐選択方法を適用することも可能である。すなわち学習済みの分岐構造パターン識別器に対し、その構造や弱判別器のパラメータは固定したままで、分岐選択判別器のみの学習を行うことによって、選択精度を高めて性能向上を図ることができる。
【０１８６】
また、これまで説明してきた実施形態では、分岐数が２乃至３の場合についてのみ説明を行ったが、本発明の分岐数は、これに限定されるものでないことは言うまでも無い。
【０１８７】
上述の実施形態では、累積スコア差による評価や、選択誤り率に基づく評価方法について説明したが、本発明の本質は、これらに限るものではない。生成した弱判別器列に評価用データセットを投入し、その検出処理結果に基づいて継続段数を決定するものに適用可能である。従って、例えば、対象パターンの検出性能（未検出率、誤検出率、検出速度等）に基づき、継続段数を決定するようにすることも可能である。
【０１８８】
また上述の実施形態では、検出対象パターンとして画像データ中に含まれる人物の顔を検出するパターン識別器に関して説明したが、本発明の適用範囲はこれに限るわけではない。入力に含まれる個人を特定する個人認識のためのパターン識別器にも適用可能であるし、人以外の特定の物体を検出するパターン識別器にも適用可能である。
【０１８９】
２次元の画像データに対する処理に限定するものでもなく、音声データ等の１次元データや、次空間要素を含む３次元以上の多次元データから、特定のパターンを抽出するパターン識別器にも適用可能である。
【０１９０】
上述の実施形態では弱判別器として矩形フィルタを用いた方式に適用した場合について説明したが、他の様々な弱判別器に適用可能である。
【０１９１】
また、弱判別器の学習手法の例としてAdaBoostを示したが、これに限定されるものではない。また、Boosting手法には他にもいろいろ提案されており、それらを使用して学習した弱判別器によって構成された検出器も本発明に含まれる。
【０１９２】
上述の実施形態では判別処理部２０３をハードウェアにより実現する場合について説明したが、ＤＳＰ（Digital Signal Processor）等でソフトウェアにより実現する場合にも適用可能である。その場合であっても、本発明を適用して最低限必要な継続段数を算出することが可能である。
【０１９３】
上述の実施形態では、本発明に関する学習方法を具備する装置内学習可能なパターン識別装置について説明したが、本発明の実施形態はこれに限るわけではない。例えば、弱判別器を決定するパラメータデータを外部のワークステーション等で学習して生成するパターン識別器生成システムとして適用可能なことは明らかである。さらには、パターン識別器生成プログラム（コンピュータプログラム）、およびコンピュータプログラムを記憶した記憶媒体も適用範囲である。
【０１９４】
なお、本発明の目的は、前述した実施形態の機能を実現するコンピュータプログラムを記録したコンピュータ可読の記憶媒体を、システムあるいは装置に供給することによっても、達成されることは言うまでもない。また、システムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたコンピュータプログラムを読出し実行することによっても、達成されることは言うまでもない。
【０１９５】
この場合、記憶媒体から読出されたコンピュータプログラム自体が前述した実施形態の機能を実現することになり、そのプログラムを記憶した記憶媒体は本発明を構成することになる。
【０１９６】
コンピュータプログラムを供給するための記憶媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、不揮発性のメモリカード、ＲＯＭなどを用いることができる。
【０１９７】
また、コンピュータが読出したコンピュータプログラムを実行することにより、前述した実施形態の機能が実現される。また、コンピュータプログラムの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した実施形態が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【０１９８】
【図１】本発明の好適な実施形態にかかるパターン識別器生成方法における学習処理を説明するフローチャートである。
【図２】本発明の好適な実施形態にかかるパターン識別器生成方法を実行する装置の構成例を示すブロック図である。
【図３】本発明の好適な実施形態にかかるパターン識別器生成方法で生成される分岐構造パターン識別器のノードの接続構造を説明する図である。
【図４】本発明の好適な実施形態にかかるパターン識別器の弱判別器ノードの詳細な構造を説明するブロック図である。
【図５】本発明の好適な実施形態にかかる分岐構造パターン識別器が対応する検出対象データの変動カテゴリの例を説明する図である。
【図６】本発明の好適な実施形態にかかる基本的な学習処理の詳細を説明するフローチャートである。
【図７】本発明の好適な実施形態にかかる識別器ノード内における処理の一例を説明するフローチャートである。
【図８】本発明の好適な実施形態にかかるパターン認識処理の一例である、顔検出処理を説明する図である。
【図９】複数の弱判別器で構成される従来のパターン識別器の構成例を示す図である。
【図１０】複数の弱判別器で構成される従来のパターン識別器における検出処理のフローチャートである。
【図１１】ＳＡＴの一例を説明する図である。
【図１２】ＳＡＴによる矩形領域の総和値の計算方法を説明する図である。
【図１３】フィルタ閾値の決定方法を説明する図である。
【図１４】打切り閾値の決定方法を説明する図である。
【図１５】本発明の好適な実施形態にかかるパターン識別器の分岐選択処理付きの検出処理の流れを示すフローチャートである。
【図１６】第１実施形態における分岐選択処理の詳細を説明するフローチャートである。
【図１７】本発明の好適な実施形態にかかるパターン識別器のパラメータメモリのメモリマップの一例を示す図である。
【図１８】第１実施形態における累積スコア評価による非分岐継続段数決定処理の詳細を説明するフローチャートである。
【図１９】第１実施形態における弱判別器各段毎の累積スコアの変化の様子の一例を示す図である。
【図２０】第２実施形態における選択誤り率評価による非分岐継続段数決定処理の詳細を説明するフローチャートである。
【図２１】第２実施形態における弱判別器各段毎の選択誤り率の変化の様子の一例を示す図である。
【図２２】第３実施形態における分岐選択判別器の一例を示す図である。
【図２３】第３実施形態における分岐選択処理の詳細を説明するフローチャートである。
【図２４】非顔データの打ち切り率の弱判別器各段毎の変化の様子の一例を示す図である。
【符号の説明】
【０１９９】
２０１  画像入力部
２０２  前処理部
２０３  判別処理部
２０４  ＤＭＡコントローラ
２０５  ＣＰＵバス
２０６  通信インターフェース
２０７  ユーザ・インターフェース
２０８  ＣＰＵ
２０９  ＲＯＭメモリ
２１０  RAMメモリ
２１１  大容量記憶部
【図１】
0004948379.tif 000011
【図２】
0004948379.tif 000012
【図３】
0004948379.tif 000013
【図４】
0004948379.tif 000014
【図５】
0004948379.tif 000015
【図６】
0004948379.tif 000016
【図７】
0004948379.tif 000017
【図８】
0004948379.tif 000018
【図９】
0004948379.tif 000019
【図１０】
0004948379.tif 000020
【図１１】
0004948379.tif 000021
【図１２】
0004948379.tif 000022
【図１３】
0004948379.tif 000023
【図１４】
0004948379.tif 000024
【図１５】
0004948379.tif 000025
【図１６】
0004948379.tif 000026
【図１７】
0004948379.tif 000027
【図１８】
0004948379.tif 000028
【図１９】
0004948379.tif 000029
【図２０】
0004948379.tif 000030
【図２１】
0004948379.tif 000031
【図２２】
0004948379.tif 000032
【図２３】
0004948379.tif 000033
【図２４】
0004948379.tif 000034