TOP > 国内特許検索 > 近似最近傍探索に係るデータベースの登録方法および登録装置

近似最近傍探索に係るデータベースの登録方法および登録装置

国内特許コード P120008410
整理番号 S2011-0810-N0
掲載日 2012年12月19日
出願番号 特願2011-119128
公開番号 特開2012-247993
登録番号 特許第5692725号
出願日 平成23年5月27日(2011.5.27)
公開日 平成24年12月13日(2012.12.13)
登録日 平成27年2月13日(2015.2.13)
発明者
  • 岩村 雅一
  • 黄瀬 浩一
出願人
  • 公立大学法人大阪府立大学
発明の名称 近似最近傍探索に係るデータベースの登録方法および登録装置
発明の概要 【課題】近似最近傍探索の一手法であるLSHにおいて、必要な計算時間とメモリ使用量を削減する。
【解決手段】画像の特徴ベクトルを抽出してデータベースに登録するとき、各特徴ベクトルを複数のビンに分類するため、k個を一組の単位としてL組生成したハッシュテーブルに登録する。そして(i)登録されたある特徴ベクトルを選んでその特徴ベクトルと同じ登録ビンの他の特徴ベクトルを特定し、(ii)各組ごとに、その組のk個の登録ビンのいずれにも登録されている他の特徴ベクトルの集合をその組のバケットとし、(iii)全L個のバケットのうち所定個以上のバケットに入っている特徴ベクトルを得、(iv)得られた特徴ベクトルを第1組のハッシュテーブルの各登録ビンにそれぞれ追加登録し、所定数の特徴ベクトルについて前記(i)~(iv)による追加登録を実行した後、第1組を除く各組のハッシュテーブルを削除する画像データベースの登録方法。
【選択図】図4
従来技術、競合技術の概要


最近傍探索は、データベースS 中からクエリベクトル(以下、単にクエリ)q と距離が最も近いベクトルデータ(以下、単にデータ)p ∈S を発見する命題である。最近傍探索ではクエリと全てのデータとの距離を計算すれば必ず正しい解が得られる。この単純な命題は、扱うデータの規模が大きくなると容易には解けなくなる。20 億ベクトルをデータベースに登録しておき、物体認識を行うタスクも存在する(例えば、非特許文献2参照)。そのため、最近傍探索の高速化は不可欠である。



最近傍探索の高速化には、木構造などでデータベースを構造化し、距離計算回数を削減することが有効である(例えば、非特許文献3参照)。しかし、構造化によってデータ以外の情報も記憶することになるため、より大きなメモリ使用量が必要になる。計算時間とメモリ使用量にはトレードオフの関係があると考えられている。次元数が2より大きい場合に扱うデータ数n に対して計算時間が対数、メモリ使用量が線形に増加するアルゴリズムは知られていない(例えば、非特許文献4参照)。



この限界を超えるために近似最近傍探索が近年注目されている。これは最近傍探索において条件を緩和し、必ずしも最近傍データが得られなくてもよくしたものである。近似最近傍探索により、常に厳密な最近傍点を求める最近傍探索に比べて計算時間とメモリ使用量を大幅に削減できる。近似最近傍探索の代表的な手法としては、木構造を用いるApproximate Nearest Neighbor(ANN、例えば、非特許文献4参照)やハッシュを用いるLocality Sensitive Hashing(LSH、例えば、非特許文献1、5参照)、Spectral Hashing(例えば、非特許文献6参照)、Minwise Hashing(例えば、非特許文献7参照)などが知られている。近似最近傍探索によって得られるベクトルデータは、クエリベクトルq に最も近いと推測されたデータであるが、真に最近傍のデータとは限らない。

産業上の利用分野


この発明は、画像に係るデータのデータベースへの登録方法および登録装置に関する。より詳細には、前記データベースの探索に適用される近似最近傍探索の手法に関する。



前記データベースは、例えば物体認識に用いられるものである。物体認識は、検索質問(クエリ)として物体の画像が与えられたとき、画像データベースに登録された各画像のうちクエリに最も近い画像、即ち物体をコンピュータを用いて探索する処理といえる。なお、ここでいう物体即ちオブジェクトは、人物や生物を含む広い意味の物体である。探索の処理手順としては、画像からその特徴を表すベクトルデータ(特徴ベクトル)を抽出し、抽出された特徴ベクトルを前記画像と共にその画像に対応する特徴ベクトルとを画像データベースに登録しておく。クエリが与えられたとき、そのクエリから特徴ベクトル(クエリベクトル)を抽出し、画像データベースに登録された各特徴ベクトルと照合する。その中で、クエリベクトルに最も近い特徴ベクトルを探索する。この探索を最近傍探索という。
なお、最近傍探索は、物体認識に限らず、他の様々な分野で用いられている。例えば、文字認識、画像検索をはじめとして、データの統計分類、データ圧縮、商品等の推薦システム、マーケティング、スペルチェッカー、DNAシークエンシングなどに適用される。この発明は、物体認識に限らずこれらの分野におけるベクトルデータの最近傍探索にも適用できる。

