JP5527555B2 - 画像データベースの作成方法、作成プログラム及び画像検索方法 - Google Patents

Description

この発明は、画像データベースの作成方法、作成プログラム及び画像検索方法に関する。より詳細には、局所特徴量を用いた特定物体認識に用いる画像データベースの作成方法、その作成方法をコンピュータが実行するためのプログラム及び前記画像データベースを用いた画像検索方法に関する。

特定物体認識(specific object recognition)とは、画像として写された物体が、他の画像中のどの物体とまったく同じなのかを言い当てる処理のことである。この明細書では、画像認識とも呼ぶ。このような処理は、部品の過不足の検出、偽造品などの検出、バーコードの代替などへの用途が考えられ、実用性が高いといえる。ここで、「画像として写された物体」とは検索質問としての画像に写っているインスタンス（検索対象）のことを指し、「どの物体とまったく同じなのかを言い当てる処理」とは、予め多数の画像が登録された画像データベースの中から、同一のインスタンスが写っている画像を検索する処理、即ち、画像検索の処理ということもできる。

前記特定物体認識の一手法として、局所特徴量(local feature)を用いる手法が知られている。この手法は、画像から所定の手順により抽出される局所特徴量でその画像を表現し、他の画像から抽出された局所特徴量と比較あるいは照合することにより、識別（認識）を行うものである。局所特徴量の例として、SIFT(Scale-Invariant Feature Transform、例えば、非特許文献１参照)や、PCA-SIFT(Principal Component Analysis-SIFT、例えば、非特許文献２参照)などがある。これらの局所特徴量は多次元のベクトル量として表現されるため、特徴ベクトルともいわれる。これらの手法の利点は、画像の局所的な特徴に基づいて多数の特徴ベクトルを抽出するため、検索質問中のインスタンスおよび／または前記画像データベースに登録された画像中のインスタンスに多少の隠れや変動があっても、高精度の認識ができる点にある。
この発明に関連する他の文献として、非特許文献３、４、５がある。それらの文献とこの発明との具体的な関連については後述する。

D. G. Lowe, "Distinctive image features from scale-invariant keypoints", Internal Journal of Computer Vision, 60, 2, pp.91-110, 2004. Y. Ke, and R. Sukthankar, "PCA-SIFT: A more distinctive representation for local image descriptors", Proc. CVPR'04, vol.2, pp.506-513, 2004. 野口, 黄瀬, 岩村: "局所記述子に基づく物体認識のため のメモリ削減の実験的検討", 画像の認識・理解シンポジウム (MIRU2008)論文集, OS10-3, pp.251-258, 2008. D. Nister and H. Stewenius, "Scalable Recognition with a Vocabulary Tree", Proc. CVPR2006, pp.775-781, 2006. S. Arya, D. 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.

1枚の画像から抽出される局所特徴量の数は、VGAサイズの画像で通常は数千程度、多い場合には数万にもなる。そのため、認識対象の画像のサイズが大きかったり数が多かったりする場合は、それらの局所特徴量の照合に要する処理時間や、記憶に必要となるメモリ容量が問題となる。

これらの問題を解決するため、個々の局所特徴量の記録に必要なメモリ容量を削減するというアプローチが提案されている（前記非特許文献３参照）。具体的には、特徴ベクトルの各次元の値を表す多値データのビット数を削減するスカラー量子化によって個々の局所特徴量を画像データベースに登録するために要するメモリ量を減らし、画像データベース全体のメモリ容量を削減している。この手法は、事前に特徴ベクトルの各次元の値の分布を調べておくことにより、スカラー量子化を比較的簡単に行うことができるというメリットがある。これに対して、ベクトル量子化という概念も提唱されている。D. Nisterらは、ベクトル量子化の方法の1つとして、Vocabulary Treeという木構造を使ったものを提唱している（例えば、非特許文献４参照）。しかしながら、この手法では高い認識率を維持するために、木構造の高さを高くしなければならず、削減効果が十分に見込めないという問題点もある。

