Pat

J-GLOBAL ID：200903084174084984

データ処理装置及びその方法、及びそのプログラム

Inventor： 鷲澤 輝芳
Applicant, Patent owner： キヤノン株式会社
Agent (1)： 西山 恵三 (外1名)
Gazette classification：公開公報
Application number (International application number)：2001122755
Publication number (International publication number)：2002318818
Application date： Apr. 20, 2001
Publication date： Oct. 31, 2002
Summary：

【要約】【課題】 与えられたベクトルデータに対して内積を基にした類似度によるデータ検索が高速に実行できるようにする。【解決手段】 プロトタイプとなるベクトルの各成分に対するソーティング・リストを作成しておき、テストベクトルX及び-Xのm成分値に最も近い値をリストから探索し、それぞれの位置をPTR+及びPTR-に格納する(S303)。k個の近傍集合の初期化を行い(S304)、PTRと関連する変数を更新する(S306)。順次プロトタイプYtを取り出し、判定処理によって、類似度が今までの最小値より大きければ、最小値に対応するプロトタイプとYtを入れ替え、近傍集合及び最小値を更新する(S308〜311)。

Claim (excerpt)：

多次元ベクトルで記述されたプロトタイプ集合から、与えられた第1のテストベクトルに類似する所定個のプロトタイプを検索結果として抽出するデータ処理装置であって、前記多次元ベクトルの各成分につき、前記プロトタイプ集合の各プロトタイプの識別子と成分値とを成分値の順に並べたリストを作成し、各プロトタイプのノルムの2乗を計算する前処理手段と、前記第1のテストベクトルから第2のテストベクトルを生成するテストベクトル生成手段と、前記リスト及び前記各プロトタイプのノルムの2乗と、第1及び第2のテストベクトルとを用いて、当該第1のテストベクトルと各プロトタイプとの内積の絶対値に基づく類似度を計算する類似度計算手段と、前記類似度の値に基づく省略条件の判断により、以後の処理を省略する省略制御手段と、前記類似度の値に基づいて検索結果を更新する更新手段とを有することを特徴とするデータ処理装置。

IPC (5)：

G06F 17/30 350 ,  G06F 17/30 210 ,  G06F 17/16 ,  G06T 7/00 300 ,  G06T 7/00

FI (5)：

G06F 17/30 350 C ,  G06F 17/30 210 D ,  G06F 17/16 K ,  G06T 7/00 300 C ,  G06T 7/00 300 F

F-Term (10)：

5B056BB42 ,  5B056HH00 ,  5B056HH03 ,  5B075NK06 ,  5B075NR12 ,  5B075PR06 ,  5B075QM08 ,  5B075QS20 ,  5L096JA03 ,  5L096JA26