特許請求の範囲 【請求項1】
コンピュータが、
画像に係るデータからそのデータの特徴を表す特徴ベクトルを抽出する工程と、
抽出された特徴ベクトルを前記データと共にデータベースに登録する登録工程とを備え、
前記データベースは、検索質問として画像に係るデータが与えられたとき、そのデータからクエリベクトルを抽出し、クエリベクトルから最も近いと推測される特徴ベクトルの探索を行うために用いられ、
前記登録工程は、各特徴ベクトルを複数のビンの何れか一つに分類して登録するためのハッシュテーブルを、k 個を一組の単位としてL 組(k ,L は2以上の整数)生成し、
各特徴ベクトルをそれらのハッシュテーブルにそれぞれ登録した後に、
(i)登録されたある特徴ベクトルを選んでその特徴ベクトルと同じビンである登録ビンに分類された他の特徴ベクトルを特定し、
(ii)各組ごとに、その組のk 個の登録ビンのいずれにも登録されている他の特徴ベクトルの集合をその組のバケットとし、
(iii)全L 個のバケットのうち所定個以上のバケットに入っている特徴ベクトルを得、
(iv)得られた特徴ベクトルを第1組のハッシュテーブルの各登録ビンにそれぞれ追加登録し、
所定数の特徴ベクトルについて前記(i)~(iv)による追加登録を実行した後、
第1組を除く各組のハッシュテーブルを削除することを特徴とするデータベースの登録方法。

【請求項2】
前記探索は、クエリベクトルにハッシュ関数を適用して、第1組の各ハッシュテーブルについて対応するk 個のビンを決定し、それらのビンのいずれにも登録されている特徴ベクトルの集合を求め、前記クエリベクトルをその集合に属する各特徴ベクトルと照合する請求項1に記載の方法。

【請求項3】
前記登録工程は、追加登録を行うために選択する特徴ベクトルを、一様乱数を用いて決定する請求項1または2に記載の方法。

【請求項4】
前記登録工程は、追加登録を行おうとする特徴ベクトルが、第1組のバケットに既に登録されているときは、その特徴ベクトルのさらなる追加登録を行わない請求項1~3のいずれか一つに記載の方法。

【請求項5】
前記登録工程は、予め定められたk およびL の値に基づいて処理を行い、
登録すべき特徴ベクトルのうち予め定められた割合の数だけ、追加登録を行う特徴ベクトルを選択し、
予め定められた個数以上のバケットに入った特徴ベクトルを追加登録する請求項1~4のいずれか一つに記載の方法。

【請求項6】
前記データベースは、各特徴ベクトルのベクトルデータと各特徴ベクトルの識別子とが対応付けられた対応表および各ハッシュテーブルを含み、
各ハッシュテーブルは、各ビンに登録される各特徴ベクトルを対応する識別子を用いて表す請求項1~5のいずれか一つに記載の方法。

【請求項7】
前記探索は、クエリベクトルと各特徴ベクトルとの距離を計算し、計算された距離に基づいてクエリベクトルから最も近いと推測される特徴ベクトルを決定する請求項1~6のいずれか一つに記載の方法。

【請求項8】
画像に係るデータからそのデータの特徴を表す特徴ベクトルを抽出する処理部と、
抽出された特徴ベクトルを前記データと共にデータベースに登録する登録部とを備え、
前記データベースは、検索質問として画像に係るデータが与えられたとき、そのデータからクエリベクトルを抽出し、クエリベクトルから最も近いと推測される特徴ベクトルの探索を行う探索装置に用いられ、
前記登録部は、各特徴ベクトルを複数のビンの何れか一つに分類して登録するためのハッシュテーブルを、k 個を一組の単位としてL 組(k ,L は2以上の整数)生成し、
各特徴ベクトルをそれらのハッシュテーブルにそれぞれ登録した後に、
(i)登録されたある特徴ベクトルを選んでその特徴ベクトルと同じビンである登録ビンに分類された他の特徴ベクトルを特定し、
(ii)各組ごとに、その組のk 個の登録ビンのいずれにも登録されている他の特徴ベクトルの集合をその組のバケットとし、
(iii)全L 個のバケットのうち所定個以上のバケットに入っている特徴ベクトルを得、
(iv)得られた特徴ベクトルを第1組のハッシュテーブルの各登録ビンにそれぞれ追加登録し、
所定数の特徴ベクトルについて前記(i)~(iv)による追加登録を実行した後、
第1組を除く各組のハッシュテーブルを削除することを特徴とするデータベースの登録装置。
産業区分
  • 演算制御装置
  • 記憶装置
  • 入出力装置
  • 計算機応用
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2011119128thum.jpg
出願権利状態 登録
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記までご連絡ください


PAGE TOP

close
close
close
close
close
close
close