複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするための方法であって、前記ベクトルは、少なくとも1つの画像におけるスケール不変特徴を識別するために、スケール不変特徴を表す、方法において、i参照点ベクトルを選択する工程と、ii前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離dを計算する工程と、iii前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離dgroupを持つベクトルのグループにソートする工程と、ivその後、2つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第2ベクトルが前記グループの第1ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、v前記特定のベクトルの最適マッチングを、a前記参照点ベクトルと前記特定のベクトルとの間の距離dspecificを計算する工程と、b計算された前記距離dspecificに最も近い距離dを備えたベクトルを持つ1つまたは複数の前記グループを識別する工程と、c前記特定のベクトルに最も近い距離dminimumを持つ1つまたは複数の識別された前記グループの中の1つまたは複数の前記ベクトルを識別する工程と、dゼロよりも大きく、dspecific-dminimumからdspecificdminimumのインターバルの中の前記参照点ベクトルから、距離dを備えた任意の追加のグループを識別する工程と、e前記インターバルの中のすべてのグループが検討されるまで、工程vcおよび工程vdを繰り返す工程と、によって識別する工程と、を備えた方法。検討されるべき次のグループは、dspecificに最も近い距離dを持つ未検討のグループである、請求項1記載の方法。前記ベクトルは、多次元である、請求項1または2に記載の方法。前記距離d、dgroup、dspecificおよびdminimumは、ユークリッド距離、マハラノビス距離、マンハッタン距離、チェビシェフ距離、およびミンコフスキー距離から成るグループの中から選択される距離として計算される、請求項1乃至3のいずれか一項に記載の方法。前記距離d、dgroup、dspecificおよびdminimumは、ユークリッド距離として計算される、請求項1乃至4のいずれか一項に記載の方法。前記参照点ベクトルは、前記データセットの中から選択される、請求項1乃至5のいずれか一項に記載の方法。前記参照点ベクトルは、前記データセットの中点として選択される、請求項1乃至5のいずれか一項に記載の方法。複数のベクトルから成るデータセットの中から特定のベクトルを次にマッチングするために前記データセットを編成するための方法であって、前記ベクトルは、少なくとも1つの画像におけるスケール不変特徴を次に識別するために、少なくとも1つの画像におけるスケール不変特徴を表す、方法において、i参照点ベクトルを選択する工程と、ii前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離dを計算する工程と、iii前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離dgroupを持つベクトルのグループにソートする工程と、ivその後、2つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第2ベクトルが前記グループの第1ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、を備えた方法。少なくとも1つの画像におけるスケール不変特徴を識別するために、複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするために使用される、請求項8記載の方法であって、v前記特定のベクトルの最適マッチングを、a前記参照点ベクトルと前記特定のベクトルとの間の距離dspecificを計算する工程と、b計算された前記距離dspecificに最も近い距離dを備えたベクトルを持つ1つまたは複数の前記グループを識別する工程と、c前記特定のベクトルに最も近い距離dminimumを持つ1つまたは複数の識別された前記グループの中の1つまたは複数の前記ベクトルを識別する工程と、dゼロよりも大きく、dspecific-dminimumからdspecificdminimumのインターバルの中の前記参照点ベクトルから、距離dを備えた任意の追加のグループを識別する工程と、e前記インターバルの中のすべてのグループが検討されるまで、工程vcおよび工程vdを繰り返す工程と、によって識別する工程と、をさらに備えた方法。複数の画素によって画成された原画像において、異なるスケールにわたって安定している画像特徴を識別するための、請求項1乃至9のいずれか一項に記載の方法であって、a程度の異なるボケを前記原画像に適用することによって得られた差分を計算することによって、前記原画像から、多数の差分画像を取得する工程と、b前記多数の差分画像において画素幅極値を配置する工程と、c各差分画像において各画素について画素勾配ベクトルを生成する工程と、d請求項1乃至9のいずれか一項に記載の方法を適用して、ベクトルの方位を、各差分画像に関連付けられた実際の最大および最小幅画素のそれぞれに関連付ける工程と、を備えた方法。複数の画素によって画成された画像におけるスケール不変特徴を識別するための画像処理装置であって、請求項1乃至10のいずれか一項に記載の方法を実施するように構成されたプロセッサ回路を備えた、画像処理装置。前記画像処理装置は多数のチップを備え、各チップは、請求項1の工程vの前記特定のベクトルの前記最適マッチングの識別の一部を実行するように構成されている、請求項11記載の画像処理装置。前記画像処理装置は、GPU、DSP、FPGAおよびASICから成るグループの中から選択された少なくとも1つの要素を備える、請求項11または12に記載の画像処理装置。前記画像処理装置は、前記参照点ベクトルを記憶するための手段、前記データセットの、記憶された前記ベクトル、前記距離dおよびdgroup、および前記特定のベクトルを受け取るための手段を備える、請求項11乃至13のいずれか一項に記載の画像処理装置。コンピュータプログラムであって、前記プログラムがコンピュータ上で実行されたときに請求項1乃至10のいずれか一項のすべての工程を実行するためのプログラムコード手段を備えた、コンピュータプログラム。コンピュータプログラム製品であって、前記プログラム製品がコンピュータ上で実行されたときに請求項1乃至10のいずれか一項の方法を実行するためのコンピュータ読取り可能な媒体上に記憶されたプログラムコード手段を備えたコンピュータプログラム製品。請求項1乃至10のいずれか一項に記載の方法を実行するソフトウェアプログラム。複数の画素によって画成された画像におけるスケール不変特徴を識別するように成された、請求項17記載のソフトウェアプログラム。最近傍探索問題近接探索としても知られている最近傍探索、類似探索、または最近接点探索は、多くの適用分野で生じている。適用分野としては、これらに限定される訳ではないが、パターン認識特に工学文字認識、統計分類k近傍法、コンピュータビジョン、データベースにおける内容型画像検索、符号理論、データ圧縮、レコメンデーションシステム、インターネットマーケティング、DNAシーケンシング、スペルチェック正しいスペルの提示、剽窃検知、プロスポーツ選手のキャリアパスを予測するための類似スコア、クラスター分析通常はユークリッド距離に基づいて、同じクラスターにおける観察が、ある意味で類似するように、サブセット、即ちクラスターの中に観察のセットを割り当てること、多変量密度推定およびパターン分類、および機会学習が含まれる。本発明の発明者は、探索時間を短縮することができ、追加的に探索時間を短縮することを可能にしつつ、更に容易に並行処理に適合できる方法を考え出した。本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするための方法に関し、この方法は、i参照点ベクトルを選択する工程と、ii前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離dを計算する工程と、iii前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離dgroupを持つベクトルのグループにソートする工程であって、aその後、2つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第2ベクトルが前記グループの第1ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する、工程と、iv前記特定のベクトルの最適マッチングを、a前記参照点ベクトルと前記特定のベクトルとの間の距離dspecificを計算する工程と、b計算された前記距離dspecificに最も近い距離dを備えたベクトルを持つ1つまたは複数の前記グループを識別する工程と、c前記特定のベクトルに最も近い距離dminimumを持つ1つまたは複数の識別された前記グループの中の1つまたは複数の前記ベクトルを識別する工程と、dゼロよりも大きく、dspecific-dminimumからdspecificdminimumのインターバルの中の前記参照点ベクトルから、距離dを備えた任意の追加のグループを識別する工程と、e前記インターバルの中のすべてのグループが検討されるまで、工程ivcおよび工程ivdを繰り返す工程と、によって識別する工程と、を備える。当業者は、本方法がマトリクスおよびテンソルにも適合可能であることを理解するであろう。より良いマッチングのための探索が、並行処理に適合可能である。当業者は、さらに、この方法が、第2の最良適合、第3の最良適合等を見つけ出すために容易に適合可能であることを理解するであろう。本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするための方法であって、前記ベクトルは、少なくとも1つの画像におけるスケール不変特徴を識別するために、スケール不変特徴を表す、方法において、i参照点ベクトルを選択する工程と、ii前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離dを計算する工程と、iii前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離dgroupを持つベクトルのグループにソートする工程であって、aその後、2つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第2ベクトルが前記グループの第1ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する、工程と、iv前記特定のベクトルの最適マッチングを、a前記参照点ベクトルと前記特定のベクトルとの間の距離dspecificを計算する工程と、b計算された前記距離dspecificに最も近い距離dを備えたベクトルを持つ1つまたは複数の前記グループを識別する工程と、c前記特定のベクトルに最も近い距離dminimumを持つ1つまたは複数の識別された前記グループの中の1つまたは複数の前記ベクトルを識別する工程と、dゼロよりも大きく、dspecific-dminimumからdspecificdminimumのインターバルの中の前記参照点ベクトルから、距離dを備えた任意の追加のグループを識別する工程と、e前記インターバルの中のすべてのグループが検討されるまで、工程ivcおよび工程ivdを繰り返す工程と、によって識別する工程と、を備えた方法に関する。本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルを次にマッチングするために前記データセットを編成するための方法であって、i参照点ベクトルを選択する工程と、ii前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離dを計算する工程と、iii前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離dgroupを持つベクトルのグループにソートする工程と、ivその後、2つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第2ベクトルが前記グループの第1ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、を備えた方法に関する。この特徴は、データセットの中からの特定のベクトルの迅速な次のマッチングを可能とする。本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルを次にマッチングするために前記データセットを編成するための方法であって、前記ベクトルは、少なくとも1つの画像におけるスケール不変特徴を次に識別するために、少なくとも1つの画像におけるスケール不変特徴を表す、方法において、i参照点ベクトルを選択する工程と、ii前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離dを計算する工程と、iii前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離dgroupを持つベクトルのグループにソートする工程と、ivその後、2つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第2ベクトルが前記グループの第1ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、を備えた方法に関する。本発明の一つの態様によれば、それは、複数の画素によって画成された原画像において、異なるスケールにわたって安定している画像特徴を識別するための方法であって、a程度の異なるボケを前記原画像に適用することによって得られた差分を計算することによって、前記原画像から、多数の差分画像を取得する工程と、b前記多数の差分画像において画素幅極値を配置する工程と、c各差分画像において各画素について画素勾配ベクトルを生成する工程と、d請求項1乃至9のいずれか一項に記載の方法を適用して、ベクトルの方位を、各差分画像に関連付けられた実際の最大および最小幅画素のそれぞれに関連付ける工程と、を備えた方法に関する。本発明の一つの態様によれば、それは、複数の画素によって画成された画像におけるスケール不変特徴を識別するための画像処理装置であって、本発明による方法を実施するように構成されたプロセッサ回路を備えた、画像処理装置に関する。本発明の一つの態様によれば、それは、本発明による方法を実行するソフトウェアプログラムに関する。本発明の一つの態様によれば、それは、コンピュータプログラムであって、前記プログラムがコンピュータ上で実行されたときに、方法に関する請求項のいずれか一つのすべての工程を実行するためのプログラムコード手段を備えた、コンピュータプログラムに関する。本発明の一つの態様によれば、それは、コンピュータプログラム製品であって、前記プログラム製品がコンピュータ上で実行されたときに、方法に関する請求項のいずれか一つの方法を実行するためのコンピュータ読取り可能な媒体上に記憶されたプログラムコード手段を備えたコンピュータプログラム製品に関する。追加的な態様および実施形態を以下に示す。本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするための方法であって、i参照点ベクトルを選択する工程と、ii前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離dを計算する工程と、iii前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離dgroupを持つベクトルのグループにソートする工程と、ivその後、2つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第2ベクトルが前記グループの第1ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、v前記特定のベクトルの最適マッチングを、a前記参照点ベクトルと前記特定のベクトルとの間の距離dspecificを計算する工程と、b計算された前記距離dspecificに最も近い距離dを備えたベクトルを持つ1つまたは複数の前記グループを識別する工程と、c前記特定のベクトルに最も近い距離dminimumを持つ1つまたは複数の識別された前記グループの中の1つまたは複数の前記ベクトルを識別する工程と、dゼロよりも大きく、dspecific-dminimumからdspecificdminimumのインターバルの中の前記参照点ベクトルから、距離dを備えた任意の追加のグループを識別する工程と、e前記インターバルの中のすべてのグループが検討されるまで、工程vcおよび工程vdを繰り返す工程と、によって識別する工程と、を備えた方法に関する。dspecific-dminimumはゼロよりも小さいかも知れないので、ゼロおよびdspecific-dminimumの大きい方を採用する必要がある。好ましくは、インターバル全体が使用され、このインターバル全体は、iゼロおよびdspecific-dminimumの大きい方、およびiidspecificdminimumの制限値の前記参照点ベクトルからの距離を持つグループを含んでいる。好ましさではより劣る方法において、良好な候補が求められる場合にのみ、例えば時間を節約するために、このインターバルの中のグループのみが使用される。より良いマッチングが識別されるにつれて、距離dminimumが短くなる。故に、dspecific-dminimumからdspecificdminimumのインターバルがより短くなり、検討すべき追加のグループの数が減少する。より良いマッチングのための探索が、並行処理に適合可能であり、例えば、dspecificよりも短い距離dを持つグループについて、およびdspecificよりも長い距離dを持つグルーブについて独立に、探索が実施されるかも知れない。そのような独立の探索は、これまでに識別された最短距離dminimumについて適切に比較し、それに続いて分配することを可能とする。この方法は、さらに、第2の最良適合、第3の最良適合等を見つけ出すために容易に適合可能である。本発明の一つの実施形態によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするための方法であって、前記ベクトルは、少なくとも1つの画像におけるスケール不変特徴を識別するために、スケール不変特徴を表す、方法において、i参照点ベクトルを選択する工程と、ii前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離dを計算する工程と、iii前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離dgroupを持つベクトルのグループにソートする工程と、ivその後、2つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第2ベクトルが前記グループの第1ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、v前記特定のベクトルの最適マッチングを、a前記参照点ベクトルと前記特定のベクトルとの間の距離dspecificを計算する工程と、b計算された前記距離dspecificに最も近い距離dを備えたベクトルを持つ1つまたは複数の前記グループを識別する工程と、c前記特定のベクトルに最も近い距離dminimumを持つ1つまたは複数の識別された前記グループの中の1つまたは複数の前記ベクトルを識別する工程と、dゼロよりも大きく、dspecific-dminimumからdspecificdminimumのインターバルの中の前記参照点ベクトルから、距離dを備えた任意の追加のグループを識別する工程と、e前記インターバルの中のすべてのグループが検討されるまで、工程vcおよび工程vdを繰り返す工程と、によって識別する工程と、を備える方法に関する。本発明の一つの実施形態によれば、それは、検討されるべき次のグループが、dspecificに最も近い距離dを持つ未検討のグループである、方法に関する。未検討のグループとは、そのグループのベクトルが、dminimumよりも特定のベクトルに近いベクトルの識別のための検討が未だ行われていないグループである。これに代えて、探索は、例えば、dspecificに最も近い距離dを持つグループからスタートし、未検討のグループの中を下降しまたは上昇するように行われるかも知れないし、或いは、好ましくは、並行処理を用いることによって、下降と上昇が同時に行われる。本発明の一つの実施形態によれば、それは、ベクトルが少なくとも1つの画像の中の特徴を表す、方法に関する。本発明の一つの実施形態によれば、それは、ベクトルが少なくとも1つの画像の中のスケール不変特徴を表す、方法に関する。本発明の一つの実施形態によれば、それは、少なくとも1つの画像の中のスケール不変特徴を識別するために使用される方法に関する。本発明の一つの実施形態によれば、それは、ベクトルが多次元である、方法に関する。本発明の一つの実施形態によれば、それは、前記距離d、dgroup、dspecificおよびdminimumは、ユークリッド距離、マハラノビス距離、マンハッタン距離、チェビシェフ距離、およびミンコフスキー距離から成るグループの中から選択される距離として計算される、方法に関する。マハラノビス距離は、距離メトリックスケール不変量を作成するための共分散マトリックスの基づく正規化を意味する。マンハッタン距離は、軸整列された方向のみに従う距離の測定を意味する。チェビシェフ距離は、最も重要なディメンションdimensionのみが関連すると仮定した距離の測定を意味する。ミンコフスキー距離は、ユークリッド距離、マンハッタン距離、およびチェビシェフ距離を統合する一般化を意味する。本発明の一つの実施形態によれば、それは、前記距離d、dgroup、dspecificおよびdminimumは、ユークリッド距離として計算される、方法に関する。本発明の一つの実施形態によれば、それは、前記参照点ベクトルがデータセットの中から選択される、方法に関する。本発明の一つの実施形態によれば、それは、前記参照点ベクトルがデータセットの中点として選択される、方法に関する。本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルを次にマッチングするために前記データセットを編成するための方法において、i参照点ベクトルを選択する工程と、ii前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離dを計算する工程と、iii前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離dgroupを持つベクトルのグループにソートする工程と、ivその後、2つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第2ベクトルが前記グループの第1ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、を備えた方法に関する。本発明の一つの態様によれば、それは、複数のベクトルから成るデータセットの中から特定のベクトルを次にマッチングするために前記データセットを編成するための方法であって、前記ベクトルは、少なくとも1つの画像におけるスケール不変特徴を次に識別するために、少なくとも1つの画像におけるスケール不変特徴を表す、方法において、i参照点ベクトルを選択する工程と、ii前記参照点ベクトルと前記データセットの前記ベクトルとの間の距離dを計算する工程と、iii前記データセットの前記ベクトルを、前記参照点ベクトルから同じ距離dgroupを持つベクトルのグループにソートする工程と、ivその後、2つよりも多くのベクトルを含む、前記グループの各々を、前記グループの第2ベクトルが前記グループの第1ベクトルまで最小距離を有し、前記グループの次の各ベクトルが前記グループの以前のベクトルまで最小距離を有するように、再編成する工程と、を備えた方法に関する。本発明の一つの実施形態によれば、それは、好ましくは少なくとも1つの画像におけるスケール不変特徴を識別するために、複数のベクトルから成るデータセットの中から特定のベクトルをマッチングするために使用される方法の特徴に関し、この方法は、v前記特定のベクトルの最適マッチングを、a前記参照点ベクトルと前記特定のベクトルとの間の距離dspecificを計算する工程と、b計算された前記距離dspecificに最も近い距離dを備えたベクトルを持つ1つまたは複数の前記グループを識別する工程と、c前記特定のベクトルに最も近い距離dminimumを持つ1つまたは複数の識別された前記グループの中の1つまたは複数の前記ベクトルを識別する工程と、dゼロよりも大きく、dspecific-dminimumからdspecificdminimumのインターバルの中の前記参照点ベクトルから、距離dを備えた任意の追加のグループを識別する工程と、e前記インターバルの中のすべてのグループが検討されるまで、工程vcおよび工程vdを繰り返す工程と、によって識別する工程と、をさらに備える。この実施形態は、この方法の特徴が、最初にデータセットを編成し、続いて各マッチングが急速に完了することを許容するかも知れないことを示す。本発明の一つの実施形態によれば、それは、複数の画素によって画成された原画像において、異なるスケールにわたって安定している画像特徴を識別するための、本発明による方法であって、a程度の異なるボケを前記原画像に適用することによって得られた差分を計算することによって、前記原画像から、多数の差分画像を取得する工程と、b前記多数の差分画像において画素幅極値を配置する工程と、c各差分画像において各画素について画素勾配ベクトルを生成する工程と、d請求項1乃至9のいずれか一項に記載の方法を適用して、ベクトルの方位を、各差分画像に関連付けられた実際の最大および最小幅画素のそれぞれに関連付ける工程と、を備えた方法に関する。本発明の一つの実施形態によれば、それは、複数の画素によって画成された画像におけるスケール不変特徴を識別するための画像処理装置であって、本発明による方法を実施するように構成されたプロセッサ回路を備えた、画像処理装置に関する。本発明の一つの実施形態によれば、それは、本発明の画像処理装置に関し、前記画像処理装置は多数のチップを備え、各チップは、特定のベクトルの前記最適マッチングの識別の一部を実行するように構成されている。本発明の一つの実施形態によれば、それは、本発明の画像処理装置に関し、前記画像処理装置は、GPU、DSP、FPGAおよびASICから成るグループの中から選択された少なくとも1つの要素を備える。本発明の一つの実施形態によれば、それは、本発明の画像処理装置に関し、前記画像処理装置は、前記参照点ベクトルを記憶するための手段、前記データセットの、記憶された前記ベクトル、前記距離dおよびdgroup、および前記特定のベクトルを受け取るための手段を備える。本発明の一つの実施形態によれば、それは、コンピュータプログラムであって、前記プログラムがコンピュータ上で実行されたときに請求項のいずれか一項のすべての工程を実行するためのプログラムコード手段を備えた、コンピュータプログラムに関する。本発明の一つの実施形態によれば、それは、コンピュータプログラム製品であって、前記プログラム製品がコンピュータ上で実行されたときに請求項のいずれか一項の方法を実行するためのコンピュータ読取り可能な媒体上に記憶されたプログラムコード手段を備えたコンピュータプログラム製品に関する。本発明の一つの実施形態によれば、それは、本発明による方法を実行するためのソフトウェアプログラムに関する。本発明の一つの実施形態によれば、それは、複数の画素によって画成された画像におけるスケール不変特徴を識別するように成された、本発明によるソフトウェアプログラムに関する。すべての引用文献は、参照により組み込まれたものとする。添付の図面および例は、本発明を限定するのではなく説明するために提供される。当業者において、本発明の態様、実施形態、および請求項を組み合わせ可能であることは明らかである。以下に図面が紹介されており、続いて幾つかの図面がさらに説明されている。本例は、メモリー要素にてn次元データベクトルを組織化し、探索することにより、高速データベクトルマッチングについての本発明の実施形態を実施する方法に関する。この方法は、多次元探索キー例えば、レンジ探索および最近傍探索を含む探索のような、幾つかの適用にとって有益である。この方法は、探索をスピードアップするような方法で特別なメモリーコンストラクションにおいて参照データベクトルを静的に構築し、動的に入力されたデータベクトルをリアルタイムでマッチングすることに依存している。この方法および本発明は、log2のファクターまでのデータベクトル間のマッチングを見つけ出すためのデータベース内の探索数を潜在的に低減する。ここで、サイズとは、データベクトルの数における参照データベースのサイズである。これは図1に図解されている。この方法は、FPGAおよびASICのようなGPU、DSPおよび並列処理ハードウェアにおいて実行され得る。この方法は、適応性のある加速された探索を可能とする特別の編成に参照データベクトル構築し、来入データベクトルにスキームをマッチングすることによって機能する。この方法は、ソートフェーズ、並びに探索およびマッチングフェーズを含む。メモリー要素内に任意に編成されたn次元参照データベクトルのデータベースを仮定すれば、この方法は、参照データベクトルの中から、マッチングまたは新しく来入データベクトルまでの最近傍参照データベクトルを見つけ出すという問題を解決する。マッチングデータベクトルは、この文脈においては、来入データベクトルまで最小距離例えばユークリッド距離を持つベクトルとして定義される。この方法では、参照データベクトルは、共通の参照データベクトルまでの昇順距離の関数としてメモリー内で最初に再編成される。共通の参照データベクトルは、既存のデータベクトルのセットから、任意または明確な基準のいずれかによって選択される。再編成が終了すると、編成されたメモリーの最初の位置でのデータベクトルは、共通の参照ベクトルまでの最小距離を持つデータベクトルを含む。ソートされたメモリー内の次のアドレスは、参照までの同じ最小距離を持つデータベクトルの残りを、そのようなベクトルが存在する場合にはこれを保持する。さもなければ、これらの昇順アドレスは、共通の参照ベクトルまでの昇順距離を備えた参照データベクトルを保持する。共通の参照までの同じ距離を持つベクトルは、以下の方法にて編成される。すなわち、もしメモリー内のアドレスXが、共通の参照までの距離Yを備えたデータベクトルAを保持している場合、位置X1は、参照データベクトルのデータベクトルBを保持し、このときの参照データベクトルは、共通の参照までの同じ距離Yを持ち、同時にAまでの最小距離を持つベクトルそのようなベクトルが存在する場合にはである。そして、位置X2は、共通の参照までの距離YおよびBまでの最小距離を持つベクトルCをここでもまた、そのようなベクトルが存在する場合には保持する。図2は、ソートされたメモリー編成の図解例を提供する。この図において、点Dは、共通の参照までの絶対的な最小距離を有し、それ故に最初のメモリーアドレスに配置されている、単一データベクトルを表している。点Sは、共通の参照までの、次に最も短い距離を持つデータベクトルを表しており、以下同様である。この図において、点A、B、Cは、共通の参照点までの等しい距離を持つ3つのデータベクトルを表している。点Bは、Aによって表される参照データベクトルまでの最も短い距離を持つデータベクトルを表し、同様に、点Cは、Bによって表される参照データベクトルまでの最も短い距離を備えた参照データベクトルを表している。ソートを行う際に、繰り返しのデータベクトルが除去される。結果として得られるアレイの中の各データベクトルは、共通の参照点までのその距離と一緒に、同じメモリー位置において、インデックス化および探索を容易にする他のデータフィールドと一緒に保存される。これは図4に例示されている。上述の方法でデータベクトルが再編成されると、既存の参照データベクトルの中からの、外来データベクトルへの最適マッチングまたは最近傍の迅速な決定が、連続近似法を用いて可能となる。この方法では、共通の参照ベクトルまでの外来データベクトルの距離が最初に計算され、編成されたアレイの中央位置に保存された距離と比較される。計算された距離が、保存された距離よりも小さい場合には、メモリースペースの下半分にて最適マッチングが見つけ出されると推定される。この場合、次の探索は、計算された距離を、メモリースペースの下半分の中央のメモリー位置に保存されたデータベクトルと比較することによって起こる。それとは逆に、計算された距離が、メモリースペースの中央にある保存された距離よりも大きいことが分かった場合には、最近傍は、編成されたメモリーの上半分の位置に見つけ出されると推定される。この場合、次の探索は、計算された距離を、メモリースペースの上半分の中央位置に保存された距離と比較することによって行われる。最後に、計算された距離が、保存された距離に等しい場合は、最近傍は、中央メモリー位置の周囲に保存された参照データベクトルの一つであると推定される。この方法においては、n次元データベクトルが、粗く保存されており、データベクトルによって表された、単一の、任意に選択された参照点までの距離の昇順にてFIFOの中に保存されている。かくして、図3の例に示されているように、すべての参照データベクトルが共通の参照点までの距離の関数として点にマッピングされたユークリッド空間が生成される。保存された参照点の共通の参照点までのそれぞれの距離は、フェッチングプロセスの際にこれらを再度計算しなければならない事態を回避するために、同じメモリーアドレスにおいて参照点と一緒に随意に保存され、これのコストは、メモリーサイズへの追加的な要求であろう。参照点は、保存されたデータベクトルの一つであり、かくして、保存されたメモリー要素、例えばFIFOの中の最初の点は、参照までの最小距離を持つデータベクトルである。保存されたメモリーの中の次のアドレスは、任意に編成され、参照までの次の最小距離を持つベクトルがこれに続く、参照までの同じ最小距離を持つすべてのデータベクトルを保持し、以下同様である。故に、保存されたメモリー内の最後のアドレスは、参照データベクトルまでの最大距離を持つデータベクトルのセットを保持する。図3の例においては、中心参照点の周囲の内側円が、その周囲に、参照までの最小距離を持つデータベクトルを表す点を含んでおり、太い黒い周囲の外側円が、例参照データセットの中から参照までの最大距離のデータベクトルを表す点を含んでいる。図3に示されているように、参照点までの等しい距離を備えたデータ点は、円の周囲を形成しており、この円は、参照点に中心が置かれており、該距離に等しい半径を備えている。粗いソートに続く細かいソートにおいては、これらの点もまた、以下の方法にて、それらの相互距離の関数としてFIFO内に編成される。すなわち、連続メモリーアドレスは、互いに最も近い点を含んでおり、それらの間の最も短い距離によって識別される例えば、もしアドレスxが、共通の参照点までの距離yを備えたデータ点Aを含む場合、アドレスx1は、Aまで最も短い距離を持ち、共通の参照データ点まで同じ距離yを持つ、データ点Bを、そのような点が、マッピングされた参照点のセットの中に存在する場合には、含むであろう図3参照。図6および図7は、粗いソートプロセスおよび細かいソートプロセスをそれぞれ例示している。粗いソートフェーズおよび細かいソートフェーズは、来入データベクトルとのマッチングのために迅速な探索参照データベクトルを助けるFIFO/メモリーおよびデータ構造を提供する。単一の、ソートされたFIFO/メモリー位置でのデータ構造が図4に例示されており、結果として得られるFIFO/メモリー構造が図5に例示されている。これらの図によって示されているように、拡張FIFO/メモリー内の各位置は、以下のデータフィールドを含んでいる下線付与:データベクトルフィールド参照点から成るn次元データベクトルを表すデータフィールド。距離フィールド随意本明細書中で共通の参照点と呼ばれている、選択された共通の参照データベクトルまでの特定のデータベクトルの計算された距離を表すデータフィールド。これは、随意のフィールドである。これは、メモリーサイズへの要求を軽減するために除去することができる。除去された場合には、オンザフライで必要に応じて距離が計算される。サイズ/インデックスフィールドおよび繰返しフラグフィールドサイズ/インデックスsz/ndxフィールドは、サイズまたはインデックスを表す2つの値のうちの1つを含む。FIFO/メモリー位置が、距離フィールドにて与えられた距離を備えた最初のデータベクトルを含む場合、フィールドは、共通の参照までの同じ距離を持つデータベクトルセットのサイズを表す値を含むか、さもなければ、フィールドは、参照までの同じ距離を備えた連続データベクトルの増大されたインデックスを表す数を含んでいるだろう。繰返しフラグフィールドは、距離フィールドが以前のFIFO位置から繰り返される場合に1にセットされ、それ以外は0にリセットされるフィールドである。図5の例において、アドレス00000でのサイズ/インデックスフィールド内の数3は、選択された参照点までの距離xxxxを持つ参照データベクトルの全体の数が3つであることを示している。アドレス00000での繰返しフラグフィールド内の0は、データベクトルフィールド内のデータベクトルが、参照点までの距離xxxxを持つFIFO内の最初のものであることを示している。アドレス00001において、繰返しフラグは、この位置でのデータベクトルが、参照点まで、先行するアドレスこの場合は00000でのデータベクトルと同じ距離を持っていることを示すために、1にセットされ、サイズ/インデックスフィールド内のインデックス値1は、手元にあるものと同じ参照までの距離を備えた参照データベクトルを持つFIFO内の以前の位置が1つのみであることを示し、アドレス00003での値3は、このアドレスでのデータベクトルと同じ参照点までの距離を持つ参照データベクトルを保存する、以前のFIFO位置が、全体で3つであることを示している。来入データベクトルの、共通の参照点までの距離は、オンザフライで計算され、ソートされたFIFO内の保存された距離と粗く比較され-或いは、ここでもまたオンザフライで計算され-、来入点を取り囲むかも知れない円の周囲に最も近い円周囲を見つけ出す。最も近い円周囲は、図8のフローチャートによって例示されたように見つけ出される。同図においては、以下の略語が使用されている。Addr.:用語FIFOアドレスを短縮したもの。Strt.:スタートの略語である即ち、strtAddrは、FIFO内の探索スタートアドレスであるスタートアドレスの略語である。EndAddr.は、探索エンドアドレスである。略語strtが単独で使用される場合、それは探索スタートアドレスを意味する。End:探索エンドアドレスを意味する。Dist:距離ディスタンスの略語である。Eucl.:ユークリッドの略語である。図において、ユークリッド距離が例として使用されており、Eucl.Dist.のように示されている。Res:結果リザルトの略字である。図において、resはレジスターとして扱われている。Crnt.:現在カレントを意味している。この略語が単独で使用される場合、それは現在のFIFOアドレスを意味する。Ndx.:インデックスの略語であり、本明細書中で先に説明したように、ndxデータフィールドによって表されるインデックスを意味している。図5参照。Rev.:用語リバースの略語である。ここで、rev.はフラグであり、セット時にFIFOからの読み込みが現在の円の最後の点から起こるようにする。図3を参照すれば、それは点Dであろう。ここで、このアイデアは、比較点の無関係を飛び越える。Rd.は読み込みリードの略語である。ここでは、FIFO読込みアドレスを示すために使用され、FIFO書込みアドレスと区別される。サイズは、図5に例示されているように、szフィールド内の値を参照している。繰返しフラグ:これは、図5に例示されているように、Rep.flagの値である。最初:これは、粗い探索によって見つけ出される最初のFIFO探索アドレスである。そして、最初は最も近い円周囲および隣接の周囲上の点の中から、来入点までの最小距離を備えた最も近い点を見つけ出すために、比較がリファインされる。図9、図10、図11、および図12は、細かい探索およびマッチングのプロセスを例示している。付録SIFT特徴のような画像特徴は、ベクトルによって表されるかも知れない。これは、以下に示す引用によって本付録の中に例示されている。当業者は、例えば米国特許第6711293号およびWikipediaから、SIFT法に精通している。米国特許第6711293号は、サブ領域記述子のセットという用語を用いており、Wikipediaは、これに代えて、記述子ベクトル、ベクトル、記述子という用語を用いている。本件特許請求の範囲および明細書の残余部分においては、ベクトルの用語を用いている。Wikipediaからの引用スケール不変特徴変換以下強調付加。キーポイント記述子以前の工程は、キーポイント位置を特定のスケールにて見つけ出し、それらに方位を割り当てた。これにより、画像位置、スケールおよび回転への不変性を確保する。さて、我々は、イルミネーション、3D視点などの残余の変量に対して記述子はその弁別性が高く且つ部分的に不変であるように、各キーポイントについて記述子ベクトルを算定することを欲する。この工程は、スケールにおいてキーポイントスケールに最も近い画像上で実施される。最初に、方位ヒストグラムのセットが、各8ビンを備えた4×4ピクセル近傍上で生成される。これらのヒストグラムは、各ヒストグラムが原近傍領域の4×4サブ領域からのサンプルを含むように、キーポイントの周りの16×16領域の中のサンプルの大きさおよび方位の値から算定する。この大きさは、さらに、記述子窓の幅の半分に等しいσを備えたガウス関数によって重み付される。そして、記述子は、これらヒストグラムの値のすべてのベクトルになる。各8ビンを備えた4×4=16ヒストグラムがあるので、ベクトルは128要素を持つ。そして、このベクトルは、不変性を高めてイルミネーション内の変化をアフィンするために、単位長さに正規化される。非線形イルミネーションの影響を低減するために、0.2の閾値が適用され、ベクトルが再び正規化される。記述子のディメンション、即ち128は、高いように見えるけれど、これよりも低いディメンションを備えた記述子は、マッチングタスクの範囲にわたって同様に機能することができずおよび、最近傍を見つけ出すために使用される概算BBF下記参照法の故に演算コストが抑制される。より長い記述子は、より良い働きをするが、ずっと良い訳でなく、歪みおよび閉塞の感度が増大するという追加の危険がある。それはまた、特徴マッチング精度が、50度までの視点変化について50よりも高いことを示している。それ故、SIFT記述子は、小さなアフィン変化に対して不変である。SIFT記述子の弁別性を試験するために、試験データベース内のキーポイントの数を変化させて、マッチング精度もまた測定された。そして、非常に大きなデータベースサイズに対して、マッチング精度は非常に僅かしか低下しないことが示されており、かくして、SIFT特徴の弁別性が高いことが示されている。米国特許第6711293号、段落[0071]の記述からの引用もし、ブロック198において、サブ領域内の対象の最後の点が検討されると、ブロック202は、プロセッサー22に対して、角コンポーネントセットおよびこれらの関連するコンポーネント記述子要素を、領域と関連して保存するように指示する。かくして、各全領域について、8セットのコンポーネントサブ領域記述子が、全数で128あり、極値について全領域を表している、ということが分かる。8セットのコンポーネントサブ領域記述子は、画像の1つのスケール不変特徴を表す。