(57)【要約】  物体が撮影された画像から、特徴ベクトルを抽出して物体を多数の特徴ベクトルで表現し、特徴の一致する物体を画像データベース中から検索する物体認識処理において、より高速な物体認識の処理手法を提供する。また、画像データベースに要するメモリ容量を節約する手法を提供する。  複数の特徴ベクトルで記述される物体を近似最近傍探索によって認識するタスクのための、高速化手法を提案する。高速化手法の一つは、近傍に多数の特徴ベクトルがあって、多くの距離計算が避けられないような場合、そのような特徴ベクトルを破棄することによって高速化を図る。もう一つの高速化手法は、距離計算を一切行わなず、ハッシュ表を引いて投票することだけを行う。また、近似最近傍探索に基づく識別器を多段階に縦列接続することにより、認識に用いる近似の程度を画像に応じて変更し、大幅な効率化を実現する。
2008026414.tif 000002
【特許請求の範囲】
【請求項１】
対象物を表す画像が入力画像として与えられたとき、局所記述子の探索により、画像データベース中から前記対象物を含む画像を識別する画像認識方法であって、
入力画像からその局所的な特徴を表す複数の局所記述子を導出する工程と、
前記画像データベース中の画像から得られる各局所記述子のうち、入力画像の各局所記述子に対して探索を行う対象をそれぞれ限定する限定工程と、
前記探索の対象中から入力画像の各局所記述子に近いものを探索し、入力画像の各局所記述子に対する近傍の各局所記述子を特定する探索工程と、
近傍の各局所記述子が得られた画像のうち、認識結果とすべき画像を、統計的処理を用いて識別する識別工程とを備え、
前記限定工程は、認識結果とすべき画像を識別し得る程度の数に前記探索の対象を限定し、
各工程をコンピュータが実行することを特徴とする画像認識方法。
【請求項２】
前記限定工程は、認識結果とすべき画像が識別されるように、入力画像に応じて探索対象を限定する程度を異ならせ得る請求項１記載の画像認識方法。
【請求項３】
認識結果とすべき画像が識別できなかったとき、前記限定工程は、探索対象を限定する程度を緩め、かつ、先に探索対象とされたものを除外して新たな探索対象を決定する処理をさらに行い、
決定された探索対象について探索工程および識別工程を実行する請求項２記載の画像認識方法。
【請求項４】
検索対象を限定する程度を段階的に緩めて前記限定工程、探索工程および識別工程を繰り返しても認識結果とすべき画像が識別できないとき、その局所記述子についての探索結果をリジェクトする請求項３記載の画像認識方法。
【請求項５】
前記画像データベースは、各画像から導出される各局所記述子をそれから所定手順で算出されるインデックス値で分類してなるハッシュ表を含んでなり、
前記限定工程は、特徴量の変動を考慮して入力画像の各局所記述子から前記手順でインデックス値を算出し、算出されたインデックス値で前記ハッシュ表を参照してその類に属する局所記述子を探索対象とし、
前記識別工程は、探索工程により特定された近傍の各局所記述子について、それが得られた画像に投票を行う統計的処理を用い、
前記ハッシュ表は、各類について、その類に属する局所記述子の数が閾値を超える場合にその類の局所記述子を探索対象から除外して作成されるものである請求項１〜４の何れか一つに記載の画像認識方法。
【請求項６】
各局所記述子はベクトルとして表現され、
特徴量の変動を考慮してハッシュ表のインデックス値を算出する処理は、各局所記述子の要素を離散化して得られる離散値に誤差の範囲を含めてインデックス値を算出する処理であり、
前記誤差の範囲は、前記変動に応じて決定されるものである請求項５記載の画像認識方法。
【請求項７】
前記探索工程は、入力画像の各局所記述子とそれに対応する類に属するハッシュ表中の各局所記述子との間の距離計算を行い、所定距離内または最短距離にある局所記述子を特定する工程である請求項５または６記載の画像認識方法。
【請求項８】
前記探索工程は、入力画像の各局所記述子に対応する類に属するハッシュ表中の各局所記述子をいずれも近傍の局所記述子とする工程である請求項５または６記載の画像認識方法。
【請求項９】
画像データベース中の画像に含まれる前記対象物のパターンは、入力画像と異なる角度から対象物をみたときのパターンである請求項１〜８のいずれか一つに記載の画像認識方法。
【請求項１０】
画像データベース中の画像に含まれる前記対象物のパターンは、その一部分が入力画像のパターンに対応するものである請求項１〜８のいずれか一つに記載の画像認識方法。
【請求項１１】
対象物を表す画像が入力画像として与えられたとき、局所記述子の探索により、画像データベース中から前記対象物を含む画像を識別する装置であって、
入力画像からその局所的な特徴を表す複数の局所記述子を導出する特徴導出部と、
前記画像データベース中の画像から得られる各局所記述子のうち、入力画像の各局所記述子に対して探索を行う対象をそれぞれ限定する限定部と、
前記探索の対象中から入力画像の各局所記述子に近いものを探索し、入力画像の各局所記述子に対する近傍の各局所記述子を特定する探索部と、
近傍の各局所記述子が得られた画像のうち、認識結果とすべき画像を、統計的処理を用いて識別する識別部とを備え、
前記限定部は、認識結果とすべき画像を識別し得る程度の数に前記探索の対象を限定することを特徴とする画像認識装置。
【請求項１２】
前記限定部は、認識結果とすべき画像が識別されるように、入力画像に応じて探索対象を限定する程度を異ならせ得る請求項１１記載の画像認識装置。
【請求項１３】
認識結果とすべき画像が識別できなかったとき、前記限定部は、探索対象を限定する程度を緩め、かつ、先に探索対象とされたものを除外して新たな探索対象を決定する処理をさらに行い、
探索部は、決定された探索対象についてさらに近傍の各局所記述子を特定し、識別部は、特定された各局所記述子に基づいて認識結果とすべき画像をさらに識別する請求項１２記載の画像認識装置。
【請求項１４】
対象物を表す画像が入力画像として与えられたとき、局所記述子の探索により、画像データベース中から前記対象物を含む画像を識別する機能をコンピュータを用いて実現するプログラムであって、
入力画像からその局所的な特徴を表す複数の局所記述子を導出する特徴導出部と、
前記画像データベース中の画像から得られる各局所記述子のうち、入力画像の各局所記述子に対して探索を行う対象をそれぞれ限定する限定部と、
前記探索の対象中から入力画像の各局所記述子に近いものを探索し、入力画像の各局所記述子に対する近傍の各局所記述子を特定する探索部と、
近傍の各局所記述子が得られた画像のうち、認識結果とすべき画像を、統計的処理を用いて識別する識別部としてコンピュータを機能させ、
前記限定部は、認識結果とすべき画像を識別し得る程度の数に前記探索の対象を限定することを特徴とする画像認識プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、画像の局所的な特徴を記述する局所記述子を用いて画像認識を行う画像認識方法、局所記述子を用いて画像認識を行う画像認識装置および画像認識プログラムに関する。
【背景技術】
【０００２】
デジタルカメラやカメラ付き携帯電話の普及に伴って、単にスナップ写真を撮るだけではなく、カメラを情報入力機器としても利用したいという要望が高まっている。一つの可能性として、カメラで捉えた物体を認識し、それに応じた情報処理を行うことが考えられる。【０００３】
何も制限を設けずに物体を認識することは未だに困難といわざるを得ないが、近年の技術的な発展により、対象に制約を加えることができれば物体認識は現実味を帯びてきている。例えば、対象が3次元物体ではなく平面上のパターン(平面物体)であること、物体のクラス（例えば、写真の物体が車というカテゴリに属するかどうか）を認識するのではなく、インスタンス（車のあるモデルをある角度から撮影した写真かどうか）を認識することなどが仮定できれば、すでにサービスが可能なレベルにある。例えば、株式会社クレメンテックの技術(US. Patent No.20040208372)を利用した大日本印刷株式会社によるサービス、オリンパス株式会社のサービス、Evolution Robotics, Inc. の技術を利用した日本電気株式会社のサービスなどが知られている。このような平面物体の認識が可能になれば、ポスターや商品の写真を撮影することによる誘導だけではなく、既存の画像やビデオの自動索引付けへの道も開けてくる。【０００４】
さて、物体認識のためには、画像から特徴を抽出する必要がある。本発明では、平面物体を対象とした局所記述子(local descriptor)を用いる認識に着目する。局所記述子とは、画像の局所的な特徴を捉えて多次元の特徴ベクトルとして抽出し、画像を記述するものである。値が局所的に決定されるので、隠れや画像の変動に対して比較的強い（ロバストである）という性質がある。ここで、「局所的」とは、画像の一部分であることを意味し、「局所記述子」とは、画像の部分的な特徴を表現したものをいう。この明細書で、局所記述子は、特徴ベクトルともいう。【０００５】
局所記述子を用いた物体認識法では、2つの画像から得た特徴ベクトル同士の距離を測り、最近傍のものに対応付けることが基本演算となる。そして、カメラで得た画像と、データベース中の多数の画像の間で特徴ベクトルを対応付け、データベース中の画像に対して投票する。最後に、得票数の最も多い画像のラベルを「認識結果」として出力する。ただし、特徴ベクトルの次元数が数十から数百、数が、画像あたり数百から数千というオーダであることを考えると、単純に全ての組み合わせの距離を計算することは実用的ではないことが分かる。【０００６】
ところが、近年の最近傍探索技術の発展により、膨大な数の特徴ベクトルを短時間で探索することが可能となってきた（例えば、非特許文献1,2参照）。特にANN(Approximate Nearest Neighbor)（例えば、非特許文献3参照）、LSH (Locality Sensitive Hashing)（例えば、非特許文献4参照）は、各々、木構造、ハッシュ表を用いて、近似的な最近傍探索を行うことにより、高速な探索を実現している。国内では、例えば、正確な最近傍探索に対するSR-Tree（例えば、非特許文献5参照）に加え、近似最近傍探索の手法として小林らの分散コーディング（例えば、非特許文献6参照）がある。【０００７】
さらに、物体認識という観点から、和田らは最近傍識別器（例えば、非特許文献7参照）という概念とそれを具体化したKDDT（例えば、非特許文献8参照）という手法を提案している。各物体が一つの特徴ベクトルに対応しており、その物体のカテゴリを認識する問題を考えるとき、認識対象の物体から得た特徴ベクトルがどのカテゴリの特徴ベクトルに近いのかが分かればよく、「最近傍」の特徴ベクトルを求める必要はない。これにより、正確な最近傍探索を用いる場合に比べて、数倍から数百倍の高速化が可能であることが示されている。【０００８】
また、文書画像の索引付けに適した特徴量の抽出手法と、その特徴量に適した検索アルゴリズムが知られている（例えば、特許文献１参照）。
【特許文献１】国際公開第2006／092957号パンフレット
【非特許文献１】P.Indyk, Nearest neighbors in high-dimensional spaces, Handbook of discrete and computational geometry (Eds. by J.E. Goodman and J.O'Rourke), Chapman & Hall/CRC, pp.877-892, 2004.
【非特許文献２】G.Shakhnarovich, T.Darrell and P.Indyk Eds., Nearest-neighbor methods in learning and vision, The MIT Press, 2005.
【非特許文献３】S.Arya, D.M. Mount, R.Silverman and A.Y. Wu, "An optimal algorithm for approximate nearest neighbor searching," Journal of the ACM, vol.45, no.6, pp.891-923, 1998.
【非特許文献４】M.Datar, N.Immorlica, P.Indyk and V.S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proc. of the 20th annual symposium on Computational Geometry, pp.253-262, 2004.
【非特許文献５】片山紀生、佐藤真一、"類似検索のための索引技術、"情報処理、vol.42, no.10，pp.958-964，Oct.，2001．
【非特許文献６】小林卓夫、中川正樹、"分散コーディングによる高次元の最近傍探索、"信学技報 PRMU2006-41，June，2006．
【非特許文献７】和田俊和、"空間分割を用いた識別と非線形写像の学習 (1)空間分割による最近傍識別の高速化、"情報処理、vol.46, no.8，pp.912-918，Aug.，2005．
【非特許文献８】柴田智行、加藤丈和、和田俊和、"K-d decision tree とその応用 − 最近傍識別器の高速化と省メモリ化、"信学論(D-II)、vol.J88-D-II, no.8，pp.1367-1377，Aug.，2005．
【発明の開示】
【発明が解決しようとする課題】
【０００９】
前述した局所記述子のように、各物体を多数の特徴ベクトルで表現する手法は、物体認識に有効なアプローチである。しかし、多数の特徴ベクトルについて計算を実行する必要があり、更なる計算時間の短縮が望まれている。即ち、より高速な物体認識の処理手法が求められている。【００１０】
特許文献１のように、特徴量の抽出手法を工夫することも高速な物体認識手法を実現する有効なアプローチの一つであるが、従来の手法で抽出された特徴量を用いる最近傍探索手法を工夫することも別の面からの有効なアプローチであり、そのような手法が望まれている。
【課題を解決するための手段】
【００１１】
統計的処理によって認識結果を決定する場合、最近傍識別器と同様、個々の特徴ベクトルに対しては、最近傍の特徴ベクトルを求める必要はなく、対応する画像がどれであるのかが分かればよい。さらに、別の物体の特徴ベクトルに誤って照合しても、最終的に正解と不正解の得票数が逆転しなければよい。従って、特徴ベクトルの探索の正確さを犠牲にして、大幅な近似最近傍探索を実施することにより、処理時間を稼ぐことが可能である。【００１２】
発明者らは、前述の発想に基づいて検討を重ね、この発明に至った。【００１３】
この発明は、
（１）対象物を表す画像が入力画像として与えられたとき、局所記述子の探索により、画像データベース中から前記対象物を含む画像を識別する画像認識方法であって、入力画像からその局所的な特徴を表す複数の局所記述子を導出する工程と、前記画像データベース中の画像から得られる各局所記述子のうち、入力画像の各局所記述子に対して探索を行う対象をそれぞれ限定する限定工程と、前記探索の対象中から入力画像の各局所記述子に近いものを探索し、入力画像の各局所記述子に対する近傍の各局所記述子を特定する探索工程と、近傍の各局所記述子が得られた画像のうち、認識結果とすべき画像を、統計的処理を用いて識別する識別工程とを備え、前記限定工程は、認識結果とすべき画像を識別し得る程度の数に前記探索の対象を限定し、各工程をコンピュータが実行することを特徴とする画像認識方法を提供する。【００１４】
また、異なる観点から、この発明は、
（２）対象物を表す画像が入力画像として与えられたとき、局所記述子の探索により、画像データベース中から前記対象物を含む画像を識別する装置であって、入力画像からその局所的な特徴を表す複数の局所記述子を導出する特徴導出部と、前記画像データベース中の画像から得られる各局所記述子のうち、入力画像の各局所記述子に対して探索を行う対象をそれぞれ限定する限定部と、前記探索の対象中から入力画像の各局所記述子に近いものを探索し、入力画像の各局所記述子に対する近傍の各局所記述子を特定する探索部と、近傍の各局所記述子が得られた画像のうち、認識結果とすべき画像を、統計的処理を用いて識別する識別部とを備え、前記限定部は、認識結果とすべき画像を識別し得る程度の数に前記探索の対象を限定することを特徴とする画像認識装置を提供する。【００１５】
さらに、異なる観点から、この発明は、
（３）対象物を表す画像が入力画像として与えられたとき、局所記述子の探索により、画像データベース中から前記対象物を含む画像を識別する機能をコンピュータを用いて実現するプログラムであって、入力画像からその局所的な特徴を表す複数の局所記述子を導出する特徴導出部と、前記画像データベース中の画像から得られる各局所記述子のうち、入力画像の各局所記述子に対して探索を行う対象をそれぞれ限定する限定部と、前記探索の対象中から入力画像の各局所記述子に近いものを探索し、入力画像の各局所記述子に対する近傍の各局所記述子を特定する探索部と、近傍の各局所記述子が得られた画像のうち、認識結果とすべき画像を、統計的処理を用いて識別する識別部としてコンピュータを機能させ、前記限定部は、認識結果とすべき画像を識別し得る程度の数に前記探索の対象を限定することを特徴とする画像認識プログラムを提供する。【００１６】
また、この発明の一側面は、
（４）ハッシュ表を用いて体系づけられた画像データベース中から、入力画像に含まれる対象物のパターンに基づいて前記対象物を含む画像を認識する方法であって、前記パターンの局所的な特徴量を表す１以上の特徴ベクトルを抽出する工程と、抽出された特徴ベクトルからハッシュ表のインデックスを算出するインデックス算出工程と、算出されたインデックスで前記ハッシュ表を参照して画像データベース中の候補画像を決定し、決定した候補画像に投票を行う投票工程と、各特徴ベクトルについての投票結果に基づいて認識結果の画像を得る工程とを備え、前記ハッシュ表の作成工程は、画像データベースに登録する各画像から抽出された各特徴ベクトルに対して、ハッシュ表のインデックスを算出し、各特徴ベクトルのうち識別能力の低い特徴ベクトルの除外を行い、残された各特徴ベクトルに対応する画像参照用データを登録する各工程を含むことを特徴とする画像認識方法を提供する。【００１７】
また、異なる観点から、この発明は、
（５）ハッシュ表を用いて体系づけられた画像データベース中から、入力画像に含まれる対象物のパターンに基づいて前記対象物を含む画像を認識する装置であって、前記パターンの局所的な特徴を表す１以上の特徴ベクトルを抽出する特徴点抽出部と、抽出された特徴ベクトルからハッシュ表のインデックスを算出するインデックス算出部と、算出されたインデックスで前記ハッシュ表を参照して画像データベース中の候補画像を決定し、決定した候補画像に投票を行う投票部と、各特徴ベクトルについての投票結果に基づいて認識結果の画像を得る画像選択部とを備え、前記ハッシュ表の作成工程は、画像データベースに登録する各画像から抽出された各特徴ベクトルに対して、特徴量の変動を考慮してハッシュ表のインデックスを算出し、各特徴ベクトルのうち識別能力の低い特徴ベクトルの除外を行い、残された各特徴ベクトルに対応する画像参照用データを登録する各工程を含むことを特徴とする画像認識装置を提供する。
【発明の効果】
【００１８】
この発明による前記（１）の画像認識方法において、前記限定工程は認識結果とすべき画像を識別し得る程度の数に前記探索の対象を限定するので、認識に要する処理時間を短縮することができる。即ち、高速に物体を認識することができる。【００１９】
また、この発明による前記（２）の画像認識装置において、前記限定部は認識結果とすべき画像を識別し得る程度の数に前記探索の対象を限定するので、認識に要する処理時間を短縮することができる。【００２０】
さらに、この発明による前記（３）の画像認識プログラムにおいて、前記限定部は認識結果とすべき画像を識別し得る程度の数に前記探索の対象を限定するので、認識に要する処理時間を短縮することができる。【００２１】
この発明による前記（４）の画像認識方法によれば、識別能力の低い特徴ベクトルは除外され、識別能力の高い特徴ベクトルに対応する画像参照用データだけがハッシュ表に登録されるので、識別能力の高い特徴ベクトルだけを処理対象として短時間で画像認識を行うことができる。また、識別能力の高い特徴ベクトルに対応する画像参照用データだけがハッシュ表に登録されるので、全ての特徴ベクトルに対応する画像参照用データを登録する場合に比べて画像データベースに要するメモリ容量を節約することができる。【００２２】
また、この発明による前記（５）の画像認識装置によれば、識別能力の高い特徴ベクトルに対応する画像参照用データだけがハッシュ表に登録されるので、それらを処理対象として短時間で画像認識を行うことができる。また、識別能力の高い特徴ベクトルに対応する画像参照用データだけがハッシュ表に登録されるので、画像データベースのメモリ容量を節約することができる。
ここで、特徴ベクトルの除外について、そのアイデアを判り易く説明する。この発明の画像認識方法は、特徴ベクトルを用いて画像を認識するものである。認識の基本は，データベースに登録された特徴ベクトルと入力画像の特徴ベクトルの照合にある。特徴ベクトルは画像の局所的な特徴を表すので、一般に、一つの画像から複数の特徴ベクトルを得る。ところが、データベースに登録された物体（画像）の特徴ベクトルの中には，その物体の特徴をよく表す（識別能力の高い）ものと、そうでない（識別能力の低い）ものがある。物体の特徴をよく表すものとは、その特徴ベクトルがあれば、入力画像はその物体であるといえるような、十分な証拠となる特徴ベクトルである。一方，そうでない特徴ベクトルというのは、様々な物体の画像に表れるため、その特徴ベクトルがあるからといって、どの物体であるのかの判断には使えないものである。特徴ベクトルの除外とは、後者、すなわち、証拠となりえない特徴ベクトルを辞書から削除する処理をいう。より具体的には、
ｉ）どれほど似た特徴ベクトルが多いのかを計算し、
ii）一定の閾値を超えたものを不要とする
という流れで処理を行い、識別能力の低い特徴ベクトルを削除する。【００２３】
以下、この発明の好ましい態様について説明する。
前記（１）の画像認識方法において、前記限定工程は、認識結果とすべき画像が識別されるように、入力画像に応じて探索対象を限定する程度を異ならせ得るものであってもよい。即ち、近似の程度を入力画像に応じて異ならせてもよい。このようにすれば、認識に用いる近似の程度を画像に応じて変更することによって処理時間を短縮することができる。【００２４】
近似最近傍探索を用いた物体認識では、近似の程度が認識率と効率をバランスするための重要なパラメータとなる。近似を強くすればするほど処理時間を削減できるが、近似を強くし過ぎると多くの特徴ベクトルに対して最近傍が求まらなくなり、結果として誤認識を引き起こしてしまう。ここでの問題の一つは、誤認識を引き起こす近似の程度が画像によって異なる点である。大幅な近似を行っても認識できる「簡単な」画像がある反面、それでは誤認識となる「難しい」画像もある。固定的な近似によって一定の認識率を確保するには、近似の程度を認識の難しい画像に合わせる必要があり、効率向上の妨げとなっている。【００２５】
そこで、この発明の好ましい一態様として、「認識に必要な最近傍探索の精度は画像によって異なる」という観点から処理を削減する手法を提供する。即ち、近似の程度を画像に対して適応的に調節する手法である。前記手法によれば、近似の程度が異なる識別器を複数用意し、それらを近似の程度が強いものから弱いものへと多段階に縦列接続することで実現できる。これによって、簡単に認識できる画像は、前段の部分で大幅な近似の識別器によって高速に認識することができ、それでは認識できない画像に対してのみ、後段の部分で近似の弱い識別器によって時間をかけて精密に認識することができる。
また、認識結果とすべき画像が識別できなかったとき、前記限定工程は、探索対象を限定する程度を緩め、かつ、先に探索対象とされたものを除外して新たな探索対象を決定する処理をさらに行い、決定された探索対象について探索工程および識別工程を実行するようにしてもよい。このようにすれば、近似の程度を変えて限定工程、探索工程および識別工程を多段階で実行した場合であっても、各段階で探索対象となったものを一度に探索した場合に比べてあまり遜色のない処理時間で認識を行うことができる。【００２６】
この手法の特徴は、多段階化する識別器の構成方法にある。後段の識別器では、近似の違いによる差分のみ、すなわち、それより前段の識別器で対象とならなかった特徴ベクトルのみを距離計算の対象とすることによって、最後段まで処理が進んでも、最後段の識別器を単独で用いる場合とほぼ同等の計算量しかかからないという利点を得ることができる。
さらに、検索対象を限定する程度を段階的に緩めて前記限定工程、探索工程および識別工程を繰り返しても認識結果とすべき画像が識別できないとき、その局所記述子についての探索結果をリジェクトするしてもよい。このようにすれば、リジェクトを行わない場合に比べて誤認識率を抑制することができる。【００２７】
また、前記画像データベースは、各画像から導出される各局所記述子をそれから所定手順で算出されるインデックス値で分類してなるハッシュ表を含んでなり、前記限定工程は、特徴量の変動を考慮して入力画像の各局所記述子から前記手順でインデックス値を算出し、算出されたインデックス値で前記ハッシュ表を参照してその類に属する局所記述子を探索対象とし、前記識別工程は、探索工程により特定された近傍の各局所記述子について、それが得られた画像に投票を行う統計的処理を用い、前記ハッシュ表は、各類について、その類に属する局所記述子の数が閾値を超える場合にその類の局所記述子を探索対象から除外して作成されるものであってもよい。このようにすれば、各類に属する局所記述子の数が閾値を超える場合はそれらを探索対象から除外してハッシュ表が作成されるので、限定工程において探索対象とされる局所記述子が識別能力の高いものに限定され、効率的な認識が実現される。【００２８】
ハッシュ表の一つの類（インデックス）に属する局所記述子（特徴ベクトル）の数が多い場合、それらの局所記述子は識別能力が低いといえる。即ち、入力画像の局所記述子からインデックス値を算出してハッシュ表を参照した場合、その類に属する候補が多数登録されているわけである。それらの局所記述子は、認識対象の絞込みにあまり貢献しておらず、識別能力が低いといえる。識別能力の低い局所記述子を探索対象から除外しておけば、識別能力の高い局所識別子だけを参照して、効率的な認識が行われる。
さらに、各局所記述子はベクトルとして表現され、特徴量の変動を考慮してハッシュ表のインデックス値を算出する処理は、各局所記述子の要素を離散化して得られる離散値に誤差の範囲を含めてインデックス値を算出する処理であり、前記誤差の範囲は、前記変動に応じて決定されるものであってもよい。即ち、インデックスを算出する際、要素の値と変動の推定値から算出した値の範囲が、離散化に用いる複数の区間にまたがる場合、各区間に対応する離散値を用いて複数のインデックスを算出するようにしてもよい。【００２９】
例えば、画像データベース中の対象物のパターンが、入力画像と異なる角度から対象物をみたパターンである場合、即ち、変動がある場合、認識されるべき画像と入力画像との間で対応関係にある局所記述子（特徴ベクトル）の要素の値は変化する。
ハッシュ表は、所定手順に従って局所記述子の要素の値から所定の算出手順で離散値であるインデックス値を算出するが、特徴ベクトルの要素の値に変動があると、異なる離散値が算出されてしまう可能性が高いといえる。特徴ベクトルの各要素は、所定の閾値で離散化された離散値である。そこで、特徴ベクトルの各要素の値を中心とする変動の推定区間が離散化の閾値を超えた複数の区間にまたがる場合、各区間に対応する離散値を要素の値として複数のインデックスを算出する。このようにすれば、上記変動に対する認識率の低下を抑制することができる。換言すれば、特徴ベクトルのある要素が離散化の閾値に近い場合、閾値をまたぐ可能性も考慮してインデックスを計算することによって、認識率を確保することができる。
また、前記探索工程は、入力画像の各局所記述子とそれに対応する類に属するハッシュ表中の各局所記述子との間の距離計算を行い、所定距離内または最短距離にある局所記述子を特定する工程であってもよい。【００３０】
あるいは、前記探索工程は、入力画像の各局所記述子に対応する類に属するハッシュ表中の各局所記述子をいずれも近傍の局所記述子とする工程であってもよい。このようにすれば、特徴ベクトルの距離計算を行わずに探索を行うことができるので、距離計算を行う場合に比べて探索に要する処理時間を短縮することができる。【００３１】
前記（２）の画像認識装置において、前記限定部は、認識結果とすべき画像が識別されるように、入力画像に応じて探索対象を限定する程度を異ならせ得るものであってもよい。即ち、近似の程度を入力画像に応じて異ならせてもよい。このようにすれば、認識に用いる近似の程度を画像に応じて変更することによって処理時間を短縮することができる。【００３２】
また、認識結果とすべき画像が識別できなかったとき、前記限定部は、探索対象を限定する程度を緩め、かつ、先に探索対象とされたものを除外して新たな探索対象を決定する処理をさらに行い、探索部は、決定された探索対象についてさらに近傍の各局所記述子を特定し、識別部は、特定された各局所記述子に基づいて認識結果とすべき画像をさらに識別するようにしてもよい。このようにすれば、近似の程度を変えて限定部、探索部および識別部が多段階の処理を実行した場合であっても、各段階で探索対象となったものを一度に探索した場合に比べて遜色のない処理時間で認識を行うことができる。【００３３】
また、前記（１）および（４）の発明の画像認識方法、前記（２）および（５）の画像認識装置、前記（３）の画像認識プログラムにおいて、画像データベース中の画像に含まれる前記対象物のパターンは、入力画像と異なる角度から対象物をみたときのパターンであってもよい。【００３４】
また、前記（１）および（４）の発明の画像認識方法、前記（２）および（５）の画像認識装置、前記（３）の画像認識プログラムにおいて、画像データベース中の画像に含まれる前記対象物のパターンは、その一部分が入力画像のパターンに対応するものであってもよい。【００３５】
ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。
さらに、この発明の好ましい態様について説明する。【００３６】
前記（４）の発明の画像認識方法において、識別能力の低い特徴ベクトルの除外は、互いにインデックスの等しい特徴ベクトルが所定数を超える場合、当該インデックスが算出される各特徴ベクトルをハッシュ表への登録対象から除外する処理であってもよい。ハッシュ表の一つのインデックスに対して登録対象となる特徴ベクトルの数が多い場合、それらの特徴ベクトルは識別能力が低いといえる。即ち、入力画像から抽出された特徴ベクトルからインデックスを算出し、算出されたインデックスでハッシュ表を参照した場合、そのインデックスについて候補となり得る画像が多数登録されているわけである。このようなインデックスは、認識対象の画像の絞込みにあまり貢献していない。従って、各インデックスについて、それらの特徴ベクトルをハッシュ表への登録対象から除外することによって、識別力の高い画像参照用データだけをハッシュ表に登録することができる。【００３７】
また、前記インデックス算出工程は、各特徴ベクトルの要素を離散化して得られる離散値に、誤差の見積もりの範囲を満たす離散値を含めることによりインデックスを算出するようにしてもよい。即ち、インデックスを算出する際、要素の値と変動の推定値から算出した値の範囲が、離散化に用いる複数の区間にまたがる場合、各区間に対応する離散値を用いて複数のインデックスを算出するようにしてもよい。
例えば、画像データベース中の対象物のパターンが、入力画像と異なる角度から対象物をみたパターンである（変動がある）場合、認識されるべき画像と入力画像との間で対応関係にある特徴ベクトルの要素の値は変化する。【００３８】
インデックス算出工程において、閾値を基準に特徴ベクトルの要素の値を離散化しているが、対応関係にある特徴ベクトルの要素の値が閾値付近の場合は、値に変動があると、離散化の結果、異なる離散値に離散化されてしまう可能性が高いといえる。そこで、特徴ベクトルの要素の値を中心とした変動の推定区間が離散化に用いる複数の区間にまたがる場合、各区間に対応する離散値を用いて複数のインデックスを算出することによって、上記変動に対する認識率の低下を抑制することができる。換言すれば、特徴ベクトルのある要素が、インデックスを計算する際の離散化の閾値に近い場合、閾値をまたぐ可能性も考慮してインデックスを計算することによって、認識率を確保することができる。【００３９】
また、前記ハッシュ表に登録される画像参照用データは、各特徴ベクトルを含むデータベース中の画像を識別する画像ＩＤと当該特徴ベクトルの要素とからなり、投票工程は、入力画像の各特徴ベクトルと当該特徴ベクトルから算出されるハッシュ表のインデックスに登録された各特徴ベクトルとの間の距離計算を行い、最短距離の特徴ベクトルの画像ＩＤで識別される画像に投票する処理であってもよい。また、この際には、最短距離が一定の閾値以下の場合のみに投票する処理であってもよい。
このようにすれば、特徴ベクトルの距離計算の回数をインデックスに登録されたものだけに絞り込んで距離計算の回数を減らすことができる。【００４０】
あるいは、前記ハッシュ表に登録される画像参照用データは、各特徴ベクトルを含むデータベース中の画像を識別する画像ＩＤからなり、投票工程は、入力画像の各特徴ベクトルから算出されるハッシュ表のインデックスに登録された画像ＩＤで識別される画像に投票する処理であってもよい。このようにすれば、ハッシュ表には、画像ＩＤだけが登録され、各特徴ベクトルの要素を登録する必要がないので、画像データベースのメモリをさらに節約することができる。また、入力画像の各特徴ベクトルについて、算出されたインデックスでハッシュ表を参照し、当該インデックスに登録された画像ＩＤを用いて投票処理を行う単純な処理で認識処理を行うので、距離計算を行う場合に比べて計算時間をさらに短縮することができる。【００４１】
また、前記（５）の発明の画像認識装置において、識別能力の低い特徴ベクトルの除外は、互いにインデックスの等しい特徴ベクトルが所定数を超える場合、当該インデックスが算出される各特徴ベクトルをハッシュ表への登録対象から除外する処理であってもよい。【００４２】
さらにまた、インデックス算出部は、各特徴ベクトルの要素を離散化して得られる離散値に、誤差の見積もりの範囲を満たす離散値を含めることによりインデックスを算出するようにしてもよい。即ち、各特徴ベクトルの要素の値と変動の推定値から算出した値の範囲が、複数の区間にまたがる場合、各区間に対応する離散値を用いて複数のインデックスを算出するようにしてもよい。【００４３】
前記ハッシュ表に登録される画像参照用データは、各特徴ベクトルを含むデータベース中の画像を識別する画像ＩＤと当該特徴ベクトルの要素とからなり、投票部は、入力画像の各特徴ベクトルと当該特徴ベクトルから算出されるハッシュ表のインデックスに登録された各特徴ベクトルとの間の距離計算を行い、最短距離の特徴ベクトルの画像ＩＤで識別される画像に投票してもよい。また、この際には、最短距離が一定の閾値以下の場合のみに投票してもよい。【００４４】
あるいはまた、前記ハッシュ表に登録される画像参照用データは、各特徴ベクトルを含むデータベース中の画像を識別する画像ＩＤからなり、投票部は、入力画像の各特徴ベクトルから算出されるハッシュ表のインデックスに登録された画像ＩＤで識別される画像に投票してもよい。
ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。
【図面の簡単な説明】
【００４５】
【図１】従来技術のPCA-SIFTによって得られる特徴ベクトルの値分布を示すグラフである。
【図２】従来技術のANNによる近似最近傍探索の概念を示す説明図である。
【図３】この発明に係るデータ登録において、ハッシュへの登録時に衝突が生じた場合の処理を示す説明図である。
【図４】この発明に係る実験に用いた登録画像の一例を示す説明図である。
【図５】この発明に係る実験に用いた検索質問画像の一例を示す説明図である。
【図６】従来技術のANNを用いて、許容誤差εを2から100まで変化させたときの認識率ならびに処理時間の実験結果を示すグラフである。
【図７】従来技術のLSHを用いて、変換後のベクトルの次元数kとハッシュ関数の数Ｌを変化させたときの認識率ならびに処理時間の実験結果を示すグラフである。
【図８】距離計算ありの本発明の手法を用いて、衝突の閾値cを変化させたときの認識率ならびに処理時間の実験結果を示すグラフである。
【図９】距離計算ありの本発明の手法を用いて、処理の対象となる次元数ｂを変化させたときの認識率ならびに処理時間の実験結果を示すグラフである。
【図１０】距離計算なしの本発明の手法を用いて、衝突の閾値cを変化させたときの認識率ならびに処理時間の実験結果を示すグラフである。
【図１１】距離計算なしの本発明の手法を用いて、処理の対象となる次元数ｂを変化させたときの認識率ならびに処理時間の実験結果を示すグラフである。
【図１２】本発明の各手法と従来技術の各手法の特徴を比較するため、パラメータをさまざまに変え、横軸に認識率、縦軸に処理時間を描いたグラフである。
【図１３】本発明の各手法ならびに従来手法における撮影角度と認識率との関係を示すグラフである。
【図１４】距離計算なしの本発明の手法を用いて、登録画像数と認識率ならびに処理時間との関係を示すグラフである。
【図１５】本発明の画像認識装置のうち、距離計算なしの手法に対応する構成例を示すブロックである。
【図１６】本発明の画像認識装置のうち、距離計算ありの手法に対応する構成例を示すブロックである。
【図１７】本発明において、特徴ベクトルの各次元の値の変動に対処した離散化の方法を示す図である。
【図１８】本発明の一態様として、識別器を多段階に縦列接続した構成を示すブロック図である。
【図１９】従来の手法について、近似最近傍探索の精度と画像の認識率との関係を示すグラフである。
【図２０】本発明による距離計算ありの手法において、bと認識率、処理時間の関係を示すグラフである。
【図２１】本発明による距離計算なしの手法において、bと認識率、処理時間の関係を示すグラフである。
【図２２】リジェクトをしない場合、本発明による手法と従来手法との特性比較をするため、各手法について認識率と処理時間との関係を示すグラフである。
【図２３】距離計算ありの識別器を多段階に縦列接続して構成する、本発明による画像認識装置を示すブロック図である。
【図２４】距離計算なしの識別器を多段階に縦列接続して構成する、本発明による画像認識装置を示すブロック図である。
【符号の説明】
【００４６】
１０    識別器
１１    特徴点抽出部
１３    インデックス算出部
１５、３５    画像データベース
１６    暫定最近傍データベース
１７、３７    ハッシュ表
１９    投票部
２１    投票テーブル
２３    画像選択部
２４    信頼性判定部
３８    特徴点照合部
【発明を実施するための最良の形態】
【００４７】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。【００４８】
この実施形態では、まず、近似の程度を入力画像に応じて段階的に調節する手法（多段階化の手法）について説明する。各段階において、入力画像に応じた画像を識別する処理は、識別器によってなされるものとする。前記識別器は、方法の請求項でいうところの限定工程、探索工程および識別工程に相当する処理を行うものである。また、物の請求項およびプログラムの請求項でいうところの限定部、探索部および識別部に相当する部分である。
次に、前記識別器のより詳細な構成について説明する。【００４９】
≪多段階化の手法≫
1. 構成と要件
一画像を複数の特徴ベクトルで表現し、特徴ベクトルの近似最近傍探索と投票によって認識する場合、性能の限界は近似を行わない場合の認識率である。近似を行えばそれだけ高速化が実現できるが、一般に認識率は低下する。先に述べたように、このような近似の程度と認識率の関係は、認識対象の画像によって異なるため、認識率を保ちつつ処理時間を短縮するためには、近似の程度を適応的に調整する必要がある。【００５０】
問題は、認識に必要な近似の程度を、認識の前に推定することが容易ではない点である。この問題に対処する一手法は、近似の程度が異なる多数の識別器を用意して、それらの識別器の出力を見ながら、適切なものを選択することであろう。
処理効率を保ちつつ複数の識別器を利用する具体的な手法としては、近似最近傍探索に基づく識別器を多段階に縦列接続する構成が考えられる。図18は、識別器を多段階に縦列接続した構成を示すブロック図である。【００５１】
ここで、1からNの数字が付けられた矩形は識別器を表し、数字が若いほど近似が強いものとする。検索質問の入力画像から得た特徴ベクトルの集合は、まず1段目の識別器によって認識される。この段階で十分な証拠が得られれば、信頼性判定部で認識処理を打ち切って結果を回答する。一方、十分な証拠が得られなければ、特徴ベクトルの集合を、次段の、より近似の弱い識別器にかけて再度認識する。処理を繰り返して最後のN段まで到達しても十分な証拠が得られない場合には、最大得票数のものを回答するか、その画像についてはリジェクトするかのいずれかをとる。以上の処理によって、早い段階で処理が打ち切られる画像については大幅な効率化が期待できると共に、必要に応じて時間をかけた認識が可能となる。【００５２】
このような構成を採用する場合、要件となる事項は、
<１> 認識処理打ち切りの判定方法
<２>「難しい」画像に対しても処理効率を保つ方法
の2点である。<1>については、少ない計算量で、なるべく正確に判定することが望まれる。<2>は、後段まで認識処理を繰り返す画像についても、処理効率を低下させないための方策である。理想的には、多段階化した識別器でs段まで処理が進んだ場合の計算量が、s段目と同じ近似の程度を持つ識別器を単独で使った場合と同等であればよい。以下、各々について述べる。【００５３】
2. 認識処理打ち切りの判定方法
認識誤りを引き起こす画像には、そもそも得票数が少ない、得票数がある程度得られる場合でも第2位の候補と得票数に開きが殆どない、という性質がある。これらの点に着目すると、信頼性判定部の処理として，得票数を用いた次のような簡便な判定方法が考えられる。1位の得票数をV1、2位の得票数をV2とすると、V1>t, rV1>V2を同時に満たすならば、処理を打ち切って1位得票の画像を回答とする。ここで、tは得票数の閾値、rは1位と2位の得票数の比の閾値である。なお、最終段については、上式にかかわらず得票数最大の画像を認識結果とする場合と、上式を満たさない場合にはリジェクトとする場合の2通りがある。【００５４】
3. 「難しい」画像に対しても処理効率を保つ方法
近似の程度が異なるN個の近似最近傍探索器1,…,N（以後、単に探索器と呼ぶ）を考える。近似の程度は、探索器 (s-1)の方が探索器 sよりも強いとする。探索器 sを用いて、特徴ベクトルqiに対して近似最近傍探索を行った結果、距離計算の対象として得られる特徴ベクトルの集合をPi(S)とする。近似最近傍探索では、通常、近似の程度が強いほど、距離計算の対象となる特徴ベクトル数が少ないという性質がある。すなわち、すべてのiとsに対して|Pi(S)|≧|Pi(S-1)|が成り立つ。【００５５】
いま、これらの探索器に対して、次の2つの性質を考える。
定義 1. 単調性 すべてのiとsについて、
Pi(S)⊇Pi(S-1)                                (1)
が成り立つとき、近似最近傍探索器には単調性があるという。
定義 2. 差分検索性 近似最近傍探索器が差集合
Pi(S)−Pi(S-1)                                (2)
を効率的に求められるとき、差分検索性があるという。【００５６】
単調性を持つ探索器を用いて、図18の多段階識別器を構成する場合、s段目では、Pi(S)ではなく、前段との差分Pi(S)−Pi(S-1)を距離計算あるいは投票の対象とすることが考えられる。このように構成すると、1段目からs段目までで距離計算あるいは投票の対象となった特徴ベクトルの和集合は、探索器sを単独で用いた際の集合 Pi(S)と等しくなるため、距離計算あるいは投票の回数は同一となる。さらに、探索器が差分探索性を持つ場合には、多段階化を行っても計算量の増加を低く抑えることができる。【００５７】
距離計算を用いる場合の認識のプロセスを図23に沿って具体的に述べる。図23で符号10が付された枠内のブロックは、多段階識別器を構成する各段の識別器の詳細な構成を示す。処理が(s-1)段目まで進んでいるときには、各特徴ベクトルqiに対する暫定最近傍pi*が見つかっており，それが暫定最近傍データベース16に記録されている。従って、s段目では、差分ハッシュキー計算によってpi∈(Pi(S)−Pi(S-1))という差分の特徴ベクトルを得、それらに対してのみqiとの距離計算を行い、pi*よりも距離の近いベクトルが見つかれば、それを新たに暫定最近傍pi*として暫定最近傍データベース16に登録するとともに、投票をやり直せばよい。【００５８】
距離計算を用いない場合の認識のプロセスを図24に沿って具体的に述べる。処理が(s-1)段目まで進んでいるときには、各特徴ベクトルqiに対してその段までで得られたハッシュキーによって投票が終了している。従って、s段目では、差分ハッシュキー計算によってpi∈(Pi(S)−Pi(S-1))という差分の特徴ベクトルを得、それらに対してのみ追加で投票を行えばよい。
なお、図24で符号10が付された枠内のブロックは、多段階識別器を構成する各段の識別器の詳細な構成を示す。また、図23、24の信頼性判定部24は、図15、16の画像選択部23の機能を包含している。信頼性判定部24は、ｓ段目までの投票結果で十分な信頼性が得られた場合、認識結果とすべき画像を決定する（画像選択部23の機能に対応）。しかし、十分な信頼性が得られなかった場合は、さらに次の段（s+1）段目に進むべきであると判定する。最終段（N段目）まで進んでも十分な信頼性が得られなかった場合はその結果をリジェクトすると判定する。【００５９】
≪識別器の構成≫
識別器として、以下の概念に基づく手法を提供する。この実施形態では、局所記述子としてPCA-SIFTを用いる。PCA-SIFTを用いる場合の最近傍探索手法として、発明者らは、従来のANNやLSHよりも高速な手法をこの発明の一側面として提案する。発明者らの最近傍探索手法は、後述するように単調性ならびに差分検索性を持つため、多段階化にも極めて好適である。そこで、多段階化の実施形態においては、発明者らの手法を識別器として適用した構成について説明する。【００６０】
ただし、前述の多段階化の手法は、発明者らの手法との組み合わせに必ずしも限定されるものでなく、単調性ならびに差分検索性を満足するものであれば、従来の最近傍探索手法を適用した識別器でもある程度の効果が得られるものと考えられる。たとえば、単調性はANNやLSHでも満たされる。ANNでは、後述する許容誤差εの値を段階的に変更する場合に単調性が満足され、LSHでは、検索するハッシュ表の数Lを段階的に増やす場合に単調性が満足される。即ち、従来の手法による識別器であっても、それを多段階化すれば１段階の場合よりも物体認識の処理時間を短縮し得る。また逆に、識別器に適用すべき発明者らの手法は、必ずしも多段階化する必要はない。１段階の識別器であっても、従来の手法による識別器に比べて処理時間を短縮することができる。しかし、発明者らの手法を適用した識別器を多段階化すれば、より高速な物体認識が実現できる。従って、両者を組み合わせることが極めて好ましい。【００６１】
識別器に適用する発明者らの手法には、近似最近傍探索の最終段階で距離計算を行う手法（距離計算ありの手法）に加えて、距離計算を全く行わずに済ませる手法（距離計算なしの手法）がある。以下では、まず、距離計算ありの手法、距離計算なしの手法に共通のデータ登録について述べたあと、各々の手法、多段階化の方法について述べる。【００６２】
発明者らは、ハッシュ表を用いた2通りの高速化手法を開示する。
高速化の一つは、特徴ベクトルの距離計算の回数を減らす方法である。具体的には、近傍に多数の特徴ベクトルがあって、多くの距離計算が避けられないような場合、そのような特徴ベクトルを破棄することによって高速化を図る。以下、この手法を「距離計算あり」の手法という。もう一つは、距離計算を一切行わない手法である。処理としてはハッシュ表を引いて投票することだけを行う。以下、この手法を「距離計算なし」の手法という。【００６３】
この実施形態によれは、カメラで捉えた画像から物体を認識する処理、詳細には、局所記述子を用いた物体認識法において、認識処理に要する計算時間を従来技術より短縮することができる。あるいは、従来技術よりも少ないメモリ容量で処理を行うことができる。
また、この実施形態によれば、ANNやLSHという従来の近似最近傍探索法を用いる場合と比べて、同じ認識率を達成するために必要な計算時間が短くてよい。後述する実験例では、計算時間が、従来技術の1/2から1/3に短縮された。また、距離計算なしの手法は、メモリの使用量が少ないため、スケーラビリティという点でも優れている。【００６４】
≪構成の概要≫
図１５および図１６は、この発明の画像認識装置の構成例を示すブロック図である。図１５は、距離計算なしの手法に対応するブロック図であり、図１６は、距離計算ありの方法に対応するブロック図である。この発明の画像認識方法は、例えば、前記画像認識装置上で実行される。画像認識装置のハードウェアは、例えば、ＣＰＵと、ＣＰＵが実行する処理手順を示すプログラムを格納したハードディスク装置などの記憶装置、ＣＰＵにワークエリアを提供するＲＡＭ、データを入出力する入出力回路などから構成される。より具体的には、例えば、上記構成を有するパーソナルコンピュータであってもよい。あるいは、異なる態様として、機器組み込み型の装置として、大規模集積回路（ＬＳＩ）とハードディスク装置およびそれらの処理を制御するマイクロコンピュータから構成されてもよい。【００６５】
図１５で、特徴点抽出部１１は、入力画像に含まれる対象物のパターンから特徴ベクトルを抽出するブロックである。
インデックス算出部１３は、特徴ベクトルから所定の算出方法でハッシュ表のインデックスを算出するブロックである。画像データベース１５には、画像ＩＤが付された複数の画像が登録されている。また、画像データベース１５は、画像を参照するためのハッシュ表１７を有する。【００６６】
ハッシュ表１７は、複数のインデックスに対して、そのインデックスに対応付けられた画像の画像ＩＤが登録されている。各インデックスへの画像ＩＤの対応付けは次のようにしておこなわれる。まず、登録対象の画像は、特徴点抽出部１１と同様の処理によって特徴ベクトルが抽出される。抽出された各特徴ベクトルについて、インデックス算出部１３と同様の算出方法でハッシュ表のインデックスが算出される。このようにして算出されたインデックスに対して、インデックスを算出した特徴ベクトルを含む画像の画像ＩＤが予め登録されている。【００６７】
投票部１９は、前記ハッシュ表１７の特定のインデックスを参照し、参照したインデックスに対してハッシュ表１７に登録されている画像ＩＤがあれば、その画像に対して投票するブロックである。投票のために、各画像について得票数を記憶する得票テーブル２１が設けられている。
画像選択部２３は、得票テーブル２１を参照し、最大得票数を得た画像を選択するブロックである。【００６８】
図１５の画像認識装置に多段階化の手法を適用する場合、前述の各ブロックのうち、インデックス算出部１３、投票部１９および投票テーブル２１が多段階化の対象となる。【００６９】
図１６で、特徴点抽出部１１、インデックス算出部１３、投票部１９、投票テーブル２１、画像選択部２３は図１５と同様の機能を有している。画像データベース３５は、ハッシュ表３７の構成が図１５と異なる。即ち、ハッシュ表３７のインデックスには、登録された画像の各特徴ベクトルについて、ベクトルの要素とその特徴ベクトルが含まれる画像の画像ＩＤとが組で登録されている。ベクトルの要素は、距離計算に使用される。また、図１６の画像認識装置は、特徴点照合部３８を備える。特徴点照合部３８は、一つのインデックスに対して複数の特徴ベクトルが登録対象になっている場合、それらの特徴ベクトルと入力画像から抽出された特徴ベクトルとの距離計算を行って最短距離のものを決定し、最短距離の特徴ベクトルと共に登録された画像ＩＤを候補画像として決定するブロックである。【００７０】
図１６の画像認識装置に多段階化の手法を適用する場合、前述の各ブロックのうち、インデックス算出部１３、投票部１９、投票テーブル２１および特徴点照合部３８が多段階化の対象となる。
なお、図１５の画像認識装置では、参照されたインデックスに対して登録された全ての画像ＩＤに投票を行うので、特徴点照合部３８に対応するブロックは存在しない。【００７１】
≪特徴ベクトル≫
本実施形態で利用する特徴ベクトルについて述べる。
1. SIFT
SIFT (Scale-Invariant Feature Transform)とは、Loweによって提案された特徴点とそれに付随する特徴ベクトルの抽出法である（例えば、D.G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, vol.60, no.2, pp.91-110, 2004.参照）。その名が示す通り、画像の拡大縮小、回転や視点のずれに対して、ロバストであるという特徴を持つ。従来は処理時間が問題視されてきたが、GPU(Graphical Processing Unit)の利用によって、高速な処理が可能となりつつある。【００７２】
本実施形態では、Loweによって提供されているソフトウェア（URL：http://www.cs.ubc.ca/~lowe/keypoints/参照）を用いて特徴点を抽出する。特徴ベクトルは、128次元の整数値(0-255)のベクトルである。【００７３】
2. PCA-SIFT
Keらは、SIFTの特徴ベクトルに対して、主成分分析(PCA)を適用することにより、SIFTの安定性や識別性を向上させるPCA-SIFTを提案している（例えば、Y.Ke and R.Sukthankar, Pca-sift: A more distinctive representation for local image descriptors, CVPR2004, Vol.2, pp.506-513, 2004.参照）。本実施形態では、このPCA-SIFTを画像の局所記述子として利用する。PCA-SIFTによって得られる特徴ベクトルは、36次元の実数値ベクトルである。即ち、SIFTから得た特徴ベクトルに対して、URL：http://www.cs.cmu.edu/~yke/ pcasift/で提供されているソフトウェアを用いることにより，36次元のベクトルに変換される。【００７４】
後述する実験例に使った画像を用いてPCA-SIFTを計算すると、各次元は図1に示すような値の分布を持つことが分かった。図１は、特徴ベクトルの値分布を示すグラフである。横軸は各次元の値、縦軸は頻度である。
1次元目は双峰性の分布であり、2次元目以降は単峰性の分布を示す。また、次元が大きくなるにつれて分散が小さくなる。平均値はいずれも0の付近である。【００７５】
≪物体認識と近似最近傍探索≫
1. 投票による物体認識
画像データベースに多数の画像が納められており、各々の画像は１つの物体を表すものとする。認識対象の画像（以下、検索質問と呼ぶ）が与えられたとき、物体認識のタスクを、検索質問に最もマッチする画像をデータベースから検索することと定義する。【００７６】
この目的のため、本実施形態では投票方式を用いる。いま検索質問の画像をＱ、データベース中の画像をＰと表す。また、Ｑ，Ｐから得たｄ次元特徴ベクトルを、q, pと表す。近似最近傍探索の結果、qに対応する特徴ベクトルとして、pが得られたとすると、画像Ｐに1票を投じる。このような投票をＱから得られた全ての特徴ベクトルに対して実行し、最終的に得票数が最大となった画像を認識結果として提示する。【００７７】
このように、検索質問から得た個々の特徴ベクトルに対して、データベース中の全ての画像から得た特徴ベクトルとの間で近似最近傍探索を行うため、近似最近傍探索をどのように高速化するかがポイントとなる。本実施形態の説明の前に、まず、従来技術の代表的な手法であるANNとLSHについて簡単に述べる。【００７８】
2. ANN
非特許文献３に挙げたANN(Approximate Nearest Neighbor)は、木構造を用いて近似最近傍探索を高速に行う手法である。木のノードは、特徴空間を分割したhyperrectangle(以後、セルと呼ぶ)に対応しており、葉ノードには特徴ベクトルも対応つけられている。【００７９】
ANNによる近似最近傍探索の概念を図2に示す。ただし、簡単のため、説明に関与しないセルは描いていない。いま、qを検索質問の特徴ベクトル、p1, p2, p3をデータベース中の画像の特徴ベクトルとし、現在、p1が近傍のベクトルとして発見されているとする。最近傍探索を実行する場合、実線で示される超球と重なるセルには、p1より近傍の特徴ベクトルが存在する可能性があるため、探索の対象となる。一方、近似最近傍探索を行う場合、p1までの距離rに対して、許容誤差εを用いて定義される半径r／(1+ε）の超球を考え、それと交わるセルのみを探索の対象とする。これにより、最近傍の特徴ベクトル(図2の場合はp3)を発見できない可能性は出てくるが、対象となるセルの数が減少するため、探索時間を削減できる。【００８０】
3. LSH
非特許文献４に挙げたLSH(Locality Sensitive Hashing)は、ハッシュ表を用いた近似最近傍探索の手法である。ここでは、実験で用いるE2LSH (Exact Euclidean LSH; 以後単にLSHと呼ぶ)について述べる。
d次元ベクトルp=(x1,…, xd)を考える。LSHでは、一つの特徴ベクトルをＬ通りのｋ次元ベクトルに変換し、各々に対応するＬ個のハッシュ表に登録する。検索時には、検索質問の特徴ベクトルqを用いて、全てのハッシュ表を検索し、得られた特徴ベクトルp1,…, psの中からqとのユークリッド距離が最小のものを結果とする。このように複数のハッシュを用いることによって、良い近似最近傍の特徴ベクトルが安定的に求められる。【００８１】
もう少し具体的に見てみよう。処理は検索質問の特徴ベクトル、データベース中の特徴ベクトルに共通するので、一般に特徴ベクトルをvで表す。vは、次の手順で生成されたＬ個の関数g1(v),...,gL(v)を用いて、対応するＬ個のハッシュ表に格納される。個々のgj(v)は、ｖをgj(v)=(h1(v),…,hk(v))のようにｋ次元ベクトルに変換するものである。hi(v)は、ｖを整数に変換する関数であり、次のような形を持つ。【００８２】
【数１】
2008026414.tif 000003
ここで、aiは、各次元が独立に正規乱数に従って生成されたd次元ベクトルであり、tiは[0,w]の一様乱数によって定められるスカラである。このような値を用いることによって、v1とv2のユークリッド距離が小さければ、それだけhi(v1)=hi(v2)となる可能性が高いという効果を実現できる。
LSHでは、i=1,…,kのk個の異なるai，tiを用いてk次元ベクトルとすることにより、ユークリッド距離の離れたｖが同じベクトルとならないようにしている。一方で、Ｌ個のgjを用いることにより、ユークリッド距離の近いｖが対象から漏れてしまうことを防いでいる。
以上が、従来技術を代表するANNならびにLSHの説明である。次に、この発明の手法について説明する。【００８３】
≪衝突の削減による高速近似近傍探索≫
1. 考え方
物体の局所的な特徴を捉えた特徴ベクトルを用いて、投票処理によって物体を認識する場合、検索質問の特徴ベクトルに対して、必ずしも最近傍の特徴ベクトルをデータベースから発見する必要はなく、特徴ベクトルに付与された画像のラベルが正解のものであればよい。さらに、認識結果が投票によって決定されるため、正解の得票数が逆転しなければ、誤った票が他の画像に入っても問題は生じない。このような特性を活かして、本発明では、大幅な近似を施すことにより、ANNやLSHを用いる場合と比べて高速な処理を実現する。【００８４】
ANNやLSHを用いる場合、最も計算時間が必要な部分は、qとpjの距離計算である。従って、これをいかに削減するかがポイントとなる。ただし、検索の精度（認識率）が著しく低下したり、必要なメモリ量が大幅に増大すると問題となる。【００８５】
本発明では、データの特性を活かしたハッシュ関数を用いることによって、高速化の問題を解決する。手法としては次の2通りを考える。一つは、距離計算を行うが、その対象となる特徴ベクトルの数を削減する方法である。具体的には、多数の衝突が生じている場合、すなわち、同じハッシュ値を持つ特徴ベクトルが多数登録されているとき、それらを予めハッシュ表から消去する。これにより、検索質問の特徴ベクトルあたりの距離計算回数を一定値以下に削減することが可能となる。もう一つは、全く距離計算を行わない方法である。衝突回数に応じた消去を行うと、ハッシュ表には画像を識別する上で効果的な特徴ベクトルが残ることになる。そこで、これらの特徴ベクトルを用いれば、投票のみでも正しい結果が得られると期待できる。【００８６】
2. データ登録
まず、本発明の2通りの手法に共通のデータ登録について述べる。本発明の手法と同様にハッシュ表を用いるLSHでは、ハッシュ表の数が多くなると大量のメモリを消費する。
そこで本実施形態では、メモリ量を削減するため、ハッシュ表を1つだけ使うこととする。
特徴ベクトルをハッシュ表に登録する方法は次のとおりである。PCA-SIFTによって得られた36次元の実数値ベクトルpの第1次元から第d次元までをとり、【００８７】
【数２】
2008026414.tif 000004
とする。次に、【００８８】
【数３】
2008026414.tif 000005
によって各次元を離散化し、自然数を要素とするベクトルu=(u1,…,ud)を作成する。そして、【００８９】
【数４】
2008026414.tif 000006
【００９０】
によってハッシュのインデックスを求め、ハッシュ表に登録する。ここで、Uは離散値の種類（U進数で表現）、Ｈsizeはハッシュ表のサイズである。ハッシュ表に登録するデータは、距離を用いるか否かによって異なる。距離を用いる場合には、特徴ベクトルpに対する画像ＩＤのほか、pそのものを登録し、検索時の距離計算に用いる。一方、距離を用いない場合には、pの登録は不要である。
特に、２値で離散化する場合（２進数で表現する場合）には、閾値T0=0を用いて、【００９１】
【数５】
2008026414.tif 000007
によって各次元を2値化し、ビットベクトルu=(u1,…,ud)を作成する。そして、【００９２】
【数６】
2008026414.tif 000008
【００９３】
によってハッシュのインデックスを求め、ハッシュ表に登録する。ここでＨsizeは、ハッシュ表のサイズである。ハッシュ表に登録するデータは、距離を用いるか否かによって異なる。距離を用いる場合には、特徴ベクトルpに対する画像ＩＤのほか、pそのものを登録し、検索時の距離計算に用いる。一方、距離を用いない場合には、pの登録は不要である。【００９４】
登録時に衝突が生じた場合は、図3のように、チェイン法により複数の特徴ベクトルをリストとして登録する。このとき、リストが長くなりすぎると、距離計算のコストがかかりすぎるという問題が生じる。そこで本実施形態では、リスト長nに対する閾値cを設け、n＞c を満たすとリスト全体をハッシュ表から削除する。なお、予備実験として、情報検索で用いられる各種の重み付けも試したところ、認識率にあまり大きな差はなかった。削除は認識率だけではなく、速度にも有利であるため、本実施形態では重み付けではなく削除を採用している。同じハッシュ値を持つ特徴ベクトルが多いということは、その特徴ベクトルが画像の識別にあまり寄与しないことを意味する。従って、削除をしても影響は比較的少ないと考えられる。
以上の処理を、データベースに登録する全ての特徴ベクトルに対して施すことにより、データの登録は完了する。【００９５】
3. 距離計算を用いる方法
次に距離計算を用いる検索について述べる。本実施形態では、検索質問Ｑから得た各特徴ベクトルqに対して、上記のハッシュ表から特徴ベクトルを検索する。得られた特徴ベクトルの集合をＰとすると、次にＰの中からqの最近傍となる特徴ベクトルp*を求める。
そして、2つの特徴ベクトルの距離dist(q,p*)が【００９６】
【数７】
2008026414.tif 000009
を満たす場合、p*に対応する画像ＩＤに投票する。ここでdmaxは距離の閾値である。ただし、dmax=∞とすると、距離によらずp*に投票する。【００９７】
この処理において、最も重要なステップは、いかにqに対する特徴ベクトルを検索するかにある。最も単純な手法は、登録時と同様にqに対してもビットベクトルを求め、ハッシュ関数によって同じハッシュ値を持つ特徴ベクトルを求めることである。ところが、このような処理では、距離の計算回数は十分削減できるものの、次の理由によって十分な認識率を得ることができない。特徴ベクトルの各次元の値は撮影条件によって変動することがある。もし、閾値を超えるような変動があると、ビットベクトルが異なるものとなり、もはや対応する特徴ベクトルを得ることができなくなる。【００９８】
LSHでは同様の問題に対処するため、式(1)において、一様乱数tを値に加えることにより、閾値付近の値をランダムに移動させている。また、前記非特許文献６に挙げた小林らの手法では、特徴ベクトルに回転行列をかけることで、閾値の相対的な位置を変化させている。
本実施形態では、値の変動幅eをパラメータとして、変動への対処を施す。具体的には、q=(x1,…, xd)とし、離散化のための閾値をTi(i=0,1,…,z)とするとき、区間【００９９】
【数８】
2008026414.tif 000010
と区間【０１００】
【数９】
2008026414.tif 000011
【０１０１】
が重なりを持つとき、各区間に対応する離散値（式(4)の場合は0, 式(5)の場合はi+1、dの場合はz+1）を割り当てる。ここで、zはiの最大値である。また、eの値によっては、割り当てられる離散値が複数であることに注意する。【０１０２】
図１７に示す例を考える。この場合、重なりを持つ区間は[T0,T1),[T1,T2),[T2,T3)の3個になるため、qjに割り当てられる離散値としては、各々対応する1,2,3の３通りとなる。
ただし、このような「様々な可能性を試す」という処理を制限なく導入すると、膨大な計算時間が必要となってしまう。そこで本実施形態では、処理の対象となる次元数bをあまり大きくない値に留めることとする。なお、３値以上に離散化した場合、必ずしも処理対象の次元の可能な全ての離散値をインデックスの計算に用いる必要はない。例えば、図１７においてインデックス計算に用いる離散値をランダムに選び、１と２のみを用いる処理であってもよい。
特に特徴ベクトルの各次元の値を２値に離散化する場合には、各次元qjの値が【０１０３】
【数１０】
2008026414.tif 000012
を満たす次元jに対しては、ujだけではなく【０１０４】
【数１１】
2008026414.tif 000013
【０１０５】
も用いて、特徴ベクトルを検索する。ただし、このような「両方試す」という処理を制限なく導入すると、膨大な計算時間が必要となってしまう。この処理では、処理の対象となる次元数をbとすると、2b通りのビットベクトルを用いてハッシュ表にアクセスすることになる。そこで本実施形態では、bをあまり大きくない値に留めることとする。【０１０６】
【数１２】
2008026414.tif 000014
【０１０７】
を満たす次元の数がbを上回るときには、次元のインデックスが小さいものからb個を採用する。なお、対象となる次元を、確率的に決めることも考えられる。ただし、実際に試したところ、認識率にはほとんど差が出ず、計算時間が余分に必要であった。
なお、このような変動への対処は、検索時ではなく登録時に行うことも可能である。具体的には、登録の際に同様にビットベクトルを2b個作成し、ハッシュ表に登録する。こうすると、検索時に複数のビットベクトルを用いてハッシュ表にアクセスする必要がなくなるため、処理時間の短縮が期待できる。しかしながら、多数の特徴ベクトルを登録するため、メモリへの負担は大きくなる。予備実験の結果、処理時間には大きな差がなく、メモリへの負担が目立ったため、本実施形態では、検索時に変動に対処することとした。【０１０８】
4. 距離計算を用いない方法
距離を用いない方法では、検索質問の特徴ベクトルqに対して上記のような距離計算を施して近似最近傍を求めるのではなく、ハッシュ表から得た特徴ベクトルの集合Ｐに属する全ての特徴ベクトル【０１０９】
【数１３】
2008026414.tif 000015
に対して投票処理を施す。処理のパラメータは、距離を用いない方法と同様、特徴量の変動幅e、変動に対処する次元の数bの2つである。【０１１０】
≪bによる多段階化≫
発明者らの手法のパラメータはb,c,d,eの4つである。この実施形態では、このうちbを変更することで近似の程度を調整する。具体的には、第s段ではb=s-1とした識別器を用いる。発明者らの手法は、bの増加に伴ってハッシュ表のアクセスに用いるインデックスが増加するだけである。そのため、単調性だけではなく差分探索性も満たす。【０１１１】
ただし、多段化するパラメータは、bに限定されるものではない。他のパラメータによる多段化も可能である。例えば、パラメータdは、単調性だけではなく差分探索性も満たすことが明らかである。c,eについてもその可能性がある。【０１１２】
なお、距離計算なしの手法では、各段の処理で、暫定最近傍pi*を更新しつつ投票するのではなく、得られた差集合Pi(S)−Pi(S-1)に属する特徴ベクトルすべてに対して投票する。【０１１３】
（実験例）
本発明の手法の有効性を検証するため実験を行った。まず、発明者らの手法を適用した識別器と、従来の手法による識別器との比較実験を説明する。【０１１４】
≪実験１≫
1. 実験条件
1.1. 画像データベース
最初に、実験に用いる画像について説明する。まず、収集方法の異なるA，B，Cの3種類のデータセットを準備した。図４は、実験に用いた登録画像の一例を示す説明図である。Aは、Googleのイメージ検索を用いて収集した3,100枚の画像である。検索キーワードとしては、ポスター、雑誌、表紙などを用いた。図4(a)に例を示す。【０１１５】
BはPCA-SIFTのサイト（URL：http://www.cs.cmu.edu/~yke/pcasift/）で公開されている画像であり、画像数は18,500枚である。このデータは主に自然写真や人物の写真などで構成されている。図4(b)に例を示す。Cは、写真共有サイトのflickrにおいてanimal，birthday，food，japanなどのタグにより収集した78,400枚の画像からなる。主に図4(c)に示すような物体や自然の写真、人物の写真などを含む。なお、収集の際には、600×600 pixel以下のサイズの画像は除外し、画像の長辺が640 pixel以下になるように縮小した。また、特徴ベクトルが100個以下の画像も除外した。画像の一辺の長さの平均はA, B, Cそれぞれ498, 612, 554 pixelであった。【０１１６】
次に、A, B, Cの画像を用いて、表1に示した画像数からなるデータベース、DB1, ..., DB5を作成し、実験に用いた。【０１１７】
【表１】
2008026414.tif 000016
ここで、大きいデータベースは、小さいデータベースをその一部として含む。なお、DB3からは、一画像あたり平均2,069個の特徴ベクトルが抽出された。【０１１８】
1.2. 検索質問画像
検索質問として、次の手順で作成した画像を2,000枚用いた。まず、DB1に含まれる画像の中でA，B，Cから、それぞれ100，200，200枚を無作為に選択し、A4の紙面に印刷した。次に、カメラを用いて印刷した紙面を撮影した。撮影した画像（検索質問画像）の例を図5に示す。図に示す通り、紙面全体が写る配置で、紙面に対するカメラの光軸の角度θを90°, 75°, 60°に変化させた。また、角度を90°として紙面の一部分を撮影した。その結果、1枚の紙面に対して、合計4通りの画像を得た。さらに、撮影した画像を512×341pixelに縮小し、PCA-SIFTにより特徴ベクトルを求めた。その結果、画像一枚あたり平均605個の特徴ベクトルが得られた。なお、印刷にはOKI（登録商標） C5200n(カラーレーザプリンタ)、撮影にはCANON（登録商標） EOS Kiss（登録商標） Digital（630万画素）と付属のレンズEF-S 18-55mm USMを用いた。【０１１９】
1.3. 評価
実験では、近似最近傍探索の比較手法としてANNとLSHを用い、本発明の手法と比較した。なお、ANNとしてはURL：http://www.cs.umd.edu/~mount/ANN/, LSHとしてはURL：http://www.mit.edu/~andoni/ で提供されているプログラムを用いた。評価基準としては、認識率と処理時間を用いた。認識率は、検索質問の画像が正しく認識できた割合を表す。また、処理時間は、検索質問の画像1枚あたりの検索に要した時間を表す。ただし、特徴ベクトルの抽出に必要な時間は含めていない。なお、実験に用いた計算機は、CPUが AMD Opteron（登録商標） 2.8GHz、メモリが16GBのものである。
なお、実験を通して、本発明の手法では、離散化はすべて２値（U=2）とし、T0=0とした。また、距離計算ありの手法での距離の最大値の閾値dmaxは3,000に固定した。【０１２０】
2. DB3を用いた比較実験
まず、DB3を用いて各手法のパラメータと認識率、処理速度の関係について述べる。
2.1. ANN
ANNを用いて、許容誤差εを2から100まで変化させたとき認識率および処理時間の実験結果を図6に示す。εの増加に伴って、認識率、処理時間が減少していることが分かる。
εが2から10程度までは、処理時間の減少に比べ、認識率の減少は緩やかである。【０１２１】
2.2. LSH
図7に、LSHを用いて変換後のベクトルの次元数kとハッシュ関数の数Ｌを変化させたときの認識率および処理時間の実験結果を示す。まず、Ｌの増加に伴って、認識率、処理時間が増加していることが分かる。Ｌを更に増加させると、認識率を向上させることができると考えられるが、メモリ不足により実行できなかった。また、図示されているもの以外にも種々のkについて試したところ、kを減少させると、認識率は改善するものの、処理時間が増大することが分かった。この理由は、kが小さいと、距離計算の対象となる特徴ベクトルの数が増加するためであると考えられる。【０１２２】
2.3. 本発明の手法(距離計算あり)
距離計算ありの本発明の手法を用いて、衝突の閾値cと認識率、処理時間の関係について調べた。このとき、ハッシュ表のサイズとしてはＨsize=2dとした。e=200, b=7, d=24,26, 28とし、cを変化させたときの認識率および処理時間の実験結果を図8に示す。cが減少するにつれ、処理時間が減少していることが分かる。ただし、cを小さくしすぎると、認識率が低下した。これは、認識に寄与していたものも削除してしまったためと考えられる。一方、cを増加させた場合に、計算時間は増加するものの、認識率が減少することはほとんどなかった。これは、最近傍にはなり得ない特徴ベクトルを検索したとしても、距離計算によって排除可能なためと考えられる。【０１２３】
また、bと認識率、処理時間の関係について調べた。ハッシュのインデックスを求めるために使用する次元をd=26とした上で、e=200, 500, 1000、c=∞とし、bを変化させた結果を図9に示す。bを増加させると処理時間は増加するものの、認識率が向上することが分かる。bが比較的小さい場合は、e=200の場合に認識率が高い。【０１２４】
2.4. 本発明の手法(距離計算なし)
次に、距離計算なしの本発明の手法を用いて、cと認識率、処理時間の関係について調べた。d=24, 26,28、e=200、b=5とし、cを変化させた結果を図10に示す。d=24, 26, 28の値について、それぞれc=2, 3, 4という小さい値のときに認識率が最大となった。これは、距離計算を用いない手法では、cが大きくなるにつれて、最近傍にはならない特徴ベクトルが多数投票に関与するためと思われる。図8に示した距離計算を用いる場合と好対照であることが分かる。【０１２５】
また、bと認識率、処理時間の関係についても調べた。d=28, e=200, c=2とし、bを変化させた結果を図11に示す。b=5までは、bの増加に伴って認識率が向上しているが、それ以上bが増加すると、認識率は低下している。これは、bの増加によって、最近傍とはなり得ない不適切な特徴ベクトルを介した投票が増大したためと考えられる。図9の距離を計算するものでは、bを増加させた場合に、認識率が減少することはなかった点を考えると、同様に好対照であるといえる。【０１２６】
2.5. 各手法の比較
各手法の特徴を比較するため、パラメータをさまざまに変え、横軸に認識率、縦軸に処理時間を描いたグラフを図12に示す。ANNでパラメータを変化させたものを線で描き、評価の基準とした。右にプロットされているものほど認識率が高く、下にプロットされているものほど処理時間が短い。そのため、右下にプロットされているものほど優れていると言える。LSHは、ほぼANNの線を越えることはなかった。本発明の手法で距離の計算を行うものは、認識率が98%以下の場合は、ANNよりも優れていた。本発明の手法で距離の計算を行わないものは、ほとんどの場合でANNより優れていた。【０１２７】
次に、各手法における撮影角度と認識率の関係を調べた。処理時間がおよそ10msで認識率の最も良いものを図13に示す。パラメータは、ANN e=40、LSH k=20, Ｌ=15、距離計算ありの手法 e=200, b=4, c=8, d=24、距離計算なしの手法 e=200, b=5, c=2, d=28である。ただし、距離計算なしの手法による処理時間は3.4msのものを示している。距離計算ありの手法は、同じ処理時間で、ANN、LSHと比べ高い認識率が得られていることが分かる。距離計算なしの手法では、θ=60°の場合を除くと、1/3の処理時間でANNと同程度の認識率を得られることが分かる。
各種パラメータの代表的な値を用いた認識率と処理時間を表2に示す。【０１２８】
【表２】
2008026414.tif 000017
【０１２９】
距離計算ありの手法は、ANNに比べ同程度の認識率を、1/3程度の処理時間で実現していることが分かる。一方、距離計算なしの手法では、平均の認識率はANNに及ばない。ただし、その原因はθ=60°の場合に認識率が低いことにある。θ≧75°に限定できる状況では、96%程度の認識率を4ms以下という短い処理時間で実現可能であることが分かる。【０１３０】
3. DB1-DB5を用いた実験
距離計算なしの手法を除く全ての手法では、検索のために元の特徴ベクトルのデータを保持しなければならないため、DB4, DB5のデータについては、メモリ不足で検索を実行できなかった。一方、距離計算を用いない手法は、ハッシュ表に画像ＩＤのみを登録すればよいため、メモリへの負担が少なく、10万画像までの実験を行うことができた。そこで、e=200, d=28とし、bとcを変化させ、登録画像数と認識率、処理時間の関係について調べた。最も認識率のよいものを図14に示す。そのときのbは、DB1から順に5, 6, 5, 6, 5で、cは1, 1, 2, 4, 5であった。登録画像数を10万件に増加させた場合でも、認識率87.3%、処理時間20.6msを得た。θ=60°の場合を除外すると認識率は91.4%となる。【０１３１】
このように、距離計算を用いない手法は、認識率という点では他に及ばないものの、ある程度の認識率で満足できる場合には、スケーラビリティという点で優れた手法といえる。また、処理がハッシュ表へのアクセスと投票という単純なものであるため、この面での利点もあると考えられる。
続いて、近似最近傍探索の従来法であるANN、LSHに加え、距離計算ありの手法を用いて１段の識別器を構成し、発明者らの手法を適用した多段階の識別器を用いる場合と比較した。【０１３２】
≪実験２≫
1. 実験条件
局所記述子としては、PCA-SIFTのサイトで提供されるものを用いた。ハッシュ表のサイズはHsize=2dとした。以下に示す処理時間は、検索質問の画像1枚あたりの認識に要した時間を表す。ただし、特徴ベクトルの抽出に必要な時間は含めない。使用計算機は、実験１と同じ構成のものである。また、この実験では、図２３に示す多段階識別器を用いた。【０１３３】
1.1. 画像データベース
画像データベースの画像は、実験１と同様の出所から収集したが、その数は、Googleのイメージ検索を用いて収集した画像が3,100枚、PCA-SIFTのサイトで公開されている画像が3,450枚、写真共有サイトのflickrにおいてanimal，birthday，foodなどのタグにより収集した画像が3,450枚、合計10,000枚の画像である。【０１３４】
1.2. 検索質問画像
検索質問としては、データベースに対応する画像のあるものとないものの2種類を作成した。前者については、データベースに含まれる画像の中から、収集方法ごとに100，200，200枚の合計500枚を無作為に選択した。後者については、画像データベースには含まれない画像を199枚用意した。次に、これらをA4の用紙に印刷し、カメラを用いて撮影した。実験１と同様、紙面全体が写る配置で、紙面に対するカメラの光軸の角度θを90°,75°,60°に変化させた。また、角度を90°として紙面の一部分を撮影した。その結果、1枚の紙面に対して、合計4通りの画像を得た。さらに、撮影した画像を512×341pixelに縮小し、PCA-SIFTにより特徴ベクトルを求めた。その結果、画像1枚あたり平均612個の特徴ベクトルが得られた。【０１３５】
2. リジェクトをしない場合
まず、対応する画像がデータベースにある検索質問のみを用いて、実験を行った。
2.1. 近似最近傍探索の精度と画像の認識率の関係
最初に、予備実験として、画像を認識するために必要な最近傍探索の精度を調べた。具体的には、多段階化なしの手法(ANN，LSH，距離計算ありの手法)について、パラメータをさまざまに変え、近似最近傍探索の精度と画像の認識率の関係を計測した。近似最近傍探索の精度とは、近似最近傍探索によって真の最近傍が求まった割合である。【０１３６】
結果を図19に示す。この結果から、近似最近傍探索の精度が100%から20%あたりまでは、近似最近傍探索の精度が減少しても、認識率はほとんど減少しないことが分かる。これは、間違って他の画像に投票されてしまっても、正解の画像と他の画像の得票数が逆転するまでには至らないためであると考えられる。また、近似最近傍探索の精度と認識率には、手法に依存しない関係があることも伺える。【０１３７】
2.2. 多段階化による処理の削減
【表３】
2008026414.tif 000018
【０１３８】
次に多段階化の効果を検証する。まず、距離計算ありの手法を用いて、bと認識率と処理時間の関係について調べた。e=200,c=5,d=28,t=2,r=0.5とし、bを変化させた結果を図20に示す。多段階化を行う場合は、行わない場合と比較し、ほとんど認識率が低下せずに、処理時間を削減できることが分かる。また、多段階化の段数(N=b+1)が多くなるにつれて、処理時間削減の効果が大きくなっていることが分かった。
同様に、距離計算なしの手法を用いて、bと認識率と処理時間の関係について調べた。e=200,c=3,d=28,t=2,r=0.5とし、bを変化させた結果を図21に示す。距離計算なしの手法でも、処理時間を削減できることが分かった。【０１３９】
2.3. 各手法の比較
各手法の特徴を比較するため、パラメータをさまざまに変え、認識率と処理時間の関係を描いたグラフを図22に示す。ANNで許容誤差εを変化させたものを線で描き、評価の基準とした。右にプロットされているものほど認識率が高く、下にプロットされているものほど処理時間が短い。そのため、右下にプロットされているものほど優れているといえる。LSHは、ほぼANNの線を越えることはなかった。距離計算ありの手法では、最大認識率はANNに及ばないものの、認識率が98%以下の場合には、同じ認識率を、ANNに比べて1/10から1/40程度の処理時間で実現できている。提案手法では、多段階化を行うことで、処理時間が距離計算ありの手法の1/5程度にまで削減されている。【０１４０】
3. リジェクトをする場合
次に、リジェクトをする場合の実験結果について述べる。評価尺度を次の様に定める。対応する画像のある検索質問に対しては、認識率C1、誤認識率E1、リジェクト率R1 (C1+E1+R1=1)とする。対応する画像のない検索質問に対しては、誤認識率E2、リジェクト率R2(E2+R2=1)とする。【０１４１】
まず、距離計算ありの提案手法を用いて、10-fold cross validationにより、実験を行った。学習サンプルに対し、E1＝0, E2=0という条件の下で、R1が最小となるパラメータを求め、テストサンプルに適用した(基準A)。また、これとは別に、E1+E2+R1が最小となるパラメータも学習サンプルに対して求め、テストサンプルに適用した(基準B)。パラメータとしてはb=5,10,d=24,28,e=200,400，c=5, t=4,8,12，r=0.2,0.4,0.6のすべての組み合わせについて試した。距離計算なしの提案手法については、パラメータにc=2を追加し、同様に実験を行った。【０１４２】
結果を表3に示す。基準Aでパラメータを設定した場合、距離計算ありの提案手法では、リジェクト率R1が12.15%の場合に誤認識率E2を0%とすることができた。このときに誤認識率E2は0%とはならなかったものの、0.25%と低い値を得ることができた。また、基準Bでパラメータを設定した場合には、誤認識率の微少な増加と引き替えに、リジェクト率R1を1/3に抑えることができた。一方、距離計算なしの提案手法では、距離計算ありの提案手法と比べて劣る結果となった。【０１４３】
処理時間については、対応する画像のない検索質問の方が、4から9倍程度長くなった。これは、多段階化によって、対応する画像のない検索質問のほとんどは、最終段まで処理されてリジェクトされるのに対し、対応する画像のある検索質問は、最終段まで到達せずに回答が出力されているためである。【０１４４】
なお、この発明について、前述した実施の形態の他にも、この発明について種々の変形例があり得ることは明らかである。例えば、この発明は、平面物体以外にも適用することも考えられる。
本発明の範囲には、特許請求の範囲と均等の意味および範囲内でのすべての変更とが含まれることが意図される。
【産業上の利用可能性】
【０１４５】
この発明を用いた物体認識処理は、カメラで捉えた画像から物体を認識し、認識結果に応じた情報処理を行うサービスに適用することができる。前記情報処理の具体例としては、既存の画像やビデオ画像などに索引付けをおこなう処理などが考えられる。
【図１】
2008026414.tif 000019
【図２】
2008026414.tif 000020
【図３】
2008026414.tif 000021
【図４】
2008026414.tif 000022
【図５】
2008026414.tif 000023
【図６】
2008026414.tif 000024
【図７】
2008026414.tif 000025
【図８】
2008026414.tif 000026
【図９】
2008026414.tif 000027
【図１０】
2008026414.tif 000028
【図１１】
2008026414.tif 000029
【図１２】
2008026414.tif 000030
【図１３】
2008026414.tif 000031
【図１４】
2008026414.tif 000032
【図１５】
2008026414.tif 000033
【図１６】
2008026414.tif 000034
【図１７】
2008026414.tif 000035
【図１８】
2008026414.tif 000036
【図１９】
2008026414.tif 000037
【図２０】
2008026414.tif 000038
【図２１】
2008026414.tif 000039
【図２２】
2008026414.tif 000040
【図２３】
2008026414.tif 000041
【図２４】
2008026414.tif 000042
【国際調査報告】
2008026414.tif 000043
2008026414.tif 000044
2008026414.tif 000045
2008026414.tif 000046