この発明は、以上のような事情を考慮してなされたものであって、画像から抽出される局所特徴量を用いた近傍探索によって物体認識を行う手法において、前記物体認識の認識率を大きく低下させずに前記物体認識に係る画像データベースの記憶容量を削減する方法、および、その方法をコンピュータが実行するためのプログラムを提供するものである。また、前記方法に基づいて作成された画像データベースを用いて画像検索を行う方法を提供するものである。

この発明は、物体認識のために検索質問画像と照合されるべき参照画像の異なる位置の局所的特徴に対応し、各局所的特徴の位置と特性とをベクトル位置、ベクトル長及びベクトル方向として表す参照特徴ベクトルを前記参照画像から抽出する抽出工程と、異なる参照特徴ベクトルからなる複数のクラスタを、各参照ベクトルがそのいずれかに属するように作成するクラスタリング工程と、各クラスタの参照特徴ベクトルの中からそのクラスタの代表ベクトルを選択する選択工程と、前記代表ベクトルを参照画像と関連付けて物体認識用の画像データベースに登録する工程とを備え、前記クラスタリング工程は、近いベクトル位置の参照特徴ベクトルが同じクラスタに属するよう各クラスタを作成し、前記選択工程は、長いベクトル長の参照特徴ベクトルを優先して前記代表ベクトルを選択し、前記検索質問画像と前記参照画像とは、前記検索質問画像から少なくとも一つのクエリ特徴ベクトルを生成し、前記クエリ特徴ベクトルと前記代表ベクトルとの間で近傍探索を適用して照合され、各工程がコンピュータより実行される画像データベースの作成方法を提供する。

また、異なる観点から、この発明は、物体認識のために検索質問画像と照合されるべき参照画像の異なる位置の局所的特徴に対応し、各局所的特徴の位置と特性とをベクトル位置、ベクトル長及びベクトル方向として表す参照特徴ベクトルを前記参照画像から抽出する抽出ステップと、異なる参照特徴ベクトルからなる複数のクラスタを、各参照ベクトルがそのいずれかに属するように作成するクラスタリングステップと、各クラスタの参照特徴ベクトルの中からそのクラスタの代表ベクトルを選択する選択ステップと、前記代表ベクトルを参照画像と関連付けて物体認識用の画像データベースに登録するステップとをコンピュータに実行させ、前記クラスタリングステップは、近いベクトル位置の参照特徴ベクトルが同じクラスタに属するよう各クラスタを作成し、前記選択ステップは、長いベクトル長の参照特徴ベクトルを優先して前記代表ベクトルを選択し、前記検索質問画像と前記参照画像とは、前記検索質問画像から少なくとも一つのクエリ特徴ベクトルを生成し、前記クエリ特徴ベクトルと前記代表ベクトルとの間で近傍探索を適用して照合される画像データベースの作成プログラムを提供する。
また、前記画像データベースの作成方法に対応するものとして、この発明は、物体認識用の画像データベースに登録された参照画像と照合されるべき検索質問画像からその局所的特徴を表す少なくとも一つのクエリ特徴ベクトルを抽出する抽出工程と、前記クエリ特徴ベクトルと各参照画像に関連する前記代表ベクトルとの間で近傍探索を適用して照合を行う照合工程と、前記照合により前記クエリ特徴ベクトルの近傍にあるとされた代表ベクトルが抽出された参照画像を決定する工程とを備え、前記代表ベクトルは、前記参照画像の複数の局所的特徴の位置と特性をベクトル位置、ベクトル長及びベクトル方向として表す参照特徴ベクトルを抽出し、近いベクトル位置の参照特徴ベクトルが同じクラスタに属するように複数のクラスタを作成し、それぞれのクラスタから長いベクトル長の参照特徴ベクトルを優先的に選択して得られ、前記画像データベースは、前記参照画像とその参照画像から抽出された代表ベクトルとが予め関連付けて格納されてなり、各工程がコンピュータより実行される画像検索方法を提供する。
なお、前記検索質問画像からクエリ特徴ベクトルを生成する手順は、参照特徴ベクトルを抽出する手順と同様である。

