(57)【特許請求の範囲】
【請求項１】
輝度画像と距離画像の画像セットを複数セット取得する取得手段と、
前記画像セットに含まれている輝度画像及び距離画像から対応する部分画像を抽出し、該輝度画像から抽出した部分画像及び該距離画像から抽出した部分画像のセットを生成する生成手段と、
前記生成手段で生成された部分画像のセットを木構造のルートノードに割り当てる第１割り当て手段と、
前記木構造における各ノードにおいて、該ノードに割り当てられている部分画像の各セットに対して２つの画素の位置を設定し、それぞれのセット中の距離画像の部分画像における該２つの画素の何れかの画素値が０であるか否かを判断する判断手段と、
前記２つの画素の何れかの画素値が０であれば輝度画像の部分画像を選択し、前記２つの画素の何れの画素値も０でない場合は距離画像の部分画像を選択する選択手段と、
前記各ノードにおいて、前記割り当てられている部分画像の各セットについて、前記選択手段が選択した輝度画像若しくは距離画像の部分画像における前記設定された位置の画素値に基づいて、該セットを下位のノードのいずれかに割り当てる第２割り当て手段と、
前記木構造の末端ノードに割り当てられているセットに関する情報を出力する出力手段と
を備えることを特徴とする情報処理装置。
【請求項２】
更に、
前記第１割り当て手段、前記判断手段、前記選択手段、前記第２割り当て手段、の各手段を複数回動作させることで複数の木構造を生成させる手段を備えることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
更に、
輝度画像と距離画像の入力画像セットを取得し、該入力画像セットにおける該輝度画像及び該距離画像のそれぞれの部分領域内の画像を入力部分画像として取得する手段と、
それぞれの入力部分画像中の前記２つの画素の画素値を用いて、前記輝度画像の入力部分画像若しくは前記距離画像の入力部分画像のうち１つを選択し、該選択した入力部分画像を対象入力部分画像とする手段と、
前記木構造における各ノードにおいて、現在参照しているノードより下位のノードのうち、前記対象入力部分画像中の前記２つの画素の画素値に応じたノードを、次の参照先として選択する手段と、
前記現在参照しているノードが前記木構造の末端ノードである場合、該末端ノードに割り当てられている情報から、前記入力画像セットの識別結果を決定する決定手段と
を備えることを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
前記２つの画素の位置は、ノードごとに異なることを特徴とする請求項１乃至３の何れか１項に記載の情報処理装置。
【請求項５】
情報処理装置が行う情報処理方法であって、
前記情報処理装置の取得手段が、輝度画像と距離画像の画像セットを複数セット取得する取得工程と、
前記情報処理装置の生成手段が、前記画像セットに含まれている輝度画像及び距離画像から対応する部分画像を抽出し、該輝度画像から抽出した部分画像及び該距離画像から抽出した部分画像のセットを生成する生成工程と、
前記情報処理装置の第１割り当て手段が、前記生成工程で生成された部分画像のセットを木構造のルートノードに割り当てる第１割り当て工程と、
前記情報処理装置の判断手段が、前記木構造における各ノードにおいて、該ノードに割り当てられている部分画像の各セットに対して２つの画素の位置を設定し、それぞれのセット中の距離画像の部分画像における該２つの画素の何れかの画素値が０であるか否かを判断する判断工程と、
前記情報処理装置の選択手段が、前記２つの画素の何れかの画素値が０であれば輝度画像の部分画像を選択し、前記２つの画素の何れの画素値も０でない場合は距離画像の部分画像を選択する選択工程と、
前記情報処理装置の第２割り当て手段が、前記各ノードにおいて、前記割り当てられている部分画像の各セットについて、前記選択工程で選択した輝度画像若しくは距離画像の部分画像における前記設定された位置の画素値に基づいて、該セットを下位のノードのいずれかに割り当てる第２割り当て工程と、
前記情報処理装置の出力手段が、前記木構造の末端ノードに割り当てられているセットに関する情報を出力する出力工程と
を備えることを特徴とする情報処理方法。
【請求項６】
コンピュータを、請求項１乃至４の何れか１項に記載の情報処理装置の各手段として機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予め学習されたパターンに基づき新規パターンを解析する為の技術に関するものである。
【背景技術】
【０００２】
従来から、学習パターンを用いて新規パターンを解析する機械学習の技術がある。その中でも、分類木、決定木と呼ばれるパターン認識手法（非特許文献１）が提案され、多くのシステムで用いられてきた。この手法は、木構造（ツリー構造とも呼ばれる）を用いて高速にパターンを解析できるという性質を持っており、計算機の能力の貧弱な時代にはその能力を発揮してきた。
【０００３】
なお、パターン認識問題をパターン識別問題として捉えたとき、識別するべきパターンの種類を“クラス”と呼び、以下説明で“クラス”という言葉はこの意味で用いるものとする。
【０００４】
ここで、非特許文献１にあるような古典的な分類木、決定木の欠点として、認識性能があまり高くないということが挙げられる。この欠点を克服する技術として、例えば、特許文献１にあるような分類木の集合（アンサンブル）を用いた手法が提案されている。これは、分類木をＬ個（Ｌは２以上の定数であり、通常は１０〜１００の範囲）作成し、それら全部を用いることによって、より高い認識性能を実現する技術である。
【０００５】
この分類木の集合（アンサンブル）を用いた手法をコンピュータビジョンに応用した例としては非特許文献２に開示されているようなものがある。この論文の中で筆者は、（３２ピクセル×３２ピクセル）の画像を対象とし、その輝度値を元に分類木を作成している。より具体的には、分類木の各ノードにおいてランダムに（３２ピクセル×３２ピクセル）の画像上の２点を選び、その輝度値を比較することによって枝の分岐を実現している。この処理は非常に高速にでき、かつ、認識精度も十分高いという報告が論文の中でなされている。
【０００６】
また、一般に、複数の手法によって取得したデータを利用することで、単一のデータから認識を行うよりも高い精度で識別を行えることが知られている。例えば、非特許文献３では、Ｊｏｉｎｔ特徴を用いた動画像からの物体検出において識別対象を異なる解像度で撮像した画像や輝度画像と時空間情報、距離情報などを組み合わせることで、人や車両の検出精度が向上することが示されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許第６，００９，１９９号明細書
【非特許文献】
【０００８】
【非特許文献１】Ｌｅｏ  Ｂｒｅｉｍａｎ， Ｊｅｒｏｍｅ  Ｆｒｉｅｄｍａｎ，  Ｃｈａｒｌｅｓ  Ｊ．  Ｓｔｏｎｅ，  ａｎｄ  Ｒ．Ａ．  Ｏｌｓｈｅｎ，  “Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  ａｎｄ  Ｒｅｇｒｅｓｓｉｏｎ  Ｔｒｅｅｓ”， Ｃｈａｐｍａｎ  ＆  Ｈａｌｌ／ＣＲＣ  （１９８４）
【非特許文献２】Ｖｉｎｃｅｎｔ  Ｌｅｐｅｔｉｔ  ａｎｄ  Ｐａｓｃａｌ  Ｆｕａ，  “Ｋｅｙｐｏｉｎｔ  Ｒｅｃｏｇｎｉｔｉｏｎ  Ｕｓｉｎｇ  Ｒａｎｄｏｍｉｚｅｄ  Ｔｒｅｅｓ”，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  （２００６）  ｐｐ．１４６５−ｐｐ．１４７９
【非特許文献３】局所特徴量の関連性に着目したＪｏｉｎｔ特徴による物体検出  信学技報，ｖｏｌ．１０８，ｎｏ．４８４，ＰＲＭＵ２００８−２４７，ｐｐ．４３−５４，２００９年３月
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、複数の取得方法によるデータを用いる識別を分類木を用いた識別に適用する場合、全ての取得部で得られた画像を網羅する分類木の作成は、サイズが膨大になるため現実的ではない。例えば、２段の二分木を作成する際に輝度画像のみで認識する場合に作成される１つの分類木に対して、輝度画像と距離画像を併用して認識を行う場合、２の３乗＝８パターンの分類木が作成されることになる。
【００１０】
本発明はこのような問題に鑑みてなされたものであり、分岐パターンの爆発によるサイズの増加を防止し、単一の取得形態で取得したデータを用いた場合に近い実行速度を実現すると共に、より高精度な分類が可能とする為の技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の目的を達成するために、例えば、本発明の情報処理装置は、輝度画像と距離画像の画像セットを複数セット取得する取得手段と、
前記画像セットに含まれている輝度画像及び距離画像から対応する部分画像を抽出し、該輝度画像から抽出した部分画像及び該距離画像から抽出した部分画像のセットを生成する生成手段と、
前記生成手段で生成された部分画像のセットを木構造のルートノードに割り当てる第１割り当て手段と、
前記木構造における各ノードにおいて、該ノードに割り当てられている部分画像の各セットに対して２つの画素の位置を設定し、それぞれのセット中の距離画像の部分画像における該２つの画素の何れかの画素値が０であるか否かを判断する判断手段と、
前記２つの画素の何れかの画素値が０であれば輝度画像の部分画像を選択し、前記２つの画素の何れの画素値も０でない場合は距離画像の部分画像を選択する選択手段と、
前記各ノードにおいて、前記割り当てられている部分画像の各セットについて、前記選択手段が選択した輝度画像若しくは距離画像の部分画像における前記設定された位置の画素値に基づいて、該セットを下位のノードのいずれかに割り当てる第２割り当て手段と、
前記木構造の末端ノードに割り当てられているセットに関する情報を出力する出力手段と
を備えることを特徴とする。
【発明の効果】
【００１２】
本発明の構成によれば、分岐パターンの爆発によるサイズの増加を防止し、単一の取得形態で取得したデータを用いた場合に近い実行速度を実現することができると共に、より高精度な分類が可能となる。
【図面の簡単な説明】
【００１３】
【図１】情報処理装置の機能構成例を示すブロック図。
【図２Ａ】学習過程の処理のフローチャート。
【図２Ｂ】ステップＳ２０６における処理の詳細を示すフローチャート。
【図３】学習データの一例を示す図。
【図４】ステップＳ２０２の処理を示す模式図
【図５】木構造の一例を示す図。
【図６】図２Ｂの処理を示す模式図。
【図７】ステップＳ２１４における処理の詳細を示すフローチャート。
【図８】チャネル選択の例を示す図。
【図９Ａ】識別過程の処理のフローチャート。
【図９Ｂ】ステップＳ９０４における処理の詳細を示すフローチャート。
【図１０】チャネル決定ルーチンのフローチャート。
【図１１】ｆｅｒｎ構造の処理を説明する図。
【発明を実施するための形態】
【００１４】
以下、添付図面を参照し、本発明の好適な実施形態について説明する。なお、以下説明する実施形態は、本発明を具体的に実施した場合の一例を示すもので、特許請求の範囲に記載の構成の具体的な実施例の１つである。
【００１５】
［第１の実施形態］
本実施形態では、複数の取得手法により取得した認識対象を含む入力画像を効率よく用いて認識対象を識別することを目的とする。複数の取得手法により取得した入力画像とは、例えば、一般的な光学装置によって得られる輝度画像や既存の距離計測手法によって得られる距離画像等が挙げられる。また、複数の取得手法により取得した入力画像とは、例えばそれぞれ異なる照明パターンで撮影された各々の輝度画像等も含まれる。
【００１６】
以下の説明では、画像取得手法や画像取得状況をチャネルと称する。そして本実施形態では、輝度画像および距離画像の２チャネルの画像を用いた場合について説明する。
【００１７】
先ず、本実施形態に係る情報処理装置のハードウェア構成例について、図１のブロック図を用いて説明する。図１に示した構成は一例であり、以下に説明する各処理を実行可能な構成であれば、如何なる構成を採用しても良い。
【００１８】
ＣＰＵ１０２は、メモリ１０３に格納されているコンピュータプログラムやデータを用いて情報処理装置全体の動作制御を行うと共に、情報処理装置が行うものとして後述する各処理を実行する。
【００１９】
メモリ１０３は、ＲＡＭやＲＯＭ等により構成されており、外部記憶装置１０１からロードされたコンピュータプログラムやデータを一時的に記憶する為のエリアや、入出力装置１０４を介して入力された各種のデータを一時的に記憶する為のエリアを有する。また、メモリ１０３は、ＣＰＵ１０２が各種の処理を実行する際に用いるワークエリアを有する。即ち、メモリ１０３は、各種のエリアを適宜提供することができる。
【００２０】
外部記憶装置１０１は、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置１０１には、ＯＳ（オペレーティングシステム）や、情報処理装置が行うものとして後述する各処理をＣＰＵ１０２に実行させるためのコンピュータプログラムやデータが保存されている。また、外部記憶装置１０１には、入出力装置１０４を介して入力された各種のデータを保存することもできる。外部記憶装置１０１に保存されているコンピュータプログラムやデータは、ＣＰＵ１０２による制御に従ってメモリ１０３にロードされ、ＣＰＵ１０２による処理対象となる。
【００２１】
入出力装置１０４は、情報処理装置におけるデータの入出力インターフェースとして機能する。例えば、入出力装置１０４は、認識対象を撮像するための撮像装置であっても良いし、認識対象を撮像した画像を保持するメモリから該画像を情報処理装置に入力する装置であっても良い。また、ユーザが各種の指示を情報処理装置（ＣＰＵ１０２）に対して入力するための操作部であっても良い。また、入出力装置１０４は、情報処理装置が生成した様々なデータ（認識結果を示すデータや、木構造のデータなど）を外部に送信する装置であっても良い。もちろん、入出力装置１０４は、これらの装置の１以上の集合であっても良い。
【００２２】
また、以下に説明する各処理を実現するコンピュータプログラムの実行のトリガーを、この入出力装置１０４を介してユーザが出す場合もある。また、ユーザが結果を見たり、コンピュータプログラムのパラメータ制御をこの入出力装置１０４を介して行うこともある。また、結果の出力先としては、人間（ユーザ）ではなく、例えばロボットを制御する装置などのマシンの場合も有り得る。
【００２３】
次に、学習過程において情報処理装置（ＣＰＵ１０２）が行う処理について、同処理のフローチャートを示す図２Ａを用いて説明する。学習過程では、図２Ａの処理の中で図２Ｂの処理を再帰的に呼び出すことで、後述する学習パターンの集合を再帰的に分割して木構造の生成を行う。
【００２４】
先ず、ステップＳ２０１では、入出力装置１０４や外部記憶装置１０１から、学習データをメモリ１０３に読み出す。学習データとは、チャネル毎に用意された画像群（学習画像）を指す。即ち、認識対象をそれぞれ異なるチャネルで撮像することで得られる画像セット（学習画像のセット）を、複数セット取得する。
【００２５】
学習データの一例を図３を用いて説明する。学習データ３００は輝度チャネル３０１と距離チャネル３０２の２チャネルから成っている。輝度チャネル３０１には認識対象を含む輝度画像（学習輝度画像）から成る学習輝度画像群３０３が、距離チャネル３０２には認識対象を含む距離画像（学習距離画像）から成る学習距離画像群３０４が存在する。学習画像がＮパターンの異なる視点から撮影された画像であるとすると、学習データは学習輝度画像Ｎ枚および学習距離画像Ｎ枚から成り、合計（２×Ｎ）枚となる。
【００２６】
ここで図３の場合、輝度チャネル３０１の画像として示されている画像のうち左端の画像と、距離チャネル３０２の画像として示されている画像のうち左端の画像と、は画像の種類は異なるものの、同じ認識対象を輝度画像、距離画像として撮像したものである。これは、左から２番目以降の画像についても同じである。即ち、学習データには、認識対象をそれぞれ異なるチャネルで撮像することで得られる画像の各セットが、複数セット含まれていることになる。
【００２７】
学習過程では、チャネル毎に存在する学習画像にクラス（パターンの種類）名称が付加されているいわゆる「教師付き学習」が行われる。また、学習輝度画像には、照明変動等の影響を軽減するためにエッジ抽出などの前処理を施してもよい。
【００２８】
図２Ａに戻って、次に、ステップＳ２０２では、入力された学習データから学習パターンの生成を行う。ステップＳ２０２における処理の詳細について、図４の模式図を用いて説明する。
【００２９】
本実施形態では、学習パターンは、各学習輝度画像、各学習距離画像から、Ｍ枚の部分画像を抽出することで生成される。なお、部分画像は、各チャネルの学習画像において同一位置の領域が抽出されるものとし、部分画像同士は重なりがあるように網羅的に元の画像から抽出されることが望ましい。図４に学習画像として示したＮ枚の画像の一枚一枚が図３における各チャネルの画像（輝度画像と距離画像）から構成されていると考えることができる。すなわち各チャネルは最終的な部分画像群として、同じクラス（学習画像）の部分画像がそれぞれＭ枚ずつ、Ｍ×Ｎ枚の部分画像をもつことになる。
【００３０】
換言すれば、認識対象をそれぞれ異なるチャネルで撮像することで得られる画像セット（Ｎセット分）ごとに、該画像セットに含まれているそれぞれのチャネルの画像（２画像分）中の部分領域（Ｍ個分）内の画像を部分画像として取得する。これにより、それぞれのチャネルの部分画像のセットがＮセット分得られる。
【００３１】
学習過程ではこれらのM×N枚の部分画像を学習パターンとして登録して分類する分類木を生成していく。すべてのチャネルのすべての部分画像（２チャネルの場合は（２×Ｎ×Ｍ）枚）を分類するのではなく、分類木の各ノードにおいて部分画像のセットごとに分岐の判定に用いるチャネルを選択する。これにより、チャネル数が増加しても木構造の本数を増加させることなく学習パターンの分類を行える。なお、精度よく分類を行うためにここで学習データに対してチャネルごとに異なる前処理を施してもよい。
【００３２】
そして、ステップＳ２０３〜Ｓ２０７のループにおいて、ステップＳ２０２で作成した学習パターンを分類するＬ本の木構造を生成する。Ｌは２以上の任意の定数であり、１０〜１００程度の数であることが望ましい。Ｌを大きくすると辞書サイズが大きくなるが、認識率は向上する。一方、Ｌを小さくすると辞書はコンパクトになるが、認識率は低下する。作成する木構造の一例を図５に示す。学習パターンはルートノード５０１から順に下位のノードへたどっていくことで分類される。
【００３３】
先ず、ステップＳ２０４では、木構造のルートノード（図５ではルートノード５０１）に全ての学習パターンを割り当てる（格納する）。図４の例では、Ｎ枚の学習輝度画像、Ｎ枚の学習距離画像、のそれぞれから抽出したＭ枚の部分画像の集合（（２×Ｍ×Ｎ）枚の部分画像）を木構造のルートノードに割り当てる。
【００３４】
なお、以下の説明において「ノードに割り当てる」とは、ノードに関連付けることである。なお、ノードＡに対して割り当てられていたものをノードＢに割り当てる場合、ノードＡとの関連づけは削除し、ノードＢとの関連付けを行う。
【００３５】
次に、ステップＳ２０５では、ルートノードをカレントノードに設定する。カレントノードとは、学習過程および認識過程において現在処理しているノードを意味する。
【００３６】
ステップＳ２０６では、カレントノードに割り当てられている学習パターン集合の分割を行う。ステップＳ２０６では、図２Ｂに示したフローチャートに従った処理を実行し（カレントノードを展開するサブルーチンを呼んで）、このサブルーチンから返ってきたら木構造の作成は終了となる。図５においては５０１から５０９の番号順にカレントノードは移動することとなる。この処理をＬ回繰り返し実行（複数回動作）して、Ｌ本の木構造を作成し、学習過程は終了する。
【００３７】
ここで、ステップＳ２０６における処理の詳細を、同処理のフローチャートを示す図２Ｂを用いて説明する。図２Ｂに示したフローチャートは、ノードを展開するサブルーチンを説明したフローチャートである。
【００３８】
先ず、ステップＳ２１１では、カレントノードがｎｕｌｌノード、ｌｅａｆノードの何れか、若しくは何れでもないのかを判断する。この判断の結果、カレントノードが、ｎｕｌｌノード、ｌｅａｆノードの何れかであった場合は、処理はステップＳ２０７に進み、次の木構造を作成すべく、処理をステップＳ２０４に進める。
【００３９】
ここで、カレントノードに１つも学習パターンが割り当てられていない場合、このカレントノードはｎｕｌｌノードとする。また、カレントノードに割り当てられている学習パターンの集合がある一定条件を満たした場合、このカレントノードをｌｅａｆノードとする。ここでいうある一定条件とは、例えば、“カレントノードに存在するクラスがＫ種類（例えばＫ＝１０）以下だった場合（カレントノードに割り当てられている学習パターンの数がＫ個以下）”という条件などが考えられる。この条件でＫ＝１に設定した場合は、“カレントノードが純粋に１つのクラスしか含まない”という条件となる。
【００４０】
図５の例では、ノード５０３、５０５、５０６、５０９がｌｅａｆノードであり、５０８がｎｕｌｌノードとなる。図２Ｂのフローチャートでいうと、カレントノードにノード５０３、５０５、５０６、５０８、５０９が設定された場合、ステップＳ２１１における判断では「ｙｅｓ」となり、サブルーチンが終了する。ｎｕｌｌノードおよびｌｅａｆノードは、ターミナルノードとも呼ばれ、残った学習パターンの情報が割り当てられる。例えば、パターン認識の目的がクラス判定の場合、ターミナルノードには各クラスの存在確率が割り当てられる。なお、前述した通り、ｌｅａｆノードの条件が“カレントノードに純粋に１つのクラスしか含まれない”であった場合、その残ったクラスの番号を情報として割り当てても良い。一方、パターン認識の目的がいわゆる回帰の場合、ターミナルノードにはある推定値、もしくは推定ベクトルが割り当てられる。
【００４１】
一方、カレントノードが、ｎｕｌｌノード、ｌｅａｆノードの何れでもない場合は、処理はステップＳ２１２に進む。ステップＳ２１２以降では、サブルーチンの処理が続き、カレントノードに格納された学習パターンを複数の子ノードへ分割する。その処理はステップＳ２１２〜Ｓ２１８のステップで行う。この中でステップＳ２１７で図２Ｂのサブルーチンを再帰的に呼び出すため、学習パターンの集合が再帰的に分割されることとなる。処理の流れを図６の模式図に示す。図６（ａ）は、カレントノードがターミナルノードではない場合の初期状態を示している。この場合、カレントノードには、複数の部分画像セット（学習輝度画像の部分画像と、該学習輝度画像と同セットの学習距離画像において該部分画像と同位置の部分画像と、から成るセット）が割り当てられている。以下では、カレントノードに割り当てられているそれぞれの部分画像セット中の学習距離画像の部分画像をカレントパターンと呼称する。
【００４２】
ステップＳ２１２では、カレントノードの展開に先立ちクエリを実行するためのクエリ点の選択を行う。“クエリ”とは、あるパターンがどの枝に属するのかを判断する問い合わせのことである。このカレントノードのクエリは、カレントノードに割り当てられているカレントパターンの集合（カレントパターン集合）を用いて作成される。
【００４３】
本実施形態では、クエリは、後述するステップＳ２１４で選択されるチャネルｃの学習パターン中の任意の２点（クエリ点）の画素値の大小を比較するものとする。すなわち，チャネルｃの学習パターン中のクエリ点Ａ，Ｂの画素値をそれぞれｑ（Ａ，ｃ），ｑ（Ｂ，ｃ）とすると、クエリ処理Ｑは以下の式で表される。
【００４４】
ｉｆ  ｑ（Ａ，ｃ）−ｑ（Ｂ，ｃ）＞０  ｉ→ｌｅｆｔ  ｎｏｄｅ
Ｑ（ｉ，ｃ）＝
ｅｌｓｅ                              ｉ→ｒｉｇｈｔ  ｎｏｄｅ
ｉ∈Ｐ  ｜  Ｐ：カレントパターン集合
この場合、ステップＳ２１２で実施するクエリ点の選択とは、カレントパターン中の任意の２点を選択する動作に該当する。図６（ｂ）に示すように、クエリ点はノードごとに決定され、あるノードに割り当てられているカレントパターンはすべて同一のクエリ点を用いてクエリを行う。クエリ点の位置は、ノードごとにランダムに決めても良いし、ノードごとに予め定められた方法で決めても良い。
【００４５】
クエリ手法は、上記の式を用いた方法以外にも様々な手法が考え得る。例えば、２点の画素値の差がある値以上か未満かで、ｉ→ｌｅｆｔ  ｎｏｄｅ（以上）とするか、ｉ→ｒｉｇｈｔ  ｎｏｄｅ（未満）とするか、を決めても良い。また、２点ではなくｎ（ｎ≧３）点を選択し、その画素値の総和がある値以上か未満かで、ｉ→ｌｅｆｔ  ｎｏｄｅ（以上）とするか、ｉ→ｒｉｇｈｔ  ｎｏｄｅ（未満）とするか、を決めても良い。
【００４６】
より一般的には、複数の点を選択し、その複数の点の画素値（ベクトル）を入力とするある関数の値が、ある値以上か未満かで分岐することができる。更に、画素値ではなく入力画像に所定の変換を加えて得られる特徴量（ベクトル）の中のｎ次元の値を比較してもよい。
【００４７】
次に、ステップＳ２１３〜Ｓ２１６のループで、カレントパターンごとにクエリを行うチャネルを決定し、クエリに従って分割する。即ち、カレントノードに割り当てられているＰ個のカレントパターンのうち第ｉ番目のカレントパターン（ｉ＝１，２，…，Ｐ）についてクエリを行うチャネルを決定し、クエリに従って分割する処理を、ｉ＝１〜Ｐについて行う。
【００４８】
ステップＳ２１４で行うチャネルの決定処理では、本実施形態では、カレントパターンにおいてステップＳ２１２で選択されたクエリ点の画素値を参照して判定する。クエリに用いるチャネルの決定処理は図７に示すサブルーチンによって実行される。
【００４９】
図７のサブルーチン（チャネル決定ルーチン）では、有効なクエリが行えるクエリ点の組み合わせをとるようなチャネルを選択する必要がある。本実施形態では、輝度チャネルと距離チャネルを用いて識別を行っている。ここで、距離チャネルの場合、例えば、空間コード化法によって距離撮像を行った場合には、外乱光によるノイズやテカリ・黒潰れ等の要因によってパターン縞が映らずに距離計測に失敗する領域が発生しうる。このような領域上の点は極力クエリに利用すべきではない。より一般的には、次のような処理を行う。即ち、優先的に選択するチャネルを決定しておき、そのチャネルにおけるクエリ点の値が正確な値でない場合（本実施形態の場合は距離計測に失敗した場合）には次に優先するチャネルのクエリ点の値を調べる、という過程を繰り返すことでチャネル決定を行う。
【００５０】
先ず、ステップＳ７０１では、第ｉ（ｉ＝１，２，…，Ｐ）番目のカレントパターン（カレントパターンｉ）におけるクエリ点の画素値を参照する。そして、それぞれのクエリ点のうち、参照した画素値が０（本実施形態では、計測失敗領域の画素値を０と設定する）であるクエリ点があったか否かを判断する。この判断の結果、あった場合は、処理はステップＳ７０２に進み、無かった場合は、処理はステップＳ７０３に進む。
【００５１】
ステップＳ７０２では、輝度チャネルをクエリに用いるチャネルとして選択する。一方、ステップＳ７０３では、クエリに用いるチャネルとして距離チャネルを選択する。クエリに応じたチャネル選択の例を図８に示す。
【００５２】
距離画像８１１における点８１２及び点８１３（輝度画像８０１における点８０２及び点８０３に対応している）がクエリ点として選択された場合、点８１２及び点８１３の何れも画素値は０ではない。この場合は、距離チャネルをクエリを行うチャネルとして選択する。
【００５３】
一方、距離画像８１１における点８１２及び点８１４（輝度画像８０１における点８０２及び点８０４に対応している）がクエリ点として選択された場合、点８１４の画素値が０である（点８１４が計測失敗領域からとられた点である）。この場合は、輝度チャネルをクエリを行うチャネルとして選択する。
【００５４】
なお、クエリ点は、輝度画像上に設定しても良く、その場合、設定した点に対応する距離画像上の点の画素値を用いて同様にチャネル選択を行えば良い。
【００５５】
このように、カレントノードにおけるそれぞれのカレントパターンについて上記のようなチャネル選択を行うことで、図６（ｃ）に示す如く、各カレントパターンには、選択したチャネルが対応づけられることになる。
【００５６】
次に、ステップＳ２１５では、カレントパターンｉを含む部分画像セットｉにおいて、ステップＳ２１４で選択したチャネルｃの学習パターンについて上記の式を用いて計算を行い、Ｑ（ｉ，ｃ）を求める。このとき、ｉにｌｅｆｔ  ｎｏｄｅが設定されていれば、カレントノードより下位（１つ下位）のノードのうち、左側のノード（ｌｅｆｔ  ｎｏｄｅ）を選択し、該選択したノードに部分画像セットｉを割り当てる。一方、ｉにｒｉｇｈｔ  ｎｏｄｅが設定されていれば、カレントノードより下位（１つ下位）のノードのうち、右側のノード（ｒｉｇｈｔ  ｎｏｄｅ）を選択し、該選択したノードに部分画像セットｉを割り当てる。
【００５７】
下位のノードへの分岐数Ｒは、一般的にはカレントノードによって異なっていても良いが、通常は全てのノードで同じ値を用いる。また、分割は枝とも呼ばれる。本実施形態ではクエリＱによって学習パターンは２つに分割されるためＲ＝２となり、図５のような二分木が作成される。
【００５８】
例えば、図８を例にとり説明すると、上記の通り、距離画像８１１における点８１２及び点８１３がクエリ点として選択された場合、点８１２及び点８１３の何れも画素値は０ではないため、距離チャネルをクエリを行うチャネルとして選択することになる。そこで、点８１２及び点８１３のそれぞれの画素値が上記の式により比較される。その結果、（点８１２における画素値）−（点８１３における画素値）＝１８０−１９０＝−１０＜０であるため、距離画像８１１及び輝度画像８０１を含む部分画像セットは、カレントノードより下位（１つ下位）のノードのうち右側のノードに割り当てられる。
【００５９】
一方、距離画像８１１における点８１２及び点８１４がクエリ点として選択された場合、点８１４の画素値が０であるため、輝度チャネルをクエリを行うチャネルとして選択することになる。そこで、点８０２及び点８０４のそれぞれの画素値が上記の式により比較される。その結果、（点８０２における画素値）−（点８０４における画素値）＝２５５−０＝２５５＞０であるため、距離画像８１１及び輝度画像８０１を含む部分画像セットは、カレントノードより下位（１つ下位）のノードのうち左側のノードに割り当てられる。
【００６０】
このようにして、カレントノードにおける各部分画像セットを、ｌｅｆｔ  ｎｏｄｅ、ｒｉｇｈｔ  ｎｏｄｅ、の何れかに分割する。このような処理によれば、各ノードでカレントパターンごとにクエリするチャネルを選択することで質の高いクエリを行うことが可能となる。
【００６１】
ステップＳ２１７〜Ｓ２２０は分岐毎のループで、ステップＳ２１８で分岐ｊをカレントノードに設定し、ステップＳ２１９で図２Ｂのサブルーチンを再帰呼び出しする。前述のとおり，本実施形態ではステップＳ２１７におけるノードごとの分岐の数Ｒは２とする。
【００６２】
以上の処理により、学習過程では、学習画像の部分領域を分類する木構造を生成する。生成した木構造のデータは、メモリ１０３や外部記憶装置１０１等に格納する。もちろん、格納先についてはこれに限るものではない。
【００６３】
なお、上記の学習過程における処理は、以下に説明する構成の一例である。即ち、まずは、画像取得手法若しくは画像取得状況をチャネルとし、認識対象をそれぞれ異なるチャネルで撮像することで得られる画像セットを、複数セット取得する。
【００６４】
そして、画像セットに含まれているそれぞれのチャネルの画像中の部分領域内の画像を部分画像として取得し、該取得したそれぞれのチャネルの部分画像のセットを木構造のルートノードに割り当てる（第１割り当て）。
【００６５】
そして、木構造における各ノードをルートノードから末端ノードに向けて順に参照する際、現在参照しているノードに割り当てられているセットをカレントセットとする。そして、該カレントセット中の規定チャネルの部分画像中の複数画素の画素値を用いて、それぞれ異なるチャネルのうち１つを選択する。
【００６６】
そして、カレントセット中の部分画像のうち選択したチャネルの部分画像を対象部分画像とする。そして、現在参照しているノードより下位のノードのうち対象部分画像中の複数画素の画素値に応じたノードを選択し、該選択したノードにカレントセットを割り当てる（第２割り当て）。
【００６７】
そして、上記の第１割り当て及び第２割り当てによる割り当て後、木構造の末端ノードに割り当てられているセットに関する情報を該末端ノードに割り当ててから、木構造を出力する。
【００６８】
次に、この木構造を用いて認識対象を識別する処理について説明する。識別過程は、チャネル数分の入力画像を入力として受けとる。本実施形態では学習過程で輝度チャネルと距離チャネルについて学習を行っているため、識別過程で入力する画像は、輝度画像と距離画像の２枚の画像を入力として受け取る。
【００６９】
そしてこれらの入力画像から部分画像を抽出し、それぞれの部分画像（識別パターン）に対して、学習過程で作成した複数の木構造を用いて識別を行い、最後に全ての木構造の識別結果を集計して、最終的な結果として出力する。なお、ここでいう各木構造を用いた「識別」とは、入力された識別パターンに最も類似する学習過程で学習されたクラスを選択することを指す。識別パターンを木構造にかけるときに各ノードで用いるチャネルを決定し、ノードごとに異なるチャネルの識別パターンのみを使って分岐をすすめていくことが特徴の一つとなる。
【００７０】
識別過程において情報処理装置（ＣＰＵ１０２）が行う処理について、同処理のフローチャートを示す図９Ａを用いて説明する。なお、識別過程の処理は、学習過程の処理を行った装置（本実施形態では図１に示した情報処理装置）以外の装置が行っても良く、その場合、図１の情報処理装置は、識別過程の処理を行う装置に対して、木構造のデータを送出する必要がある。
【００７１】
ステップＳ９０１〜Ｓ９０６のループは、識別用に入力された輝度画像及び距離画像のそれぞれから抽出する部分画像の枚数分だけ繰り返して行う。即ち、輝度画像及び距離画像のそれぞれからＭ枚の部分画像を抽出する場合、ステップＳ９０１〜Ｓ９０６のループはＭ回繰り返すことになる。
【００７２】
ステップＳ９０２では、識別用に入力された輝度画像及び距離画像のそれぞれから、上記のステップＳ２０２と同様にして１枚の部分画像を抽出し、これを識別パターンとする。識別パターンのサイズは、学習パターンのサイズと同じであり、入力画像（輝度画像及び距離画像）全体から重なりを持って抽出するものとする。入力画像から抽出される識別パターンはできるだけ密にとることが精度の面からみると望ましいが、ステップＳ９０１〜Ｓ９０６のループは識別パターンの枚数だけ実行されるため、実行時間とのトレードオフを考える必要がある。
【００７３】
ステップＳ９０３〜Ｓ９０５のループでは、ステップＳ９０２で抽出した識別パターンに対し、学習過程で作成したＬ本の木構造を順に適用し、Ｌ本の木構造のそれぞれについて、該識別パターンがたどり着くＬｅａｆノードを特定する。この処理は、ステップＳ９０４で行われる。即ち、学習過程で生成したＬ本の木構造においてｉ番目の木構造を用いたステップＳ９０４の処理を、ｉ＝１〜Ｌについて行う。ステップＳ９０４における処理の詳細について、同処理のフローチャートを示す図９Ｂを用いて説明する。
【００７４】
ステップＳ９１１では、ｉ番目の木構造のルートノードをカレントノードに設定する。
【００７５】
ステップＳ９１２では、カレントノードがｎｕｌｌノード、ｌｅａｆノードの何れか、若しくは何れでもないのかを判断する。この判断の結果、カレントノードが、ｎｕｌｌノード、ｌｅａｆノードの何れかであった場合は、処理はステップＳ９０５に進み、（ｉ＋１）番目の木構造を用いてステップＳ９０４の処理を行う。
【００７６】
一方、カレントノードが、ｎｕｌｌノード、ｌｅａｆノードの何れでもない場合は、処理はステップＳ９１３に進む。ステップＳ９１３では、ステップＳ９０２で抽出した識別パターンのうち距離チャネルの識別パターンを用いて、図７のフローチャートに従った処理を行う。これにより、ステップＳ９０２で抽出した識別パターンのうち、何れのチャネルの識別パターンを以降で用いるのかを選択することができる。
【００７７】
このように、チャネルの決定を学習過程と同様に行うことで、次のような効果を奏することができる。即ち、クエリに用いるチャネルの情報が辞書に記載されていなくても、識別過程においてある学習パターンと同一のクラスに属する識別パターンが入力されたときにはその学習パターンと同様のチャネルが選択され、正しくクエリを行うことができる。 
ステップＳ９１４では、ステップＳ９０２で抽出した識別パターンのうちステップＳ９１３で選択したチャネルの識別パターンを用いて、カレントノードより１つ下位のノード（左側のノード及び右側のノード）のうち一方を選択する。選択方法は、学習過程と同様の方法（上記式を用いた方法）でもって行う。
【００７８】
ステップＳ９１５では、ステップＳ９１４で選択したノード（子ノード）をカレントノードに設定し、ステップＳ９１２に処理を進める。これにより、図９Ｂに示したフローチャートでは、ルートノードからｎｕｌｌノードかｌｅａｆノードに到達するまで木構造をたどることになる。
【００７９】
ステップＳ９０１〜Ｓ９０６のループが全て終了すると、ステップＳ９０２で抽出した識別パターンごとに、Ｌ個の識別結果（Ｌ本の木構造の個々について得た、該識別パターンがたどり着いたｌｅａｆノードに割り当てられている情報）が得られる。
【００８０】
ステップＳ９０７では、これらの識別結果を集計することで最終的にある１つの学習画像を、入力画像に対する認識対象識別結果として出力する。集計方法は特定の方法に限るものではなく、如何なる方法を用いても良い。例えば、ステップＳ９０２で抽出した識別パターンごとに得たＬ個のクラスの存在確率ベクトルの相加平均、相乗平均などの計算処理を行い、その結果に最も近いクラスの学習画像を出力しても良い。また、部分画像の学習画像中での位置を記録したオフセットを用いて、学習画像の存在位置を投票によって求めることもできる。
【００８１】
なお、上記の識別過程における処理は、以下に説明する構成の一例である。即ち、それぞれ異なるチャネルで撮像することで得られる入力画像セットを取得し、該入力画像セットに含まれているそれぞれのチャネルの入力画像中の部分領域内の画像を入力部分画像として取得する。
【００８２】
そしてそれぞれのチャネルの入力部分画像のうち規定チャネルの入力部分画像中の複数画素の画素値を用いてそれぞれ異なるチャネルのうち１つを選択し、それぞれのチャネルの入力部分画像のうち該選択したチャネルの入力部分画像を対象入力部分画像とする。
【００８３】
そして、木構造における各ノードをルートノードから末端ノードに向けて順に参照する際、現在参照しているノードより下位のノードのうち、対象入力部分画像中の複数画素の画素値に応じたノードを、次の参照先として選択する。そして、現在参照しているノードが木構造の末端ノードである場合、該末端ノードに割り当てられている情報から、入力画像セットの識別結果を決定する。
【００８４】
［第２の実施形態］
本実施形態では図２Ｂおよび図９Ｂにおけるチャネル決定ルーチンの処理のみが異なり、その他については、第１の実施形態と同様である。然るに以下では、他の処理は第１の実施形態と同様であるため、ここではチャネル決定ルーチンについて図１０を用いて説明する。
【００８５】
ステップＳ１００１〜Ｓ１００３のループは、チャネルの数Ｃだけ繰り返す。本実施形態でも２チャネルであるため、Ｃ＝２となる。然るに、この場合、ｃ＝１，２について、ステップＳ１００２〜Ｓ１００３の処理を行うことになる。
【００８６】
ステップＳ１００２では、チャネルｃの部分画像におけるクエリ点の画素値を参照する。そして、参照したクエリ点の画素値から、該クエリ点に対する信頼度を算出する。ここでの信頼度とは、各チャネルにおけるカレントノードでのクエリ点がクエリに有用であるかどうかを示す指標である。信頼度の算出の仕方は任意であり、また、チャネルに応じて異なる算出手法を用いてよい。一般的には、有効にクエリが行えるクエリ点の組み合わせである時に高い値が出るように設定される。前処理としてエッジ抽出処理が行われた輝度画像の場合、画素値の差が大きい点をクエリしたときにそのクエリ点は有効であり、逆にエッジのない領域同士がクエリ点として選択されている場合はいずれの画素値も０であるため有用なクエリ点とは言えない。
【００８７】
そこで本実施形態では、輝度画像におけるクエリ点の画素値の差を輝度チャネルにおけるクエリの信頼度とする。また、距離画像の場合、第１の実施形態の説明で述べたように、計測に失敗した領域内の点がクエリ点に選ばれた時には、そのチャネルを用いたクエリは誤った分割をする恐れがあるため信頼度を低く設定すべきである。本実施形態ではいずれかのクエリ点の画素値が０である場合の信頼度を０とする。ただし、本実施形態でも第１の実施形態と同様に計測に失敗した領域の画素値を０としている。
【００８８】
また、ステレオ法や空間コード化法による距離データの取得では、急激に距離の変動が生じる物体のエッジ付近で誤差が大きくなる傾向がある。あるいは、物体同士の多重反射により空間コード化法における照射パターンが乱れ誤った距離情報が取得されてしまう場合がある。そこで、一定の範囲内で大きく距離変動が生じている領域の信頼度は低く設定した方がよい。本実施形態では、クエリ点とその周辺の領域の画素値の分散を信頼度の値とする。
【００８９】
処理がステップＳ１００４に進んだ時点で、Ｃチャネルのそれぞれの部分画像について信頼度が求まっていることになるため、ステップＳ１００４では、最大の信頼度を求めたチャネルを選択する。なお、あるチャネルの信頼度が閾値以上であるときにはそのチャネルを用い、閾値未満であるときには別のチャネルを使うようにしてもよい。
【００９０】
［第３の実施形態］
本実施形態では、木構造の代わりに、ｆｅｒｎ構造（Ｍ．  Oｚｕｙｓａｌ，ｅｔ  ａｌ  “Ｆａｓｔ  Ｋｅｙｐｏｉｎｔ  Ｒｅｃｏｇｎｉｔｉｏｎ  ｕｓｉｎｇ  Ｒａｎｄｏｍ  Ｆｅｒｎｓ”  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ＰＡＭＩ，  Ｖｏｌ．  ３２，  Ｎｒ．  ３，  ｐｐ．  ４４８  −  ４６１，  ２０１０．）を用いた学習・識別について述べる。
【００９１】
入力されるデータや全体の処理の流れについては第１の実施形態あるいは公知のｆｅｒｎ構造と同様であるため詳細な処理の流れの説明については割愛し、ここでは本実施形態に固有のｆｅｒｎ構造（判別器）の処理について述べるものとする。
【００９２】
木構造による学習では各ノードでの分割結果に基づいて学習パターンを異なる子ノードへと分割していくことで学習パターンの分類を行った。また、分割の判定を行うクエリはノードごとに異なるものが用いられていた。ｆｅｒｎ構造による学習では、クエリは深さごとに決められており、学習パターンごとに各深さでのクエリの結果を記録することで、学習パターンの分類を行う。
【００９３】
図１１を用いて本実施形態に係るｆｅｒｎ構造の処理について説明する。なお、本実施形態では、第１の実施形態と同様に、クエリは選択されたチャネルｃにおけるカレントパターン中の任意の２点（クエリ点）の画素値の大小を比較するものとする。すなわち，チャネルｃの学習パターン中のクエリ点Ａ，Ｂの画素値をそれぞれｑ（Ａ，ｃ），ｑ（Ｂ，ｃ）とすると、クエリ処理Ｑは以下の式で表される。
【００９４】
ｉｆ  ｑ（Ａ，ｃ）−ｑ（Ｂ，ｃ）＞０  Ｑ（ｉ，ｃ）＝１
ｅｌｓｅ                              Ｑ（ｉ，ｃ）＝０
ｉ∈Ｐ  ｜  Ｐ：カレントパターン集合
図１１では、３段の深さを有するｆｅｒｎ判別器１１００を示している。第１の実施形態と同様に、学習パターンはまず１段目の深さ（ｄ１）のクエリにより分類される。このとき、カレントパターンごとに各チャネルにおけるクエリ点の画素値により適切なチャネルが選択される。図１１においては３種のチャネルを用いて学習を行っているが、チャネル選択は図１０で示した処理と同様にチャネルに応じて定められた信頼度を比較することで行えばよい。
【００９５】
図１１では、チャネル選択の結果、カレントパターンＣＰ１１０１はチャネル１が選択され、ｄ１のクエリにより“０”と分類されている。同様にカレントパターンＣＰ１１０２はチャネル３が選択され“１”に分類され、カレントパターンＣＰ１１０３はチャネル２が選択されて“１”と分類されている。以下、ｄ２、ｄ３のクエリでも同様に全ての学習パターンについてチャネル選択およびクエリによる分類を行い、最終的に全てのクエリでの分類をまとめたものがその学習パターンの分類結果となる。例えば図１１におけるカレントパターンＣＰ１１０１の分類結果は“００１”となり、同様にカレントパターンＣＰ１１０２は“１１１”、カレントパターンＣＰ１１０３は“１００”と分類されている。なお、簡単のためここでは３段のｆｅｒｎ構造について説明したが、本来は１０以上の深さであることが望ましい。
【００９６】
識別過程におけるｆｅｒｎ構造の動作の詳細な説明は割愛するが、学習過程と同様に、識別パターン集合に対して各深さでパターンごとにチャネル選択およびクエリによる分類を行い、全てのクエリの結果をまとめたものをその識別パターンの分類結果とする。学習時に行われたチャネル選択の結果は識別時には反映されないが、同種の判断基準によってチャネル選択を行うため、ある学習パターンに類似した識別パターンが入力された時にはチャネル選択の結果も同じになる。これにより、学習過程と識別過程の双方で適切なチャネルが選択されることになる。
【００９７】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
0006032930.tif 000002
【図２Ａ】
0006032930.tif 000003
【図２Ｂ】
0006032930.tif 000004
【図３】
0006032930.tif 000005
【図４】
0006032930.tif 000006
【図５】
0006032930.tif 000007
【図６】
0006032930.tif 000008
【図７】
0006032930.tif 000009
【図８】
0006032930.tif 000010
【図９Ａ】
0006032930.tif 000011
【図９Ｂ】
0006032930.tif 000012
【図１０】
0006032930.tif 000013
【図１１】
0006032930.tif 000014