"三次元の物体を異なる視点から見た複数の画像が入力されたとき、各画像の局所的特徴を抽出し特徴ベクトルとしてそれぞれ表す工程と、特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数の部分空間を部分空間法により生成する部分空間生成工程と、各部分空間に前記物体の識別子を関連づけて三次元物体認識用データベースに登録する登録工程とを備え、前記データベースは、三次元物体の認識処理のため、コンピュータによりアクセスされ、前記認識処理は、ある物体をある視点から見た一つの画像または一連の視点から見た複数の画像が検索質問として与えられたとき、その検索質問の局所的特徴をそれぞれ表す複数の特徴ベクトルをクエリ特徴ベクトルとして抽出し、各クエリ特徴ベクトルに最も類似する部分空間をそれぞれ決定し、各部分空間に関連づけられた物体IDについて集計処理を行い、前記検索質問に最も類似する物体を得る工程により実現される三次元物体認識用画像データベースの作成方法。前記登録工程は、前記物体の識別子および前記一連の視点を表す視点データの組み合わせを各部分空間に関連づけて登録し、前記認識処理は、各部分空間に関連づけられた前記組み合わせについて集計処理を行い、前記検索質問に最も類似する物体および最も類似する視点を得る工程である請求項1に記載の方法。前記部分空間生成工程は、隣り合う視点に対応する各対の特徴ベクトルの距離を計算し、異なる対との距離が予め定められた基準を超えて相違するものをノイズとして除外し、残った特徴ベクトルを同一箇所を表す特徴ベクトルの集合とする請求項1または2に記載の方法。前記部分空間生成工程は、各集合の特徴ベクトルが予め定められた視点の変化量より広範囲に渡る場合は部分空間を生成するが、前記変化量に満たない場合は部分空間を生成しない請求項1~3のいずれか一つに記載の方法。前記部分空間生成工程は、各対のうち、最も近い距離の対と2番目に近い距離の対との相違が前記基準を超えるものをノイズとして除外する請求項4に記載の方法。前記認識処理は、各クエリ特徴ベクトルを前記データベースに予め登録された各部分空間の座標系を定める基底にそれぞれ射影して射影成分の大きさに基づき各クエリ特徴ベクトルと各部分空間との類似度を算出し、最も高い類似度の部分空間を、そのクエリ特徴ベクトルに最も類似する部分空間であると決定する請求項1~5のいずれか一つに記載の方法。前記認識処理は、各部分空間が特性を表す特徴ベクトルの集合において最大の固有値に係る第一主成分の基底を各部分空間についてそれぞれ決定し、第一主成分の各基底上において原点からの正規化された距離が等しい位置にそれぞれ点をおき、各点と各クエリ特徴ベクトルとの距離を近似最近傍探索の手法を適用して求め、最も近い距離の部分空間を、そのクエリ特徴ベクトルに最も類似する部分空間であると決定する請求項1~5のいずれか一つに記載の方法。前記認識処理は、請求項7に記載の方法により各クエリ特徴ベクトルに類似する部分空間を幾つかの候補に絞り込んだ後、候補とされた各部分空間の各基底にそのクエリ特徴ベクトルをそれぞれ射影して射影成分の大きさに基づき各クエリ特徴ベクトルと各部分空間との類似度を算出し、最も高い類似度の部分空間を、そのクエリ特徴ベクトルに最も類似する部分空間であると決定する三次元物体認識用画像データベースの作成方法。前記認識処理は、各クエリ特徴ベクトルに最も類似する部分空間を決定する処理に代えて、1一連の視点から見た複数の画像が検索質問として与えられたとき、その検索質問に係るクエリ特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数のクエリ部分空間を部分空間法により生成し、2各クエリ部分空間の座標系を定める各基底上において原点からの正規化された距離が所定の位置にそれぞれクエリ基準点をおき、前記データベースに登録された各部分空間の各基底上において原点からの正規化された距離が前記所定の位置にそれぞれ基準点をおき、3各クエリ基準点から最短距離の基準点を有する部分空間を各近似最近傍探索の手法を用いて決定することにより、各クエリ部分空間に最も類似する部分空間を決定する請求項1~5の何れか一つに記載の方法。前記視点データは、前記物体の撮影角度のデータである請求項1~9のいずれか一つに記載の方法。前記部分空間生成工程は、CLAFIC法を適用して特徴ベクトルを集合としてまとめ、部分空間を生成する請求項1~10のいずれか一つに記載の方法。部分空間の次元数は、1以上3以下である請求項1~6のいずれか一つに記載の方法。三次元の物体を異なる視点から見た複数の画像が入力されたとき、各画像の局所的特徴を抽出し特徴ベクトルとしてそれぞれ表す抽出部と、特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数の部分空間を部分空間法により生成する部分空間生成部と、各部分空間に前記物体の識別子を関連づけて三次元物体認識用データベースに登録する登録部とを備え、前記データベースは、三次元物体の認識装置によりアクセスされ、前記認識装置は、ある物体をある視点から見た一つの画像または一連の視点から見た複数の画像が検索質問として与えられたとき、その検索質問の局所的特徴をそれぞれ表す複数の特徴ベクトルをクエリ特徴ベクトルとして抽出し、各クエリ特徴ベクトルに最も類似する部分空間をそれぞれ決定し、各部分空間に関連づけられた物体IDについての集計処理を各クエリ特徴ベクトルについて行い、前記検索質問に最も類似する物体を得る機能を有する三次元物体認識用画像データベースの作成装置。しかし、局所特徴量の格納に要するメモリ容量を節約しようとして無作為に局所特徴量の取捨選択を行うと、物体の認識率が低下する可能性がある。認識率を低下させることなく効率良くメモリ容量を削減するためには、認識に有用な局所特徴量のみを保存する必要がある。そこで発明者らは、連続して変化する画像の集合から、ある程度一貫して得られる局所領域に注目し、そのような部分から得られる局所特徴量のみを用いることを新たに考えた。そのような局所特徴量のみをデータベースに登録すれば、物体認識の精度をあまり低下させずにメモリ容量を削減することができるはずである。さらに、メモリ容量の削減効果を高めるため、物体の同じ部分から得られる局所特徴量を一つにまとめてデータベースに登録することを考えた。具体的には、CLAFIC法例えば、石井健一郎、前田英作、上田修功、村瀬洋著、わかりやすいパターン認識、オーム社、1998年8月、p147151、あるいは、EOjaSubspacemethodsofpatternrecognitionResearchStudiesPressを参照。また、下の実施の形態でも説明を述べている。として知られる技術を適用してそれらの局所特徴量の集合ごとに部分空間を作成する。それによって複数の局所特徴量を一つにまとめて表現することができる。この発明は、以上のような事情を考慮してなされたものであって、三次元物体認識用画像データベースに登録する局所特徴量の取捨選択を行ってメモリ容量を削減しつつ、前記取捨選択の代償として生じる認識率の低下を無削減の状態と遜色ない程度に抑制できる手法を提供するものである。この発明は、三次元の物体を異なる視点から見た複数の画像が入力されたとき、各画像の局所的特徴を抽出し特徴ベクトルとしてそれぞれ表す工程と、特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数の部分空間を部分空間法により生成する部分空間生成工程と、各部分空間に前記物体の識別子を関連づけて三次元物体認識用データベースに登録する登録工程とを備え、前記データベースは、三次元物体の認識処理のため、コンピュータによりアクセスされ、前記認識処理は、ある物体をある視点から見た画像が検索質問、即ち、クエリとして与えられたとき、その検索質問の局所的特徴をそれぞれ表す複数の特徴ベクトルをクエリ特徴ベクトルとして抽出し、各クエリ特徴ベクトルに最も類似する部分空間をそれぞれ決定し、各部分空間に関連づけられた物体IDについて集計処理を行い、前記検索質問に最も類似する物体を得る工程により実現される三次元物体認識用画像データベースの作成方法を提供する。また、異なる観点から、この発明は、三次元の物体を異なる視点から見た複数の画像が入力されたとき、各画像の局所的特徴を抽出し特徴ベクトルとしてそれぞれ表す抽出部と、特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数の部分空間を部分空間法により生成する部分空間生成部と、各部分空間に前記物体の識別子を関連づけて三次元物体認識用データベースに登録する登録部とを備え、前記データベースは、三次元物体の認識装置によりアクセスされ、前記認識装置は、ある物体をある視点から見た画像が検索質問として与えられたとき、その検索質問の局所的特徴をそれぞれ表す複数の特徴ベクトルをクエリ特徴ベクトルとして抽出し、各クエリ特徴ベクトルに最も類似する部分空間をそれぞれ決定し、各部分空間に関連づけられた物体IDについての集計処理を各クエリ特徴ベクトルについて行い、前記検索質問に最も類似する物体を得る機能を有する三次元物体認識用画像データベースの作成装置を提供する。この発明による三次元物体認識用画像データベースの作成方法は、特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数の部分空間を部分空間法により生成する部分空間生成工程と、各部分空間に前記物体の識別子を関連づけて三次元物体認識用データベースに登録する登録工程とを備えるので、連続した視点の変化に対して前記物体の同一箇所を表す特徴ベクトルを一つにまとめて近似的な部分空間に変換し、各特徴ベクトルに代えて前記部分空間をデータベースに登録することでメモリ容量を削減しつつその代償として生じる認識率の低下を、各特徴ベクトルをそのまま登録するときと比べてあまり低下しない程度に抑制できる。効果検証の実験によれば、各特徴ベクトルをそのまま登録する無削減状態に対して983の認識率を維持する一方、メモリ容量は無削減状態の約118にすることができた。前記方法と実質的に対応する、この発明の三次元物体認識用画像データベースの作成装置についても、同様の作用効果を奏する。なお、この発明の三次元物体認識用画像データベースの作成方法において、データベース作成の各工程はコンピュータにより実行されるが、そのコンピュータと認識処理を実行するコンピュータとは同一であってもよいが、異なるものであってもよい。ここでいうコンピュータは、単一のものであってもよいが、いわゆるクラウドコンピューティングのように物理的に複数の装置が一つのコンピュータとしての機能を実現する態様も含む。三次元物体は、二次元平面的な物体と異なり、視点撮影角度の変化に伴ってある部分が見え隠れする物体である。部分空間は周知の部分空間法を適用して生成可能である。この発明の特徴的な一側面は、一連の視点から見た同一物体の同一箇所の特徴ベクトルを部分空間法により一つにまとめ、データベースのメモリ容量を節約する点にある。他の特徴的な一側面は、一つにまとめられた特徴ベクトルの集合としての部分空間に一連の視点を表す視点データを付加する点にある。視点データの具体的な一態様は、撮影角度である。後述する実施形態において、撮影角度は、三次元物体をターンテーブルで一回転させて異なる方向からその物体を撮影したときのターンテーブルの回転角度に相当する。以下、この発明の好ましい態様について説明する。この発明による三次元物体認識用画像データベースの作成方法において、前記登録工程は、前記物体の識別子および前記一連の視点を表す視点データの組み合わせを各部分空間に関連づけて登録し、前記認識処理は、各部分空間に関連づけられた前記組み合わせについて集計処理を行い、前記検索質問に最も類似する物体および最も類似する視点を得る工程であってもよい。このようにすれば、物体IDおよび視点データの組み合わせについての集計処理を各クエリ特徴ベクトルについて行うので、メモリ容量削減の代償として生じる認識率の低下を、各特徴ベクトルをそのまま登録するときと比べて遜色のない程度に抑制できる。後述する効果検証の実験によれば、各特徴ベクトルをそのまま登録する無削減状態に対して989の認識率を維持する一方、メモリ容量は無削減状態の約118にすることができた。また、このようにすれば、質問画像の物体の種類を認識するだけでなく、検索質問のおおよその視点を推定することができる。また、前記部分空間生成工程は、隣り合う視点に対応する各対の特徴ベクトルの距離を計算し、異なる対との距離が予め定められた基準を超えて相違するものをノイズとして除外し、残った特徴ベクトルを同一箇所を表す特徴ベクトルの集合としてもよい。このようにすれば、隣り合う視点の各特徴ベクトルの距離計算を行うことにより同一箇所を表す特徴ベクトルの集合を得ることができ、かつ、ノイズを除外し安定した取得が可能になる。前記部分空間生成工程は、各集合の特徴ベクトルが予め定められた視点の変化量より広範囲に渡る場合は部分空間を生成するが、前記変化量に満たない場合は部分空間を生成しないように構成してもよい。このようにすれば、広範な視点変化に渡って同一箇所を表す特徴ベクトルがデータベースに登録されるので、撮影角度の変化によって生じたノイズは登録対象から除去され、安定した精度の高い認識が可能になる。前記部分空間生成工程は、各対のうち、最も近い距離の対と2番目に近い距離の対との相違が前記基準を超えるものをノイズとして除外してもよい。さらにまた、前記認識処理は、各クエリ特徴ベクトルを前記データベースに予め登録された各部分空間の座標系を定める基底にそれぞれ射影して射影成分の大きさに基づき各クエリ特徴ベクトルと各部分空間との類似度を算出し、最も高い類似度の部分空間を、そのクエリ特徴ベクトルに最も類似する部分空間であると決定してもよい。このようにすれば、各部分空間の各基底への射影成分の大きさに基づいて、類似度を算出することができる。前記認識処理は、各部分空間が特性を表す特徴ベクトルの集合において最大の固有値に係る第一主成分の基底を各部分空間についてそれぞれ決定し、第一主成分の各基底上において原点からの正規化された距離が等しい位置にそれぞれ点をおき、各点と各クエリ特徴ベクトルとの距離を近似最近傍探索の手法を適用して求め、最も近い距離の部分空間を、そのクエリ特徴ベクトルに最も類似する部分空間であると決定してもよい。このようにすれば、類似度の計算を距離計算として処理し、その距離計算に近似最近傍探索の手法を適用することによって、各基底への射影を行う手法に比べて類似度の計算にかかる処理時間を短縮することができる。さらに、前述の方法により各クエリ特徴ベクトルに類似する部分空間を幾つかの候補に絞り込んだ後、候補とされた各部分空間の各基底にそのクエリ特徴ベクトルをそれぞれ射影して射影成分の大きさに基づき各クエリ特徴ベクトルと各部分空間との類似度を算出し、最も高い類似度の部分空間を、そのクエリ特徴ベクトルに最も類似する部分空間であると決定してもよい。このようにすれば、各部分空間の第一主成分のみを用いる場合に比べて高い認識率を見込むことができる。一方、各部分空間の各基底に各特徴ベクトルを射影して類似度を求める場合に比べて、類似度計算の対象候補を絞り込むので、処理時間を削減することができる。前記認識処理は、各クエリ特徴ベクトルに最も類似する部分空間を決定する処理に代えて、1一連の視点から見た複数の画像が検索質問として与えられたとき、その検索質問に係るクエリ特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数のクエリ部分空間を部分空間法により生成し、2各クエリ部分空間の座標系を定める各基底上において原点からの正規化された距離が所定の位置にそれぞれクエリ基準点をおき、前記データベースに登録された各部分空間の各基底上において原点からの正規化された距離が前記所定の位置にそれぞれ基準点をおき、3各クエリ基準点から最短距離の基準点を有する部分空間を各近似最近傍探索の手法を適用して決定することにより、各クエリ部分空間に最も類似する部分空間を決定してもよい。このようにすれば、近似最近傍探索の手法を適用した距離計算によって各クエリ部分空間に最も類似する部分空間を決定することができるので、近似最近傍探索の手法を用いない場合に比べて処理時間を短縮でき、かつ、各クエリ特徴ベクトルに対して最も類似する部分空間を決定する場合に比べて、クエリ部分空間との比較を行うので高い認識率を見込むことができる。前記視点データは、前記物体の撮影角度のデータであってもよい。このようにすれば、前記視点データとして撮影角度を用い、かつ、撮影角度の変化量に対して連続して同一箇所のベクトルが集合に含まれることをノイズ除去の条件として部分空間を生成することができる。前記部分空間生成工程は、CLAFIC法を適用して特徴ベクトルを集合としてまとめ、部分空間を生成してもよい。部分空間の次元数は、1以上3以下であってもよい。実施例で用いたSIFT特徴量は128次元のベクトルであるが、部分空間に変換することによってその次元数を減らすことができる。しかし、認識率低下とのトレードオフが生じると予想されるため、どこまで次元数が減らせるかは、両者のバランスを考慮して決定しなければならない。ところが、後述する検証実験によれば、発明者にとっても意外なことに、視点データを付加する態様において部分空間の次元数が三次元のときもメモリ無削減状態に対して989の認識率が維持された。そして、次元数をそれ以上増やしても989以上の認識率を得ることはなかった。また、究極の一次元まで次元数を減らしても、無削減状態に対して980の認識率が維持されたのである図6および表1参照。視点データを付加しない態様であっても、部分空間の次元数が三次元のときに極大値の983の認識率が得られ、一次元まで次元数を減らしても958の認識率が維持された。ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。≪関連技術の説明≫発明をよりよく理解できるようにするため、まず、この発明の基礎となる技術について簡単に説明する。1.局所特徴量を用いた三次元物体認識画像から得ることができる特徴量には、大きく分けて大域特徴量と局所特徴量の2つがある。前者は、画像の画素値などを用いて1枚の画像全体を特徴量とするもので、比較的容易に得ることができる。しかし、質問画像に物体の一部しか写っていない場合や一部が隠れている場合など、データベースの画像と質問画像の画素値が全く異なると、特徴量の値も大きく変動するという問題が生じ、物体の認識が困難になる。一方、後者の局所特徴量は画像から特徴的な局所領域を取り出し、その局所領域をベクトルで記述したものである。このように局所特徴量はベクトルとして記述されるので、特徴ベクトルともいう。1枚の画像の様々な個所から計数百個から数千個ほど得られるため、大域特徴量がもつ問題に対処する方法として、有効であることが知られている。ここでは、局所特徴量の代表的なものの一つであるSIFT特徴量例えば、DLoweDistinctiveimagefeaturesfromscaleinvariantkeypointsInternationalJournalofComputerVision602pp91110参照と、局所特徴量を用いた三次元物体認識の基本的な手法前記非特許文献4参照について簡単に説明する。1-1.SIFTScaleInvariantFeatureTransform特徴量Loweらによって提案されたSIFT特徴量は、画像内の輝度の勾配を利用することで局所領域を取得し、その座標、方向、大きさなどを特徴ベクトルで表したものである。SIFT特徴量は、128次元のベクトルで表され、相似変換や回転などの変換に対して頑健である。図1は、従来の局所特徴量であるSIFT特徴量をある物体について異なる二つの視点から見た画像データからそれぞれ抽出した様子を示す説明図である。図1aとbは、同一の物体を異なる撮影角度で撮影したものである。図中に白い矢印で表したものが、SIFT特徴量である。図2は、従来の局所特徴量であるSIFT特徴量を図1と異なる物体について異なる二つの視点から見た画像データからそれぞれ抽出した様子を示す説明図である。1-2.三次元物体の認識手法三次元物体の物体認識手法について簡単に説明する。まず、データベースへの登録について述べる。データベースに登録したい物体を様々な視点撮影角度から撮影した画像がユーザーによって用意されているとする。登録処理として、コンピュータは、登録すべき物体が撮影された各画像からSIFT特徴量を抽出する。抽出されたSIFT特徴量を、前記物体に固有の識別子物体IDとともにデータベースに登録する。物体IDは、データベースに登録された各物体を識別するためのものである。次に、認識処理について説明する。検索質問としての物体がある視点から撮影され、撮影された画像が与えられたとする。認識処理は、与えられた検索質問画像と同一の物体が前記データベースに登録されているかをコンピュータが検索し、同一物体があればその物体IDを特定するものである。認識処理の手順は次のとおりである。前述の登録処理と同様に、質問画像からもSIFT特徴量を抽出する。抽出された各SIFT特徴量とデータベースに登録された各SIFT特徴量との距離計算を行う。そして、質問画像のSIFT特徴量に対して最も小さい距離にあるSIFT特徴量、即ち、最近傍のSIFT特徴量を見出す。最近傍のSIFT特徴量が属する物体の物体IDに対して投票を行う。質問画像の他のSIFT特徴量についてもいずれかの物体IDに対しそれぞれ投票を行う。投票処理の結果、最多得票を得た物体IDをその検索質問に対する認識結果とする。2.CLAFIC法-局所特徴量の分類CLAFIC法は、1969年にWatanabeが提案した部分空間法の一種であり、クラスごとにKL展開KarhunenLoeve展開の略であり、ベクトルの分布を最もよく近似する部分空間を求める手法により作成した部分空間を用いてクラス分類を行う手法である。この発明では、ある物体について異なる撮影角度の複数の画像から抽出される同一部分の局所特徴量を、CLAFIC法を用いて同一クラスにまとめることを考える。局所特徴量のクラスタリングである。一般に、CLAFIC法により部分空間を作成するにはまず、クラスごとに多数のサンプルベクトルxを用意し、それらの自己相関行列Qを以下の式、によって計算する。そして、λiをQの固有値、uiをそれに対する固有ベクトルとするとき、の固有値問題を解くことで固有ベクトルを求める。元のサンプルベクトルxがn個あるとすると、一般にn個の固有ベクトルが求まる。そのn個の固有ベクトルのうち、いくつかの固有ベクトルによって張られる空間を部分空間という。求めたい部分空間の次元数をkとすると、上位k個の大きな固有値に対応する固有ベクトルを基底座標系とする空間が、求めたい部分空間である。あるサンプルベクトルxの基底uiに係る固有値は、サンプルベクトルxを基底uiに正射影したときの長さ射影成分に相当する。基底u1は、クラス全体として最大の固有値に対応する基底であって、この明細書において第一主成分と呼ぶ。この部分空間をクラスごとに作成し、未知パターンのベクトルxとの類似度Dを計算することで、未知パターンのクラスを識別することができる。未知パターンのベクトルxは、最大の射影成分を持つ部分空間のクラスに識別されることになる。類似度Dは、より求めることができる。≪この発明の説明≫三次元物体の認識手法で述べたように、SIFT特徴量を用いた物体認識の従来手法によれば、高精度な認識結果を得るために、様々な視点撮影角度から撮影した画像から得た局所特徴量特徴ベクトルをそのままデータベースに登録する。そのため、メモリ容量が莫大なものになってしまう。そこでこの発明では、一連の視点の画像データから得られる同一部分の局所特徴量を、部分空間を用いて一つにまとめ、まとめられたものをデータベースに登録することによってメモリ容量を削減することを考える。また、部分空間に撮影角度の情報を対応づけておくことで、物体認識と併せて検索質問のおおよその撮影角度を得る。1.局所特徴量の選定局所特徴量の格納に要するメモリ容量が莫大になるという問題の解決策として、データベースに登録する局所特徴量の数の削減を考える。しかし、局所特徴量を無作為に削減すると、認識率が大きく低下するおそれがある。そこで、同一の物体を示しかつ撮影角度が連続して変化する複数の画像データから抽出される、ある程度一貫性のある局所領域に注目し、そのような局所領域から得られる局所特徴量のみを物体認識に用いることを考える。なぜなら、撮影角度の変化に対してある程度一貫した局所特徴量が得られなければ、その局所特徴量は撮影角度の変化によって生じたノイズの可能性が高いからである。撮影角度が連続して変化する複数の画像データにおいて、物体の同じ部分から得られた局所特徴量は少しずつ変化する。そのような局所特徴量の変化を近似的に精度よく記述することができる部分空間を作成することで、複数の局所特徴量を一つにまとめて表現するのである。撮影角度が連続して変化する複数の画像データから、物体の同じ部分から得た局所特徴量を見つけ出す処理は以下のようになる。まず、撮影角度がわずかに異なる2枚の画像データにおいて、1フレーム目の画像データの各局所特徴量と2フレーム目の画像データの各局所特徴量との距離計算を行う。そして、それぞれ一番距離が近い局所特徴量を見つけることで、1フレーム目画像と2フレーム目画像の局所特徴量の対応づけを行う。このとき、ノイズなどの影響により、最近傍となった局所特徴量が、本当はあまり関連のない部分から得られたものであることがある。そこで、一番近い局所特徴量との距離をd1、二番目に近い局所特徴量との距離をd2とし、閾値をαとすると、を満たす局所特徴量の組のみを、物体の同じ部分から得られたものであるとする。これを満たさない局所特徴量はノイズであると考える。これを連続するすべての画像データ間で行い、局所特徴量の軌跡を得る。以下、このような処理をトレース処理とよぶ。前記軌跡は特徴ベクトルの集合ともいえる。なお、一番近い局所特徴量と二番目に近い局所特徴量との距離の差異を閾値と比較してノイズを除去する手法を述べたが、その変形例として、画像中の近い箇所から抽出された局所特徴量の距離の差異を閾値と比較してノイズを除去する手法が考えられる。図3は、この発明に係るトレース処理の様子を模式的に表す説明図である。1フレーム目、2フレーム目等の矩形枠は異なる視点から物体を撮影した各画像を示す。a,bおよびcは前記物体の同一箇所を表す特徴ベクトルが異なる撮影角度視点の画像に連続して出現する軌跡を表す。例えば、特徴ベクトル集合aは1フレーム目に属する特徴ベクトルα1から2フレーム目に属する特徴ベクトルα2に対応づき、2フレーム目の特徴ベクトルα2は3フレーム目のどの特徴ベクトルにも対応づかなかったことを表している。また、特徴ベクトル集合bは1フレーム目から5フレーム目までの各視点に特徴ベクトルが連続して対応づいた様子を表している。特徴ベクトル集合cは、3フレーム目から5フレーム目までの各視点に特徴ベクトルが連続して対応づいた様子を表している。2.部分空間の作成登録処理この発明に係る登録処理においてコンピュータは、トレース処理によって得られた局所特徴量の集合を、その集合の部分空間を作成することで一つにまとめる。そして、その部分空間を物体IDとともに登録する。このとき、図3の軌跡aのように、軌跡が短い局所特徴量の集合からも部分空間を作成しデータベースに登録すると、登録する部分空間の数が多くなり、メモリ容量の削減があまりなされない。そこで、軌跡の長さに閾値を設け、ある程度以上連続して対応づけられた局所特徴量の集合のみから部分空間を作成し、データベースに登録する。これは、局所特徴量の軌跡が短いものは、軌跡が長いものに比べて、識別できる撮影範囲が少ないためである。この発明により作成される部分空間は、具体的にはk次元の基底座標系を定めるk個の方向ベクトルで構成される。各軌跡はCLAFIC法の説明で述べたクラスに相当する。クラスごとのサンプルベクトルxは、各軌跡に属する局所特徴量に相当する。CLAFIC法により局所特徴量の自己相関行列を求め、その固有ベクトルを前記基底とする部分空間を張る。データベースには、この部分空間を成すk個の固有ベクトルを登録すればよい。登録された固有ベクトルは、その部分空間に属する各局所特徴量を近似的に表す。部分空間の次元数kが小さいほどメモリ容量は削減することができる。SIFT特徴量は128次元のベクトルで表現されるので、その部分空間の次元数kは1以上128未満のいずれかの次元数をとる。後述する実験例では、各部分空間の次元数kを一律に定めた。即ち、図6に示すようにk1から8の8通りの場合をそれぞれ定め、それぞれの場合について実験している。しかし、次元数kの値は、部分空間ごとに適応的に決めてもよい。先に述べたように、登録処理では、局所特徴量そのものではなく、局所特徴量の集合を一つにまとめた部分空間を物体IDとともにデータベースに登録する。このとき、登録する部分空間が、どの視点からどの視点までの局所特徴量の変化を表現しているかといった、その部分空間の撮影角度の範囲も併せて登録する。認識処理の際に撮影角度の情報を用いることで、認識率の向上と質問画像がどの視点から撮影されたものであるかという大まかなパラメータの検出が可能となる。よって、登録処理は、部分空間を物体IDおよび撮影角度の範囲と関連付けて登録するものである。3.認識処理この発明に係る認識処理において、コンピュータは、検索質問の画像が与えられたとき、その検索質問画像から局所特徴量を抽出し、各局所特徴量をデータベース中の各部分空間に射影し、局所特徴量と部分空間の類似度を計算する。そして最も類似度の高い部分空間を求め、その部分空間をもつ物体IDに投票処理を行う。これをすべての局所特徴量において行う。最終的に、最多得票数を得た物体IDを物体認識の結果として出力する。この際、物体によって部分空間の数が異なるため、得票数を部分空間の数で正規化する。正規化を行わなければ、部分空間の数が多い物体IDに多数の得票が集まってしまい、誤認識を起こす可能性がある。物体のある撮影角度ωを識別することができる部分空間の数をNωとし、撮影角度ωの得票数をGωとすると、によって、得票数の正規化を行う。図4は、この発明に係る投票処理の様子を示す説明図である。例えば、質問画像から得られたある5つの局所特徴量とそれぞれ最も類似度の高い部分空間を求めたところ、図4の左のような物体IDと撮影範囲をもつ5つの部分空間が得られたとする。このとき、この発明の一態様に従い、もし単に物体IDごとの投票を行うとすると、図4ののようになる。ところが、ある2つの局所特徴量が同じ物体IDをもつ部分空間に対応づいたとしても、視点の範囲が全く異なれば、それらは異なるものを示しているといえる。そこでこの発明の異なる態様においては、図4ののように物体の撮影角度を考慮して投票を行う。具体的には、最も類似度の高い部分空間を求め、投票する際、その部分空間を作成した物体IDと、その部分空間を構成する局所特徴量が得られた物体の撮影角度との組み合わせに対して投票を行う。図4では、検索質問から5つの部分空間が抽出された例を示している。図4のは、単に物体IDに対してのみ投票をおこった場合の投票結果を示している。図4のの投票結果によれば、物体1と物体2が同数で最多の得票を得るためにどちらを認識結果とすればよいか判断できない。一方、図4のは、物体IDと撮影角度の組み合わせに対して投票を行った場合の投票結果を示している。図4のの投票結果によれば、物体1のうち撮影角度が20度から40度の範囲が最多得票を得るので、物体1を認識結果とすることができる。さらに、撮影角度20度から40度を質問画像のおおよその撮影角度として推定できるという利点もある。≪処理の流れ≫図13は、この発明に係る三次元物体認識の処理の流れを示す説明図である。図13に示すように、三次元物体認識の処理は、登録処理と認識処理に大別される。登録処理は、認識に用いる三次元物体の画像のデータベースを作成する処理である。認識処理は、検索質問として三次元物体の画像が与えられたとき、その画像に示された物体の画像を前記データベースの中から検索し、物体を特定する処理である。図13で、aは登録処理の流れを示し、bは認識処理の流れを示す。登録処理は、同一の物体を異なる視点から撮影した複数の画像が入力になる。登録処理を行うコンピュータは、前記入力が与えられると、各画像から局所特徴量を抽出するステップS1。そして、異なる視点の画像に連続して含まれる同一箇所の局所特徴量を距離計算を用いて求め、それらの局所特徴量を一つにまとめる部分空間を作成するステップS3。そして、生成された部分空間に前記物体の識別子と視点の撮影角度の範囲を付加し、データベースに登録するステップS5。認識処理は、データベースに複数のデータが登録されていることを前提として行われる。認識処理は、入力として検索質問の画像が与えられる。ここで、検索質問はある物体をある視点から撮影した画像である。検索質問が入力されると、認識処理を行うコンピュータは、検索質問から局所特徴量を抽出するステップS11。検索質問から抽出された各局所特徴量について、最も類似する部分空間を前記データベースの中からそれぞれ検索する。そして、検索された部分空間に付加された物体IDを多数決処理し、一つの物体IDを定めるステップS13。そして、その物体IDによって識別される物体をオペレーターが認識できるように出力するステップS15。この発明のデータベース作成装置は、登録に係る各処理を実行するコンピュータを装置としての観点で捉えたものである。各処理を実現するのは前記コンピュータを主とする共通のハードウェアであるが、各処理のプログラムが異なればコンピュータ処理によって実現される機能が異なる。これは、異なる機能を持つ複数の部品が組み合わされて全体として一つの装置が実現されることに対応するので、各処理の機能を実現する部分が組み合わされた装置として発明を捉えることができる。即ち、装置の観点から発明を捉えた場合は、局所特徴量の抽出処理の機能を担う抽出部、部分空間の作成処理の機能を担う部分空間生成部、データベースへの登録処理の機能を担う登録部を備えるデータベースの作成装置としてこの発明を捉えることができる。なお、認識処理についても、検索質問から局所特徴量を抽出する機能を担う部分、抽出された各局所特徴量に最も類似する部分空間を検索し、その部分空間に付加された物体IDを多数決処理して一つの物体IDを決定する機能を担う部分、決定された物体IDを出力する機能を担う部分を備える装置として捉えることができる。≪処理時間の削減≫以上に述べた手法では、複数フレームに渡って同一の局所領域から得られた特徴量の集合から、KL展開を用いて部分空間を作成し、複数の局所特徴量を一つにまとめて表現する。そうすることで、データベースに登録する特徴量を大幅に減らすことができ、メモリ容量を削減することができる。しかし、メモリ容量の削減が実現できても、一方で、処理時間の削減が課題となる。即ち、前述の手法では認識の際に、検索質問から得られた局所特徴量をデータベース内の部分空間のすべての基底に射影し、類似度を求めて認識を行っている。そのため、データベースに登録する物体数が増えると、適切な部分空間を探索するために時間を要する。射影して類似度を求めることで、各検索質問の局所特徴量に対応する部分空間を求める処理に代えて、距離計算によって適切な部分空間を求めることができれば、処理時間の削減の目処が立つ。既に提案されているANN参照を用いた近似最近傍探索の手法により、距離計算にかかる処理時間の短縮が可能になるからである。また、データベースに登録される物体の数が非常に大きかったり、検索質問に隠れオクルージョンや照明条件などの変化が加わったりして実験条件が厳しくなると、局所特徴量と部分空間の比較だけでは認識が非常に困難になる。この実施形態では、相互部分空間法詳細は、前田、渡辺:局所構造を導入したパターンマッチング法、信学論、pp345352参照にANNを用いることで、認識率の向上と処理の高速化を実現する。1.処理時間削減手法の具体的手法各クラスに対応するk次元の部分空間との類似度を計算する前述の手法では、認識を行う際に、局所特徴量としての各クエリ特徴ベクトルをデータベース中の各クラスに対応する部分空間のそれぞれの基底に射影し、類似度を求めなければならない。そのためデータベースに登録する物体の増加に伴って、処理時間が大きくなる。この実施形態では、近似的に類似度の高い部分空間を探索する手法を採用し処理時間を削減する。1-1.ANNを用いた距離計算への置換k次元の部分空間への射影による認識処理では、各クエリ特徴ベクトルをデータベース中の各部分空間の各基底に射影し、最も類似度の高い部分空間を見つけるため、処理時間がかかるという問題が生じる。そこで、この実施形態では、最も類似度の高い部分空間を、クエリから得られた局所特徴量と部分空間の第一主成分上の点との距離計算によって求める方法を提案する。距離計算によって、最も類似度の高い部分空間を求めることができれば、既に提案されている様々な近似最近傍探索の手法により、高速化することができる。距離計算により、最も類似度の高い部分空間を求める方法は以下のようになる。まず、データベース中の各部分空間の座標軸上に、原点から等距離の点をおく。そして、これらの点とクエリから得られた局所特徴量との距離計算を行う。この距離が短ければ短いほど、局所特徴量をその部分空間へ射影したときの射影長が長くなる。すなわち、最も類似度の高い部分空間となる。以上が、ANNを用いた距離計算による処理時間の削減手法の概要である。さらに、詳細な説明を以下に述べる。近似最近傍探索の手法の一つとして、ANNと呼ばれる手法が提案されている。この手法は、木構造をベースにしたもので、処理ソフトウェアが利用可能なため容易にANNの処理を試すことができる。ANNでの処理の概要を以下に示す。まずデータベースに登録された局所特徴量特徴ベクトルの集合である特徴空間を2分割してゆき、分割した領域中の特徴ベクトルが唯一になるまで繰り返す。分割した結果、最終的に得られる領域をセルと呼ぶ。次に、与えられたクエリ特徴ベクトルがどのセルに属するかを木構造を辿ることにより判定する。そして、このセルに対応づけられている特徴ベクトルとクエリ特徴ベクトルとの距離rを求める。このとき、真の最近傍点は半径rの超球内に存在する。そこで。この超球と重なりをもつすべてのセルにある特徴ベクトルと距離計算を行うことで、最近傍となる点を発見することができる。ANNでは、超球の半径を1倍して縮小することで、距離計算を行うセルを減らす。これにより、正しい最近傍が得られなくなるというリスクは負うものの、大幅な処理時間の削減、即ち、高速化が可能となる。しかし、ANNはある点に対する近傍点を近似的に求める手法であり、局所特徴量と部分空間の類似度を求めることはできない。そのため、部分空間法でANNを利用するためには、局所特徴量と最も類似度の高い部分空間を距離計算により求めることが必要である。この実施形態では、それを実現する手法を示す。まずこの実施形態の前提条件として、最も固有値の大きな固有ベクトルのみを基底とする1次元の部分空間、即ち、第一主成分のみで、部分空間を作成した元の局所特徴量の集合が十分よく表現されている必要がある。先に述べたk次元の部分空間を用いる手法では、トレース処理により連続的に変化する局所特徴量の集合を求め、その集合から部分空間を作成している。そのため、外れ値がほとんど存在せず、1次元の部分空間で近似的に十分よく表現できている。このとき、局所特徴量と部分空間の類似度は、局所特徴量と部分空間の基底との距離に反比例するといえる。すなわち、局所特徴量と最も距離の近い部分空間を求めることで、最も類似度の高い部分空間を求めることができる。局所特徴量と部分空間の基底との距離は、一般には局所特徴量から各部分空間の基底に下した垂線の長さとして求められる。しかしながら、これでは点と直線の距離を求めることとなり、ANNを用いて近似最近某探索を行うことができない。そこで、各部分空間の基底上に原点からの長さを正規化した点Siをそれぞれおき、点Siと局所特徴量の距離dSiを求める。この距離dSiから、局所特徴量と部分空間の距離を正確に求めることはできないが、局所特徴量と各部分空間との距離の遠近関係を知ることができる。つまり、距離dSiが最小となる部分空間が、最近傍の部分空間であり、最も類似度の高い部分空間である。1-2.近似最近傍探索による絞込み前述のように、部分空間の第一主成分のみを用いて距離計算を行う手法により、k次元の部分空間に対する類似度を求める手法に比べて認識に要する処理時間を削減することができる。しかし、部分空間の複数の軸を用いたほうが、より高い認識率を見込むことができる。そこで、別の実施形態として、2段階の処理を採用して認識を行う態様を挙げることができる。この実施形態では、まず1段階目として、部分空間の第一主成分のみを用いて、近似最近傍探索により高速に最も類似度の高い部分空間となるであろう候補を絞り込む。そして2段階目に、その候補に挙げられた各部分空間の複数の軸を用いて高次元に射影し、真に最も類似度の高い部分空間を求める。2段階目の処理を加えることによって、各部分空間の第一主成分のみを用いる場合に比べて高い認識率を見込むことができる。一方、2段階目のみの態様、即ち、各部分空間の各基底に各特徴ベクトルを射影して類似度を求める場合に比べて、類似度計算の対象候補を絞り込むので、処理時間を削減することができる。1-3.相互部分空間法におけるANNの利用この実施形態は、検索質問に動画もしくは連続撮影した複数の画像を用いる場合に有効である。この態様によれば、データベースを作成する際と同様に、検索質問に係る複数画像に対してもトレース処理を行う。トレース処理によって得られた局所特徴量の集合から部分空間を作成する。そうすることで、データベースの部分空間と質問画像から得た部分空間とを比較することができる。検索質問から得られた部分空間を、この明細書ではクエリ部分空間と呼ぶ。部分空間同士を比較し最適な部分空間を見つけるには、一般的にそれらの正準角を用いる。しかし、その手法では高速化が望めない。そこで、ここでも距離計算によって最適な部分空間を求める。既に述べたANNの距離計算と同様、各部分空間の軸上に、原点から等距離の点を置き、その点と点との距離計算を行う。この実施形態ではクエリも部分空間であるから、そのクエリ部分空間の座標軸上にも点を置く必要がある点に留意すべきである。以下、さらに詳細な説明を述べる。相互部分空間法MutualSubspaceMethodは、検索質問として動画像や複数の視点の画像を利用できる場合に用いられる。検索質問から得た局所特徴量の集合からもクエリ部分空間を作成し、クエリ部分空間とデータベース内の部分空間との比較によって検索質問を認識する。局所特徴量に比べ部分空間は変動が少ないため、検索質問として用いることで高い認識率を見込むことができる。ここで、検索質問から作成したクエリ部分空間とデータベース内の部分空間の類似度は、両者がなす正準角を算出することで求めることができる。しかし、正準角の算出にかかる処理時間は莫大なものになる。そこで、処理時間の削減を実現するため、この実施形態においてもANNを用いて処理時間を削減することを考える。まず、データベースに登録する各部分空間のそれぞれの基底上に、原点からの距離が1となるような点Siを配置する。また、検索質問から得たクエリ部分空間の基底上にも、適当な点Qをおく。このとき、点Qとの距離が最小となる点Siを基底上にもつ部分空間が、求めたい部分空間である。点Qとの距離が最小となる点Siは、ANNを用いることで近似的に求めることができる。これにより、相互部分空間法におけるクエリ部分空間と部分空間との比較が短い処理時間で実現できる。≪実験例1≫局所特徴量を用いた物体認識の基本的な従来手法と、複数の局所特徴量を部分空間で表現するこの発明の手法との比較実験を行った。比較の指標はメモリ容量と認識率である。1-1.実験の説明本実験で用いたデータセットについて説明する。本実験では、55個の三次元物体をターンテーブルで一回転させ、動画を撮影した。図5は、この発明に係る実験に使用した物体のいくつかの例を示す説明図である。そして、撮影された動画を構成する各フレーム画像を取得し、そのフレーム画像の中からデータベースに登録する登録用画像と検索質問画像を作成した。登録用画像は、各物体につき撮影角度を約1度ごとに変化させた360枚の画像を作成した。また、質問画像は、各物体につき約36度ごとに変化させた10枚の画像を作成した。ここで、登録用画像と質問画像は、異なる画像とした。つまり、検索質問画像と完全に同一の登録用画像は存在しない。データベースを作成するために、登録用画像からSIFT特徴量を抽出した。1枚の登録用画像から100~400個ほどの局所特徴量をそれぞれ得た。仮に1枚あたり300個の局所特徴量が得られたとすると、1つの物体の局所特徴量は300個×360枚=108000個であり、55個の物体に係る局所特徴量の総数はその55倍の5940000個である。検索質問は、全部で10枚×55個=550枚である。1枚の画像につきそれぞれ物体認識を行うので、最大550通りの物体認識が行われる。図6の縦軸の認識率はそれらの平均である。そして、前述のトレース処理によって、それらの局所特徴量から、20個以上連続して対応づいたもののみを選定した。つまり、撮影角度20度以上の範囲に渡り局所特徴量が対応づいたものを登録の対象とした。このとき、トレース処理を行う際に物体の同じ部分から得られた局所特徴量であるかどうかを判定するための閾値α前述の数5の式を参照の値を06に定めた。その各局所特徴量の集合からなる部分空間を求め、求まった部分空間に物体IDと対応する撮影角度の範囲とを付加してデータベースに登録した。一つの物体から得られる部分空間の数は、それぞれ100~400個ほどであった。1-2.実験結果考察まず、この発明の認識処理において、投票を行う際、図4のように物体に加えその撮影角度を考慮して投票を行うことが、どのくらい認識率に影響を及ぼしているかを調べる第1の実験を行った。図6は、この発明に係る第1の実験結果を示すグラフである。横軸は用いた部分空間の次元数を、縦軸は認識率を表している。実験結果より、物体IDごとに投票を行う態様であっても、95を超える認識率が得られ、部分空間の次元数が三次元のときに983となった。物体の撮影角度ごとに投票を行うと誤投票が分散され、部分空間の次元に関係なく認識率がさらに向上した。単なる物体IDでなく、物体IDと撮影角度との組み合わせに投票を行った場合、部分空間の次元数が三次元のときに989となった。意外にも、次元数をそれ以上増やしても989以上の認識率を得ることはなかった。この理由としては、部分空間の次元数を増やすと、部分空間と部分空間の間で重なりが増加し、部分空間の識別性が低下するためではないかと考えられる。つまり、求めたい部分空間との類似度だけが高くなるだけでなく、他の部分空間との類似度も高くなる可能性があるのである。図7は、この発明の実験に検索質問として用いた物体Aを示す説明図である。図8は、図7の物体Aに対して物体IDのみに投票を行った結果を示すグラフである。また、図9は、図7の物体Aに対して物体IDと撮影角度との組み合わせに投票を行うことで正しく認識されるようになった例を示す説明図である。図7の質問画像は、物体Aをある撮影角度で撮影したものである。図8に、各物体IDに投票を行い得票数を正規化して得られるスコアを示す。本来ならば物体Aのスコアが最も高くなるべきであるが、他の物体Bや物体Cのスコアのほうが高くなった。そのため、物体ごとに投票を行った場合、質問画像は物体Cと認識された。一方、図9は、物体IDと撮影角度の組み合わせに投票したときの物体A、物体B、物体Cの各撮影角度におけるスコアの様子を示す。物体IDのみに投票を行ったとき最もスコアが高かった物体Cでは、物体IDと撮影角度の組み合わせに投票することで得票数が分散し、スコアが低くなった。また、物体Aでは、ある範囲の撮影角度に票が集まった。そのため、物体IDのみに投票を行ったときには物体Cと認識されたものが、物体IDと撮影角度の組み合わせに投票を行うことで物体Aと正しく認識された。このとき、認識を行うと同時に、最もスコアが高くなった物体Aの68度と69度を、質問画像のおおよその撮影角度と推定することができた。図10は、この発明の実験に用いた物体Aの68度と69度の画像を示す説明図である。は68度、は69度の画像である。図10からわかるように、物体Aの撮影角度が正しく推定できているといえる。一方、この発明で認識できなかった例を次に示す。図11は、この発明の実験に用いた物体Dを示す説明図である。図12は、図11に示す物体Dを質問画像としたときの、物体Dと物体Eの各撮影角度のスコアを表したものである。本来ならば、物体Dの最もスコアが高い132度から144度が認識結果として得られることが望ましい。しかし、物体Eのスコアのように、得票数がある程度分散しているにも関わらず、スコアが高い場合は誤認識となってしまう。次に、物体IDと撮影角度の組み合わせに対して投票するこの発明の、メモリ容量を調べる実験を行った。実験結果より、部分空間の次元数が1次元のときに1998MBとなり、次元が増えるごとに約826MBずつ増えることがわかった。表1に、最もメモリ容量が少なかった1次元の部分空間を用いたときの認識率とメモリ容量表1中のデータベースのを参照、および、最も認識率が高くなった三次元の部分空間を用いたときの認識率とメモリ容量表1中のデータベースのを参照をそれぞれ示す。さらに、この発明がどのくらいメモリ削減に有用でありかつ認識率が維持されるかを比較するために、局所特徴量同士の最近傍探索による手法を用いて以下のデータベースで実験を行った。比較に用いたデータベースは、データベースを作成するために用いたすべての局所特徴量を登録したもの、トレース処理で得られた局所特徴量をすべて登録したもの、トレース処理後、各局所特徴量の集合の中からその中央に位置する局所特徴量のみを、その集合の代表ベクトルとして登録したものの3つである。表1に、それらのデータベースで実験を行ったときの認識率とメモリ容量を示す。この発明で三次元の部分空間を用いたときのメモリ容量は、無削減状態であるデータベースのメモリ容量の約118にすることができた。また、トレース処理で得られた局所特徴量をすべて登録したデータベースと比較すると、部分空間を作成し用いることで、メモリ容量を約17にしながら、無削減状態から若干低下した認識率を回復させることができた。さらに、1次元の部分空間を用いたときのメモリ容量とデータベースと比較すると、に対してメモリ容量はわずかに増加するが、より高い認識率が得られた。に対して認識率が向上した理由は、次の理由による。トレースの中央の局所特徴量は、トレース処理によって対応づけられた複数の局所特徴量の代表ベクトルであるだけで、その集合のすべての局所特徴量を表しているわけではいない。これに対し、この発明で用いた部分空間はその集合に含まれるいずれの局所特徴量の特性をもよく表している。より具体的に説明する。例えば、データベースに物体Fのトレース範囲が20度から60度の局所特徴量の集合Aと40度から80度の局所特徴量の集合Bがあったとする。このとき、質問画像が物体Fの40度の向きを撮影したものであるとする。トレースの中央の局所特徴量を用いる手法では、集合Aは40度の局所特徴量が代表ベクトルとなるので物体Fと対応づけられるが、集合Bは60度の局所特徴量が代表ベクトルとなり物体Fと正しく対応づけることが難しくなる。そのため、誤投票を行うことが多くなってしまい、誤認識されやすい。一方、部分空間法を用いたこの発明では、集合A、Bのどちらとも40度の向きを含んだ部分空間が作成されるので、正しく対応づけることができる。そもそも部分空間は、そのクラスのメンバーの特性がよく表されるようにクラス分類を行う手法だからである。そのため、部分空間法を用いたこの発明の手法では誤投票が少なくなり、認識率が向上したと考えられる。異なる表現をすれば、代表ベクトルは一つの局所特徴量にすぎず、局所特徴量は点を表すものである。これに対して撮影角度の範囲は区間を表すため、区間を点で表現するとどうしてもズレが生じる。一方、部分空間法では、得られる部分空間は区間を表す。そのためズレは生じない。次に、データベースを用いて、物体IDと撮影角度の組み合わせに投票する実験を行った。すなわち、トレース処理後の局所特徴量の集合から選択した一つの局所特徴量に、その局所特徴量が含まれるトレースが何度から何度まで対応しているかという情報をもたせ、投票の際に最近傍となった局所特徴量が対応する撮影角度の範囲に投票を行った。その結果、認識率は9636となり、物体ごとに投票を行った結果とほとんど認識率が変わらず、厳密には少し低下する結果となった。これより、トレースの中央の局所特徴量のみを登録しただけのデータベースでは、撮影角度ごとに投票することにあまり意味がないといえる。もちろん、物体ごとに投票した際に誤認識となっていたものが、物体の撮影角度ごとに投票することで正しく認識されるようになったものもある。しかし、逆に物体の撮影角度ごとに投票することで誤認識となったものもあり、結果的に認識率が向上しなかったのである。物体ごとに投票した際は正しく認識されたものが、物体の撮影角度ごとに投票することで誤認識となったものの原因は、次のように考えられる。誤投票が多いため、正解の物体であっても撮影角度ごとに投票することで票が分散してしまったり、逆に誤りである物体の撮影角度に票が偶然いくつか重なってしまったりすることが多くなったのである。また、得票数の正規化を行うことで、正解の物体の撮影角度のスコアが低くなってしまうこともある。例えば、物体Gの20度から60度の局所特徴量の集合と60度から100度の局所特徴量の集合と60度から110度の局所特徴量の集合があったとする。物体Gの60度を表している代表ベクトルは3つあることになるが、実際には代表ベクトルは物体Gの40度と80度と85度のものであるから、質問画像が物体Gの60度である場合には、なかなか対応づけることが難しい。そのため、正規化を行う際の分母√Nωが必要以上に大きくなってしまい、スコアが低くなってしまう傾向がある。以上に述べたように、この発明によれば、連続して変化する局所特徴量を、その変化を近似的によく表現することができる部分空間を作成して一つにまとめてデータベースに登録することで、メモリ容量を削減した。その結果、989の認識率を得ながら、メモリ容量は無削減状態の約118にすることができた。また、物体の撮影角度ごとに投票することによって、質問画像の物体の種類を認識するだけでなく、おおよその物体の向きを推定することもできた。≪実験例2≫1002個の物体の認識実験に対して、1ANNを用いることの有効性と2相互部分空間法による認識率の向上を確かめることを目的としてそれぞれ実験を行った。第1の実験では局所特徴量と部分空間の比較により物体を認識した。第2の実験では相互部分空間法を用いて物体を認識した。2-1.実験準備この実験例で用いたデータベースについて説明する。実験例では、1002個の3次元物体につき各物体をターンテーブルで1回転させ、正面、上15度および上30度の仰角からの動画をそれぞれ撮影した。図14は、データベースに登録した物体の一例を示す説明図である。撮影された動画からフレーム画像を取得し、データベース用画像とした。これらの画像からSIFT特徴量を抽出し、トレース処理を行い、部分空間を作成した。ここで、部分空間を作成する局所特徴量の集合は、トレース処理によって50フレーム以上連続して対応づいた局所特徴量の集合とした。作成した部分空間を物体IDとともにデータベースに登録した。部分空間の数は、1物体あたり約550個である。次に、この実験例で用いた検索質問について説明する。データベースに用いた1002物体のうち、無作為に100物体を選び、選んだ物体を手で持って動画を撮影した。そして、撮影動画からフレーム画像を取得し、検索質問用画像とした。図15は、検索質問用に撮影した物体の一例を示す説明図である。検索質問用画像からもSIFT特徴量を抽出した。2-2.ANNを用いた距離計算に関する実験第1の実験として、ANNを用いた距離計算の有効性を検証するため、最近傍探索を行った際と、ANNを用いて近似最近傍探索を行った際の認識率と処理時間の比較を行った。各検索質問用画像に対して撮影した物体を認識した。結果を以下の表2に示す。表2に示す実験結果から、近似最近傍探索を行った場合、最近傍探索によって認識を行った場合と比べてほとんど認識率を落とすことなく、処理時間が大幅に短縮できることがわかる。また、ANNの近似の度合いを示すパラメータεを変化させても処理時間がほとんど変わらない原因は、εの値が小さくても十分処理時間が短く、誤差によるものだと考えられる。2-3.相互部分空間法に関する実験相互部分空間法による認識率の向上を確かめることを目的として実験を行った。各物体の検索質問用フレーム画像に対して、トレース処理を行い、クエリ部分空間を作成した。クエリ部分空間を作成した局所特徴量の集合は、トレース処理によってTフレーム以上対応づいたもののみとした。Tの値は813253850と変化させた。また、相互部分空間法の比較対象として、複数の検索質問用フレーム画像を一つの検索質問として認識実験を行った。一つにまとめるフレーム画像の間隔をIとして、Iの値を52040100と変化させた。結果を以下の表3に示す。1枚の画像を検索質問に用いる前記項目2-2の実験と比較すると、動画として複数フレーム画像を検索質問に用いるほうが、1枚の画像を用いるよりもよい認識率を得ることができることがわかる。検索質問として用いるフレーム画像の間隔が短く画像の数が多くなればなるほどなればなるほど、認識率の向上を見込むことができる。また、T8のときの物体ごとの部分空間の数は平均5200個であり、I5のときの物体ごとの局所特徴量の数は平均45600個であった。そのことから、複数のフレーム画像から得た局所特徴量をそのまま認識に用いるより。クエリ部分空間を作成して認識を行ったほうが、認識率処理時間とも向上したといえる。2-4.実験例2のまとめこの実施形態では、部分空間法において、最も高い類似度の部分空間を求める処理を高速化する手法を示した。この実施形態によれば、局所特徴量と最も高い類似度となる部分空間を求めるにあたり、各部分空間の各基底への射影成分ではなく、各部分空間の基底上の定点との距離の大小関係に基づいて求めた。距離の大小関係によって求めることで、ANNを用いて近似最近傍探索を行うことができ、処理時間の高速化が実現できた。その結果、従来の部分空間法では処理時間が190秒、認識率が34であったものが、ANNを使うことで認識率を略同程度に保ちながら処理時間を0012秒にすることができた。また、相互部分空間法にも提案手法を適用し、処理時間の高速化と同時に、大幅な認識率の向上を可能にした。前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。"