この発明の画像データベースの作成方法によれば、近いベクトル位置の参照特徴ベクトルが同じクラスタに属するよう各クラスタを作成し、長いベクトル長の参照特徴ベクトルを優先して各クラスタから所定の数の代表ベクトルを選択し、前記代表ベクトルと前記クエリ特徴ベクトルとの間で照合が行われるので、前記代表ベクトルを選択しない場合に比べて、画像データベースへの特徴ベクトルの登録に要するメモリ容量を節約することができる。しかも、各クラスタからそれぞれの代表ベクトルが登録されるので、つまり、画像の一部に偏らず全領域にわたり略均一に登録されるので、画像中にインスタンスが偏在していたり幾何学的変換による歪みを受けて写されていたりしても、頑強（ロバスト）な認識を行うことができる。
この発明による画像データベースの作成プログラムは、前述した画像データベースの作成方法と同様の利点を有する。

公知の近似最近傍探索手法であるANNの概念を示す説明図である。この実施形態の近似最近傍探索手法にはANNを適用している。 この発明の実験例で、画像データベースに登録された画像の一例を示す説明図である。(a)は、Googleイメージ検索を用いて収集した画像の例、(b)は、PCA-SIFTのWebサイトで公開されていた画像の例、(c)は写真共有サイトのflickrにおいて収集した画像の例である。 この発明の実験例で、検索質問として用いた画像の一例を示す説明図である。(a), (b), (c)は撮影角度がそれぞれ90°, 75°, 60°でインスタンスの写真を撮影した画像ある。(d)は、そのインスタンスの写真の一部分を撮影した画像の例である。 この発明の実験例の結果を示すグラフである。図３(a), (b), (c), (d)に示した検索質問に対する認識率およびそれらの平均の認識率を示す。

以下、この発明の好ましい態様について説明する。
前記クラスタリング工程は、予め定められた数のクラスタを生成してもよい。画像中にインスタンスが偏在していたり幾何学的変換による歪みを受けて写されていたりしても、代表ベクトルが画像の全領域にわたり略均一に分散していれば、頑強（ロバスト）な認識を行うことができる。生成されるクラスタの数を多くすればするほど、代表ベクトルは均一に分散する。十分にロバストな認識が行われるクラスタの細かさを、例えば、実験的に予め決定しておき、前記クラスタリング工程が、予め定められた数のクラスタを生成するようにすれば、十分にロバストな認識が実現できる。

また、前記選択工程は、各クラスタから一つの代表ベクトルを選択してもよい。

さらにまた、前記クラスタリング工程は、ケーミーンズ（k-means）法を用いて特徴ベクトルを分けてもよい。このようにすれば、k-means法を用いることによって画像の全領域に渡り満遍なく分散されるように特徴ベクトルをクラスタリングすることができる。
ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。

この発明の特徴的な一側面は、画像認識に用いる画像データベースのメモリ容量の削減を、局所特徴量の取捨選択の観点から検討し、その解決手法を提供する点にある。より具体的には、特徴ベクトルのベクトル長（スケール）と画像空間上での分散の均一性とを考慮して局所特徴量の取捨選択を行う。
以下に述べる実施形態及び実験例により、局所特徴量の取捨選択を行わない場合の画像データベースのメモリ容量に対し10%程度にまでメモリ容量を削減した画像データベースを用いた場合においても、98%の認識率を得ることができ、この発明の有効性が実証された。
ここで、この発明による記憶容量の削減手法を説明に先立ち、特定物体認識に対して行われているスカラー量子化による従来のメモリ容量削減手法と画像認識処理について改めて述べておく。スカラー量子化によるメモリ容量削減手法は、この発明の手法と異なるアプローチで画像データベースのメモリ容量を削減する手法であって、この発明による手法と組み合わせることができ、また組み合わせることが効果的である。
≪スカラー量子化によるメモリ削減手法≫

