高速判別装置および高速判別装置を高速化する方法、並びに高速判別装置プログラム
【課題】複数の判別器からなる判別装置において、判別精度を犠牲にすることなく高速に判別が行なえる高速判別装置を提供する。
【解決手段】所定の順番に並べられた判別器群１２から最終結果を得る際に、評価値取得手段１３で１番目の判別器から順に各判別器の評価を行い、Ｉ番目までの判別器を評価して得られた総合評価値Ｆｉが示す判別結果が、Ｉ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、判別結果決定手段１４よりＩ＋１番目以降の判別器の評価の打ち切りを評価値取得手段１３に指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値に応じた判別結果を最終結果sign（ＦI）として決定する。
【解決手段】所定の順番に並べられた判別器群１２から最終結果を得る際に、評価値取得手段１３で１番目の判別器から順に各判別器の評価を行い、Ｉ番目までの判別器を評価して得られた総合評価値Ｆｉが示す判別結果が、Ｉ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、判別結果決定手段１４よりＩ＋１番目以降の判別器の評価の打ち切りを評価値取得手段１３に指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値に応じた判別結果を最終結果sign（ＦI）として決定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データに含まれるオブジェクトの判別に関し、特に複数の判別器を用いた判別の高速化に関するものである。
【背景技術】
【０００２】
ブースティングとは、必ずしも精度の良くない判別器を複数組み合わせることによって、精度の良い判別器を構築するアルゴリズムである。ブースティングによって学習された判別器は様々な分野で使われている（非特許文献１など）。
【０００３】
特に顔検知や顔認識技術などに使われており、デジタルカメラやビデオカメラの普及によって私たちの生活に身近なものとなっている。顔検出器は入力データとして、ある画像領域の輝度値を受け取り、画像領域に顔が有るかどうかを判別する判別装置である。顔検出の研究は、１９９０ 年代後半から行われていたが、計算速度の点で実用には至らなかった。しかしViolaとJonesによって提案された高速演算可能なHaar-Like特徴量（図２０参照）を使った弱判別器を用いた顔検出器により、実時間での顔検出の処理が可能になった。
【０００４】
顔検出にブースティングが使われる理由は判別装置の学習にかかる時間よりも実際に判別する際の判別時間が重要視されるからである。顔検出問題においてブースティングが速く判別を行える理由の一つは前述の高速演算可能な特徴量を導入した点にあるが、さらに、弱判別器の評価を途中で打ち切るという手法が用いられている点も高速に顔検出を行うポイントになっている。ブースティングで得られる判別装置は，弱判別器の線形結合であり、それらを逐次評価して最終的な判別結果を得る手法が一般的に用いられている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Yoav Freund and Robert E. Schapire “A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting” journal of computer and system sciences 55, 119_139 (1997)
【発明の概要】
【発明が解決しようとする課題】
【０００６】
通常、画像中に顔が存在する割合は少ないため、「顔でない」と判定する弱判別器も多い。「顔でない」と判定する弱判別器も多いと考えられる判別装置については、それらの評価を途中で打ち切れば、判別に要する時間を平均的に短縮することが可能である。特に、「顔でない」判定への寄与度の高い弱判別器を先に評価するようにすれば、より早い段階で打ち切ることができる。つまり、弱判別器の並び順が、判別速度を決める重要な要因になる。
【０００７】
従来、ブースティングなどによる弱判別器群の順序は、全ての弱判別器を用いることを前提に設計されているので、全体ではなく一部の弱判別器で判別すると精度が犠牲になり、判別の速度と精度を両立した総合性能を更に高めることは困難だった。
【０００８】
そこで、本発明では、複数の弱判別器群からなる判別装置において判別の精度を犠牲にすることなく高速に判別が行なえる高速判別装置および高速判別装置を高速化する方法、並びに高速判別装置プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の高速判別装置は、判別対象の対象データに所定のオブジェクトが含まれるか否かを判別した判別結果を得る高速判別装置であって、
前記対象データｘの入力を受け付ける対象データ入力受付手段と、所定の順番に並べられた、前記対象データｘに前記オブジェクトが含まれるか否かを評価する複数個の判別器ｆｊ（ｊ＝１〜Ｊ）からなる判別器群と、前記複数個の判別器のうちの１番目の判別器から順に各判別器を用いて前記対象データｘを評価した評価値ｆｊ（ｘ）を求め、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）（ｊ＝１〜ｉ）から得られた総合評価値Ｆｉ（ｘ）をｉ＝１からＪまで順に得る評価値取得手段と、前記評価値取得手段によってｉ＝Ｉ（Ｉ＜Ｊ）番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が示す前記判別結果が、Ｉ＋１番目以降の各判別器が取り得る評価値の範囲に基づいて、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩ（ｘ）にＩ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定する判別結果決定手段とを備えたことを特徴とするものである。
【００１０】
また、本発明のプログラムは、判別対象の対象データに所定のオブジェクトが含まれるか否かを判別した判別結果を得る高速判別装置のプログラムであって、
コンピュータを、前記対象データｘの入力を受け付ける対象データ入力受付手段と、所定の順番に並べられた、前記対象データｘに前記オブジェクトが含まれるか否かを評価する複数個の判別器ｆｊ（ｊ＝１〜Ｊ）からなる判別器群と、前記複数個の判別器のうちの１番目の判別器から順に各判別器を用いて前記対象データｘを評価した評価値ｆｊ（ｘ）を求め、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）（ｊ＝１〜ｉ）から得られた総合評価値Ｆｉ（ｘ）をｉ＝１からＪまで順に得る評価値取得手段と、前記評価値取得手段によってｉ＝Ｉ（Ｉ＜Ｊ）番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が示す前記判別結果が、Ｉ＋１番目以降の各判別器が取り得る評価値の範囲に基づいて、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩ（ｘ）にＩ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定する判別結果決定手段として機能させることを特徴とするものである。
【００１１】
「対象データ」とは、画像データ、音のデータ、文字データ、生体データ、自然・物理データなどをいい、画像データには、デジタルスチールカメラなどの撮影装置で撮影した画像や、ＣＴやＭＲＩなどの医療用撮影装置で撮影した画像などが含まれ、生体データには、心拍、脈拍、血圧、呼吸、発汗の波形や周期、振幅などを計測したデータが含まれ、自然・物理データには、天候、気候、地震の波形や周期、振幅などを計測したデータが含まれる。文字データは、文字（数字を含む）からなるデータをいう。
【００１２】
「オブジェクト」とは、対象データ中に含まれるものであり、例えば、デジタルスチールカメラなどの撮影装置によって対象データとなる画像に撮影された顔、頭部または人物の手などの人体の外観の一部の部位、あるいは人体の外観ではなく生体内の少なくとも一部の部位を含む領域が含まれる。なお、生体とは、生体内部の血管などのように、生体の内部に存在する特定の組織をいう。対象データが内視鏡システムや顕微鏡などで撮影した画像の場合には、オブジェクトには、生体内部の腫瘍組織、細胞、タンパク質、DNA・RNAなどの高分子、低分子が含まれる。生体の他にも、顕微鏡などで撮影された薬などの化合物やタンパク質などであってもよい。あるいは、貨幣、キャッシュカードなどのカード、車輌、あるいは車両のナンバープレートなど、デジタルスチールカメラなどの撮影装置によって対象データに撮影された画像であってもよい。また、対象データが、複写機などのスキャナ機器によりスキャニングされた画像である場合には、ドキュメントの文字、図面、表、写真などがオブジェクトに含まれる。さらに、オブジェクトは、画像データを統計的分析したときに統計的偏りのある群であればよく、例えば、テクスチャをも含むものである。
さらに、対象データが音のデータの場合には、「オブジェクト」は、例えば、音声、生体の音、生き物の声（動物、鳥、昆虫）、楽器の音、乗り物の音などである。
【００１３】
また、前記判別器群が、前記複数の判別器ｆｊとともに、該判別器のそれぞれに対する重みαｊとを記憶するものであり、
前記評価値取得手段が、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）と各判別器の重みαｊとを線形結合した総合評価値Ｆｉ（ｘ）
【数１】
をｉ＝１からＪまで順に得るものであってもよい。
【００１４】
また、前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩが条件１
【数２】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものが望ましい。
【００１５】
また、前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩが条件２
【数３】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであってもよい。
【００１６】
また、前記評価値取得手段が、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）を線形結合した総合評価値Ｆｉ（ｘ）
【数４】
をｉ＝１からＪまで順に得るものであってもよい。
【００１７】
また、前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件３−１または条件４−１
【数５】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものが望ましい。
【００１８】
また、前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件５−１または条件６−１
【数６】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであってもよい。
【００１９】
また、前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件３−２または条件４−２
【数７】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであってもよい。
【００２０】
また、前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件５−２または条件６−２
【数８】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであってもよい。
【００２１】
さらに、前記判別結果は、前記総合評価値Ｆｉ（ｘ）の符号に応じて決定されるものであってもよい。
【００２２】
また、前記判別器群が、Ｋ個のステージに分けられるとともに、各ステージ毎に所定の順番で並べられたJｋ（ｋ＝１〜Ｋ）個の判別器からなる判別器群が含まれるものである場合には、前記評価値取得手段が、前記各ステージ毎に１番目から順に前記総合評価値Ｆｉ（ｘ）を各ステージのｉ＝１からＪｋまで順に得るものであり、前記判別結果決定手段が、前記評価値取得手段によって、各ステージのｉ＝Ｉｋ（Ｉｋ＜Ｊｋ）番目までの判別器を評価して得られた前記総合評価値ＦｋI（ｘ）が示す前記判別結果が、各ステージに含まれるＩｋ＋１番目以降の各判別器が取り得る評価値の範囲に基づいて、前記Ｉｋ番目までの判別器を評価して得られた総合評価値ＦｋI（ｘ）にＩｋ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、前記評価値取得手段に各ステージのＩｋ＋１番目以降の判別器の評価の打ち切りを指示するとともに、前記Ｉｋ番目までの判別器を評価して得られた総合評価値ＦｋＩに応じた前記判別結果を各ステージの最終結果として決定するものが望ましい。
【００２３】
本発明の前記高速判別装置を高速化するための方法は、Ｎ個のサンプルデータを記憶するサンプルデータ記憶ステップと、前記所定の順番に並べられた複数の判別器からなる判別器群の２以上の判別器を交換して並び替えを行う判別器交換ステップと、該判別器交換ステップによる交換前と交換後の並び順の判別器群のそれぞれにおいて、前記Ｎ個のサンプルデータのそれぞれを前記対象データ入力受付手段より対象データｘとして受け付けて、前記評価値取得手段を実行した後に前記判別結果決定手段が前記判別器の評価の打ち切りを指示するまでに評価された判別器の数Ｉを各サンプルデータごとに取得し、前記Ｎ個のサンプルデータの前記評価された判別器の数の代表値を取得する評価済判別器数取得ステップと、前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より小さい場合には、前記判別器群の並び順を前記交換後の並び順に並び替えて前記判別器群に記憶し、前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より大きい場合には、前記判別器群に記憶されている前記判別器群の並び順をそのままとする並び替えステップと、前記判別器交換ステップ、前記評価済判別器数取得ステップ、および前記並び替えステップを繰り返して、前記評価された判別器の数の代表値が最小となる前記判別器群の並び順を探索する探索ステップと、を備えたことを特徴とするものである。
【００２４】
本発明の他の前記高速判別装置を高速化するための方法は、Ｎ個のサンプルデータを記憶するサンプルデータ記憶ステップと、前記各ステージ毎に所定の順番に並べられた複数の判別器からなる判別器群の２以上の判別器を交換して並び替えを行う判別器交換ステップと、該判別器交換ステップによる交換前と交換後の並び順の判別器群のそれぞれにおいて、前記Ｎ個のサンプルデータのそれぞれを前記対象データ入力受付手段より対象データｘとして受け付けて、前記評価値取得手段を実行した後に各ステージにおいて前記判別結果決定手段が前記判別器の評価の打ち切りを指示するまでに評価された判別器の数Ｉｋを各サンプルデータごとに取得し、前記Ｎ個のサンプルデータの前記評価された判別器の数の代表値を各ステージ毎に取得する評価済判別器数取得ステップと、前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より小さい場合には、前記各ステージの判別器群の並び順を前記交換後の並び順に並び替えて前記判別器群に記憶し、前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より大きい場合には、前記各ステージの判別器群に記憶されている前記判別器群の並び順をそのままとする並び替えステップと、前記判別器交換ステップ、前記評価済判別器数取得ステップ、および前記並び替えステップを繰り返して、前記評価された判別器の数の代表値が最小となる前記各ステージの判別器群の並び順を探索する探索ステップと、を備えたことを特徴とするものである。
【００２５】
また、前記高速判別装置を高速化するための方法において、前記判別器交換ステップが、前記所定の順番に並べられた複数の判別器からなる判別器群のうちの任意の２つの判別器を交換するようにし、前記探索ステップで、前記判別器交換ステップにおいて前記交換した２つの判別器の全ての組み合わせについて、前記評価済判別器数取得ステップ、および前記並び替えステップを繰り返して、前記評価された判別器の数の代表値が最小となる前記判別器群の並び順を探索することを特徴とするものが望ましい。
【００２６】
「代表値」とは、具体的には平均値、最頻値、中央値などをいう。
【００２７】
また、前記サンプルデータには、ラベル無学習データを含むものが好ましい。
【００２８】
さらに、前記判別器群は、所定の分布Ｐ１に従う学習データを用いて学習を行うことにより選択されたものであり、前記サンプルデータには、前記分布Ｐ１とは異なる分布Ｐ２の学習データを含むものが好ましい。
【００２９】
さらにまた、前記分布Ｐ２が前記対象データの分布に近い分布を表すものが望ましい。
【発明の効果】
【００３０】
本発明の高速判別装置によれば、所定の順番に並べられた判別器群から最終結果を得る際に、１番目の判別器から順に各判別器の評価を行い、Ｉ番目までの判別器を評価して得られた総合評価値が示す判別結果が、Ｉ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、Ｉ＋１番目以降の判別器の評価を打ち切って、Ｉ番目までの判別器を評価して得られた総合評価値に応じた判別結果を最終結果として決定しているので、判別器の精度を犠牲にすることなく高速に判別を行なうことが可能になる。
【００３１】
また、Ｉ番目までの判別器を評価して得られた総合評価値に上記の条件２，５−１，６−１，５−２，６−２のように、ある程度の許容誤差があってもＩ＋１番目以降の判別器の評価を打ち切るようにすることで、多少判別精度を犠牲にすることでより高速に判別することが可能になる。
【００３２】
また、判別器を複数のステージに分けたカスケード構造の高速判別装置においても、各ステージkにおいて、Ｉｋ番目までの判別器を評価して得られた総合評価値が示す判別結果が、Ｉｋ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、Ｉｋ＋１番目以降の判別器の評価を打ち切って、Ｉｋ番目までの判別器を評価して得られた総合評価値に応じた判別結果を各ステージの最終結果として決定するようにすれば、各ステージを高速化することができ、さらにカスケード構造による高速化を図ることが可能になる。
【００３３】
さらに、本発明の高速判別装置を高速化するための方法によれば、所定の順番に並べられた判別器群の並び替えを行いながら、Ｎ個のサンプルデータに対して、判別器の評価が打ち切られるまでに評価された判別器の数の平均値、最頻値、中央値などの代表値を求めて、もっとも早い段階で判別器の評価の打ち切りが行われる判別器群の並び順を探索するようにしているので、本発明の高速判別装置をさらに高速化することが可能になる。
【００３４】
また、カスケード構造の高速判別装置を高速化するための方法によれば、各ステージ毎に、もっとも早い段階で判別器の評価の打ち切りが行われる判別器群の並び順を探索するようにしているので、カスケード構造により早いステージで次の段階に進む画像であるか否かを判別した上で、さらに、各ステージの判別を高速化することができるので、本発明の高速判別装置をさらに高速化することが可能になる。
【００３５】
また、最適な判別器群の並び順を探索するには、全ての判別器群に対して並び替えを行うことで最適解を得られると考えられるが、実際に顔などの判別に用いられる判別器は千個を超える数になるため、全ての判別器群に対して並び替えを行うと計算量が膨大になる。そこで、本発明のように判別器群の中の任意の２つの判別器を交換するようにすれば計算量を減らすことができるとともに、全ての判別器群に対して並び替えを行なった場合に近い準最適解を得ることが可能になる。
【００３６】
さらに、最適な判別器群の並び順を探索する際のサンプルデータにラベル無学習データを含めることにより、サンプルデータのサイズを大きくすることが可能になり、多様なデータに対応した高速化が図れる。
【００３７】
さらに、ブースティングなどの学習によって判別器を選択する際に用いられる学習データと、この学習データとは異なる分布に従うサンプルデータを用いて判別器群の並び順を探索することにより、ブースティング学習などに用いられるラベル付き学習データとサンプルデータの分布の違いを考慮した並び順に弱判別器を並び替えて高速判別装置の高速化をさらに図ることが可能になる。
【００３８】
さらにまた、サンプルデータを実際の判別対象となる対象データに近い分布にすれば、対象データの分布を考慮した高速化を行なうことができる。
【図面の簡単な説明】
【００３９】
【図１】第１の実施形態に係る高速判別装置の構成を示したブロック図
【図２】第１の実施形態に係る高速判別装置の処理の流れを示すフローチャート
【図３】第２の実施形態に係る高速判別装置の構成を示したブロック図
【図４】第２の実施形態に係る高速判別装置の処理の流れを示すフローチャート
【図５】サンプルデータの特徴量の確率密度関数および真の条件付き分布の一例を示す図
【図６】アダブーストによって選ばれた弱判別器とその係数の関係を表す図
【図７】第３の実施の形態の順序構造学習の処理の流れを示すフローチャート
【図８】全解探索により順序構造学習を行なったときに評価された弱判別器の数の平均Γを示すグラフ
【図９】２つの弱判別器の交換により順序構造学習を行なったときに評価された弱判別器の数の平均Γを示すグラフ
【図１０】弱判別器の数を増やしたときの２つの弱判別器の交換により順序構造学習を行なったときに評価された弱判別器の数の平均Γを示すグラフ
【図１１】第４の実施形態に係る複数のステージからなる高速判別装置の構成を示したブロック図
【図１２】第５の実施の形態の順序構造学習の処理の流れを示すフローチャート
【図１３】ブースティング順の各ステージの平均評価回数と、SL(2)による順序構造学習後の各ステージの平均評価回数を示すグラフ
【図１４】ブースティング順と、SL(2)による順序構造学習後の各ステージで評価される弱判別器の割合を示すグラフ
【図１５】最初のステージに入力された探索窓の各ステージにおける棄却率を示すグラフ
【図１６】統合した正面顔検出器の平均評価回数を示すグラフ
【図１７】実験５の順序構造学習を行なったときに性能評価を示すグラフ
【図１８】実験６の順序構造学習を行なったときに性能評価を示すグラフ
【図１９】実験７の順序構造学習を行なったときに性能評価を示すグラフ
【図２０】Haar-Likeフィルタを示す図
【発明を実施するための形態】
【００４０】
以下、図面により、本発明の実施形態を詳細に説明する。本発明の高速判別装置は、デジタルカメラまたはデジタルビデオに搭載されるファームウェアに組み込まれた高速判別プログラムが実行されることにより、あるいは、高速判別プログラムがパソコンなどのコンピュータにロードされて実行されることにより実現する。また、高速判別プログラムはＣＤ−ＲＯＭなどの記憶媒体に記憶されて配布され、ＣＤ−ＲＯＭなどの記憶媒体からコンピュータにインストールされる。あるいは、インターネットなどのネットワークを介してプログラムが配布されて、コンピュータにインストールされる。あるいは、デジタルカメラまたはデジタルビデオの製造時にファームウェアに組み込まれる。
【００４１】
まず、図１および図２を用いて、本発明の第１の実施形態に係る高速判別装置を説明する。図１は、本発明の第１の実施形態に係る高速判別装置１の構成を示したブロック図である。図２は、高速判別装置１の処理の流れを示すフローチャートである。
【００４２】
図１に示すように、高速判別装置１は、対象データｘの入力を受け付ける対象データ入力受付手段１１と、Ｊ個の判別器ｆｊからなる判別器群を記憶する判別器記憶手段１２と、複数の判別器から総合評価値を得る評価値取得手段１３と、総合評価値から最終結果を決定する判別結果決定手段１４と、を備えている。本実施の形態では、ブースティングのアルゴリズムを用いて対象データの判別を行う場合について説明する。
【００４３】
判別器記憶手段１２は、ブースティングのアルゴリズムによって選別されたＪ個の判別器ｆｊ（判別器群）が所定の並び順で記憶されている。例えば、対象データが画像であり（以下、対象データを対象画像データとする）、対象画像データに顔が存在するかどうかを判別する場合には、判別器ｆｊとして、多数あるHaar-Likeフィルタの中から選択することができる（図２０、および、Pual.Viola,Michael J.Jones.Robust Real-Time Face Detection, International Journal ofComputer Vision,Vol.57,pp.137-154, 2004.などを参照）。以下、オブジェクトとして顔を検出する場合を例に説明する。
【００４４】
このＪ個の判別器ｆｊの少なくとも１つには、誤判別率が1/2 よりも小さい弱判別器を含むものとする（以下、判別器を弱判別器とし、判別器群を弱判別器を含む弱判別器群として説明する）。ブースティングのアルゴリズムは、Ｊ個の判別器ｆｊを線形結合することで強力な判別装置を構築するアルゴリズムであり、各弱判別ｆｊに対する重み（線形結合係数）αｊが決定されて弱判別器群と一緒に判別器記憶手段１２に記憶される。
【００４５】
ここで、Ｊ個の弱判別器ｆｊで構成する強力な判別装置を用いた判別方法について説明する。１番目〜Ｊ番目までの各弱判別器ｆｊを用いて対象画像データｘを評価したときの評価値はｆｊ（ｘ）とあらわす。このとき、Ｊ 個の弱判別器ｆｊの線形結合で構築されている判別関数Fは、
【数９】
と定義することができる。
【００４６】
最終的な判別装置ｇは、
【数１０】
とする。signは符号を表し、符号に応じて判別装置ｇの最終的な判定結果が決定される（ｇが正であれば顔が含まれる。ｇが負であれば顔が含まれない。）。
【００４７】
弱判別器による線形結合の方法はブースティングのアルゴリズムによって異なるが、ここでは、Adaboost によって学習された判別関数Ｆを例に以下説明する。
【００４８】
実際にデジタルカメラなどで撮影された撮影画像（対象画像）データ中に顔が存在するかどうかを判別するために用いられる弱判別器の数Ｊは、千個を超える数になる。実際には一枚の対象画像データから顔を検出する時間を30msec以下で終えるのが望ましく、常に全ての弱判別器で評価するのは実用的ではない。Adaboostでは重みαｊは判別誤差が小さくなるように決められる。そこで、Ｊ個の弱判別器をBoostingが求めた順または重みの大きい順などに並べておく。並べられた順に弱判別器を評価して途中で判別を打ち切り、少ない弱判別器を用いて高速に判別を行なうことが考えられるが、打切ると判別精度が落ちて問題になる。
【００４９】
判別精度を維持するためには、評価関数Ｆを計算する際に１番目からI（＜Ｊ） 番目までの弱判別器を評価したときに、評価していないＩ＋１番目以降の弱判別器を評価してもsign(Ｆ(ｘ)) の符号が変わらなければ、Ｉ＋１番目以降の弱判別器は評価を打ち切っても精度を犠牲にすることがない。以下に、この打ち切り法について詳細に説明する。
【００５０】
まず、対象画像データ入力受付手段１１で判別対象の対象画像データｘの入力を受け付ける（＃１）。対象画像データｘは、デジタルスチールカメラで撮影した画像データ、デジタルビデオで撮影した１フレームの画像データ、スキャナで読み込んだデジタルデータなどである。
【００５１】
評価値取得手段１３は、１番目の弱判別器ｆｊから順に対象画像データｘを評価した評価値ｆｊ（ｘ）を求める（＃２、＃３、＃７、＃８）。１番目からｉ番目までの弱判別器を用いて対象画像データｘを評価したときの総合評価値Ｆｉ（ｘ）は、１番目からｉ（＞１）番目までの弱判別器の評価値ｆｊ（ｘ）（ｊ＝１〜ｉ）と重みαｊを線形結合して求められる。総合評価値Ｆｉ（ｘ）はｉ＝１からＪまで順に算出する（＃４）。
【数１１】
【００５２】
次に、判別結果決定手段１４は、i＋１番目以降の弱判別器の重みの合計ｍｉを求める（＃５）。
【数１２】
【００５３】
また、未評価のｉ番目以降の弱判別器による評価値の総合評価値Ｆ’ｉは下の式から求められる。
【数１３】
【００５４】
全ての弱判別器を評価したときの総合評価値はＦｉ＋Ｆ’ｉであるが各弱判別器ｆｊは−１または１の値を取るので、Ｆ’ｉは−ｍｉから＋ｍｉの値（数式（４）参照）を取る。したがって、
【数１４】
を満足するＩ番目までの弱判別器で評価を打ち切っても、Ｉ＋１番目以降の弱判別器を評価しなくともsign（ＦI）の符号は、全ての弱判別器を評価したときのsign（Ｆ=ＦI＋Ｆ’I）と必ず一致する。
【００５５】
そこで、判別結果決定手段１４は、Ｉ番目の弱判別器までの総合評価値ＦＩ（ｘ）が条件１を満足する場合には（＃６-Yes）、評価値取得手段１３にＩ＋１番目以降の弱判別器の評価の打ち切りを指示する。また、Ｉ番目までの弱判別器を評価して得られた総合評価値ＦＩのsign（ＦI）の符号から最終結果を決定する（＃９、＃１０）。
【００５６】
条件１を満足するまで、上記の判定を繰り返し（＃３〜＃８）、打ち切りが行われなかった場合は、Ｊ個の全ての弱判別器から得られた総合評価値ＦJの符号sign（ＦJ）から最終結果を決定する（＃１１）。
【００５７】
上述では、判別結果決定手段１４でｍｉを算出する場合について説明したが、ｍｉの値は対象画像データｘに依らないため、判別を行う前に計算可能な値である。事前にｍｉが取りうる全ての値のルックアップテーブルを記憶しておくことにより、I 番目の弱判別器を評価した時点で判別を打ち切ることができる。このように途中で判別を打ち切ることからＪ−I 個の弱判別器を評価しない分高速に判別できる。
【００５８】
次に、弱判別器の打ち切り法の具体例を挙げる。
判別関数: Ｆ（ｘ）＝3 ｆ１（ｘ）＋1.5 ｆ２（ｘ）＋ｆ３（ｘ）＋0.5 ｆ４（ｘ）＋0.3ｆ５（ｘ）が与えられたとする。
（１） まず、一項目ｆ１(ｘ)＝1と評価されたとする。するとＦ１ (ｘ)＝3かつｍ１＝3.3である。この段階では残りの全ての弱判別器が−1 をとると符号が逆転するので打ちきれない。
（２） 二項目f２(ｘ)＝−1と評価されたとする。するとＦ２(ｘ)＝1.5かつｍ２＝1.8である。この段階でも残りの全ての弱判別器が−１をとると符号が逆転するので打ちきれない。
（３） 三項目f３(ｘ)＝1と評価されたとする。すなわちＦ３(ｘ)＝2.5かつｍ３ ＝0.8である。このとき数式（６）の条件１が満たされ、残りの弱判別器f４, f５ がいかなる値をとっても符号は逆転できずsign（Ｆ（ｘ））＝sign（Ｆ３（ｘ））＝１ である。
よってγ（ｘ, Ｆ）＝３で打ち切ることができる。
【００５９】
上記の条件１を満足するときに、弱判別器の評価を打ち切るようにすれば判別精度を犠牲にすることはないが、さらに高速に判別を行ないたい場合には、判別結果決定手段１４は、上記の条件１を満足する少し手前の弱判別器で評価を打ち切るようにしてもよい。この場合、判別結果決定手段１４は、総合評価値ＦＩが下記の条件２、
【数１５】
を満足する場合には、評価値取得手段１３にＩ＋１番目以降の弱判別器の評価の打ち切りを指示するようにし、Ｉ番目までの弱判別器を評価して得られた総合評価値ＦＩのsign（ＦI）の符号を最終結果として決定する。係数ｂは、多数のサンプルデータを実際に評価して、正答率が少なくとも1/2以上になるように決められる。好ましくは、正答率が要求を満足する％となるように係数ｂを決定する。
【００６０】
次に、第２の実施の形態について、図３および図４を用いて説明する。第２の実施の形態では拡張した弱判別器を用いた場合について説明する。図３は、本実施の形態に係る高速判別装置１の構成を示すブロック図である。また、図４に本実施の形態の高速判別装置１の処理の流れを示すフローチャートを示す。
【００６１】
図３に示すように、高速判別装置１ａは、対象データ入力受付手段１１と、判別器記憶手段１２ａと、評価値取得手段１３ａと、判別結果決定手段１４ａと、を備えている。本実施の形態の高速判別装置１ａは、第１の実施の形態と略同じ構成を備えるので、詳細な説明は省略して相違する点について説明する。
【００６２】
本実施の形態では、判別器記憶手段１２ａに記憶されている弱判別器ｆｊは、−１、１の２値ではなく適当な二値の実数αｊ、βｊをとる場合について説明する（本実施の形態のαｊは第１の実施の形態の重みαｊとは異なることに注意）。
【００６３】
このとき、判別関数Ｆは適当な閾値Ｔを用いて、
【数１６】
と定義することができる。
【００６４】
最終的な判別装置ｇは、
【数１７】
とする。signは符号を表し、第１の実施の形態と同様に、ｇの符号に応じて最終的な判別結果が決定される。
【００６５】
本実施の形態でも、Ｊ個の弱判別器はBoostingが求めた(判別誤差が小さい)順または重みの大きい順などに並べておく。まず、第１の実施の形態と同様に対象画像データ入力受付手段１１で判別対象の対象画像データｘの入力を受け付ける（＃１）。
【００６６】
次に、評価値取得手段１３ａは、第１の実施の形態と同様に、１番目の弱判別器ｆｊから順に対象画像データｘを評価した評価値ｆｊ（ｘ）を求め（＃２、＃３、＃７、＃８）、さらに、１番目からｉ番目までの弱判別器を用いて対象画像データｘを評価したときの総合評価値Ｆｉ（ｘ）を求める。総合評価値Ｆｉ（ｘ）はｉ＝１からＪまで順に算出する（＃１２）。
【数１８】
【００６７】
次に、判別結果決定手段１４ａは、ｉ＋１番目以降の弱判別器が取り得る値の範囲を求める（＃１３）。
【数１９】
【００６８】
そこで、Ｉ番目までの弱判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、下記の条件３−１または条件４−１、
【数２０】
のいずれかを満足すれば、Ｉ番目までの弱判別器で評価を打ち切っても、Ｉ＋１番目以降の弱判別器を評価しなくともsign（ＦI）の符号は、全ての弱判別器を評価したときのsign（Ｆ）と必ず一致する。つまり、条件３−１ が成り立てばsign（Ｆ（ｘ））＝１が保証される．同様に条件４−１ が成り立てばばsign（Ｆ（ｘ））＝-１ が保証される。
【００６９】
そこで、判別結果決定手段１４ａは、Ｉ番目の弱判別器までの総合評価値ＦＩ（ｘ）が条件３−１または４−１を満足する場合には（＃１４-Yes）、評価値取得手段１３ａ にＩ＋１番目以降の弱判別器の評価の打ち切りを指示する。また、Ｉ番目までの弱判別器を評価して得られた総合評価値ＦＩのsign（ＦI）の符号を最終結果として決定する（＃１０）。
【００７０】
条件１を満足するまで、上記の判定を繰り返し（＃３、＃１２、＃１３、＃１４、＃７、＃８）、打ち切りが行われなかった場合は、Ｊ個の全ての弱判別器から得られた総合評価値ＦJの符号sign（ＦJ）から最終結果を決定する（＃１１）。また、事前に各ＩについてｍＩ＋，ｍＩ―を計算してルックアップテーブルとして保存しておけば、I 番目の弱判別器を評価した時点で判別を打ち切ることができる。
【００７１】
次に、拡張した弱判別器を用いた場合の打ち切り法の具体例を挙げる。
まず、弱判別器の個数Ｊ＝５とし、弱判別器の取りうる値を下の表１に示す。
【表１】
【００７２】
閾値Ｔ＝０であるときに、対象画像データｘが与えられたときのＦ（ｘ）の符号を評価してみる。
（１） 一項目ｆ１（ｘ）＝2.0と評価されたとする。するとＦ１（ｘ）＝2.0，ｍ−1＝6.3となる。このときsign（Ｆ１（ｘ））×Ｆ１（ｘ）＝2.0 はｍ−1 より小さいためＦ（ｘ）の符号が負である可能性が残る．従って評価を打ち切ることはできない。
（２） 二項目f２（ｘ）＝1.5評価されたとする。するとＦ２（ｘ）＝3.5，ｍ−２＝3.8となる。このときsign（Ｆ２（ｘ））×Ｆ２（ｘ）＝3.5はｍ−２ より小さいため，Ｆ（ｘ） の符号が負である可能性が残る。従って評価を打ち切ることはできない。
（３） 三項目f３（ｘ）＝1.7と評価されたとする。するとＦ3（ｘ）＝5.4，ｍ−３＝3.6となる。このときsign(Ｆ３（ｘ）)×Ｆ３（ｘ）＝5.4＞ｍ−３であるため残りの弱判別器がどんな値を取っても総合評価値の値が負になることはない。従って残りの弱判別器を評価することなく判別を打ち切ることができる。
【００７３】
上記の条件３−１または条件４−１を満足するときに、弱判別器の評価を打ち切るようにすれば判別精度を犠牲にすることはないが、さらに高速に判別を行ないたい場合には、判別結果決定手段１４ａは、上記の条件３−１または条件４−１を満足する少し手前の弱判別器で評価を打ち切るようにしてもよい。この場合、判別結果決定手段１４ａは、前記総合評価値ＦＩが条件５−１または条件６−１、
【数２１】
のいずれかを満足すれば、評価値取得手段１３ａにＩ＋１番目以降の弱判別器の評価の打ち切りを指示する。判別結果決定手段１４ａは、Ｉ番目までの弱判別器を評価して得られた総合評価値ＦＩのsign（ＦI）の符号を最終結果として決定する。係数ｂは、多数のサンプルデータを実際に評価して、正答率が少なくとも1/2以上になるように決められる。好ましくは、正答率が要求を満足する％となるように係数ｂを決定する。
【００７４】
上述の第２の実施の形態では、判別結果決定手段１４ａが条件３−１または条件４−１が成り立つ場合にＩ番目までの弱判別器で評価を打ち切っていたが、下記の条件３−２または条件４−２が成り立つ場合にＩ番目までの弱判別器で評価を打ち切るようにしてもよい。
【数２２】
【００７５】
上記の条件３−２または条件４−２を満足するときに、さらに高速に判別を行ないたい場合には、判別結果決定手段１４ａは、上記の条件３−２または条件４−２を満足する少し手前の弱判別器で評価を打ち切るようにしてもよい。この場合、判別結果決定手段１４ａは、前記総合評価値ＦＩが条件５−２または条件６−２、
【数２３】
のいずれかを満足すれば、評価値取得手段１３ａにＩ＋１番目以降の弱判別器の評価の打ち切りを指示する。判別結果決定手段１４ａは、Ｉ番目までの弱判別器を評価して得られた総合評価値ＦＩのsign（ＦI）の符号を最終結果として決定する。係数ｂは、多数のサンプルデータを実際に評価して、正答率が少なくとも1/2以上になるように決められる。好ましくは、正答率が要求を満足する％となるように係数ｂを決定する。
【００７６】
第３の実施の形態では、高速判別装置を高速化するための方法について説明する。
【００７７】
従来、ブースティングによって選択された弱判別器群の順序は、全ての弱判別器を用いることを前提に設計されているので、全体ではなく一部の弱判別器で判別しつつも精度を犠牲にしないようにする場合には、どうしても高速化に限界があった。そこで、さらに判別を高速に行うために弱判別器の最適な並び順について検討する。このような高速判別のための最適な弱判別器の並び順を求めることを順序構造学習ということにする。
【００７８】
まず、サンプルデータ記憶ステップでＮ個のサンプルデータを用意する。ここで、各サンプルデータをｘｓ（ｓ＝１〜Ｎ）で表す。
【００７９】
上述の高速判別装置ではＪ個の弱判別器群ｆ１，ｆ２，・・・，ｆｊ，・・・，ｆＪ−１，ｆＪが重み順に並べられていたが、弱判別器群の中の２以上の弱判別器を置換した弱判別器群を多数作成して、いずれの並び順が最適であるかについて検討する。ある特定の置換によって得られた弱判別器群の並びをｋを用いて表すものとし、置換後の弱判別器の添え字をｋ（i）で表し、弱判別器はｆｋ（ｊ）と表す。また、ｋの並びの弱判別器群を用いたときの判別関数をＦｋ とする。ｋの並びを用いると与えられたＦｋ は下式 のように書ける（本実施の形態では、第１の実施の形態と同様に弱判別器ｆｊが１または−１の値をとり、判別関数Ｆが重みαｊを用いて線形結合される場合を例に説明する。）。
【数２４】
【００８０】
また、このときの打ち切り条件は下式のように書ける。
【数２５】
【００８１】
各並びｋの弱判別器群で構成される高速判別装置１を用いてサンプルデータｘｓ を評価した際に、高速判別装置１の判別結果決定手段１４で弱判別器の打ち切りが指示されるまでに評価値取得手段１３で評価された弱判別器の数Ｉをγとおく。
【数２６】
【００８２】
Ｎ個のサンプルデータｘｓ（ｓ＝１，２，・・・，Ｎ）のそれぞれについて、並び＾ｋの高速判別装置を用いてγを取得し、Ｎ個のサンプルデータのγの平均値Γ（Ｆ，ｋ）を取得する。
【数２７】
この評価された弱判別器の数の平均Γ（Ｆ，ｋ）が最小となる並び＾ｋを求める。
【００８３】
ところで上述の打ち切り法の性質を考えると、一見各弱判別器の係数の絶対値について降順で並べた順序が最適な並びになりそうに見える。なぜなら係数の絶対値が小さい弱判別器が後半に集まるため、評価値取得手段１３で評価した弱判別器の数が少なくても、ｍＩ は小さいので、早期に打ちきれる可能性が高まるからである。このことからわざわざ順序構造学習を行わなくても例えば以下の二つの並び順
ブースティング順＾ｋｂ ：ブースティングの学習時に選択された順序
係数絶対値順＾ｋｄ ：各弱判別器の係数（重みα）の絶対値が降順で並ぶ順序
はそもそも最適になっているのではないかと考えられる。
【００８４】
しかし、実際以下のような反例を作ることができる。まず、ここで、サンプルデータの特徴量をｘ（本実施の形態では、xは特徴量を表すものとして説明する）とし、その判別結果をｙ（真：ｙ＝１ 偽：ｙ＝−１）で表すものとする。特徴量ｘの周辺分布ｐ(ｘ)を、
【数２８】
とする。結果として各区間Ｒ１:＝[0, 1/3], Ｒ２:＝[1/3, 2/3], Ｒ３:＝[2/3, 1] に該当する特徴量ｘが発生する確率は、
【数２９】
となる。また真の条件付き分布ｐ(ｙ|ｘ) （ｙ＝１）を、
【数３０】
と定める。図５にｐ（ｘ）とｐ（１｜ｘ） を図示する。
【００８５】
今、同時分布ｐ（ｘ，ｙ）＝ｐ（ｘ）ｐ（ｙ｜ｘ）からｎ個のサンプルデータがＤ:＝{（ｘｉ， ｙｉ） | ｉ＝１，２，・ ・ ・，ｎ} で与えられたとする。
【００８６】
図５の左図はｘの確率密度関数ｐ（ｘ）を、右図はｐ（１｜ｘ）を表す。図の点線はｐ（１｜ｘ）＝1/2 を示している。
【００８７】
図６の左図はアダブーストによって得られた判別関数を表し、右表はＮ個のサンプルデータで実際にアダブーストを行ったとき、各ステップでアダブーストによって得られた弱判別器とその係数（重み）を表している。
【００８８】
ここで、３個の弱判別器ｆ１、ｆ２、ｆ３
【数３１】
を用いてアダブーストにより学習したとする。このときサンプルデータ数及びステップ数が十分に大きければアダブーストの判別関数は
【数３２】
になることがよく知られている（文献２：J. H. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: A statisticalview of boosting. The Annals of Statistics, 28:337-407, 2000.参照）。ただし、同じ弱判別器についての係数はまとめてある。実際、例えばｎ= 1000 でアダブーストの逐次学習を100 回行うと0.35 *ｆ１(ｘ) + 0.15 *ｆ２(ｘ) + 0.38ｆ３(ｘ) となった。以下では簡単のために上記のＦ(ｘ) をアダブーストによって得られた判別関数として進める。図６の右表からアダブーストによって選ばれた弱判別器の順序はｆ１, ｆ３, ｆ２ である。一方係数絶対値順はｆ３, ｆ１, ｆ２であることがわかる。今、ｆ１, ｆ２, ｆ３ の全ての並び順についてΓ(Ｆ) を計算すると表２のようになる。この表からブースティング順も係数絶対値順も最適な並びではないことがわかる。
【００８９】
下記の表２は 全ての順序ｋについてのΓ(Ｆ) の値を示す。表２では、順序「１２３」は弱判別器をＦ（ｘ）＝α１ｆ１（ｘ）＋α２ｆ２（ｘ）＋α３ｆ３（ｘ）と並べることを意味する。また６列目のΓ（Ｆ）は２，３，４ 列目を一つの６×３行列Ａとみなし、５列目を３次元縦ベクトルｂとみなしたとき，Ａｂと計算できることに注意。
【表２】
【００９０】
このような現象が起きる理由には以下の三つの事実が深く関連している。
（１） 最小のγ（ｘ，Ｆ） を達成する順序は場所ｘによって異なる。
（２） 最適な判別関数Ｆ（ｘ）はｐ（ｙ｜ｘ）のみから決まる。その一方最適順序構造はｐ(ｘ)にも依存する。
（３） ブースティング順は最終的な形Ｆ（ｘ）に最も早く近づけるように弱判別器を選択する。
【００９１】
まず（１）が正しいことは上記の例でも確認できる。区間Ｒ２では係数絶対値順ｆ３, ｆ１, ｆ２ では全ての弱判別器を評価しなければならないが、順序ｆ１, ｆ２, ｆ３では二回で打ちきれる。すなわち全ての場所で係数絶対値順＾ｋｄが必ずしもγ（ｘ, Ｆ）を最小にするわけではない。
【００９２】
係数絶対値順＾ｋｄが最適でないことは（１）と（２）からわかる。数式（２２）よりアダブーストの判別関数はｐ（ｙ｜ｘ） のみから決まることがわかる。また順序構造学習は定義よりｐ（ｘ） に依存することもわかる。従って（２） が成り立つ。今、（２） を認めるとｐ（ｘ）を変化させても＾ｋｄは不変である。しかしデータが区間Ｒ２に発生する確率が大きくなるほど、＾ｋｄはその区間でのΓ(Ｆ) が悪化する。実際上記の例ではＲ２の発生確率が一番高くなっているため、この区間で最短で打ちきれる＾ｋの方が、＾ｋｄよりΓ(Ｆ) を小さくできる。実際、上記のｐ（ｘ） はそれを満たすように作られている。ブースティング順＾ｋｂが最適でないことは（１）と（３）からわかる。事実（３）は文献２などにより早くから知られている。ブースティング順は図６のステップ１でｆ１を選んでいる。このあとｆ２を選べば上記の理由で最適な順序となる。しかし全体的にＦ(ｘ) の形により近づくためにはｆ３を選ぶ方が有利なためブースティングはｆ３を選んでいる。すなわちブースティングの目的は早くＦ(ｘ) に近づくことであり、打ち切り法を最短にすることとは無関係である。そのため一般には最適な順序と異なる。上記の例はその具体例となっている。
【００９３】
そこで、弱判別器群を並び替えた全ての弱判別器群の並び順に対して評価される弱判別器の数の平均値（以下、平均評価回数という）Γを求めることで、最適な並び＾ｋを求める。この全ての並び順に対して探索を行って最適な並び＾ｋを求めるのがよいが、Ｊ個の弱判別器全ての並び順はＪ！通り存在する。弱判別器の総数は千個以上に及ぶため、実際に探索を行なうのは不可能である。
【００９４】
そこで、効率よく弱判別器群の並び＾ｋを求める手法について検討する。
【００９５】
所定の並びで弱判別器が並んでいるときに、弱判別器群から適当な個数の弱判別器に限定してその中で順を交換したとき、Γが交換前より小さくなった場合には弱判別器を交換する。この操作をΓが小さくならなくなるまで繰り返すことによって弱判別器群の並び順の準最適解が得られると考えられる。
【００９６】
ここでは、弱判別器群から２個の弱判別器の順番を交換する場合について、図７のフローチャートに従って説明する。
【００９７】
まず、サンプルデータ記憶ステップでＮ個のサンプルデータを用意してハードディスクなどの記憶装置に記憶する（＃２０）。
【００９８】
次に、ブースティングで選ばれた弱判別器ｆｊの係数絶対値順＾ｋｂを＾ｋの初期値とする。また、このときのΓ（Ｆ，＾ｋ）をΓｍｉｎの初期値とする（＃２１）。
【００９９】
弱判別器交換ステップでは、所定の順番に並べられた複数の弱判別器からなる弱判別器群のうちの任意の２つの弱判別器を交換する。ここでｓ番目とｔ番目の弱判別器の交換という操作をσ２（ｓ，ｔ）とし、
σ2(s,t) ＝ {1,2,・・・,s,・・・,t,・・・,J｝-> {1,2,・・・,t,・・・,s,・・・,J}
と定義する。並び＾ｋの弱判別器群から選択したｓ番目とｔ番目の２つの弱判別器を交換して新しい並びσ2(s,t)＾ｋの弱判別器群を生成する（＃２２）。
【０１００】
次に、評価済弱判別器数取得ステップで、Ｎ個のサンプルデータのそれぞれを対象画像データ入力受付手段１１より対象画像データｘとして受け付けて、交換後の並びσ2(s,t)＾ｋにおけるΓ（Ｆ，σ2(s,t)＾ｋ）を求める（＃２３）。
【０１０１】
並び替えステップでは、交換後のΓ（Ｆ，σ2(s,t)＾ｋ）が交換前のΓｍｉｎより小さい場合には（＃２４−YES）、弱判別器群の並び順を交換後の並び順σ2(s,t)＾ｋに並び替えて弱判別器群を記憶する。さらに、Γ（Ｆ，σ2(s,t)＾ｋ）をΓｍｉｎとする（＃２５）。一方、交換後のΓ（Ｆ，σ2(s,t)＾ｋ）が交換前のΓｍｉｎより大きい場合には、弱判別器群の並び順はそのままにする（＃２４−NO）。
【０１０２】
探索ステップでは、次に交換するs’番目とt’番目の弱判別器を選択してs’をsとしt’をｔとして（＃２７）、以上の弱判別器交換ステップ、評価済弱判別器数取得ステップ、および、並び替えステップを繰り返して（＃２２〜＃２７）、評価された弱判別器の数の平均が最小となる弱判別器群の並び順を探索する。弱判別器交換ステップで行なわれる１〜Ｊの弱判別器の中の２つを交換する全ての組み合わせはＪＣ２となる。したがって、ＪＣ２ 回の交換が終わるまで（＃２６−YES）、弱判別器交換ステップ、評価済弱判別器数取得ステップ、および、並び替えステップを繰り返す（＃２６−NO）。
【０１０３】
上述では、弱判別器群のうちの２つの弱判別器を交換して行くことで、弱判別器群の準最適な並びを求めているが、弱判別器群のうちの３つ弱判別器を交換していくことで準最適な並びを求めることもできる。
【０１０４】
弱判別器交換ステップで弱判別器群の中の三つの弱判別器を選び、その三つの弱判別器について下の表３の５パターンの並び順の交換σ3 を行い、評価済弱判別器数取得ステップで平均評価回数Γを計算する。並び替えステップでは、５つの結果の中で、交換する前より平均評価回数Γが改善した中で、平均評価回数Γが最小となる並び順の交換を採用し、弱判別器群の並び順を更新する。探索ステップでは、以上の弱判別器交換ステップ、評価済弱判別器数取得ステップ、および、並び替えステップを繰り返して、評価された弱判別器の数の平均が最小となる弱判別器群の並び順を探索する。弱判別器の中の３つを交換する組み合わせによる弱判別器群の並び替えの交換回数はＪＣ３＊５になる。したがって、ＪＣ３＊５ 回の交換が終わるまで、弱判別器交換ステップ、評価済弱判別器数取得ステップ、および、並び替えステップを繰り返して準最適な並び順を探索する。
【表３】
【０１０５】
弱判別器群のうちの２つの弱判別器を交換して行く場合に比べて、弱判別器群のうちの３つの弱判別器を交換して行く場合のほうがより最適解に近い結果が得られると予測できる。しかし、弱判別器交換ステップ、評価済弱判別器数取得ステップ、および、並び替えステップの繰り返しは確実に増えることになり、弱判別器群のうちの２つの弱判別器を交換して行く場合より準最適解を得るための計算量は大きくなる。
【０１０６】
以下、実験結果に基づいて順序構造学習の効果について説明する。
【０１０７】
実験１では、弱判別器群の全ての並び替え（全解探索）による順序構造学習（以下、SL(1)による学習という）と、弱判別器群の中の２個の弱判別器の順番を交換する順序構造学習（以下、SL(2)による学習という）の効果について、実験した結果を説明する。
【０１０８】
計算量の観点から５〜１０個の弱判別器をSL(1)による順序構造学習とSL(2) による順序構造学習を行なった高速判別装置１による平均評価回数Γを下の表４に示す。また、図８にSL(1)により順序構造学習を行なったときの平均評価回数Γと、ブースティング順＾ｋｂや係数絶対値順＾ｋｄ（弱判別器の重みの順）のときの平均評価回数Γを示す。また、図９にSL(2)により順序構造学習を行なったときの平均評価回数Γと、ブースティング順＾ｋｂや係数絶対値順＾ｋｄのときの平均評価回数Γを示す。図８および図９にSL(1) やSL(2)により順序構造学習を行なったときの平均評価回数Γの方がブースティング順＾ｋｂや係数絶対値順＾ｋｄ（弱判別器の重みの順）のときの平均評価回数Γより小さく、高速評価できることがわかる。また、表４をみるとＪが小さい範囲ではSL(2)は、SL(1)のよい近似となっていることが確認できる。つまり、SL(2)による順序構造学習であってもSL(1)による順序構造学習に近い結果を得ることができるものと考えられる。
【表４】
【０１０９】
実験２では、弱判別器の数を増やしてSL(2)の学習を行った結果を図１０に示す。数が増えるに従って高速化の効果が表れていることがわかる。大体弱判別器の数Ｊ＝２０，・・・，５０ぐらいから評価される弱判別器の総数の１割ほど早くなる。この実験より準最適解でも他の並び順よりも一定して高速に判別できることがわかる。
【０１１０】
実験３では、弱判別器群から２個の弱判別器の順番を交換した順序構造学習と、弱判別器群から３個の弱判別器の順番を交換した順序構造学習（以下、SL(3)による学習という）の効果について、実験した結果を説明する。
【０１１１】
計算量の観点から２０〜３０個の弱判別器をSL(2)による順序構造学習とSL(3)による順序構造学習を行なった高速判別装置１による平均評価回数Γを下の表５に示す。
【表５】
二つの結果に大きな差はなく0.01〜0.1(Γ=J)の差でしかない。この実験よりSL(2)による順序構造学習でも十分な高速化を行なうことができると考えられる。
【０１１２】
以上より、順序構造学習にかかる計算量と、高速判別別装置で判別時間の削減との両方を考慮するとSL(2)による順序構造学習によって弱判別器の並び順を決定するのが最もよいという結論に達する。
【０１１３】
本実施の形態では、第１の実施の形態で説明したように、弱判別器ｆｊが−１、１の２値を取る場合を例に弱判別器の並び順を決定する手法について説明したが、第２の実施の形態で説明したように、弱判別器ｆｊが適当な二値の実数αｊ、βｊをとる場合には、評価済弱判別器数取得ステップで、＾ｋの並びの弱判別器群を用いたときのΓを求める際に、判別結果決定手段１４ａが条件３−１または条件４−１を満たすときに弱判別器の評価を打ち切るものとして求める。あるいは、並び順を決定する際に、評価済弱判別器数取得ステップで、＾ｋの並びの弱判別器群を用いたときのΓを求める際に、条件３−２または条件４−２を満たすときに弱判別器の評価を打ち切るものとして求めるようにしてもよい。
【０１１４】
本発明は、第３の実施の形態で説明したように、弱判別器群の最適な（あるいは準最適な）並び順を決定した後に、この決定された並び順の弱判別器群で構成された第１の実施の形態の高速判別装置、または、この決定された並び順の弱判別器群で構成された第２の実施の形態の高速判別装置で、判別対象の対象画像データに顔が含まれているか否かを判別することで、非常に高速な判別を行なうことを実現することができる。
【０１１５】
第１の実施の形態のように弱判別器ｆｊが−１，１の二値をとる場合には、上記に詳細に説明した手法を用いて最適な（あるいは準最適な）並び順を決定した後、決定された最適な（あるいは準最適な）並び順の弱判別器群で構成された高速判別装置１で判別を行なうことによって最も高速な判別を行なうことが可能になる。
【０１１６】
一方、第２の実施の形態のように弱判別器ｆｊが適当な二値の実数αｊ、βｊをとる場合には、条件３−１または条件４−１を満足した場合に、弱判別器の評価を打ち切るケースと、条件３−２または条件４−２を満足した場合に、弱判別器の評価を打ち切るケースとがある。そこで、第２の実施の形態のように弱判別器ｆｊが適当な二値の実数αｊ、βｊをとる場合には、以下の４通りの組み合わせが考えられる。
（１）最適な（あるいは準最適な）並び順を決定するには、条件３−１または条件４−１を満たすときに弱判別器の評価を打ち切るという条件のもとで決定し、この決定された最適な（あるいは準最適な）並び順の弱判別器群で構成された高速判別装置１ａでも、条件３−１または条件４−１を満たすときに弱判別器の評価を打ち切るようにする。
（２）最適な（あるいは準最適な）並び順を決定するには、条件３−１または条件４−１を満たすときに弱判別器の評価を打ち切るという条件のもとで決定し、この決定された最適な（あるいは準最適な）並び順の弱判別器群で構成された高速判別装置１aでも、条件３−２または条件４−２を満たすときに弱判別器の評価を打ち切るようにする。
（３）最適な（あるいは準最適な）並び順を決定するには、条件３−２または条件４−２を満たすときに弱判別器の評価を打ち切るという条件のもとで決定し、この決定された最適な（あるいは準最適な）並び順の弱判別器群で構成された高速判別装置１aでも、条件３−１または条件４−１を満たすときに弱判別器の評価を打ち切るようにする。
（４）最適な（あるいは準最適な）並び順を決定するには、条件３−２または条件４−２を満たすときに弱判別器の評価を打ち切るという条件のもとで決定し、この決定された最適な（あるいは準最適な）並び順の弱判別器群で構成された高速判別装置１aでも、条件３−２または条件４−２を満たすときに弱判別器の評価を打ち切るようにする。
【０１１７】
以上の４通りから、最も高速に判別を行なうことができる高速判別装置を決定することが可能である。上記の各条件において、条件３−１，４−１の方が、条件３−２，４−２より処理がシンプルであるため処理自体は高速であるが、打ち切り回数の性能差が小さいことが実験において確認されている。実験の結果などから、適宜最適な条件の組み合わせを決定するのが良い。
【０１１８】
第４の実施の形態では、高速判別装置の弱判別器群をカスケード型に構成した場合について説明する。図１１は、本実施の形態に係る高速判別装置１ｂの構成を示すブロック図である。高速判別装置１ｂは、対象データ入力受付手段１１と、判別器記憶手段１２ｂと、評価値取得手段１３ｂと、判別結果決定手段１４ｂと、を備えている。本実施の形態の高速判別装置は、弱判別器群が複数のステージに分けられてカスケード型で構成される以外は、第１および２の実施の形態と略同じ構成を備えるので、詳細な説明は省略して相違する点を主に説明する。
【０１１９】
判別器記憶手段１２ｂには、Ｊ個の弱判別器がＫ個のステージに分けて記憶され、各ステージにはＪｋ（ｋ＝１〜Ｋ）個の弱判別器が所定の順番で並べられている。
ここで、ｋ番目のステージの判別関数をＦｋと定義する。Ｆｋ は、
【数３３】
と表わされる。
【０１２０】
各ステージの最終的な判別装置ｇｋは、
【数３４】
で表される。
【０１２１】
次に評価値取得手段１３ｂは、各ステージ毎に総合評価値Ｆｋｉ（ｘ）をｉ＝１からＪｋまで順に算出する。
【数３５】
【０１２２】
次に判別結果決定手段１４ｂは、各ステージ毎にｉ＋１番目以降の弱判別器が取り得る値の範囲を求める（＃１３）。
【数３６】
【０１２３】
そこで、Ｉｋ番目までの弱判別器を評価して得られた前記総合評価値ＦＩｋ（ｘ）が、下記の条件７または条件８
【数３７】
のいずれかを満足すれば、各ステージではＩｋ番目までの弱判別器で評価を打ち切る。
【０１２４】
ここでは、弱判別器が適当な二値の実数をとる場合について説明したが、第１の実施の形態と同様に、弱判別器が１、−１の２値を取る場合であっても、同様に各ステージごとに弱判別器で評価の打ち切りを行うようにすることができる。
【０１２５】
第５の実施の形態では、高速判別装置の複数の弱判別器をカスケード型に構成した場合の最適な弱判別器の並び順を求める順序構造学習について説明する。このカスケード型（カスケード構造）の高速判別装置は、弱判別器がステージと呼ばれるいくつかのグループにまとめられている。実際に検出を行う際には第１ステージから順に評価を行い、顔でないと評価されたステージがあれば、その画像は顔でないと判定し，そのステージで評価を打ち切り、次のステージに進まない。従って、全ステージで顔であると判定されたときに限りその画像を顔であると判定する。ここでは、各ステージを一つのブースティングによって得られた高速判別装置とみなして順序構造学習を行う場合について説明する。
図１２は、カスケード型の高速判別装置の順序構造学習の処理の流れを示すフローチャートである。各ステージ毎に並び替えを行なう以外は、第３の実施の形態の順序構造学習の処理の流れと略同様であるので、図１２に従って相違する点を主に説明する。
【０１２６】
まず、各ステージ毎に所定の順番に並べられた弱判別器群に対して上述のSL(1)、SL(2),SL(3)のいずれかの手法で並び替えを行なえばよいが、ここでは、SL(2)で並び替える場合について説明する。
【０１２７】
まず、Ｎ個のサンプルデータを用意して記憶装置に記憶する（＃３０）。ステージkをステージ１とし、ステージ１から弱判別器群の並び順を探索する（＃３１）。
【０１２８】
ブースティングで選ばれた弱判別器ｆｊの係数絶対値順＾ｋｂを各ステージの並び＾ｋの初期値とする。また、このときのΓk（Ｆ，＾ｋ）をΓkｍｉｎの初期値とする（＃３２）。
【０１２９】
次に、弱判別器交換ステップで、現在のステージの弱判別器群のうちのs番目とt番目の２つの弱判別器を交換する（＃３３）。次に、評価済弱判別器数取得ステップで、Ｎ個のサンプルデータのそれぞれを対象画像データ入力受付手段１１より対象画像データｘとして受け付けて、評価値取得手段１３ｂを実行した後に各ステージにおいて判別結果決定手段１４ｂが弱判別器の評価の打ち切りを指示するまでに評価された弱判別器の数Ｉｋを各サンプルデータごとに取得し、Ｎ個のサンプルデータから平均評価回数Γｋを取得する（＃３４）。
【０１３０】
並び替えステップでは、交換後の平均評価回数Γｋが交換前の平均評価回数Γｋｍｉｎより小さい場合には（＃３５―YES）、現在のステージの弱判別器群の並び順を交換後の並び順に並び替える（＃３６）。交換後の平均評価回数Γｋが交換前の平均評価回数Γｋｍｉｎより大きい場合には、現在のステージの弱判別器群の並び順はそのままにする（＃３５―NO）。
【０１３１】
次に交換するs’番目とt’番目の弱判別器を選ぶ（＃３８）。探索ステップでは、全ての並び替えが終了するまで、再度、弱判別器交換ステップ、評価済弱判別器数取得ステップ、および並び替えステップを繰り返して（＃３７−NO）、平均評価回数Γｋが最小になる現在のステージの弱判別器群の並び順を探索する。全ての並び替えが終了すると次のステージの並び替えに移る（＃３７−YES）。
【０１３２】
まず、現在のステージｋが最後のステージＫではないかを確認して、最後のステージでない場合には（＃３９―NO）、次のステージｋ＋１に進めて（＃４０）、再度、次のステージの弱判別器群の並び順を探索する（＃３３〜＃３８）。
【０１３３】
全てのステージで、平均評価回数Γｋが最小になる弱判別器群の並び順の探索が終了すると順序構造学習は完了する（＃３９―YES）。
【０１３４】
実験４では、カスケード構造の正面顔検出器（高速判別装置）に順序構造学習を行った。表６に各ステージに含まれる弱判別器の数の一覧を示す。
【表６】
【０１３５】
弱判別器の総数が大きいため、順序構造学習はSL(2)を採用した。図１３に、各ステージの弱判別器の数と、ブースティング順＾ｋｂの各ステージの平均評価回数Γｋと、SL(2)による順序構造学習後の各ステージの平均評価回数Γｋを示す。図１４に、ブースティング順＾ｋｂと、SL(2)による順序構造学習後の各ステージで評価される弱判別器の割合（平均評価回数Γｋ／弱判別器の数Ｊ）を示す。各ステージごとに順序構造学習の効果がみられ、どのステージでも順序構造学習によって得られた並び順の方がブースティング順＾ｋｂより、平均評価回数Γｋが小さく速く検出することができている。また最後のステージになるにつれて順序構造学習の効果が大きくなり，平均評価回数で最大で1.5割ほど高速化が図れていることが分かる。
【０１３６】
次に、顔検出時に対象画像データ内に顔検出範囲（以下、探索窓という）を設定して、その探索窓内に顔が存在するか判定しながら、対象画像データ全体を走査することで対象画像データ内の顔を検索する場合の各ステージの棄却率（探索窓内に顔が存在しないと判定されて、その探索窓が棄却される率）について説明する。カスケード型の判別器は、最初のステージから順に評価を行い、顔でないと評価されたステージがあれば、探索窓は棄却される。設定された探索窓が各ステージでどの程度棄却されるかを表す棄却率を図１５に示す。図１５よりステージ5，6までに設定された探索窓の9割が棄却されている。つまり、前半のステージでは多くの探索窓を棄却し、後半のステージでは精密に顔であるかどうか検査していることを示している。
【０１３７】
次に、カスケード構造の正面画像検出器と順序構造学習の検出速度の高速化の効果についてみる。表６に示すカスケード構造のステージ0からステージ6までのステージを統合しステージ0とし、ステージ7…24まではそのままにするが、ステージの番号を振りなおしてステージ1…18とする。この各ステージに対して順序構造学習を行い、統合した正面顔検出器の平均評価回数Γｋを図１６に示す。ステージ0を見ると順序構造学習を行った場合の平均評価回数Γ０は180程度だが、順序構造学習を行わない場合と比べて40程度しか変わっていない。統合する前は9個の弱判別器で構成されたステージ0で40%ほど探索窓を棄却している。従って検出速度の高速化の観点からみると、複数のステージを統合した顔検出器に対して順序構造学習を行う場合より、カスケード構造の方が速いことがわかる。以上より、カスケード構造を採用した上で各ステージに対して順序構造学習を行なった高速判別装置が最も高速に判別を行えるという結論に達する。
【０１３８】
上述の第３および第５の実施の形態の順序構造学習では、Ｎ個のサンプルデータを使って、判別器の評価が打ち切られるまでに評価された判別器の数の平均値を求めて、もっとも早い段階で判別器の評価の打ち切りが行われる判別器群の並び順を探索するようにしたが、平均値ではなく最頻値、中央値などの代表値からもっとも早い段階で判別器の評価の打ち切り行なわれる判別器群の並び順を探索するようにしてもよい。
【０１３９】
次に、第６の実施の形態では、ブースティング学習時と順序構造学習時に用いる学習データ、および性能評価に用いる評価用データについて説明する。本実施の形態の高速判別装置は、第１、第２および第４の実施の形態で説明した高速判別装置のいずれかを用いる。また、順序構造学習は第３および第５の実施の形態で説明した高速判別装置を高速化する方法を用いるものとする。高速判別装置は前述の実施の形態と同じ構成を備え、高速判別装置を高速化する方法でも前述と同じ順番で各ステップが実施されるので、本実施の形態では学習データと評価用データについて詳細に説明する。
【０１４０】
一般的に、学習データセットとして、ラベル付き学習データとラベル無し学習データが用いられることはよく知られている。例えば、顔検出に用いる学習用データの場合、特徴量ｘは機械で自動で大量収集可能であるのに対して、各学習データのラベルｙ（顔有り：１、顔無し：−１）は人手でつけなければならない。そのためラベル付き学習データセットＤＬのサイズを大きくするにはコストがかかると考えられる。一方で特徴量ｘだけの学習データ（ラベル無し学習データ）は大量に手に入れやすい。
【０１４１】
ところで、デジタルカメラで顔検出を実際に行う場合の対象画像データに近い評価データＤＴと、学習に用いられるラベル付き学習データセットＤＬでは、特徴量の分布が異なると考えられる。通常、顔検出のための学習を行う場合には顔画像を多く含む学習データを準備するのが自然であろうが、実際のデジタルカメラで撮影した対象画像データにはそこまで多く常に顔が写っているとは限らないからである。
【０１４２】
そこで、学習データの３つのタイプについて説明する。
（ａ）教師付き学習用データセット
ラベル付き学習データＤＬのみが与えられる。従来から広く用いられてきた設定である。本発明のブースティング学習時に用いられ、弱判別器の選択が行われる。しかし上述したようにデータサイズを大きくするためにはラベルづけのコストがかかる。
（ｂ）半教師付き学習データセット
ラベル付き学習データＤＬとラベル無し学習データＤＵが与えられる。ただし、ＤＵとＤＬが同じ分布に従っている。
（ｃ）共変量シフト学習データセット
ラベル付き学習データＤＬとラベル無し学習データＤＵが与えられる。ただし、ＤＵとＤＬが異なる分布に従っている。
【０１４３】
順序構造学習にはデータの数を増やすため、ラベル付き学習データＤＬとラベル無し学習データＤＵが含まれる半教師付き学習データセット、あるいは共変量シフト学習データセットを使う方法が考えられる。
【０１４４】
ここで、従来の判別装置と上述の各実施の形態で説明した高速判別装置の判別速度について検討する。まず、判別装置を下の４通りに分ける。
(ｉ) viola and jonesらが提案した従来の判別装置（例えば、文献３：Pual.Viola,Michael J.Jones.Rapid Object Detection using a Boosted Cascade of Simple Feature, IEEE Conf. on Computer Vision and Pattern Recognition, 2001.V参照）
(ii) 係数絶対値順に弱判別器を並べて、弱判別器の数γ（第１、第２および第４の実施の形態のＩ、Ｉｋ）で打ち切る高速判別装置（第１、第２および第４の実施の形態の高速判別装置）
(iii) ブースティング順に弱判別器を並べて、弱判別器の数γで打ち切る高速判別装置（第１、第２、および第４の実施の形態の高速判別装置）
(iv)さらに、弱判別器の並び順に対して順序構造学習を行なって、弱判別器の数γで打ち切る高速判別装置（第３および第５の実施の形態の方法によって高速化された高速判別装置）
(ｉ)の従来の判別装置に対しては、(ii)、(iii) 、(iv)の高速判別装置はどんな場合でも必ず同じかそれ以上の判別速度を出すことができる。また、(iv)が一番高速であると考えられるが、順序構造学習をしなくても(ii)、(iii)でも一定程度の高速化が実現可能である。ただし、これは学習データと評価データの分布が同じ場合が前提となる。
【０１４５】
顔検出において学習データと評価データが異なる分布に従うことは不可避である（例えば、文献３参照）。(ｉ)の従来の判別装置においても、顔ではなさそうなものを判断する処理が少ない弱判別器を初段側のステージに用意して初期に顔でないデータは棄却するように構成にしたカスケード構造の判別装置では、学習データと評価データの分布が違うことを想定してカスケード構造を決定している。これは、経験則によるヒューリスティックなものである。
【０１４６】
(ii)、(iii)の係数絶対値順は、弱判別器が十分多様であれば、アダブーストの判別関数は学習データｘの分布Ｐ(ｘ)には依存しないが、高速判別装置が弱判別器の途中で判別を打ち切るときの弱判別器の数γは教師付き学習データセット（ラベル付き学習データ）ｘの分布Ｐ(ｘ)に依存する。そのため、係数絶対値順は最適な並び順とはならない。アダブースト順が最適にならない理由も同様に、アダブーストが教師付き学習データセットを最も改善する弱判別器を選ぶため、高速判別装置が弱判別器の途中で判別を打ち切るときの最適な並び順とはならない。
【０１４７】
それに対して、(iv)の順序構造学習を評価データ（実際にデジタルカメラなどで顔の判別を行なう対象画像データに近い分布のデータ）と同じ分布に従うラベル無し学習データで学習を行うことができれば、(i)〜(iii)をかなり上回る性能が期待できる。
【０１４８】
まず、分布Ｐ１(x)のラベル付き学習データセットＤＬ:= {(ｘｉ, ｙｉ) | ｉ＝1, 2, ・ ・ ・ , n}と、ラベル付き学習データセットＤＬとは独立なラベル無し学習データセットとして分布Ｐ１(x) に従うＤ１Ｕ:= {ｘ１, ｘ２, ・・・, ｘｎｕ} と分布Ｐ２(x) に従うＤ２Ｕ:= {ｘ１, ｘ２, ・・・, ｘｎｕ} を用意する。さらにＤＬ, Ｄ１Ｕ, Ｄ２Ｕと独立な評価用データセットとして分布Ｐ１(x)に従うＤ１T:= {ｘ１, ｘ２, ・・・, ｘｎｔ } と、分布Ｐ２(x)に従うＤ２T:= {ｘ１, ｘ２, ・・・, ｘｎｔ} を用意する。学習データの分布Ｐ１(x)と分布Ｐ２(x)は異なる分布を表し、Ｐ１(x)はブースティング学習に用いられるデータの分布と略一致する分布を表し、Ｐ２(x)は、実際に顔の判別を行なう対象画像データの分布と略一致する分布を表すものとする。この実験ではｎ＝300, ｎｕ＝300, ｎｔ＝1200 とした。
【０１４９】
最初にデータＤＬを用いてブースティング学習を行う。その結果得られた判別関数を
【数３８】
とする（ここでは、第１の実施の形態と同じ判別関数を例に説明する）。以降全ての実験において同じ判別関数を用いるものとする。この判別関数Ｆ（ｘ）について下表に示した４種類の実験（表の実験２は、第３の実施の形態の実験２と同じである）を行った。これらの実験の意図は下で説明する。性能評価は評価用データセットＤ１T あるいはＤ２T を用いて計算されたΓ(F)/Ｊで行った。ＤｘＬはＤＬの特徴量だけの集合をさす。以下、ブースティング学習に用いるデータを学習データセットといい、順序構造学習に用いるデータをサンプルデータセットとして区別する。
【表７】
上表の実験ではいずれも順序構造学習にSL(2)を用いる。
【０１５０】
実験２では、順序構造学習に学習データセットと同じデータをサンプルデータセットＤｘＬとして用い、評価用には学習データセットと同じ分布の評価用データＤ１Tを用いた。実験２の結果を図１０に示す。数が増えるに従って高速化の効果が表れていることがわかる。大体弱判別器の数Ｊ＝２０，・・・，５０ぐらいから評価される弱判別器の総数の１割ほど早くなる。
【０１５１】
実験５では、順序構造学習に学習データセットと同じデータをサンプルデータセットＤｘＬとして用い、評価用には学習データセットと異なる分布の評価用データセットＤ２Tを用いた。実験５の結果を図１７に示す。
実験２，５はともにブースティング順は係数絶対値順に似た挙動を示している。また両者は実験２，５であまり結果が変わらないことがわかる。その一方で順序構造学習は実験２に比べて実験５では、弱判別器の数が増えると結果が安定していない。これは学習時と評価時でデータの分布が変わっている影響が出ているためであると考えられる。
【０１５２】
実験６では、順序構造学習に学習データセットと同じデータのサンプルデータセットＤｘＬと学習データセットと同じ分布であるが学習データとは独立なサンプルデータセットＤ１Ｕを用い、評価用には学習データセットと同じ分布であるが学習データとは独立な評価用データセットＤ１Tを用いた。実験６の結果を図１８に示す。
順序構造学習を行うと、データ数が増えているため早期から安定して高速化できている。ただし実験２と同様に、学習データセットとサンプルデータセットが同じ分布に従い、学習データセット・サンプルデータセットと同じ分布の評価用データセットＤ１Tを用いるため、弱判別器の数が増えても改良の度合いが増加していない。
【０１５３】
実験７は、順序構造学習に学習データセットと異なる分布のサンプルデータセットＤ２Ｕを用い、評価用にも学習データセットと異なる分布の評価用データセットＤ２Tを用いる。実験７の結果を図１９に示す。
順序構造学習による高速化が著しいことが見て取れる。この理由は共変量シフトを起こしている場合、係数絶対値順やブースティング順が重要であると考えた判別装置の優先順位が予想を外すこととなる。ただしブースティングの学習アルゴリズムを共変量シフトに拡張すればここまで差が生じることはないと考えられる。
【０１５４】
ブースティング学習においては、ラベル付きの学習データしか学習できない。そのためブースティング学習に用いる学習データセットのサイズを大きくするにはコストがかかる。順序構造学習においては、順序構造を学習(弱判別器の順序のみに着目)しているので、学習データのラベルは必須ではなくなり、ラベル付き、ラベル無のどちらでも高速化のための学習が可能となる。そのため、順序構造学習に用いる学習データセットのサイズを大きくするのは比較的容易に行なえる。
【０１５５】
デジタルカメラで顔検出を実際に行う場合の対象画像データと、ブースティング学習に用いられるラベル付き学習データとでは、特徴量の分布が異なると考えられる。そこで、順序構造学習でブースティングを行なう際の学習データとは異なる分布のサンプルデータ、つまり実際に判別を行う対象画像データに近い分布のサンプルデータを用いることで、その違いを考慮した並び順に弱判別器を並び替えて高速判別装置の高速化を図ることが可能になる。
具体的には、上記実施形態で説明したように、ラベル無しの半教師付き学習や、共変量シフトの分布特性を持つサンプルデータを順序構造学習に適用することで、更に、係数絶対値順、アダブースト順より高速となるように高速判別装置の弱判別器を並び替えることが可能になる。
【０１５６】
本実施の形態では、弱判別器が−１、１の２値を取る場合について説明をしたが、第２の実施の形態のように２値の実数を取る場合についても、ラベル無しの半教師付き学習や、共変量シフトの分布特性を持つサンプルデータを順序構造学習に適用することで、より高速となるように高速判別装置の弱判別器を並び替えることが可能になる。
【０１５７】
上述では、顔の検出について具体的に説明を行なったが、オブジェクトが人物の手などの人体の外観の一部の部位、あるいは人体の外観ではなく生体内の少なくとも一部の部位を含む領域であってもよい。対象画像データが内視鏡システムや顕微鏡などで撮影した画像の場合には、オブジェクトは、生体内部の腫瘍組織、細胞、タンパク質、DNA・RNAなどの高分子、低分子、であってもよい。生体の他にも、顕微鏡などで撮影された薬などの化合物やタンパク質などであってもよい。あるいは、デジタルスチールカメラなどの撮影装置によって対象画像データに撮影された貨幣、キャッシュカードなどのカード、車輌、あるいは車両のナンバープレートなどであってもよい。また、対象画像データが、複写機などのスキャナ機器によりスキャニングされた画像である場合には、オブジェクトがドキュメントの文字、図面、表、写真などであてもよい。さらに、オブジェクトは、画像データを統計的分析したときに統計的偏りのある群であればよく、例えば、テクスチャであってもよい。
【０１５８】
上述では、対象データが画像データである場合について説明したが、音のデータ、文字データ、生体データ、自然・物理データなどでもよい。具体的には、音のデータから音声、生体の音、生き物の声（動物、鳥、昆虫）、楽器の音、乗り物の音などを検索するときに上述の高速判別装置を用いることができる。
また、音声データや文字データには、日本語や英語などの種々の言語の情報からなる言語データが含まれる。言語データからは、例えば、地域の方言の判別、用途（ニュースのようなフォーマルなデータであるかインフォーマルなデータであるか）の判別、書かれた（あるいは、話された）時代（平安、江戸、現代）の判別、書いた（あるいは、話している）世代（高校生、年輩）の判別をおこなうときに上述の高速判別装置を用いることができる。
さらに、生体データは、心拍、脈拍、血圧、呼吸、発汗の波形や周期、振幅などを計測したデータであってもよい。さらにまた、自然・物理データとして、天候、気候、地震の波形や周期、振幅などを計測したデータであってもよい。
【０１５９】
上述では、判別器が弱判別器である場合について説明したが、判別器群には誤判別率が低いものが含まれていても良い。
【０１６０】
上述では、ブースティングを例に説明したが、バギングにより構成された判別器群であってもよい。
【符号の説明】
【０１６１】
１，１ａ，１ｂ 高速判別装置
１１ 対象画像データ入力受付手段
１２，１２ａ，１２ｂ 判別器記憶手段
１３，１３ａ，１３ｂ 評価値取得手段
１４，１４ａ，１４ｂ 判別結果決定手段
【技術分野】
【０００１】
本発明は、画像データに含まれるオブジェクトの判別に関し、特に複数の判別器を用いた判別の高速化に関するものである。
【背景技術】
【０００２】
ブースティングとは、必ずしも精度の良くない判別器を複数組み合わせることによって、精度の良い判別器を構築するアルゴリズムである。ブースティングによって学習された判別器は様々な分野で使われている（非特許文献１など）。
【０００３】
特に顔検知や顔認識技術などに使われており、デジタルカメラやビデオカメラの普及によって私たちの生活に身近なものとなっている。顔検出器は入力データとして、ある画像領域の輝度値を受け取り、画像領域に顔が有るかどうかを判別する判別装置である。顔検出の研究は、１９９０ 年代後半から行われていたが、計算速度の点で実用には至らなかった。しかしViolaとJonesによって提案された高速演算可能なHaar-Like特徴量（図２０参照）を使った弱判別器を用いた顔検出器により、実時間での顔検出の処理が可能になった。
【０００４】
顔検出にブースティングが使われる理由は判別装置の学習にかかる時間よりも実際に判別する際の判別時間が重要視されるからである。顔検出問題においてブースティングが速く判別を行える理由の一つは前述の高速演算可能な特徴量を導入した点にあるが、さらに、弱判別器の評価を途中で打ち切るという手法が用いられている点も高速に顔検出を行うポイントになっている。ブースティングで得られる判別装置は，弱判別器の線形結合であり、それらを逐次評価して最終的な判別結果を得る手法が一般的に用いられている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Yoav Freund and Robert E. Schapire “A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting” journal of computer and system sciences 55, 119_139 (1997)
【発明の概要】
【発明が解決しようとする課題】
【０００６】
通常、画像中に顔が存在する割合は少ないため、「顔でない」と判定する弱判別器も多い。「顔でない」と判定する弱判別器も多いと考えられる判別装置については、それらの評価を途中で打ち切れば、判別に要する時間を平均的に短縮することが可能である。特に、「顔でない」判定への寄与度の高い弱判別器を先に評価するようにすれば、より早い段階で打ち切ることができる。つまり、弱判別器の並び順が、判別速度を決める重要な要因になる。
【０００７】
従来、ブースティングなどによる弱判別器群の順序は、全ての弱判別器を用いることを前提に設計されているので、全体ではなく一部の弱判別器で判別すると精度が犠牲になり、判別の速度と精度を両立した総合性能を更に高めることは困難だった。
【０００８】
そこで、本発明では、複数の弱判別器群からなる判別装置において判別の精度を犠牲にすることなく高速に判別が行なえる高速判別装置および高速判別装置を高速化する方法、並びに高速判別装置プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の高速判別装置は、判別対象の対象データに所定のオブジェクトが含まれるか否かを判別した判別結果を得る高速判別装置であって、
前記対象データｘの入力を受け付ける対象データ入力受付手段と、所定の順番に並べられた、前記対象データｘに前記オブジェクトが含まれるか否かを評価する複数個の判別器ｆｊ（ｊ＝１〜Ｊ）からなる判別器群と、前記複数個の判別器のうちの１番目の判別器から順に各判別器を用いて前記対象データｘを評価した評価値ｆｊ（ｘ）を求め、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）（ｊ＝１〜ｉ）から得られた総合評価値Ｆｉ（ｘ）をｉ＝１からＪまで順に得る評価値取得手段と、前記評価値取得手段によってｉ＝Ｉ（Ｉ＜Ｊ）番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が示す前記判別結果が、Ｉ＋１番目以降の各判別器が取り得る評価値の範囲に基づいて、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩ（ｘ）にＩ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定する判別結果決定手段とを備えたことを特徴とするものである。
【００１０】
また、本発明のプログラムは、判別対象の対象データに所定のオブジェクトが含まれるか否かを判別した判別結果を得る高速判別装置のプログラムであって、
コンピュータを、前記対象データｘの入力を受け付ける対象データ入力受付手段と、所定の順番に並べられた、前記対象データｘに前記オブジェクトが含まれるか否かを評価する複数個の判別器ｆｊ（ｊ＝１〜Ｊ）からなる判別器群と、前記複数個の判別器のうちの１番目の判別器から順に各判別器を用いて前記対象データｘを評価した評価値ｆｊ（ｘ）を求め、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）（ｊ＝１〜ｉ）から得られた総合評価値Ｆｉ（ｘ）をｉ＝１からＪまで順に得る評価値取得手段と、前記評価値取得手段によってｉ＝Ｉ（Ｉ＜Ｊ）番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が示す前記判別結果が、Ｉ＋１番目以降の各判別器が取り得る評価値の範囲に基づいて、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩ（ｘ）にＩ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定する判別結果決定手段として機能させることを特徴とするものである。
【００１１】
「対象データ」とは、画像データ、音のデータ、文字データ、生体データ、自然・物理データなどをいい、画像データには、デジタルスチールカメラなどの撮影装置で撮影した画像や、ＣＴやＭＲＩなどの医療用撮影装置で撮影した画像などが含まれ、生体データには、心拍、脈拍、血圧、呼吸、発汗の波形や周期、振幅などを計測したデータが含まれ、自然・物理データには、天候、気候、地震の波形や周期、振幅などを計測したデータが含まれる。文字データは、文字（数字を含む）からなるデータをいう。
【００１２】
「オブジェクト」とは、対象データ中に含まれるものであり、例えば、デジタルスチールカメラなどの撮影装置によって対象データとなる画像に撮影された顔、頭部または人物の手などの人体の外観の一部の部位、あるいは人体の外観ではなく生体内の少なくとも一部の部位を含む領域が含まれる。なお、生体とは、生体内部の血管などのように、生体の内部に存在する特定の組織をいう。対象データが内視鏡システムや顕微鏡などで撮影した画像の場合には、オブジェクトには、生体内部の腫瘍組織、細胞、タンパク質、DNA・RNAなどの高分子、低分子が含まれる。生体の他にも、顕微鏡などで撮影された薬などの化合物やタンパク質などであってもよい。あるいは、貨幣、キャッシュカードなどのカード、車輌、あるいは車両のナンバープレートなど、デジタルスチールカメラなどの撮影装置によって対象データに撮影された画像であってもよい。また、対象データが、複写機などのスキャナ機器によりスキャニングされた画像である場合には、ドキュメントの文字、図面、表、写真などがオブジェクトに含まれる。さらに、オブジェクトは、画像データを統計的分析したときに統計的偏りのある群であればよく、例えば、テクスチャをも含むものである。
さらに、対象データが音のデータの場合には、「オブジェクト」は、例えば、音声、生体の音、生き物の声（動物、鳥、昆虫）、楽器の音、乗り物の音などである。
【００１３】
また、前記判別器群が、前記複数の判別器ｆｊとともに、該判別器のそれぞれに対する重みαｊとを記憶するものであり、
前記評価値取得手段が、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）と各判別器の重みαｊとを線形結合した総合評価値Ｆｉ（ｘ）
【数１】
をｉ＝１からＪまで順に得るものであってもよい。
【００１４】
また、前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩが条件１
【数２】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものが望ましい。
【００１５】
また、前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩが条件２
【数３】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであってもよい。
【００１６】
また、前記評価値取得手段が、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）を線形結合した総合評価値Ｆｉ（ｘ）
【数４】
をｉ＝１からＪまで順に得るものであってもよい。
【００１７】
また、前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件３−１または条件４−１
【数５】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものが望ましい。
【００１８】
また、前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件５−１または条件６−１
【数６】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであってもよい。
【００１９】
また、前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件３−２または条件４−２
【数７】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであってもよい。
【００２０】
また、前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件５−２または条件６−２
【数８】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであってもよい。
【００２１】
さらに、前記判別結果は、前記総合評価値Ｆｉ（ｘ）の符号に応じて決定されるものであってもよい。
【００２２】
また、前記判別器群が、Ｋ個のステージに分けられるとともに、各ステージ毎に所定の順番で並べられたJｋ（ｋ＝１〜Ｋ）個の判別器からなる判別器群が含まれるものである場合には、前記評価値取得手段が、前記各ステージ毎に１番目から順に前記総合評価値Ｆｉ（ｘ）を各ステージのｉ＝１からＪｋまで順に得るものであり、前記判別結果決定手段が、前記評価値取得手段によって、各ステージのｉ＝Ｉｋ（Ｉｋ＜Ｊｋ）番目までの判別器を評価して得られた前記総合評価値ＦｋI（ｘ）が示す前記判別結果が、各ステージに含まれるＩｋ＋１番目以降の各判別器が取り得る評価値の範囲に基づいて、前記Ｉｋ番目までの判別器を評価して得られた総合評価値ＦｋI（ｘ）にＩｋ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、前記評価値取得手段に各ステージのＩｋ＋１番目以降の判別器の評価の打ち切りを指示するとともに、前記Ｉｋ番目までの判別器を評価して得られた総合評価値ＦｋＩに応じた前記判別結果を各ステージの最終結果として決定するものが望ましい。
【００２３】
本発明の前記高速判別装置を高速化するための方法は、Ｎ個のサンプルデータを記憶するサンプルデータ記憶ステップと、前記所定の順番に並べられた複数の判別器からなる判別器群の２以上の判別器を交換して並び替えを行う判別器交換ステップと、該判別器交換ステップによる交換前と交換後の並び順の判別器群のそれぞれにおいて、前記Ｎ個のサンプルデータのそれぞれを前記対象データ入力受付手段より対象データｘとして受け付けて、前記評価値取得手段を実行した後に前記判別結果決定手段が前記判別器の評価の打ち切りを指示するまでに評価された判別器の数Ｉを各サンプルデータごとに取得し、前記Ｎ個のサンプルデータの前記評価された判別器の数の代表値を取得する評価済判別器数取得ステップと、前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より小さい場合には、前記判別器群の並び順を前記交換後の並び順に並び替えて前記判別器群に記憶し、前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より大きい場合には、前記判別器群に記憶されている前記判別器群の並び順をそのままとする並び替えステップと、前記判別器交換ステップ、前記評価済判別器数取得ステップ、および前記並び替えステップを繰り返して、前記評価された判別器の数の代表値が最小となる前記判別器群の並び順を探索する探索ステップと、を備えたことを特徴とするものである。
【００２４】
本発明の他の前記高速判別装置を高速化するための方法は、Ｎ個のサンプルデータを記憶するサンプルデータ記憶ステップと、前記各ステージ毎に所定の順番に並べられた複数の判別器からなる判別器群の２以上の判別器を交換して並び替えを行う判別器交換ステップと、該判別器交換ステップによる交換前と交換後の並び順の判別器群のそれぞれにおいて、前記Ｎ個のサンプルデータのそれぞれを前記対象データ入力受付手段より対象データｘとして受け付けて、前記評価値取得手段を実行した後に各ステージにおいて前記判別結果決定手段が前記判別器の評価の打ち切りを指示するまでに評価された判別器の数Ｉｋを各サンプルデータごとに取得し、前記Ｎ個のサンプルデータの前記評価された判別器の数の代表値を各ステージ毎に取得する評価済判別器数取得ステップと、前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より小さい場合には、前記各ステージの判別器群の並び順を前記交換後の並び順に並び替えて前記判別器群に記憶し、前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より大きい場合には、前記各ステージの判別器群に記憶されている前記判別器群の並び順をそのままとする並び替えステップと、前記判別器交換ステップ、前記評価済判別器数取得ステップ、および前記並び替えステップを繰り返して、前記評価された判別器の数の代表値が最小となる前記各ステージの判別器群の並び順を探索する探索ステップと、を備えたことを特徴とするものである。
【００２５】
また、前記高速判別装置を高速化するための方法において、前記判別器交換ステップが、前記所定の順番に並べられた複数の判別器からなる判別器群のうちの任意の２つの判別器を交換するようにし、前記探索ステップで、前記判別器交換ステップにおいて前記交換した２つの判別器の全ての組み合わせについて、前記評価済判別器数取得ステップ、および前記並び替えステップを繰り返して、前記評価された判別器の数の代表値が最小となる前記判別器群の並び順を探索することを特徴とするものが望ましい。
【００２６】
「代表値」とは、具体的には平均値、最頻値、中央値などをいう。
【００２７】
また、前記サンプルデータには、ラベル無学習データを含むものが好ましい。
【００２８】
さらに、前記判別器群は、所定の分布Ｐ１に従う学習データを用いて学習を行うことにより選択されたものであり、前記サンプルデータには、前記分布Ｐ１とは異なる分布Ｐ２の学習データを含むものが好ましい。
【００２９】
さらにまた、前記分布Ｐ２が前記対象データの分布に近い分布を表すものが望ましい。
【発明の効果】
【００３０】
本発明の高速判別装置によれば、所定の順番に並べられた判別器群から最終結果を得る際に、１番目の判別器から順に各判別器の評価を行い、Ｉ番目までの判別器を評価して得られた総合評価値が示す判別結果が、Ｉ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、Ｉ＋１番目以降の判別器の評価を打ち切って、Ｉ番目までの判別器を評価して得られた総合評価値に応じた判別結果を最終結果として決定しているので、判別器の精度を犠牲にすることなく高速に判別を行なうことが可能になる。
【００３１】
また、Ｉ番目までの判別器を評価して得られた総合評価値に上記の条件２，５−１，６−１，５−２，６−２のように、ある程度の許容誤差があってもＩ＋１番目以降の判別器の評価を打ち切るようにすることで、多少判別精度を犠牲にすることでより高速に判別することが可能になる。
【００３２】
また、判別器を複数のステージに分けたカスケード構造の高速判別装置においても、各ステージkにおいて、Ｉｋ番目までの判別器を評価して得られた総合評価値が示す判別結果が、Ｉｋ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、Ｉｋ＋１番目以降の判別器の評価を打ち切って、Ｉｋ番目までの判別器を評価して得られた総合評価値に応じた判別結果を各ステージの最終結果として決定するようにすれば、各ステージを高速化することができ、さらにカスケード構造による高速化を図ることが可能になる。
【００３３】
さらに、本発明の高速判別装置を高速化するための方法によれば、所定の順番に並べられた判別器群の並び替えを行いながら、Ｎ個のサンプルデータに対して、判別器の評価が打ち切られるまでに評価された判別器の数の平均値、最頻値、中央値などの代表値を求めて、もっとも早い段階で判別器の評価の打ち切りが行われる判別器群の並び順を探索するようにしているので、本発明の高速判別装置をさらに高速化することが可能になる。
【００３４】
また、カスケード構造の高速判別装置を高速化するための方法によれば、各ステージ毎に、もっとも早い段階で判別器の評価の打ち切りが行われる判別器群の並び順を探索するようにしているので、カスケード構造により早いステージで次の段階に進む画像であるか否かを判別した上で、さらに、各ステージの判別を高速化することができるので、本発明の高速判別装置をさらに高速化することが可能になる。
【００３５】
また、最適な判別器群の並び順を探索するには、全ての判別器群に対して並び替えを行うことで最適解を得られると考えられるが、実際に顔などの判別に用いられる判別器は千個を超える数になるため、全ての判別器群に対して並び替えを行うと計算量が膨大になる。そこで、本発明のように判別器群の中の任意の２つの判別器を交換するようにすれば計算量を減らすことができるとともに、全ての判別器群に対して並び替えを行なった場合に近い準最適解を得ることが可能になる。
【００３６】
さらに、最適な判別器群の並び順を探索する際のサンプルデータにラベル無学習データを含めることにより、サンプルデータのサイズを大きくすることが可能になり、多様なデータに対応した高速化が図れる。
【００３７】
さらに、ブースティングなどの学習によって判別器を選択する際に用いられる学習データと、この学習データとは異なる分布に従うサンプルデータを用いて判別器群の並び順を探索することにより、ブースティング学習などに用いられるラベル付き学習データとサンプルデータの分布の違いを考慮した並び順に弱判別器を並び替えて高速判別装置の高速化をさらに図ることが可能になる。
【００３８】
さらにまた、サンプルデータを実際の判別対象となる対象データに近い分布にすれば、対象データの分布を考慮した高速化を行なうことができる。
【図面の簡単な説明】
【００３９】
【図１】第１の実施形態に係る高速判別装置の構成を示したブロック図
【図２】第１の実施形態に係る高速判別装置の処理の流れを示すフローチャート
【図３】第２の実施形態に係る高速判別装置の構成を示したブロック図
【図４】第２の実施形態に係る高速判別装置の処理の流れを示すフローチャート
【図５】サンプルデータの特徴量の確率密度関数および真の条件付き分布の一例を示す図
【図６】アダブーストによって選ばれた弱判別器とその係数の関係を表す図
【図７】第３の実施の形態の順序構造学習の処理の流れを示すフローチャート
【図８】全解探索により順序構造学習を行なったときに評価された弱判別器の数の平均Γを示すグラフ
【図９】２つの弱判別器の交換により順序構造学習を行なったときに評価された弱判別器の数の平均Γを示すグラフ
【図１０】弱判別器の数を増やしたときの２つの弱判別器の交換により順序構造学習を行なったときに評価された弱判別器の数の平均Γを示すグラフ
【図１１】第４の実施形態に係る複数のステージからなる高速判別装置の構成を示したブロック図
【図１２】第５の実施の形態の順序構造学習の処理の流れを示すフローチャート
【図１３】ブースティング順の各ステージの平均評価回数と、SL(2)による順序構造学習後の各ステージの平均評価回数を示すグラフ
【図１４】ブースティング順と、SL(2)による順序構造学習後の各ステージで評価される弱判別器の割合を示すグラフ
【図１５】最初のステージに入力された探索窓の各ステージにおける棄却率を示すグラフ
【図１６】統合した正面顔検出器の平均評価回数を示すグラフ
【図１７】実験５の順序構造学習を行なったときに性能評価を示すグラフ
【図１８】実験６の順序構造学習を行なったときに性能評価を示すグラフ
【図１９】実験７の順序構造学習を行なったときに性能評価を示すグラフ
【図２０】Haar-Likeフィルタを示す図
【発明を実施するための形態】
【００４０】
以下、図面により、本発明の実施形態を詳細に説明する。本発明の高速判別装置は、デジタルカメラまたはデジタルビデオに搭載されるファームウェアに組み込まれた高速判別プログラムが実行されることにより、あるいは、高速判別プログラムがパソコンなどのコンピュータにロードされて実行されることにより実現する。また、高速判別プログラムはＣＤ−ＲＯＭなどの記憶媒体に記憶されて配布され、ＣＤ−ＲＯＭなどの記憶媒体からコンピュータにインストールされる。あるいは、インターネットなどのネットワークを介してプログラムが配布されて、コンピュータにインストールされる。あるいは、デジタルカメラまたはデジタルビデオの製造時にファームウェアに組み込まれる。
【００４１】
まず、図１および図２を用いて、本発明の第１の実施形態に係る高速判別装置を説明する。図１は、本発明の第１の実施形態に係る高速判別装置１の構成を示したブロック図である。図２は、高速判別装置１の処理の流れを示すフローチャートである。
【００４２】
図１に示すように、高速判別装置１は、対象データｘの入力を受け付ける対象データ入力受付手段１１と、Ｊ個の判別器ｆｊからなる判別器群を記憶する判別器記憶手段１２と、複数の判別器から総合評価値を得る評価値取得手段１３と、総合評価値から最終結果を決定する判別結果決定手段１４と、を備えている。本実施の形態では、ブースティングのアルゴリズムを用いて対象データの判別を行う場合について説明する。
【００４３】
判別器記憶手段１２は、ブースティングのアルゴリズムによって選別されたＪ個の判別器ｆｊ（判別器群）が所定の並び順で記憶されている。例えば、対象データが画像であり（以下、対象データを対象画像データとする）、対象画像データに顔が存在するかどうかを判別する場合には、判別器ｆｊとして、多数あるHaar-Likeフィルタの中から選択することができる（図２０、および、Pual.Viola,Michael J.Jones.Robust Real-Time Face Detection, International Journal ofComputer Vision,Vol.57,pp.137-154, 2004.などを参照）。以下、オブジェクトとして顔を検出する場合を例に説明する。
【００４４】
このＪ個の判別器ｆｊの少なくとも１つには、誤判別率が1/2 よりも小さい弱判別器を含むものとする（以下、判別器を弱判別器とし、判別器群を弱判別器を含む弱判別器群として説明する）。ブースティングのアルゴリズムは、Ｊ個の判別器ｆｊを線形結合することで強力な判別装置を構築するアルゴリズムであり、各弱判別ｆｊに対する重み（線形結合係数）αｊが決定されて弱判別器群と一緒に判別器記憶手段１２に記憶される。
【００４５】
ここで、Ｊ個の弱判別器ｆｊで構成する強力な判別装置を用いた判別方法について説明する。１番目〜Ｊ番目までの各弱判別器ｆｊを用いて対象画像データｘを評価したときの評価値はｆｊ（ｘ）とあらわす。このとき、Ｊ 個の弱判別器ｆｊの線形結合で構築されている判別関数Fは、
【数９】
と定義することができる。
【００４６】
最終的な判別装置ｇは、
【数１０】
とする。signは符号を表し、符号に応じて判別装置ｇの最終的な判定結果が決定される（ｇが正であれば顔が含まれる。ｇが負であれば顔が含まれない。）。
【００４７】
弱判別器による線形結合の方法はブースティングのアルゴリズムによって異なるが、ここでは、Adaboost によって学習された判別関数Ｆを例に以下説明する。
【００４８】
実際にデジタルカメラなどで撮影された撮影画像（対象画像）データ中に顔が存在するかどうかを判別するために用いられる弱判別器の数Ｊは、千個を超える数になる。実際には一枚の対象画像データから顔を検出する時間を30msec以下で終えるのが望ましく、常に全ての弱判別器で評価するのは実用的ではない。Adaboostでは重みαｊは判別誤差が小さくなるように決められる。そこで、Ｊ個の弱判別器をBoostingが求めた順または重みの大きい順などに並べておく。並べられた順に弱判別器を評価して途中で判別を打ち切り、少ない弱判別器を用いて高速に判別を行なうことが考えられるが、打切ると判別精度が落ちて問題になる。
【００４９】
判別精度を維持するためには、評価関数Ｆを計算する際に１番目からI（＜Ｊ） 番目までの弱判別器を評価したときに、評価していないＩ＋１番目以降の弱判別器を評価してもsign(Ｆ(ｘ)) の符号が変わらなければ、Ｉ＋１番目以降の弱判別器は評価を打ち切っても精度を犠牲にすることがない。以下に、この打ち切り法について詳細に説明する。
【００５０】
まず、対象画像データ入力受付手段１１で判別対象の対象画像データｘの入力を受け付ける（＃１）。対象画像データｘは、デジタルスチールカメラで撮影した画像データ、デジタルビデオで撮影した１フレームの画像データ、スキャナで読み込んだデジタルデータなどである。
【００５１】
評価値取得手段１３は、１番目の弱判別器ｆｊから順に対象画像データｘを評価した評価値ｆｊ（ｘ）を求める（＃２、＃３、＃７、＃８）。１番目からｉ番目までの弱判別器を用いて対象画像データｘを評価したときの総合評価値Ｆｉ（ｘ）は、１番目からｉ（＞１）番目までの弱判別器の評価値ｆｊ（ｘ）（ｊ＝１〜ｉ）と重みαｊを線形結合して求められる。総合評価値Ｆｉ（ｘ）はｉ＝１からＪまで順に算出する（＃４）。
【数１１】
【００５２】
次に、判別結果決定手段１４は、i＋１番目以降の弱判別器の重みの合計ｍｉを求める（＃５）。
【数１２】
【００５３】
また、未評価のｉ番目以降の弱判別器による評価値の総合評価値Ｆ’ｉは下の式から求められる。
【数１３】
【００５４】
全ての弱判別器を評価したときの総合評価値はＦｉ＋Ｆ’ｉであるが各弱判別器ｆｊは−１または１の値を取るので、Ｆ’ｉは−ｍｉから＋ｍｉの値（数式（４）参照）を取る。したがって、
【数１４】
を満足するＩ番目までの弱判別器で評価を打ち切っても、Ｉ＋１番目以降の弱判別器を評価しなくともsign（ＦI）の符号は、全ての弱判別器を評価したときのsign（Ｆ=ＦI＋Ｆ’I）と必ず一致する。
【００５５】
そこで、判別結果決定手段１４は、Ｉ番目の弱判別器までの総合評価値ＦＩ（ｘ）が条件１を満足する場合には（＃６-Yes）、評価値取得手段１３にＩ＋１番目以降の弱判別器の評価の打ち切りを指示する。また、Ｉ番目までの弱判別器を評価して得られた総合評価値ＦＩのsign（ＦI）の符号から最終結果を決定する（＃９、＃１０）。
【００５６】
条件１を満足するまで、上記の判定を繰り返し（＃３〜＃８）、打ち切りが行われなかった場合は、Ｊ個の全ての弱判別器から得られた総合評価値ＦJの符号sign（ＦJ）から最終結果を決定する（＃１１）。
【００５７】
上述では、判別結果決定手段１４でｍｉを算出する場合について説明したが、ｍｉの値は対象画像データｘに依らないため、判別を行う前に計算可能な値である。事前にｍｉが取りうる全ての値のルックアップテーブルを記憶しておくことにより、I 番目の弱判別器を評価した時点で判別を打ち切ることができる。このように途中で判別を打ち切ることからＪ−I 個の弱判別器を評価しない分高速に判別できる。
【００５８】
次に、弱判別器の打ち切り法の具体例を挙げる。
判別関数: Ｆ（ｘ）＝3 ｆ１（ｘ）＋1.5 ｆ２（ｘ）＋ｆ３（ｘ）＋0.5 ｆ４（ｘ）＋0.3ｆ５（ｘ）が与えられたとする。
（１） まず、一項目ｆ１(ｘ)＝1と評価されたとする。するとＦ１ (ｘ)＝3かつｍ１＝3.3である。この段階では残りの全ての弱判別器が−1 をとると符号が逆転するので打ちきれない。
（２） 二項目f２(ｘ)＝−1と評価されたとする。するとＦ２(ｘ)＝1.5かつｍ２＝1.8である。この段階でも残りの全ての弱判別器が−１をとると符号が逆転するので打ちきれない。
（３） 三項目f３(ｘ)＝1と評価されたとする。すなわちＦ３(ｘ)＝2.5かつｍ３ ＝0.8である。このとき数式（６）の条件１が満たされ、残りの弱判別器f４, f５ がいかなる値をとっても符号は逆転できずsign（Ｆ（ｘ））＝sign（Ｆ３（ｘ））＝１ である。
よってγ（ｘ, Ｆ）＝３で打ち切ることができる。
【００５９】
上記の条件１を満足するときに、弱判別器の評価を打ち切るようにすれば判別精度を犠牲にすることはないが、さらに高速に判別を行ないたい場合には、判別結果決定手段１４は、上記の条件１を満足する少し手前の弱判別器で評価を打ち切るようにしてもよい。この場合、判別結果決定手段１４は、総合評価値ＦＩが下記の条件２、
【数１５】
を満足する場合には、評価値取得手段１３にＩ＋１番目以降の弱判別器の評価の打ち切りを指示するようにし、Ｉ番目までの弱判別器を評価して得られた総合評価値ＦＩのsign（ＦI）の符号を最終結果として決定する。係数ｂは、多数のサンプルデータを実際に評価して、正答率が少なくとも1/2以上になるように決められる。好ましくは、正答率が要求を満足する％となるように係数ｂを決定する。
【００６０】
次に、第２の実施の形態について、図３および図４を用いて説明する。第２の実施の形態では拡張した弱判別器を用いた場合について説明する。図３は、本実施の形態に係る高速判別装置１の構成を示すブロック図である。また、図４に本実施の形態の高速判別装置１の処理の流れを示すフローチャートを示す。
【００６１】
図３に示すように、高速判別装置１ａは、対象データ入力受付手段１１と、判別器記憶手段１２ａと、評価値取得手段１３ａと、判別結果決定手段１４ａと、を備えている。本実施の形態の高速判別装置１ａは、第１の実施の形態と略同じ構成を備えるので、詳細な説明は省略して相違する点について説明する。
【００６２】
本実施の形態では、判別器記憶手段１２ａに記憶されている弱判別器ｆｊは、−１、１の２値ではなく適当な二値の実数αｊ、βｊをとる場合について説明する（本実施の形態のαｊは第１の実施の形態の重みαｊとは異なることに注意）。
【００６３】
このとき、判別関数Ｆは適当な閾値Ｔを用いて、
【数１６】
と定義することができる。
【００６４】
最終的な判別装置ｇは、
【数１７】
とする。signは符号を表し、第１の実施の形態と同様に、ｇの符号に応じて最終的な判別結果が決定される。
【００６５】
本実施の形態でも、Ｊ個の弱判別器はBoostingが求めた(判別誤差が小さい)順または重みの大きい順などに並べておく。まず、第１の実施の形態と同様に対象画像データ入力受付手段１１で判別対象の対象画像データｘの入力を受け付ける（＃１）。
【００６６】
次に、評価値取得手段１３ａは、第１の実施の形態と同様に、１番目の弱判別器ｆｊから順に対象画像データｘを評価した評価値ｆｊ（ｘ）を求め（＃２、＃３、＃７、＃８）、さらに、１番目からｉ番目までの弱判別器を用いて対象画像データｘを評価したときの総合評価値Ｆｉ（ｘ）を求める。総合評価値Ｆｉ（ｘ）はｉ＝１からＪまで順に算出する（＃１２）。
【数１８】
【００６７】
次に、判別結果決定手段１４ａは、ｉ＋１番目以降の弱判別器が取り得る値の範囲を求める（＃１３）。
【数１９】
【００６８】
そこで、Ｉ番目までの弱判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、下記の条件３−１または条件４−１、
【数２０】
のいずれかを満足すれば、Ｉ番目までの弱判別器で評価を打ち切っても、Ｉ＋１番目以降の弱判別器を評価しなくともsign（ＦI）の符号は、全ての弱判別器を評価したときのsign（Ｆ）と必ず一致する。つまり、条件３−１ が成り立てばsign（Ｆ（ｘ））＝１が保証される．同様に条件４−１ が成り立てばばsign（Ｆ（ｘ））＝-１ が保証される。
【００６９】
そこで、判別結果決定手段１４ａは、Ｉ番目の弱判別器までの総合評価値ＦＩ（ｘ）が条件３−１または４−１を満足する場合には（＃１４-Yes）、評価値取得手段１３ａ にＩ＋１番目以降の弱判別器の評価の打ち切りを指示する。また、Ｉ番目までの弱判別器を評価して得られた総合評価値ＦＩのsign（ＦI）の符号を最終結果として決定する（＃１０）。
【００７０】
条件１を満足するまで、上記の判定を繰り返し（＃３、＃１２、＃１３、＃１４、＃７、＃８）、打ち切りが行われなかった場合は、Ｊ個の全ての弱判別器から得られた総合評価値ＦJの符号sign（ＦJ）から最終結果を決定する（＃１１）。また、事前に各ＩについてｍＩ＋，ｍＩ―を計算してルックアップテーブルとして保存しておけば、I 番目の弱判別器を評価した時点で判別を打ち切ることができる。
【００７１】
次に、拡張した弱判別器を用いた場合の打ち切り法の具体例を挙げる。
まず、弱判別器の個数Ｊ＝５とし、弱判別器の取りうる値を下の表１に示す。
【表１】
【００７２】
閾値Ｔ＝０であるときに、対象画像データｘが与えられたときのＦ（ｘ）の符号を評価してみる。
（１） 一項目ｆ１（ｘ）＝2.0と評価されたとする。するとＦ１（ｘ）＝2.0，ｍ−1＝6.3となる。このときsign（Ｆ１（ｘ））×Ｆ１（ｘ）＝2.0 はｍ−1 より小さいためＦ（ｘ）の符号が負である可能性が残る．従って評価を打ち切ることはできない。
（２） 二項目f２（ｘ）＝1.5評価されたとする。するとＦ２（ｘ）＝3.5，ｍ−２＝3.8となる。このときsign（Ｆ２（ｘ））×Ｆ２（ｘ）＝3.5はｍ−２ より小さいため，Ｆ（ｘ） の符号が負である可能性が残る。従って評価を打ち切ることはできない。
（３） 三項目f３（ｘ）＝1.7と評価されたとする。するとＦ3（ｘ）＝5.4，ｍ−３＝3.6となる。このときsign(Ｆ３（ｘ）)×Ｆ３（ｘ）＝5.4＞ｍ−３であるため残りの弱判別器がどんな値を取っても総合評価値の値が負になることはない。従って残りの弱判別器を評価することなく判別を打ち切ることができる。
【００７３】
上記の条件３−１または条件４−１を満足するときに、弱判別器の評価を打ち切るようにすれば判別精度を犠牲にすることはないが、さらに高速に判別を行ないたい場合には、判別結果決定手段１４ａは、上記の条件３−１または条件４−１を満足する少し手前の弱判別器で評価を打ち切るようにしてもよい。この場合、判別結果決定手段１４ａは、前記総合評価値ＦＩが条件５−１または条件６−１、
【数２１】
のいずれかを満足すれば、評価値取得手段１３ａにＩ＋１番目以降の弱判別器の評価の打ち切りを指示する。判別結果決定手段１４ａは、Ｉ番目までの弱判別器を評価して得られた総合評価値ＦＩのsign（ＦI）の符号を最終結果として決定する。係数ｂは、多数のサンプルデータを実際に評価して、正答率が少なくとも1/2以上になるように決められる。好ましくは、正答率が要求を満足する％となるように係数ｂを決定する。
【００７４】
上述の第２の実施の形態では、判別結果決定手段１４ａが条件３−１または条件４−１が成り立つ場合にＩ番目までの弱判別器で評価を打ち切っていたが、下記の条件３−２または条件４−２が成り立つ場合にＩ番目までの弱判別器で評価を打ち切るようにしてもよい。
【数２２】
【００７５】
上記の条件３−２または条件４−２を満足するときに、さらに高速に判別を行ないたい場合には、判別結果決定手段１４ａは、上記の条件３−２または条件４−２を満足する少し手前の弱判別器で評価を打ち切るようにしてもよい。この場合、判別結果決定手段１４ａは、前記総合評価値ＦＩが条件５−２または条件６−２、
【数２３】
のいずれかを満足すれば、評価値取得手段１３ａにＩ＋１番目以降の弱判別器の評価の打ち切りを指示する。判別結果決定手段１４ａは、Ｉ番目までの弱判別器を評価して得られた総合評価値ＦＩのsign（ＦI）の符号を最終結果として決定する。係数ｂは、多数のサンプルデータを実際に評価して、正答率が少なくとも1/2以上になるように決められる。好ましくは、正答率が要求を満足する％となるように係数ｂを決定する。
【００７６】
第３の実施の形態では、高速判別装置を高速化するための方法について説明する。
【００７７】
従来、ブースティングによって選択された弱判別器群の順序は、全ての弱判別器を用いることを前提に設計されているので、全体ではなく一部の弱判別器で判別しつつも精度を犠牲にしないようにする場合には、どうしても高速化に限界があった。そこで、さらに判別を高速に行うために弱判別器の最適な並び順について検討する。このような高速判別のための最適な弱判別器の並び順を求めることを順序構造学習ということにする。
【００７８】
まず、サンプルデータ記憶ステップでＮ個のサンプルデータを用意する。ここで、各サンプルデータをｘｓ（ｓ＝１〜Ｎ）で表す。
【００７９】
上述の高速判別装置ではＪ個の弱判別器群ｆ１，ｆ２，・・・，ｆｊ，・・・，ｆＪ−１，ｆＪが重み順に並べられていたが、弱判別器群の中の２以上の弱判別器を置換した弱判別器群を多数作成して、いずれの並び順が最適であるかについて検討する。ある特定の置換によって得られた弱判別器群の並びをｋを用いて表すものとし、置換後の弱判別器の添え字をｋ（i）で表し、弱判別器はｆｋ（ｊ）と表す。また、ｋの並びの弱判別器群を用いたときの判別関数をＦｋ とする。ｋの並びを用いると与えられたＦｋ は下式 のように書ける（本実施の形態では、第１の実施の形態と同様に弱判別器ｆｊが１または−１の値をとり、判別関数Ｆが重みαｊを用いて線形結合される場合を例に説明する。）。
【数２４】
【００８０】
また、このときの打ち切り条件は下式のように書ける。
【数２５】
【００８１】
各並びｋの弱判別器群で構成される高速判別装置１を用いてサンプルデータｘｓ を評価した際に、高速判別装置１の判別結果決定手段１４で弱判別器の打ち切りが指示されるまでに評価値取得手段１３で評価された弱判別器の数Ｉをγとおく。
【数２６】
【００８２】
Ｎ個のサンプルデータｘｓ（ｓ＝１，２，・・・，Ｎ）のそれぞれについて、並び＾ｋの高速判別装置を用いてγを取得し、Ｎ個のサンプルデータのγの平均値Γ（Ｆ，ｋ）を取得する。
【数２７】
この評価された弱判別器の数の平均Γ（Ｆ，ｋ）が最小となる並び＾ｋを求める。
【００８３】
ところで上述の打ち切り法の性質を考えると、一見各弱判別器の係数の絶対値について降順で並べた順序が最適な並びになりそうに見える。なぜなら係数の絶対値が小さい弱判別器が後半に集まるため、評価値取得手段１３で評価した弱判別器の数が少なくても、ｍＩ は小さいので、早期に打ちきれる可能性が高まるからである。このことからわざわざ順序構造学習を行わなくても例えば以下の二つの並び順
ブースティング順＾ｋｂ ：ブースティングの学習時に選択された順序
係数絶対値順＾ｋｄ ：各弱判別器の係数（重みα）の絶対値が降順で並ぶ順序
はそもそも最適になっているのではないかと考えられる。
【００８４】
しかし、実際以下のような反例を作ることができる。まず、ここで、サンプルデータの特徴量をｘ（本実施の形態では、xは特徴量を表すものとして説明する）とし、その判別結果をｙ（真：ｙ＝１ 偽：ｙ＝−１）で表すものとする。特徴量ｘの周辺分布ｐ(ｘ)を、
【数２８】
とする。結果として各区間Ｒ１:＝[0, 1/3], Ｒ２:＝[1/3, 2/3], Ｒ３:＝[2/3, 1] に該当する特徴量ｘが発生する確率は、
【数２９】
となる。また真の条件付き分布ｐ(ｙ|ｘ) （ｙ＝１）を、
【数３０】
と定める。図５にｐ（ｘ）とｐ（１｜ｘ） を図示する。
【００８５】
今、同時分布ｐ（ｘ，ｙ）＝ｐ（ｘ）ｐ（ｙ｜ｘ）からｎ個のサンプルデータがＤ:＝{（ｘｉ， ｙｉ） | ｉ＝１，２，・ ・ ・，ｎ} で与えられたとする。
【００８６】
図５の左図はｘの確率密度関数ｐ（ｘ）を、右図はｐ（１｜ｘ）を表す。図の点線はｐ（１｜ｘ）＝1/2 を示している。
【００８７】
図６の左図はアダブーストによって得られた判別関数を表し、右表はＮ個のサンプルデータで実際にアダブーストを行ったとき、各ステップでアダブーストによって得られた弱判別器とその係数（重み）を表している。
【００８８】
ここで、３個の弱判別器ｆ１、ｆ２、ｆ３
【数３１】
を用いてアダブーストにより学習したとする。このときサンプルデータ数及びステップ数が十分に大きければアダブーストの判別関数は
【数３２】
になることがよく知られている（文献２：J. H. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: A statisticalview of boosting. The Annals of Statistics, 28:337-407, 2000.参照）。ただし、同じ弱判別器についての係数はまとめてある。実際、例えばｎ= 1000 でアダブーストの逐次学習を100 回行うと0.35 *ｆ１(ｘ) + 0.15 *ｆ２(ｘ) + 0.38ｆ３(ｘ) となった。以下では簡単のために上記のＦ(ｘ) をアダブーストによって得られた判別関数として進める。図６の右表からアダブーストによって選ばれた弱判別器の順序はｆ１, ｆ３, ｆ２ である。一方係数絶対値順はｆ３, ｆ１, ｆ２であることがわかる。今、ｆ１, ｆ２, ｆ３ の全ての並び順についてΓ(Ｆ) を計算すると表２のようになる。この表からブースティング順も係数絶対値順も最適な並びではないことがわかる。
【００８９】
下記の表２は 全ての順序ｋについてのΓ(Ｆ) の値を示す。表２では、順序「１２３」は弱判別器をＦ（ｘ）＝α１ｆ１（ｘ）＋α２ｆ２（ｘ）＋α３ｆ３（ｘ）と並べることを意味する。また６列目のΓ（Ｆ）は２，３，４ 列目を一つの６×３行列Ａとみなし、５列目を３次元縦ベクトルｂとみなしたとき，Ａｂと計算できることに注意。
【表２】
【００９０】
このような現象が起きる理由には以下の三つの事実が深く関連している。
（１） 最小のγ（ｘ，Ｆ） を達成する順序は場所ｘによって異なる。
（２） 最適な判別関数Ｆ（ｘ）はｐ（ｙ｜ｘ）のみから決まる。その一方最適順序構造はｐ(ｘ)にも依存する。
（３） ブースティング順は最終的な形Ｆ（ｘ）に最も早く近づけるように弱判別器を選択する。
【００９１】
まず（１）が正しいことは上記の例でも確認できる。区間Ｒ２では係数絶対値順ｆ３, ｆ１, ｆ２ では全ての弱判別器を評価しなければならないが、順序ｆ１, ｆ２, ｆ３では二回で打ちきれる。すなわち全ての場所で係数絶対値順＾ｋｄが必ずしもγ（ｘ, Ｆ）を最小にするわけではない。
【００９２】
係数絶対値順＾ｋｄが最適でないことは（１）と（２）からわかる。数式（２２）よりアダブーストの判別関数はｐ（ｙ｜ｘ） のみから決まることがわかる。また順序構造学習は定義よりｐ（ｘ） に依存することもわかる。従って（２） が成り立つ。今、（２） を認めるとｐ（ｘ）を変化させても＾ｋｄは不変である。しかしデータが区間Ｒ２に発生する確率が大きくなるほど、＾ｋｄはその区間でのΓ(Ｆ) が悪化する。実際上記の例ではＲ２の発生確率が一番高くなっているため、この区間で最短で打ちきれる＾ｋの方が、＾ｋｄよりΓ(Ｆ) を小さくできる。実際、上記のｐ（ｘ） はそれを満たすように作られている。ブースティング順＾ｋｂが最適でないことは（１）と（３）からわかる。事実（３）は文献２などにより早くから知られている。ブースティング順は図６のステップ１でｆ１を選んでいる。このあとｆ２を選べば上記の理由で最適な順序となる。しかし全体的にＦ(ｘ) の形により近づくためにはｆ３を選ぶ方が有利なためブースティングはｆ３を選んでいる。すなわちブースティングの目的は早くＦ(ｘ) に近づくことであり、打ち切り法を最短にすることとは無関係である。そのため一般には最適な順序と異なる。上記の例はその具体例となっている。
【００９３】
そこで、弱判別器群を並び替えた全ての弱判別器群の並び順に対して評価される弱判別器の数の平均値（以下、平均評価回数という）Γを求めることで、最適な並び＾ｋを求める。この全ての並び順に対して探索を行って最適な並び＾ｋを求めるのがよいが、Ｊ個の弱判別器全ての並び順はＪ！通り存在する。弱判別器の総数は千個以上に及ぶため、実際に探索を行なうのは不可能である。
【００９４】
そこで、効率よく弱判別器群の並び＾ｋを求める手法について検討する。
【００９５】
所定の並びで弱判別器が並んでいるときに、弱判別器群から適当な個数の弱判別器に限定してその中で順を交換したとき、Γが交換前より小さくなった場合には弱判別器を交換する。この操作をΓが小さくならなくなるまで繰り返すことによって弱判別器群の並び順の準最適解が得られると考えられる。
【００９６】
ここでは、弱判別器群から２個の弱判別器の順番を交換する場合について、図７のフローチャートに従って説明する。
【００９７】
まず、サンプルデータ記憶ステップでＮ個のサンプルデータを用意してハードディスクなどの記憶装置に記憶する（＃２０）。
【００９８】
次に、ブースティングで選ばれた弱判別器ｆｊの係数絶対値順＾ｋｂを＾ｋの初期値とする。また、このときのΓ（Ｆ，＾ｋ）をΓｍｉｎの初期値とする（＃２１）。
【００９９】
弱判別器交換ステップでは、所定の順番に並べられた複数の弱判別器からなる弱判別器群のうちの任意の２つの弱判別器を交換する。ここでｓ番目とｔ番目の弱判別器の交換という操作をσ２（ｓ，ｔ）とし、
σ2(s,t) ＝ {1,2,・・・,s,・・・,t,・・・,J｝-> {1,2,・・・,t,・・・,s,・・・,J}
と定義する。並び＾ｋの弱判別器群から選択したｓ番目とｔ番目の２つの弱判別器を交換して新しい並びσ2(s,t)＾ｋの弱判別器群を生成する（＃２２）。
【０１００】
次に、評価済弱判別器数取得ステップで、Ｎ個のサンプルデータのそれぞれを対象画像データ入力受付手段１１より対象画像データｘとして受け付けて、交換後の並びσ2(s,t)＾ｋにおけるΓ（Ｆ，σ2(s,t)＾ｋ）を求める（＃２３）。
【０１０１】
並び替えステップでは、交換後のΓ（Ｆ，σ2(s,t)＾ｋ）が交換前のΓｍｉｎより小さい場合には（＃２４−YES）、弱判別器群の並び順を交換後の並び順σ2(s,t)＾ｋに並び替えて弱判別器群を記憶する。さらに、Γ（Ｆ，σ2(s,t)＾ｋ）をΓｍｉｎとする（＃２５）。一方、交換後のΓ（Ｆ，σ2(s,t)＾ｋ）が交換前のΓｍｉｎより大きい場合には、弱判別器群の並び順はそのままにする（＃２４−NO）。
【０１０２】
探索ステップでは、次に交換するs’番目とt’番目の弱判別器を選択してs’をsとしt’をｔとして（＃２７）、以上の弱判別器交換ステップ、評価済弱判別器数取得ステップ、および、並び替えステップを繰り返して（＃２２〜＃２７）、評価された弱判別器の数の平均が最小となる弱判別器群の並び順を探索する。弱判別器交換ステップで行なわれる１〜Ｊの弱判別器の中の２つを交換する全ての組み合わせはＪＣ２となる。したがって、ＪＣ２ 回の交換が終わるまで（＃２６−YES）、弱判別器交換ステップ、評価済弱判別器数取得ステップ、および、並び替えステップを繰り返す（＃２６−NO）。
【０１０３】
上述では、弱判別器群のうちの２つの弱判別器を交換して行くことで、弱判別器群の準最適な並びを求めているが、弱判別器群のうちの３つ弱判別器を交換していくことで準最適な並びを求めることもできる。
【０１０４】
弱判別器交換ステップで弱判別器群の中の三つの弱判別器を選び、その三つの弱判別器について下の表３の５パターンの並び順の交換σ3 を行い、評価済弱判別器数取得ステップで平均評価回数Γを計算する。並び替えステップでは、５つの結果の中で、交換する前より平均評価回数Γが改善した中で、平均評価回数Γが最小となる並び順の交換を採用し、弱判別器群の並び順を更新する。探索ステップでは、以上の弱判別器交換ステップ、評価済弱判別器数取得ステップ、および、並び替えステップを繰り返して、評価された弱判別器の数の平均が最小となる弱判別器群の並び順を探索する。弱判別器の中の３つを交換する組み合わせによる弱判別器群の並び替えの交換回数はＪＣ３＊５になる。したがって、ＪＣ３＊５ 回の交換が終わるまで、弱判別器交換ステップ、評価済弱判別器数取得ステップ、および、並び替えステップを繰り返して準最適な並び順を探索する。
【表３】
【０１０５】
弱判別器群のうちの２つの弱判別器を交換して行く場合に比べて、弱判別器群のうちの３つの弱判別器を交換して行く場合のほうがより最適解に近い結果が得られると予測できる。しかし、弱判別器交換ステップ、評価済弱判別器数取得ステップ、および、並び替えステップの繰り返しは確実に増えることになり、弱判別器群のうちの２つの弱判別器を交換して行く場合より準最適解を得るための計算量は大きくなる。
【０１０６】
以下、実験結果に基づいて順序構造学習の効果について説明する。
【０１０７】
実験１では、弱判別器群の全ての並び替え（全解探索）による順序構造学習（以下、SL(1)による学習という）と、弱判別器群の中の２個の弱判別器の順番を交換する順序構造学習（以下、SL(2)による学習という）の効果について、実験した結果を説明する。
【０１０８】
計算量の観点から５〜１０個の弱判別器をSL(1)による順序構造学習とSL(2) による順序構造学習を行なった高速判別装置１による平均評価回数Γを下の表４に示す。また、図８にSL(1)により順序構造学習を行なったときの平均評価回数Γと、ブースティング順＾ｋｂや係数絶対値順＾ｋｄ（弱判別器の重みの順）のときの平均評価回数Γを示す。また、図９にSL(2)により順序構造学習を行なったときの平均評価回数Γと、ブースティング順＾ｋｂや係数絶対値順＾ｋｄのときの平均評価回数Γを示す。図８および図９にSL(1) やSL(2)により順序構造学習を行なったときの平均評価回数Γの方がブースティング順＾ｋｂや係数絶対値順＾ｋｄ（弱判別器の重みの順）のときの平均評価回数Γより小さく、高速評価できることがわかる。また、表４をみるとＪが小さい範囲ではSL(2)は、SL(1)のよい近似となっていることが確認できる。つまり、SL(2)による順序構造学習であってもSL(1)による順序構造学習に近い結果を得ることができるものと考えられる。
【表４】
【０１０９】
実験２では、弱判別器の数を増やしてSL(2)の学習を行った結果を図１０に示す。数が増えるに従って高速化の効果が表れていることがわかる。大体弱判別器の数Ｊ＝２０，・・・，５０ぐらいから評価される弱判別器の総数の１割ほど早くなる。この実験より準最適解でも他の並び順よりも一定して高速に判別できることがわかる。
【０１１０】
実験３では、弱判別器群から２個の弱判別器の順番を交換した順序構造学習と、弱判別器群から３個の弱判別器の順番を交換した順序構造学習（以下、SL(3)による学習という）の効果について、実験した結果を説明する。
【０１１１】
計算量の観点から２０〜３０個の弱判別器をSL(2)による順序構造学習とSL(3)による順序構造学習を行なった高速判別装置１による平均評価回数Γを下の表５に示す。
【表５】
二つの結果に大きな差はなく0.01〜0.1(Γ=J)の差でしかない。この実験よりSL(2)による順序構造学習でも十分な高速化を行なうことができると考えられる。
【０１１２】
以上より、順序構造学習にかかる計算量と、高速判別別装置で判別時間の削減との両方を考慮するとSL(2)による順序構造学習によって弱判別器の並び順を決定するのが最もよいという結論に達する。
【０１１３】
本実施の形態では、第１の実施の形態で説明したように、弱判別器ｆｊが−１、１の２値を取る場合を例に弱判別器の並び順を決定する手法について説明したが、第２の実施の形態で説明したように、弱判別器ｆｊが適当な二値の実数αｊ、βｊをとる場合には、評価済弱判別器数取得ステップで、＾ｋの並びの弱判別器群を用いたときのΓを求める際に、判別結果決定手段１４ａが条件３−１または条件４−１を満たすときに弱判別器の評価を打ち切るものとして求める。あるいは、並び順を決定する際に、評価済弱判別器数取得ステップで、＾ｋの並びの弱判別器群を用いたときのΓを求める際に、条件３−２または条件４−２を満たすときに弱判別器の評価を打ち切るものとして求めるようにしてもよい。
【０１１４】
本発明は、第３の実施の形態で説明したように、弱判別器群の最適な（あるいは準最適な）並び順を決定した後に、この決定された並び順の弱判別器群で構成された第１の実施の形態の高速判別装置、または、この決定された並び順の弱判別器群で構成された第２の実施の形態の高速判別装置で、判別対象の対象画像データに顔が含まれているか否かを判別することで、非常に高速な判別を行なうことを実現することができる。
【０１１５】
第１の実施の形態のように弱判別器ｆｊが−１，１の二値をとる場合には、上記に詳細に説明した手法を用いて最適な（あるいは準最適な）並び順を決定した後、決定された最適な（あるいは準最適な）並び順の弱判別器群で構成された高速判別装置１で判別を行なうことによって最も高速な判別を行なうことが可能になる。
【０１１６】
一方、第２の実施の形態のように弱判別器ｆｊが適当な二値の実数αｊ、βｊをとる場合には、条件３−１または条件４−１を満足した場合に、弱判別器の評価を打ち切るケースと、条件３−２または条件４−２を満足した場合に、弱判別器の評価を打ち切るケースとがある。そこで、第２の実施の形態のように弱判別器ｆｊが適当な二値の実数αｊ、βｊをとる場合には、以下の４通りの組み合わせが考えられる。
（１）最適な（あるいは準最適な）並び順を決定するには、条件３−１または条件４−１を満たすときに弱判別器の評価を打ち切るという条件のもとで決定し、この決定された最適な（あるいは準最適な）並び順の弱判別器群で構成された高速判別装置１ａでも、条件３−１または条件４−１を満たすときに弱判別器の評価を打ち切るようにする。
（２）最適な（あるいは準最適な）並び順を決定するには、条件３−１または条件４−１を満たすときに弱判別器の評価を打ち切るという条件のもとで決定し、この決定された最適な（あるいは準最適な）並び順の弱判別器群で構成された高速判別装置１aでも、条件３−２または条件４−２を満たすときに弱判別器の評価を打ち切るようにする。
（３）最適な（あるいは準最適な）並び順を決定するには、条件３−２または条件４−２を満たすときに弱判別器の評価を打ち切るという条件のもとで決定し、この決定された最適な（あるいは準最適な）並び順の弱判別器群で構成された高速判別装置１aでも、条件３−１または条件４−１を満たすときに弱判別器の評価を打ち切るようにする。
（４）最適な（あるいは準最適な）並び順を決定するには、条件３−２または条件４−２を満たすときに弱判別器の評価を打ち切るという条件のもとで決定し、この決定された最適な（あるいは準最適な）並び順の弱判別器群で構成された高速判別装置１aでも、条件３−２または条件４−２を満たすときに弱判別器の評価を打ち切るようにする。
【０１１７】
以上の４通りから、最も高速に判別を行なうことができる高速判別装置を決定することが可能である。上記の各条件において、条件３−１，４−１の方が、条件３−２，４−２より処理がシンプルであるため処理自体は高速であるが、打ち切り回数の性能差が小さいことが実験において確認されている。実験の結果などから、適宜最適な条件の組み合わせを決定するのが良い。
【０１１８】
第４の実施の形態では、高速判別装置の弱判別器群をカスケード型に構成した場合について説明する。図１１は、本実施の形態に係る高速判別装置１ｂの構成を示すブロック図である。高速判別装置１ｂは、対象データ入力受付手段１１と、判別器記憶手段１２ｂと、評価値取得手段１３ｂと、判別結果決定手段１４ｂと、を備えている。本実施の形態の高速判別装置は、弱判別器群が複数のステージに分けられてカスケード型で構成される以外は、第１および２の実施の形態と略同じ構成を備えるので、詳細な説明は省略して相違する点を主に説明する。
【０１１９】
判別器記憶手段１２ｂには、Ｊ個の弱判別器がＫ個のステージに分けて記憶され、各ステージにはＪｋ（ｋ＝１〜Ｋ）個の弱判別器が所定の順番で並べられている。
ここで、ｋ番目のステージの判別関数をＦｋと定義する。Ｆｋ は、
【数３３】
と表わされる。
【０１２０】
各ステージの最終的な判別装置ｇｋは、
【数３４】
で表される。
【０１２１】
次に評価値取得手段１３ｂは、各ステージ毎に総合評価値Ｆｋｉ（ｘ）をｉ＝１からＪｋまで順に算出する。
【数３５】
【０１２２】
次に判別結果決定手段１４ｂは、各ステージ毎にｉ＋１番目以降の弱判別器が取り得る値の範囲を求める（＃１３）。
【数３６】
【０１２３】
そこで、Ｉｋ番目までの弱判別器を評価して得られた前記総合評価値ＦＩｋ（ｘ）が、下記の条件７または条件８
【数３７】
のいずれかを満足すれば、各ステージではＩｋ番目までの弱判別器で評価を打ち切る。
【０１２４】
ここでは、弱判別器が適当な二値の実数をとる場合について説明したが、第１の実施の形態と同様に、弱判別器が１、−１の２値を取る場合であっても、同様に各ステージごとに弱判別器で評価の打ち切りを行うようにすることができる。
【０１２５】
第５の実施の形態では、高速判別装置の複数の弱判別器をカスケード型に構成した場合の最適な弱判別器の並び順を求める順序構造学習について説明する。このカスケード型（カスケード構造）の高速判別装置は、弱判別器がステージと呼ばれるいくつかのグループにまとめられている。実際に検出を行う際には第１ステージから順に評価を行い、顔でないと評価されたステージがあれば、その画像は顔でないと判定し，そのステージで評価を打ち切り、次のステージに進まない。従って、全ステージで顔であると判定されたときに限りその画像を顔であると判定する。ここでは、各ステージを一つのブースティングによって得られた高速判別装置とみなして順序構造学習を行う場合について説明する。
図１２は、カスケード型の高速判別装置の順序構造学習の処理の流れを示すフローチャートである。各ステージ毎に並び替えを行なう以外は、第３の実施の形態の順序構造学習の処理の流れと略同様であるので、図１２に従って相違する点を主に説明する。
【０１２６】
まず、各ステージ毎に所定の順番に並べられた弱判別器群に対して上述のSL(1)、SL(2),SL(3)のいずれかの手法で並び替えを行なえばよいが、ここでは、SL(2)で並び替える場合について説明する。
【０１２７】
まず、Ｎ個のサンプルデータを用意して記憶装置に記憶する（＃３０）。ステージkをステージ１とし、ステージ１から弱判別器群の並び順を探索する（＃３１）。
【０１２８】
ブースティングで選ばれた弱判別器ｆｊの係数絶対値順＾ｋｂを各ステージの並び＾ｋの初期値とする。また、このときのΓk（Ｆ，＾ｋ）をΓkｍｉｎの初期値とする（＃３２）。
【０１２９】
次に、弱判別器交換ステップで、現在のステージの弱判別器群のうちのs番目とt番目の２つの弱判別器を交換する（＃３３）。次に、評価済弱判別器数取得ステップで、Ｎ個のサンプルデータのそれぞれを対象画像データ入力受付手段１１より対象画像データｘとして受け付けて、評価値取得手段１３ｂを実行した後に各ステージにおいて判別結果決定手段１４ｂが弱判別器の評価の打ち切りを指示するまでに評価された弱判別器の数Ｉｋを各サンプルデータごとに取得し、Ｎ個のサンプルデータから平均評価回数Γｋを取得する（＃３４）。
【０１３０】
並び替えステップでは、交換後の平均評価回数Γｋが交換前の平均評価回数Γｋｍｉｎより小さい場合には（＃３５―YES）、現在のステージの弱判別器群の並び順を交換後の並び順に並び替える（＃３６）。交換後の平均評価回数Γｋが交換前の平均評価回数Γｋｍｉｎより大きい場合には、現在のステージの弱判別器群の並び順はそのままにする（＃３５―NO）。
【０１３１】
次に交換するs’番目とt’番目の弱判別器を選ぶ（＃３８）。探索ステップでは、全ての並び替えが終了するまで、再度、弱判別器交換ステップ、評価済弱判別器数取得ステップ、および並び替えステップを繰り返して（＃３７−NO）、平均評価回数Γｋが最小になる現在のステージの弱判別器群の並び順を探索する。全ての並び替えが終了すると次のステージの並び替えに移る（＃３７−YES）。
【０１３２】
まず、現在のステージｋが最後のステージＫではないかを確認して、最後のステージでない場合には（＃３９―NO）、次のステージｋ＋１に進めて（＃４０）、再度、次のステージの弱判別器群の並び順を探索する（＃３３〜＃３８）。
【０１３３】
全てのステージで、平均評価回数Γｋが最小になる弱判別器群の並び順の探索が終了すると順序構造学習は完了する（＃３９―YES）。
【０１３４】
実験４では、カスケード構造の正面顔検出器（高速判別装置）に順序構造学習を行った。表６に各ステージに含まれる弱判別器の数の一覧を示す。
【表６】
【０１３５】
弱判別器の総数が大きいため、順序構造学習はSL(2)を採用した。図１３に、各ステージの弱判別器の数と、ブースティング順＾ｋｂの各ステージの平均評価回数Γｋと、SL(2)による順序構造学習後の各ステージの平均評価回数Γｋを示す。図１４に、ブースティング順＾ｋｂと、SL(2)による順序構造学習後の各ステージで評価される弱判別器の割合（平均評価回数Γｋ／弱判別器の数Ｊ）を示す。各ステージごとに順序構造学習の効果がみられ、どのステージでも順序構造学習によって得られた並び順の方がブースティング順＾ｋｂより、平均評価回数Γｋが小さく速く検出することができている。また最後のステージになるにつれて順序構造学習の効果が大きくなり，平均評価回数で最大で1.5割ほど高速化が図れていることが分かる。
【０１３６】
次に、顔検出時に対象画像データ内に顔検出範囲（以下、探索窓という）を設定して、その探索窓内に顔が存在するか判定しながら、対象画像データ全体を走査することで対象画像データ内の顔を検索する場合の各ステージの棄却率（探索窓内に顔が存在しないと判定されて、その探索窓が棄却される率）について説明する。カスケード型の判別器は、最初のステージから順に評価を行い、顔でないと評価されたステージがあれば、探索窓は棄却される。設定された探索窓が各ステージでどの程度棄却されるかを表す棄却率を図１５に示す。図１５よりステージ5，6までに設定された探索窓の9割が棄却されている。つまり、前半のステージでは多くの探索窓を棄却し、後半のステージでは精密に顔であるかどうか検査していることを示している。
【０１３７】
次に、カスケード構造の正面画像検出器と順序構造学習の検出速度の高速化の効果についてみる。表６に示すカスケード構造のステージ0からステージ6までのステージを統合しステージ0とし、ステージ7…24まではそのままにするが、ステージの番号を振りなおしてステージ1…18とする。この各ステージに対して順序構造学習を行い、統合した正面顔検出器の平均評価回数Γｋを図１６に示す。ステージ0を見ると順序構造学習を行った場合の平均評価回数Γ０は180程度だが、順序構造学習を行わない場合と比べて40程度しか変わっていない。統合する前は9個の弱判別器で構成されたステージ0で40%ほど探索窓を棄却している。従って検出速度の高速化の観点からみると、複数のステージを統合した顔検出器に対して順序構造学習を行う場合より、カスケード構造の方が速いことがわかる。以上より、カスケード構造を採用した上で各ステージに対して順序構造学習を行なった高速判別装置が最も高速に判別を行えるという結論に達する。
【０１３８】
上述の第３および第５の実施の形態の順序構造学習では、Ｎ個のサンプルデータを使って、判別器の評価が打ち切られるまでに評価された判別器の数の平均値を求めて、もっとも早い段階で判別器の評価の打ち切りが行われる判別器群の並び順を探索するようにしたが、平均値ではなく最頻値、中央値などの代表値からもっとも早い段階で判別器の評価の打ち切り行なわれる判別器群の並び順を探索するようにしてもよい。
【０１３９】
次に、第６の実施の形態では、ブースティング学習時と順序構造学習時に用いる学習データ、および性能評価に用いる評価用データについて説明する。本実施の形態の高速判別装置は、第１、第２および第４の実施の形態で説明した高速判別装置のいずれかを用いる。また、順序構造学習は第３および第５の実施の形態で説明した高速判別装置を高速化する方法を用いるものとする。高速判別装置は前述の実施の形態と同じ構成を備え、高速判別装置を高速化する方法でも前述と同じ順番で各ステップが実施されるので、本実施の形態では学習データと評価用データについて詳細に説明する。
【０１４０】
一般的に、学習データセットとして、ラベル付き学習データとラベル無し学習データが用いられることはよく知られている。例えば、顔検出に用いる学習用データの場合、特徴量ｘは機械で自動で大量収集可能であるのに対して、各学習データのラベルｙ（顔有り：１、顔無し：−１）は人手でつけなければならない。そのためラベル付き学習データセットＤＬのサイズを大きくするにはコストがかかると考えられる。一方で特徴量ｘだけの学習データ（ラベル無し学習データ）は大量に手に入れやすい。
【０１４１】
ところで、デジタルカメラで顔検出を実際に行う場合の対象画像データに近い評価データＤＴと、学習に用いられるラベル付き学習データセットＤＬでは、特徴量の分布が異なると考えられる。通常、顔検出のための学習を行う場合には顔画像を多く含む学習データを準備するのが自然であろうが、実際のデジタルカメラで撮影した対象画像データにはそこまで多く常に顔が写っているとは限らないからである。
【０１４２】
そこで、学習データの３つのタイプについて説明する。
（ａ）教師付き学習用データセット
ラベル付き学習データＤＬのみが与えられる。従来から広く用いられてきた設定である。本発明のブースティング学習時に用いられ、弱判別器の選択が行われる。しかし上述したようにデータサイズを大きくするためにはラベルづけのコストがかかる。
（ｂ）半教師付き学習データセット
ラベル付き学習データＤＬとラベル無し学習データＤＵが与えられる。ただし、ＤＵとＤＬが同じ分布に従っている。
（ｃ）共変量シフト学習データセット
ラベル付き学習データＤＬとラベル無し学習データＤＵが与えられる。ただし、ＤＵとＤＬが異なる分布に従っている。
【０１４３】
順序構造学習にはデータの数を増やすため、ラベル付き学習データＤＬとラベル無し学習データＤＵが含まれる半教師付き学習データセット、あるいは共変量シフト学習データセットを使う方法が考えられる。
【０１４４】
ここで、従来の判別装置と上述の各実施の形態で説明した高速判別装置の判別速度について検討する。まず、判別装置を下の４通りに分ける。
(ｉ) viola and jonesらが提案した従来の判別装置（例えば、文献３：Pual.Viola,Michael J.Jones.Rapid Object Detection using a Boosted Cascade of Simple Feature, IEEE Conf. on Computer Vision and Pattern Recognition, 2001.V参照）
(ii) 係数絶対値順に弱判別器を並べて、弱判別器の数γ（第１、第２および第４の実施の形態のＩ、Ｉｋ）で打ち切る高速判別装置（第１、第２および第４の実施の形態の高速判別装置）
(iii) ブースティング順に弱判別器を並べて、弱判別器の数γで打ち切る高速判別装置（第１、第２、および第４の実施の形態の高速判別装置）
(iv)さらに、弱判別器の並び順に対して順序構造学習を行なって、弱判別器の数γで打ち切る高速判別装置（第３および第５の実施の形態の方法によって高速化された高速判別装置）
(ｉ)の従来の判別装置に対しては、(ii)、(iii) 、(iv)の高速判別装置はどんな場合でも必ず同じかそれ以上の判別速度を出すことができる。また、(iv)が一番高速であると考えられるが、順序構造学習をしなくても(ii)、(iii)でも一定程度の高速化が実現可能である。ただし、これは学習データと評価データの分布が同じ場合が前提となる。
【０１４５】
顔検出において学習データと評価データが異なる分布に従うことは不可避である（例えば、文献３参照）。(ｉ)の従来の判別装置においても、顔ではなさそうなものを判断する処理が少ない弱判別器を初段側のステージに用意して初期に顔でないデータは棄却するように構成にしたカスケード構造の判別装置では、学習データと評価データの分布が違うことを想定してカスケード構造を決定している。これは、経験則によるヒューリスティックなものである。
【０１４６】
(ii)、(iii)の係数絶対値順は、弱判別器が十分多様であれば、アダブーストの判別関数は学習データｘの分布Ｐ(ｘ)には依存しないが、高速判別装置が弱判別器の途中で判別を打ち切るときの弱判別器の数γは教師付き学習データセット（ラベル付き学習データ）ｘの分布Ｐ(ｘ)に依存する。そのため、係数絶対値順は最適な並び順とはならない。アダブースト順が最適にならない理由も同様に、アダブーストが教師付き学習データセットを最も改善する弱判別器を選ぶため、高速判別装置が弱判別器の途中で判別を打ち切るときの最適な並び順とはならない。
【０１４７】
それに対して、(iv)の順序構造学習を評価データ（実際にデジタルカメラなどで顔の判別を行なう対象画像データに近い分布のデータ）と同じ分布に従うラベル無し学習データで学習を行うことができれば、(i)〜(iii)をかなり上回る性能が期待できる。
【０１４８】
まず、分布Ｐ１(x)のラベル付き学習データセットＤＬ:= {(ｘｉ, ｙｉ) | ｉ＝1, 2, ・ ・ ・ , n}と、ラベル付き学習データセットＤＬとは独立なラベル無し学習データセットとして分布Ｐ１(x) に従うＤ１Ｕ:= {ｘ１, ｘ２, ・・・, ｘｎｕ} と分布Ｐ２(x) に従うＤ２Ｕ:= {ｘ１, ｘ２, ・・・, ｘｎｕ} を用意する。さらにＤＬ, Ｄ１Ｕ, Ｄ２Ｕと独立な評価用データセットとして分布Ｐ１(x)に従うＤ１T:= {ｘ１, ｘ２, ・・・, ｘｎｔ } と、分布Ｐ２(x)に従うＤ２T:= {ｘ１, ｘ２, ・・・, ｘｎｔ} を用意する。学習データの分布Ｐ１(x)と分布Ｐ２(x)は異なる分布を表し、Ｐ１(x)はブースティング学習に用いられるデータの分布と略一致する分布を表し、Ｐ２(x)は、実際に顔の判別を行なう対象画像データの分布と略一致する分布を表すものとする。この実験ではｎ＝300, ｎｕ＝300, ｎｔ＝1200 とした。
【０１４９】
最初にデータＤＬを用いてブースティング学習を行う。その結果得られた判別関数を
【数３８】
とする（ここでは、第１の実施の形態と同じ判別関数を例に説明する）。以降全ての実験において同じ判別関数を用いるものとする。この判別関数Ｆ（ｘ）について下表に示した４種類の実験（表の実験２は、第３の実施の形態の実験２と同じである）を行った。これらの実験の意図は下で説明する。性能評価は評価用データセットＤ１T あるいはＤ２T を用いて計算されたΓ(F)/Ｊで行った。ＤｘＬはＤＬの特徴量だけの集合をさす。以下、ブースティング学習に用いるデータを学習データセットといい、順序構造学習に用いるデータをサンプルデータセットとして区別する。
【表７】
上表の実験ではいずれも順序構造学習にSL(2)を用いる。
【０１５０】
実験２では、順序構造学習に学習データセットと同じデータをサンプルデータセットＤｘＬとして用い、評価用には学習データセットと同じ分布の評価用データＤ１Tを用いた。実験２の結果を図１０に示す。数が増えるに従って高速化の効果が表れていることがわかる。大体弱判別器の数Ｊ＝２０，・・・，５０ぐらいから評価される弱判別器の総数の１割ほど早くなる。
【０１５１】
実験５では、順序構造学習に学習データセットと同じデータをサンプルデータセットＤｘＬとして用い、評価用には学習データセットと異なる分布の評価用データセットＤ２Tを用いた。実験５の結果を図１７に示す。
実験２，５はともにブースティング順は係数絶対値順に似た挙動を示している。また両者は実験２，５であまり結果が変わらないことがわかる。その一方で順序構造学習は実験２に比べて実験５では、弱判別器の数が増えると結果が安定していない。これは学習時と評価時でデータの分布が変わっている影響が出ているためであると考えられる。
【０１５２】
実験６では、順序構造学習に学習データセットと同じデータのサンプルデータセットＤｘＬと学習データセットと同じ分布であるが学習データとは独立なサンプルデータセットＤ１Ｕを用い、評価用には学習データセットと同じ分布であるが学習データとは独立な評価用データセットＤ１Tを用いた。実験６の結果を図１８に示す。
順序構造学習を行うと、データ数が増えているため早期から安定して高速化できている。ただし実験２と同様に、学習データセットとサンプルデータセットが同じ分布に従い、学習データセット・サンプルデータセットと同じ分布の評価用データセットＤ１Tを用いるため、弱判別器の数が増えても改良の度合いが増加していない。
【０１５３】
実験７は、順序構造学習に学習データセットと異なる分布のサンプルデータセットＤ２Ｕを用い、評価用にも学習データセットと異なる分布の評価用データセットＤ２Tを用いる。実験７の結果を図１９に示す。
順序構造学習による高速化が著しいことが見て取れる。この理由は共変量シフトを起こしている場合、係数絶対値順やブースティング順が重要であると考えた判別装置の優先順位が予想を外すこととなる。ただしブースティングの学習アルゴリズムを共変量シフトに拡張すればここまで差が生じることはないと考えられる。
【０１５４】
ブースティング学習においては、ラベル付きの学習データしか学習できない。そのためブースティング学習に用いる学習データセットのサイズを大きくするにはコストがかかる。順序構造学習においては、順序構造を学習(弱判別器の順序のみに着目)しているので、学習データのラベルは必須ではなくなり、ラベル付き、ラベル無のどちらでも高速化のための学習が可能となる。そのため、順序構造学習に用いる学習データセットのサイズを大きくするのは比較的容易に行なえる。
【０１５５】
デジタルカメラで顔検出を実際に行う場合の対象画像データと、ブースティング学習に用いられるラベル付き学習データとでは、特徴量の分布が異なると考えられる。そこで、順序構造学習でブースティングを行なう際の学習データとは異なる分布のサンプルデータ、つまり実際に判別を行う対象画像データに近い分布のサンプルデータを用いることで、その違いを考慮した並び順に弱判別器を並び替えて高速判別装置の高速化を図ることが可能になる。
具体的には、上記実施形態で説明したように、ラベル無しの半教師付き学習や、共変量シフトの分布特性を持つサンプルデータを順序構造学習に適用することで、更に、係数絶対値順、アダブースト順より高速となるように高速判別装置の弱判別器を並び替えることが可能になる。
【０１５６】
本実施の形態では、弱判別器が−１、１の２値を取る場合について説明をしたが、第２の実施の形態のように２値の実数を取る場合についても、ラベル無しの半教師付き学習や、共変量シフトの分布特性を持つサンプルデータを順序構造学習に適用することで、より高速となるように高速判別装置の弱判別器を並び替えることが可能になる。
【０１５７】
上述では、顔の検出について具体的に説明を行なったが、オブジェクトが人物の手などの人体の外観の一部の部位、あるいは人体の外観ではなく生体内の少なくとも一部の部位を含む領域であってもよい。対象画像データが内視鏡システムや顕微鏡などで撮影した画像の場合には、オブジェクトは、生体内部の腫瘍組織、細胞、タンパク質、DNA・RNAなどの高分子、低分子、であってもよい。生体の他にも、顕微鏡などで撮影された薬などの化合物やタンパク質などであってもよい。あるいは、デジタルスチールカメラなどの撮影装置によって対象画像データに撮影された貨幣、キャッシュカードなどのカード、車輌、あるいは車両のナンバープレートなどであってもよい。また、対象画像データが、複写機などのスキャナ機器によりスキャニングされた画像である場合には、オブジェクトがドキュメントの文字、図面、表、写真などであてもよい。さらに、オブジェクトは、画像データを統計的分析したときに統計的偏りのある群であればよく、例えば、テクスチャであってもよい。
【０１５８】
上述では、対象データが画像データである場合について説明したが、音のデータ、文字データ、生体データ、自然・物理データなどでもよい。具体的には、音のデータから音声、生体の音、生き物の声（動物、鳥、昆虫）、楽器の音、乗り物の音などを検索するときに上述の高速判別装置を用いることができる。
また、音声データや文字データには、日本語や英語などの種々の言語の情報からなる言語データが含まれる。言語データからは、例えば、地域の方言の判別、用途（ニュースのようなフォーマルなデータであるかインフォーマルなデータであるか）の判別、書かれた（あるいは、話された）時代（平安、江戸、現代）の判別、書いた（あるいは、話している）世代（高校生、年輩）の判別をおこなうときに上述の高速判別装置を用いることができる。
さらに、生体データは、心拍、脈拍、血圧、呼吸、発汗の波形や周期、振幅などを計測したデータであってもよい。さらにまた、自然・物理データとして、天候、気候、地震の波形や周期、振幅などを計測したデータであってもよい。
【０１５９】
上述では、判別器が弱判別器である場合について説明したが、判別器群には誤判別率が低いものが含まれていても良い。
【０１６０】
上述では、ブースティングを例に説明したが、バギングにより構成された判別器群であってもよい。
【符号の説明】
【０１６１】
１，１ａ，１ｂ 高速判別装置
１１ 対象画像データ入力受付手段
１２，１２ａ，１２ｂ 判別器記憶手段
１３，１３ａ，１３ｂ 評価値取得手段
１４，１４ａ，１４ｂ 判別結果決定手段
【特許請求の範囲】
【請求項１】
判別対象の対象データに所定のオブジェクトが含まれるか否かを判別した判別結果を得る高速判別装置であって、
前記対象データｘの入力を受け付ける対象データ入力受付手段と、
所定の順番に並べられた、前記対象データｘに前記オブジェクトが含まれるか否かを評価する複数個の判別器ｆｊ（ｊ＝１〜Ｊ）からなる判別器群と、
前記複数個の判別器のうちの１番目の判別器から順に各判別器を用いて前記対象データｘを評価した評価値ｆｊ（ｘ）を求め、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）（ｊ＝１〜ｉ）から得られた総合評価値Ｆｉ（ｘ）をｉ＝１からＪまで順に得る評価値取得手段と、
前記評価値取得手段によってｉ＝Ｉ（Ｉ＜Ｊ）番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が示す前記判別結果が、Ｉ＋１番目以降の各判別器が取り得る評価値の範囲に基づいて、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩ（ｘ）にＩ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定する判別結果決定手段とを備えたことを特徴とする高速判別装置。
【請求項２】
前記判別器群が、前記複数の判別器ｆｊとともに、該判別器のそれぞれに対する重みαｊとを記憶するものであり、
前記評価値取得手段が、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）と各判別器の重みαｊとを線形結合した総合評価値Ｆｉ（ｘ）
【数３９】
をｉ＝１からＪまで順に得るものであることを特徴とする請求項１記載の高速判別装置。
【請求項３】
前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩが条件１
【数４０】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであることを特徴とする請求項２記載の高速判別装置。
【請求項４】
前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩが条件２
【数４１】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであることを特徴とする請求項２記載の高速判別装置。
【請求項５】
前記評価値取得手段が、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）を線形結合した総合評価値Ｆｉ（ｘ）
【数４２】
をｉ＝１からＪまで順に得るものであることを特徴とする請求項１記載の高速判別装置。
【請求項６】
前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件３−１または条件４−１
【数４３】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであることを特徴とする請求項５記載の高速判別装置。
【請求項７】
前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件５−１または条件６−１
【数４４】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであることを特徴とする請求項５記載の高速判別装置。
【請求項８】
前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件３−２または条件４−２
【数４５】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであることを特徴とする請求項５記載の高速判別装置。
【請求項９】
前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件５−２または条件６−２
【数４６】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであることを特徴とする請求項５記載の高速判別装置。
【請求項１０】
前記判別結果は、前記総合評価値Ｆｉ（ｘ）の符号に応じて決定されることを特徴とする請求項２〜９いずれか１項記載の高速判別装置。
【請求項１１】
前記判別器群が、Ｋ個のステージに分けられるとともに、各ステージ毎に所定の順番で並べられたJｋ（ｋ＝１〜Ｋ）個の判別器からなる判別器群が含まれるものであり、
前記評価値取得手段が、前記各ステージ毎に１番目から順に前記総合評価値Ｆｉ（ｘ）を各ステージのｉ＝１からＪｋまで順に得るものであり、
前記判別結果決定手段が、前記評価値取得手段によって、各ステージのｉ＝Ｉｋ（Ｉｋ＜Ｊｋ）番目までの判別器を評価して得られた前記総合評価値ＦｋI（ｘ）が示す前記判別結果が、各ステージに含まれるＩｋ＋１番目以降の各判別器が取り得る評価値の範囲に基づいて、前記Ｉｋ番目までの判別器を評価して得られた総合評価値ＦｋI（ｘ）にＩｋ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、前記評価値取得手段に各ステージのＩｋ＋１番目以降の判別器の評価の打ち切りを指示するとともに、前記Ｉｋ番目までの判別器を評価して得られた総合評価値ＦｋＩに応じた前記判別結果を各ステージの最終結果として決定するものであることを特徴とする請求項１記載の高速判別装置。
【請求項１２】
請求項１記載の高速判別装置を高速化するための方法であって、
Ｎ個のサンプルデータを記憶するサンプルデータ記憶ステップと、
前記所定の順番に並べられた複数の判別器からなる判別器群の２以上の判別器を交換して並び替えを行う判別器交換ステップと、
該判別器交換ステップによる交換前と交換後の並び順の判別器群のそれぞれにおいて、前記Ｎ個のサンプルデータのそれぞれを前記対象データ入力受付手段より対象データｘとして受け付けて、前記評価値取得手段を実行した後に前記判別結果決定手段が前記判別器の評価の打ち切りを指示するまでに評価された判別器の数Ｉを各サンプルデータごとに取得し、前記Ｎ個のサンプルデータの前記評価された判別器の数の代表値を取得する評価済判別器数取得ステップと、
前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より小さい場合には、前記判別器群の並び順を前記交換後の並び順に並び替えて前記判別器群に記憶し、前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より大きい場合には、前記判別器群に記憶されている前記判別器群の並び順をそのままとする並び替えステップと、
前記判別器交換ステップ、前記評価済判別器数取得ステップ、および前記並び替えステップを繰り返して、前記評価された判別器の数の代表値が最小となる前記判別器群の並び順を探索する探索ステップと、を備えたことを特徴とする高速判別装置を高速化するための方法。
【請求項１３】
請求項１１記載の高速判別装置を高速化するための方法であって、
Ｎ個のサンプルデータを記憶するサンプルデータ記憶ステップと、
前記各ステージ毎に所定の順番に並べられた複数の判別器からなる判別器群の２以上の判別器を交換して並び替えを行う判別器交換ステップと、
該判別器交換ステップによる交換前と交換後の並び順の判別器群のそれぞれにおいて、前記Ｎ個のサンプルデータのそれぞれを前記対象データ入力受付手段より対象データｘとして受け付けて、前記評価値取得手段を実行した後に各ステージにおいて前記判別結果決定手段が前記判別器の評価の打ち切りを指示するまでに評価された判別器の数Ｉｋを各サンプルデータごとに取得し、前記Ｎ個のサンプルデータの前記評価された判別器の数の代表値を各ステージ毎に取得する評価済判別器数取得ステップと、
前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より小さい場合には、前記各ステージの判別器群の並び順を前記交換後の並び順に並び替えて前記判別器群に記憶し、前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より大きい場合には、前記各ステージの判別器群に記憶されている前記判別器群の並び順をそのままとする並び替えステップと、
前記判別器交換ステップ、前記評価済判別器数取得ステップ、および前記並び替えステップを繰り返して、前記評価された判別器の数の代表値が最小となる前記各ステージの判別器群の並び順を探索する探索ステップと、を備えたことを特徴とする高速判別装置を高速化するための方法。
【請求項１４】
前記判別器交換ステップが、前記所定の順番に並べられた複数の判別器からなる判別器群のうちの任意の２つの判別器を交換するものであり、
前記探索ステップが、前記判別器交換ステップにおいて前記交換した２つの判別器の全ての組み合わせについて、前記評価済判別器数取得ステップ、および前記並び替えステップを繰り返して、前記評価された判別器の数の代表値が最小となる前記判別器群の並び順を探索することを特徴とする請求項１２または１３記載の高速判別装置を高速化するための方法。
【請求項１５】
前記サンプルデータには、ラベル無学習データを含むことを特徴とする請求項１２〜１４いずれか１項記載の高速判別装置を高速化するための方法。
【請求項１６】
前記判別器群は、所定の分布Ｐ１に従う学習データを用いて学習を行うことにより選択されたものであり、
前記サンプルデータには、前記分布Ｐ１とは異なる分布Ｐ２の学習データを含むことを特徴とする請求項１２〜１５いずれか１項記載の高速判別装置を高速化するための方法。
【請求項１７】
前記分布Ｐ２が前記対象データの分布に近い分布を表すものであることを特徴とする請求項１６記載の高速判別装置を高速化するための方法。
【請求項１８】
判別対象の対象データに所定のオブジェクトが含まれるか否かを判別した判別結果を得る高速判別装置のプログラムであって、
コンピュータを、
前記対象データｘの入力を受け付ける対象データ入力受付手段と、
所定の順番に並べられた、前記対象データｘに前記オブジェクトが含まれるか否かを評価する複数個の判別器ｆｊ（ｊ＝１〜Ｊ）からなる判別器群と、
前記複数個の判別器のうちの１番目の判別器から順に各判別器を用いて前記対象データｘを評価した評価値ｆｊ（ｘ）を求め、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）（ｊ＝１〜ｉ）から得られた総合評価値Ｆｉ（ｘ）をｉ＝１からＪまで順に得る評価値取得手段と、
前記評価値取得手段によってｉ＝Ｉ（Ｉ＜Ｊ）番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が示す前記判別結果が、Ｉ＋１番目以降の各判別器が取り得る評価値の範囲に基づいて、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩ（ｘ）にＩ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定する判別結果決定手段として機能させる高速判別装置のプログラム。
【請求項１】
判別対象の対象データに所定のオブジェクトが含まれるか否かを判別した判別結果を得る高速判別装置であって、
前記対象データｘの入力を受け付ける対象データ入力受付手段と、
所定の順番に並べられた、前記対象データｘに前記オブジェクトが含まれるか否かを評価する複数個の判別器ｆｊ（ｊ＝１〜Ｊ）からなる判別器群と、
前記複数個の判別器のうちの１番目の判別器から順に各判別器を用いて前記対象データｘを評価した評価値ｆｊ（ｘ）を求め、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）（ｊ＝１〜ｉ）から得られた総合評価値Ｆｉ（ｘ）をｉ＝１からＪまで順に得る評価値取得手段と、
前記評価値取得手段によってｉ＝Ｉ（Ｉ＜Ｊ）番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が示す前記判別結果が、Ｉ＋１番目以降の各判別器が取り得る評価値の範囲に基づいて、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩ（ｘ）にＩ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定する判別結果決定手段とを備えたことを特徴とする高速判別装置。
【請求項２】
前記判別器群が、前記複数の判別器ｆｊとともに、該判別器のそれぞれに対する重みαｊとを記憶するものであり、
前記評価値取得手段が、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）と各判別器の重みαｊとを線形結合した総合評価値Ｆｉ（ｘ）
【数３９】
をｉ＝１からＪまで順に得るものであることを特徴とする請求項１記載の高速判別装置。
【請求項３】
前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩが条件１
【数４０】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであることを特徴とする請求項２記載の高速判別装置。
【請求項４】
前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩが条件２
【数４１】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであることを特徴とする請求項２記載の高速判別装置。
【請求項５】
前記評価値取得手段が、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）を線形結合した総合評価値Ｆｉ（ｘ）
【数４２】
をｉ＝１からＪまで順に得るものであることを特徴とする請求項１記載の高速判別装置。
【請求項６】
前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件３−１または条件４−１
【数４３】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであることを特徴とする請求項５記載の高速判別装置。
【請求項７】
前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件５−１または条件６−１
【数４４】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであることを特徴とする請求項５記載の高速判別装置。
【請求項８】
前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件３−２または条件４−２
【数４５】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであることを特徴とする請求項５記載の高速判別装置。
【請求項９】
前記判別結果決定手段が、前記評価値取得手段によってＩ番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が、条件５−２または条件６−２
【数４６】
を満足する場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定するものであることを特徴とする請求項５記載の高速判別装置。
【請求項１０】
前記判別結果は、前記総合評価値Ｆｉ（ｘ）の符号に応じて決定されることを特徴とする請求項２〜９いずれか１項記載の高速判別装置。
【請求項１１】
前記判別器群が、Ｋ個のステージに分けられるとともに、各ステージ毎に所定の順番で並べられたJｋ（ｋ＝１〜Ｋ）個の判別器からなる判別器群が含まれるものであり、
前記評価値取得手段が、前記各ステージ毎に１番目から順に前記総合評価値Ｆｉ（ｘ）を各ステージのｉ＝１からＪｋまで順に得るものであり、
前記判別結果決定手段が、前記評価値取得手段によって、各ステージのｉ＝Ｉｋ（Ｉｋ＜Ｊｋ）番目までの判別器を評価して得られた前記総合評価値ＦｋI（ｘ）が示す前記判別結果が、各ステージに含まれるＩｋ＋１番目以降の各判別器が取り得る評価値の範囲に基づいて、前記Ｉｋ番目までの判別器を評価して得られた総合評価値ＦｋI（ｘ）にＩｋ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、前記評価値取得手段に各ステージのＩｋ＋１番目以降の判別器の評価の打ち切りを指示するとともに、前記Ｉｋ番目までの判別器を評価して得られた総合評価値ＦｋＩに応じた前記判別結果を各ステージの最終結果として決定するものであることを特徴とする請求項１記載の高速判別装置。
【請求項１２】
請求項１記載の高速判別装置を高速化するための方法であって、
Ｎ個のサンプルデータを記憶するサンプルデータ記憶ステップと、
前記所定の順番に並べられた複数の判別器からなる判別器群の２以上の判別器を交換して並び替えを行う判別器交換ステップと、
該判別器交換ステップによる交換前と交換後の並び順の判別器群のそれぞれにおいて、前記Ｎ個のサンプルデータのそれぞれを前記対象データ入力受付手段より対象データｘとして受け付けて、前記評価値取得手段を実行した後に前記判別結果決定手段が前記判別器の評価の打ち切りを指示するまでに評価された判別器の数Ｉを各サンプルデータごとに取得し、前記Ｎ個のサンプルデータの前記評価された判別器の数の代表値を取得する評価済判別器数取得ステップと、
前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より小さい場合には、前記判別器群の並び順を前記交換後の並び順に並び替えて前記判別器群に記憶し、前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より大きい場合には、前記判別器群に記憶されている前記判別器群の並び順をそのままとする並び替えステップと、
前記判別器交換ステップ、前記評価済判別器数取得ステップ、および前記並び替えステップを繰り返して、前記評価された判別器の数の代表値が最小となる前記判別器群の並び順を探索する探索ステップと、を備えたことを特徴とする高速判別装置を高速化するための方法。
【請求項１３】
請求項１１記載の高速判別装置を高速化するための方法であって、
Ｎ個のサンプルデータを記憶するサンプルデータ記憶ステップと、
前記各ステージ毎に所定の順番に並べられた複数の判別器からなる判別器群の２以上の判別器を交換して並び替えを行う判別器交換ステップと、
該判別器交換ステップによる交換前と交換後の並び順の判別器群のそれぞれにおいて、前記Ｎ個のサンプルデータのそれぞれを前記対象データ入力受付手段より対象データｘとして受け付けて、前記評価値取得手段を実行した後に各ステージにおいて前記判別結果決定手段が前記判別器の評価の打ち切りを指示するまでに評価された判別器の数Ｉｋを各サンプルデータごとに取得し、前記Ｎ個のサンプルデータの前記評価された判別器の数の代表値を各ステージ毎に取得する評価済判別器数取得ステップと、
前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より小さい場合には、前記各ステージの判別器群の並び順を前記交換後の並び順に並び替えて前記判別器群に記憶し、前記交換後に前記評価された判別器の数の代表値が前記交換前に前記評価された判別器の数の代表値より大きい場合には、前記各ステージの判別器群に記憶されている前記判別器群の並び順をそのままとする並び替えステップと、
前記判別器交換ステップ、前記評価済判別器数取得ステップ、および前記並び替えステップを繰り返して、前記評価された判別器の数の代表値が最小となる前記各ステージの判別器群の並び順を探索する探索ステップと、を備えたことを特徴とする高速判別装置を高速化するための方法。
【請求項１４】
前記判別器交換ステップが、前記所定の順番に並べられた複数の判別器からなる判別器群のうちの任意の２つの判別器を交換するものであり、
前記探索ステップが、前記判別器交換ステップにおいて前記交換した２つの判別器の全ての組み合わせについて、前記評価済判別器数取得ステップ、および前記並び替えステップを繰り返して、前記評価された判別器の数の代表値が最小となる前記判別器群の並び順を探索することを特徴とする請求項１２または１３記載の高速判別装置を高速化するための方法。
【請求項１５】
前記サンプルデータには、ラベル無学習データを含むことを特徴とする請求項１２〜１４いずれか１項記載の高速判別装置を高速化するための方法。
【請求項１６】
前記判別器群は、所定の分布Ｐ１に従う学習データを用いて学習を行うことにより選択されたものであり、
前記サンプルデータには、前記分布Ｐ１とは異なる分布Ｐ２の学習データを含むことを特徴とする請求項１２〜１５いずれか１項記載の高速判別装置を高速化するための方法。
【請求項１７】
前記分布Ｐ２が前記対象データの分布に近い分布を表すものであることを特徴とする請求項１６記載の高速判別装置を高速化するための方法。
【請求項１８】
判別対象の対象データに所定のオブジェクトが含まれるか否かを判別した判別結果を得る高速判別装置のプログラムであって、
コンピュータを、
前記対象データｘの入力を受け付ける対象データ入力受付手段と、
所定の順番に並べられた、前記対象データｘに前記オブジェクトが含まれるか否かを評価する複数個の判別器ｆｊ（ｊ＝１〜Ｊ）からなる判別器群と、
前記複数個の判別器のうちの１番目の判別器から順に各判別器を用いて前記対象データｘを評価した評価値ｆｊ（ｘ）を求め、１番目からｉ番目までの判別器の評価値ｆｊ（ｘ）（ｊ＝１〜ｉ）から得られた総合評価値Ｆｉ（ｘ）をｉ＝１からＪまで順に得る評価値取得手段と、
前記評価値取得手段によってｉ＝Ｉ（Ｉ＜Ｊ）番目までの判別器を評価して得られた前記総合評価値ＦＩ（ｘ）が示す前記判別結果が、Ｉ＋１番目以降の各判別器が取り得る評価値の範囲に基づいて、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩ（ｘ）にＩ＋１番目以降の判別器の評価値を加えても変わらないと判定された場合には、前記評価値取得手段にＩ＋１番目以降の判別器の評価の打ち切りを指示するとともに、前記Ｉ番目までの判別器を評価して得られた総合評価値ＦＩに応じた前記判別結果を最終結果として決定する判別結果決定手段として機能させる高速判別装置のプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公開番号】特開２０１３−４１３１２（Ｐ２０１３−４１３１２Ａ）
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願番号】特願２０１１−１６５１７３（Ｐ２０１１−１６５１７３）
【出願日】平成２３年７月２８日（２０１１．７．２８）
【出願人】（３０６０３７３１１）富士フイルム株式会社 (25,513)
【Ｆターム（参考）】
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願日】平成２３年７月２８日（２０１１．７．２８）
【出願人】（３０６０３７３１１）富士フイルム株式会社 (25,513)
【Ｆターム（参考）】
[ Back to top ]