(57)【特許請求の範囲】
【請求項１】
画像から特定被写体を検出する特定被写体検出装置において、
画像入力手段と、
前記画像入力手段から入力された画像を判別する木構造検出器であって、ルートノードは、分岐される全ての対象物の向きに対応するサブ対象物空間を含み、前記ルートノードから分岐する子ノードは少なくとも１つの対象物の向きに対応するサブ対象物空間を含み、前記ルートノードと前記子ノードの各ノードは複数の弱判別器を含み、各弱判別器の出力を分割するサブ対象物空間毎に集計して、隣接する下層の子ノードのどこに移行するか判定する木構造検出器と、
を有し、
弱判別器は、
ハール特徴が取り得る値の空間を所定の幅で分割することで規定される複数の級と、各々の級に対応する信頼度とを対応付けているルックアップテーブルを有しており、
前記画像から得られたハール特徴の値を前記ルックアップテーブルに適用して、対応する信頼度を出力するものであり、
級への分割の細かさであるルックアップテーブルの粒度は、前記木構造検出器の初めの層における弱判別器のルックアップテーブルほうが、前記木構造検出器の後の層における弱判別器のルックアップテーブルよりも、細かいことを特徴とする特定被写体検出装置。
【請求項２】
弱判別器は、
異なる顔向きを判別するための複数のルックアップテーブルを有しており、
前記画像から得られた１つのハール特徴の値を前記複数のルックアップテーブルに適用し、各ルックアップテーブルから得られる複数の信頼度を出力するものであることを特徴とする請求項１に記載の特定被写体検出装置。
【請求項３】
１つのサブ対象物空間にまで分割された葉ノードに接続する非分岐のカスケード判別器
をさらに含み、
前記カスケード判別器は非対象物を排除することで、前記サブ対象物空間が示す向きの対象物を検出することを特徴とする請求項１又は２に記載の特定被写体検出装置。
【請求項４】
前記木構造検出器は幅優先探索を行うことを特徴とする請求項１〜３のいずれかに記載の特定被写体検出装置。
【請求項５】
前記ルートノードまたは前記子ノードから、どの隣接する下層の子ノードに分岐させるかを決定するために、ベクトルブースティングアルゴリズムを用いて学習することを特徴とする請求項１〜４のいずれかに記載の特定被写体検出装置。
【請求項６】
前記特定被写体及び前記対象物は顔であることを特徴とする請求項１〜５のいずれかに記載の特定被写体検出装置。
【請求項７】
前記ノードはそれぞれ１つの強判別器を含み、前記強判別器の判別は複数の弱判別器の出力値によって決まることを特徴とする請求項１〜６のいずれかに記載の特定被写体検出装置。
【請求項８】
前記サブ対象物空間は検出する対象物の平面内回転及び／又は平面外回転を含み、対象物の複数の向きに分割されていることを特徴とする請求項１〜７のいずれかに記載の特定被写体検出装置。
【請求項９】
前記ルートノードは±９０°の平面外回転によるサブ対象物空間を含むことを特徴とする請求項８に記載の特定被写体検出装置。
【請求項１０】
前記ルートノードは±４５°の平面内回転によるサブ対象物空間を含むことを特徴とする請求項８又は９に記載の特定被写体検出装置。
【請求項１１】
前記木構造検出器または前記入力された画像を９０°、１８０°、２７０°回転させることで、３６０°の平面内回転の対象物の向きを判別できることを特徴とする請求項８〜１０のいずれかに記載の特定被写体検出装置。
【請求項１２】
前記木構造検出器によって対象物が検出されたか否かを示すデータ及び／又は検出された対象物の位置や大きさなどを示すデータを出力する出力手段をさらに含むことを特徴とする請求項１〜１１のいずれかに記載の特定被写体検出装置。
【請求項１３】
画像から特定被写体を検出する特定被写体検出方法であって、
情報処理装置が、
入力された画像を木構造検出器のルートノードに入力するステップと、
前記木構造検出器の前記ルートノードと子ノードのうち分岐する各ノードにおいて、前記画像を複数の弱判別器に入力し、各弱判別器の出力を分割するサブ対象物空間毎に集計し、隣接する下層の子ノードのどこに移行するか判別するステップと
を実行するものであり、
弱判別器は、
ハール特徴が取り得る値の空間を所定の幅で分割することで規定される複数の級と、各々の級に対応する信頼度とを対応付けているルックアップテーブルを有しており、
前記画像から得られたハール特徴の値を前記ルックアップテーブルに適用して、対応する信頼度を出力するものであり、
級への分割の細かさであるルックアップテーブルの粒度は、前記木構造検出器の初めの層における弱判別器のルックアップテーブルほうが、前記木構造検出器の後の層における
弱判別器のルックアップテーブルよりも、細かいことを特徴とする特定被写体検出方法。
【請求項１４】
画像から特定被写体を検出する木構造検出器を構築する方法であって、
情報処理装置が、
画像を判別するノードを木構造に構成するステップと、
前記木構造のルートノードは分割された全ての対象物の向きのサブ対象物空間を含み、かつ複数の分岐を有しており、各分岐は１つの子ノードに接続し、この子ノードは少なくとも１つの対象物の向きに対応するサブ対象物空間を含むように構成するステップと、
２つ以上の前記サブ対象物空間を含む子ノードは複数の分岐を有しており、各分岐は隣接する下層の子ノードに接続し、各隣接する下層の子ノードは少なくとも１つの前記サブ対象物空間を含むように構成するステップと、
１つのサブ対象物空間を含む子ノードは木構造の葉ノードになるように構成するステップと、
前記ルートノードと前記子ノードのうち分岐する各ノードにおいて、画像を複数の弱判別器に入力し、各弱判別器の出力を分割するサブ対象物空間毎に集計し、隣接する下層の子ノードのどこに移行するか判別させるように構成するステップと
を実行するものであり、
弱判別器は、
ハール特徴が取り得る値の空間を所定の幅で分割することで規定される複数の級と、各々の級に対応する信頼度とを対応付けているルックアップテーブルを有しており、
前記画像から得られたハール特徴の値を前記ルックアップテーブルに適用して、対応する信頼度を出力するものであり、
級への分割の細かさであるルックアップテーブルの粒度は、前記木構造検出器の初めの層における弱判別器のルックアップテーブルほうが、前記木構造検出器の後の層における弱判別器のルックアップテーブルよりも、細かいことを特徴とする木構造検出器を構築する方法。
【請求項１５】
画像から特定被写体を検出する特定被写体検出プログラムであって、
情報処理装置に、
画像入力手段から入力された画像を木構造検出器のルートノードに入力させるステップと、
前記ルートノードと子ノードのうち分岐する各ノードにおいて、前記画像を複数の弱判別器に入力し、各弱判別器の出力を分割するサブ対象物空間毎に集計し、隣接する下層の子ノードのどこに移行するか判定させるステップとを実行させるものであり、
弱判別器は、
ハール特徴が取り得る値の空間を所定の幅で分割することで規定される複数の級と、各々の級に対応する信頼度とを対応付けているルックアップテーブルを有しており、
前記画像から得られたハール特徴の値を前記ルックアップテーブルに適用して、対応する信頼度を出力するものであり、
級への分割の細かさであるルックアップテーブルの粒度は、前記木構造検出器の初めの層における弱判別器のルックアップテーブルほうが、前記木構造検出器の後の層における弱判別器のルックアップテーブルよりも、細かいことを特徴とする特定被写体検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、撮像された画像から、この画像中に含まれている人物や動物や物体などの特定の被写体又は被写体の一部を検出する装置及び方法などに適用されて有効な技術に関する。
【背景技術】
【０００２】
従来の技術として、撮像された画像から、この画像中に含まれている人物や動物や物体などの特定の被写体又は被写体の一部を検出するものがある。このような従来の技術の一例として、撮像された画像から人物の顔を検出する技術、即ち顔の検出技術がある。
【０００３】
顔の検出（face detection）とは、任意の画像に対して、コンピュータによる一定の処理によりサーチを行うことで顔が含まれているか否かを判定する処理である。
【非特許文献１】H. A.Rowley, “Neural Network-based Human Face Detection”, Ph.D. thesis,Carnegie Mellon Uni-versity, May 1999.
【非特許文献２】H.Schneiderman and T. Kanade, “A Statistical Method for 3D ObjectDetection Applied to Faces and Cars”. CVPR 2000.
【非特許文献３】RongXiao, Long Zhu, Hongjiang Zhang, Boosting Chain Learning for Object Detection,ICCV 2003.
【非特許文献４】C.Liu andH. Y. Shum, “Kullback-Leibler Boosting”, CVPR 2003.
【非特許文献５】S. Z. Li,L. Zhu, Z. Q. Zhang, et al., “Statistical Learn-ing of Multi-ViewFace Detection”. ECCV 2002.
【非特許文献６】Jones andViola, “Fast Multi-view Face Detection”. MERL-TR2003-96, July 2003.
【非特許文献７】Bo Wu,Haizhou Ai, Chang Huang, and Shihong Lao, Fast rotation invariant multi-viewface detection based on real adaboost, FG 2004.
【非特許文献８】R. E.Schapire and Y. Singer, “Improved Boosting Algo-rithms UsingConfidence-rated Predictions”, Ma-chine Learning, 37, 1999,297-336.
【非特許文献９】Y. Freundand R. E. Schapire, “Experiments with a New BoostingAlgorithm”. In Proc. of the 13-th Conf. on Machine Learning, Morgan Kaufmann, 1996,148-156.
【非特許文献１０】R.E. Schapire, Y. Freund, P. Bartlettand W.S. Lee, “Boosting the margin: A new explanation forthe effectiveness of voting methods”, The Annals ofStatistics, 26(5), 1998, 1651-1686.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
顔の検出には２つの難点がある。１つ目は顔の内在的な変化、例えば顔の形が異なることである。２つ目は顔の外在的な変化、例えば平面内での回転である。よって、リアルタイムアプリケーションを実現できる適切なアルゴリズムを見つけてはじめて、実際に適用価値のある顔の検出装置を構成でき、さらに実際に適用価値のある特定被写体検出装置を構成できる。
【０００５】
顔の検出の実用性は検出精度及び検出速度という双方の向上によるものである。しかしながら、精度は向上している一方で、速度が向上しないことが顔の検出の実用化を阻止している。顔の検出に関する先行技術、例えば、Rowley氏のANN方法（非特許文献１参照）
と、ベイズ決定則によるSchneiderman氏の方法（非特許文献２参照）は共に高精度である
。しかし、その膨大な演算の量によって、それらの適用は非常に限られている。ここで言及するのは、Schneiderman氏は顔の向きを左向きと正面と右向きに分けて、ベイジアン（Bayesian）方法及びウェーブレット変換（wavelettransform）により顔向きによる３つの検出器を学習して、３つの検出器の結果を合わせて最終の結果を得るようにした。Schneiderman氏の検出器は演算が複雑で、速度がとても遅い代わりに、顔向きの違いによる顔の検出に大いに貢献した。
【０００６】
速度の問題はカスケード判別器が提案されたことにより進展した。このカスケード判別器はリアルタイムで正面顔の検出を実施するものである。また、関連する文献としては、例えば、Xiao氏等のチェーン式ブースティングアルゴリズム（Boosting Chain）（非特許文献３参照）や、Liu氏等のKullback−Leiblerブースティングアルゴリズム（KLBoosting）（非特許文献４参照）などの多くのものがある。これらのブースティングアルゴリズムは共にカスケード判別器の一部に注目し、新しい方法でそれを改善するものである。
【０００７】
近年、顔の検出のためのカスケード判別器は成功的で効果的なものであると考えられていた。しかし、複数の顔向きに対応する顔の検出器（ＭＶＦＤ、Multi View Face Detector）を実現するためにこの構造を拡張する最も簡単な方法は、顔向き毎に異なるカスケード判別器を独立に学習し、それらのカスケード判別器を図１（ａ）に示すように一つにまとめて使用するというものである。非特許文献７での論述では、このように簡単な構造の拡張であっても、複数の顔向きという複雑な問題を解決する時に良く作用する。よって、その構造にはさらなる改良の余地が広く残っているといえる。例えば、以下のアプローチがある。
【０００８】
一、ピラミッド構造
一つのアプローチはピラミッド構造である。多種類の姿勢の顔を検出するために、Li氏はピラミッド構造（pyramid−structured）による複数の顔向きの顔の検出器（ＭＶＦＤ
）（非特許文献５参照）を発表した。このピラミッド構造は、図１（ｂ）に示すように、その頂層には±９０°の平面外回転（ＲＯＰ）をカバーする１つのノード（メインノード）しかなく、第２層の３つのノード（子ノード）でこの範囲を３つに分けてから、層ごとに細分化する。これは、始めは粗く判別し、後の判別で詳細に判断する（course to fine）手法を用いて、平面外回転（ＲＯＰ）の姿勢変化を処理するものである。顔は異なる姿勢でも類似なところがあるので、ピラミッド方法では、顔の特徴抽出の効果を改善するために、それらの類似な顔を一つのポジティブなアンサンブルクラス（oneensemble positive class）として取り扱うことにした。ただし、こうすると、それらの内在的な差異が無視され、ピラミッド方法の異なる姿勢への識別力がなくなった。その結果、親ノードを経たサンプルはその全ての子ノードに送られなければならなくなるので、決定処理が極めて低速になる問題がある。
【０００９】
二、決定木構造
別のアプローチは、図１（ｃ）に示す決定木構造である。上記のピラミッド方法とは逆に、多種類の姿勢の顔を検出するために、非特許文献６では決定木方法が提案され、平面内回転（ＲＩＰ）の問題に一つの解決策が示された。異なる姿勢同士の差異点に着目し、その決定木はＲＩＰの１つの姿勢を評価することができ、決定木の強制的な判断により、姿勢推測に必要とする時間を確実に効果的に減少させた。しかし、その結果は安定しなくなることがあり、且つ実用性が悪い。
【００１０】
このように、ＭＶＦＤ問題としては主に、１つは顔と非顔（non-face,顔以外のもの）
を区別すること、もう一つは顔の姿勢を識別することの２つの課題がある。１つ目の課題は、非顔をなるべく早く排除する必要があるので、顔を非顔と分離するように異なる姿勢の顔から類似点を見出さなければならない。２つ目の課題は、異なる姿勢同士の差異点に
注目している。２つの課題の衝突は、あらゆる顔を単一のクラスとして処理するか（例えばピラミッド方法）、或いは異なる独立の分離されたクラスとして処理するか（例えば決定木方法）というジレンマとなる。なお、両方は共にＭＶＦＤ問題の処理に満足できる結果を得られない。この問題は、通常、顔の姿勢変化（平面内回転ＲＩＰと平面外回転ＲＯＰを含む）によって画像における顔の構造及びテクスチャが顕著に変化されて、更に分類の複雑度が大きくなるのが難点である。
【００１１】
この課題を解決するために、上記の説明のように、ピラミッド（Pyramid）モデルと決
定木（DecisionTree）が提案された。前者は、姿勢変化の度合いに応じて、粗から詳細へ（coarse to fine）の原則に基づいて、順次に多角度の顔の空間を角度が単一である顔のエレメント空間に分けて、ピラミッド構造の判別器により多角度の顔を非顔と順次に分離するものである。後者は、決定木により多角度の顔を直接分類して、分類された結果に基づいて、対応するカスケード（cascade）判別器を選択する。そして、分類された結果の
姿勢の顔を非顔と分離するものである。概略的に言えば、ピラミッド（Pyramid）構造で
は異なる姿勢の顔を同一のクラスと想定して、それらと非顔との分類問題を解決することに注目して、顔の空間が徐々に精細に分割されることに伴って、最終で比較的に合理的な姿勢推測の結果が得られる。それに対して、決定木方法では、まず姿勢推測の問題を解決し、複数回の分類により異なる姿勢の顔を分離してから、従来のカスケードモデルによりある特定姿勢での顔と非顔との分類問題を解決するのである。
【００１２】
この２種類の方法では、異なる順序でＭＶＦＤの２つの問題（顔の検出及び姿勢推測）を解決している。しかし、これによってもそれぞれの異なる問題が発生する。ピラミッド構造では異なる姿勢の顔同士の一致性を強調し、複雑な多角度の顔と非顔とを直接に分離することにした。このような分類は難し過ぎて、構造の複雑な判別器でなければ解決できないので、良い検出精度を実現したとしても、速度の面では理想的ではない。一方、決定木構造では異なる姿勢の顔同士の差異性を強調し、まず、判別器を設計して複数回に分類し、次にそれらを非顔と分離するものであり、この方法は速度が理想的であるけれども、精度及びロバスト性は理想的ではなく、これは顔姿勢に対する複数回の分類そのものは容易に解決できる問題ではない。さらに、このように決定木により顔姿勢を迅速に判定する方法はある程度では必然的に精度及び実用性を喪失してしまう。要するに、異なる姿勢の顔同士の一致性と差異性が共存することは、上記の２つの方法では解決できない重要な問題である。
【００１３】
実際は、現実の顔の画像にとっては、ＲＩＰとＲＯＰとは普遍で同時に存在するものであり、従来の方法では実際に適用する上での必要な要求を満足できない。例えば、ＭＶＦＤとしては回転不変性が要求されている。この要求に対して、画像を回転してＭＶＦＤを数回適用することでこれらの問題を解決できる可能性がある。しかしこのやり方では、演算の複雑さが増し失敗が発生する。
【００１４】
従来技術の問題を解消するために、本発明は、幅優先（WFS：Width−First−Search）
の方法による木構造判別器を提案すると共に、顔検出及び姿勢の推測という２つの問題を解決する。
【００１５】
本発明の目的は、複数の顔向きに対応する特定被写体検出装置の精度及び速度を向上し、関係する検出装置の効果を改善するように上記の２つの問題のバランスを取る複数の顔向きに対応する特定被写体検出方法及び装置を提供することである。
【課題を解決するための手段】
【００１６】
本発明は、画像から特定被写体を検出する特定被写体検出装置において、画像入力手段と、前記画像入力手段から入力された画像を判別する木構造検出器であって、ルートノー
ドは、分岐される全ての対象物の向きに対応するサブ対象物空間を含み、前記ルートノードから分岐する子ノードは少なくとも１つの対象物の向きに対応するサブ対象物空間を含み、前記ルートノードと前記子ノードの各ノードは複数の弱判別器を含み、各弱判別器の出力を分割するサブ対象物空間毎に集計して、隣接する下層の子ノードのどこに移行するか判定する木構造検出器と、を有することを特徴とする特定被写体検出装置である。
【００１７】
また、本発明において、１つの向きにまで絞り込まれたサブ対象物空間のノード（葉ノード）にカスケード判別器を付加しても良い。このカスケード判別器により、画像に含まれる対象物が目的とする対象物である正確性を高めることができる。
【００１８】
また、本発明の木構造検出器の動作において、幅優先探索を行うようにさせても良い。幅優先探索を行うことにより、非対象物を早い段階で排除できるので木構造検出器の動作が高速になる。
【００１９】
また、本発明の木構造検出器の動作を決定する学習において、ブースティングアルゴリズムを用いても良い。ブースティングアルゴリズムの中でも、ベクトルブースティングアルゴリズムを用いた学習をすることにより、ロバスト性を良くすることができる。
【００２０】
また、前記対象物は顔であっても良い。特定被写体となる対象物は人の顔のほか、動物顔、自動車などにも適用することができる。特に、平面内回転、平面外回転により見え方に違いのある立体物の検出に適用することができる。
【００２１】
また、前記各ノードは１つの強判別器を含み、前記強判別器は複数の弱判別器の出力値によって決まるようにしても良い。複数の弱判別器を用いることにより、あるノードで強判別器が判断すべき複数のサブ対象物空間毎に、複数の弱判別器の値を集計することができるので、正確性が増すとともに効率の良い計算ができる。
【００２２】
また、前記サブ対象物空間は検出する対象物の平面内回転及び／又は平面外回転を含み、対象物の複数の向きに分割されているようにしても良い。Ｘ，Ｙ，Ｚ軸の各軸が直交した立体空間において、平面内回転はＹ軸周りの回転と定義できる。この場合、平面外回転はＺ軸周りの回転となり、対象物は右向き、左向きの状態となる。またＸ軸周りの回転も平面外回転であり、対象物は下向き、上向きの状態となる。
【００２３】
また、前記木構造検出器によって対象物が検出されたか否かを示すデータ及び／又は検出された対象物の位置や大きさなどを示すデータを出力する出力手段をさらに含めても良い。
【００２４】
さらに本発明は、画像から特定被写体を検出する木構造検出器を構築する方法として表すことができる。すなわち、情報処理装置が、画像を判別するノードを木構造に構成するステップと、前記木構造のルートノードは分割された全ての対象物の向きのサブ対象物空間を含み、かつ複数の分岐を有しており、各分岐は１つの子ノードに接続し、この子ノードは少なくとも１つの対象物の向きに対応するサブ対象物空間を含むように構成するステップと、２つ以上の前記サブ対象物空間を含む子ノードは複数の分岐を有しており、各分岐は隣接する下層の子ノードに接続し、各隣接する下層の子ノードは少なくとも１つの前記サブ対象物空間を含むように構成するステップと、１つのサブ対象物空間を含む子ノードは木構造の葉ノードになるように構成するステップと、前記ルートノードと前記子ノードのうち分岐する各ノードにおいて、画像を複数の弱判別器に入力し、各弱判別器の出力を分割するサブ対象物空間毎に集計し、隣接する下層の子ノードのどこに移行するか判別させるように構成するステップとを実行することを特徴とする木構造検出器を構築する方法である。
【００２５】
なお、本発明は、上記手段の少なくとも一部を有する特定被写体検出装置として捉えることができる。また、本発明は、上記処理の少なくとも一部を含む特定被写体検出方法、又は、かかる方法を情報処理装置に実行させるプログラムとして捉えることもできる。上記手段及び処理の各々は可能な限り互いに組み合わせて本発明を構成することができる。
【発明の効果】
【００２６】
本発明の有益的な効果は、本発明はピラミッド構造（非特許文献５）や決定木（非特許文献６）とは異なる、幅優先探索（ＷＦＳ）木構造を採用しているので、高精度かつ高速度で動作できる点、幅優先探索木のノードを学習させ、リアルアダブースティング（Real
AdaBoosting）アルゴリズム（非特許文献８，９，１０参照）を拡張するベクトルブースティング（vectorboosting）アルゴリズムを得たことで、より良い性能を達成できる点、弱判別器が分級関数（piece-wise function）で定義されており、それはルックアップテ
ーブル（ＬＵＴ）により実現され、複雑な分布を近似するために用いられ、信頼度を評価した判別を与える点である。
【００２７】
従来技術と比べると、本発明による幅優先探索木構造方法は速度でも精度でも明らかに改良されている。また、このような幅優先探索木構造検出器を４つ組み合わせて動作させることにより、リアルタイムで動作する回転不変性を有するＭＶＦＤを構成できる。
【００２８】
また、本発明によるベクトルブースティングアルゴリズムは、リアルアダブースティングアルゴリズムの構造を拡張してなるものと考えられてもよく、仮に適当に投影ベクトルを予め設定すれば、ベクトルブースティングアルゴリズムは古典的なリアルアダブースティングアルゴリズムと同じように動作する。ベクトルブースティングアルゴリズムは、古典的なリアルアダブースティングアルゴリズムをカバーするものである。ベクトルブースティングの主な貢献は、従来のアダブースト（AdaBoost）方法において、簡単な二値分類（binary classification）であるか複雑なマルチ分類マルチタグ（multi-classmulti-label）問題を問わず、一つのフレームワークで取り扱えるようにしたことである。従来の
二値分類法では、判別器の出力をスカラー空間に制限して最適化しており、マルチ分類問題については複数の独立した二値分類問題に分けて別々に解決する。この方法は明瞭で直接的であるが、複雑なマルチ分類マルチタグ問題を処理する場合、処理が膨大となり、且つ分割された二値分類問題同士を関係付けるのも難しい。本発明のベクトルブースティングアルゴリズムは、分割された複数の二値分類問題を含む複雑な問題を同一のベクトル出力空間において取り扱うことができ、従来のアダブースト方法をも一つのフレームワークで取り扱えるようにする。さらに、ベクトルブースティングによれば異なる分類問題同士の関連性を考慮でき、ベクトルブースティングはアダブースト方法を発展してなるものだと言える。ベクトルブースティングアルゴリズムはＭＶＦＤ問題のために開発されたものであるが、他の複雑な分類問題にも適用できる。
【発明を実施するための最良の形態】
【００２９】
以下、図面を参照しながら本発明の最良の実施形態を説明する。以下の説明では、特定被写体検出方法及び装置の具体例として、人物の画像から顔を検出する顔検出方法及び装置を説明する。
【００３０】
なお、以下の説明では、特定被写体検出装置の具体例として、人物の画像から顔部を検出する木構造検出器（図８ａと図８ｂを参照）を説明する。
【００３１】
この説明において、いわゆる人物の画像とは、少なくとも顔部の一部又は全部の画像を含む画像をいう。従って、人物の画像は人物全体を含む画像でもよく、顔部又は上半身を含む画像でもよい。また、人物の画像は複数の人物を含む画像でもよく、さらに、人物の
画像は背景として人物以外の風景（被写体として注目される物体も含む）及び模様などを含むいかなる図形でもよい。
【００３２】
さらに、木構造検出器についての以下の説明はただ一つの例だけであり、その構造は以下の説明に限られるのではない。
【００３３】
＜実施例１＞
図２のように、本発明は複数の顔向きに対応する顔検出方法を提供している。この方法では、顔空間を複数の顔向きによるサブ顔空間に分割する。例えば、一つの顔を±９０°の平面外回転をさせて、正面の顔と、半左向きの顔と、全左向きの顔と、半右向きの顔と、全右向きの顔という５つの顔向きによるサブ顔空間に分割する。次にこの５つのサブ顔空間をそれぞれ±４５°の平面内回転させて、各顔向きによるサブ顔空間から平面内回転による２つのサブ顔空間（例えば±３０°の平面内回転）に分割する。このように顔空間を１５つの顔向きによるサブ顔空間に分割する。
【００３４】
本実施例で示す平面外回転はＺ軸周りの回転であるが、Ｘ軸周りの回転であっても良い。Ｘ軸周りの回転をした場合、画像上では顔は俯き、上向きのように見え方が変化する。この軸の定義によればＹ軸周りの回転は、平面内回転に相当する。
【００３５】
前記木構造は１つのルートノードがあり、このルートノードは分割されたあらゆる顔向きによるサブ顔空間（即ち、上記の顔の分割例では、ルートノードは１５の顔向きによるサブ顔空間を含む）を含み、且つ複数の分岐を有しており、各分岐は１つの子ノードに対応して、前記子ノードは少なくとも１つの顔向きによるサブ顔空間を含むように幅優先探索木構造検出器を構築する。そのうち、１つ以上の顔向きによるサブ顔空間を含む子ノードは複数の分岐を有している。また、子ノードは非分岐としてもよい。ここで非分岐とは、サブ顔空間を分割せずに下層の子ノードに移行することである。各分岐は１つの隣接する下層の子ノードに対応して、各隣接する下層の子ノードは少なくとも１つの顔向きによるサブ顔空間を含む。１つの顔向きによるサブ顔空間のみを含む子ノードは前記木構造の葉ノードである。
【００３６】
対応するノードの顔画像をどの隣接する下層のノードに送るかを決定するために、ベクトルブースティングアルゴリズムにより前記の各ノードをデシジョンベクトルに学習し、かつ木構造におけるあらゆる有効なノードを処理する時に幅優先探索を採用する。
【００３７】
前記の葉ノードに対して非分岐のカスケード分類を行い、非顔を排除することで対応する顔向きのある顔を得られる。
【００３８】
一、幅優先探索（WFS、Width First Search、またはBFS、BreadthFirst Search）木構
造検出器
図２に示すように、±４５°の平面内回転（ＲＩＰ）及び±９０°の平面外回転（ＲＯＰ）をもつ顔空間に関して、この検出器は粗から細への方法（course to fine）により顔空間全体を徐々に小さなサブ空間に分割する。最も大きい空間を含むルートノードは２層目で左向きと、正面と、右向きの顔向きに分けられる。これにより、平面外回転（ＲＯＰ）がより正確に表現される。その次の下の層において、完全な横向き及び半横向きが定義される。最後に、４層目で各顔向きを異なる平面内回転（ＲＩＰ）に従って３種類に分ける。
【００３９】
本発明による木構造検出器は決定木方法のように１つのサンプルに唯一の経路を選択することはない。その代わりに、各ノードに１つのデシジョンベクトルＧ（ｘ）を算出することで、この顔画像をどのノードに送るかを決定する。例えば、図２に示すルートノード
において、あるサンプルのデシジョンベクトルがＧ（ｘ）＝（１，１，０）であれば、これはこの顔画像が右向きの顔ではなく、左向きの顔又は正面の顔であることを意味するので、２層目では、この顔画像は右側のノードではなく、左側のノード及び真ん中のノードに送られる。別の例では、顔画像のデシジョンベクトルがＧ（ｘ）＝（０，０，０）であれば、これはこのサンプルがいかなる子ノードにも属さないことを意味しており、迅速に廃棄されることを意味する。木のあらゆる使用可能なノードを処理するときに、幅優先の方法により探索が行われる。幅優先探索の擬似コードを以下に示す：
【００４０】
【数１】
0004801557.tif 000002
【００４１】
図２は、木構造検出器における幅優先探索の方法を示している。要するに、幅優先探索木による方法は、精度を犠牲してしまう非特許文献６の方法とは違って、姿勢をすぐに判定しようとはせず、また、速度を犠牲にしてしまう非特許文献５の方法とも違って、クラス内での姿勢の差異を考慮することなく単純に異なる姿勢を組合せるようなこともしない。よって、幅優先探索木では異なる姿勢同士の相違点及び類似点という２点に注目することにより、上記の方法より優れ、高精度だけでなく、高速度も保証できるようになった。
【００４２】
以上の検討でわかるように、幅優先探索木においてノードは重要な役を果たしている。上記の新技術をサポートするため、本発明は、リアルアダブースティング（非特許文献８参照）を拡張した「ベクトルブースティング」アルゴリズムを導入する。この新しいベク
トルブースティングアルゴリズムにより、各ノードの学習が行われ、要求されるデシジョンベクトルＧ（ｘ）を迅速且つ正確に算出できるようになる。
【００４３】
二、ベクトルブースティングアルゴリズム
ここで言うベクトルブースティングアルゴリズムはリアルアダブースティングアルゴリズムの拡張バージョンとして提案されている。ベクトルブースティングアルゴリズムでは、弱判別器及び最終の出力が共にスカラーではなくベクトルである。ベクトルブースティングアルゴリズムはもともとはリアルアダブースティング（非特許文献８参照）のマルチタイプマルチラベル（ＭＣＭＬ）バージョンからのものであり、サンプル毎に１組のラベルを分配すると共に、オリジナルの問題をｋ個の直交する二値分類問題に分解するものである。このアルゴリズムの主要な点は、各二値分類問題に関して、サンプルをポジティブ又はネガティブと評価することである。しかしながら、多くの複雑なケースでは、サンプルに関連性のない二値分類問題において、ポジティブでもネガティブでもないサンプルがでてくるため、上記評価が成立しなくなる。このことが、リアルアダブースティングのマルチタイプマルチラベル（ＭＣＭＬ）バージョンの適用を阻害している。図２の幅優先探索木のルートノードを例に挙げると、ある正面顔のサンプルのデシジョンベクトルはＧ（ｘ）＝（＊，＋１，＊）となり（＊は＋１でも−１でもよい）、第１（即ち、左向きの顔）及び第３（即ち、右向きの顔）の二値分類は正面顔のサンプルには関連性がないことがわかる。１つの複雑な分類問題が１組の二値分類問題に分解されると、ベクトルブースティングアルゴリズムは、多成分ベクトルの共有出力空間を用いることにより、それらの二値分類問題を統一的なフレームワークで処理する。この出力空間において、各二値問題は固有の「興味（interested）」方向をもつ。これが、その二値問題の投影ベクトルとよばれる。この方法において、異なる二値問題は独立している（直交投影ベクトルを有する）必要はなく、通常、互いに関連してもいい（非直交投影ベクトルを有する）。
【００４４】
一連の学習サンプルとして、
【数２】
0004801557.tif 000003
が与えられたとする。ただし、ｘｉは１つのサンプル空間Ｘに属し、ｖｉは有限のｋ次元の投影ベクトル集合Ωに属し、ラベルｙｉ＝±１（即ち、ポジティブ或いはネガティブ）である。ｎ個の二値分類問題を同時に処理するｋ次元のベクトルブースティングアルゴリズムの汎用バージョンの擬似コードは次のようになる。
【００４５】
【数３】
0004801557.tif 000004
【００４６】
以上は一般的なベクトルブースティングアルゴリズムである。
【００４７】
前記のベクトルブースティングアルゴリズムは、ｋ次元の出力空間で、ｎ個の二値分類問題に分割される一つの複雑な問題を解決するように構成されたものである。アダブーストアルゴリズムと同じように、サンプル分布が更新されるたびに弱判別器を繰り返しコー
ルすることで、高精度の判別器を作成できる。その中心となる変換規則式（１）では、出力のベクトル化により、ラベルｙ及び投影ベクトルｖｉを有するサンプルｘｉの分類マージン（margin）がｙｉ（ｖｉ・ｈ（ｘｉ））のように定義される。従って、１つの弱判別器から出力された直交成分はサンプルのウェイト（重み）の更新に役立たない。この方法では、ベクトルブースティングアルゴリズムは投影ベクトル（興味方向）により誤って分類されたサンプルのウェイトを増加する一方、正確に予測されたサンプルのウェイトを減少する。
【００４８】
最終の出力はあらゆる学習をさせた弱判別器の線形結合式（２）である。二値問題毎に信頼度を算出するため、ｎ×ｋマトリクスＡを用いてｋ次元の出力空間がｎ次元の信頼度空間に変換され（式（３））、これによって、集合Ωにおけるｎ個全ての投影ベクトルが構成される。信頼度空間のそれぞれの次元は１つの二値問題に対応している。最後に、閾値ベクトルＢに基づいて、二値（Boolean）出力を有する強判別器が得られる（式（４）
）。
【００４９】
実際上、試験では、簡単化のために、複雑な分類問題が複数の直交する二値問題に分解されるが、ただし各種の顔姿勢同士の独立性を維持しなければならない。例えば、図２では、ルートノードを学習する時に、左向きと正面と右向きという３つの顔グループを集め、それぞれの投影ベクトルとして（１，０，０）、（０，１，０）、（０，０，１）を割り当て、それらにポジティブな値（即ち、ｙ＝＋１）のラベルを付与する。そして、同じ投影ベクトルを有する３つの非顔グループを用意し、それらにネガティブな値（即ち、ｙ＝−１）のラベルを付与する。この３つの二値問題は独立に学習されるように考えられるが、選別された特徴を共有しているので、非特許文献７における１つずつ学習する方法より優れている。図３は出力空間Ｈ（ｘ）における３種類の結果を示しており、ここで、Ｈ（ｘ，１）は左向き（Left profile）の次元で、Ｈ（Ｘ，３）は右向き（Right profile
）の次元である（簡単のために、正面からの顔向き及びその関係する投影ベクトルが省略されている）。これによってわかるように、この二次元空間で、左向きの顔と右向きの顔は、それぞれに固有の投影ベクトルw１とw３により、非顔（Non-face）から分離できる。
【００５０】
なお、ｎ＝ｋ＝１であり、w１（Wにおける唯一の投影ベクトル）が単位ベクトルである場合、ベクトルブースティングアルゴリズムは丁度リアルアダブーストアルゴリズムと同じになる、と簡単に理解できる。実際には、更新規則式（1）における一致性により、ベ
クトルブースティングアルゴリズムではリアルアダブーストアルゴリズムと同じ学習誤差範囲、即ち、
学習誤差：Ｐｅｒｒｏｒ≦ΠＺｔ        （５）
を確保している。
【００５１】
ここまでは、ベクトルブースティングアルゴリズムの構造及び予測可能な学習誤差範囲を説明し、どのように弱判別器をトレー二ングするかを明確に記載した。次に、弱判別器の設計及びベクトルブースティングの最適化方法を説明する。
【００５２】
三、分級関数
従来のカスケード判別器では、積分画像の方法によりハール特徴ｆ（Ｘ）を高速に算出するが、この方法においては、図５ａに示すように、弱判別器ｈ（ｘ）は二値（Boolean
）出力を有する閾値型関数で定義されている。この関数は、
ｈ（ｘ）＝ｓｉｇｎ［ｆ（ｘ）−ｂ］
のように模式的に表される（ここでｂは閾値である）。これは簡単でかつ容易に学習できるが、抽出された特徴の情報を十分に活用できない。例えば、図４ａでは、ポジティブとネガティブのサンプルは適当な閾値により良好に区分される。しかし、粒度が粗いため、それらの差異を正確に表すことができない。また、アダブーストアルゴリズムの更新中で
は、それらの差異は徐々に減少して（図４ｂは、５回目で選別されたハール特徴の差異を示している。）、これは閾値型関数の区分能力を大いに弱くさせ、アルゴリズムの収束（即ち、カスケードにおける後寄りの層において、顔と非顔とが非常に似る場合）に支障をきたすことがある。その結果、閾値型弱判別器における粗い粒度は検出器の速度及び精度の改良を大いに阻止している。
【００５３】
図５ｂに示す関数を分級関数と定義する。分級関数は特徴空間を同一幅を有する複数の級（ビン）に分割すると共に、ビン毎に一定の値を出力する設計にする。この分級関数は様々な分布をより正確に近似することができ、且つ二値出力の制限を受けないので、実質的に等間隔サンプリング処理と同じになる。これは実際に非特許文献８に係るドメイン分割（domain partition）を実現する自然的な方法であり、リアルアダブーストアルゴリズムにおける弱判別器への要求に丁度よく適応できる。また、分級関数はルックアップテーブル（ＬＵＴ）により効果的に実現できるので、閾値型関数と比べると、過剰な演算負荷を発生することはなく（１つの乗算のみで特徴値をＬＵＴのインデックスに変換できる）、実数値出力により弱判別器の能力は大幅に強化される。
【００５４】
「只飯無し（うまい話には裏がある）」というように、１つの分級関数に適当な粒度を選択することはとても重要なことである。粒度は細いほど、分級関数による推測は正確になる（学習誤差が低くなる）が、ノイズ及び学習グループの大きさに敏感になる（構造のリスクが高くなる）。経験によれば、最初の数層では、学習を早く収束させるように粒度を細くしてもかまわないが、後の層では、分類の結果をロバスト化させるように粒度を粗くするほうが良い。
【００５５】
四、弱判別器の最適化
式（５）に示すように、ベクトルブースティングアルゴリズムにおける学習誤差は全ての規格化因子の積が上限となるから、欲張りアルゴリズム（greedy strategy）を適用す
れば、弱判別器の目的は現在回の因子を最小化することである。仮に、弱判別器ｈ（ｘ；θ，μ）の特徴を２つのパラメータで記述すれば、θはそのハール特徴を記述するのに、μはその分級関数を記述するのに用いられる。有限冗長のハール特徴の集合を用いて、全ての探索方法を実施し、最も区分能力を有するものを得られるように各特徴に１つの分級関数を最適化する。
【００５６】
１つの分級関数は、特徴空間の分割及び各分割（即ち、級、ｂｉｎ、ビン）の出力常数という２つの部分により構成される。簡単のために、特徴空間の分割については特徴毎に経験的に定め、それぞれのビンの出力常数は次のように最適化できる。
【００５７】
サンプル
【数４】
0004801557.tif 000005
が分布Ｄｔ（ｉ）をもつと仮定する。ある特徴ｆ（ｘ）について、サンプルは予め定義された分級関数に基づき対応するビンに分配される。それぞれは次のように表される。
【数５】
0004801557.tif 000006
ただし、ｊはビンのインデックスである。
【００５８】
第ｊ番目のビンの出力常数をｃｊとすれば、規格化因子は次式で得られる。
【数６】
0004801557.tif 000007
ビンｋ（ｂｉｎ  ｋ）に関して、学習損失は次のようになる。
【数７】
0004801557.tif 000008
この損失関数はｃｋを変数とする凸関数である。従って、各ｃｊが適当な最適化アルゴリズム、例えばニュートンステップ（Newton−Step）により、最適化される。
【００５９】
弱学習処理は下記の擬似コードにまとめられる。
【数８】
0004801557.tif 000009
【００６０】
以上をまとめると、ＭＶＦＤへの新しい貢献は、幅優先探索木と、ベクトルブースティングアルゴリズムと、分級関数に基づく弱判別器とを含む。
【００６１】
図１１に示すように、前記の各ノードは共に１つの強判別器を含み、前記強判別器は複数の弱判別器で前記のベクトルブースティングアルゴリズムにより得られるものであり、前記の弱判別器は積分画像ハール特徴に基づいて特徴を抽出し、またルックアップテーブル（ＬＵＴ）の分級関数に基づいて弱判別を行う。各強判別器は顔と非顔を区分し、非顔を排除して、それ以外のものを対応する下層のノードに出力する。
【００６２】
前記の各葉ノードは１つの分岐を有し、その分岐は非分岐の子葉ノードに繋がっている。前記葉ノードとその子葉ノードによりカスケード判別器を構成して、非顔を排除することで対応する顔向きの顔を得られるようにした。
【００６３】
＜実施例２＞
図８ａ、図８ｂに示すように、本発明はさらに複数の顔向きに対応する顔検出装置を提供するものであり、該装置は、顔画像入力手段、幅優先探索木構造検出器、顔出力手段を含むものである。
【００６４】
顔画像入力手段は、サブ顔空間を含む顔画像を入力する。
【００６５】
幅優先探索木構造検出器では、前記木構造は１つのルートノードがあり、このルートノードは分割されたあらゆる顔向きによるサブ顔空間を含み、且つ複数の分岐を有しており、各分岐は１つの子ノードに対応して、前記子ノードは少なくとも１つの顔向きによるサブ顔空間を含み、
１つ以上の顔向きによるサブ顔空間を含む子ノードは複数の分岐を有しており、各分岐は１つの隣接する下層の子ノードに対応して、各隣接する下層の子ノードは少なくとも１つの顔向きによるサブ顔空間を含み、１つのみの顔向きによるサブ顔空間を含む子ノードは前記木構造の葉ノードであり、
前記各ノードは顔であるか否かの信頼度を出力する１つの強判別器を含み、各ノードの分岐数をこの強判別器で出力できる信頼度の顔の顔向き種類に等しくさせることにより、対応するノードの顔画像をどの隣接する下層のノードに伝送するかを決定すると共に、前記の葉ノードに対して非分岐のカスケード分類を行い、非顔を排除することで相応する顔向きを有する顔を得られ、かつ、木構造におけるあらゆる有効なノードを処理する時に幅優先探索を採用する。
【００６６】
顔出力手段は、最終で底層の葉ノードに達することができるサブ顔空間を顔として検出すると共に、達した底層の葉ノードの相違により、このサブ顔空間の顔向きを決定する。
【００６７】
図８ａ、図８ｂは顔検出装置を示す機能ブロック図である。顔検出装置はＣＰＵにより実行されることによって、顔画像入力手段、顔出力手段、木構造検出器を含む装置として機能する。以下、図８ａ、図８ｂを用いて、顔検出装置の各機能部について説明する。
【００６８】
顔画像入力手段：
顔画像入力手段は、人物画像の原画像のデータ（以下、「原画像のデータ」と呼ぶ）を顔検出装置へ入力するためのインタフェースとして機能する。原画像のデータは、静止画像のデータであっても良いし、動画像のデータであっても良い。顔画像入力手段によって、顔検出装置の外部から、原画像のデータが顔検出装置へ入力される。顔画像入力手段は、顔検出装置へ原画像のデータを入力するためのいずれかの既存技術を用いて構成されても良い。
【００６９】
例えば、ネットワーク（例えばローカル・エリア・ネットワークやインターネット）を介して原画像のデータを顔検出装置へ入力させても良い。この場合に入力手段はネットワークインタフェースを用いて構成されても良い。また、デジタルカメラやスキャナやパーソナルコンピュータや記憶装置（例えばハードディスクドライブ）等から原画像のデータを顔検出装置へ入力させても良い。この場合、入力手段は、デジタルカメラやパーソナルコンピュータや記憶装置などを顔検出装置とデータ通信可能に接続させる規格（例えばＵＳＢ（Universal Serial Bus）やＳＣＳＩ（Small Computer System Interface）等の有
線接続やbluetooth等の無線接続の規格）に応じて構成されて良い。また、記憶媒体（例
えば各種フラッシュメモリやフロッピー（登録商標）ディスクやＣＤ（CompactDisk）や
ＤＶＤ（Digital Versatile Disc、Digital Video Disc））に記録されている原画像のデータを顔検出装置へ入力させても良い。この場合、入力手段は、記憶媒体からデータを読み出す装置（例えばフラッシュメモリリーダやフロッピーディスクドライブやＣＤドライブやＤＶＤドライブ）を用いて構成されて良い。
【００７０】
また、顔検出装置をデジタルカメラ等の撮像装置又はデジタルカメラ等の撮像装置（例えばＰＤＡ（PersonalDigital Assistant）や携帯電話機）の内部に含め、撮像された人
物画像を原画像のデータとして顔検出装置へ入力させても良い。この場合、入力手段は、ＣＣＤ（Charge-CoupledDevices）やＣＭＯＳ（Complementary Metal-Oxide Semiconduct
or）センサ等を用いて構成されても良いし、CCDやCMOSセンサなどによって撮像された原
画像のデータを顔検出装置に入力するためのインタフェースとして構成されても良い。また、出力データとしてこの画像出力装置に入力された人物画像を原画像のデータとして顔検出装置へ入力させても良い。この場合、入力手段は、これらの画像出力装置に入力された原画像のデータを顔検出装置において取り扱い可能なデータに変換させる装置等を用いて構成されても良い。
【００７１】
また、入力手段は上述の複数の場合に応じるように構成されても良い。
【００７２】
処理対象窓（subwindow）の場所を移動させながら現画像のデータから、処理対象窓の
画像データを切り出し、顔検出器に送る機能が顔画像入力手段に含まれていても良い。この機能を付加することにより、背景を含めた画像から、顔を検出することが可能となる。
【００７３】
顔出力手段：
出力手段は、木構造検出器によって顔が検出されたか否かを示すデータ及び／又は検出された顔の位置や大きさなどを示すデータを、顔検出装置の外部へ出力するためのインタフェースとして機能する。出力手段は顔検出装置から顔の検出結果に関するデータを出力するためのいずれかの既存技術を用いて構成されても良い。
【００７４】
例えば、ネットワークを介して検出結果に関するデータを顔検出装置から出力させても良い。この場合、出力手段はネットワークインタフェースを用いて構成される。また、パーソナルコンピュータ等の他の情報処理装置や記憶装置へ検出結果に関するデータを出力させても良い。この場合、出力手段はパーソナルコンピュータ等の他の情報処理装置や記憶装置などをデータ通信可能に顔検出装置と接続させる規格に応じて構成される。また、記憶媒体へ検出結果に関するデータを出力（書込み）させても良い。この場合、出力手段はこれらの記憶装置又は記憶媒体へデータを書込む装置（例えばフラッシュメモリレコーダやフロッピーディスクドライブやＣＤ−ＲドライブやＤＶＤ−Ｒドライブ）を用いて構成される。
【００７５】
出力手段から出力されるデータの具体的な用途例についても説明する。例えば、顔検出装置から検出された顔の領域を示す図形をディスプレイ等の表示装置に出力するために、出力手段から出力されたデータを使用しても良い。この場合、出力手段は、例えばディスプレイ等の表示装置とデータ通信するためのインタフェースとして構成されても良いし、ディスプレイ等の表示装置に接続する、又は内蔵された情報処理装置にデータを伝達するインタフェースとして構成されても良い。図６はディスプレイに表示した一例である。また、例えば顔検出装置をデジタルカメラ又はデジタルカメラを備える各種装置の内部に含める場合、デジタルカメラは出力手段によって出力されたデータを元に焦点制御や露光補正などの撮像に関する制御を行うように構成されても良い。この場合、出力手段は、例えばデジタルカメラ内の情報処理装置とデータ通信可能なインタフェースとして構成されても良い。また、例えば顔検出装置を画像補正処理を行う情報処理装置の内部に含める場合及びこのような情報処理装置に接続されるのを決定する場合、情報処理装置は出力手段から出力されたデータを元に画像補正処理の処理領域や処理内容などを決定するように構成されても良い。このような場合、出力手段は、例えばこのような情報処理装置及びその内部の装置とデータ通信可能なインタフェースとして構成されても良い。
【００７６】
また、出力手段は上述の複数の場合に応じるように構成されても良い。
【００７７】
顔検出器：
一、木構造検出器の基本的な構成
図１１は、複数の顔向きを分類する木構造の顔判別器を示す。そのうち、各ノードは１
つの層判別器（即ち強判別器）を含み、各層判別器は多くのハール特徴によるルックアップテーブル型弱判別器で連続アダブーストアルゴリズムにより得られるものである。
【００７８】
前記のハール特徴は矩形特徴であり、各ハール特徴は一般的に画像の処理対象窓における２つの領域の画素の階調の差と定義されており、各領域は幾つかの矩形（基本ブロック）から構成される。ハール特徴はパターンへの表現力が他のさらに複雑な特徴よりは劣るが、積分画像によって迅速に計算できることから、弱判別器に適当な特徴となっている。
【００７９】
１つのハール特徴の属性は、基本ブロックの長さと幅、処理対象窓に対する特徴の位置、及びそのタイプ（形態）を含む。特徴は、処理対象窓との相対的位置及び相対的大きさが変わらないように、検査中の処理対象窓の変化に伴って変わっている。特徴の計算を加速させるために、処理対象窓が変わる場合、各ハール特徴において一部の冗長情報を予め算出すればよい。
【００８０】
二、ルックアップテーブル型弱判別器
各ハール特徴に基づいて、１つのルックアップテーブル型弱判別器を学習させることができる。この弱判別器はハール特徴の値の領域をｎ等分し、等分された各領域に二分類（顔であるか否か）の信頼度を付与する。ｎはルックアップテーブルの長さである。
【００８１】
従来のルックアップテーブル型弱判別器とは異なって、本発明に用いられる弱判別器はマルチルックアップテーブル（Multi LUT）を含んでいる。このマルチルックアップテー
ブルは、同一のハール特徴に基づいて異なる顔向きに関する顔の信頼度情報（confidenceinformation）を提供することができる。簡単に言えば、異なる顔向きの複数の判別器が
同一のハール特徴を共用しているのである（shared featureor mutual feature）。これ
による利点は次の通りである。異なる向きの顔を１つのアンサンブルクラスとして扱い判定する方法と比べると、マルチルックアップテーブル型弱判別器はそれぞれの向きの顔の分類情報を同時に提供できるので、より良い区分度が得られる。また、それぞれの顔向きに対して判別器を独立に学習させる方法と比べると、マルチルックアップテーブル型弱判別器は、各ハール特徴の利用効率を向上することで、正解率を維持したまま用いるハール特徴の数を減らすことができ、検出速度を向上させることができる。
【００８２】
図９はマルチルックアップテーブル型弱判別器の一例を示す。この弱判別器は３つのＬＵＴを有し、それぞれ３０°、０°、−３０°の平面内回転について信頼度を出力する。ここで、３つのルックアップテーブルの添字（インデックス）は共に同一のハール特徴に基づいて算出される。
【００８３】
連続アダブーストアルゴリズムは、弱学習アルゴリズムの一つとして、複数の弱判別器（weakclassifier）を線形に組み合わせて１つの強判別器（strong classifier）とする
ことができる。連続アダブーストアルゴリズムにおける弱学習過程は多量のラベルしたサンプルデータにより、サンプルのウェイトを調整することにより、新しい弱判別器を次々に選択して既存の判別器と線形に組み合わせし、学習用のサンプルデータでのエラー率が低下し、収束するまで実行する。
【００８４】
連続アダブーストアルゴリズムをルックアップテーブル型弱判別器に適用し、異なる学習パラメータと異種類のサンプルを採用すれば、一系の強判別器が得られる。ここで各強判別器を「層判別器」（layer classifier）と称する（１組の弱判別器の線形結合を一層とする）。検出対象となる１つの処理対象窓に対して、１つの層判別器が、複数の異なる向きの顔それぞれに関する信頼度を提供できる（異なる顔向きの数はこの層判別器における弱判別器のルックアップテーブルの数と等しい）。
【００８５】
図１０は層判別器の一例を示す。この層判別器は、連続アダブーストアルゴリズムにより図９の弱判別器を線形結合することで得られるものであり、３０°、０°、−３０°の平面内回転を伴う顔に対して、顔であるか否かの信頼度を出力するものである。
【００８６】
木構造検出器は図１１のように構成されてもよい。その各ノード（Node）は１つの層判別器から構成される。各ノードの分岐数はこの層判別器によって信頼度を出力できる顔向き種類の数と等しい。
【００８７】
木構造検出器のルートノードを例にすると、ルートノードは、全左向き、半左向き、正面、全右向き、半右向きという５つの顔向きに対してそれぞれ５つの信頼度を出力できるので、５つの子ノードを有する。ルートノードにおける検出によって、ある画像の処理対象窓のある顔向きに関する信頼度が所定の閾値より大きいと判定されると、この処理対象窓の画像は対応する子ノードに入力され、さらなる検出に供される。
【００８８】
図１１では３層目のノードからそれぞれ３０°、０°、−３０°の平面内回転を伴う顔に対応する３つの信頼度が出力される。
【００８９】
木構造判別器は、各層にて非顔を排除して行き、最終的に葉ノードまで到達した処理対象窓を顔として検出する。また、処理対象窓の到達した葉ノードがどれなのかによって、この顔向きが決定される。１つの木構造検出器がカバーできる顔向きは１８０°の平面外回転（つまり、正面と左右の回転）と９０°の平面内回転を含む。
【００９０】
三、木構造検出器の動作フロー
処理対象窓のサーチでは、木構造判別器に入力された１つの処理対象窓（グレースケール画像）に対し、その判別器が対応する複数の姿勢のそれぞれに関して検出が実行される。そして、その処理対象窓が検出にパスする場合には、木構造判別器は、ある姿勢の顔であるとの信頼度を示すものとして、その処理対象窓を出力する。画像における顔検出では、理論上、画像上の各処理対象窓を列挙して、木構造判別器でそれらの処理対象窓の検出処理を実行した後、画像全体に関する検出結果を得られる。３２０×２４０画素の画像では、２４×２４〜２４０×２４０の範囲の大きさをもつ正方形の処理対象窓が全部で５２５７４７６もある。完全に探索するためには膨大な時間がかかる。
【００９１】
処理対象窓のスケール（Scale）に関して言えば、１画素ずつ大きくするのでなく、倍
率を増大させていくとよい（毎回１つのスケール倍率と乗算する）、処理対象窓の位置に関して言えば、逐一走査するのでなく、マルチ解像度による走査に変更するとよい（即ち、まず粗い解像度でグリッド走査を行い、顔の出現する可能性が高いところが見つけられれば、その周辺に細い解像度でグリッド走査を行う）。
【００９２】
図１２は木構造検出器における可能性探索の過程を示す。
【００９３】
太い矢印は可能性のある探索経路を示している。このようなケースにおいて、粗い探索（CoarseSearch）を完了した時点で探索キューに残るノードを、灰色で示す。
【００９４】
処理対象窓の検出処理について以下説明する。
【００９５】
各処理対象窓の検出は、粗い探索と細かい探索（Fine Search）という二段階で完成す
るものであり、両者の対照は次の通りとする。
【表１】
0004801557.tif 000010
【００９６】
粗い探索過程では、探索で到達する各ノード（層判別器）について、検出処理対象窓に応じて対応するハール特徴の値を算出することにより、１つ以上（ノードの分岐数により決まる）の信頼度を得られる。信頼度が閾値より大きい分岐に対しては、この分岐の到達先のノードが探索キューに加えられる。キューにおけるノードの層番号が粗い探索において規定されている最大の層番号になるまで幅優先探索を続けていく。
【００９７】
そして、キューが空きでなかった場合は、この範囲に顔が存在する可能性があると考えられて、現在の処理対象窓周辺の処理対象窓に関する細かい探索を行う。細かい探索を行う処理対象窓は粗い探索の場合と異なるが、処理対象窓が互いに近い（Half_coarse_step（粗い探索における探索点間隔の半分）以下）ので、粗い探索における探索キューを引き継いで探索を続ける。１つ以上の葉ノードに達することができるならば、各葉ノードは１つの顔の検出結果に対応し、それを記録して出力する。
【００９８】
本発明を検証するために、約７５０００枚の顔画像を採集してラベルを付与した。そのうち、正面顔は３００００枚、半横顔は２５０００枚、横顔は２００００枚である。一部のサンプルは以下に示す。図２に示すように、まず、全ての顔を左右の平面外回転に応じて５つのカテゴリーに分けて、次に各カテゴリーを３つの顔向きに分ける。各顔向きは３０度の平面内回転をカバーする。これらの１５個の顔向きは上下［−３０度、＋３０度］の平面外回転による範囲もカバーしている。各サンプルは規格化され、また２４×２４の大きさに調整されている。
【００９９】
各ノードの誤報率（false positive rate）をｆ、検出率をｄとし、全ての顔向きの全
誤報率の期待値をＦとし、対象物（顔）のサンプル集合をＰ、非対象物（非顔）のサンプル集合をＮとする。
【０１００】
現在のノードＥ＝木のルートノードとし、
ノードＥの学習処理を次の通り実行する。
【０１０１】
ＰとＮから、Ｅの全ての親ノードを通過したサンプルを採集して、適当な大きさの２つの学習用サンプル集合ｐとｎを形成する。
ｐとｎについて、ベクトルブースティングアルゴリズムにより、所望の検出率ｄ及び誤報率ｆが得られるまで、１つの強判別器Ｇ（ｘ）を学習させる。
現在の全誤報率Ｆｃｕｒについて評価し、
Ｆ＞Ｆｃｕｒであれば、
Ｅのそれぞれの子ノードＥｃｈｉｌｄについて、Ｅ＝ＥｃｈｉｌｄとしノードＥの学習処理を同様に実行する。
【０１０２】
ペンティアム（登録商標）４、２．８ＧＨｚのＰＣを用い、スケール倍率１．２５で処理対象窓のサイズを２４×２４〜２５６×２５６の範囲で変化させた場合、本発明のＭＶＦＤは３２０×２４０の画像の検出を約４０ｍｓで実行することができた。非特許文献７の方法で８０ｍｓかかっていることと比べると、所要時間が半分に減っている。この顕著な改善は幅優先探索木構造及びそれに関する学習アルゴリズムであるベクトルブースティングに由来する。
【０１０３】
ＭＶＦＤでは±４５度の平面内回転をカバーしているので、ＭＶＦＤを単純に９０度、１８０度、２７０度回転させることで３６０度の平面内回転を十分にカバーできるように３つの検出器を構成することができる。これらの検出器は一緒に動作することで回転不変の問題を処理する。また、仕様はペンティアム（登録商標）４で、２．８ＧＨｚのＰＣにおいて、３２０×２４０のビデオ系での速度は約１１ｆｐｓとなり、これは非特許文献７（２５０ｍｓ／フレーム）の方法より１．５倍速い。
【０１０４】
以上の実施形態は本発明を説明するためのものであり、本発明を限定するものではない。
【図面の簡単な説明】
【０１０５】
【図１】図１（ａ）はパラレルカスケード構造を示す図であり、図１（ｂ）はピラミッド構造を示す図であり、図１（ｃ）は決定木構造を示す図である。
【図２】図２は本発明に係る木構造を示す図である。
【図３】図３は出力空間Ｈ（ｘ）における３つのクラスの分布を示している。
【図４ａ】図４ａはハール（Ｈａａｒ）特徴の分布を示している。
【図４ｂ】図４ｂはハール（Ｈａａｒ）特徴の分布を示している。
【図５ａ】図５ａは閾値型弱判別器の特性図である。
【図５ｂ】図５ｂは分級（Piece-wise）型弱判別器の特性図である。
【図６】図６は回転不変性を有するＭＶＦＤの結果図である。
【図７】図７（ａ）−（ｅ）は本発明に係る木構造のベクトルブースティングアルゴリズムと、ピラミッド構造のリアルアダブーストアルゴリズムとの特徴区分性の効果対照図である。
【図８ａ】図８ａは本発明に係る装置の機能ブロック図である。
【図８ｂ】図８ｂは本発明に係る装置の機能ブロック図である。
【図９】図９は３つのルックアップテーブルを有する弱判別器を示す図である。
【図１０】図１０は３つの信頼度出力を有する層判別器を示す図である。
【図１１】図１１は本発明に係る木構造検出器を示す図である。
【図１２】図１２は木構造検出器における処理対象窓（sub-window）の検出処理を示す図である。
【図１】
0004801557.tif 000011
【図２】
0004801557.tif 000012
【図３】
0004801557.tif 000013
【図４ａ】
0004801557.tif 000014
【図４ｂ】
0004801557.tif 000015
【図５ａ】
0004801557.tif 000016
【図５ｂ】
0004801557.tif 000017
【図６】
0004801557.tif 000018
【図７】
0004801557.tif 000019
【図８ａ】
0004801557.tif 000020
【図８ｂ】
0004801557.tif 000021
【図９】
0004801557.tif 000022
【図１０】
0004801557.tif 000023
【図１１】
0004801557.tif 000024
【図１２】
0004801557.tif 000025