特許

J-GLOBAL ID：201203034912496476

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

発明者： 岩村 雅一 ,  黄瀬 浩一
出願人/特許権者： 公立大学法人大阪府立大学
代理人 (5件)： 野河 信太郎 ,  秋山 雅則 ,  甲斐 伸二 ,  金子 裕輔 ,  稲本 潔
公報種別：公開公報
出願番号（国際出願番号）：特願2011-119128
公開番号（公開出願番号）：特開2012-247993
出願日： 2011年05月27日
公開日（公表日）： 2012年12月13日
要約：

【課題】近似最近傍探索の一手法であるLSHにおいて、必要な計算時間とメモリ使用量を削減する。【解決手段】画像の特徴ベクトルを抽出してデータベースに登録するとき、各特徴ベクトルを複数のビンに分類するため、k個を一組の単位としてL組生成したハッシュテーブルに登録する。そして(i)登録されたある特徴ベクトルを選んでその特徴ベクトルと同じ登録ビンの他の特徴ベクトルを特定し、(ii)各組ごとに、その組のk個の登録ビンのいずれにも登録されている他の特徴ベクトルの集合をその組のバケットとし、(iii)全L個のバケットのうち所定個以上のバケットに入っている特徴ベクトルを得、(iv)得られた特徴ベクトルを第1組のハッシュテーブルの各登録ビンにそれぞれ追加登録し、所定数の特徴ベクトルについて前記(i)〜(iv)による追加登録を実行した後、第1組を除く各組のハッシュテーブルを削除する画像データベースの登録方法。【選択図】図4

請求項（抜粋）：

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

IPC (2件)：

G06T 1/00 ,  G06F 17/30

FI (4件)：

G06T1/00 200D ,  G06F17/30 320Z ,  G06F17/30 170B ,  G06F17/30 412

Fターム (5件)：

5B050AA09 ,  5B050BA10 ,  5B050BA15 ,  5B050EA04 ,  5B050FA02