学習装置及び学習方法
【課題】入力データを、高速、かつ、高精度にパターン識別する識別器を構成することを目的とする。
【解決手段】分岐ノードは、パラメータに基づいて、次に起動するべきノードを決定するノードであり、識別ノードは、パラメータに基づいて、入力データが第２のクラスに属するかどうかを識別するノードであり、第１のクラスに属する学習データの特徴ベクトルに対して多変量解析を行い、方向ベクトルを求める多変量解析手段と、多変量解析手段で求められた方向ベクトルに対して垂直であって、学習データの特徴空間を分割する分割面を決定する分割面決定手段と、分割面決定手段で決定された分割面に基づいて、分岐ノードのパラメータを決定するパラメータ決定手段と、を有することによって課題を解決する。
【解決手段】分岐ノードは、パラメータに基づいて、次に起動するべきノードを決定するノードであり、識別ノードは、パラメータに基づいて、入力データが第２のクラスに属するかどうかを識別するノードであり、第１のクラスに属する学習データの特徴ベクトルに対して多変量解析を行い、方向ベクトルを求める多変量解析手段と、多変量解析手段で求められた方向ベクトルに対して垂直であって、学習データの特徴空間を分割する分割面を決定する分割面決定手段と、分割面決定手段で決定された分割面に基づいて、分岐ノードのパラメータを決定するパラメータ決定手段と、を有することによって課題を解決する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、学習装置及び学習方法に関する。
【背景技術】
【０００２】
従来、線形識別を用いたパターン識別が盛んに行われている。非特許文献１には線形識別のいくつかの例が解説されている。
簡単に説明すると、線形識別では、入力データを特徴ベクトルとして多次元空間内のベクトルで表し、これら特徴ベクトルが張る特徴空間を、超平面によって分割する。そして、入力データに対応する特徴ベクトルが、その超平面のどちら側に位置するかによって、入力データを識別する。更に、複数の超平面を用意すれば、これら超平面に囲まれた領域にある特徴ベクトルを１つのクラスとして識別することができる。非特許文献２には、このような例が開示されている。
前記識別器は比較的処理が高速である反面、線形識別を論理積によって統合した構造を採用している。そのため、識別したい特徴ベクトルの集合を、特徴空間内の超平面の片側或いは凸多面体としてしか表現することができない。つまり、凹凸のある集合を表現することができない。
【０００３】
この問題を克服するためにいくつかの方法が提案されている。最も一般的な方法は、個々の線形識別の結果を論理積以外の演算で統合する方法である。非特許文献１にも解説されている区分的識別関数を利用する方法はその一つである。これは集合の表面を複数の多角形で覆うという考え方である。また、決定木を使う方法もある。典型的な決定木は教師あり学習である。決定木を構築する際には、分岐先ノードの不純度という概念を利用するのが通例となっている。これは分岐先ノードにたどり着く入力データの種類のばらつきのことである。通常、決定木を構築する際には、この不純度が低下するように分岐条件を決定する。非特許文献３では教師なしで決定木を構築する方法が提案されている。しかし、非特許文献３でもやはり不純度の概念を導入し、これが低下するように分岐条件を定めている。
【０００４】
凹凸のある集合を表すための別の方法として、特徴空間の次元を増やすということも行われている。例えば、非特許文献２では、複数の弱判別器の結果を加算して強判別器という概念を導入している。しかしながら、特徴空間の次元を増やしても、その次元の増えた特徴空間の中で非凹多面体しか表せないという本質的な問題は解決されない。
教師なしで決定木を構築する方法は、クラスタリングと似通ったところがある。クラスタリングでは、クラスの分からないデータを複数の集合に分割する。非特許文献４は、階層的に入力データを分割していくクラスタリングの１つの手法を提案している。その際、できあがったクラスタを次々と２つずつに分割していく。できあがる２つのクラスタが、それぞれなるべくガウス分布に近くなるように作られる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】石井、上田、前田、村瀬 （１９９８） "わかりやすいパターン認識"、オーム社．
【非特許文献２】Ｖｉｏｌａ ＆ Ｊｏｎｅｓ （２００１） "Ｒａｐｉｄ Ｏｂｊｅｃｔ Ｄｅｔｅｃｔｉｏｎ ｕｓｉｎｇ ａ Ｂｏｏｓｔｅｄ Ｃａｓｃａｄｅ ｏｆ Ｓｉｍｐｌｅ Ｆｅａｔｕｒｅｓ"， Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ （ＣＶＰＲ）， Ｖｏｌ．１， ｐ．５５１．
【非特許文献３】Ｂａｓａｋ ＆ Ｋｒｉｓｈｎａｐｕｒａｍ （２００５） "Ｉｎｔｅｒｐｒｅｔａｂｌｅ Ｈｉｅｒａｒｃｈｉｃａｌ Ｃｌｕｓｔｅｒｉｎｇ ｂｙ Ｃｏｎｓｔｒｕｃｔｉｎｇ ａｎ Ｕｎｓｕｐｅｒｖｉｓｅｄ Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ"， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｖｏｌ．１７ （１）， ｐ．１２１．
【非特許文献４】Ｍｉａｓｎｉｋｏｖ， Ｒｏｍｅ ＆ Ｈａｒａｌｉｃｋ （２００４） "Ａ Ｈｉｅｒａｒｃｈｉｃａｌ Ｐｒｏｊｅｃｔｉｏｎ Ｐｕｒｓｕｉｔ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ"， Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ， Ｖｏｌ． １， ｐ．２６８．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述したように従来技術では、入力データを高速、かつ、高精度にパターン識別する識別器を構成することができない問題があった。
【０００７】
本発明はこのような問題点に鑑みなされたもので、入力データを、高速、かつ、高精度にパターン識別する識別器を構成することを目的とする。
【課題を解決するための手段】
【０００８】
そこで、本発明は、識別ノードと分岐ノードとを複数、連結した木構造を有し、入力データを特徴空間のＳと〜Ｓとの２クラスに識別する識別器の、各ノードのパラメータを決定する学習装置であって、前記分岐ノードは、前記パラメータに基づいて、次に起動するべきノードを決定するノードであり、前記識別ノードは、前記パラメータに基づいて、入力データが〜Ｓに属するかどうかを識別するノードであり、前記Ｓと〜Ｓとの何れかに属する学習データに基づいて、前記Ｓに属する学習データの特徴ベクトルに対して多変量解析を行い、方向ベクトルを求める多変量解析手段と、前記多変量解析手段で求められた前記方向ベクトルに対して垂直であって、学習データの特徴空間を分割する分割面を決定する分割面決定手段と、前記分割面決定手段で決定された前記分割面に基づいて、前記分岐ノードのパラメータを決定するパラメータ決定手段と、を有することを特徴とする。
かかる構成とすることにより、例えばパターン識別のための決定木を構築する際に分岐ノードのパラメータを適切に決定することができるため、入力データを、高速、かつ、高精度にパターン識別する識別器を構成することができる。
また、本発明は、学習方法としてもよい。
【発明の効果】
【０００９】
本発明によれば、入力データを、高速、かつ、高精度にパターン識別する識別器を構成することができる。
【図面の簡単な説明】
【００１０】
【図１】実施形態に係る情報処理装置のハードウェア構成の一例を示すブロック図である。
【図２】顔を検出する際の処理の流れを表すフローチャートである。
【図３】図２のデータフローチャートである。
【図４】パターン識別用パラメータ２１１を表すデータの構造を示す図である。
【図５】タイプＴ１のノードのデータ構造を表す図である。
【図６】タイプＴ２のノードのデータ構造を表す図である。
【図７】図２のステップＳ２０３の詳細を表すフローチャートである。
【図８】入力画像が分岐される様子を描いたイメージを表す図である。
【図９】ノードＮ３のための学習の大まかな処理の一例を示すフローチャートである。
【図１０】図９のステップＦ０１の詳細を表すフローチャートである。
【図１１】図９のステップＦ０３の詳細を表すフローチャート（その１）である。
【図１２】図９のステップＦ０３の詳細を表すフローチャート（その２）である。
【図１３】図１２のステップＦ０３１１の詳細を表すフローチャート（その１）である。
【図１４】目的関数を最小化する射影ベクトルｑ'を求める処理の一例を示すフローチャートである。
【図１５】図１２のステップＦ０３１１の詳細を表すフローチャート（その２）である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施形態について図面に基づいて説明する。
【００１２】
＜実施形態１＞
入力された画像に顔があるかどうかを判定する情報処理装置の例を示す。実施形態を簡単にするために、入力された画像はグレースケール画像であり、顔があればパスポート写真のようにほぼ中央にほぼ決められた大きさで配置されているものと仮定する。なお、画像を走査したり、画像を拡大・縮小するなどしたりすれば、任意の位置にある任意の大きさの顔を検出できるようになる。また、輝度値も正規化されているものとする。正規化の方法には、平均輝度との差分を取ったり、輝度の標準偏差で割ったりする方法がある。
図１は、実施形態に係る情報処理装置のハードウェア構成の一例を示すブロック図である。図１において、ＣＰＵ（中央演算装置）１００は、実施形態で説明するパターン識別用パラメータ学習方法をプログラムに従って実行する。プログラムメモリ１０１は、ＣＰＵ１００により実行されるプログラムが記憶されている。ＲＡＭ１０２は、ＣＰＵ１００によるプログラムの実行時に、各種情報を一時的に記憶するためのメモリを提供している。ハードディスク１０３は、画像ファイルやパターン識別用のパラメータなどを保存するための記憶媒体である。ディスプレイ１０４は、本実施形態の処理結果をユーザに提示する装置である。バス１１０は、これら各部とＣＰＵ１００とを接続している制御バス・データ バスである。
【００１３】
図２は、顔を検出する際の処理の流れを表すフローチャートである。
まずステップＳ２０１において、ＣＰＵ１００は、ハードディスク１０３より画像をＲＡＭ１０２に読み込む。画像は、ＲＡＭ１０２上では２次元配列として保持される。次のステップＳ２０２において、ＣＰＵ１００は、後述する学習方法により作成したパターン識別用パラメータをハードディスク１０３よりＲＡＭ１０２に読み込む。ステップＳ２０３において、ＣＰＵ１００は、ステップＳ２０２で読み込んだパターン識別用パラメータを使用して、ステップＳ２０１で読み込んだ画像内に顔があるかどうかを判定する。その結果を次のステップＳ２０４において、ＣＰＵ１００は、ディスプレイ１０４に表示する。
【００１４】
図２をデータフローチャートとして書き表すと図３ようになる。図３は、図２のデータフローチャートである。２０５は、ハードディスク１０３に保存されている画像である。２０１の画像の読み込み処理において、ハードディスク内の画像２０５がＲＡＭ１０２上に入力画像Ｉとして記憶される。２０９は、ハードディスク１０３に保存されているパターン識別用パラメータである。２１０のパターン識別用パラメータの読み込み処理において、ハードディスク１０３内のパターン識別用パラメータ２０９がＲＡＭ１０２上にパターン識別用パラメータ２１１として記憶される。２０３の検出処理では、ＣＰＵ１００が、先の入力画像Ｉとパターン識別用パラメータ２１１とを使用して、入力画像Ｉの中に顔があるかどうかを判定し、顔があるかどうかを２０７の検出結果としてＲＡＭ１０２に書き込む。２０４の検出結果表示処理では、ＣＰＵ１００が、検出結果２０７の内容をディスプレイ１０４に表示する。
【００１５】
ここで、２１１のパターン識別用パラメータの内容について図４や図５、図６を用いて簡単に説明する。パターン識別用パラメータ２１１を作成する方法については、後ほど記述する。図４は、パターン識別用パラメータ２１１を表すデータの構造を示す図である。図４において、正方形は木構造の各ノードを表している。また、矢印は各ノードの処理が実行される順番を表している。パターン識別用パラメータ２１１は、タイプＴ１とタイプＴ２とで表された２種類のノードをツリー状に接続した構造をしている。タイプＴ１のノードは、識別ノードであって、その後にはノードが１つだけ接続されている。また、タイプＴ２のノードは、分岐ノードであって、ノードの後にはノードが複数接続されている。Ｎ３と記されたノードもまたタイプＴ２のノードである。本実施形態は、タイプＴ１の種類によらず様々な種類の検出器（識別器）に適用できるが、ここでは非特許文献２に書かれているような弱判別器（ｗｅａｋ ｃｌａｓｓｉｆｉｅｒ）をタイプＴ１のノードに使用した例を示す。これ以外にもｌｉｎｅａｒ ｄｉｓｃｒｉｍｉｎａｎｔ ａｎａｌｙｓｉｓ（ＬＤＡ）やｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ（ＳＶＭ）等を使った検出器を利用することができる。また、これらを連結した検出器であってもよい。
【００１６】
以後の説明において、パラメータ・分岐先Ａ・分岐先Ｂ・集合Ｆ+・集合Ｇ+という表現を用いているが、これらは着目するノードによって内容が異なるものである。これらを用いて求めた値もノードによって異なる。本実施形態では煩雑さを避けるためにノードを示す添え字を省略している。
【００１７】
非特許文献２に書かれている弱判別器は、図４のタイプＴ１のノードに相当する。図５は、タイプＴ１のノードのデータ構造を表す図である。このデータは、ＲＡＭ１０２のメモリ上に複数格納される。個々のデータはそれぞれ値が異なるのが普通である。まず先頭にノードのタイプが格納されている。このノードはタイプＴ１なので、Ｔ１を表すコードがノードのタイプとして格納される。その次に矩形情報が格納されている。矩形情報の初めに矩形の個数ｎが格納されており、その後にその個数ｎだけの矩形の座標（左上点・右下点）が格納されている。これら複数の矩形をまとめて矩形群と呼ぶことにする。次に、打ち切りのためのパラメータが格納されている。ここで「打ち切り」とは、後に図７を用いて説明するが、簡単に言うと早めの段階で入力画像に顔がないと判断することである。打ち切り用パラメータの先頭には閾値θが格納されている。その後に、先の矩形の数ｎだけの打ち切りのための計算に利用する符号が並ぶ。ここで言う符号とは、＋１や−１のことである。最後に次のノードへのポインタが格納されている。
【００１８】
図６は、タイプＴ２のノードのデータ構造を表す図である。このデータも、ＲＡＭ１０２のメモリ上に複数格納される。個々のデータはそれぞれ値が異なるのが普通である。まず先頭にノードのタイプが格納されている。このノードはタイプＴ２なので、Ｔ２を表すコードがノードのタイプとして格納される。その次に矩形情報が格納されている。矩形情報の初めに矩形の個数ｎが格納されており、その後にその個数ｎだけの矩形の座標（左上点・右下点）が格納されている。次に分岐先Ａのためのパラメータが配置されている。分岐先Ａのためのパラメータには、打ち切り用パラメータ同様に閾値や矩形の係数が格納されているが、更に分岐先ノードＡへのポインタも格納されている。このポインタの指し示す先には、また別のノードのパラメータが格納されている。最後にもう１つの分岐先ノードＢへのポインタが格納されている。
【００１９】
上記パラメータの作成方法を説明する前に、このパラメータを使用して顔を検出する方法を説明する。検出処理の全体的な流れは、ＣＰＵ１００が、図４の各ノードを根ノード（図で最も上位に描かれているノード）から順にたどることによって行われる。処理するノードがタイプＴ１のノードである場合、ＣＰＵ１００は、図５に図示されたノードに固有のパラメータを用いて、入力画像Ｉに顔が含まれているかどうかを判定する。顔がない可能性が高いと判定した場合には、ＣＰＵ１００は、そこで処理を中断する。そうでない場合には、ＣＰＵ１００は、次のノードの処理へと移る。処理するノードがタイプＴ２のノードである場合には、ＣＰＵ１００は、図６に図示されたノードに固有のパラメータを用いて、次にどのノードに処理を移すかの判断を行う。このように順にノードをたどっていくことによって、ＣＰＵ１００は、タイプＴ１のノードでは打ち切りか継続かの判断を行い、タイプＴ２のノードでは分岐先ノードの選択を行う。ここで、タイプＴ１のノード、つまり識別ノードは、入力データを特徴空間のＳ（第１のクラス）と〜Ｓ（第２のクラス）との２クラスに識別する識別器において、パラメータに基づいて、入力データが〜Ｓに属するかどうかを識別するノードである。また、タイプＴ２のノード、つまり分岐ノードは、パラメータに基づいて、次に起動するべきノードを決定するノードである。
【００２０】
図７は、図２のステップＳ２０３の詳細を表すフローチャートである。初めのステップＤ１０において、ＣＰＵ１００は、ポインタ変数ｐを最初のノードを指すように初期化する。次のステップＤ０２において、ＣＰＵ１００は、ｐが指し示すノードの種類を確認する。ｐが指し示すノードがタイプＴ１の場合、ＣＰＵ１００は、ステップＤ１１に進む。逆にタイプＴ２の場合、ＣＰＵ１００は、ステップＤ２１へ進む。
ステップＤ１１において、ＣＰＵ１００は、変数ｃを０で初期化する。そして、ＣＰＵ１００は、ステップＤ１２からＤ１５までのループを矩形の数ｎ回だけ繰り返す。ループ内において、ＣＰＵ１００は、矩形を表すループ変数をｉとする。ステップＤ１３において、ＣＰＵ１００は、図５のノード情報から矩形ｉの対角線の座標（ｘiL， ｙiT）−（ｘiR，ｙiB）を取得し、その入力画像Ｉにおける矩形内の輝度値の総和を求める。ＣＰＵ１００は、これをｂiとする。ｂiは、非特許文献２に書かれているように累積情報（ｉｎｔｅｇｒａｌ ｉｍａｇｅ）を使って高速に求めることができる。そしてステップＤ１４において、ＣＰＵ１００は、変数ｃにｂiと矩形ｉの符号ａiの積を加算する。まとめると、このループでＣＰＵ１００が求めているのは、次の和である。
【００２１】
【数１】
【００２２】
ステップＤ１６において、ＣＰＵ１００は、この和ｃが図５の閾値θを超えているかどうか判定する。そして、ＣＰＵ１００は、θを超えていればステップＤ１７へ進み、検出結果２０７に「偽」の値を書き込む。これは顔が検出されなかったことを表す。ここで、図４で示されたツリーの処理は打ち切られる。ステップＤ１６において、ＣＰＵ１００は、和ｃが閾値θを超えていないと判断すると、次のステップＤ１８へ進む。ここではＣＰＵ１００は、全ノードの処理を終えたかどうか確認する。全ノードの処理が完了している場合、ＣＰＵ１００は、ステップＤ１９で検出結果２０７に「真」の値を書き込む。これにより顔が検出されたことになる。逆に、ステップＤ１８で全ノードの処理が完了していない場合、ＣＰＵ１００は、ステップＤ０５でポインタ変数ｐに次のノードへのポインタを格納する。そして、ＣＰＵ１００は、ステップＤ０２へと制御を戻す。
ステップＤ０２においてポインタ変数ｐが指すノードのタイプがＴ２であることになれば、ＣＰＵ１００は、ステップＤ２１からの処理を実行する。まずステップＤ２１において、ＣＰＵ１００は、変数ｃを０で初期化する。そしてステップＤ２２からＤ２５までのループでＣＰＵ１００は、次の内積値を求める。なお、ａAiは図６の矩形の係数である。
【００２３】
【数２】
【００２４】
ステップＤ２６において、ＣＰＵ１００は、内積値ｃが図６の閾値θAを超えているかどうか確認する。超えている場合、ＣＰＵ１００は、次のステップＤ２８へと進む。ステップＤ２８において、ＣＰＵ１００は、ポインタ変数ｐに図６の分岐先ノードＡへのポインタ値を代入する。そして、ＣＰＵ１００は、再びステップＤ０２からの処理を始める。ステップＤ２６で閾値を超えていなかった場合、ＣＰＵ１００は、ステップＤ３０へ進む。ここで、ＣＰＵ１００は、ポインタ変数ｐに図６の分岐先ノードＢへのポインタ値を代入する。そして、ＣＰＵ１００は、再びステップＤ０２からの処理を始める。この様子をイメージ図にしたのが図８である。図８は、入力画像が分岐される様子を描いたイメージを表す図である。図８には、丸や三角で描かれているのが、これらは、入力画像Ｉの特徴ベクトルｂｉである。入力画像Ｉが顔である場合は丸（Ｅ００やＥ０１）、顔でない場合には三角（Ｅ１０やＥ１１）として描かれている。Ｅ０２は、ｃ＝θAとなる超平面である。Ｅ０３がベクトルａA＝（ａA1，ａA2，・・・，ａAn）で、超平面Ｅ０２の法線ベクトルである。上記の分岐条件により、黒丸Ｅ０１として表示されている顔画像と黒塗りの三角Ｅ１１として表示されている非顔画像とが分岐先Ａへと振り分けられることになる。また、白丸Ｅ００として表示されている顔画像と白抜きの三角Ｅ１０として表示されている非顔画像とが分岐先Ｂへ振り分けられることになる。以上の処理で、図４のツリーのノードを遷移していくことになる。図４に示されているとおり、タイプＴ２のノードを連続させることもできる。そうすることによって、より複雑な分岐が可能となる。或いは、複数の閾値を用意することによって、３つ以上の分岐先の中から１つを選ぶこともできる。
【００２５】
図５に示されるタイプＴ１のノードのパラメータを求めるための学習手順は、非特許文献２に示されるとおりである。ここで、図５の各矩形となる候補は学習前に予め提示されていると考えると分かりやすい。これら矩形の集合をＲ ＝ ｛ｒi｜ｉ ＝ １・・・Ｎr｝とする。当然のことながら、集合Ｒは規則的に生成されても、乱数によって生成されてもよい。
図６に示されるタイプＴ２のノードのパラメータを求めるための本実施形態における学習手順を示す。まず、前提として学習用の顔画像ｆjの集合Ｆ ＝ ｛ｆj ｜ ｊ ＝ １・・・Ｎf｝があり、顔の写っていない学習画像ｇjの集合Ｇ ＝ ｛ｇj ｜ ｇj ＝ １・・・Ｎg｝が用意されているものとする。更に、図４のツリー構造は予め決められており、パラメータを確保するためのメモリがＲＡＭ１０２上に確保されているものとする。例えば、あくまでも例であるが、図４のように分岐数が３本になるまで２回に１回分岐が起こるように分岐ノードを配置することができる。このとき、図５や図６の各ポインタ値も確定しており、格納しておくことができる。そこで、図４においてＴ１と記されているノードからＮ３と記されているノードの直前（つまり、ここではＴ２と書かれているノード）までの学習が済んでいるものとする。前述した検出の処理を適用すると、Ｎ３までのノードで学習画像のいくつかは顔がないものとして棄却（打ち切り）されたり、タイプＴ２のノードによって他の分岐先に振り分けられたりする。そこで、ＣＰＵ１００は、Ｎ３のノードでは、それまでに棄却されたり他の分岐先に振り分けられたりしない顔画像ｆj+の集合Ｆ+ ＝ ｛ｆj+ ｜ ｊ ＝ １・・・Ｎf+｝と非顔画像ｇj+の集合Ｇ+ ＝ ｛ｇj+ ｜ ｊ ＝ １・・・Ｎg+｝とを学習に利用する。
【００２６】
ノードＮ３のための学習の大まかな流れを図９に示す。まず、ステップＦ０１において、ＣＰＵ１００は、学習画像Ｆ+を特徴ベクトルの集合として表す。次にステップＦ０３において、ＣＰＵ１００は、特徴ベクトルの集合を用いて、学習データの特徴空間を分割する特徴空間内の超平面を決定し（分割面決定）、ノードＮ３のパラメータとして書き込む（パラメータ決定）。
次に、これら各ステップの詳細を説明する。
図１０は、図９のステップＦ０１の詳細を表すフローチャートである。ステップＦ０１０１からＦ０１０７までのループは、学習画像Ｆ+に属する各顔画像ｆj+に関する処理である。ステップＦ０１０３からステップＦ０１０５までのループは、矩形候補集合Ｒに属する各矩形ｒiに対して繰り返す。そしてステップＦ０１０４でＣＰＵ１００は、２次元配列の要素ｂjifに、顔画像ｆj+上の矩形ｒi内にあるピクセルの輝度値の総和を代入する。以上の処理により、学習画像の集合Ｆ+の各画像に対してＮr次元の特徴ベクトルが対応付けられたことになる。特徴空間の各次元は、それぞれある矩形の中の輝度値総和に対応する。学習画像の集合Ｆ+に対応する特徴ベクトルの集合をＢF+ ＝ ｛ ｂjf ｜ ｂjf ＝ （ｂj1f， ｂj2f，・・・， ｂjNrf）｝とする。
【００２７】
図９のステップＦ０３でＣＰＵ１００は、ステップＦ０１で求められたベクトルに対して垂直であって、学習データの特徴空間を分割する分割超平面を決定する（分割面決定）。分割超平面は、分割面の一例である。ステップＦ０３の流れを図１１のフローチャートに示す。図１１は、図９のステップＦ０３の詳細を表すフローチャート（その１）である。
まず、ステップＦ０３０１において、ＣＰＵ１００は、顔特徴ベクトルの集合ＢF+の第１主成分方向ベクトルを求める。ここでいう第１主成分方向とは、集合ＢF+の散らばりが最大となる方向である。ＣＰＵ１００は、ｓｉｎｇｕｌａｒ−ｖａｌｕｅ ｄｅｃｏｍｐｏｓｉｔｉｏｎ （ＳＶＤ）やｐｒｉｎｃｉｐａｌ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ （ＰＣＡ；主成分分析）等の多変量解析の手法を用いて主成分方向ベクトルを求めることができる。或いはＣＰＵ１００は、ｉｎｄｅｐｅｎｄｅｎｔ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ（ＩＣＡ；独立成分分析）等の多変量解析の手法を用いて主成分方向ベクトルを求めることもできる。ここで得られた主成分方向ベクトルをｄ ＝ （ｄ1， ｄ2，・・・， ｄNr）とする。次にステップＦ０３０２において、ＣＰＵ１００は、この主成分方向ベクトルｄの次元を削減する。より具体的に説明すると、ＣＰＵ１００は、ｎを予め決められた値として、ｄの成分の中で絶対値が大きい上位ｎ個の成分を取り出し、ａA ＝ （ａA1， ａA2，・・・， ａAn）とする。ｎは値を大きく取るとその分計算に時間を要することになるので、大きくしすぎないことが必要である。ｄの各次元はそれぞれＲ内の矩形１つに対応する。このことに着目して、ＣＰＵ１００は、ａAの各要素に対応する矩形を並べることができる。これをｒA ＝ （ｒA1， ｒA2，・・・， ｒAn）とする。ａAの各成分はＣＰＵ１００によって図６の分岐先Ａ用パラメータの該当する領域に書き込まれ、ｎとｒAとの各矩形の座標がＣＰＵ１００によって図６の矩形情報として書き込まれる。なお、次元削減の方法は、上記方法に限らない。例えば、ＣＰＵ１００は、ベクトルｄの中の絶対値と対応する矩形面積との積が大きい上位ｎ個の成分を取り出すこともできる。また、ＣＰＵ１００は、次元削減を行わないことも可能である。
主成分方向ベクトルは、方向ベクトルの一例である。
【００２８】
残る閾値θAは、図１１のステップＦ０３０３で求められる。閾値θAを求める方法の一例を式で表すと、前述のＢF+の重心ｃを用いて、次のように表される。
【００２９】
【数３】
【００３０】
ここで、ｂjAfは、ｂjfからｒA＝ （ｒA1， ｒA2，・・・， ｒAn）に対応する成分を取り出したベクトルである。ｗj＝１でもよいが、非特許文献２に書かれているようなＡｄａｂｏｏｓｔの重みでもよい。
【００３１】
以上の方法によりタイプＴ１とタイプＴ２とのノードのパラメータを学習することにより、図４に示したツリー構造のパラメータを用意することができる。そして、このパラメータを使用することにより、比較的計算負荷の軽い処理により入力画像中の顔を検出することができる。本実施形態では、主成分方向を求めるためにＰＣＡ等を利用したが、当然のことながらｋｅｒｎｅｌ ＰＣＡ等の非線形な手法を用いることもできる。また、これまでの説明から、識別器は、顔の識別に限るものでなく、人物や図形や文字等他の画像も扱えることは明らかである。
【００３２】
＜実施形態２＞
実施形態１では、主成分分析等を行ってから次元削減を行ったが、実施形態２では次元削減を行ってから、ｉｎｄｅｐｅｎｄｅｎｔ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ（ＩＣＡ；独立成分分析）等を行う例を示す。
本実施形態では、図１１の代わりに図１２を利用する。図１２は、図９のステップＦ０３の詳細を表すフローチャート（その２）である。
ステップＦ０３１１において、ＣＰＵ１００は、分割超平面の法線ベクトルを求める。そして、ステップＦ０３１３において、ＣＰＵ１００は、図１１のステップＦ０３０３と同じ手順（同じ処理）で閾値θAを求める。
【００３３】
図１３は、図１２のステップＦ０３１１の詳細を表すフローチャート（その１）である。
ステップＧ０１において、ＣＰＵ１００は、矩形の集合Ｒのなかからいくつかの矩形の組み合わせを選び、その組み合わせの集合をＲＣとする。それぞれの組み合わせでの矩形の数ｍは、例えば２のように一定であってもよいが、不揃いであってもよい。不揃いの場合には、ＣＰＵ１００は、根ノードから数えたノード数に応じて、ｍが単調に増加するように選んでもよい。ＣＰＵ１００は、矩形の組み合わせ集合ＲＣの各組み合わせｒC＝（ｒC1，ｒC2，・・・，ｒCm）（Ｃ1〜Ｃmは矩形の番号を表すインデックス）について、ステップＧ０２からＧ０６までのループを繰り返す。
【００３４】
次にステップＧ０３において、ＣＰＵ１００は、集合ＢF+の各特徴ベクトルｂjfについて、ｒC＝（ｒC1，ｒC2，・・・，ｒCm）の各要素（矩形）に対応する成分を取り出した特徴ベクトル
【数４】
を生成する。もし、ｒC＝（ｒ5，ｒ236，ｒ5468
）の場合、
【数５】
は、（ｂj,5f，ｂj,236f，ｂj,5468f）となる。つまり、学習画像ｆ
j+上の矩形ｒ5とｒ236とｒ5468内の輝度値総和を並べたベクトルとなる。
【００３５】
ステップＧ０４において、ＣＰＵ１００は、これらｍ次元のベクトルの集合
【数６】
に対してＩＣＡを適用し、最大でｍ本のｍ次元ベクトルｑk（ｋ＝１，・・・，ｍq；ｍq≦ｍ）を得る。ＩＣＡを適用する際の目的関数には例えば次のような関数Ｊ（ｑ）を選ぶことができる。ここで、ｖは平均０、分散１の正規分布に従う確率変数である。
【００３６】
【数７】
【００３７】
次にステップＧ０５において、ＣＰＵ１００は、評価値として集合
【数８】
の尖度（ｋｕｒｔｏｓｉｓ）の符号を反転したものを計算する。より具体的に説明すると、ＣＰＵ１００は、次の値を求める（射影評価）。
【００３８】
【数９】
【００３９】
或いはＣＰＵ１００は、評価値としてｃｏｎｔｒａｓｔ ｆｕｎｃｔｉｏｎや目的関数を使用してもよい。ループを抜けると、ＣＰＵ１００は、ステップＧ０７で評価値が最も大きかったベクトルｑkとそのときの矩形組み合わせｒとを、それぞれａAとｒAとして選択する（最適化）。なお、ベクトルｑkは、射影ベクトルと学習データの特徴ベクトルとの内積値の集合に関する統計量の一例である。つまり、ＣＰＵ１００は、ベクトルｑkを最大化又は最小化する射影ベクトルｑを求め、方向ベクトルとする。
【００４０】
以上の方法でタイプＴ１とタイプＴ２とのノードのパラメータを学習することにより、図４に示したツリー構造のパラメータを用意することができる。そして、このパラメータを使用することにより、比較的計算負荷の軽い処理により入力画像中の顔を検出することができる。特に本実施形態では、全ての組み合わせｒCに共通する評価関数によって評価値を求めて比較することによって、分割超平面の法線ベクトルを求めるだけでなく、次元削減において使用する成分の選択も行っている。なお、本実施形態では、超平面の法線ベクトルを求めるためにＩＣＡを使用したが、ＰＣＡやＳＶＤ等他の手法を使用することもできる。
【００４１】
＜実施形態３＞
実施形態２では、尖度が正規分布からより乖離した射影ベクトルｑを、ＩＣＡを使って求める方法を示した。この方法は、尖度が小さい射影ベクトルだけでなく、尖度が大きい射影ベクトルも求めてしまうことになる。本実施形態では、射影追跡法を利用して、直接尖度が小さい射影ベクトルのみを求める方法を示す。本実施形態でも、尖度は正規分布からの乖離度を表す指標の例として用いる。実施形態２とほぼ同じ構成であるが、図１３の代わりに本実施形態では図１５を使用する。
【００４２】
まず射影ベクトルｑ'を極座標系で表現する。
【数１０】
【００４３】
また、
【数１１】
を次式に従って平行移動させる。
【数１２】
【００４４】
そして、目的関数は以下の通りとする。
【数１３】
【００４５】
この目的関数を最小化する射影ベクトルｑ'を求める方法のフローチャートを図１４に示す。図１４は、目的関数を最小化する射影ベクトルｑ'を求める処理の一例を示すフローチャートである。
ステップＫ０１において、ＣＰＵ１００は、θi（ｉ＝１，・・・，ｍ）を所定の値で初期化する。例えば、ＣＰＵ１００は、θi＝０（ｉ＝１，・・・，ｍ）とすることができる。或いは、ＣＰＵ１００は、前記値を乱数で生成することもできる。また、ＣＰＵ１００は、収束条件のためのカウンタ変数ｓを０に初期化する。
【００４６】
ＣＰＵ１００は、ステップＫ０２から繰り返し処理に入る。まずステップＫ０２において、ＣＰＵ１００は、θ+を生成する。より具体的に説明すると、ＣＰＵ１００は、まず乱数により自然数ｕ（１≦ｕ≦ｍ−１）とΔを生成する。Δは、例えば平均０の正規分布をなすものとする。そしてθ+はθの第ｕ成分にΔを足したものとする。つまり、次式の通りとする。θi（ｉ＝１，．．．，ｍ）はθの第ｉ成分である。
θi+＝θi（ｉ≠ｕ）
θu+＝θu＋Δ
【００４７】
次に、ステップＫ０３において、ＣＰＵ１００は、目的関数の増減を調べる。より具体的に説明すると、ＣＰＵ１００は、（式１）にθを代入して射影ベクトルｑ'を求め、Ｊ（ｑ'）を計算する。次にＣＰＵ１００は、θの代わりにθ+を使って射影ベクトルｑ+'を求め、Ｊ（ｑ+'）を計算する。ＣＰＵ１００は、Ｊ（ｑ'）≦Ｊ（ｑ+'）であれば、ステップＫ０６へ進み、逆であればステップＫ０４へ進む。
ステップＫ０４において、ＣＰＵ１００は、カウンタ変数ｓを０に初期化する。そして、ステップＫ０５において、ＣＰＵ１００は、θにθ+を代入して、再びステップＫ０２よりループを繰り返す。ステップＫ０６において、ＣＰＵ１００は、カウンタ変数ｓを１つ増分させる。そして、ステップＫ０７において、ＣＰＵ１００は、予め定められた定数Ｓとｓとを比較し、まだｓ＜Ｓであれば、ステップＫ０２よりループを繰り返す。逆にｓ≦ＳであればＣＰＵ１００は、最小化処理を中止する。これにより、目的関数の値がＳ回改善されなければループを抜けることになる。このときのθから求めた射影ベクトルｑ'を、目的関数を最小化する値として扱う。
【００４８】
ステップＫ０３において、ＣＰＵ１００は、逐次Ｊ（ｑ'）を評価しているので、実施形態２の図１３のステップＧ０５ように評価値（Ｊ（ｑ'）の値）を再度計算する必要がない。そのため、図１３の代わりに本実施形態では図１５に従う。ステップＬ０４の詳細は図１４に示したとおりである。
【００４９】
以上、尖度を最小化する射影ベクトルを求める方法を示した。本実施形態ではこの射影ベクトルを用いてタイプＴ２ノードの分割超平面を決定する。
なお、上述した最適化手法以外にも、ニュートン法等他の最適化手法によって射影ベクトルを求めるようにしてもよい。
また、これまでの実施形態では矩形特徴を用いた例を示したが、本発明はこれに限定されるものではない。特徴量としては、入力画像のピクセル値、入力画像にガボール フィルタをかけた特徴量、また局所特徴と呼ばれ入力画像の個々のピクセルにベクトルを割り当てるもの等がある。このようにパターン認識の分野においては、数多くの特徴量が定義されている。また、これまで顔の識別を例に取り上げたが、本発明は、画像のみならず、音声情報やアンケート結果等、他の情報にも適用することができる。
【００５０】
以上、上述した各実施形態によれば、パターン識別のための決定木を構築する際に、分岐ノードのパラメータを適切に決定することができるため、入力データを、高速、かつ、高精度にパターン識別する識別器を構成することができる。
【００５１】
以上、本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００５２】
１００ ＣＰＵ、１０１ プログラムメモリ、１０２ ＲＡＭ、１０３ ハードディスク、１０４ ディスプレイ
【技術分野】
【０００１】
本発明は、学習装置及び学習方法に関する。
【背景技術】
【０００２】
従来、線形識別を用いたパターン識別が盛んに行われている。非特許文献１には線形識別のいくつかの例が解説されている。
簡単に説明すると、線形識別では、入力データを特徴ベクトルとして多次元空間内のベクトルで表し、これら特徴ベクトルが張る特徴空間を、超平面によって分割する。そして、入力データに対応する特徴ベクトルが、その超平面のどちら側に位置するかによって、入力データを識別する。更に、複数の超平面を用意すれば、これら超平面に囲まれた領域にある特徴ベクトルを１つのクラスとして識別することができる。非特許文献２には、このような例が開示されている。
前記識別器は比較的処理が高速である反面、線形識別を論理積によって統合した構造を採用している。そのため、識別したい特徴ベクトルの集合を、特徴空間内の超平面の片側或いは凸多面体としてしか表現することができない。つまり、凹凸のある集合を表現することができない。
【０００３】
この問題を克服するためにいくつかの方法が提案されている。最も一般的な方法は、個々の線形識別の結果を論理積以外の演算で統合する方法である。非特許文献１にも解説されている区分的識別関数を利用する方法はその一つである。これは集合の表面を複数の多角形で覆うという考え方である。また、決定木を使う方法もある。典型的な決定木は教師あり学習である。決定木を構築する際には、分岐先ノードの不純度という概念を利用するのが通例となっている。これは分岐先ノードにたどり着く入力データの種類のばらつきのことである。通常、決定木を構築する際には、この不純度が低下するように分岐条件を決定する。非特許文献３では教師なしで決定木を構築する方法が提案されている。しかし、非特許文献３でもやはり不純度の概念を導入し、これが低下するように分岐条件を定めている。
【０００４】
凹凸のある集合を表すための別の方法として、特徴空間の次元を増やすということも行われている。例えば、非特許文献２では、複数の弱判別器の結果を加算して強判別器という概念を導入している。しかしながら、特徴空間の次元を増やしても、その次元の増えた特徴空間の中で非凹多面体しか表せないという本質的な問題は解決されない。
教師なしで決定木を構築する方法は、クラスタリングと似通ったところがある。クラスタリングでは、クラスの分からないデータを複数の集合に分割する。非特許文献４は、階層的に入力データを分割していくクラスタリングの１つの手法を提案している。その際、できあがったクラスタを次々と２つずつに分割していく。できあがる２つのクラスタが、それぞれなるべくガウス分布に近くなるように作られる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】石井、上田、前田、村瀬 （１９９８） "わかりやすいパターン認識"、オーム社．
【非特許文献２】Ｖｉｏｌａ ＆ Ｊｏｎｅｓ （２００１） "Ｒａｐｉｄ Ｏｂｊｅｃｔ Ｄｅｔｅｃｔｉｏｎ ｕｓｉｎｇ ａ Ｂｏｏｓｔｅｄ Ｃａｓｃａｄｅ ｏｆ Ｓｉｍｐｌｅ Ｆｅａｔｕｒｅｓ"， Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ （ＣＶＰＲ）， Ｖｏｌ．１， ｐ．５５１．
【非特許文献３】Ｂａｓａｋ ＆ Ｋｒｉｓｈｎａｐｕｒａｍ （２００５） "Ｉｎｔｅｒｐｒｅｔａｂｌｅ Ｈｉｅｒａｒｃｈｉｃａｌ Ｃｌｕｓｔｅｒｉｎｇ ｂｙ Ｃｏｎｓｔｒｕｃｔｉｎｇ ａｎ Ｕｎｓｕｐｅｒｖｉｓｅｄ Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ"， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｖｏｌ．１７ （１）， ｐ．１２１．
【非特許文献４】Ｍｉａｓｎｉｋｏｖ， Ｒｏｍｅ ＆ Ｈａｒａｌｉｃｋ （２００４） "Ａ Ｈｉｅｒａｒｃｈｉｃａｌ Ｐｒｏｊｅｃｔｉｏｎ Ｐｕｒｓｕｉｔ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ"， Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ， Ｖｏｌ． １， ｐ．２６８．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述したように従来技術では、入力データを高速、かつ、高精度にパターン識別する識別器を構成することができない問題があった。
【０００７】
本発明はこのような問題点に鑑みなされたもので、入力データを、高速、かつ、高精度にパターン識別する識別器を構成することを目的とする。
【課題を解決するための手段】
【０００８】
そこで、本発明は、識別ノードと分岐ノードとを複数、連結した木構造を有し、入力データを特徴空間のＳと〜Ｓとの２クラスに識別する識別器の、各ノードのパラメータを決定する学習装置であって、前記分岐ノードは、前記パラメータに基づいて、次に起動するべきノードを決定するノードであり、前記識別ノードは、前記パラメータに基づいて、入力データが〜Ｓに属するかどうかを識別するノードであり、前記Ｓと〜Ｓとの何れかに属する学習データに基づいて、前記Ｓに属する学習データの特徴ベクトルに対して多変量解析を行い、方向ベクトルを求める多変量解析手段と、前記多変量解析手段で求められた前記方向ベクトルに対して垂直であって、学習データの特徴空間を分割する分割面を決定する分割面決定手段と、前記分割面決定手段で決定された前記分割面に基づいて、前記分岐ノードのパラメータを決定するパラメータ決定手段と、を有することを特徴とする。
かかる構成とすることにより、例えばパターン識別のための決定木を構築する際に分岐ノードのパラメータを適切に決定することができるため、入力データを、高速、かつ、高精度にパターン識別する識別器を構成することができる。
また、本発明は、学習方法としてもよい。
【発明の効果】
【０００９】
本発明によれば、入力データを、高速、かつ、高精度にパターン識別する識別器を構成することができる。
【図面の簡単な説明】
【００１０】
【図１】実施形態に係る情報処理装置のハードウェア構成の一例を示すブロック図である。
【図２】顔を検出する際の処理の流れを表すフローチャートである。
【図３】図２のデータフローチャートである。
【図４】パターン識別用パラメータ２１１を表すデータの構造を示す図である。
【図５】タイプＴ１のノードのデータ構造を表す図である。
【図６】タイプＴ２のノードのデータ構造を表す図である。
【図７】図２のステップＳ２０３の詳細を表すフローチャートである。
【図８】入力画像が分岐される様子を描いたイメージを表す図である。
【図９】ノードＮ３のための学習の大まかな処理の一例を示すフローチャートである。
【図１０】図９のステップＦ０１の詳細を表すフローチャートである。
【図１１】図９のステップＦ０３の詳細を表すフローチャート（その１）である。
【図１２】図９のステップＦ０３の詳細を表すフローチャート（その２）である。
【図１３】図１２のステップＦ０３１１の詳細を表すフローチャート（その１）である。
【図１４】目的関数を最小化する射影ベクトルｑ'を求める処理の一例を示すフローチャートである。
【図１５】図１２のステップＦ０３１１の詳細を表すフローチャート（その２）である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施形態について図面に基づいて説明する。
【００１２】
＜実施形態１＞
入力された画像に顔があるかどうかを判定する情報処理装置の例を示す。実施形態を簡単にするために、入力された画像はグレースケール画像であり、顔があればパスポート写真のようにほぼ中央にほぼ決められた大きさで配置されているものと仮定する。なお、画像を走査したり、画像を拡大・縮小するなどしたりすれば、任意の位置にある任意の大きさの顔を検出できるようになる。また、輝度値も正規化されているものとする。正規化の方法には、平均輝度との差分を取ったり、輝度の標準偏差で割ったりする方法がある。
図１は、実施形態に係る情報処理装置のハードウェア構成の一例を示すブロック図である。図１において、ＣＰＵ（中央演算装置）１００は、実施形態で説明するパターン識別用パラメータ学習方法をプログラムに従って実行する。プログラムメモリ１０１は、ＣＰＵ１００により実行されるプログラムが記憶されている。ＲＡＭ１０２は、ＣＰＵ１００によるプログラムの実行時に、各種情報を一時的に記憶するためのメモリを提供している。ハードディスク１０３は、画像ファイルやパターン識別用のパラメータなどを保存するための記憶媒体である。ディスプレイ１０４は、本実施形態の処理結果をユーザに提示する装置である。バス１１０は、これら各部とＣＰＵ１００とを接続している制御バス・データ バスである。
【００１３】
図２は、顔を検出する際の処理の流れを表すフローチャートである。
まずステップＳ２０１において、ＣＰＵ１００は、ハードディスク１０３より画像をＲＡＭ１０２に読み込む。画像は、ＲＡＭ１０２上では２次元配列として保持される。次のステップＳ２０２において、ＣＰＵ１００は、後述する学習方法により作成したパターン識別用パラメータをハードディスク１０３よりＲＡＭ１０２に読み込む。ステップＳ２０３において、ＣＰＵ１００は、ステップＳ２０２で読み込んだパターン識別用パラメータを使用して、ステップＳ２０１で読み込んだ画像内に顔があるかどうかを判定する。その結果を次のステップＳ２０４において、ＣＰＵ１００は、ディスプレイ１０４に表示する。
【００１４】
図２をデータフローチャートとして書き表すと図３ようになる。図３は、図２のデータフローチャートである。２０５は、ハードディスク１０３に保存されている画像である。２０１の画像の読み込み処理において、ハードディスク内の画像２０５がＲＡＭ１０２上に入力画像Ｉとして記憶される。２０９は、ハードディスク１０３に保存されているパターン識別用パラメータである。２１０のパターン識別用パラメータの読み込み処理において、ハードディスク１０３内のパターン識別用パラメータ２０９がＲＡＭ１０２上にパターン識別用パラメータ２１１として記憶される。２０３の検出処理では、ＣＰＵ１００が、先の入力画像Ｉとパターン識別用パラメータ２１１とを使用して、入力画像Ｉの中に顔があるかどうかを判定し、顔があるかどうかを２０７の検出結果としてＲＡＭ１０２に書き込む。２０４の検出結果表示処理では、ＣＰＵ１００が、検出結果２０７の内容をディスプレイ１０４に表示する。
【００１５】
ここで、２１１のパターン識別用パラメータの内容について図４や図５、図６を用いて簡単に説明する。パターン識別用パラメータ２１１を作成する方法については、後ほど記述する。図４は、パターン識別用パラメータ２１１を表すデータの構造を示す図である。図４において、正方形は木構造の各ノードを表している。また、矢印は各ノードの処理が実行される順番を表している。パターン識別用パラメータ２１１は、タイプＴ１とタイプＴ２とで表された２種類のノードをツリー状に接続した構造をしている。タイプＴ１のノードは、識別ノードであって、その後にはノードが１つだけ接続されている。また、タイプＴ２のノードは、分岐ノードであって、ノードの後にはノードが複数接続されている。Ｎ３と記されたノードもまたタイプＴ２のノードである。本実施形態は、タイプＴ１の種類によらず様々な種類の検出器（識別器）に適用できるが、ここでは非特許文献２に書かれているような弱判別器（ｗｅａｋ ｃｌａｓｓｉｆｉｅｒ）をタイプＴ１のノードに使用した例を示す。これ以外にもｌｉｎｅａｒ ｄｉｓｃｒｉｍｉｎａｎｔ ａｎａｌｙｓｉｓ（ＬＤＡ）やｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ（ＳＶＭ）等を使った検出器を利用することができる。また、これらを連結した検出器であってもよい。
【００１６】
以後の説明において、パラメータ・分岐先Ａ・分岐先Ｂ・集合Ｆ+・集合Ｇ+という表現を用いているが、これらは着目するノードによって内容が異なるものである。これらを用いて求めた値もノードによって異なる。本実施形態では煩雑さを避けるためにノードを示す添え字を省略している。
【００１７】
非特許文献２に書かれている弱判別器は、図４のタイプＴ１のノードに相当する。図５は、タイプＴ１のノードのデータ構造を表す図である。このデータは、ＲＡＭ１０２のメモリ上に複数格納される。個々のデータはそれぞれ値が異なるのが普通である。まず先頭にノードのタイプが格納されている。このノードはタイプＴ１なので、Ｔ１を表すコードがノードのタイプとして格納される。その次に矩形情報が格納されている。矩形情報の初めに矩形の個数ｎが格納されており、その後にその個数ｎだけの矩形の座標（左上点・右下点）が格納されている。これら複数の矩形をまとめて矩形群と呼ぶことにする。次に、打ち切りのためのパラメータが格納されている。ここで「打ち切り」とは、後に図７を用いて説明するが、簡単に言うと早めの段階で入力画像に顔がないと判断することである。打ち切り用パラメータの先頭には閾値θが格納されている。その後に、先の矩形の数ｎだけの打ち切りのための計算に利用する符号が並ぶ。ここで言う符号とは、＋１や−１のことである。最後に次のノードへのポインタが格納されている。
【００１８】
図６は、タイプＴ２のノードのデータ構造を表す図である。このデータも、ＲＡＭ１０２のメモリ上に複数格納される。個々のデータはそれぞれ値が異なるのが普通である。まず先頭にノードのタイプが格納されている。このノードはタイプＴ２なので、Ｔ２を表すコードがノードのタイプとして格納される。その次に矩形情報が格納されている。矩形情報の初めに矩形の個数ｎが格納されており、その後にその個数ｎだけの矩形の座標（左上点・右下点）が格納されている。次に分岐先Ａのためのパラメータが配置されている。分岐先Ａのためのパラメータには、打ち切り用パラメータ同様に閾値や矩形の係数が格納されているが、更に分岐先ノードＡへのポインタも格納されている。このポインタの指し示す先には、また別のノードのパラメータが格納されている。最後にもう１つの分岐先ノードＢへのポインタが格納されている。
【００１９】
上記パラメータの作成方法を説明する前に、このパラメータを使用して顔を検出する方法を説明する。検出処理の全体的な流れは、ＣＰＵ１００が、図４の各ノードを根ノード（図で最も上位に描かれているノード）から順にたどることによって行われる。処理するノードがタイプＴ１のノードである場合、ＣＰＵ１００は、図５に図示されたノードに固有のパラメータを用いて、入力画像Ｉに顔が含まれているかどうかを判定する。顔がない可能性が高いと判定した場合には、ＣＰＵ１００は、そこで処理を中断する。そうでない場合には、ＣＰＵ１００は、次のノードの処理へと移る。処理するノードがタイプＴ２のノードである場合には、ＣＰＵ１００は、図６に図示されたノードに固有のパラメータを用いて、次にどのノードに処理を移すかの判断を行う。このように順にノードをたどっていくことによって、ＣＰＵ１００は、タイプＴ１のノードでは打ち切りか継続かの判断を行い、タイプＴ２のノードでは分岐先ノードの選択を行う。ここで、タイプＴ１のノード、つまり識別ノードは、入力データを特徴空間のＳ（第１のクラス）と〜Ｓ（第２のクラス）との２クラスに識別する識別器において、パラメータに基づいて、入力データが〜Ｓに属するかどうかを識別するノードである。また、タイプＴ２のノード、つまり分岐ノードは、パラメータに基づいて、次に起動するべきノードを決定するノードである。
【００２０】
図７は、図２のステップＳ２０３の詳細を表すフローチャートである。初めのステップＤ１０において、ＣＰＵ１００は、ポインタ変数ｐを最初のノードを指すように初期化する。次のステップＤ０２において、ＣＰＵ１００は、ｐが指し示すノードの種類を確認する。ｐが指し示すノードがタイプＴ１の場合、ＣＰＵ１００は、ステップＤ１１に進む。逆にタイプＴ２の場合、ＣＰＵ１００は、ステップＤ２１へ進む。
ステップＤ１１において、ＣＰＵ１００は、変数ｃを０で初期化する。そして、ＣＰＵ１００は、ステップＤ１２からＤ１５までのループを矩形の数ｎ回だけ繰り返す。ループ内において、ＣＰＵ１００は、矩形を表すループ変数をｉとする。ステップＤ１３において、ＣＰＵ１００は、図５のノード情報から矩形ｉの対角線の座標（ｘiL， ｙiT）−（ｘiR，ｙiB）を取得し、その入力画像Ｉにおける矩形内の輝度値の総和を求める。ＣＰＵ１００は、これをｂiとする。ｂiは、非特許文献２に書かれているように累積情報（ｉｎｔｅｇｒａｌ ｉｍａｇｅ）を使って高速に求めることができる。そしてステップＤ１４において、ＣＰＵ１００は、変数ｃにｂiと矩形ｉの符号ａiの積を加算する。まとめると、このループでＣＰＵ１００が求めているのは、次の和である。
【００２１】
【数１】
【００２２】
ステップＤ１６において、ＣＰＵ１００は、この和ｃが図５の閾値θを超えているかどうか判定する。そして、ＣＰＵ１００は、θを超えていればステップＤ１７へ進み、検出結果２０７に「偽」の値を書き込む。これは顔が検出されなかったことを表す。ここで、図４で示されたツリーの処理は打ち切られる。ステップＤ１６において、ＣＰＵ１００は、和ｃが閾値θを超えていないと判断すると、次のステップＤ１８へ進む。ここではＣＰＵ１００は、全ノードの処理を終えたかどうか確認する。全ノードの処理が完了している場合、ＣＰＵ１００は、ステップＤ１９で検出結果２０７に「真」の値を書き込む。これにより顔が検出されたことになる。逆に、ステップＤ１８で全ノードの処理が完了していない場合、ＣＰＵ１００は、ステップＤ０５でポインタ変数ｐに次のノードへのポインタを格納する。そして、ＣＰＵ１００は、ステップＤ０２へと制御を戻す。
ステップＤ０２においてポインタ変数ｐが指すノードのタイプがＴ２であることになれば、ＣＰＵ１００は、ステップＤ２１からの処理を実行する。まずステップＤ２１において、ＣＰＵ１００は、変数ｃを０で初期化する。そしてステップＤ２２からＤ２５までのループでＣＰＵ１００は、次の内積値を求める。なお、ａAiは図６の矩形の係数である。
【００２３】
【数２】
【００２４】
ステップＤ２６において、ＣＰＵ１００は、内積値ｃが図６の閾値θAを超えているかどうか確認する。超えている場合、ＣＰＵ１００は、次のステップＤ２８へと進む。ステップＤ２８において、ＣＰＵ１００は、ポインタ変数ｐに図６の分岐先ノードＡへのポインタ値を代入する。そして、ＣＰＵ１００は、再びステップＤ０２からの処理を始める。ステップＤ２６で閾値を超えていなかった場合、ＣＰＵ１００は、ステップＤ３０へ進む。ここで、ＣＰＵ１００は、ポインタ変数ｐに図６の分岐先ノードＢへのポインタ値を代入する。そして、ＣＰＵ１００は、再びステップＤ０２からの処理を始める。この様子をイメージ図にしたのが図８である。図８は、入力画像が分岐される様子を描いたイメージを表す図である。図８には、丸や三角で描かれているのが、これらは、入力画像Ｉの特徴ベクトルｂｉである。入力画像Ｉが顔である場合は丸（Ｅ００やＥ０１）、顔でない場合には三角（Ｅ１０やＥ１１）として描かれている。Ｅ０２は、ｃ＝θAとなる超平面である。Ｅ０３がベクトルａA＝（ａA1，ａA2，・・・，ａAn）で、超平面Ｅ０２の法線ベクトルである。上記の分岐条件により、黒丸Ｅ０１として表示されている顔画像と黒塗りの三角Ｅ１１として表示されている非顔画像とが分岐先Ａへと振り分けられることになる。また、白丸Ｅ００として表示されている顔画像と白抜きの三角Ｅ１０として表示されている非顔画像とが分岐先Ｂへ振り分けられることになる。以上の処理で、図４のツリーのノードを遷移していくことになる。図４に示されているとおり、タイプＴ２のノードを連続させることもできる。そうすることによって、より複雑な分岐が可能となる。或いは、複数の閾値を用意することによって、３つ以上の分岐先の中から１つを選ぶこともできる。
【００２５】
図５に示されるタイプＴ１のノードのパラメータを求めるための学習手順は、非特許文献２に示されるとおりである。ここで、図５の各矩形となる候補は学習前に予め提示されていると考えると分かりやすい。これら矩形の集合をＲ ＝ ｛ｒi｜ｉ ＝ １・・・Ｎr｝とする。当然のことながら、集合Ｒは規則的に生成されても、乱数によって生成されてもよい。
図６に示されるタイプＴ２のノードのパラメータを求めるための本実施形態における学習手順を示す。まず、前提として学習用の顔画像ｆjの集合Ｆ ＝ ｛ｆj ｜ ｊ ＝ １・・・Ｎf｝があり、顔の写っていない学習画像ｇjの集合Ｇ ＝ ｛ｇj ｜ ｇj ＝ １・・・Ｎg｝が用意されているものとする。更に、図４のツリー構造は予め決められており、パラメータを確保するためのメモリがＲＡＭ１０２上に確保されているものとする。例えば、あくまでも例であるが、図４のように分岐数が３本になるまで２回に１回分岐が起こるように分岐ノードを配置することができる。このとき、図５や図６の各ポインタ値も確定しており、格納しておくことができる。そこで、図４においてＴ１と記されているノードからＮ３と記されているノードの直前（つまり、ここではＴ２と書かれているノード）までの学習が済んでいるものとする。前述した検出の処理を適用すると、Ｎ３までのノードで学習画像のいくつかは顔がないものとして棄却（打ち切り）されたり、タイプＴ２のノードによって他の分岐先に振り分けられたりする。そこで、ＣＰＵ１００は、Ｎ３のノードでは、それまでに棄却されたり他の分岐先に振り分けられたりしない顔画像ｆj+の集合Ｆ+ ＝ ｛ｆj+ ｜ ｊ ＝ １・・・Ｎf+｝と非顔画像ｇj+の集合Ｇ+ ＝ ｛ｇj+ ｜ ｊ ＝ １・・・Ｎg+｝とを学習に利用する。
【００２６】
ノードＮ３のための学習の大まかな流れを図９に示す。まず、ステップＦ０１において、ＣＰＵ１００は、学習画像Ｆ+を特徴ベクトルの集合として表す。次にステップＦ０３において、ＣＰＵ１００は、特徴ベクトルの集合を用いて、学習データの特徴空間を分割する特徴空間内の超平面を決定し（分割面決定）、ノードＮ３のパラメータとして書き込む（パラメータ決定）。
次に、これら各ステップの詳細を説明する。
図１０は、図９のステップＦ０１の詳細を表すフローチャートである。ステップＦ０１０１からＦ０１０７までのループは、学習画像Ｆ+に属する各顔画像ｆj+に関する処理である。ステップＦ０１０３からステップＦ０１０５までのループは、矩形候補集合Ｒに属する各矩形ｒiに対して繰り返す。そしてステップＦ０１０４でＣＰＵ１００は、２次元配列の要素ｂjifに、顔画像ｆj+上の矩形ｒi内にあるピクセルの輝度値の総和を代入する。以上の処理により、学習画像の集合Ｆ+の各画像に対してＮr次元の特徴ベクトルが対応付けられたことになる。特徴空間の各次元は、それぞれある矩形の中の輝度値総和に対応する。学習画像の集合Ｆ+に対応する特徴ベクトルの集合をＢF+ ＝ ｛ ｂjf ｜ ｂjf ＝ （ｂj1f， ｂj2f，・・・， ｂjNrf）｝とする。
【００２７】
図９のステップＦ０３でＣＰＵ１００は、ステップＦ０１で求められたベクトルに対して垂直であって、学習データの特徴空間を分割する分割超平面を決定する（分割面決定）。分割超平面は、分割面の一例である。ステップＦ０３の流れを図１１のフローチャートに示す。図１１は、図９のステップＦ０３の詳細を表すフローチャート（その１）である。
まず、ステップＦ０３０１において、ＣＰＵ１００は、顔特徴ベクトルの集合ＢF+の第１主成分方向ベクトルを求める。ここでいう第１主成分方向とは、集合ＢF+の散らばりが最大となる方向である。ＣＰＵ１００は、ｓｉｎｇｕｌａｒ−ｖａｌｕｅ ｄｅｃｏｍｐｏｓｉｔｉｏｎ （ＳＶＤ）やｐｒｉｎｃｉｐａｌ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ （ＰＣＡ；主成分分析）等の多変量解析の手法を用いて主成分方向ベクトルを求めることができる。或いはＣＰＵ１００は、ｉｎｄｅｐｅｎｄｅｎｔ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ（ＩＣＡ；独立成分分析）等の多変量解析の手法を用いて主成分方向ベクトルを求めることもできる。ここで得られた主成分方向ベクトルをｄ ＝ （ｄ1， ｄ2，・・・， ｄNr）とする。次にステップＦ０３０２において、ＣＰＵ１００は、この主成分方向ベクトルｄの次元を削減する。より具体的に説明すると、ＣＰＵ１００は、ｎを予め決められた値として、ｄの成分の中で絶対値が大きい上位ｎ個の成分を取り出し、ａA ＝ （ａA1， ａA2，・・・， ａAn）とする。ｎは値を大きく取るとその分計算に時間を要することになるので、大きくしすぎないことが必要である。ｄの各次元はそれぞれＲ内の矩形１つに対応する。このことに着目して、ＣＰＵ１００は、ａAの各要素に対応する矩形を並べることができる。これをｒA ＝ （ｒA1， ｒA2，・・・， ｒAn）とする。ａAの各成分はＣＰＵ１００によって図６の分岐先Ａ用パラメータの該当する領域に書き込まれ、ｎとｒAとの各矩形の座標がＣＰＵ１００によって図６の矩形情報として書き込まれる。なお、次元削減の方法は、上記方法に限らない。例えば、ＣＰＵ１００は、ベクトルｄの中の絶対値と対応する矩形面積との積が大きい上位ｎ個の成分を取り出すこともできる。また、ＣＰＵ１００は、次元削減を行わないことも可能である。
主成分方向ベクトルは、方向ベクトルの一例である。
【００２８】
残る閾値θAは、図１１のステップＦ０３０３で求められる。閾値θAを求める方法の一例を式で表すと、前述のＢF+の重心ｃを用いて、次のように表される。
【００２９】
【数３】
【００３０】
ここで、ｂjAfは、ｂjfからｒA＝ （ｒA1， ｒA2，・・・， ｒAn）に対応する成分を取り出したベクトルである。ｗj＝１でもよいが、非特許文献２に書かれているようなＡｄａｂｏｏｓｔの重みでもよい。
【００３１】
以上の方法によりタイプＴ１とタイプＴ２とのノードのパラメータを学習することにより、図４に示したツリー構造のパラメータを用意することができる。そして、このパラメータを使用することにより、比較的計算負荷の軽い処理により入力画像中の顔を検出することができる。本実施形態では、主成分方向を求めるためにＰＣＡ等を利用したが、当然のことながらｋｅｒｎｅｌ ＰＣＡ等の非線形な手法を用いることもできる。また、これまでの説明から、識別器は、顔の識別に限るものでなく、人物や図形や文字等他の画像も扱えることは明らかである。
【００３２】
＜実施形態２＞
実施形態１では、主成分分析等を行ってから次元削減を行ったが、実施形態２では次元削減を行ってから、ｉｎｄｅｐｅｎｄｅｎｔ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ（ＩＣＡ；独立成分分析）等を行う例を示す。
本実施形態では、図１１の代わりに図１２を利用する。図１２は、図９のステップＦ０３の詳細を表すフローチャート（その２）である。
ステップＦ０３１１において、ＣＰＵ１００は、分割超平面の法線ベクトルを求める。そして、ステップＦ０３１３において、ＣＰＵ１００は、図１１のステップＦ０３０３と同じ手順（同じ処理）で閾値θAを求める。
【００３３】
図１３は、図１２のステップＦ０３１１の詳細を表すフローチャート（その１）である。
ステップＧ０１において、ＣＰＵ１００は、矩形の集合Ｒのなかからいくつかの矩形の組み合わせを選び、その組み合わせの集合をＲＣとする。それぞれの組み合わせでの矩形の数ｍは、例えば２のように一定であってもよいが、不揃いであってもよい。不揃いの場合には、ＣＰＵ１００は、根ノードから数えたノード数に応じて、ｍが単調に増加するように選んでもよい。ＣＰＵ１００は、矩形の組み合わせ集合ＲＣの各組み合わせｒC＝（ｒC1，ｒC2，・・・，ｒCm）（Ｃ1〜Ｃmは矩形の番号を表すインデックス）について、ステップＧ０２からＧ０６までのループを繰り返す。
【００３４】
次にステップＧ０３において、ＣＰＵ１００は、集合ＢF+の各特徴ベクトルｂjfについて、ｒC＝（ｒC1，ｒC2，・・・，ｒCm）の各要素（矩形）に対応する成分を取り出した特徴ベクトル
【数４】
を生成する。もし、ｒC＝（ｒ5，ｒ236，ｒ5468
）の場合、
【数５】
は、（ｂj,5f，ｂj,236f，ｂj,5468f）となる。つまり、学習画像ｆ
j+上の矩形ｒ5とｒ236とｒ5468内の輝度値総和を並べたベクトルとなる。
【００３５】
ステップＧ０４において、ＣＰＵ１００は、これらｍ次元のベクトルの集合
【数６】
に対してＩＣＡを適用し、最大でｍ本のｍ次元ベクトルｑk（ｋ＝１，・・・，ｍq；ｍq≦ｍ）を得る。ＩＣＡを適用する際の目的関数には例えば次のような関数Ｊ（ｑ）を選ぶことができる。ここで、ｖは平均０、分散１の正規分布に従う確率変数である。
【００３６】
【数７】
【００３７】
次にステップＧ０５において、ＣＰＵ１００は、評価値として集合
【数８】
の尖度（ｋｕｒｔｏｓｉｓ）の符号を反転したものを計算する。より具体的に説明すると、ＣＰＵ１００は、次の値を求める（射影評価）。
【００３８】
【数９】
【００３９】
或いはＣＰＵ１００は、評価値としてｃｏｎｔｒａｓｔ ｆｕｎｃｔｉｏｎや目的関数を使用してもよい。ループを抜けると、ＣＰＵ１００は、ステップＧ０７で評価値が最も大きかったベクトルｑkとそのときの矩形組み合わせｒとを、それぞれａAとｒAとして選択する（最適化）。なお、ベクトルｑkは、射影ベクトルと学習データの特徴ベクトルとの内積値の集合に関する統計量の一例である。つまり、ＣＰＵ１００は、ベクトルｑkを最大化又は最小化する射影ベクトルｑを求め、方向ベクトルとする。
【００４０】
以上の方法でタイプＴ１とタイプＴ２とのノードのパラメータを学習することにより、図４に示したツリー構造のパラメータを用意することができる。そして、このパラメータを使用することにより、比較的計算負荷の軽い処理により入力画像中の顔を検出することができる。特に本実施形態では、全ての組み合わせｒCに共通する評価関数によって評価値を求めて比較することによって、分割超平面の法線ベクトルを求めるだけでなく、次元削減において使用する成分の選択も行っている。なお、本実施形態では、超平面の法線ベクトルを求めるためにＩＣＡを使用したが、ＰＣＡやＳＶＤ等他の手法を使用することもできる。
【００４１】
＜実施形態３＞
実施形態２では、尖度が正規分布からより乖離した射影ベクトルｑを、ＩＣＡを使って求める方法を示した。この方法は、尖度が小さい射影ベクトルだけでなく、尖度が大きい射影ベクトルも求めてしまうことになる。本実施形態では、射影追跡法を利用して、直接尖度が小さい射影ベクトルのみを求める方法を示す。本実施形態でも、尖度は正規分布からの乖離度を表す指標の例として用いる。実施形態２とほぼ同じ構成であるが、図１３の代わりに本実施形態では図１５を使用する。
【００４２】
まず射影ベクトルｑ'を極座標系で表現する。
【数１０】
【００４３】
また、
【数１１】
を次式に従って平行移動させる。
【数１２】
【００４４】
そして、目的関数は以下の通りとする。
【数１３】
【００４５】
この目的関数を最小化する射影ベクトルｑ'を求める方法のフローチャートを図１４に示す。図１４は、目的関数を最小化する射影ベクトルｑ'を求める処理の一例を示すフローチャートである。
ステップＫ０１において、ＣＰＵ１００は、θi（ｉ＝１，・・・，ｍ）を所定の値で初期化する。例えば、ＣＰＵ１００は、θi＝０（ｉ＝１，・・・，ｍ）とすることができる。或いは、ＣＰＵ１００は、前記値を乱数で生成することもできる。また、ＣＰＵ１００は、収束条件のためのカウンタ変数ｓを０に初期化する。
【００４６】
ＣＰＵ１００は、ステップＫ０２から繰り返し処理に入る。まずステップＫ０２において、ＣＰＵ１００は、θ+を生成する。より具体的に説明すると、ＣＰＵ１００は、まず乱数により自然数ｕ（１≦ｕ≦ｍ−１）とΔを生成する。Δは、例えば平均０の正規分布をなすものとする。そしてθ+はθの第ｕ成分にΔを足したものとする。つまり、次式の通りとする。θi（ｉ＝１，．．．，ｍ）はθの第ｉ成分である。
θi+＝θi（ｉ≠ｕ）
θu+＝θu＋Δ
【００４７】
次に、ステップＫ０３において、ＣＰＵ１００は、目的関数の増減を調べる。より具体的に説明すると、ＣＰＵ１００は、（式１）にθを代入して射影ベクトルｑ'を求め、Ｊ（ｑ'）を計算する。次にＣＰＵ１００は、θの代わりにθ+を使って射影ベクトルｑ+'を求め、Ｊ（ｑ+'）を計算する。ＣＰＵ１００は、Ｊ（ｑ'）≦Ｊ（ｑ+'）であれば、ステップＫ０６へ進み、逆であればステップＫ０４へ進む。
ステップＫ０４において、ＣＰＵ１００は、カウンタ変数ｓを０に初期化する。そして、ステップＫ０５において、ＣＰＵ１００は、θにθ+を代入して、再びステップＫ０２よりループを繰り返す。ステップＫ０６において、ＣＰＵ１００は、カウンタ変数ｓを１つ増分させる。そして、ステップＫ０７において、ＣＰＵ１００は、予め定められた定数Ｓとｓとを比較し、まだｓ＜Ｓであれば、ステップＫ０２よりループを繰り返す。逆にｓ≦ＳであればＣＰＵ１００は、最小化処理を中止する。これにより、目的関数の値がＳ回改善されなければループを抜けることになる。このときのθから求めた射影ベクトルｑ'を、目的関数を最小化する値として扱う。
【００４８】
ステップＫ０３において、ＣＰＵ１００は、逐次Ｊ（ｑ'）を評価しているので、実施形態２の図１３のステップＧ０５ように評価値（Ｊ（ｑ'）の値）を再度計算する必要がない。そのため、図１３の代わりに本実施形態では図１５に従う。ステップＬ０４の詳細は図１４に示したとおりである。
【００４９】
以上、尖度を最小化する射影ベクトルを求める方法を示した。本実施形態ではこの射影ベクトルを用いてタイプＴ２ノードの分割超平面を決定する。
なお、上述した最適化手法以外にも、ニュートン法等他の最適化手法によって射影ベクトルを求めるようにしてもよい。
また、これまでの実施形態では矩形特徴を用いた例を示したが、本発明はこれに限定されるものではない。特徴量としては、入力画像のピクセル値、入力画像にガボール フィルタをかけた特徴量、また局所特徴と呼ばれ入力画像の個々のピクセルにベクトルを割り当てるもの等がある。このようにパターン認識の分野においては、数多くの特徴量が定義されている。また、これまで顔の識別を例に取り上げたが、本発明は、画像のみならず、音声情報やアンケート結果等、他の情報にも適用することができる。
【００５０】
以上、上述した各実施形態によれば、パターン識別のための決定木を構築する際に、分岐ノードのパラメータを適切に決定することができるため、入力データを、高速、かつ、高精度にパターン識別する識別器を構成することができる。
【００５１】
以上、本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００５２】
１００ ＣＰＵ、１０１ プログラムメモリ、１０２ ＲＡＭ、１０３ ハードディスク、１０４ ディスプレイ
【特許請求の範囲】
【請求項１】
識別ノードと分岐ノードとを複数、連結した木構造を有し、入力データを特徴空間の第１のクラスと第２のクラスとの２クラスに識別する識別器の、各ノードのパラメータを決定する学習装置であって、
前記分岐ノードは、パラメータに基づいて、次に起動するべきノードを決定するノードであり、
前記識別ノードは、パラメータに基づいて、入力データが前記第２のクラスに属するかどうかを識別するノードであり、
前記第１のクラスに属する学習データの特徴ベクトルに対して多変量解析を行い、方向ベクトルを求める多変量解析手段と、
前記多変量解析手段で求められた前記方向ベクトルに対して垂直であって、学習データの特徴空間を分割する分割面を決定する分割面決定手段と、
前記分割面決定手段で決定された前記分割面に基づいて、前記分岐ノードのパラメータを決定するパラメータ決定手段と、
を有することを特徴とする学習装置。
【請求項２】
前記分割面決定手段は、前記多変量解析手段で求められた前記方向ベクトルに対して垂直であって、学習データの特徴空間を分割する前記特徴空間内の超平面を分割面として決定することを特徴とする請求項１に記載の学習装置。
【請求項３】
前記多変量解析手段は、
ある射影ベクトルと前記第１のクラスに属する学習データの特徴ベクトルとの内積値を求める射影手段と、
前記内積値の集合に関する統計量を求める射影評価手段と、
前記統計量を最大化又は最小化する前記射影ベクトルを求め、前記方向ベクトルとする最適化手段と、
を有することを特徴とする請求項１に記載の学習装置。
【請求項４】
前記射影評価手段は、前記内積値の集合の正規分布からの乖離度を表す統計量を求め、
前記最適化手段は、前記統計量を最大化する前記射影ベクトルを求め、前記方向ベクトルとすることを特徴とする請求項３に記載の学習装置。
【請求項５】
前記射影評価手段は、前記内積値の集合の尖度を統計量として求めることを特徴とする請求項３に記載の学習装置。
【請求項６】
前記多変量解析手段で求められた前記方向ベクトルから絶対値の大きさに基づいて要素を削減する次元削減手段を更に有し、
前記分割面決定手段は、前記次元削減手段で次元削減されたベクトルに垂直である、前記分割面を決定することを特徴とする請求項１乃至５の何れか１項に記載の学習装置。
【請求項７】
識別ノードと分岐ノードとを複数、連結した木構造を有し、入力データを特徴空間の第１のクラスと第２のクラスとの２クラスに識別する識別器の、各ノードのパラメータを決定する学習装置における学習方法であって、
前記分岐ノードは、パラメータに基づいて、次に起動するべきノードを決定するノードであり、
前記識別ノードは、パラメータに基づいて、入力データが前記第２のクラスに属するかどうかを識別するノードであり、
前記学習装置が、
前記第１のクラスに属する学習データの特徴ベクトルに対して多変量解析を行い、方向ベクトルを求める多変量解析ステップと、
前記多変量解析ステップで求められた前記方向ベクトルに対して垂直であって、学習データの特徴空間を分割する分割面を決定する分割面決定ステップと、
前記分割面決定ステップで決定された前記分割面に基づいて、前記分岐ノードのパラメータを決定するパラメータ決定ステップと、
を含むことを特徴とする学習方法。
【請求項８】
前記分割面決定ステップでは、前記多変量解析ステップで求められた前記方向ベクトルに対して垂直であって、学習データの特徴空間を分割する前記特徴空間内の超平面を分割面として決定することを特徴とする請求項７に記載の学習方法。
【請求項９】
前記多変量解析ステップでは、
ある射影ベクトルと前記第１のクラスに属する学習データの特徴ベクトルとの内積値を求める射影ステップと、
前記内積値の集合に関する統計量を求める射影評価ステップと、
前記統計量を最大化又は最小化する前記射影ベクトルを求め、前記方向ベクトルとする最適化ステップと、
を含むことを特徴とする請求項７に記載の学習方法。
【請求項１０】
前記射影評価ステップでは、前記内積値の集合の正規分布からの乖離度を表す統計量を求め、
前記最適化ステップでは、前記統計量を最大化する前記射影ベクトルを求め、前記方向ベクトルとすることを特徴とする請求項９に記載の学習方法。
【請求項１１】
前記射影評価ステップでは、前記内積値の集合の尖度を統計量として求めることを特徴とする請求項９に記載の学習方法。
【請求項１２】
前記多変量解析ステップで求められた前記方向ベクトルから絶対値の大きさに基づいて要素を削減する次元削減ステップを更に有し、
前記分割面決定ステップでは、前記次元削減ステップで次元削減されたベクトルに垂直である、前記分割面を決定することを特徴とする請求項７乃至１１の何れか１項に記載の学習方法。
【請求項１】
識別ノードと分岐ノードとを複数、連結した木構造を有し、入力データを特徴空間の第１のクラスと第２のクラスとの２クラスに識別する識別器の、各ノードのパラメータを決定する学習装置であって、
前記分岐ノードは、パラメータに基づいて、次に起動するべきノードを決定するノードであり、
前記識別ノードは、パラメータに基づいて、入力データが前記第２のクラスに属するかどうかを識別するノードであり、
前記第１のクラスに属する学習データの特徴ベクトルに対して多変量解析を行い、方向ベクトルを求める多変量解析手段と、
前記多変量解析手段で求められた前記方向ベクトルに対して垂直であって、学習データの特徴空間を分割する分割面を決定する分割面決定手段と、
前記分割面決定手段で決定された前記分割面に基づいて、前記分岐ノードのパラメータを決定するパラメータ決定手段と、
を有することを特徴とする学習装置。
【請求項２】
前記分割面決定手段は、前記多変量解析手段で求められた前記方向ベクトルに対して垂直であって、学習データの特徴空間を分割する前記特徴空間内の超平面を分割面として決定することを特徴とする請求項１に記載の学習装置。
【請求項３】
前記多変量解析手段は、
ある射影ベクトルと前記第１のクラスに属する学習データの特徴ベクトルとの内積値を求める射影手段と、
前記内積値の集合に関する統計量を求める射影評価手段と、
前記統計量を最大化又は最小化する前記射影ベクトルを求め、前記方向ベクトルとする最適化手段と、
を有することを特徴とする請求項１に記載の学習装置。
【請求項４】
前記射影評価手段は、前記内積値の集合の正規分布からの乖離度を表す統計量を求め、
前記最適化手段は、前記統計量を最大化する前記射影ベクトルを求め、前記方向ベクトルとすることを特徴とする請求項３に記載の学習装置。
【請求項５】
前記射影評価手段は、前記内積値の集合の尖度を統計量として求めることを特徴とする請求項３に記載の学習装置。
【請求項６】
前記多変量解析手段で求められた前記方向ベクトルから絶対値の大きさに基づいて要素を削減する次元削減手段を更に有し、
前記分割面決定手段は、前記次元削減手段で次元削減されたベクトルに垂直である、前記分割面を決定することを特徴とする請求項１乃至５の何れか１項に記載の学習装置。
【請求項７】
識別ノードと分岐ノードとを複数、連結した木構造を有し、入力データを特徴空間の第１のクラスと第２のクラスとの２クラスに識別する識別器の、各ノードのパラメータを決定する学習装置における学習方法であって、
前記分岐ノードは、パラメータに基づいて、次に起動するべきノードを決定するノードであり、
前記識別ノードは、パラメータに基づいて、入力データが前記第２のクラスに属するかどうかを識別するノードであり、
前記学習装置が、
前記第１のクラスに属する学習データの特徴ベクトルに対して多変量解析を行い、方向ベクトルを求める多変量解析ステップと、
前記多変量解析ステップで求められた前記方向ベクトルに対して垂直であって、学習データの特徴空間を分割する分割面を決定する分割面決定ステップと、
前記分割面決定ステップで決定された前記分割面に基づいて、前記分岐ノードのパラメータを決定するパラメータ決定ステップと、
を含むことを特徴とする学習方法。
【請求項８】
前記分割面決定ステップでは、前記多変量解析ステップで求められた前記方向ベクトルに対して垂直であって、学習データの特徴空間を分割する前記特徴空間内の超平面を分割面として決定することを特徴とする請求項７に記載の学習方法。
【請求項９】
前記多変量解析ステップでは、
ある射影ベクトルと前記第１のクラスに属する学習データの特徴ベクトルとの内積値を求める射影ステップと、
前記内積値の集合に関する統計量を求める射影評価ステップと、
前記統計量を最大化又は最小化する前記射影ベクトルを求め、前記方向ベクトルとする最適化ステップと、
を含むことを特徴とする請求項７に記載の学習方法。
【請求項１０】
前記射影評価ステップでは、前記内積値の集合の正規分布からの乖離度を表す統計量を求め、
前記最適化ステップでは、前記統計量を最大化する前記射影ベクトルを求め、前記方向ベクトルとすることを特徴とする請求項９に記載の学習方法。
【請求項１１】
前記射影評価ステップでは、前記内積値の集合の尖度を統計量として求めることを特徴とする請求項９に記載の学習方法。
【請求項１２】
前記多変量解析ステップで求められた前記方向ベクトルから絶対値の大きさに基づいて要素を削減する次元削減ステップを更に有し、
前記分割面決定ステップでは、前記次元削減ステップで次元削減されたベクトルに垂直である、前記分割面を決定することを特徴とする請求項７乃至１１の何れか１項に記載の学習方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１０−２８２３６７（Ｐ２０１０−２８２３６７Ａ）
【公開日】平成２２年１２月１６日（２０１０．１２．１６）
【国際特許分類】
【出願番号】特願２００９−１３４３０５（Ｐ２００９−１３４３０５）
【出願日】平成２１年６月３日（２００９．６．３）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２２年１２月１６日（２０１０．１２．１６）
【国際特許分類】
【出願日】平成２１年６月３日（２００９．６．３）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]