前記非特許文献３では、特定物体認識に必要なメモリ容量を削減するため、スカラー量子化というアプローチを提案している。これは、個々の局所特徴量を表す特徴ベクトルの各次元が取り得る値を離散値に制限することによって、メモリ容量の削減を実現するものである。即ち、各次元の値を所定のビット長に制限するものである。画像データベースに登録する局所特徴量の数は、変わらないものの、個々の局所特徴量の登録に要するメモリ容量が小さくなるため、全体として画像データベースに必要なメモリ量が削減される。

〔特徴ベクトルの抽出〕
この実施形態においては、PCA-SIFTの手法を適用して参照画像及び検索質問画像からそれぞれの局所特徴量（特徴ベクトル）を抽出する。
前記非特許文献３で、PCA-SIFTを適用して得られる特徴ベクトルは、特徴ベクトルの各次元を2bitで表現しても、画像認識の認識率はほとんど変化しない旨が述べられている。PCA-SIFTにより抽出される特徴ベクトルの各次元の値は、short型整数で表現した場合に16bitで表現される。従って、特徴ベクトルの各次元をスカラー量子化して2bitに削減すると、特徴ベクトル単体は、1/8程度のメモリ容量になる。画像データベースとしては、特徴ベクトルの格納の他に必要なメモリ容量があるが、それを考慮しても、画像データベースのメモリ容量を1/3程度に削減できる旨が述べられている。

〔クエリ特徴ベクトルと参照特徴ベクトルとの照合〕
画像検索は、クエリ特徴ベクトルと参照特徴ベクトルとを照合して行われる。前記照合処理は、検索質問画像から抽出されたクエリ特徴ベクトルと、画像データベースに登録されている参照特徴ベクトルとの間の距離計算を行い、各クエリ特徴ベクトルに対して近傍となる参照特徴ベクトルを決定する。そして、決定した参照特徴ベクトルに関連付けられた画像IDを得る。
〔認識結果としての参照画像の決定〕
照合の結果に基づき画像認識の結果を決定する処理を行う。前記処理は、前記照合処理によって得られた各クエリ特徴ベクトルに対する画像IDへの投票を行って、最大得票を得た画像IDが示す参照画像を認識結果として決定する。
スカラー量子化の結果、距離計算の精度は低下する。それでも認識率がほとんど変化しない理由として、投票による多数決のおかげで誤った画像IDが除外されることが挙げられる。

≪局所特徴量の取捨選択によるメモリ削減手法≫
先に述べたスカラー量子化とは異なるアプローチによって画像データベースのメモリ容量を削減する手法として、発明者らは、特徴ベクトルの取捨選択を行うことに着目した。
〔取捨選択の方針〕

参局所特徴量の取捨選択によるメモリ削減手法においても、PCA-SIFTの手法を用いて局所特徴量を抽出するものとする。
参照画像から抽出される局所特徴量の数は、参照画像の内容によって異なる。局所特徴量の取捨選択を行わない無削減状態の画像データベースでは画像から抽出された局所特徴量を全て登録する。そのため、異なる参照画像の間で、登録される局所特徴量の数が大きく異なる。数多くの局所特徴量が多抽出される参照画像では、参照画像中の特定の部分から類似した局所特徴量が多数抽出されることがある。類似した局所特徴量は、その全てを画像データベースに登録しておく必要はない。類似しているが故に、認識率の向上にはあまり寄与しないと考えられるからである。よって、画像1枚から画像データベースに抽出する局所特徴量の数の最大値をRに制限し、参照特徴ベクトルを格納するために必要なメモリ容量の増大を防ぐことにする。抽出された参照特徴ベクトルの数がRを越えない場合には、抽出された局所特徴量を全て画像データベースに登録する。参照特徴ベクトルの数がRを越えた場合には、以下の着想に基づき、登録する局所特徴量を選択する。

