(57)【特許請求の範囲】
【請求項１】
入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の前記登録ベクトルから、前記入力ベクトルに最も類似する登録ベクトルないしＫ番目に類似する登録ベクトルの、Ｋ個の登録ベクトルを検索する検索システムであって、
少なくともＫ個以上の前記登録ベクトルのそれぞれに対して、前記入力ベクトルおよび当該登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出する部分類似度算出手段と、
少なくともＫ個以上の前記部分類似度のそれぞれに対して、前記類似度を算出した場合に見込まれる当該類似度の上限および下限を、当該部分類似度に基づいて算出する限界算出手段と、
前記類似度の上限が算出された登録ベクトルについて、前記類似度の上限と、少なくともＫ個以上の前記類似度の下限のうちＫ番目に高い前記類似度の下限と、の比較の結果に応じて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する棄却判定手段と、
を備える検索システム。
【請求項２】
入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の前記登録ベクトルから、前記入力ベクトルに最も類似する登録ベクトルないしＫ番目に類似する登録ベクトルの、Ｋ個の登録ベクトルを検索する検索システムであって、
少なくともＫ個以上の前記登録ベクトルに対してそれぞれ算出された少なくともＫ個以上の前記類似度のうち、最も高い類似度からＫ番目に高い類似度までのＫ個の類似度の値を記憶している候補記憶手段と、
前記入力ベクトルおよび前記登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出する部分類似度算出手段と、
前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度に基づいて算出する限界算出手段と、
前記候補記憶手段が記憶している類似度のうちＫ番目に高い類似度の値と、前記類似度の上限との比較の結果に応じて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する棄却判定手段と、
を備える検索システム。
【請求項３】
前記限界算出手段は、前記類似度を算出した場合に見込まれる当該類似度の上限を、
前記部分類似度と、
前記次元のうち残りの次元に関するノルムに０以上１以下の係数を乗じた値と、
に基づいて算出する、
請求項１または２に記載の検索システム。
【請求項４】
入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の登録ベクトルから入力ベクトルに類似する登録ベクトルを検索する検索システムにおいて、
前記入力ベクトルおよび前記登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出する部分類似度算出手段と、
前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度に基づいて算出する限界算出手段と、
前記類似度の上限に基づいて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する棄却判定手段と、
を備え、
前記類似度は前記入力ベクトルおよび前記登録ベクトルの全ての次元を用いて算出される値であり、
前記限界算出手段は、前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度と、前記複数の次元のうち残りの次元に関するノルムと、に基づいて算出し、前記限界算出手段は、検索処理実行時にあらかじめ算出されている値である、ベクトルの各次元の値の二乗値を読み出し、当該読み出した値を用いて前記残りの次元に関するノルムの値を算出する、
検索システム。
【請求項５】
入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の前記登録ベクトルから、前記入力ベクトルに最も類似する登録ベクトルないしＫ番目に類似する登録ベクトルの、Ｋ個の登録ベクトルを検索するコンピュータが、
少なくともＫ個以上の前記登録ベクトルのそれぞれに対して、前記入力ベクトルおよび当該登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出し、
少なくともＫ個以上の前記部分類似度のそれぞれに対して、前記類似度を算出した場合に見込まれる当該類似度の上限および下限を、当該部分類似度に基づいて算出し、
前記類似度の上限が算出された登録ベクトルについて、前記類似度の上限と、少なくともＫ個以上の前記類似度の下限のうちＫ番目に高い前記類似度の下限と、の比較の結果に応じて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する、
検索方法。
【請求項６】
入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の前記登録ベクトルから、前記入力ベクトルに最も類似する登録ベクトルないしＫ番目に類似する登録ベクトルの、Ｋ個の登録ベクトルを検索するコンピュータが、
少なくともＫ個以上の前記登録ベクトルに対してそれぞれ算出された少なくともＫ個以上の前記類似度のうち、最も高い類似度からＫ番目に高い類似度までのＫ個の類似度の値を候補記憶手段に記憶させ、
前記入力ベクトルおよび前記登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出し、
前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度に基づいて算出し、
前記候補記憶手段が記憶している類似度のうちＫ番目に高い類似度の値と、前記類似度の上限との比較の結果に応じて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する、
検索方法。
【請求項７】
入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の登録ベクトルから入力ベクトルに類似する登録ベクトルを検索するコンピュータが、
前記入力ベクトルおよび前記登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出し、
前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度に基づいて算出し、
前記類似度の上限に基づいて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定し、
前記類似度は前記入力ベクトルおよび前記登録ベクトルの全ての次元を用いて算出される値であり、
前記類似度を算出した場合に見込まれる当該類似度の上限の算出は、前記部分類似度と、前記複数の次元のうち残りの次元に関するノルムと、に基づく算出であり、
検索処理実行時にあらかじめ算出されている値である、ベクトルの各次元の値の二乗値を読み出し、当該読み出した値を用いて前記残りの次元に関するノルムの値を算出する、
検索方法。
【請求項８】
入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の前記登録ベクトルから、前記入力ベクトルに最も類似する登録ベクトルないしＫ番目に類似する登録ベクトルの、Ｋ個の登録ベクトルを検索するコンピュータに、
少なくともＫ個以上の前記登録ベクトルのそれぞれに対して、前記入力ベクトルおよび当該登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出する処理と、
少なくともＫ個以上の前記部分類似度のそれぞれに対して、前記類似度を算出した場合に見込まれる当該類似度の上限および下限を、当該部分類似度に基づいて算出する処理と、
前記類似度の上限が算出された登録ベクトルについて、前記類似度の上限と、少なくともＫ個以上の前記類似度の下限のうちＫ番目に高い前記類似度の下限と、の比較の結果に応じて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する処理と、
を実行させるプログラム。
【請求項９】
入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の前記登録ベクトルから、前記入力ベクトルに最も類似する登録ベクトルないしＫ番目に類似する登録ベクトルの、Ｋ個の登録ベクトルを検索するコンピュータに、
少なくともＫ個以上の前記登録ベクトルに対してそれぞれ算出された少なくともＫ個以上の前記類似度のうち、最も高い類似度からＫ番目に高い類似度までのＫ個の類似度の値を候補記憶手段に記憶させる処理と、
前記入力ベクトルおよび前記登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出する処理と、
前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度に基づいて算出する処理と、
前記候補記憶手段が記憶している類似度のうちＫ番目に高い類似度の値と、前記類似度の上限との比較の結果に応じて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する処理と、
を実行させるプログラム。
【請求項１０】
入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の登録ベクトルから入力ベクトルに類似する登録ベクトルを検索するコンピュータに、
前記入力ベクトルおよび前記登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出する処理と、
前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度に基づいて算出する上限算出処理と、
前記類似度の上限に基づいて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する処理と、
を実行させ、
前記類似度は前記入力ベクトルおよび前記登録ベクトルの全ての次元を用いて算出される値であり、
前記上限算出処理は、前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度と、前記複数の次元のうち残りの次元に関するノルムと、に基づいて算出し、
前記上限算出処理は、検索処理実行時にあらかじめ算出されている値である、ベクトルの各次元の値の二乗値を読み出し、当該読み出した値を用いて前記残りの次元に関するノルムの値を算出する、
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン検索に関する。
【背景技術】
【０００２】
画像処理または音声処理の分野では、複数の登録パターンを記憶しているデータベースから、入力パターンに最も類似した登録パターンを検索する、などの処理が行われる。このような処理はパターン検索と呼ばれる。【０００３】
多くの場合、パターンは特徴ベクトルとして表現される。パターン検索を実行する検索システムは、入力パターンの特徴ベクトルと登録パターンの特徴ベクトルとの類似度を算出する。そして、検索システムは、類似度が高い登録パターンを検索結果として出力する。【０００４】
データベースに登録されている登録パターンの個数が非常に多い場合、入力パターンと登録パターンとの類似度の算出を検索システムが単純に繰り返すと、計算コストが非常に大きくなってしまう。そこで、検索処理を高速化する方法が必要となる。【０００５】
検索処理を高速化する方法は大きく２種類存在する。1つは近似最近傍探索、もう1つはカスケードである。【０００６】
まず、Locally Sensitive Hashing （LSH）またはSpectral Hashingに代表される近似最近傍探索について説明する。近似最近傍探索において、検索システムは、特徴ベクトルをインデックスに変換し、入力パターンと同じインデックスを持つ登録パターンに関してのみ類似度を算出する。これにより、検索システムが類似度を算出する回数が低減するため、検索システムは高速に検索を行うことができる。このような検索方法では、検索精度および検索速度は、インデックスをどのように作成するかに大きく依存する。特許文献１および特許文献２は、その方法の一例を開示する。以上、近似最近傍探索について説明した。【０００７】
次にカスケードについて説明する。カスケードにおいては、検索システムは、低次元の特徴ベクトルを用いて類似度を算出し、類似度が閾値以下の登録パターンを棄却する。検索システムは、この操作を繰り返し、最終的に棄却されなかった登録パターンについてのみ全ての次元を用いた類似度の算出を行う。多くの登録データは低次元の類似度計算のみで棄却されるため、高速に検索を行うことができる。閾値は事前の学習によって多くの場合決定されるが、例えば特許文献３が開示する検索方法のように、登録パターンに応じて閾値を決めることもできる。以上、カスケードについて説明した。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１１−２２１６８９号公報
【特許文献２】特開２０１２−６３９５９号公報
【特許文献３】特開２００５−１１０４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本明細書では、データベース中から、検索条件として与えられた入力パターンと類似度の高い登録ベクトルをＫ個検索するような検索処理を、Ｋ近傍検索（k-nearest neighbor search）と呼ぶ。ここで、入力パターンと登録パターンとの類似度の算出を単純に繰り返した場合に検索されるＫ個の登録パターンと、高速な検索方法により検索されるＫ個の登録パターンとの一致度を、当該検索方法の「Ｋ近傍正解率」と呼ぶ。Ｋ近傍正解率が高いほど、当該検索方法は正確である。従って、Ｋ近傍正解率が高く、かつ、検索速度が速い検索方法ほど、望ましい検索方法である。【００１０】
特許文献１および特許文献２が開示する検索方法の問題点は、「Ｋ近傍正解率」が低下する場合がある点である。特許文献１および特許文献２が開示する検索方法においては、Ｋ近傍正解率の保証が確率的である。その理由は、近似最近傍探索においてＫ近傍正解率を全く劣化させずに高速化を行うことは原理的に不可能であるためである。高い検索精度が求められるような用途、（例えば、顔認証または音声認証などの認証用途）においては、特許文献１および特許文献２が開示する検索方法では精度が不十分な場合がある。【００１１】
特許文献３が開示する検索方法の問題点は、利用できる類似度がユークリッド距離のみに原理上限定される点である。【００１２】
本発明は、利用できる類似度がユークリッド距離のみには限定されず、かつ、Ｋ近傍正解率が劣化せずに検索処理を高速化できる検索システム、検索方法およびプログラムを提供することを一つの目的とする。
【課題を解決するための手段】
【００１３】
本発明の第１の側面は、入力ベクトルと登録ベクトルとの類似の度合いかを示す指標である類似度に基づいて、複数の登録ベクトルから入力ベクトルに類似する登録ベクトルを検索する検索システムにおいて、前記入力ベクトルおよび前記登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出する部分類似度算出部と、前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度に基づいて算出する限界算出部と、前記類似度の上限に基づいて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する棄却判定部と、を備える検索システムである。【００１４】
本発明の第２の側面は、入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の登録ベクトルから入力ベクトルに類似する登録ベクトルを検索するコンピュータが、前記入力ベクトルおよび前記登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出し、前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度に基づいて算出し、前記類似度の上限に基づいて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する、検索方法である。【００１５】
本発明の第３の側面は、入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の登録ベクトルから入力ベクトルに類似する登録ベクトルを検索するコンピュータに、前記入力ベクトルおよび前記登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出する処理と、前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度に基づいて算出する処理と、前記類似度の上限に基づいて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する処理と、を実行させるプログラムである。【００１６】
また、本発明の目的は、上記のプログラムが格納されたコンピュータ読み取り可能な記憶媒体によっても達成される。
【発明の効果】
【００１７】
本発明によれば、利用できる類似度がユークリッド距離のみには限定されず、かつ、Ｋ近傍正解率が劣化せずに検索処理を高速化できる検索システム、検索方法およびプログラムを提供することができる。
【図面の簡単な説明】
【００１８】
【図１】図１は、本発明における第１の実施形態にかかる検索システム１００の構成を示すブロック図である。
【図２】図２は、本発明における第１の実施形態にかかる検索システム１００の動作を示すフローチャートである。
【図３】図３は、本発明における第１の実施形態にかかる検索システム１００の概要を示す図である。
【図４】図４は、本発明における第１の実施形態にかかる検索システム１００の概要を示す図である。
【図５】図５は、本発明における第１の実施形態にかかる検索システム１００のハードウェア構成の一例を示す図である。
【図６】図６は、本発明における具体例１にかかる検索システム１００の動作を示すフローチャートである。
【図７】図７は、本発明における具体例２にかかる検索システム１００の構成を示すブロック図である。
【図８】図８は、本発明における具体例２にかかる検索システム１００の動作を示すフローチャートである。
【図９】図９は、本発明における具体例６にかかる検索システム１００Ａの構成を示すブロック図である。
【図１０】図１０は、本発明における第２の実施形態にかかる検索システム２００Ｂの構成を示すブロック図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態について図面を参照して詳細に説明する。
【００２０】
＜用語の定義＞
「類似度」という用語を定義する。「類似度」とは、あるベクトルと他のベクトルとがどの程度類似しているかを示す指標である。類似度は、例えば、内積、ユークリッド距離または正規化相関である。以下、あるパターンから抽出された特徴ベクトルと、他のパターンから抽出された特徴ベクトルとの類似度のことを、「あるパターンと他のパターンとの類似度」と表現する場合がある。
【００２１】
「類似度が高い」とは、あるベクトルと他のベクトルとが類似していることを示す。「類似度が低い」とは、あるベクトルと他のベクトルとが類似していないことを示す。類似度の値の大小と類似度の高低との関係は、類似度の定義によって異なる。例えば、類似度を内積により定義した場合には、類似度の値が大きいほど類似度が高くなる。逆に、類似度をユークリッド距離により定義した場合には、類似度の値が小さいほど類似度が高くなる。
【００２２】
以下、理解を容易にするため、類似度の値の大小ではなく、類似度の高低に着目して本実施形態にかかる検索システム１００を説明する。以下の説明において、「類似度と閾値とを比較する処理」についての説明が複数回登場するが、この処理においては「類似度の高低」と「類似度の高さを示す閾値」とが比較されるものとする。
【００２３】
また、以下、「類似度の上限」または「類似度の下限」という文言が登場するが、これらは類似度の値の上限値または下限値を表すものではない。「類似度の上限」または「類似度の下限」は、類似度の高さの上限または下限を表すものである。
【００２４】
＜第１の実施形態＞
（構成の概要の説明）
図１は第１の実施形態にかかる検索システム１００の構成を示すブロック図である。図１に示すように、検索システム１００は、特徴抽出部１１０と、登録パターン記憶部１２０と、部分類似度算出部１３０と、限界算出部１４０と、閾値決定部１５０と、棄却判定部１６０と、を備える。
【００２５】
検索システム１００はＫ近傍検索を実行する。すなわち、検索システム１００は、入力パターンの入力を受け付け、登録パターン記憶部１２０に記憶されている複数の登録パターンの中から、当該入力パターンと類似度の高い登録パターンをＫ個検索して出力する。Ｋの値はあらかじめ設定されていてもよい。Ｋの値はオペレータから入力されてもよい。
【００２６】
特徴抽出部１１０は、入力パターンから特徴ベクトルを抽出する。特徴ベクトルは多次元のベクトルである。以下、特徴ベクトルの次元数をＤと表現する。以下、入力パターンから抽出された特徴パターンを「入力ベクトル」と表現する。
【００２７】
登録パターン記憶部１２０は、複数の登録パターンを記憶している。登録パターン記憶部１２０は、登録パターンと当該登録パターンに対応する特徴ベクトルとを関連付けて記憶していてもよい。以下、登録パターンに対応する特徴ベクトルを「登録ベクトル」と表現する。以下、登録パターン記憶部１２０に記憶されている登録パターンの数をＮとし、登録ベクトルの数もＮ個とする。但し、登録パターンと登録ベクトルは１対１でなくてもよく、異なる登録パターンに同一の登録ベクトルが関連付けられていてもよい。
【００２８】
部分類似度算出部１３０は、特徴抽出部１１０が抽出した入力ベクトルと、登録パターン記憶部１２０に記憶されている登録ベクトルとの部分類似度を算出する。部分類似度とは、入力ベクトルおよび登録ベクトルの次元（すなわちＤ次元）のうち一部の次元に関する類似度である。以下、当該「一部の次元」の次元数をｄと表現する。ここで、１＜ｄ＜Ｄである。記号「＜」は不等号を表す。以下、ｄの初期値をｄ０と表す。
【００２９】
部分類似度の一つの具体例を説明する。例えば、入力ベクトルおよび登録ベクトルが１００次元ベクトルである場合を想定する。すなわち、Ｄ＝１００である。部分類似度は例えば、１００次元のうち一部の次元、例えば、１次元目から１０次元目までの１０個の次元（すなわち、ｄ＝１０）を用いて算出された類似度である。この場合、当該部分類似度を、「ｄ＝１０において算出された部分類似度」と表現する。
【００３０】
限界算出部１４０は、部分類似度算出部１３０が算出した部分類似度に基づいて、当該入力ベクトルおよび当該登録ベクトルの類似度を算出した場合に見込まれる、類似度の上限（以下、単に「類似度の上限」と記載する）を算出する。例えば、部分類似度算出部１３０がある入力ベクトルと他の入力ベクトルとの部分類似度をｄ＝１０において算出した場合、限界算出部１４０は、当該入力ベクトルと当該登録ベクトルとの類似度（すなわちｄ＝Ｄ＝１００で算出された類似度）に見込まれる上限を算出する。
【００３１】
閾値決定部１５０は、ある登録ベクトルが検索結果として選ばれるために、当該登録ベクトルの類似度に最低限求められる高さを決定する。言い換えると、閾値決定部１５０は、ある登録ベクトルが、類似度の高い上位Ｋ個の登録ベクトルとして選ばれるために、当該登録ベクトルの類似度に最低限求められる高さを決定する。以下、閾値決定部１５０が決定した類似度の高さを閾値と表現する。閾値決定部１５０の具体的な処理は後述する具体例毎に様々であるので、閾値決定部１５０の詳細は後述する。
【００３２】
棄却判定部１６０は、限界算出部１４０が算出した類似度の上限と、閾値決定部１５０が決定した閾値とを比較する。類似度の上限が閾値よりも低い場合には、当該類似度の上限に対応する登録ベクトルは、検索結果として選ばれる可能性がない。従って棄却判定部１６０は、当該類似度に対応する登録パターンを、検索結果の候補から棄却する。
【００３３】
（動作の概要の説明）
第１の実施形態にかかる検索システム１００の動作の概要を、図２に示すフローチャートを用いて説明する。
【００３４】
特徴抽出部１１０は、入力パターンから入力ベクトルを抽出する（ステップＳ１０１）。部分類似度算出部１３０は、入力ベクトルを登録ベクトルとの部分類似度をｄ＝ｄ０において算出する（ステップＳ１０２）。限界算出部１４０は、算出された部分類似度に基づいて、類似度の上限を算出する（ステップＳ１０３）。閾値決定部１５０は、ある登録ベクトルが検索結果として選ばれるために、当該登録ベクトルの類似度に最低限求められる高さを、閾値として決定する（ステップＳ１０４）。棄却判定部１６０は、限界算出部１４０が算出した類似度の上限と、閾値決定部１５０が決定した閾値とを比較する。類似度の上限が閾値よりも低い場合には、棄却判定部１６０は、当該類似度に対応する登録パターンを、検索結果の候補から棄却する（ステップＳ１０５）。
【００３５】
次に、部分類似度算出部１３０は、変数ｄの値を初期値ｄ０からより大きな値であるd1に更新する。ここで、１＜ｄ０＜d1＜＝Ｄである。記号「＜＝」は小なりイコールを表す。そして部分類似度算出部１３０、限界算出部１４０、閾値決定部１５０および棄却判定部１６０は、ステップＳ１０２からステップＳ１０５に示した処理を繰り返す。
【００３６】
すなわち、部分類似度算出部１３０は、棄却判定部１６０により棄却されなかった登録パターンについて、ｄ＝d1において部分類似度を再度算出する。そして、限界算出部１４０、閾値決定部１５０および棄却判定部１６０は、再度算出された部分類似度に対して上述した処理を改めて実行する。
【００３７】
検索システム１００は、変数ｄの値が更新されてｄ＝Ｄとなるまで上記の処理を繰り返す。すなわち、部分類似度算出部１３０がｄ＝Ｄにおいて部分類似度を算出し、棄却判定部１６０が判定を行うまで上記の処理を繰り返す。なお、ｄ＝Ｄにおいて算出される部分類似度はすなわち類似度そのものである。検索システム１００は、最後まで棄却されなかった登録ベクトルＫ個を、検索結果として出力する（ステップＳ１０６）。検索システム１００は、最後まで棄却されなかった登録ベクトルに対応する登録パターンＫ個を出力してもよい。
【００３８】
図３および図４は、本実施形態の概要を説明する図である。図３および図４において、横軸は、部分類似度が算出される際の次元数ｄを示す。縦軸は、類似度Ｓの高さを示す。
【００３９】
図３および図４において実線で示される曲線は、ある登録ベクトルが検索結果として選ばれるために、当該登録ベクトルの類似度に最低限求められる高さを示す。すなわち、実線で示される曲線の高さは、部分類似度算出部１３０が次元数ｄにおいて部分類似度を算出した場合における、閾値決定部１５０が決定する閾値の高さを示す。図３と図４とで、実線で示される曲線は共通している。
【００４０】
図３および図４において点線で示される曲線は、ある登録ベクトルに対して、次元数ｄにおいて部分類似度が算出された場合に見込まれる類似度の上限を示す。
【００４１】
図３および図４において一点鎖線で示される曲線は、ある登録ベクトルに対して、次元数ｄにおいて部分類似度が算出された場合に見込まれる類似度の下限を示す。
【００４２】
図３および図４に示すように、次元数ｄが大きくなるにつれて、類似度の上限は低く、類似度の下限は高くなっていく。ｄ＝Ｄにおいて、類似度の上限および類似度の下限は、全次元を用いて算出された類似度の高さと同じ高さに収束する。以下、全次元を用いて算出された類似度を、部分類似度と区別する目的で「最終的な類似度」と表現する場合がある。
【００４３】
図３は、登録ベクトルの一つの具体例である「登録ベクトル１」が、棄却判定部１６０によって棄却される様子を示す図である。図３には、「登録ベクトル１」に対して算出された、類似度の上限（点線）および下限（一点鎖線）が示されている。図３において、登録ベクトル１の類似度に見込まれる上限は、ｄ＝rにおいて、検索結果に選ばれるために最低限必要となる当該登録ベクトルの類似度を下回っている。ｄ＝rにおいて部分類似度が算出された段階で、登録ベクトル１が最終的に検索結果に選ばれる可能性はないと判定できる。よって、登録ベクトル１についてｄ＝rよりも大きい次元で部分類似度を算出しても有効でないため、棄却判定部１６０は登録ベクトル１を検索結果の候補から棄却する。
【００４４】
図４は、登録ベクトルの一つの具体例である「登録ベクトル２」が棄却判定部１６０によって棄却されない様子を示す図である。図４には、「登録ベクトル２」に対して算出された、類似度の上限（点線）および下限（一点鎖線）が示されている。図４において、登録ベクトル２の類似度に見込まれる上限は、ｄの値によらず、検索結果に選ばれるために最低限必要となる当該登録ベクトルの類似度を下回らない。従って、ｄ＝Ｄにおいて類似度を算出してみないと、登録ベクトル２が最終的に検索結果に選ばれるか否かはわからない。棄却判定部１６０は登録ベクトル２を棄却することはせずに、部分類似度算出部１３０はｄ＝Ｄにおいて入力ベクトルと登録ベクトル２との類似度を算出する。
【００４５】
（第１の実施形態の効果）
このように、第１の実施形態にかかる検索システム１００は、検索結果として選ばれる可能性がない登録ベクトルのみを、検索結果の候補から棄却することができる。従って検索システム１００が実行する検索方法によれば、入力パターンと登録パターンとの類似度の算出を単純に繰り返す検索方法と比較して、Ｋ近傍正解率が劣化しない。
【００４６】
また、第１の実施形態にかかる検索システム１００は、検索結果として選ばれる可能性がないと判定された登録ベクトルについては、それ以上類似度の算出処理を行わない。言い換えると、検索結果として選ばれる可能性がない登録ベクトルについては、検索システム１００は、一部の次元について部分類似度を算出する処理は実行するが、それ以上、全次元について類似度を算出する処理は実行しない。一部の次元について部分類似度を算出する処理は、全次元について類似度を算出する処理よりも、当然に計算量が少ない。従って、検索システム１００が実行する検索方法によれば、入力パターンと登録パターンとの類似度の算出を単純に繰り返す検索方法と比較して、計算量を削減することができる。これにより、検索システム１００が実行する検索方法は、高速に実行可能である。
【００４７】
また、以下に示すように、第１の実施形態にかかる検索システム１００は、様々な方法により定義された類似度に対して適用可能である。
【００４８】
さらに、検索システム１００においては、Ｋの値はオペレータが直接指定することが可能である。一般に近似最近傍探索またはカスケードを用いた高速化では、未知の入力データに対して所望の検索精度を得るためのパラメータ調整が非常に困難である。検索システム１００においては、保証すべきＫ近傍正解率からＫの値を直接指定できるという利点がある。
【００４９】
（ハードウェア構成の一例の説明）
図５は、第１の実施形態にかかる検索システム１００を実現可能なハードウェア構成の一例を説明する図である。検索システム１００（コンピュータ）を構成するハードウェアは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１、メモリ２、記憶装置３、通信インターフェース（Ｉ／Ｆ）４を備える。検索システム１００は、入力装置５または出力装置６を備えていてもよい。検索システム１００の機能は、例えばＣＰＵ１が、メモリ２に読み出されたコンピュータプログラム（ソフトウェアプログラム、以下単に「プログラム」と記載する）を実行することにより実現される。実行に際して、ＣＰＵ１は、通信インターフェース４、入力装置５および出力装置６を適宜制御する。
【００５０】
なお、本実施形態および後述する各実施形態を例として説明される本発明は、かかるプログラムが格納されたコンパクトディスク等の不揮発性の記憶媒体８によって構成されてもよい。記憶媒体８が格納するプログラムは、例えばドライブ装置７により読み出される。
【００５１】
検索システム１００が実行する通信は、例えばＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）が提供する機能を使ってアプリケーションプログラムが通信インターフェース４を制御することによって実現される。
【００５２】
検索システム１００は、２つ以上の物理的に分離した装置が有線または無線で接続されることによって構成されていてもよい。
【００５３】
図５に示すハードウェア構成例は、後述する各実施形態および各具体例にも適用可能である。なお、検索システム１００は専用の装置であってもよい。なお、検索システム１００およびその各機能ブロックのハードウェア構成は、上述の構成に限定されない。
【００５４】
（具体例）
次に、第１の実施形態にかかる検索システム１００のより具体的な態様を、下記に示す具体例１ないし具体例５を用いて説明する。下記の具体例において説明する具体例は、検索システム１００の態様における具体例であり、検索システム１００を限定的に解釈するためのものではない。
【００５５】
（具体例１）
具体例１にかかる検索システム１００の詳細を、図１を用いて説明する。具体例１では、類似度として内積を用いる。また、具体例１では、登録パターン記憶部１２０に記憶されているＮ個の登録パターンが並列に処理される。
【００５６】
検索システム１００はＫ近傍検索を実行する。
【００５７】
特徴抽出部１１０は入力パターンから入力ベクトルを抽出する。
【００５８】
登録パターン記憶部１２０はＮ個の登録パターンを記憶している。
【００５９】
部分類似度算出部１３０は、特徴抽出部１１０が抽出した入力ベクトルと、登録パターン記憶部１２０に記憶されている登録ベクトルとの部分類似度を算出する。部分類似度算出部１３０は、Ｎ個の登録ベクトルに対してそれぞれ部分類似度を算出する。従って、部分類似度算出部１３０は、Ｎ個の部分類似度を算出することになる。
【００６０】
限界算出部１４０は、部分類似度算出部１３０が算出したそれぞれの部分類似度に基づいて、Ｎ個の登録ベクトルに対してそれぞれ類似度の上限および類似度の下限を算出する。従って、限界算出部１４０は、類似度の上限をＮ個と、類似度の下限をＮ個、算出することになる。
【００６１】
閾値決定部１５０は、限界算出部１４０が算出したＮ個の「類似度の下限」をソートする。閾値決定部１５０は、ソートされたＮ個の「類似度の下限」のうちＫ番目に高い「類似度の下限」の高さを、閾値として決定する。この閾値は、ある登録ベクトルが検索結果として選ばれるために、当該登録ベクトルの類似度に最低限求められる高さである。なぜなら、ｄの値が段階的に増加されてｄ＝Ｄとなった段階において（以下、この段階を「最終的」と表現する）、類似度がこの閾値よりも高くなる登録パターンがＫ個必ず存在するためである。
【００６２】
棄却判定部１６０は、限界算出部１４０が算出した類似度の上限と、閾値決定部１５０が決定した閾値とを比較する。類似度の上限が閾値よりも低い場合には、棄却判定部１６０は、当該類似度に対応する登録パターンを、検索結果の候補から棄却する。
【００６３】
本具体例では、入力ベクトルをｘ、登録ベクトルをｙと表記する。登録パターン記憶部１２０は登録ベクトルをＮ個記憶しているので、それぞれの登録ベクトルをｙｎ（ｎ＝１，・・・，Ｎ）という記号で識別する。本具体例では、次元数Ｄである入力ベクトルをｘ ＝ { ｘ（i) } （ i ＝ １，・・・，Ｄ ）と表記する。同様に、本具体例では、次元数Ｄである登録ベクトルをｙｎ ＝ { yn（i) } （ i ＝ １，・・・，Ｄ ）と表記する。
【００６４】
次元数Ｄである入力ベクトルおよび登録ベクトルについて、一部の次元ｄに関する部分類似度Ｓｄ（x，yn）は、以下のように計算できる。ここで、＜数式１＞において、記号「・」は積を表す。以下、本願において同様である。
【００６５】
＜数式１＞
0006589639.tif 000002
【００６６】
棄却判定部１６０によって棄却されなかった登録ベクトルについては、部分類似度算出部１３０がｄ＝ｄ’（ただしｄ’＞ｄ）において再度部分類似度を算出する。この場合の部分類似度Ｓｄ（x，yn）は下記の式により逐次的に算出される。
【００６７】
＜数式２＞
0006589639.tif 000003
【００６８】
限界算出部１４０は、部分類似度算出部１３０が算出した部分類似度に基づいて、類似度の上限および類似度の下限を算出する。Ｄ次元のベクトルｘ， ｙ間の内積は、一般的に以下のような上限と下限を持つ。ここで、ｘＴは、ベクトルｘの転置を表す。
【００６９】
＜数式３＞
0006589639.tif 000004
【００７０】
従って、限界算出部１４０は、部分類似度に基づいて、Ｄ次元における類似度ＳＤ（x，y）の上限および下限を以下のように算出することができる。
【００７１】
＜数式４＞
0006589639.tif 000005
【００７２】
次に、具体例１にかかる検索システム１００の動作を、図６に示すフローチャートを用いて説明する。図６に示すフローチャートにおいては複数の処理が順番に説明されているが、その複数の処理の順番は支障のない範囲で変更することができる。
【００７３】
特徴抽出部１１０は、入力パターンから入力ベクトルを抽出する（ステップＳ２０１）。部分類似度算出部１３０は、変数ｄに初期値ｄ０を設定する（ステップＳ２０２）。
【００７４】
部分類似度算出部１３０は、棄却されていない全ての登録ベクトルに対してステップＳ２０４ないしステップＳ２０５に記載の処理を繰り返す（ステップＳ２０３）。この段階ではまだいずれの登録ベクトルも棄却されていないので、部分類似度算出部１３０は、登録パターン記憶部１２０に記憶されているＮ個の登録ベクトルに対して、処理を繰り返すことになる。
【００７５】
部分類似度算出部１３０は、入力ベクトルと登録ベクトルとの部分類似度を算出する（ステップＳ２０４）。限界算出部１４０は、部分類似度に基づいて、類似度の上限および類似度の下限を算出する（ステップＳ２０５）。
【００７６】
部分類似度算出部１３０が、登録パターン記憶部１２０に記憶されているＮ個の登録ベクトルに対してステップＳ２０４ないしステップＳ２０５に記載の処理を実行する。すると、限界算出部１４０が、Ｎ個の登録ベクトルのそれぞれに対して、部分類似度、類似度の上限および類似度の下限を算出した状態となる（ステップＳ２０６）。
【００７７】
閾値決定部１５０は、限界算出部１４０が算出したＮ個の「類似度の下限」をソートする。閾値決定部１５０は、ソートされたＮ個の「類似度の下限」のうちＫ番目に高い「類似度の下限」の高さを、閾値として決定する（ステップＳ２０７）。
【００７８】
棄却判定部１６０は、棄却されていない全ての登録ベクトルに対して、ステップＳ２０９ないしステップＳ２１０に記載の処理を繰り返す（ステップＳ２０８）。この段階ではまだいずれの登録ベクトルも棄却されていないので、部分類似度算出部１３０は、登録パターン記憶部１２０に記憶されているＮ個の登録ベクトルに対して、Ｓ２０９ないしステップＳ２１０に記載の処理を繰り返すことになる。
【００７９】
棄却判定部１６０は、限界算出部１４０が算出した類似度の上限と、閾値決定部１５０が決定した閾値とを比較する（ステップＳ２０９）。類似度の上限が閾値よりも低い場合には（ステップＳ２０９においてＹＥＳ）、棄却判定部１６０は、当該類似度に対応する登録パターンを、検索結果の候補から棄却する（ステップＳ２１０）。類似度の上限が閾値よりも低くない場合には（ステップＳ２０９においてＮＯ）棄却判定部１６０は、当該類似度に対応する登録パターンを、検索結果の候補から棄却しない。
【００８０】
棄却判定部１６０は、棄却されていない全ての登録ベクトルに対して、ステップＳ２０９ないしステップＳ２１０に記載の処理を繰り返す（ステップＳ２１１）。この結果、検索結果の候補である登録ベクトルの個数はＮ個からＮ’個になる（Ｎ’＜＝Ｎ）。
【００８１】
変数ｄの値がＤである場合（ステップＳ２１２においてＹＥＳ）、検索システム１００は、棄却されなかったＫ個の登録ベクトルを検索結果として出力する（ステップＳ２１３）。変数ｄの値がＤでない場合（ステップＳ２１２においてＮＯ）、部分類似度算出部１３０はｄの値を増やす。そして、部分類似度算出部１３０、限界算出部１４０、閾値決定部１５０および棄却判定部１６０は、棄却されなかったＮ’個の登録パターンについて、ステップＳ２０３からステップＳ２１１までの処理を繰り返す。以上、具体例１にかかる検索システム１００の動作を説明した。
【００８２】
ここで、入力パターンと登録パターンとの類似度の算出を単純に繰り返す検索方法と、検索システム１００が実行する検索方法とを比較して、検索システム１００が実行する検索方法が高速である理由を詳細に説明する。
【００８３】
例えば、入力ベクトルおよび登録ベクトルが１００次元の特徴ベクトルである場合を想定する（Ｄ＝１００）。また、理解を容易にするため、計算量は掛け算の回数に比例すると考える。もし、普通に内積を計算して類似度を算出する場合、全ての次元において掛け算が行われるため、１００回の掛け算が行われる。一方、本具体例において、例えば１０次元まで内積を計算し（ｄ＝１０）、棄却判定が行われたとする。１０次元までの内積計算の計算量は掛け算１０回分であり、上限の計算量と下限の計算量とはそれぞれ掛け算1回分であるため、もし１０次元で棄却が行われれば、掛け算１１回分の計算量で済む。多くの登録ベクトルは低次元における部分類似度が算出された段階で棄却されるため、結果的に計算量が削減され、検索処理が高速化される。
【００８４】
なお、部分類似度算出部１３０は、上限および下限の算出に用いられる残りの次元のノルム＜数式５＞を、例えば下記に示すような方法により高速に算出することができる。検索システム１００は、各ベクトルの各次元（要素）の値の二乗値、すなわちx(i)2またはy(i)2の値を、パターンから特徴量を抽出する際に前もって算出しておくことができる。部分類似度算出部１３０は、前もって算出されたこれらの値を読み出して、残りの次元のノルムを算出する際に用いてもよい。また、ｄの初期値であるｄ０の値が検索システム１００にあらかじめ与えられていれば、検索システム１００は、バックグラウンド処理としてあらかじめ残りの次元のノルムを算出して記憶していてもよい。部分類似度算出部１３０は、検索が行われる際に、あらかじめ算出された残りの次元のノルムの値を読み出して用いてもよい。このように、部分類似度算出部１３０は、上限および下限を高速に算出することができる。
【００８５】
＜数式５＞
0006589639.tif 000006
【００８６】
（具体例２）
具体例２にかかる検索システム１００の詳細を、図７を用いて説明する。具体例２では、類似度として内積を用いる。また、具体例２では、登録パターン記憶部１２０に記憶されているＮ個の登録パターンが逐次的に処理される。
【００８７】
図７は、具体例２にかかる検索システム１００の構成を示すブロック図である。図７に示すように、具体例２においては、検索システム１００は候補記憶部１７０を備える。
【００８８】
候補記憶部１７０は、少なくともＫ個の最終的な類似度（すなわちｄ＝Ｄにおいて算出された類似度）の高さ（または大きさ）を記憶している。すなわち、候補記憶部１７０は、少なくともＫ個以上の登録ベクトルに対してそれぞれ算出された、少なくともＫ個以上の類似度のうち、最も高い類似度からＫ番目に高い類似度までのＫ個の類似度を記憶している。候補記憶部１７０が記憶する類似度よりも高い類似度が算出された場合、候補記憶部１７０が記憶する類似度は更新される。
【００８９】
次に、具体例２にかかる検索システム１００の動作を、図８に示すフローチャートを用いて説明する。図８に示すフローチャートにおいては複数の処理を順番に説明しているが、その複数の処理の順番は支障のない範囲で変更することができる。
【００９０】
特徴抽出部１１０は、入力パターンから入力ベクトルを抽出する（ステップＳ３０１）。部分類似度算出部１３０は、変数ｄに初期値ｄ０を設定する（ステップＳ３０２）。
【００９１】
部分類似度算出部１３０は、登録パターン記憶部１２０に記憶されているＮ個の登録ベクトルに対してステップＳ３０４からステップＳ３１３までの処理を繰り返す（ステップＳ３０３）。
【００９２】
閾値決定部１５０は、候補記憶部１７０が記憶しているＫ個の類似度のうち、Ｋ番目に高い類似度の高さを閾値として決定する（ステップＳ３０４）。この閾値は、ある登録ベクトルが検索結果として選ばれるために、当該登録ベクトルの類似度に最低限求められる高さである。なぜなら、ｄの値が段階的に増加されてｄ＝Ｄとなった段階において、類似度がこの閾値よりも高くなる登録パターンがＫ個必ず存在するためである。
【００９３】
部分類似度算出部１３０は、入力ベクトルと登録ベクトルとの部分類似度を算出する（ステップＳ３０５）。限界算出部１４０は、部分類似度に基づいて、類似度の上限および類似度の下限を算出する。または、限界算出部１４０は、部分類似度に基づいて、類似度の上限だけを算出してもよい（ステップＳ３０６）。棄却判定部１６０は、限界算出部１４０が算出した類似度の上限と、閾値決定部１５０が決定した閾値とを比較する（ステップＳ３０７）。
【００９４】
類似度の上限が閾値よりも低い場合には（ステップＳ３０７においてＹＥＳ）、棄却判定部１６０は、当該類似度に対応する登録パターンを、検索結果の候補から棄却する（ステップＳ３１２）。検索システム１００は、当該棄却された登録ベクトルについての処理を終了し、登録パターン記憶部１２０に記憶されている次の登録ベクトルについての処理を開始する。
【００９５】
類似度の上限が閾値よりも低くない場合には（ステップＳ３０７においてＮＯ）、棄却判定部１６０は、当該類似度に対応する登録パターンを、検索結果の候補から棄却せずに、ステップＳ３０８に示す処理に進む。
【００９６】
変数ｄの値がＤよりも小さい場合（ステップＳ３０８においてＮＯ）、部分類似度算出部１３０は、変数ｄの値を増やして（ステップＳ３１３）、当該登録ベクトルに対してステップＳ３０５からステップＳ３０８までに示す処理を繰り返す。
【００９７】
変数ｄの値がＤである場合（ステップＳ３０８においてＹＥＳ）、検索システム１００はステップＳ３０９に示す処理に進む。
【００９８】
ｄ＝Ｄにおいて算出された類似度の高さが、候補記憶部１７０に記録されているＫ個の登録ベクトルのうちいずれかの登録ベクトルの類似度の高さを超える場合（ステップＳ３０９においてＹＥＳ）、棄却判定部１６０は、候補記憶部１７０が記憶する内容を更新する（ステップＳ３１０）。
【００９９】
ｄ＝Ｄにおいて算出された類似度の高さが、候補記憶部１７０に記録されているＫ個の登録ベクトルのうちいずれかの登録ベクトルの類似度の高さを超えていない場合（ステップＳ３０９においてＮＯ）、棄却判定部１６０は、当該登録ベクトルを破棄する（ステップＳ３１１）。
【０１００】
部分類似度算出部１３０、限界算出部１４０、閾値決定部１５０および棄却判定部１６０は、登録パターン記憶部１２０が記憶するＮ個の登録ベクトルに対してそれぞれ、ステップＳ３０３からステップＳ３１１に示す処理を繰り返す（ステップＳ３１４）。
【０１０１】
検索システム１００は、候補記憶部１７０に記憶されているＫ個の登録ベクトルを検索結果として出力する（ステップＳ３１５）。以上、具体例２にかかる検索システム１００の動作を説明した。
【０１０２】
（具体例３）
具体例１は、内積の性質に基づいて数学的に厳密な上限と下限とを用い、具体例２は、内積の性質に基づいて数学的に厳密な上限を用いた。本具体例ではこれを緩和し、より狭い範囲の上限と下限にすることで、検索速度を一層高速化することができる。ただし、この場合はＫ近傍正解率の非劣化の保証が近似的になるため、実際にはＫ近傍正解率が若干低下する。本具体例は、後述する他の具体例にも適用可能である。
【０１０３】
下記に示す数式６は、緩和された上限および下限を示す。
【０１０４】
＜数式６＞
0006589639.tif 000007
【０１０５】
ここで、αとβは０以上１以下の定数である。αとβがともに１の場合が具体例１または具体例２に相当する。本具体例では、αまたはβとして０以上１未満の値を設定することで、より狭い範囲の上限と下限を得る。範囲が狭いほど高速化の効果が大きくなるが、Ｋ近傍正解率は悪化する。αとβは事前に決定してもよいし、登録パターンによって適応的に変化させてもよい。例えば、残りの次元は最悪でも無相関と仮定するならば、α＝０となる。また、残りの次元の相関は最高でも計算済みの次元と同等程度の相関であると仮定するならば、係数の値を下記に示す数式７のように登録パターンによって適応的に決めることができる。
【０１０６】
＜数式７＞
0006589639.tif 000008
【０１０７】
また、類似度の上限および下限は、例えば下記に示す数式８のような方法で緩和されてもよい。
【０１０８】
＜数式８＞
0006589639.tif 000009
【０１０９】
（具体例４）
具体例１および具体例２では類似度として内積を用いる例を示したが、本具体例では類似度としてユークリッド距離の2乗を用いる例を示す。なお、距離を用いる場合と距離の2乗を用いる場合では類似度の大小関係が保存されるため、本具体例では距離の2乗を用いる場合を示す。一般に、ベクトルｘ、ｙ間のユークリッド距離の2乗は以下のように3つの内積に分解できる。
【０１１０】
＜数式９＞
0006589639.tif 000010
【０１１１】
ここで、右辺の第1項と第2項は特徴ベクトルを抽出する際に計算しておくことができる。従って、類似度を算出する際に計算するのは第3項のみでよい。ここで、数式１、数式４、数式９を用いると、ユークリッド距離の上限と下限は以下のように求めることができる。
【０１１２】
＜数式１０＞
0006589639.tif 000011
【０１１３】
従って、類似度としてユークリッド距離の2乗を用いる場合は、上式で示した上限・下限が用いられればよい。このように、類似度が内積ではない場合でも、内積計算に基づく類似度であれば、検索システム１００による検索方法を適用することができる。
【０１１４】
（具体例５）
具体例１および具体例２では類似度として内積を用いる例を示したが、本具体例では正規化相関を用いる例を示す。一般に、ベクトルｘ、ｙ間の正規化相関は以下のように書ける。
【０１１５】
＜数式１１＞
0006589639.tif 000012
【０１１６】
従って、特徴を抽出する際に特徴ベクトルのノルムを正規化しておくことで、類似度の算出は内積計算のみとなる。これにより、具体例１および具体例２と同様の方法で本発明を実施できる。このように、類似度が内積ではない場合でも、内積計算に基づく類似度であれば、検索システム１００による検索方法を適用することができる。以上、具体例５について説明した。
【０１１７】
（具体例６）
図９は、具体例６にかかる検索システム１００Ａの構成を示すブロック図である。検索システム１００Ａは、あるベクトルと他のベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の登録ベクトルから入力ベクトルに類似する登録ベクトルを検索する検索システムである。検索システム１００Ａは、部分類似度算出部１３０Ａと、限界算出部１４０Ａと、棄却判定部１６０Ａと、を備える。
【０１１８】
部分類似度算出部１３０Ａは、入力ベクトルおよび登録ベクトルの１以上の次元のうち一部の次元に関する類似度である部分類似度を算出する。
【０１１９】
限界算出部１４０Ａは、類似度を算出した場合に見込まれる当該類似度の上限を、部分類似度に基づいて算出する。
【０１２０】
棄却判定部１６０Ａは、類似度の上限に基づいて、前記類似度の上限に対応する前記登録ベクトルを棄却するか否かを判定する。
【０１２１】
＜第２の実施形態＞
図１０は、第２の実施形態にかかる検索システム２００Ｂの構成を示すブロック図である。検索システム１００Ｂは、複数の登録画像から、入力画像と類似する登録画像を検索する検索システムである。図１０に示すように、検索システム２００Ｂは、第１の受付部２１０Ｂと、第２の受付部２２０Ｂと、検索部２３０Ｂと、出力部２４０Ｂと、を備える。
【０１２２】
第１の受付部２１０Ｂは、入力画像を受け付ける。
【０１２３】
第２の受付部２２０Ｂは、自然数Ｋの入力を受け付ける。
【０１２４】
検索部２３０Ｂは、複数の登録画像から、入力画像と最も類似する登録画像ないしＫ番目に類似する登録画像のＫ個の登録画像を検索する。検索部２３０Ｂは、上述した具体例１ないし具体例５に示すいずれかの検索方法を実行する。
【０１２５】
出力部２４０Ｂは、検索の結果得られたＫ個の登録画像を出力する。
【０１２６】
すなわち、検索システム２００Ｂは、入力された検索条件として与えられた画像と類似度の高い画像をＫ個、データベース中から検索し、類似度の高い順番に、ユーザに対して当該Ｋ個の画像を提示する。
【０１２７】
上述した各実施の形態および具体例は、適宜組み合わせて実施されることが可能である。
【０１２８】
各ブロック図に示したブロック分けは、説明の便宜上から表された構成である。各実施形態を例に説明された本発明は、その実装に際して、各ブロック図に示した構成には限定されない。
【０１２９】
また、上述した図面参照符号は、理解を助けるための一例として各要素に便宜上付記したものであり、本発明を図示の態様に限定することを意図するものではない。
【０１３０】
以上、本発明を実施するための形態について説明したが、上記実施の形態は本発明の理解を容易にするためのものであり、本発明を限定して解釈するためのものではない。本発明はその趣旨を逸脱することなく変更、改良され得るとともに、本発明にはその等価物も含まれる。
【０１３１】
以下、参考形態の例を付記する。
【０１３２】
（付記１）
入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の登録ベクトルから入力ベクトルに類似する登録ベクトルを検索する検索システムにおいて、
前記入力ベクトルおよび前記登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出する部分類似度算出手段と、
前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度に基づいて算出する限界算出手段と、
前記類似度の上限に基づいて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する棄却判定手段と、
を備える検索システム。
【０１３３】
（付記２）
前記棄却判定手段は、前記類似度の上限と、当該登録ベクトルが検索結果として選ばれるために当該登録ベクトルの類似度に最低限求められる高さと、を比較することにより、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する、
付記１に記載の検索システム。
【０１３４】
（付記３）
複数の前記登録ベクトルから、前記入力ベクトルに最も類似する登録ベクトルないしＫ番目に類似する登録ベクトルの、Ｋ個の登録ベクトルを検索するに際して、
前記部分類似度算出手段は、少なくともＫ個以上の前記登録ベクトルに対してそれぞれ部分類似度を算出し、
前記限界算出手段は、少なくともＫ個以上の前記部分類似度に対してそれぞれ前記類似度の上限および前記類似度の下限を算出し、
前記棄却判定手段は、少なくともＫ個以上の前記類似度の下限のうちＫ番目に高い前記類似度の下限と、前記類似度の上限との比較の結果に応じて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する、
付記１に記載の検索システム。
【０１３５】
（付記４）
複数の前記登録ベクトルから、前記入力ベクトルに最も類似する登録ベクトルないしＫ番目に類似する登録ベクトルの、Ｋ個の登録ベクトルを検索するに際して、
少なくともＫ個以上の前記登録ベクトルに対してそれぞれ算出された少なくともＫ個以上の前記類似度のうち、最も高い類似度からＫ番目に高い類似度までのＫ個の類似度の値を記憶している候補記憶手段を更に備え、
前記棄却判定手段は、前記候補記憶手段が記憶している類似度のうちＫ番目に高い類似度の値と、前記類似度の上限との比較の結果に応じて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する、
付記１に記載の検索システム。
【０１３６】
（付記５）
前記限界算出手段は、前記類似度を算出した場合に見込まれる当該類似度の上限または当該類似度の下限を、
前記部分類似度と、
前記複数の次元のうち残りの次元に関するノルムに０以上１以下の係数を乗じた値と、
に基づいて算出する、
付記３または４のいずれかに記載の検索システム。
【０１３７】
（付記６）
前記係数の値は、前記複数の次元のうち一部の次元に関する、前記入力ベクトルと前記登録ベクトルとの相関に基づいて決定される、付記５に記載の検索システム。
【０１３８】
（付記７）
前記類似度は前記入力ベクトルおよび前記登録ベクトルの全ての次元を用いて算出される値であり、
前記限界算出手段は、前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度と、前記複数の次元のうち残りの次元に関するノルムと、に基づいて算出し、前記限界算出手段は、検索処理実行時にあらかじめ算出されている値である、ベクトルの各次元の値の二乗値を読み出し、当該読み出した値を用いて前記残りの次元に関するノルムの値を算出する、
付記１ないし６のいずれかに記載の検索システム。
【０１３９】
（付記８）
前記類似度は、前記入力ベクトルと前記登録ベクトルとの、内積、ユークリッド距離または正規化相関である、付記１から７のいずれかに記載の検索システム。
【０１４０】
（付記９）
入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の登録ベクトルから入力ベクトルに類似する登録ベクトルを検索するコンピュータが、
前記入力ベクトルおよび前記登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出し、
前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度に基づいて算出し、
前記類似度の上限に基づいて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する、検索方法。
【０１４１】
（付記１０）
入力ベクトルと登録ベクトルとの類似の度合いを示す指標である類似度に基づいて、複数の登録ベクトルから入力ベクトルに類似する登録ベクトルを検索するコンピュータに、
前記入力ベクトルおよび前記登録ベクトルの１以上の次元のうち、一部の次元に関する前記類似度である部分類似度を算出する処理と、
前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度に基づいて算出する処理と、
前記類似度の上限に基づいて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する処理と、
を実行させるプログラム。
【０１４２】
（付記１１）
前記部分類似度算出部は、前記複数の登録ベクトルのうち、前記棄却判定部により棄却されていない登録ベクトルについて、前記一部の次元より大きく前記全ての次元以下の次元に関する前記部分類似度を改めて算出する、付記７に記載の検索システム。
【０１４３】
（付記１２）
前記棄却判定手段は、前記類似度の上限に０以上１以下の係数を乗じた値に基づいて、当該登録ベクトルを検索結果の候補から棄却するか否かを判定する、
付記１ないし８のいずれかに記載の検索システム。
【０１４４】
（付記１３）
前記類似度は前記入力ベクトルおよび前記登録ベクトルの全ての次元を用いて算出される値であり、
前記限界算出手段は、前記類似度を算出した場合に見込まれる当該類似度の上限を、前記部分類似度と、前記複数の次元のうち残りの次元に関するノルムと、に基づいて算出し、前記限界算出手段は、前記残りの次元に関するノルムの値を、検索処理実行時にあらかじめ算出されている値を読み出すことにより取得する、
付記１ないし６のいずれかに記載の検索システム。
【０１４５】
（付記１４）
複数の登録画像から、入力画像と類似する登録画像を検索する画像検索システムであって、
入力画像を受け付ける第１の受付手段と、
自然数Ｋの入力を受け付ける第２の受付手段と、
複数の前記登録画像から、入力画像と最も類似する登録画像ないしＫ番目に類似する登録画像のＫ個の登録画像を検索する検索手段と、
前記Ｋ個の登録画像を出力する出力手段と、
を備える画像検索システム。
【０１４６】
（付記１５）
複数の登録画像から、入力画像と類似する登録画像を検索するコンピュータが、
入力画像を受け付け、
自然数Ｋの入力を受け付け、
複数の前記登録画像から、入力画像と最も類似する登録画像ないしＫ番目に類似する登録画像のＫ個の登録画像を検索し、
前記Ｋ個の登録画像を出力する、
画像検索方法。
【０１４７】
（付記１６）
複数の登録画像から、入力画像と類似する登録画像を検索するコンピュータに、
入力画像を受け付ける処理と、
自然数Ｋの入力を受け付ける処理と、
複数の前記登録画像から、入力画像と最も類似する登録画像ないしＫ番目に類似する登録画像のＫ個の登録画像を検索する処理と、
前記Ｋ個の登録画像を出力する処理と、
を実行させるプログラム。
【産業上の利用可能性】
【０１４８】
本発明は、画像処理または音声処理において、データベースに登録されたパターンから入力パターンに類似するパターンを抽出するといった用途に適用できる。【０１４９】
以上、上述した実施形態を模範的な例として本発明を説明した。しかしながら、本発明は、上述した実施形態には限定されない。即ち、本発明は、本発明のスコープ内において、当業者が理解し得る様々な態様を適用することができる。【０１５０】
この出願は、２０１４年２月１０日に出願された日本出願特願２０１４−０２３４０２を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１５１】
１  ＣＰＵ
２  メモリ
３  記憶装置
４  通信インターフェース
５  入力装置
６  出力装置
７  ドライブ装置
８  記憶媒体
１００  検索システム
１１０  特徴抽出部
１２０  登録パターン記憶部
１３０  部分類似度算出部
１４０  限界算出部
１５０  閾値決定部
１６０  棄却判定部
１７０  候補記憶部
１００Ａ  検索システム
１３０Ａ  部分類似度算出部
１４０Ａ  限界算出部
１６０Ａ  棄却判定部
２００Ｂ  検索システム
２１０Ｂ  第１の受付部
２２０Ｂ  第２の受付部
２３０Ｂ  検索部
２４０Ｂ  出力部
【図１】
0006589639.tif 000013
【図２】
0006589639.tif 000014
【図３】
0006589639.tif 000015
【図４】
0006589639.tif 000016
【図５】
0006589639.tif 000017
【図６】
0006589639.tif 000018
【図７】
0006589639.tif 000019
【図８】
0006589639.tif 000020
【図９】
0006589639.tif 000021
【図１０】
0006589639.tif 000022