(57)【特許請求の範囲】
【請求項１】
複数のカテゴリのいずれかに属する対象物体を含む入力画像を取得する第１の取得手段と、
前記入力画像を構成する複数の部分画像を取得する第２の取得手段と、
前記部分画像から、少なくとも一つの特徴量を抽出する抽出手段と、
前記対象物体を認識するための学習画像を構成する部分学習画像のカテゴリと前記部分学習画像の位置情報との組を登録した辞書を保持する保持手段と、
前記抽出手段で抽出された特徴量に基づいて前記辞書を参照することにより、前記部分画像ごとに、前記辞書に登録されている前記部分学習画像のカテゴリ及び前記部分学習画像の位置情報との組に分類する分類手段と、
前記分類手段によって前記部分画像ごとに分類された結果を集計することにより、前記入力画像に含まれる対象物体のカテゴリと位置とを認識する認識手段とを備えることを特徴とする情報処理装置。
【請求項２】
前記認識手段は、前記部分画像ごとに、前記分類されたそれぞれのカテゴリの前記位置情報が示す位置に投票する投票手段を備え、
前記投票手段による投票結果を集計することにより前記入力画像に含まれる対象物体のカテゴリと位置とを認識することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記投票手段は、前記部分画像の中心画素から前記分類されたカテゴリの前記対象物体の重心位置の画素へ投票することを特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記カテゴリは、前記対象物体の姿勢であることを特徴とする請求項１乃至３のいずれか１項に記載の情報処理装置。
【請求項５】
前記位置情報は、前記部分学習画像の中心位置と前記部分学習画像に含まれる対象物体の重心位置との間の関係であることを特徴とする請求項１乃至４のいずれか１項に記載の情報処理装置。
【請求項６】
前記保持される辞書は、複数の識別器を備え、
前記分類手段は、前記取得された部分画像に対して、前記複数の識別器ごとにそれぞれ前記カテゴリ及び前記部分学習画像の位置情報との組に分類することを特徴とする請求項１乃至５のいずれか１項に記載の情報処理装置。
【請求項７】
前記辞書は、木構造型の識別器であることを特徴とする請求項１乃至６のいずれか１項に記載の情報処理装置。
【請求項８】
前記抽出手段により抽出される特徴量は、前記部分画像に含まれる画素の輝度値であることを特徴とする請求項１乃至７のいずれか１項に記載の情報処理装置。
【請求項９】
前記輝度値が抽出される画素は、ランダムに決定されることを特徴とする請求項８に記載の情報処理装置。
【請求項１０】
前記入力画像は、濃淡画像であることを特徴とする請求項１乃至９に記載の情報処理装置。
【請求項１１】
前記学習画像は、ＣＧ画像であることを特徴とする請求項１乃至１０のいずれか１項に記載の情報処理装置。
【請求項１２】
前記複数の部分画像は、互いに重複する領域を持つことを特徴とする請求項１乃至１１のいずれか１項に記載の情報処理装置。
【請求項１３】
前記入力画像には、複数の対象物体が含まれることを特徴とする請求項１乃至１２のいずれか１項に記載の情報処理装置。
【請求項１４】
複数のカテゴリのいずれかに属する対象物体を含む学習画像を取得する第１の取得手段と、
前記学習画像を構成する複数の部分学習画像を取得する第２の取得手段と、
前記部分学習画像から、少なくとも一つの特徴量を抽出する抽出手段と、
前記抽出手段で抽出された特徴量に基づいて、前記部分学習画像を、前記部分学習画像のカテゴリと前記部分学習画像の位置情報との組に分類する分類手段と、
前記分類された前記部分学習画像のカテゴリと前記部分学習画像の位置情報との組を記憶する記憶手段とを備えることを特徴とする情報処理装置。
【請求項１５】
複数のカテゴリのいずれかに属する対象物体を含む入力画像を取得する第１の取得工程と、
前記入力画像を構成する複数の部分画像を取得する第２の取得工程と、
前記部分画像から、少なくとも一つの特徴量を抽出する抽出工程と、
前記抽出工程において抽出された特徴量に基づいて、前記部分画像ごとに、前記対象物体を認識するための辞書に登録されている部分学習画像のカテゴリ及び前記部分学習画像の位置情報との組に分類する分類工程と、
前記分類工程において前記部分画像ごとに分類された結果を集計することにより、前記入力画像に含まれる対象物体のカテゴリと位置とを認識する認識工程とを備えることを特徴とする情報処理方法。
【請求項１６】
複数のカテゴリを取り得る対象物体を含んだ学習画像を取得する第１の取得工程と、
前記学習画像を構成する複数の部分学習画像を取得する第２の取得工程と、
前記部分学習画像から、少なくとも一つの特徴量を抽出する抽出工程と、
前記抽出工程で抽出された特徴量に基づいて、前記部分学習画像に含まれる前記対象物体のカテゴリと前記部分学習画像の位置情報との組を分類する分類工程とを備えることを特徴とする情報処理装置。
【請求項１７】
コンピュータを、請求項１乃至１３のいずれか１項に記載の情報処理装置の各手段としてを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は対象物の撮像画像を用いて対象物の名称、種類、存在位置、姿勢等の情報を推定する画像認識方法に関するものである。ここでいう対象物とは任意の物体を表し、例えば、人、動物、自動車、カメラ、プリンタ、半導体基板など何でもよい。
【背景技術】
【０００２】
従来、予め学習しておいた対象物体の画像と新たに撮影した対象物体を含む画像をパターンマッチングすることによって対象物体の種類と存在領域を推定する方法があった（例えば、特許文献１参照）。特許文献１においては、予め学習、登録しておく対象物体の画像から固有値と固有ベクトルを計算する。そして、新たに撮影した画像から切り出した画像をその固有ベクトルへ射影することで、より少ない数のモデルで対象物体の認識ができるようになる工夫がなされている。また、予め学習、登録しておく対象物体の画像を分割して得られる部分学習画像を用いることによって、より認識率を高める工夫が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００２−３２７６６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１に開示された方法に代表される画像のパターンマッチング方法では認識に膨大な時間を要するという問題があった。特に判別するべきクラスの数が膨大になると認識時間が爆発するという問題があった。例えば、対象物体の種類が１，０００種類（例えば１，０００人の顔を登録）あり、それぞれの対象物体に対して色々な角度から撮影した学習画像が１つの物体につき１００枚（横顔なども含む）あったとする。すると、全部で１００，０００個の学習パターンが存在することになる。これでは、１つの登録画像と新規撮影画像の画像照合がたとえ１０ｎｓで行えたとしても、最終的な認識結果を得るために１秒かかってしまう。
【０００５】
なお、ここで言う登録画像は例えば対象物体を囲む外接矩形の内部を想定し、新規撮影画像は登録画像を含む大きなサイズの画像を想定している。よって、１つの登録画像と新規撮影画像の画像照合は単純な１対１の画像パターンマッチングではなく、新規撮影画像の中のどの部分に対象物体が存在するかという位置特定のタスクも含む。具体的には、例えば新規撮影画像をスライディングウィンドウで切り出しそれぞれの切り出し画像と登録画像をマッチングすることによって、画像照合を実現する。よって、登録画像と新規撮影画像のピクセル数にもよるが、上記の１０ｎｓという画像照合時間は現状のコンピュータ処理速度からいうと非常に高速で処理した場合といえる。
【０００６】
さらに従来技術で問題だったことは、特許文献１で開示された部分学習画像を用いる画像マッチング方法ではこの認識時間が爆発するという問題がより顕著に現れてくるということである。例えば１つの学習画像を互いに重なり合う１００（＝１０×１０）の部分画像に分割したとすると、マッチングするべき登録画像が１００倍になることになるので、計算時間も単純に１００倍となる。先の例だと１００秒もの時間が必要になってくる。
【０００７】
また、特許文献１で開示された固有ベクトルを用いて次元を削減する方法を用いたとしても、距離計算の計算時間は短縮できるが、次元を削減するためのベクトル計算を省略することはできないので、結局トータルの画像認識の高速化は実現できない。そして登録画像の種類と同じ回数の画像照合が必要になるという本質的な課題は全く解決されていない。
【課題を解決するための手段】
【０００８】
そこで、本発明の情報処理装置は、複数のカテゴリのいずれかに属する対象物体を含む入力画像を取得する第１の取得手段と、前記入力画像を構成する複数の部分画像を取得する第２の取得手段と、前記部分画像から、少なくとも一つの特徴量を抽出する抽出手段と、前記対象物体を認識するための学習画像を構成する部分学習画像のカテゴリと前記部分学習画像の位置情報との組を登録した辞書を保持する保持手段と、前記抽出手段で抽出された特徴量に基づいて前記辞書を参照することにより、前記部分画像ごとに、前記辞書に登録されている前記部分学習画像のカテゴリ及び前記部分学習画像の位置情報との組に分類する分類手段と、前記分類手段によって前記部分画像ごとに分類された結果を集計することにより、前記入力画像に含まれる対象物体のカテゴリと位置とを認識する認識手段とを有する。
【発明の効果】
【００１０】
本発明によれば、高速、高精度に対象物の名称、種類、存在位置、姿勢等の情報を推定することが出来るようになるという効果がある。特に、照合するべき登録画像が増加した場合でも認識速度がその数に比例して落ちないという効果がある。より限定したケースとして、属性判定方法に分類木を採用した場合は、登録画像の種類の数の対数に比例した認識時間しか必要としないという効果がある。また、画像認識に好適な部分画像のサイズを決定することによって、より高い認識率を実現できるという効果もある。
【図面の簡単な説明】
【００１１】
【図１】実施形態の画像認識装置の処理構成を表す図である。
【図２】実施形態の画像認識方法の処理手順を示すフローチャートである。
【図３】情報処理装置のハードウェア構成の一例を示す図である。
【図４】部分画像属性判定ステップを説明する図である。
【図５】登録部分画像群を説明する図である。
【図６】学習ステップを模式的に表した図である。
【図７】学習ステップの具体的な処理を説明する図である。
【図８】部分画像集合を分割する方法を説明する図である。
【図９】実施形態２の部分画像結果集計ステップを説明する図である。
【図１０】実施形態３を説明する図である。
【図１１】実施形態３を説明するフローチャートである。
【図１２】実施形態４の部分画像サイズ決定ステップを説明するフローチャートである。
【図１３】実施形態４の部分画像サイズ決定ステップでのサイズ評価方法を説明する図である。
【図１４】実施形態５の部分画像サイズ決定ステップでのサイズ評価方法を説明する図である。
【図１５】実施形態５の部分画像サイズ決定ステップの動作の仕方を模式的に表した図である。
【図１６】実施形態６の処理手順を表わすフローチャートである。
【図１７】実施形態６の分類木による認識処理手順を表わすフローチャートである。
【図１８】実施形態６の投票方法を説明する図である。
【図１９】実施形態６の投票の際の重み分布を説明する図である。
【発明を実施するための形態】
【００１２】
以下、添付図面を参照しながら本発明の実施形態を説明する。
【００１３】
＜実施形態１＞
図１は、実施形態による画像認識方法の基本的な処理構成を説明する図である。図２は、実施形態による画像認識方法の処理手順を示すフローチャートである。
【００１４】
まず、部分画像サイズ決定部１０１で、切り出す部分画像のサイズ１０２を事前に決定する。この部分画像サイズ決定部１０１の処理内容の詳細は実施形態４で説明する。ここでは、適切な部分画像サイズ１０２が部分画像サイズ決定部１０１によって事前に決定されるものとする。
【００１５】
ここで、認識時に比較対象となる画像を登録する場合、第１の抽出手段である登録部分画像集合抽出部１０４により、部分画像サイズ１０２に基づいて、登録画像１０３から登録部分画像集合１０５が取り出される。取り出された登録部分画像集合１０５が登録画像毎にＭ枚、登録画像の数がＮ枚だとすれば、登録部分画像集合１０５は全部でＮ×Ｍ枚となる。更に、辞書作成部１１３により、登録部分画像集合１０５から認識用の辞書１１４を作成する。ただし、認識用の辞書１１４を作成する処理は必須ではなく、登録部分画像集合１０５をそのまま利用して認識するようにしてもよい。
【００１６】
一方、新規画像を認識する場合、第２の抽出手段である新規部分画像集合抽出部１０７により、新規画像１０６から部分画像サイズ１０２の新規部分画像集合１０８が抽出される。そして、部分画像属性判定部１０９で、先に抽出された登録部分画像集合１０５もしくはそれから作成された辞書１１４を元に新規部分画像集合１０８を構成する各新規部分画像の属性が判定される。
【００１７】
最後に、新規部分画像集合１０８の各要素である新規部分画像の判定結果１１０を部分画像判定結果集計部１１１で集計し、最終的な認識結果１１２が得られる。なお、実施形態１においては、部分画像判定結果１１０は属性の判定結果だけであるが、実施形態２では、部分画像判定結果１１０にその部分画像の画像内の位置を表わす位置情報１１５が含まれる。詳しくは実施形態２の説明で述べる。
【００１８】
部分画像集合抽出部１０７で抽出される新規部分画像集合１０８を構成する部分画像がＫ枚だとする。この時、もしも部分画像属性判定部１０９で、特許文献１に代表されるような、いわゆるテンプレートマッチングと呼ばれる処理を採用すると、全部でＮ×Ｍ×Ｋ回の照合処理をする必要がある。この時、部分画像属性判定部１０９では登録部分画像集合１０５が用いられる。
【００１９】
これに対して、本実施形態に示す方法では、いわゆる機械学習を取り入れることでこの処理回数をＫ回に削減できる。この時、部分画像属性判定部１０９では辞書１１４が用いられる。
【００２０】
なお、一般には上記説明した定数Ｍと定数Ｋの関係はＭ≠Ｋである。しかし、登録画像のサイズと新規画像のサイズが同じ場合、例えばそれぞれの画像に含まれる全部分画像を用いるとＭ＝Ｋの関係が成り立つ。登録画像のサイズと新規画像のサイズが異なる場合は実施形態３で詳しく説明する。
【００２１】
部分画像判定結果集計部１１１をより具体的に説明する。部分画像属性判定１０９における“属性”とは、一般には（ｐ１，ｐ２，・・・，ｐＮ）というＮ次元の確率ベクトルを意味する。ここにＰｉとは新規部分画像がｉ番目の登録画像に含まれる確率である。新規部分画像集合１０８がＫ枚から構成されている場合、このＮ次元確率ベクトルがＫ個存在することとなる。最終的な認識結果１１２は、これらＫ個の確率ベクトルを単純に相加平均、または、対数を取った後の相加平均（Ｋ個の確率を掛け合わせる相乗平均に対応する）などの処理をして得られる平均確率の中で、最大確率を示す登録画像のインデックスとなる。
【００２２】
図２において、（ａ）が学習時のフローチャートで、（ｂ）が判定時のフローチャートとなる。
【００２３】
学習時は、登録画像それぞれについてステップＳ１０１〜Ｓ１０５のループが実行され、各登録画像において、部分画像のそれぞれについてステップＳ１０２〜Ｓ１０４のループが実行され、登録部分画像集合１０５が作成される。ステップＳ１０１〜Ｓ１０５の登録画像のループはＮ回実行され、ステップＳ１０２〜Ｓ１０４の部分画像のループはＭ回実行され、ステップＳ１０３の部分画像抽出は合計でＮ×Ｍ回実行される。
【００２４】
本実施形態の画像認識方法では、望ましくは、ステップＳ１０６で、登録部分画像集合１０５から辞書１１４を作成する。但し、本実施形態は、このいわゆる機械学習の枠組みを用いる方法に限ったものではなく、登録部分画像集合１０５をそのまま用いて画像マッチングを行っても良い。
【００２５】
図２の（ｂ）が判定時のフローチャートで、まず、新規画像からそれに含まれる部分画像を抽出しながら部分画像の属性を判定するループ（Ｓ１０６〜Ｓ１０９）が実行される。このループはＫ回実行される。ステップＳ１０７で抽出される部分画像は１０８の新規部分画像集合１０８を構成する１枚の新規画像中の部分画像である。
【００２６】
ステップＳ１０９では、登録部分画像集合１０５または辞書１１４を用いて新規部分画像から部分画像判定結果１１０を導く。
【００２７】
ステップＳ１１０において、部分画像判定結果１１０を集計して最終的な認識結果１１２が導かれる。
【００２８】
図３は、本実施形態を含む全ての実施形態に係わる画像認識方法が実行される情報処理装置の構成を示すブロック図である。
【００２９】
画像認識方法は、外部記憶装置２０１、中央処理装置（ＣＰＵ）２０２、メモリ２０３、入出力装置２０４を備えた装置に実装される。外部記憶装置２０１は、本実施形態の処理を実現するプログラムや、カメラで撮影した登録画像、登録画像を用いて作成された辞書１１４等を保持する。また、本実施形態によって導かれた対象物体の認識結果を保持する機能を持つ。ＣＰＵ２０２は、画像認識方法のプログラムを実行したり、装置各部の制御を行ったりする。メモリ２０３は、ＣＰＵ２０２が使用するプログラム、及びサブルーチンやデータを一時的に記憶する。入出力装置２０４は、カメラからの画像を取り込んだり、ユーザーとのインタラクションを行ったり、画像認識結果を他の情報処理装置へ出力したりする。入力装置としてはカメラが一般的であるが、スキャナーなどの装置も利用できる。また、本実施形態の画像認識方法を実現するプログラム実行のトリガーを、この入出力装置を介してユーザーが出す場合もある。また、ユーザーが結果を見たり、プログラムのパラメータ制御をこの入出力装置を介して行うこともある。また、出力先としてはロボットを制御する装置のような場合も有り得る。
【００３０】
図４を用いて、部分画像属性判定部１０９の処理を詳しく述べる。本実施形態の画像認識方法では、いわゆる機械学習の手法を想定している。この場合、部分画像属性判定部１０９の処理は、学習フェーズと認識フェーズの２つのフェーズに分れる。
【００３１】
まず、学習フェーズでは、学習部３０２において、登録部分画像集合３０１から判別器３０３が作成される。判別器３０３では、ニューラルネット、サポートベクターマシン等の機械学習で一般的に用いられるアルゴリズムを用いることができる。より好ましくは、図６以降で述べる分類木の集合を用いた方法を採用することができる。
【００３２】
判別器３０３は、部分画像の属性をルールに従って判別するものであり、その実態は、採用したアルゴリズムの学習後の内部パラメータである。具体的には、ニューラルネットであれば全てのコネクションの重みの集合となり、サポートベクターマシンであれば全てのサポートベクトルの集合となる。分類木の場合は、木構造の各インターナルノードでの判定パラメータ集合と各ターミナルノードにおけるクラス存在確率の集合が内部パラメータとなる。ここで、インターナルノードとは、子ノードがあるノードで、ターミナルノードとは子ノードがない末端のノードのことを意味する。
【００３３】
認識フェーズでは、属性判定部３０５において、新規画像から抽出された新規部分画像を判別器３０３を用いて判定し、属性判定結果３０６を得る。なお、新規部分画像３０４は、図１の新規部分画像集合１０８を構成する各要素に対応し、属性判定結果３０６は図１の部分画像判定結果１１０に対応する。
【００３４】
図３の属性判定部３０５では、属性判定という表現を用いたが、機械学習の分野では通常は認識と呼ぶ。というのも、属性判定部３０５では新規部分画像と登録部分画像を１枚１枚照合するわけではなく、学習した全ての登録部分画像群の情報が格納されている判別器３０３に基づいて新規部分画像がどの登録部分画像とどれだけ似ているかを導くからである。
【００３５】
本実施形態においては、新規部分画像３０４が複数あり、部分画像判定結果３０６も複数ある。それを図１の部分画像判定結果集計部１１１において集計することによって、最終的な認識結果１１２が求まる。属性判定部３０５に敢えて認識という表現を用いなかったのは、この最終的な認識結果を得るのではないことを強調したかったためである。
【００３６】
従来のパターンマッチングの方法であれば、この属性判定部３０５において、登録部分画像集合１０５と新規部分画像集合１０８の全ての組み合わせ毎の処理が必要となる。これに対して、本実施形態では、基本的に新規部分画像集合１０８の要素の数しか処理の回数は必要ない。
【００３７】
次に、図５を用いて登録部分画像集合１０５の説明をする。１枚の登録画像（学習画像）からＭ枚の部分画像が抽出される。これを部分画像集合と呼ぶ。この部分画像集合を構成する部分画像同士は重なりがなくても良いが、重なりがあるように網羅的に元の学習画像から抽出されることが望ましい。
【００３８】
例えば学習画像のサイズが１００×１００ピクセルで、部分画像のサイズが５０×５０ピクセルだったとする。ピクセルとピクセルの中間の位置（いわゆるサブピクセル）を考慮に入れないとすると、１枚の学習画像から抽出される全部分画像は２６０１（＝５１×５１）枚となる。なお、重なりのない部分画像を抽出したとすると全部で２×２＝４枚の部分画像が得られる。
【００３９】
部分画像集合は２６０１枚ある全部分画像に含まれる、出来るだけ多く（例えば半分以上）の部分画像からなることが望ましい。最終的な学習（登録）部分画像群としては、同じクラス（＝登録画像のインデックスと同義）にタグ付けされた登録部分画像がそれぞれＭ枚ずつ、全部でＭ×Ｎ枚の学習部分画像が得られる。
【００４０】
次に、学習アルゴリズムの説明をする。図６は学習部３０２の処理を模式的に表した図である。また、同じ図を使って属性判定部３０５の処理も説明する。
【００４１】
本実施形態の学習では、分類木と呼ばれる木構造の判別器がＬ個作られる。Ｌは１でもよいが、１０〜３０の数が望ましい。分類木はインターナルノードとターミナルノードから構成されている。インターナルノードでは、どの子ノードへ行くべきかという判定式、判定のルールもしくは判定ルーチンが存在する。ターミナルノードでは、認識対象のクラスの存在確率が保持されている。
【００４２】
学習フェーズでは、図５に示した学習部分画像群を用いて２分木を作成していく。全部でＬ個分類木が存在するので、この分類木作成はＬ回行われる。分類木作成の際、各分類木のインターナルノードでは、ランダムに２つのピクセルを選び、そのピクセルの輝度比較をすることにより、学習部分画像群に含まれる部分画像の集合を２つに分けていく。この処理の詳細な説明は図７を用いて後で述べる。
【００４３】
なお、本実施形態においてはランダムに２つのピクセルを選んだが、部分画像中の任意の矩形領域をランダムに２つ選んで、その矩形領域の平均輝度を比較することによって枝分れを行ってもよい。また、矩形ではなく予め用意した複数のマスクパターンを用いて部分画像中の任意の位置にある任意の種類のマスクパターンをランダムに２つ選んで、その領域の平均輝度を比較することによって枝分かれを行っても良い。
【００４４】
新規部分画像をこの分類木の集合を使って処理する属性判定部３０５では、分類木をたどる処理をＬ回することになる。新規部分画像を参照しながら分類木を辿った結果、最終的にＬ回ターミナルノードに行き着く。登録画像がＮ枚あるとすると、一般的にはそれぞれのターミナルノードではＮ個の存在確率のベクトル（ｐ１，ｐ２，…，ｐＮ）が格納されているので、結局、Ｌ個の確率ベクトルが得られる。最終的にはこれらＬ個の確率ベクトルを単純に相加平均、または、対数を取った後の相加平均（Ｌ個の確率を掛け合わせる相乗平均に対応する）などの処理をして得られる平均確率が、本実施形態の属性判定部３０５の最終出力となる。なお、上記平均確率を先鋭化する方法として、一番確率の高い値以外の確率を０としてもよい。これはいわゆるＬ個の分類木の認識結果の投票で一番得点の高かったクラスを属性判定部３０５の結果とすることに相当する。
【００４５】
次に、属性判定部３０５による計算時間のオーダーを解析してみる。上記の分類木の個数Ｌは定数なので、計算時間のオーダーには関係ない。計算時間は、分類木の深さに比例し、最大値としては登録する画像の数の対数に比例して増加する。つまり、本実施形態の画像認識方法の場合、どんなに遅くてもｌｏｇ（登録部分画像の数）のオーダーの計算時間しか必要ないことになる。これに対して例えば特許文献１で開示されたような従来の画像照合方法では、登録部分画像の枚数のオーダーで計算時間が必要になってくる。
【００４６】
図７を用いて学習部３０２の具体的な処理を説明する。
【００４７】
分類木の作成はサブルーチン６０１のＳｐｌｉｔ＿ａ＿ｎｏｄｅ（Ｓ）を再帰的にコールすることによって実現される。サブルーチンＳｐｌｉｔ＿ａ＿ｎｏｄｅ（Ｓ）はサブルーチン６０２のＰｉｃｋ＿ａ＿ｒａｎｄｏｍ＿ｓｐｌｉｔ（Ｓ）とサブルーチン６０３のＳｔｏｐ＿Ｓｐｌｉｔ（Ｓ）をコールする。
【００４８】
分類木のトップのノード（ルートノード）に存在する画像は登録部分画像全部であり、Ｓｐｌｉｔ＿ａ＿ｎｏｄｅ（Ｓ）を最初にコールする時のＳは登録部分画像の全部となる（全体集合も部分集合の１種）。
【００４９】
再帰的にサブルーチン６０１が呼び出されるということは、Ｓｐｌｉｔ＿ａ＿ｎｏｄｅ（Ｓ）の結果、登録部分画像の集合がＳ０とＳ１の２つの集合に分割され、Ｓｐｌｉｔ＿ａ＿ｎｏｄｅ（Ｓ０）とＳｐｌｉｔ＿ａ＿ｎｏｄｅ（Ｓ１）が実行されることを意味する。
【００５０】
サブルーチン６０１のＳｐｌｉｔ＿ａ＿ｎｏｄｅの中身は、まずＳｔｏｐ＿ｓｐｌｉｔ（Ｓ）をコールし、返り値がＴＲＵＥの場合、そのノードをターミナルノードとして再帰呼び出しを終了する。ターミナルノードでは、これまで説明してきた通り、クラスの存在確率が格納される。このクラスの存在確率は、サブルーチンＳｐｌｉｔ＿ａ＿ｎｏｄｅの引数であるＳから、Ｓの中の登録画像のクラスの個数を数えることにより求められる。例えば、Ｓの登録部分画像の集合の中に、ある登録画像の部分画像しか含まれなかったら、そのクラスの確率が１で、他のクラスの確率が０となる。
【００５１】
次に、Ｓｔｏｐ＿ｓｐｌｉｔ（Ｓ）の返り値がＦＡＬＳＥの場合、Ｚ回Ｐｉｃｋ＿ａ＿ｒａｎｄｏｍ＿ｓｐｌｉｔ（Ｓ）をコールする。（例えばＺ＝１０００）そして、もしＰｉｃｋ＿ａ＿ｒａｎｄｏｍ＿ｓｐｌｉｔ（Ｓ）の返り値となる分割がＯＫだったら、ループを終了してその分割を返す。ＯＫかどうかの判定はＳＯとＳ１のどちらにも１個以上の登録部分画像が含まれる条件となる。（｜Ｓ｜は集合Ｓに含まれる要素の数を意味する）
Ｚ回Ｐｉｃｋ＿ａ＿ｒａｎｄｏｍ＿ｓｐｌｉｔ（Ｓ）を試みてもＯＫな分割ができない場合は、そのノードをターミナルノードとして再帰処理を終了する。
【００５２】
Ｐｉｃｋ＿ａ＿ｒａｎｄｏｍ＿ｓｐｌｉｔ（Ｓ）ルーチンは、図６で説明してきた通り、画像中の２つのピクセルをランダムに選び、それらの輝度比較をする。
【００５３】
サブルーチン６０３のＳｔｏｐ＿Ｓｐｌｉｔ（Ｓ）はターミナルノードの条件が満たされるかどうかを判定するルーチンである。ｅｎｔｒｏｐｙ（Ｓ）とは登録部分画像の集合Ｓの情報論的エントロピーでクラスの存在確率を（ｐ１，ｐ２，・・・，ｐＮ）とすると  式  −Σ（ｐｉ＊ｌｏｇ（ｐｉ））で計算される。例えばＳがある登録画像に含まれる部分画像しか含まないとするとエントロピーは０となる。
【００５４】
このＳｔｏｐ＿Ｓｐｌｉｔ（Ｓ）のｔｈｒｅｓｈｏｌｄの値を変更することで、どれだけノードがピュアになればターミナルノードにするかという基準を変えることができる。例えばｔｈｒｅｓｈｏｌｄを０とすると、ターミナルノードには必ずある登録画像の部分画像しか含まないようになる。
【００５５】
なお、本実施形態において、関数Ｓｔｏｐ＿Ｓｐｌｉｔ（Ｓ）が常にＴＲＵＥを返すようにすることもできる。すると再帰的なノード作成（展開）は行われず、ルートノードとその子ノードしか存在しない構造が出来上がることになる。
【００５６】
続いて、図８を用いて、サブルーチン６０１のＳｐｌｉｔ＿ａ＿ｎｏｄｅ（Ｓ）の動きを説明する。
【００５７】
登録部分画像の集合の要素が、例えば１６個（登録部分画像の数が１６枚）だったとする。するとルートノードには図８の左に書いた１６枚の画像が存在することになる。
【００５８】
ルートノードでランダムに２つのピクセルを選び、登録部分画像集合に含まれる全部分画像をそれらの輝度比較をすることで２つの集合に分割する。図８の例では、左の子ノードに１０枚の部分画像が残り、右の子ノードに６枚の部分画像が残ったことになる。なお、グレーアウトした画像は残らなかった画像を意味する。
【００５９】
次に、右の子ノードにおいて、サブルーチン６０３のＳｔｏｐ＿Ｓｐｌｉｔ（Ｓ）の返り値がＦＡＬＳＥだった場合は、さらにその下の子ノードを展開する。その時は、また別の２つのピクセルをランダムに選び、それらの輝度比較をすることによって、集合を分割していく。
【００６０】
図８に示した例では、左の子ノード、右の子ノードとも３つの要素が残ったことになる。
【００６１】
＜実施形態２＞
図９を用いて実施形態２を説明する。
【００６２】
実施形態１においては、ある登録画像に含まれる部分画像を全て同じクラスとして扱ってきた。実施形態２においては、これを全て異なるクラスとして扱う。
【００６３】
なお、“クラス”とは、機械学習で判別するべき対象の種類のことで、通常、画像認識の場合は登録画像の種類となる。上で述べた「ある登録画像に含まれる部分画像を全て同じクラスとして扱う」ということは、ある登録画像に含まれる色々な部分画像群を、“見え”が異なるが同じ種類の画像群として扱うことを意味する。これに対して、「ある登録画像に含まれる部分画像を全て異なるクラスとして扱う」ということは、違う位置から取り出した部分画像は同じ登録画像由来であっても異なる種類のものだとして扱うことを意味する。具体的には、部分画像に位置情報を持たせることによって、部分画像１つ１つを区別する。
【００６４】
Ｎ枚の登録画像があり、１枚の登録画像につきＭ枚の部分画像があるとすると、実施形態１では登録部分画像が全部でＭ×Ｎ枚、クラスの数はＮであった。実施形態２では、これが登録部分画像が全部でＭ×Ｎ枚、クラスの数のＭ×Ｎとなる。
【００６５】
図９を用いて、位置情報の具体的な例とその使い方を述べる。
【００６６】
図９では登録画像が登録画像Ａと登録画像Ｂの２枚、１つの登録画像につき部分画像が重なりのない３×３＝９枚あるとする。本実施形態では部分画像は好ましくは重なっているが、重ならなくても一般性を失わないので、簡単のために重ならない例を用いて以下、説明する。
【００６７】
図９に描かれている点線の矢印は、図１の部分画像判定結果１１０、図３の属性判定結果３０６で、最もマッチした登録部分画像と入力部分画像との組み合わせを示す。新規部分画像は９枚、そのそれぞれに登録部分画像１８（＝９＋９）枚とのマッチング結果がある。一般的には、部分画像属性判定の結果、新規部分画像９枚それぞれに（ｐ１，ｐ２，・・・，ｐ１８）の１８次元のクラス存在確率が導かれることになるが、簡単のために図に示した最もマッチした部分画像の確率が１でその他が０として、説明する。なお、以下の議論は、確率ベクトル（ｐ１，ｐ２，・・・，ｐ１８）による重み付け平均を計算することによって、一般の場合に拡張できる。
【００６８】
部分画像属性判定の結果、新規画像の部分画像９枚は、Ａの部分画像６枚とＢの部分画像３枚とマッチングしたことになる。正確にマッチした部分画像の枚数をスコアとすると、実施形態１の場合、Ａの得点が６で、Ｂの得点が３となり、新規画像は登録画像Ａと認識される。
【００６９】
しかし、“正確にマッチした部分画像”という定義を位置情報も含めて考えると、Ａの得点が１で、Ｂの得点が３となり、新規画像は登録画像Ｂと認識される。これが実施形態２の一番簡単な例となる。
【００７０】
この場合、結果的に、新規画像の正しい認識結果がＢだとすると、実施形態１の場合は間違いで、実施形態２の場合は正解となることになる。
【００７１】
なお、より精密にスコアを計算したい場合、マッチした部分画像の位置と本来マッチすべき位置との距離Ｄの関数を用いてスコアを算出しても良い。例えばｅｘｐ（−Ｃ＊Ｄ）、ｅｘｐ（−Ｃ＊Ｄ＊Ｄ）、１／（１＋Ｃ＊Ｄ＊Ｄ）（Ｃは任意の正定数、ｅｘｐとは指数関数）などの関数（評価式）を用いても良い。
【００７２】
スコアにｅｘｐ（−Ｃ＊Ｄ）を用いた場合の計算式を以下に述べる。（簡単のために以下、Ｄは２次元上のユークリッド距離、Ｃ＝１とする）
図９にあるように、新規部分画像と登録画像Ａの部分画像は、新規部分画像９枚のうち、６枚の登録画像Ａの部分画像とのマッチングがとれている。そして、それらの位置から２次元上の距離を計算すると、（左上Ａ（０，１））、（右上Ａ（０，０））、（左中Ａ（０，１））、（左下Ａ（２，２））、（中下Ａ（２，２））、（右下Ａ（０，２））がそれぞれ、
【００７３】
【数１】
0005538967.tif 000002
【００７４】
となる（ここで、上記の説明で、左上などの表記は新規画像における部分画像の位置を意味しており、それに続くＡ（０，１）などの表記はそれに対応するマッチング結果を意味する。）。その結果、Ａのトータルスコアは、
【００７５】
【数２】
0005538967.tif 000003
【００７６】
となる。
【００７７】
一方、新規部分画像と登録画像Ｂの部分画像は、新規部分画像９枚のうち、３枚の登録画像Ｂの部分画像とのマッチングがとれている。そして、それらの位置から２次元上の距離を計算すると、（中上Ｂ（１，０））、（中中Ｂ（１，１））、（右中Ｂ（２，１））がそれぞれ、
【００７８】
【数３】
0005538967.tif 000004
【００７９】
となる。その結果、Ｂのトータルスコアは、
【００８０】
【数４】
0005538967.tif 000005
【００８１】
となる。
【００８２】
なお、この例ではそれぞれマッチングが取れた部分画像同士のスコアを加算してトータルスコアを導いたが、乗算することでトータルスコアを導いてもよい。
【００８３】
＜実施形態３＞
図１０、図１１を用いて実施形態３を説明する。
【００８４】
実施形態１、実施形態２においては、登録画像は矩形の形をしていた。つまり、矩形の内部を全て登録画像として扱っていた。しかし、一般には、登録画像の矩形の内部は対象物と背景に分離することができる。例えば、図１０の（ａ）に示した対象物は登録画像中の楕円の形をしているとする。本実施形態では、図１の登録部分画像集合抽出部１０４において、登録画像中の全ての部分画像を抽出するのではなく、対象物が存在する楕円の内部の部分画像のみを抽出する。このことで、背景の画像を抽出せずに、対象物の内部の画像のみを抽出することができるようになる。
【００８５】
また、登録する部分画像が対象物の内部に完全に含まれる、という条件よりもっと緩い条件を設定することもできる。例えば、部分画像中の対象物の占める面積が８０％以上となる部分画像を抽出する、ということもできる。
【００８６】
この動作をフローチャートにしたものが図１１である。
【００８７】
部分画像評価のループ１１０１において、その画像に含まれる部分画像全部がチェックされる。そして、上記の例のように例えば、部分画像中の対象物の占める面積が８０％以上となる部分画像のみ採用部分画像集合１１０２に加えられる。
【００８８】
一方、部分画像属性判定部１０９では、本実施形態でも実施形態１、実施形態２と同様に新規画像から抽出された任意の部分画像とのマッチングを行う。これは新規画像に含まれる対象物体が未知であるために、新規画像のどの位置を見るべきかは予め分かっていないからである。
【００８９】
また、実施形態１、実施形態２においては、登録画像と新規画像のサイズは同一として本実施形態を説明してきた。しかし、一般には新規画像は登録画像より大きい。このことを説明したのが、図１０の（ｂ）である。
【００９０】
例えば登録画像のサイズが１００×１００で、部分画像のサイズが２０×２０だとする。実施形態１と実施形態２では新規画像の大きさが登録画像と同じ１００×１００だったので、新規部分画像集合抽出部１０７で抽出される部分画像の数は６，５６１（＝８１×８１）枚となる。
【００９１】
これに対して本実施形態では、新規画像のサイズが２００×２００だとすると、新規部分画像集合抽出部１０７で抽出される部分画像の数は３２，７６１（＝１８１×１８１）枚となる。
【００９２】
登録画像全体を新規画像から切り出してマッチングする場合（いわゆるスライディングウィンドウによる登録画像のマッチング）を考える。登録画像のサイズが１００×１００、新規画像のサイズが２００×２００だとすると、１０，２０１（＝１０１×１０１）回マッチングを行うこととなる。これに対し上記の部分画像を用いた場合でも、マッチング回数は３倍強ほどしか増えない。よって、部分画像属性判定部１０９の処理が高速であれば（より正確には登録画像の枚数に比例して速度が低下しなければ）、本実施形態の登録部分画像を非常に多く用いた画像認識方法は十分実用に耐えうることとなる。
【００９３】
＜実施形態４＞
図１２および図１３を用いて実施形態４を説明する。実施形態４では、部分画像サイズ決定部１０１の具体的実装の例を示す。本実施形態では、いわゆるクロスバリデーションという手法を用いて部分画像のサイズを決定する。
【００９４】
図１の登録画像１０３を以下に述べる方法でサンプル登録画像群１３０１とサンプル新規画像群１３０２とに分ける。通常はランダムに２分割するが、登録画像１０３がＮ枚あるとして、その中の１枚をサンプル新規画像（群）とし、それ以外の画像をサンプル登録画像群とすることもできる。（これをｌｅａｖｅ  ｏｎｅ  ｏｕｔ法と呼ぶ。この場合、認識率の評価はサンプル新規画像をＮ回巡回していった認識率の値の平均で行い、認識率評価のループ１３０３は、｛Ｎ×（評価する部分画像のサイズの種類数）｝回の実行となる。）
まず、部分画像のサイズをあるサイズに仮に決定しておいてサンプル登録画像群１３０１を登録画像１０３として学習する。学習は学習部３０２で行う。次に、サンプル新規画像群１３０２の１枚１枚を新規画像１０６とし、画像認識をする。そして、新規画像群、全部から得られた認識結果１１２を集計することによって、部分画像が所定のサイズであった場合の認識率が求まる。
【００９５】
図１３は、サイズをいろいろ変えたときの認識率の違いをプロットしたグラフである。横軸が部分画像サイズで、縦軸がそのサイズで評価した平均認識率である。
【００９６】
この例でいうと、部分画像サイズが４０のところにピークがあるので、最高認識率決定ステップ１３０４で４０が選択され、最適部分画像サイズ１３０５が４０となる。本実施形態で重要なことは、実施形態１〜実施形態３で述べた画像認識方法を用いて部分画像サイズを評価することである。
【００９７】
＜実施形態５＞
図１４および図１５を用いて実施形態５を説明する。
【００９８】
実施形態４で述べたクロスバリデーションの方法は、認識性能の高い部分画像サイズを決定できるというメリットがある反面、非常に多くのコンピュータコストを必要とするというデメリットも存在する。本実施形態では、より簡便な部分画像サイズ決定部１０１の処理の例を述べる。
【００９９】
図１４は、図１の登録画像１０３の中から２枚の異なるクラスに属する登録画像を適当に選び、それらの部分画像群間の構造を解析したグラフである。（以下、クラスとは登録画像の種類を意味し、例えばクラスＡの画像がＡさんの顔画像、クラスＢの画像がＢさんの顔画像というようになる。）
図１４のグラフにおいて、横軸は部分画像のサイズで、縦軸は（クラス内平均距離／クラス間距離）である。クラス内平均距離とクラス間距離を図１５を用いて説明する。
【０１００】
図１５では、あたかも特徴空間が３次元のような書き方をしているが、これは便宜的に書いたもので、実際は非常に高次元である。より具体的には、部分画像のピクセルサイズ数の次元となる。また、以下“距離”という言葉で説明しているものは、ユークリッド距離を意味する。なお、本実施形態はユークリッド距離に限定したものではなく、任意の距離尺度を利用できる。
【０１０１】
例えば、登録画像１０３のサイズが１００×１００であるとする。そして、クラスＡとクラスＢの２つの画像があるとする。部分画像のサイズをフルサイズである１００×１００とすると登録部分画像の個数はそれぞれのクラスで１つずつとなり、図１５の右の空間配置となる。ここで空間の次元数は１０，０００（＝１００×１００）である。なお、以下の説明で図１５の○は１つの部分画像を意味する。クラスＡとクラスＢの配置は便宜上、左がＡで右がＢとして説明する。
【０１０２】
“クラス内平均距離”とは、クラスの平均部分画像とそれぞれの部分画像の距離の平均を意味し、この場合、部分画像が１つだけなので、クラスの平均部分画像は“登録画像そのもの”となり、クラス内平均距離は０となる。
【０１０３】
そして、“クラス間距離”とは、クラスの平均部分画像間（＝２つの登録画像間）の距離を意味し、図１５の右の場合、横向きの矢印の長さを指す。
【０１０４】
結局、図１４の縦軸である（クラス内平均距離／クラス間距離）は分子が０となるので０となる。
【０１０５】
なお、“クラス内平均距離”と“クラス間距離”を数式を用いて説明すると以下の通りとなる。
【０１０６】
部分画像のベクトルを
【０１０７】
【数５】
0005538967.tif 000006
【０１０８】
（ｉは部分画像のインデックス、ｘ、ｙは座標で、Ｉはその座標のピクセル値（実数））とする。
【０１０９】
すると、平均部分画像（ベクトル）
【０１１０】
【数６】
0005538967.tif 000007
【０１１１】
は
【０１１２】
【数７】
0005538967.tif 000008
【０１１３】
で定義される。（なおＮは部分画像の個数）
【０１１４】
そして、クラス内平均距離（スカラー）は
【０１１５】
【数８】
0005538967.tif 000009
【０１１６】
（ＸとＹはそれぞれ画像の横サイズと縦サイズ）となる。
【０１１７】
クラス間距離（スカラー）は
【０１１８】
【数９】
0005538967.tif 000010
【０１１９】
（Ａ、Ｂはクラス名）となる。
【０１２０】
次に図１４のグラフの指数がピークとなる部分画像サイズ３０の説明をする。部分画像のサイズが３０×３０となると、部分画像の個数はＡ、Ｂそれぞれ５，０４１（＝７１×７１）個となり、次元数は９００（＝３０×３０）となる。
【０１２１】
図１５の真ん中にある図がこの９００次元の空間で、それぞれの部分画像がどのように分布するかを示した図となる。なお、正確に記述すると、クラスＡ、クラスＢ、それぞれに関して○の数が部分画像の数（＝５，０４１）個あるはずであるが、書ききれないのでほとんどは省略してある。
【０１２２】
太い２本の矢印１６０１と１６０２が“クラス内平均距離”を意味し、具体的には上でも説明したように、“クラスの平均部分画像とそれぞれの部分画像の距離の平均”で定義される。なお指数で用いる“クラス内平均距離”はクラスＡのクラス内平均距離１６０１とクラスＢのクラス内平均距離１６０２の平均をとる。
【０１２３】
図１５の真ん中にある通り、部分画像の個数がある程度多いと、その分布が広がりクラス内平均距離が大きくなる。なお、図１５において、“クラスの広がりぐらい”は○で表される部分画像を囲む大きな楕円で表現している。
【０１２４】
そして、“クラス間距離”（横向きの矢印の長さ）は図１５の右の１００×１００の場合より小さくなるが、最終的な指数（クラス内平均距離／クラス間距離）は大きくなる。
【０１２５】
更に部分画像のサイズを小さく（５×５）とすると、図１５の左のような空間配置となる。ここで次元数は２５（＝５×５）で、部分画像の個数はクラスＡ、Ｂ、それぞれ９，２１６（＝９６×９６）個となる。
【０１２６】
“クラス間距離”は更に短くなるが、それ以上に“クラス内平均距離”が小さくなり、指数（クラス内平均距離／クラス間距離）は下がる。これは、部分画像の個数は増えるが、その分布範囲は相対的に、小さくなることを意味する。これは部分画像の分布に個性がなくなり、Ａの部分画像群もＢの部分画像群も区別が付きにくくなることに対応する。
【０１２７】
以上説明してきた（クラス内平均距離／クラス間距離）を用いた部分画像サイズ評価法は、いわゆるＦｉｓｈｅｒの分離関数と混同しやすい概念である。しかし、上記の指数は、ちょうどＦｉｓｈｅｒの分離関数とは逆の関係になる。つまり、Ｆｉｓｈｅｒの分離関数は、クラス内の分布範囲を出来るだけ小さくし、クラス間の分布範囲を出来るだけ大きくするようにすることになる。これに対して、本実施形態で説明してきた指数（クラス内平均距離／クラス間距離）は、クラス間の分布範囲を出来るだけ小さく、クラス間の分布範囲を出来るだけ大きくするような指数となる。
【０１２８】
これではＦｉｓｈｅｒの分離関数と全く逆の性質を見てしまうので、通常の感覚では、この指数が大きいと認識率が低くなるように感じる。しかし、本発明の部分画像を用いた画像認識方法では、この指数が大きいと部分画像の集合の形が十分意味のある構造（分布）を持つことを意味し、結果的に（経験的に）認識率が高くなるという現象が起こる。
【０１２９】
＜実施形態６＞
図１６〜図１９を用いて実施形態６を説明する。
【０１３０】
実施形態６では対象物体をいろいろな方向から撮影した画像を登録画像として学習し、入力された対象物体を含む画像の中から対象物体を検出する技術を実現する。本実施形態の学習ステップ（図４の３０２）は、基本的に実施形態２と同じである。つまり、図８のＮ枚の登録画像として、１つの対象物体をＮ姿勢方向から撮影した画像Ｎ枚を採用することになる。例えば、図１８（ｂ）に示したような画像となる。ここから複数の部分画像を抽出して登録部分画像とする。
【０１３１】
通常、このＮ姿勢方向はジオディシックドーム上の等間隔に配置された点から物体中心に向かう方向にカメラもしくは画像の面内回転を掛け合わせた姿勢方向となる。このように登録画像を準備することにより、入力画像中に対象物体がどのような姿勢で写っていてもそれを認識、検出することが可能となる。なお、機械学習でＮ枚の登録画像のマッチングを行うことはＮ個のクラス判別を行うことと等価となる。以下、Ｎ枚の登録画像とＮ個の姿勢クラスを同一視して説明する。
【０１３２】
なお、コンピュータグラフィックスの技術を用いて、例えばＣＡＤ画像から人工的に対象物体をいろいろな方向から撮影した画像を作り出してもよい。また、本実施形態の説明では対象物体を１つとしているが、対象物体が複数あっても本質は変わらない。
【０１３３】
姿勢クラスの数を増やせば増やすほど詳細に姿勢の判別が可能となる。つまり、姿勢について高い分解能を実現するためには、登録画像の枚数Ｎを十分多くする必要がある。しかしＮ＝２として説明してもその本質は変わらないので、以下では説明を簡単にするためにＮ＝２とする。対象物体は図１８（ｂ）に示すような直方体であり、２つ（＝Ｎ）の姿勢クラスは同じく図１８（ｂ）に示すような正面右向き、正面左向きの姿勢とする。また、高い物体認識、検出能力を実現するためには、部分画像の枚数（Ｍ）もある程度の量必要となる。しかし、Ｍ＝２として説明してもその本質は変わらないので、以下説明を簡単にするためにＭ＝２とする。具体的には、それぞれの姿勢クラスの登録部分画像は図１８（ｂ）に示すように、クラス１では１９１０、１９１１、クラス２では１９１３、１９１４とする。なお、図１８（ｂ）では、登録画像における対象物体の中心位置を、クラス１では１９１２、クラス２では１９１５で示している。
【０１３４】
次に物体を検出する工程を説明する。図１６は実施形態６における物体検出ルーチンのフローチャートを示した図である。物体検出工程では、まず新規に入力された画像でウィンドウをスライディングさせながら、ウィンドウ内にある部分画像を処理するルーチンが走る。このループがＳ１７０１からＳ１７０７までのループとなる。この様子は、実施形態３の説明で用いた図１０（ｂ）と同じ動作となる。
【０１３５】
例えば登録画像のサイズが１００ｘ１００で、部分画像のサイズが２０ｘ２０だとする。そして、新規画像のサイズが２００ｘ２００だとすると、Ｓ１７０２の部分画像の抽出ステップ（図２（ｂ）の新規部分画像集合抽出ステップＳ１０７と同じ）で抽出される部分画像の数は３２，７６１（＝１８１ｘ１８１）枚となる。なお、ステップＳ１７０１からＳ１７０７までのループで、この３２，７６１（＝１８１ｘ１８１）枚全てを処理せずに、その中から適当にサンプリングすることによって高速化を実現してもよい。
【０１３６】
このループの中で、まず部分画像の抽出を行い（Ｓ１７０２）、抽出された部分画像を入力としてＬ本の分類木判別器の判別結果を得る。このループがＳ１７０３からＳ１７０６までのループとなる。抽出された部分画像をそれぞれの分類木に認識処理させるステップはＳ１７０４であり、図１７にその詳細のフローチャートを示す。
【０１３７】
図１７で示したフローチャートは、分類木をルートノードからリーフノード、またはヌルノードへ向かって辿る工程を説明したものである。分類木における現在着目しているノードをカレントノードと定義する。まずルートノードをカレントノードとする（Ｓ１８０１）。次にカレントノードがヌルノードかリーフノードかの判定を行う（Ｓ１８０２）。そして、カレントノードがヌルノードかリーフノードであった場合は、このサブルーチンは終了する。
【０１３８】
なお、リーフノードが格納している情報は、“どの登録画像のどの位置の部分画像”という情報の集合であり、より具体的には“クラス番号と基準位置からのオフセット”群である。（オフセットの詳細な説明は図１８を用いて後述する。）
もしカレントノードがヌルノードかリーフノードのどちらでもない場合、カレントノードのクエリーに基づいて枝番号を計算する（Ｓ１８０３）。そして、計算された枝番号の子ノードをカレントノードに設定する（Ｓ１８０４）。なお、以上説明した工程は分類木を用いた認識工程に一般的、普遍的なものである。
【０１３９】
図１６に戻って、ｉ番目の判別器（分類木）の認識結果を用いて投票する（Ｓ１７０５）。この様子を図１８と図１９を用いて説明する。図１８（ａ）に示したのは投票の様子で、図１８（ｂ）に示したのが学習画像の様子である。登録画像、つまり、クラスの数が２であるので、図１８（ａ）に示した投票面（２次元のシート）の枚数は２枚となる。ここでいう投票面の具体的な中身は投票のスコアを加算する２次元のテーブルのことである。このテーブルで値の高い場所はそのクラスの物体が存在する可能性が高い場所を意味する。
【０１４０】
図１８（ａ）の図において点線で描かれた２つの直方体（１９０１）が表示されているが、これは入力された画像に２つの直方体が写っていたことを意味する。図１８（ａ）はあくまで投票面なので、点線で描画をすることで入力画像そのものではないことを表現した。（図１８（ａ）のクラス１、クラス２の２枚の投票面の同じ位置に１９０１が描かれていることに注意する。）
図１８（ａ）の１９０２は、部分画像枠をスライディングさせた時、つまり、図１６のステップＳ１７０１からＳ１７０７までのループを回した時の“ある一つ”の切り出された部分画像を意味する。部分画像１９０２を認識させた結果、クラス１の登録画像の部分画像１９１０（図１８（ｂ））とマッチしたとする。この結果、図１８（ｂ）の部分画像１９１０と部分画像１９１２のそれぞれの位置関係（中心位置へのオフセット）が読み出される（なお、この情報は図１７で説明したリーフノードに格納されている。）。そして、部分画像１９０２の位置からクラス１の投票面上の点１９０４の位置へ投票が行われる。
【０１４１】
同様に、部分画像１９０３の認識結果からも投票面上の点１９０４への投票が行われる。また、部分画像１９０５の認識結果からはクラス２の投票面上の点１９０７への投票が行われる。また、部分画像１９０６の認識結果からも１９０７への投票が行われる。
【０１４２】
以上説明してきたように、ステップＳ１７０５の投票面への投票とは“入力画像中の部分画像と似ている登録画像のクラス投票面の物体中心位置へ投票する”ことを意味する。
【０１４３】
図１８の説明では説明を簡単にするために物体中心の１点へ投票するような説明をしたが、普通は図１９に示したように広がった領域に分散して投票してもよい。例えば、図１９は底面がｘ、ｙの２次元（ｘ、ｙの２次元は投票面の縦横の２次元と同じ意味）で高さが投票の重みを意味する。式で表現すると、
【０１４４】
【数１０】
0005538967.tif 000011
【０１４５】
（ｄｘ，ｄｙは中心からの距離）という釣鐘型の関数を用いる。一般に釣鐘型の関数ならこの関数でなくてもよい。また、区間一様分布のような分布関数でもよい。
【０１４６】
なお、図１８では物体中心へ投票する方法を説明したが、必ずしも物体中心へ投票しなくてもよい。つまり、対象物体の３次元モデルに複数の基準位置を設定しておいて、その基準位置毎に図１８（ａ）で示したような投票面を用意してもよい。
【０１４７】
また、図１８で示した例は、１つの部分画像について１つの位置または領域への投票だったが、図１７で述べたリーフノードに格納された情報が複数クラスの複数位置の部分画像だった場合、それぞれのクラスの投票領域に投票することになる。
【０１４８】
図１８で説明した投票は、マッチしたクラスの投票面だけへの投票であった。つまり、部分画像１９０２と１９０３はクラス１の部分画像とマッチしたのでクラス１の投票面へ投票した。同じく部分画像１９０５と１９０６はクラス２の部分画像とマッチしたのでクラス２の投票面へ投票した。しかしながらクラス１とクラス２は全く異なるカテゴリではなく、同じ直方体（対象物体）の異なる姿勢という意味を持つ。よって、部分画像１９０２、１９０３の認識結果からクラス２の投票面上の点１９０９への投票をしても良い。同様に部分画像１９０５、１９０６の認識結果からクラス１の投票面上の点１９０８への投票をしても良い。
【０１４９】
このことをより一般的に説明すると、クラスがＮ個あるとして、その全てのペアの類似度、または、距離を予め計算しておく。そして、例えば距離がある閾値以下の類似するクラスの投票面へ距離に応じた大きさで投票をする。ここで距離に応じた投票とは、例えばクラス間の距離をＤとすると、Ｅｘｐ（−Ｄ）で示すような係数をかけた投票をする。（同一クラス間の距離は０だとすると、この係数は１となることに注意。）なお、通常は姿勢クラス間の距離はロドリゲスローテーションの回転角で求めるが、特にこれに限定しなくてもよい。
【０１５０】
図１６のステップＳ１７０１からＳ１７０７までのループが終了した時点で、図１８（ａ）に示したそれぞれの投票面への投票が終了し、それぞれの投票面の強度分布が求まる。結局、それぞれのクラスつまり姿勢方向における対象物体が存在する分布が求まることになる。この情報から部品の姿勢方向と位置を確定するのであるが、その１つの例を以下に述べる。
【０１５１】
Ｓ１７０８からＳ１７１０までのループでそれぞれのクラスの投票面においてピークとなる位置を算出する（Ｓ１７０９）。結果、Ｎ個の姿勢クラスそれぞれが存在する可能性の最も高い場所とそのスコアが求められることになる。具体的には図１８の場合、クラス１の投票面では１９０４の点がピークとして選ばれ、クラス２の投票面では１９０７の点がピークとして選ばれる。
【０１５２】
そして、Ｎ個の姿勢クラスの結果をソートすることによって投票結果の集計を行う（Ｓ１７１１）。この集計結果によって入力画像中で存在可能性が高い姿勢方向の物体とその位置が識別できる。具体的には図１８の場合、点１９０４の値が点１９０７の値より大きかったとすると、識別結果の第１候補が姿勢クラス１で位置が１９０４、第２候補が姿勢クラス２で位置が１９０７となる。
【０１５３】
なお、図１６で説明した方法は集計方法の１つの例であって、対象物体の姿勢方向、および位置が識別できればどのような処理を行ってもよい。例えば、それぞれのクラスの投票面の局所的なピークを複数算出し、それを集計しても良い。例えば、図１８の場合、点１９０４、点１９０７の他に、点１９０８、点１９０９の点を候補点に含めて集計してもよい。その結果、例えば、得点の高い順に１９０４、１９０８、１９０７、１９０９となったとする。すると、姿勢クラス１の物体が１９０４と１９０８の２つの位置に検出されることになる。
【０１５４】
以上、実施形態を詳述したが、本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体等としての実施態様をとることが可能である。具体的には、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【０１５５】
尚、本発明は、ソフトウェアのプログラムをシステム或いは装置に直接或いは遠隔から供給し、そのシステム或いは装置のコンピュータが該供給されたプログラムコードを読み出して実行することによって前述した実施形態の機能が達成される場合を含む。この場合、供給されるプログラムは実施形態で図示したフローチャートに対応したコンピュータ読み取り可能なプログラムである。
【０１５６】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される他、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどとの協働で実施形態の機能が実現されてもよい。この場合、ＯＳなどが、実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される。
【符号の説明】
【０１５７】
１０１  部分画像サイズ決定部
１０２  部分画像サイズ
１０３  登録画像
１０４  登録部分画像集合抽出部
１０５  登録部分画像集合
１０６  新規画像
１０７  新規部分画像集合抽出部
１０８  新規部分画像集合
１０９  部分画像属性判定部
１１０  部分画像判定結果
１１１  部分画像判定結果集計部
１１２  認識結果
１１３  辞書作成部
１１４  辞書
【図１】
0005538967.tif 000012
【図２】
0005538967.tif 000013
【図３】
0005538967.tif 000014
【図４】
0005538967.tif 000015
【図５】
0005538967.tif 000016
【図６】
0005538967.tif 000017
【図７】
0005538967.tif 000018
【図８】
0005538967.tif 000019
【図９】
0005538967.tif 000020
【図１０】
0005538967.tif 000021
【図１１】
0005538967.tif 000022
【図１２】
0005538967.tif 000023
【図１３】
0005538967.tif 000024
【図１４】
0005538967.tif 000025
【図１５】
0005538967.tif 000026
【図１６】
0005538967.tif 000027
【図１７】
0005538967.tif 000028
【図１８】
0005538967.tif 000029
【図１９】
0005538967.tif 000030