〔クラスタリング〕
この発明では、撮影角度の変化に対する耐性が比較的強いとされる、長いベクトル長の特徴ベクトルを優先的に選択し、画像データベースに登録することとする。認識結果とされるべき参照画像及び対応する検索質問画像に、検索対象の全体が写っている可能性は低くないといえる。しかしながら、長いベクトル長の特徴ベクトルが、前記参照画像又は検索質問画像の一部領域に偏在していると、その領域以外の部分がノイズとなってしまい検索質問に対応する参照画像の検索が困難になる。こういった検索対象の偏在に対処するため、参照特徴ベクトルが抽出された参照画像の中で参照特徴ベクトルの位置を示す座標値について、最大クラスタ数をRとするk-meansクラスタリングを行う。

〔代表ベクトルの選択と画像データベースへの登録〕
さらに、k-meansクラスタリングによって得られた各クラスタ内の参照特徴ベクトルの中からベクトル長が最も大きなものを優先して選択する。
選択した参照特徴ベクトルを画像データベースに登録する。即ち、各クラス他を代表する代表ベクトルだけを画像データベースに登録する。
この手順により、参照画像の中から偏りなく略均一に参照特徴ベクトルを選択することになる。よって、参照画像の中に検索対象の物体が一部分しか写っていない場合においても、認識できる可能性を高めることができると考えられる。

〔照合に用いる近似最近傍探索の手法〕
クエリ特徴ベクトルと参照特徴ベクトル（あるいは、代表ベクトル）との照合には、ANN(Approximate Nearest Neighbor、例えば、非特許文献５参照)の手法を用いることができる。ANNは、木構造を用いて、近似最近傍探索を高速に行う手法である。近似を行うことにより、ベクトル照合の精度は低下するものの、検索にかかる処理時間を削減することが可能となる。

ANNによる近似最近傍探索の概念を図１に示す。ただし、簡単のため、説明に関与するセルのみを描いている。画像データベース中の参照特徴ベクトルは、幾つかのセルに分けられ木構造をなすようにして画像データベースに登録されている。いま、qを検索質問のクエリ特徴ベクトル、p₁ からp₆ を参照特徴ベクトルとし、現在、p₁ が近傍のベクトルとして発見されているとする。rはクエリ特徴ベクトルqと参照特徴ベクトルp₁ とがなす距離である。最近傍探索を実行する場合、実線で示される超球と重なるセルには、p₁ より近傍の参照特徴ベクトル、即ち、qとの距離がrよりも近い参照特徴ベクトルが存在する可能性があるため、探索の対象となる。一方、近似最近傍探索を行う場合、p₁ までの距離rに対して、許容誤差εを用いて定義される半径

の超球を考え、それと交わるセルのみを探索の対象とする。これにより、最近傍の参照特徴ベクトル(図１の場合はp₃ )を発見できない可能性は出てくるが、探索の対象となるセルの数が減少するため、探索時間を削減できる。
この発明の手法では、局所特徴量の削減のため、あるクエリ特徴ベクトルに対し、最近傍の参照特徴ベクトル（正解となるべき参照特徴ベクトル）が対応づけられないことも考えられる。そのため、ANNによる照合の結果として対応付けられたクエリ特徴ベクトルと参照特徴ベクトルとの距離dが、予め定められた閾値tよりも近い場合にのみ、画像に投票を行う。
≪実験例≫
〔参照画像と画像データベース〕

局所特徴量の取捨選択の有効性を実証する実験を行った。実験に用いた画像データベースは、参照画像として10万枚が登録されたものを用いた。参照画像10万枚の画像データベースは、Ａ, Ｂ, Ｃの3種類のデータセットで構成されている。Ａは、Googleイメージ検索を用いて収集した、3,100枚の画像からなる。画像の収集に用いた検索キーワードは、ポスター"、"雑誌"、"表紙" などである。Ｂは、PCA-SIFTのサイトで公開されている18,500枚の画像からなる。Ｃは、写真共有サイトのflickrにおいて、"animal", "birthday", "food","japan"などのタグにより収集した78,400枚の画像からなる。主に物体や、自然の写真、人物の写真などを含む。
図２に、上記の手順で収集された参照画像の例を示す。

