特許

J-GLOBAL ID：200903080638854340

多次元検索方法及び装置

発明者： フェリックス ヘンリ
出願人/特許権者： キヤノン株式会社
代理人 (1件)： 大塚 康徳 (外2名)
公報種別：公開公報
出願番号（国際出願番号）：特願平10-047391
公開番号（公開出願番号）：特開平10-247204
出願日： 1998年02月27日
公開日（公表日）： 1998年09月14日
要約：

【要約】【課題】超平面を適切に設定,選択して参照ベクトルの絞り込みを行い、高速で正確な多次元近傍検索を可能とする。【解決手段】参照ベクトルの第1集合の中から入力ベクトルの近傍を検索する多次元検索方法は、参照ベクトルを含む空間における超平面の第1集合を決定し、その第1集合から第1の超平面を選択し、選択された第1の超平面で分割された空間で入力ベクトルの存在しないほうの空間に属する参照ベクトルを消去することで参照ベクトルの第2集合を生成し、第1の超平面を消去することで超平面の第2集合を生成し、参照ベクトルの第1集合及び超平面の第1集合としてそれぞれ生成された第2集合を用いて上記選択と生成を所定回数繰り返す。こうして得られた参照ベクトルの第2集合の中から 入力ベクトルの最近傍を検索する。

請求項（抜粋）：

記憶手段に格納された基準ベクトルの第1集合(EVR1)の中から、物理量を表す入力ベクトル(VE)の近傍を多次元検索する方法であって、第1の規則に従って、基準ベクトルを含む平面における超平面の第1集合(EH1)を決定する前工程(EP3)と、第2の規則に従って、前記超平面の第1集合から第1の超平面(Hi)を選択する選択工程(E12)と、選択された前記第1の超平面(Hi)で分割された空間のうち前記入力ベクトル(VE)と反対側の空間にある基準ベクトルを消去することにより、前記基準ベクトルの第1集合から基準ベクトルの第2集合(EVR2)を形成する第1形成工程(E13)と、前記超平面の第1集合から前記第1の超平面を除去することにより超平面の第2集合(EH2)を形成する第2形成工程(E14)と、前回に形成された基準ベクトルの第2集合(EVR2)と超平面の第2集合(EH2)をそれぞれ基準ベクトルの第1集合(EVR1)と超平面の第1集合(EH1)として用いて、前記選択工程と2つの形成工程(E12,E13,E14)を所定回数繰り返す繰り返し工程と、第3の規則に従って、前記基準ベクトルの第2集合(EVR2)から入力ベクトル(VE)の最近傍を検索する検索工程(E17)とを備えることを特徴する多次元検索方法。

FI (2件)：

G06F 15/401 310 D ,  G06F 15/40 370 B