(57)【特許請求の範囲】
【請求項１】
学習パターンの集合に含まれる学習パターンを下位のノードに分配していくことにより入力パターンを認識するための木構造の辞書を作成する情報処理装置であって、
学習の過程で作成される木構造の各階層において、該階層の各ノードに対応付けられている学習パターンの数に基づいてノードを選択する選択手段と、
前記選択されたノードに分配された学習パターンに対して実行するクエリを作成するクエリ作成手段と、
前記選択されたノードに分配された学習パターンに対して、前記作成されたクエリを実行し、該クエリの実行結果に基づいて個々の学習パターンを複数の下位のノードへ分配する分配手段とを備え、
前記クエリ作成手段は、前記分配手段により前記複数の下位のノードに分配される学習パターンの数が前記下位のノード間で略均等となるようなクエリを作成することを特徴とする情報処理装置。
【請求項２】
前記クエリ作成手段は、前記木構造の辞書における同一の階層に存在するノードに対して、同一のクエリを作成することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記木構造の辞書における各々のルートノードに設定する学習パターンの集合は、全ての学習パターンからランダムに選択された学習パターンの集合であることを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
前記選択手段は、当該階層に存在するノードのうち、対応付けられている学習パターンの数が最も多いノードを選択することを特徴とする請求項１乃至３のいずれか１項に記載の情報処理装置。
【請求項５】
前記選択手段は、対応付けられている学習パターンの数が、所定の値より大きいノードを選択することを特徴とする請求項１乃至３のいずれか１項に記載の情報処理装置。
【請求項６】
前記選択手段は、各階層に存在するノードを当該ノードに対応付けられている学習パターンの数の大きい順でソートして、上位Ｎ位のノードを選択することを特徴とする請求項１乃至３のいずれか１項に記載の情報処理装置。
【請求項７】
学習パターンの集合に含まれる学習パターンを下位のノードに分配していくことにより入力パターンを認識するための木構造の辞書を作成する情報処理装置であって、
学習の過程で作成される木構造の各階層に存在するノードを、少なくとも１つ以上のノードからなる組に分割する分割手段と、
前記分割されたそれぞれの組において、各ノードが保持する学習パターンの数に基づいてノードを選択する選択手段と、
前記選択されたノードに分配された学習パターンに対して、実行するクエリを該ノードに対応して作成するクエリ作成手段と、
前記選択されたノードに分配された学習パターンに対して、該ノードに対応して作成されたクエリを実行し、該クエリの実行結果に基づいて個々の学習パターンを複数の下位のノードへ分配する分配手段とを備え、
前記クエリ作成手段は、前記分配手段により前記下位のノードに分配される学習パターンの数が前記下位のノード間で略均等となるようなクエリを作成することを特徴とする情報処理装置。
【請求項８】
前記クエリ作成手段は、前記選択されたノードに対応付けられている学習パターンの次元の分散を求め、該求められた分散に基づいて、クエリを作成することを特徴とする請求項１乃至７のいずれか１項に記載の情報処理装置。
【請求項９】
パターン認識の対象となる入力パターンをルートノードに設定し、前記木構造の辞書を辿りながら各ノードに対応して作成されたクエリを実行することにより前記パターンの認識を行なう認識手段を更に備えることを特徴とする請求項１または７に記載の情報処理装置。
【請求項１０】
前記学習パターンは画像であり、前記クエリは、複数の画素位置における画素値を比較する処理であることを特徴とする請求項１乃至９の何れか１項に記載の情報処理装置。
【請求項１１】
階層構造を有する木構造の辞書の所定の階層における所定のノードに設定された対象物体を含む学習画像を、該学習画像から取得される特徴量に基づいて前記ノードより下位の階層の複数の下位ノードのいずれかに分類して対象物体を認識するための辞書を生成する場合に、前記特徴量を取得する画素の位置を決定するための情報処理装置であって、
所定の階層に存在する複数のノードそれぞれに対応付けられている学習画像の数に基づいて、前記複数のノードから一つのノードを選択する選択手段と、
前記選択されたノードに対応付けられている複数の学習画像を、前記所定の階層よりも下位の階層の複数のノードに割り当てるための特徴量が取得される画素の位置を決定する決定手段と、
前記決定手段で決定された位置に基づいて前記複数のノードそれぞれに対応付けられている複数の学習画像を前記所定の階層よりも下位の階層の複数のノードに割り当てる割り当て手段とを備え、
前記決定手段は、前記割り当て手段によって前記複数の学習画像が前記下位の階層の複数のノードのいずれかに割り当てられるときに、前記学習パターンの数が前記下位のノード間で略均等となるように、前記特徴量が取得される画素の位置を決定することを特徴とする情報処理装置。
【請求項１２】
前記選択手段は、前記所定の階層に存在する複数のノードのうち、対応付けられている学習画像の数が最も多いノードを選択することを特徴とする請求項１１に記載の情報処理装置。
【請求項１３】
前記特徴量は画素値であることを特徴とする請求項１１または１２に記載の情報処理装置。
【請求項１４】
前記割り当て手段は、前記決定手段で決定された複数の画素の位置から取得される画素値同士を比較した結果に基づいて前記複数の学習画像を前記所定の階層よりも下位の階層の複数のノードに割り当てることを特徴とする請求項１３に記載の情報処理装置。
【請求項１５】
パターン認識の対象となる対象物体が含まれる学習パターンの集合をルートノードに設定し、該設定した学習パターンの集合に含まれる学習パターンを下位のノードに分配していくことにより入力パターンを認識するための木構造の辞書を作成する情報処理方法であって、
学習の過程で作成される木構造の各階層において、該階層の各ノードに対応付けられている学習パターンの数に基づいてノードを選択する選択ステップと、
前記選択されたノードに分配された学習パターンに対して実行するクエリを作成するクエリ作成ステップと、
前記選択されたノードに分配された学習パターンに対して、前記作成されたクエリを実行し、該クエリの実行結果に基づいて個々の学習パターンを複数の下位のノードへ分配する分配ステップとを有し、
前記クエリ作成ステップは、前記分配ステップにより前記下位のノードに分配される学習パターンの数が前記下位のノード間で略均等となるようなクエリを作成することを特徴とする情報処理方法。
【請求項１６】
パターン認識の対象となる対象物体が含まれる学習パターンの集合をルートノードに設定し、該設定した学習パターンの集合に含まれる個々の学習パターンを各ノードに分配していくことにより入力パターンを認識するための木構造の辞書を作成する情報処理方法であって、
学習の過程で作成される木構造の各階層に存在するノードを、少なくとも１つ以上のノードからなる組に分割する分割ステップと、
前記分割されたそれぞれの組において、各ノードが保持する学習パターンの数に基づいてノードを選択する選択ステップと、
前記選択されたノードに分配された学習パターンに対して実行するクエリを作成するクエリ作成ステップと、
前記選択されたノードに分配された学習パターンに対して、前記作成されたクエリを実行し、該クエリの実行結果に基づいて個々の学習パターンを複数の下位のノードへ分配する分配ステップとを備え、
前記クエリ作成ステップは、前記分配ステップにより前記下位のノードに分配される学習パターンの数が前記下位のノード間で略均等となるようなクエリを作成することを特徴とする情報処理方法。
【請求項１７】
階層構造を有する木構造の辞書の所定の階層における所定のノードに設定された対象物体を含む学習画像を、該学習画像から取得される特徴量に基づいて前記ノードより下位の階層の複数の下位ノードのいずれかに分類して対象物体を認識するための辞書を生成する場合に、前記特徴量を取得する画素の位置を決定するための情報処理方法であって、
所定の階層に存在する複数のノードそれぞれに対応付けられている学習画像の数に基づいて、前記複数のノードから一つのノードを選択する選択工程と、
前記選択されたノードに対応付けられている複数の学習画像を前記所定の階層よりも下位の階層の複数のノードに割り当てるための特徴量が取得される画素の位置を決定する決定工程と、
前記決定工程で決定された位置に基づいて前記複数のノードそれぞれに対応付けられている複数の学習画像を前記所定の階層よりも下位の階層の複数のノードに割り当てる割り当て工程とを備え、
前記決定工程では、前記割り当て工程で前記複数の学習画像が前記下位の階層の複数のノードのいずれかに割り当てられるときに、前記学習パターンの数が前記下位のノード間で略均等となるように、前記特徴量が取得される画素の位置を決定することを特徴とする情報処理方法。
【請求項１８】
コンピュータを、請求項１乃至１４の何れか１項に記載の情報処理装置の各手段として実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、認識に用いるパターンを学習するための情報処理装置、その処理方法及びプログラムに関する。
【背景技術】
【０００２】
学習パターンを用いて新規パターンを認識する機械学習が知られている。その中でも、分類木、決定木と呼ばれるパターン認識手法が提案され（非特許文献１参照）、多くのシステムにおいて用いられてきた。この手法は木構造（ツリー構造とも呼ばれる）を用いて高速にパターンを解析できるという性質を持っており、計算機の能力の貧弱な時代には、その能力を発揮してきた。
【０００３】
なお、パターン認識問題をパターン識別問題として捉えたとき、識別するべきパターンの種類を“クラス”と呼び、以下説明で“クラス”という言葉はこの意味で用いる。また、通常、機械学習の結果、生成される木構造自体をパターン認識装置、すなわち判別器と同一視することが多い。
【０００４】
非特許文献１に記載されるような、古典的な分類木、決定木の欠点として認識性能があまり高くないということが挙げられる。この欠点を克服する技術として、例えば特許文献１に示されるような分類木の集合（アンサンブル）を用いた手法が提案されている。これは分類木をＬ個（Ｌは２以上の定数であり、通常は１０〜１００の範囲）作成し、それら全部を用いることによって、より高い認識性能を実現する技術である。
【０００５】
しかしながら、上記技術は、従来１つの分類木を用いた手法のＬ倍、計算時間を要するという欠点を持っており、従来の分類木に対して、高速性を犠牲にしている。そのため、木構造の各ノードにおけるクエリとして、学習パターンの特徴の部分集合をランダムに選択することにより、高速性を得ている。より具体的には、分類木の各ノードにおいて、ランダムに所定サイズ（３２ピクセル×３２ピクセル）の画像上の２点を選び、その輝度値を比較する。この処理は、非常に高速にでき、且つ認識精度も十分高いという報告が非特許文献２の中でされている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】米国特許第６００９１９９号明細書
【非特許文献】
【０００７】
【非特許文献１】Ｌｅｏ  Ｂｒｅｉｍａｎ，  Ｊｅｒｏｍｅ  Ｆｒｉｅｄｍａｎ，  Ｃｈａｒｌｅｓ  Ｊ．  Ｓｔｏｎｅ，  ａｎｄ  Ｒ．Ａ．  Ｏｌｓｈｅｎ，  “Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  ａｎｄ  Ｒｅｇｒｅｓｓｉｏｎ  Ｔｒｅｅｓ”，  Ｃｈａｐｍａｎ  ＆  Ｈａｌｌ／ＣＲＣ  （１９８４）
【非特許文献２】Ｖｉｎｃｅｎｔ  Ｌｅｐｅｔｉｔ  ａｎｄ  Ｐａｓｃａｌ  Ｆｕａ，  “Ｋｅｙｐｏｉｎｔ  Ｒｅｃｏｇｎｉｔｉｏｎ  Ｕｓｉｎｇ  Ｒａｎｄｏｍｉｚｅｄ  Ｔｒｅｅｓ”，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  （２００６）  ｐｐ．１４６５〜ｐｐ．１４７９
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、例えば、山積みされた部品の認識や人ごみの中での人物認識など、背景の変動が大きい場合、非特許文献２に記載された技術は、そのまま適用できない。なぜなら、未知の画像の中で背景となる部分の輝度値は、学習する画像と全く異なる値になるからである。具体的には、分類木の各ノードにおいて２点の輝度値を比較する際に、対象物体とは無関係な輝度値を用いてしまう可能性がある。この結果、（従来の）分類木を用いたパターン認識では信頼性の低い結果しか得られない。できるだけ対象物体の存在する部分の２点の輝度値を比較しようとしても、どうしても対象物体以外の部分を参照してしまうケースが発生してしまう。そこで、本発明は、上記課題に鑑みてなされたものであり、より認識精度の高いパターン認識用の辞書を作成できるようにした技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するために、例えば、本発明の情報処理装置は、学習パターンの集合に含まれる学習パターンを下位のノードに分配していくことにより入力パターンを認識するための木構造の辞書を作成する情報処理装置であって、学習の過程で作成される木構造の各階層において、該階層の各ノードに対応付けられている学習パターンの数に基づいてノードを選択する選択手段と、前記選択されたノードに分配された学習パターンに対して実行するクエリを作成するクエリ作成手段と、前記選択されたノードに分配された学習パターンに対して、前記作成されたクエリを実行し、該クエリの実行結果に基づいて個々の学習パターンを複数の下位のノードへ分配する分配手段とを備え、前記クエリ作成手段は、前記分配手段により前記複数の下位のノードに分配される学習パターンの数が前記下位のノード間で略均等となるようなクエリを作成することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、より認識精度の高いパターン認識用の辞書を作成できる。
【図面の簡単な説明】
【００１１】
【図１】第１の実施形態の学習過程を説明するフローチャートである。
【図２】本発明の実施形態を表す図である。
【図３】出来上がった分類木の例である。
【図４】第１の実施形態のパターン認識過程を説明するフローチャートである。
【図５】第２の実施形態の学習過程を説明するフローチャートである。
【図６】第２の実施形態のパターン認識過程を説明するフローチャートである。
【図７】第３の実施形態の学習過程を説明するフローチャートである。
【図８】第４の実施形態の学習過程を説明するフローチャートである。
【図９】第４の実施形態の学習過程のアルゴリズムを説明する図である。
【図１０】第４の実施形態を説明する図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態について図面に基づいて説明する。
【００１３】
以下の実施形態においては、予め学習されたパターンに基づき、新規パターンを解析するパターンに認識方法について説明する。ここで、具体的な例を挙げると、パターンとして対象物体を撮像した画像を用いて、対象物体の名称、種類、３次元上の存在位置、姿勢等の情報を推定する形態があげられる。
【００１４】
なお、対象物体とは、任意の物体を表し、例えば、人、動物、臓器、自動車、カメラ。プリンタ、半導体基板などであり、特にこれに限定されず、なんでも良い。また更に、一般的な適用例としては、対象とする物理現象を測定した計測値をパターンとして用いてもよい。
【００１５】
［第１の実施形態］
図２は、本発明の一実施形態に係わる情報処理装置の構成の一例を示す図である。本発明は、他形態の情報処理装置として、例えば組み込みデバイス、デジタルカメラ、ハンドヘルドデバイスなどの情報処理装置上で実行されてもよい。
【００１６】
情報処理装置１０は、記憶部１１と、中央処理装置（ＣＰＵ）１２と、メモリ１３と、入力部１４と、出力部１５とを備えて構成される。これら各機能は、バス１６を介して相互通信可能に接続されている。
【００１７】
記憶部１１は、ＲＡＭなどの書き換え可能なメモリで構成され、各種プログラムや学習パターンと、当該学習パターンを用いて作成された辞書等を保持する。また、記憶部１１には、新規パターンの認識結果が保持されても良い。
【００１８】
ＣＰＵ１２は、情報処理装置における各部の動作を制御する。
【００１９】
メモリ１３は、ＣＰＵ１２により使用されるプログラム、及びサブルーチンやデータを一時的に格納する。また、後述する処理により導出される新規パターンの認識結果を保持しても良い。
【００２０】
入力部１４は、各種情報を入力する。例えば、新規パターンを取り込んだり、ユーザからの指示入力を処理したりする。例えば、パターンとして２次元の画像を用いる場合、入力部１４は、例えば対象物体を撮影するカメラとして実現される。その他、入力部１４は、キーボードやマウス等としての役割も果たし、例えば、プログラム実行のユーザからのトリガを入力する。
【００２１】
出力部１５は、各種情報を出力する。例えば、パターン認識結果を他の装置へ出力する。出力部１５は、例えば、モニタ等で実現される場合もある。その場合、ユーザに向けて処理結果等を提示する。なお、出力先としては、人間ではなく、例えば、ロボットを制御する装置などの場合もあり得る。
【００２２】
ここで、ＣＰＵ１２上に実現される機能的な構成の一例について説明する。ＣＰＵ１２上には、機能的な構成として、学習部２１と、認識部２２とが実現される。なお、ＣＰＵ１２上に実現される機能構成は、例えば、ＣＰＵ１２が、メモリ１３等（または記憶部１１）に格納された各種制御プログラムを実行することにより実現される。
【００２３】
学習部２１は、パターン認識の対象物体が含まれる学習パターンの集合を用いて学習する。これにより、学習パターンの集合に含まれる個々の学習パターンが各ノードに分配された木構造の辞書が作成される。ここで、学習部２１には、選択部２３と、クエリ作成部２４と、分配部２５とが備えられる。
【００２４】
選択部２３は、木構造の階層ごとに、各階層に存在するノードのうちから、１または複数のノードを選択する。
【００２５】
クエリ作成部２４は、ノードに分配された学習パターンに対して実行するクエリを当該ノードに対応して作成する。
【００２６】
分配部２５は、クエリ作成部２４により作成されたクエリを各ノードで実行し、その実行結果に基づいて、学習パターンの集合に含まれる個々の学習パターンを下位のノードへ分配する。
【００２７】
認識部２２は、パターン認識の対象となるパターンの集合をルートノードに設定し、学習部２１により作成された木構造の辞書をたどりながら、各ノードに対応して作成されたクエリを実行する。これによりパターンの認識を行う。
【００２８】
次に図３の例を用いて、本発明の情報処理装置が生成する木構造を説明する。通常、パターン認識に用いられる木構造は、図３に示すような木を上下反転した図を用いる。３０１のノードが、ルートノードと呼ばれるノードで、１つの木に１つしか存在しない。線でつながっている上位ノードと下位ノードとの関係性は「親」と「子」という呼び方をする。
【００２９】
例えばノード３０１の子ノードはノード３０２とノード３０７となる。逆にノード３０２の親ノードはノード３０１である。
【００３０】
図３に示した木構造は、１つの親ノードに対して２つの子ノードがつながっている２分木と呼ばれる構造のツリーである。そして、この数は２に限らず、一般にはＮ分木のツリー構造がありうる。
【００３１】
子ノードを持つノードをインターナルノードと呼び、子ノードを持たないノードをターミナルノードと呼ぶ。ターミナルノードの中で、学習パターンの情報を全く持たないノードをｎｕｌｌノードと呼び、学習パターンの情報を持つノードをｌｅａｆノードと呼ぶ。
【００３２】
図３においては、ノード３０６とノード３０８がｎｕｌｌノードとなっておりノードを黒く塗りつぶしてｌｅａｆノードと区別している。一方、図３においてｌｅａｆノードはノード３０３、ノード３０５、ノード３０９の３つのノードとなる。
【００３３】
ここで、本実施形態に関係して重要な事がノードの階層という概念である。上から下に向かって階層が１段ずつ深くなる、と表現する。具体的には、図３において階層０に存在するノードは、ノード３０１のみである。階層１に存在するノードは、ノード３０２とノード３０７の２つのノードとなる。階層２に存在するノードは、ノード３０３、ノード３０４、ノード３０８、ノード３０９の４つのノードとなる。そして階層３に存在するノードが、ノード３０５、ノード３０６の２つのノードとなる。
【００３４】
機械学習によるパターン認識手法では、多くのパターンから学習をする学習過程と新規パターンを解析する認識過程の２つの過程が存在する。
【００３５】
図１は、学習過程を詳しく説明した図で、図４は、認識過程を詳しく説明した図はである。
【００３６】
本実施形態では、複数（Ｌ個）の木構造の辞書を作成する。Ｌは２以上の任意の定数である。Ｌを大きくすると、辞書サイズが大きくなるが、認識率は向上する。一方、Ｌを小さくすると辞書はコンパクトになるが、認識率は低下する。好ましくは、１０〜１００程度である。
【００３７】
学習過程は、ツリー番号が１からＬのループ（Ｓ５０１とＳ５０３で括られたループ）を実行する。ループの中で、図１の学習過程がサブルーチンとして呼び出される（Ｓ５０２）。Ｓ５０２でのサブルーチン呼び出しは全く独立に行われる。つまり、Ｓ５０１〜Ｓ５０３のループ処理は単純にマルチスレッド、マルチタスクで行っても何の問題もない。また、容易に複数の計算機を用いて実行することも可能となる。図５で示した複数（Ｌ個）の木構造の辞書を作成する方法は、並列計算向きであり、並列度を高くすると極めて高速に実行できると言える。
【００３８】
以下、学習過程を図１のフローチャートを用いて詳述する。
【００３９】
（ステップＳ１０１）
まず、ステップＳ１０１で、情報処理装置１０は、学習部２１において、学習パターンをルートノードに格納する。このとき、準備された全ての学習パターンを格納しても良い。また、学習パターンの全集合からランダムに選択した学習パターンの部分集合を格納しても良い。
【００４０】
（ステップＳ１０２）
次に、ステップＳ１０２で、情報処理装置１０は、学習部２１において、ターゲット階層を０に設定する。ここで言う階層は、図３で説明した木構造の階層であり、ターゲット階層を０に設定するということは、ルートノードが存在する階層をターゲット階層とすることと同義である。
【００４１】
（ステップＳ１０３）
次に、ステップＳ１０３で、情報処理装置１０は、選択部２３において、ターゲット階層にある最も多くの学習パターンを保持するノードをターゲットノードに設定する。
【００４２】
（ステップＳ１０４）
次に、ステップＳ１０４で、情報処理装置１０は、クエリ作成部２４において、ターゲットノードが保持する学習パターン集合を出来るだけ均等（略均等）に分割するクエリαを探索する。以下の説明で１つ１つの学習パターンは一般にＮ次元の特徴量ベクトルで記述されるとする。例えば、身体測定の身長、体重、体脂肪率の３次元ベクトルをもって一人一人のパターンを記述する例がある。また、ＨＯＧやＳＩＦＴといった画像を記述する特徴量ベクトルなどの例もある。
【００４３】
例えば、学習パターンを記述する特徴点（次元）を１つ選んだとして、その特徴点（次元）の値の順で学習パターン集合をソートする。そのとき、ちょうど真ん中、つまりメディアンとなる学習パターンの特徴点（次元）の値を保存する。そしてクエリとしては、保存された値以上か、値未満かで２つに分岐するクエリを生成すれば、均等に学習パターン集合を分割できる。先に述べた身体測定の例でいうと、母集団における身長の分布のメディアンをとってきて、その値より身長が高いか低いかで母集団を分割する。すると、母集団は同じ人数の部分集合に分割される。
【００４４】
特徴点（次元）を１つ選ぶ方法は、例えば、それぞれの特徴点（次元）で、学習パターン集合のヒストグラムを求めて、より分散が大きい特徴点（次元）を選ぶ方法がある。より分散が大きいということを評価するためには、例えば情報量エントロピーなどの定量化指数を用いる方法がある。なお、特徴点（次元）を１つに選ぶ選び方は、例えば一番分散の大きい特徴点（次元）を選ぶという方法がある。
【００４５】
見るべき特徴点（次元）が１つに絞れない場合や、連続値ではなく離散的な特徴量しかない場合なども存在する。例えば、性別などは２値の離散的な特徴量の例である。このときは、例えば、クエリとしてあり得るバリエーションを出来るだけ多く列挙する。そして、それらを順番に試行した後で最も均等に学習パターン集合を分割したクエリを選択する方法がある。
【００４６】
クエリとしては、画像（特徴量ベクトル）上の２点（２つの次元）を選び、その値の大小を比較することによって２つのノードに分配するクエリが考えられる。また、それ以外では、例えば、２つの点の値（輝度）の差が所定の値以上であるか否かを判定するクエリであっても良い。また、一方の点の値（輝度）が（もう一方の点の値（輝度）＋所定値）以上であるか否かを判定するクエリであっても良い。また更に、２点ではなく、ｎ点を選択して、その選択されたｎ点の輝度の値（ベクトル）を入力とする所定関数の値がある値以上であるか否かを判定するクエリであっても良い。
【００４７】
（ステップＳ１０５）
次にステップＳ１０５で、情報処理装置１０は、分配部２５において、ステップＳ１０４で決定されたクエリαを用いてターゲット階層にあるｎｕｌｌノードもしくはｌｅａｆノード以外の全てのノードを分割する。この結果、木構造は１段深くなる。すなわち、本実施形態では、同一の階層に存在するノードには共通のクエリが作成される。
【００４８】
（ステップＳ１０６）
そして、ステップＳ１０６で、情報処理装置１０は、学習部２１において、ターゲット階層を１つインクリメントする。
【００４９】
（ステップＳ１０７）
最後に、ステップＳ１０７で、情報処理装置１０は、学習部２１において、ターゲット階層にある全てのノードがターミナルノードかどうかを判定し、もし全てターミナルノードなら終了する。もしインターナルノードが残っていたら、ステップＳ１０３に戻る。
このようにして、プログラムが終了するまで木構造の深化を続ける。
【００５０】
次に、図８を用いて、図１に示す情報処理装置１０における認識処理について説明する。すなわち、図１の処理で作成した木構造の辞書を用いて、新規の未学習パターンを検出する処理の流れについて説明する。
【００５１】
次に、図４、図６を用いて、図２に示す情報処理装置１０における認識過程について説明する。すなわち、図１の処理で作成した木構造の辞書を用いて、新規の未学習パターンを検出する処理の流れについて説明する。
【００５２】
図６の認識過程も、図５の学習過程と同様に並列処理に向いており、並列度を高くすると非常に高速に処理できる。
【００５３】
次に、図６のフローチャートで認識過程を説明する。認識過程は、ツリー番号が１からＬまでのループ（Ｓ６０１〜Ｓ６０３）の後、最終的に得られたＬ個の結果を集計するステップ（Ｓ６０４）がある。ループの中で図４の木構造を用いた学習過程がサブルーチンとして呼び出される（Ｓ６０２）。
【００５４】
（ステップＳ６０２）
ステップＳ６０２は、情報処理装置１０は、図４の認識過程をサブルーチンとして呼び出す。そして、ステップＳ４０１が実行される。
【００５５】
（ステップＳ４０１）
まず、ステップＳ４０１で、情報処理装置１０は、認識部２２において、カレントノードをルートノードに設定する。
【００５６】
（ステップＳ４０２）
次に、ステップＳ４０２で、情報処理装置１０は、認識部２２において、カレントノードがターミナルノード（ｎｕｌｌノードもしくはｌｅａｆノード）であるかどうかの判断を行う。もしカレントノードがターミナルノードであった場合、認識結果にそのターミナルノードの情報をセットし終了する。
【００５７】
（ステップＳ４０３）
もし、カレントノードがターミナルノードでない場合、情報処理装置１０は、認識部２２において、カレントノードに格納されているクエリに基づいて、ノード番号を計算する。
【００５８】
（ステップＳ４０４）
そして、情報処理装置１０は、認識部２２において、計算された枝番号の子ノードをカレントノードに設定する（ステップＳ４０４）。続いて、ステップＳ４０２のカレントノードがターミナルノードかどうかの判定ステップに戻る。
【００５９】
結果、図４に示したフローチャートでは、ルートノードからｎｕｌｌノードかｌｅａｆノードに到達するまで木構造をたどることになる。ツリーをたどった結果、ｎｕｌｌノードだったら認識過程の答えは不定となる。一方、ツリーを辿った結果、ｌｅａｆノードに到達したら、そのｌｅａｆノードが持つクラス情報（例えば最も可能性の高いクラス）が答えとなる。
【００６０】
（ステップＳ６０４）
ステップＳ６０４では、情報処理装置１０は、認識部２２において、ステップＳ６０２で得られたＬ個の認識結果を集計し、最終的なパターン認識結果を得る。集計方法としては、いろいろなものが考えられる。例えばパターン認識のタスクがクラス判定タスクだったとすると、図４の結果は各クラスの存在確率ベクトルとなる。このとき、ステップＳ６０４の集計としては、Ｌ個の存在確率ベクトルの相加平均や、相乗平均などが考えられる。
【００６１】
図６の認識過程も、図５の学習過程と同様に並列処理に向いており、並列度を高くすると非常に高速に処理できる。
【００６２】
以上説明したように本実施形態によれば、各ノードにおいて実行されるクエリを、下位ノードへ均等またはなるべく均等に分配されるようにする。そのため、作成される木構造の辞書は、有効なクエリしか残らないことになる。
【００６３】
これにより、当該辞書を用いた認識処理においては、従来よりも高速且つ高精度に対象物体を認識できる。特に、山積みされた部品や人ごみ等での人物検出のように背景に対象物体と同じようなものが重なった場合に有効である。
【００６４】
［第２の実施形態］
第１の実施形態では、ターゲット階層に存在する最も多くの学習パターンを保持するインターナルノードを選び、ターゲットノードとした。これに対して、本実施形態では複数のターゲットノード群を選び、それらが保持する学習パターン集合を出来るだけ均等に分割するクエリを探索する。
【００６５】
より詳細に述べると、まず、考えうるクエリ毎にそのクエリを試行してみてターゲットノード群が分割された状況を作り出す。そして、個々のターゲットノードにおける分割指数、例えば、Ｇｉｎｉ係数やエントロピーといった指数をターゲットノード群の保持する学習パターン数に応じて重み付き平均する。そして、最終的に、この重み付き平均の値が最も良いクエリを選択する。
【００６６】
具体的には、図１と図７のフローチャートの違いで、ステップＳ７０３、ステップＳ７０４が、本実施形態の異なる点である。ステップＳ７０３で、情報処理装置１０は、選択部２３において、ある閾値以上の数の学習パターンを保持するノードをターゲットノード群として選択する。そして、ステップＳ７０４で、情報処理装置１０は、クエリ作成部２４において、ターゲットノード群が保持する全ての学習パターン集合をできるだけ均等に分割するクエリを探索する。
【００６７】
図７ではある閾値以上の数の学習パターンを保持するノードを選択したが、ターゲット階層にこの条件を満たすノードが全くない場合もあり得る。このときは、例えば、保持する学習パターンの数の多い順でターゲット階層のノードをソートし、上位Ｎ位までのノードをターゲットノードとして選択しても良い。
【００６８】
［第３の実施形態］
第１、第２の実施形態では、ある基準でクエリαを探索し、そのクエリαを用いてターゲット階層にある全てのノードを分割した。これに対して、本実施形態では、第一の実施形態の構成に加え、学習部２１に不図示の分割部２６備える。そして、本実施形態では、ターゲット階層にあるノードを複数の組（グループ）に分割する。そして、それぞれの組でクエリを探索し、それぞれのグループのノードの分割にそれを適用する。
【００６９】
フローチャートとしては図８に示したようになる。
【００７０】
（ステップＳ８０３）
まず、ステップＳ８０３で、情報処理装置１０は、不図示の分割部２６において、ターゲット階層に存在するノードをＮ組のノード群に分割する。この様子を図９を例にとって、説明する。
【００７１】
図９ではターゲット階層の深さが２である例となる。ノードは全部で９０１〜９０４の４つある。ここでそれぞれのノードが保持する学習パターンの多い順でソートした結果が、９０２、９０１、９０３、９０４の順だったとする。そこで、これら４つのノードを９０１、９０２のグループ１と９０３、９０４のグループ２に分ける。
【００７２】
（ステップＳ８０４）
そしてステップＳ８０４で、情報処理装置１０は、選択部２３において、それぞれのグループでターゲットノードを選択する。図９の例では、ノード９０２とノード９０３が選択されている。そして、それぞれの組で、ターゲットノードが保持する学習パターン集合を好適に分割するクエリを探索しそれを用いてノードを分割する。
【００７３】
なお、ここで述べた方法以外の方法を用いてターゲット階層に存在するノードを分割してもよい。例えば予め段階的な複数の閾値を決めておいて、それぞれのノードが保持する学習パターンの数がその段階的な複数の閾値以上ｏｒ未満の基準でノードをグループ分けしてもよい。
【００７４】
［第４の実施形態］
第１〜３の実施形態では、分割効率基準でクエリαを探索し、そのクエリαを用いてターゲット階層にある全て、または一部のノードを分割した。
【００７５】
選ぶべき特徴量のバリエーションが比較的少ない場合は、この方法でも現実的な時間内に処理を終わらせることができる。しかしながら、選ぶべき特徴量のバリエーションが増えてくると、この分割効率基準でクエリを選ぶ方法は破たんする場合が出てくる。本実施形態はそういう場合に有効である。
【００７６】
フローチャートに沿って説明すると、分割効率基準によるクエリαの探索にあたるステップは、ステップＳ１０４（図１）、ステップＳ７０４（図７）、ステップＳ８０５（図８）である。本実施例の方法では、これらのステップにおいて分割効率基準ではない方法でクエリを決定する。
【００７７】
図１０は、パターンとして画像が与えられている例である。この例では画像のピクセル数は縦１５×横１５の２２５ピクセルとなっている。クエリとしては、この画像の中にあるピクセルペア（例えば１００１と１００２の２点）の値の比較をすることで分岐させるクエリを考える。するとクエリのバリエーションは、２２５点あるピクセルから２ピクセルを選ぶバリエーションとなるので、結局２５２００通りとなる。
【００７８】
このクエリのバリエーションの中から最も効率よいものを選ぶためには、学習パターン集合の要素数×２５２００回の比較演算を行う必要がある。学習パターン集合の要素数が例えば１億個を超えるような場合は、比較演算だけでも２兆回を超える状況となり、最適分割のクエリを選ぶ処理は非常に時間のかかるものとなる。
【００７９】
これに対して本実施形態では、ステップＳ１００４において、まず２２５点のピクセルの平均値、分散を求める。次にステップＳ１００５で、分散の値の最も少ない点を選ぶ。これの意味は最も値が安定している点という意味である。次にステップＳ１００６で最も分散の大きい点を選ぶ。
【００８０】
なお、ステップＳ１００６において分散を評価値とするのではなく、ステップＳ１００４で決定した値との平均差分値などの指標を用いて、それが一番大きな点を選んでもよい。ただし、この場合は、２２４点（２２５から１を引いた点数）のピクセルに対する演算をもう一度行う必要があるので、速度的には不利となる。
【００８１】
また、本実施形態を簡略化した方法として、クエリで選ぶ２点のうち一方の点を画像中央の点（１００３）とするアルゴリズムを採用しても良い。
【００８２】
また、一方の点を選んだ後で、ステップＳ１００６ではなく分割効率基準でもう一方の点を選んでも良い。
【００８３】
また、ステップＳ１００４では分散の最も小さい点を選んだが、最も不安定な点を選ぶ目的で最も分散の大きい点を選んでもよい。
【００８４】
以上が本発明の代表的な実施形態の例であるが、本発明は、上記及び図面に示す実施形態に限定することなく、その要旨を変更しない範囲内で適宜変形して実施できるものである。
【００８５】
［その他の実施形態］
本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【符号の説明】
【００８６】
１１  記憶部
１２  ＣＰＵ
１３  メモリ
１４  入力部
１５  出力部
１６  バス
２１  学習部
２２  認識部
２３  選択部
２４  クエリ作成部
２５  分配部
【図１】
0006053341.tif 000002
【図２】
0006053341.tif 000003
【図３】
0006053341.tif 000004
【図４】
0006053341.tif 000005
【図５】
0006053341.tif 000006
【図６】
0006053341.tif 000007
【図７】
0006053341.tif 000008
【図８】
0006053341.tif 000009
【図９】
0006053341.tif 000010
【図１０】
0006053341.tif 000011