なお、参照画像収集の際には、600×600 pixel以下のサイズの画像は除外し、各参照画像の長辺が640pixel以下になるように縮小した。画像サイズは、およそVGAサイズである。
そして、これらの参照画像に対し、PCA-SIFT(http://www.cs.cmu.edu/yke/pcasift/で提供されていたものを用いた)の手法を適用して局所特徴量を抽出した。抽出された局所特徴量の総数は、1.82×10⁸である。そのサブセットである参照画像1万枚のデータベースにおいて抽出された局所特徴量の総数は、2.07×10⁷である。
そして、各画像データベースに対して、比較のため前記非特許文献４のベクトル量子化による従来のメモリ削減手法、並びに、この発明による局所特徴量の取捨選択によるメモリ削減手法をそれぞれ適用し、合計で４つの画像データベースを作成した。

〔ベクトル量子化によるメモリ削減手法〕
ここで、ベクトル量子化による従来のメモリ削減手法について簡単に説明する。
ベクトル量子化では、特徴空間上の一定領域に分布している特徴ベクトルをまとめることによって行う。そのため、何らかの方法により、特徴ベクトルをどのようにしてまとめるのかを定める必要がある。本稿では、以下のようにして、特徴ベクトルをまとめることにする。まず、kd-tree を作成するときに用いられている、standard kd-tree splitting rule を用いて特徴空間を分割する。これは、特徴空間上で、最も分散が大きい次元を選択し、その次元上に分布している点の座標の中央値で、空間を分割する方法である。分割空間に含まれる特徴ベクトルの最大数（バケットサイズ）b を設定し、各空間内に含まれる特徴ベクトルの数を、b 以下になるまで分割する。そして、分割された特徴空間に分布している特徴ベクトルの重心を求め、その空間上の特徴ベクトルを重心ベクトルに置換する。データベース中には、重心ベクトルを記録すると共に、置換した特徴ベクトルに付与されていた画像ID を、この重心ベクトルに付与し直すことで、ベクトル量子化を行う。
この重心ベクトルは、ベクトル量子化の符号語（codeword）に相当するものであり、しばしばvisual word と呼ばれる。

〔実験パラメータ〕
ベクトル量子化の方法で画像データベースを作成する際に用いたパラメータbの値は、b=1, 2, 3, 5, 10, 20 である。
一方、局所特徴量の取捨選択によるメモリ削減手法で画像データベースを作成する際に用いたパラメータRの値は、R = 300, 200, 100, 75, 50である。Rの各値に対して、参照画像10万枚の画像データベース内に登録された局所特徴量の数を表1に示す。

〔検索質問画像〕

検索対象を得るために、データセットＡ, Ｂ, Ｃ のそれぞれから100、200、200枚の合計500枚の参照画像を無作為に選択した。よって、各検索対象は、認識されるべき参照画像が画像データベースに必ず存在する。次に、これらの検索対象をA4の用紙に印刷し、カメラを用いて撮影した。
図３は、得られた撮影画像の例である。図３に示すとおり、検索対象の紙面全体が写る配置で、その紙面に対するカメラの光軸の角度θを90°, 75°, 60°に変化させてそれぞれ撮影画像を得た。また、角度を90°として紙面の一部分を撮影した。その結果、１つの検索対象につき、それぞれ4つの撮影画像を得た。さらに、撮影された撮影画像を512×341 pixelに縮小して検索質問画像とし、PCA-SIFTにより特徴ベクトルを求めた。その結果、検索質問画像1枚あたり平均612個のクエリ特徴ベクトルが得られた。
〔閾値ｔの決定〕

まず、前述のANNを用いた照合に係る距離の閾値tとして、どの程度の値を定めるのが適切かを調べる実験を行った。具体的には、作成した画像データベースに対してtの値を変化させて、認識率がどのように変化するかを調べた。得られた実験結果のうち、参照画像１枚の画像データベースから抽出する局所特徴量の最大数RをR = 50とした場合の結果を表２に示す。表２の結果から、閾値ｔの値が、およそ、t = 3873, 3162の場合に認識率がよくなっていることが分かる。Rの値を変化させたときにおいても、総じて、t = 3873, 3162のあたりで認識率がよくなっていることがわかった。この結果に基づいて、以下の実験では、閾値tは、t = 3873とした。

〔特徴量の取捨選択の有効性〕
次に、以下の（Ａ），（Ｂ），（Ｃ），（Ｄ）の４手法を比較した。（Ａ）は、k-meansクラスタリングをして、その中で長いベクトル長の特徴ベクトルを選択する方法である。（Ｂ）は、各画像から画像空間上でk-meansクラスタリングをして、その中から、局所特徴量をランダムに選択する方法である。（Ｃ）は、各画像から、長いベクトル長の特徴ベクトルから順に選択する方法である。（Ｄ）は、各画像からランダムに局所特徴量を選択する方法である。

前述の４手法について、同じRの値を用いて画像データベースを作成し、認識率を比較した。距離の閾値は、t = 3873である。R = 50のときの結果を図４に示す。

図４で、縦軸は認識率を示しており、横軸は、左端の「平均」が、以降に述べる４つのデータを通した平均認識率を示す。「60°」は、撮影角度60°の検索質問画像の平均認識率を、「75°」は、撮影角度75°の検索質問画像の平均認識率を、「90°」は、撮影角度90°の検索質問画像の平均認識率を、「一部」は、一部分を撮影した検索質問画像の平均認識率を示す。図４より、画像全体が写っている場合においては、手法（Ａ）が最もよい認識率となっている。

図４の手法（Ａ）と（Ｃ）を比較すると、特定平面物体全体が写っている画像を認識する場合、角度変化への耐性が強いとされる、長いベクトル長の特徴ベクトルが認識に有利であるといえる。
しかしながら、長いベクトル長の特徴ベクトルだけを登録した場合、手法（Ｃ）において、検索対象の一部分のみが写っている検索質問画像を用いると、認識率が著しく下がっている。この原因の一つとして、長いベクトル長の特徴ベクトルが、検索質問画像の撮影範囲外の部分に偏ってしまった結果、クエリ特徴ベクトルと参照特徴ベクトルとの照合がうまくできなかったと考えられる。
これに対して、k-means法を適用し、画像の各部分から満遍なく局所特徴量を選択する手法（Ａ）を用いると、認識率が大きく回復していることがわかる。よって、画像上から長いベクトル長の特徴ベクトルを満遍なく選択することが重要であるといえる。

続いて、手法（Ａ）に対して、Rの値を変化させたときの認識率を表３に示す。∞は、局所特徴量を画像データベースに登録する際に、その最大数を制限しなかった場合を示している。

表３より、元の画像データベースの10%程度のメモリ容量でも、98%以上の認識率が実現されている。Rが小さくなるにつれ、一部分のみを拡大した検索質問に対しては、認識率の低下が現われ、次第に大きくなっている。これは、長いベクトル長の特徴ベクトルを選択したためであると考えられる。

以上の実験例に示したように、特徴ベクトルのベクトル長と、画像空間上での分散の均一性を考慮して局所特徴量を取捨選択することで、無削減状態の1/10程度の画像データベースを用いた場合においても、98%の認識率を得ることができ、子の発明による面離削減手法の有効性が実証された。

前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。

この発明は、SIFT(Scale-Invariant Feature Transform)などの局所特徴量を用いて、何万枚、何十万枚といった大規模な画像データベースを対象に特定物体認識を行うような場合の画像データベースの作成に極めて有効な手法である。
大規模特定物体認識の画像データベースでは、画像データベースに保持しておく局所特徴量（特徴ベクトル）の数が増大する。そのため、メモリ容量の削減が課題となる。この発明によれば、局所特徴量の取捨選択の方法を工夫することによって、局所特徴量を画像データベースに保持しておくのに要するメモリ容量を節約することができる。

p₁, p₂, p₃, p₄, p₅, p₆：画像データベース中の画像の特徴ベクトル
q：検索質問の特徴ベクトル
r：ベクトルp₁とqとの距離、半径

Claims (5)

1. 特定物体認識のために、物体が写された検索質問画像と照合されるべき参照画像の異なる位置の局所的特徴に対応し、各局所特徴量をベクトル位置、ベクトル長及びベクトル方向として表す参照特徴ベクトルを前記参照画像から抽出する抽出工程と、
   異なる参照特徴ベクトルからなる複数のクラスタを、各参照ベクトルがそのいずれかに属するように作成するクラスタリング工程と、
   各クラスタの参照特徴ベクトルの中からそのクラスタの代表ベクトルを選択する選択工程と、
   前記代表ベクトルを参照画像と関連付けて特定物体認識用の画像データベースに登録する工程とを備え、
   前記画像データベースはメモリに格納され、
   前記クラスタリング工程は、前記参照画像中で各参照ベクトルの位置を示す座標値についてクラスタリングを行い、
   前記選択工程は、各クラスタ内で最も長いベクトル長の参照特徴ベクトルを前記代表ベクトルとして選択し、
   前記検索質問画像と前記参照画像とは、前記検索質問画像から複数のクエリ特徴ベクトルを生成し、各クエリ特徴ベクトルと各代表ベクトルとの間で近似最近傍探索を適用して照合され、
   各工程がコンピュータより実行される画像データベースの作成方法。
2. 前記選択工程は、各クラスタから一つの代表ベクトルを選択する請求項１に記載の方法。
3. 前記クラスタリング工程は、ケーミーンズ・クラスタリングを用いて前記複数のクラスタを作成する請求項１または２に記載の方法。
4. 特定物体認識用の画像データベースに登録された参照画像と照合されるべき物体が写された検索質問画像からその局所的特徴を表す複数のクエリ特徴ベクトルを抽出する抽出工程と、
   各クエリ特徴ベクトルと各参照画像に関連する複数の代表ベクトルとの間で近似最近傍探索を適用して照合を行う照合工程と、
   前記照合により前記クエリ特徴ベクトルの最近傍にあるとされた代表ベクトルが抽出された参照画像を決定する工程とを備え、
   前記画像データベースはメモリに格納され、
   各代表ベクトルは、前記参照画像の複数の局所特徴量をベクトル位置、ベクトル長及びベクトル方向として表す参照特徴ベクトルを抽出し、
   前記参照画像中で各参照ベクトルの位置を示す座標値についてクラスタリングを行い、それぞれのクラスタから最も長いベクトル長の参照特徴ベクトルを選択して得られ、
   前記画像データベースは、前記参照画像とその参照画像から抽出された代表ベクトルとが予め関連付けて格納されてなり、
   各工程がコンピュータより実行される画像検索方法。
5. 特定物体認識のために、物体が写された検索質問画像と照合されるべき参照画像の異なる位置の局所的特徴に対応し、各局所特徴量をベクトル位置、ベクトル長及びベクトル方向として表す参照特徴ベクトルを前記参照画像から抽出する抽出ステップと、
   異なる参照特徴ベクトルからなる複数のクラスタを、各参照ベクトルがそのいずれかに属するように作成するクラスタリングステップと、
   各クラスタの参照特徴ベクトルの中からそのクラスタの代表ベクトルを選択する選択ステップと、
   前記代表ベクトルを参照画像と関連付けて特定物体認識用の画像データベースに登録するステップとをコンピュータに実行させ、
   前記画像データベースはメモリに格納され、
   前記クラスタリングステップは、各参照ベクトルの位置を示す座標値についてクラスタリングを行い、
   前記選択ステップは、各クラスタ内で最も長いベクトル長の参照特徴ベクトルを前記代表ベクトルとして選択し、
   前記検索質問画像と前記参照画像とは、前記検索質問画像から複数のクエリ特徴ベクトルを生成し、各クエリ特徴ベクトルと各代表ベクトルとの間で近似最近傍探索を適用して照合される画像データベースの作成プログラム。