(57)【要約】【課題】超球を用いて簡単に類似検索を実行すること。【解決手段】本実施例にかかる検索装置１００は、ｍ次元の特徴量空間と、ｍ次元よりも上位の次元の空間に存在する超球を通る直線との交点ｘ０および超球の北極から特徴量空間までの距離ｄを含むパラメータを基にして特徴量ベクトルを前記超球上に射影する場合に、超球上に射影される特徴量ベクトルの位置が、超球の所定の半球に集約されるパラメータを検索する処理を実行する。【選択図】図１
2015118639.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータが実行する検索方法であって、
データベースに記憶された第１次元の特徴量ベクトルを取得し、
特徴量空間と、前記特徴量空間の次元よりも１次元以上大きい空間に存在する球を通る直線との交点および前記球の所定点から前記特徴量空間までの距離を含むパラメータを基にして前記特徴量ベクトルを前記球の表面上に射影する場合に、前記球の表面上に射影される特徴量ベクトルの位置が、前記球の半球に集約されるパラメータを検索する
処理を実行することを特徴とする検索方法。
【請求項２】
前記検索する処理によって探索されたパラメータを用いて複数の特徴量ベクトルを前記球の表面上に射影し、射影した前記特徴量ベクトルの位置と前記球を分割する複数の超平面との関係から前記特徴量ベクトルのビット列を生成し、生成したビット列を基にして類似する特徴量ベクトルを特定する処理を判定する処理を更に実行することを特徴とする請求項１に記載の検索方法。
【請求項３】
前記検索する処理は、前記球の表面上に射影される特徴量ベクトルの位置が、前記球の南半球、東半球または西半球に集約される前記パラメータを検索することを特徴とする請求項１または２に記載の検索方法。
【請求項４】
前記検索する処理は、前記特徴量ベクトルの平均値と、前記特徴量ベクトルの分散共分散行列の固有値の最大値を基にして前記パラメータを検索することを特徴とする請求項１または２に記載の検索方法。
【請求項５】
前記検索する処理は、前記特徴量ベクトルの主成分分析結果を基にして、累積寄与率曲線を特定し、該累積寄与率曲線を基にして前記パラメータを検索することを特徴とする請求項１または２に記載の検索方法。
【請求項６】
前記検索する処理は、山登り法、マルコフ連鎖モンテカルロ法または群知能を基にして、パラメータを検索することを特徴とする請求項１または２に記載の検索方法。
【請求項７】
コンピュータに、
特徴量空間と、前記特徴量空間の次元よりも１次元以上大きい空間に存在する球を通る直線との交点および前記球の所定点から前記特徴量空間までの距離を含むパラメータを基にして前記特徴量ベクトルを前記球の表面上に射影する場合に、前記球の表面上に射影される特徴量ベクトルの位置が、前記球の半球に集約されるパラメータを検索する
処理を実行させることを特徴とする検索プログラム。
【請求項８】
データベースに記憶された第１次元の特徴量ベクトルを取得し、特徴量空間と、前記特徴量空間の次元よりも１次元以上大きい空間に存在する球を通る直線との交点および前記球の所定点から前記特徴量空間までの距離を含むパラメータを基にして前記特徴量ベクトルを前記球の表面上に射影する場合に、前記球の表面上に射影される特徴量ベクトルの位置が、前記球の半球に集約されるパラメータを検索する検索部
を有することを特徴とする検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索方法等に関する。
【背景技術】
【０００２】
例えば、各種のシステムで利用者を認証する場合には、利用者の生体情報を取得し、取得した生体情報と一致する生体情報が予め登録されたデータベースに存在するか否かを判定する処理を行う。ここで、認証時に取得する生体情報は、登録時に取得した生体情報と完全に一致することは少ないため、類似検索が有効である。
【０００３】
類似検索を行う場合の類似度合いの表現として、生体情報の特徴量をハッシュベクトルに変換する技術があり、ハッシュベクトルのハミング距離の近い各生体情報を、類似する生体情報として特定する。
【０００４】
従来技術では、超平面を用いて特徴量をハッシュベクトルに変換する処理を行っているが、超球を用いて特徴量をハッシュベクトルに変換する処理も存在し、超球を用いた方が精度の向上が見込まれる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１１−１００３９５号公報
【特許文献２】特開２０１２−１６００４７号公報
【特許文献３】特開２０１１−３９７５５号公報
【非特許文献】
【０００６】
【非特許文献１】Jae-Pil  Heo,  Youngwoon  Lee,  Junfeng  He,  Shih-Fu  Chang,  and  Sung-Eui  Yoon.  “Spherical  hashing”,  In  CVPR,  pp.  2957-2964,  2012.
【非特許文献２】Kengo  Terasawa  and  Yuzuru  Tanaka.  “Spherical  lsh  for  approximate  nearest  neighbor  search  on  unit  hyper-sphere”,  In  Frank  K.  H.  A.  Dehne,  Jorg-Rudiger  Sack,  and  Norbert  Zeh,  editors,  WADS,  Vol.  4619  of  Lecture  Notes  in  Computer  Sciene,  pp.  27-38.  Springer,  2007.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した従来技術では、超球を用いてハッシュベクトルを算出すると、計算量が大きくなるという問題がある。
【０００８】
また、超球を用いて特徴量ベクトルをハッシュベクトルに変換すると、ワームホールの影響により、大きく異なる特徴量ベクトル同士であっても、ハッシュベクトル変換後のハミング距離が小さくなる場合がある。このため、異なる特徴量ベクトル同士を、類似する特量ベクトルとして誤判定する場合がある。
【０００９】
１つの側面では、超球を用いて簡単に類似検索を実行することができる検索方法、検索プログラムおよび検索装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
第１の案では、コンピュータが下記の処理を実行する。コンピュータは、データベースに記憶された第１次元の特徴量ベクトルを取得する。コンピュータは、球の表面上に射影される特徴量ベクトルの位置が、前記球の半球に集約されるパラメータを検索する。ただし、パラメータは、特徴量空間と、特徴量空間の次元よりも１次元以上大きい空間に存在する球を通る直線との交点および球の所定点から特徴量空間までの距離を含む情報である。
【発明の効果】
【００１１】
本発明の１実施態様によれば、超球を用いて簡単に類似検索を実行することができるという効果を奏する。
【図面の簡単な説明】
【００１２】
【図１】図１は、本実施例１に係る検索装置の構成を示す機能ブロック図である。
【図２Ａ】図２Ａは、特徴量記憶部のデータ構造の一例を示す図である。
【図２Ｂ】図２Ｂは、ビット列記憶部のデータ構造の一例を示す図である。
【図３】図３は、特徴量空間Ｖと超球Ｓとの関係を示す図（１）である。
【図４】図４は、特徴量空間Ｖと超球Ｓとの関係を示す図（２）である。
【図５】図５は、本実施例１に係る検索装置の処理手順を示すフローチャートである。
【図６】図６は、本実施例１に係るパラメータ特定処理の処理手順を示すフローチャートである。
【図７】図７は、無限遠点のショートカットを説明するための図である。
【図８】図８は、特徴量ベクトルが超球の東半球に逆立体射影されるパラメータの一例を示す図である。
【図９】図９は、特徴量ベクトルが超球の西半球に逆立体射影されるパラメータの一例を示す図である。
【図１０】図１０は、本実施例２に係る検索装置の構成を示す機能ブロック図である。
【図１１】図１１は、近似直線の一例を示す図である。
【図１２】図１２は、本実施例２に係るパラメータ特定処理の処理手順を示すフローチャートである。
【図１３】図１３は、本実施例３に係る検索装置の構成を示す機能ブロック図である。
【図１４】図１４は、山登り探索を用いたパラメータ特定処理の処理手順を示すフローチャートである。
【図１５】図１５は、マルコフ連鎖モンテカルロ法を用いたパラメータ特定処理の処理手順を示すフローチャートである。
【図１６】図１６は、群知能を用いたパラメータ特定処理の処理手順を示すフローチャートである。
【図１７】図１７は、目的関数の処理手順の一例を示すフローチャートである。
【図１８】図１８は、検索プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１３】
以下に、本願の開示する検索方法、検索プログラムおよび検索装置の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００１４】
本実施例１に係る検索装置の構成の一例について説明する。図１は、本実施例１に係る検索装置の構成を示す機能ブロック図である。図１に示すように、この検索装置１００は、特徴量記憶部１０１、クエリ記憶部１０２、ビット列記憶部１０３、逆立体射影部１０４ａ，１０４ｂ、ビット列生成部１０５ａ，１０５ｂを有する。また、検索装置１００は、超平面配置部１０６、変換規則生成部１０７、パラメータ設定部１０８、ハミング距離計算部１０９、類似ベクトル特定部１１０を有する。
【００１５】
特徴量記憶部１０１は、複数の特徴量ベクトルを記憶する記憶部である。図２Ａは、特徴量記憶部のデータ構造の一例を示す図である。図２Ａに示すように、この特徴量記憶部１０１は、識別情報と、特徴量ベクトルとを対応付けて記憶する。識別情報は、特徴量ベクトルを一意に識別する情報である。特徴量ベクトルは、例えば、ユーザの生体情報から得られるｍ次元の特徴量のデータである。生体情報から特徴量ベクトルを求める手法は、如何なる従来技術を用いても良い。
【００１６】
クエリ記憶部１０２は、クエリとなる特徴量ベクトルを記憶する記憶部である。検索装置１００は、クエリとなる特徴量ベクトルに類似する特徴量ベクトルを、特徴量記憶部１０１から検索する。
【００１７】
ビット列記憶部１０３は、後述するビット列生成部１０５から取得するビット列を記憶する記憶部である。図２Ｂは、ビット列記憶部のデータ構造の一例を示す図である。図２Ｂに示すように、このビット列記憶部１０３は、識別情報と、ビット列とを対応付けて記憶する。識別情報は、ビット列の生成元となった特徴量ベクトルを一意に識別する情報である。ビット列は、特徴量ベクトルを基にして生成されるビット列である。
【００１８】
逆立体射影部１０４ａ，１０４ｂは、ｍ次元の特徴量空間Ｖに対して逆立体射影を行うことで、ｍ次元よりもｐ次元高い空間Ｖ’に埋め込まれた（ｍ＋ｐ−１）次元の超球Ｓと特徴量空間Ｖとを対応付ける処理部である。ｐは、１以上の整数である。以下の説明では、逆立体射影部１０４ａ，１０４ｂをまとめて適宜、逆立体射影部１０４と表記する。逆立体射影部１０４は、射影部の一例である。
【００１９】
図３および図４は、特徴量空間Ｖと超球Ｓとの関係を示す図である。図３に示すように、逆立体射影を行うと、特徴量空間Ｖ上の点と、超球Ｓ上の点とが対応付けられる。図３に示す例では、特徴量空間Ｖ上の点ｘＶと、超球Ｓ上の点ｘＳとが対応付けられる。超球Ｓの北極ＳＮと南極ＳＳを結ぶ直線と、特徴量空間Ｖとの交点をｘ０と定義する。例えば、北極ＳＮの座標は、（ｘｏ１，ｘｏ２，・・・，ｘｏｍ，１）となり、南極の座標は、（ｘｏ１，ｘｏ２，・・・，ｘｏｍ，−１）となる。特徴量空間Ｖから超球Ｓの北極ＳＮまでの高さをｄと定義する。北極ＳＮと、点ｘＶとを通る直線と、超球Ｓの表面との交点が、ｘＳに対応する。また、例えば、図４に示すように、超球Ｓの断面ＳＡは、特徴量空間Ｖの領域ＶＡに対応する。
【００２０】
ここで、逆立体射影は、立体射影の逆射影である。立体射影は、図３のように超球Ｓと特徴量空間Ｖとを配置し、北極ＳＮから超球Ｓと交わる直線を引いたとき、超球Ｓと直線との交点ｘＳから直線と特徴量空間Ｖとの交点ｘＶへの写像と定義される。図３に示す例は、ｐの値が１である場合を示す。
【００２１】
特徴量空間Ｖの特徴量ベクトル（座標）を（ｘ１，ｘ２，・・・、ｘｍ）とするとき、逆立体射影「ｆ−１：Ｖ→Ｗ」を、式（１）とする。ただし、式（１）のｒ２は、式（２）で定義される。
【００２２】
【数１】
2015118639.tif 000003
【００２３】
【数２】
2015118639.tif 000004
【００２４】
式（１）および式（２）において、ｘ０およびｄはパラメータである。パラメータｘ０およびｄは、図３に示すｘ０およびｄに対応するものである。パラメータｘ０は、超球Ｓの南極ＳＳに写像される特徴量空間Ｖの点の座標である。パラメータｄは、立体射影のスケールを調整するパラメータであり、超球Ｓの赤道が特徴量空間Ｖに写像された時の超球Ｓの半径に相当するものである。なお、超球Ｓの赤道の座標は、（ｘＳ１，ｘＳ２，・・・，ｘＳｍ，０）となる。
【００２５】
逆立体射影部１０４は、後述するパラメータ設定部１０８から、パラメータｘ０およびパラメータｄを取得する。逆立体射影部１０４は、特徴量ベクトルを、式（１）に代入することで、逆立体射影を行う。
【００２６】
逆立体射影部１０４ａは、クエリ記憶部１０２に記憶された特徴量ベクトルと式（１）とを基にして、逆立体射影を行い、特徴量ベクトルに対応する超球Ｓ上の座標を算出する。逆立体射影部１０４ａは、算出した座標を、ビット列生成部１０５ａに出力する。
【００２７】
逆立体射影部１０４ｂは、特徴量記憶部１０１に記憶された各特徴量ベクトルと式（１）とを基にして、逆立体射影を行い、各特徴量ベクトルに対応する超球Ｓ上の複数の座標を算出する。逆立体射影部１０４ｂは、算出した複数の座標を、ビット列生成部１０５ｂおよび超平面配置部１０６に出力する。
【００２８】
ビット列生成部１０５ａ，１０５ｂは、超球Ｓ上の座標を変換規則に従って、ビット列に変換する処理部である。このビット列は、ハッシュベクトルに対応する。以下の説明では、ビット列生成部１０５ａ，１０５ｂをまとめて適宜、ビット列生成部１０５と表記する。ビット列生成部１０５は、生成部の一例である。
【００２９】
ビット列生成部１０５は、式（３）を基にして、超球Ｓ上の座標を、ビット列に変換する。
【００３０】
【数３】
2015118639.tif 000005
【００３１】
式（３）において、ｎ×（ｍ＋１）行列の情報「Ｗ１１，Ｗ１２,・・・，Ｗｎ（ｍ＋１）」およびｎ×１の情報「ｃ１，ｃ２，・・・，ｃｎ」は、変換規則である。ビット列生成部１０５は、変換規則を、後述する変換規則生成部１０７から取得する。式（３）において、「ｘ１，ｘ２，・・・，ｘｍ＋１」の情報は、超球Ｓ上の座標である。
【００３２】
ビット列生成部１０５は、式（３）を計算することで、「ｂ１，ｂ２，ｂ３，・・・、ｂｎ」を算出する。例えば、ビット列生成部１０５は、ｂＮを式（４）のように計算する。
【００３３】
ｂＮ＝（ＷＮ１×ｘ１＋ＷＮ２×ｘ２＋・・・＋ＷＮ、ｍ＋１×ｘｍ＋１）＋ｃＮ・・・（４）
【００３４】
ビット列生成部１０５は、「ｂ１，ｂ２，ｂ３，・・・、ｂｎ」を算出した後に、ｂＮの値が正であれば、ｂＮを「１」に変換し、ｂＮの値が正でない場合には、ｂＮを「０」に変換することで、ビット列を算出する。例えば、「ｂ１，ｂ２，ｂ３，・・・，ｂｎ」の値がそれぞれ正、負、正、・・・、正の場合には、ビット列生成部１０５は、ビット列「１，０，１，・・・，１」を生成する。
【００３５】
ビット列生成部１０５ａは、逆立体射影部１０４ａから取得した座標を基にして、ビット列を生成し、生成したビット列をハミング距離生成部１０４に出力する。
【００３６】
ビット列生成部１０５ｂは、逆立体射影部１０４ｂから取得する各座標を基にして、複数のビット列を生成し、生成した複数のビット列をビット列記憶部１０３に出力する。
【００３７】
超平面配置部１０６は、（ｍ＋ｐ−１）次元の超球Ｓを横切る超平面をｎ個、超球Ｓに配置する処理部である。超平面配置部１０６は、超球Ｓを横切る超平面であれば、ランダムにｎ個の超平面を並べても良いし、予め設定された位置にｎ個の超平面を並べても良い。超平面配置部１０６は、各超平面の法線ベクトルおよびオフセット座標を特定し、特定した法線ベクトルの情報およびオフセット座標の情報を変換規則生成部１０７に出力する。法線ベクトルを（ｖ１，ｖ２，・・・，ｖｎ）とし、オフセット座標を（ｃ１，ｃ２，・・・ｃｎ）とする。
【００３８】
変換規則生成部１０７は、法線ベクトルの情報およびオフセット座標の情報を基にして、変換規則の情報を生成する処理部である。変換規則生成部１０７は、ｎ個の法線ベクトルを並べることで、ｎ×（ｍ＋１）行列の情報「Ｗ１１，Ｗ１２,・・・、Ｗｎ（ｍ＋１）」を生成する。例えば、式（３）のｎ×（ｍ＋１）行列の各行がそれぞれ、法線ベクトルに対応する。なお、変換規則生成部１０７は、ｎ×（ｍ＋１）行列の情報のうち、不足する次元の値には、ランダム値を割り当てる。また、変換規則生成部１０７は、オフセット座標を、ｎ×１の情報として生成する。
【００３９】
変換規則生成部１０７は、ｎ×（ｍ＋１）行列の情報およびｎ×１の情報を、ビット列生成部１０５およびパラメータ設定部１０８に出力する。
【００４０】
パラメータ設定部１０８は、パラメータｘ０およびｄを算出する処理部である。パラメータ設定部１０８は、検索部の一例である。パラメータ設定部１０８は、算出したパラメータｘ０およびｄを立体射影部１０４に出力する。パラメータ設定部１０８の処理について具体的に説明する。
【００４１】
パラメータ設定部１０８が、パラメータｘ０（ｘ０１，ｘ０２，・・・，ｘ０ｍ）を算出する処理について説明する。パラメータ設定部１０８は、特徴量記憶部１０１から各特徴量ベクトルを取得し、各特徴量ベクトルの平均値μを算出する。パラメータ設定部１０８は、平均値μをパラメータｘ０に設定する。
【００４２】
パラメータ設定部１０８が、パラメータｄを算出する処理について説明する。パラメータ設定部１０８は、特徴量記憶部１０１から各特徴量ベクトルを取得し、各特徴量ベクトルの分散共分散列の固有値σｉの平方根を算出する。分散共分散列の固有値は、多次元の特徴量ベクトルが期待値からどれだけ散らばっているかを示す値であり、値が大きいほど、より散らばっていると言える。パラメータ設定部１０８は、各固有値σｉのうち、最大のものをσとして特定する。パラメータ設定部１０８は、σの値をパラメータｄに設定する。
【００４３】
パラメータ設定部１０８は、各特徴量ベクトルが散らばっているほど、パラメータｄの値が大きくなる。これによって、逆立体射影部１０４が逆立体射影を実行すると、特徴量ベクトルが超球の南半球に集約されることになる。
【００４４】
ハミング距離計算部１０９は、ビット列生成部１０５ａから取得するビット列と、ビット列記憶部１０３に格納された各ビット列とのハミング距離を算出する処理部である。ハミング距離は、桁数の同じ２つの２進数を比較した場合の、異なる桁の個数である。以下の説明において、ビット列生成部１０５ａから取得するビット列をクエリビット列と表記する。
【００４５】
ハミング距離計算部１０９は、クエリビット列とビット列記憶部１０３の各ビット列とのハミング距離の算出結果を、類似ベクトル特定部１１０に出力する。
【００４６】
類似ベクトル特定部１１０は、ハミング距離計算部１０９のハミング距離の算出結果を取得し、クエリビット列とのハミング距離が近い順に、各ビット列に対して順位付けを行う。類似ベクトル特定部１１０は、順位付けした各ビット列のうち、上位のビット列を、クエリビット列に対応するビット列として出力しても良いし、順位付けの結果を出力しても良い。類似ベクトル特定部１１０は、特定部の一例である。
【００４７】
次に、本実施例１に係る検索装置１００の処理手順の一例について説明する。図５は、本実施例１に係る検索装置の処理手順を示すフローチャートである。図５に示すように、検索装置１００のパラメータ設定部１０８は、パラメータ特定処理を実行する（ステップＳ１０１）。
【００４８】
検索装置１００の逆立体射影部１０４ａが、パラメータｄおよびｘ０を基にして、クエリの特徴ベクトルを逆立体射影し、ビット列生成部１０５ａが、クエリビット列を生成する（ステップＳ１０２）。
【００４９】
検索装置１００の逆立体射影部１０４ｂが、パラメータｄおよびｘ０を基にして、特徴量記憶部１０１の各特徴量ベクトルを逆立体射影し、ビット列生成部１０５ｂが、ビット列を生成する（ステップＳ１０３）。
【００５０】
検索装置１００のハミング距離計算部１０９が、クエリビット列とビット列記憶部１０３のビット列とのハミング距離を計算し、類似ベクトル特定部１１０が、クエリビット列に類似するビット列を特定する（ステップＳ１０４）。
【００５１】
次に、図５のステップＳ１０１に示したパラメータ特定処理の処理手順について説明する。図６は、本実施例１に係るパラメータ特定処理の処理手順を示すフローチャートである。図６に示すように、パラメータ設定部１０８は、特徴量記憶部１０１の特徴量ベクトルの平均値μを算出する（ステップＳ１１０）。
【００５２】
パラメータ設定部１０８は、特徴量ベクトルの分散共分散行列の固有値σｉの平方根を算出し、その中で最大のものをσに設定する（ステップＳ１１１）。パラメータ設定部１０８は、μの値をｘ０に設定する（ステップＳ１１２）。パラメータ設定部１０８は、σの値をｄに設定する（ステップＳ１１３）。
【００５３】
次に、本実施例１に係る検索装置１００の効果について説明する。検索装置１００は、ｍ次元の特徴量ベクトルを（ｍ＋ｐ−１）次元の超球に逆立体射影してビット列を求める場合に、特徴ベクトルが超球の南半球に射影されるパラメータｄおよびｘ０を検索する。このように、検索装置１００は、特徴量ベクトルに対して逆立体射影を実行することで、ビット列を求めるため、ハッシュベクトルを計算する場合の計算量を削減することが出来る。更に、検索装置１００は、特徴量ベクトルが超球の南半球に逆立体射影されるパラメータを用いて、逆立体射影を行うため、無限遠点を通るショートカットの影響を除外して、正確に、クエリビット列とビット列とのハミング距離を算出することができる。
【００５４】
図７は、無限遠点のショートカットを説明するための図である。本実施例１に係る検索装置１００のようにパラメータ設定を実行しない場合には、特徴量空間Ｖの無限遠点が、超球Ｓの北極に一点射影される。このため、例えば、特徴量空間Ｖの点ｘ０から十分に遠い点ｐが逆立体射影すると超球Ｓ上の点ｐ’に対応付けられる。また、特徴量空間Ｖの点ｑを逆立体射影すると超球Ｓ上の点ｑ’に対応付けられる。このような逆立体射影が行われると、ショートカットが発生する。例えば、特徴量空間Ｖの原点付近を通る経路１０ａよりも、無限読点付近を通る経路１０ｂが近くなってしまう場合がある。そうすると、特徴量空間Ｖ上では距離１０ｃだけ離れている点同士であっても、超球Ｓ上では、距離が近くなってしまう場合があり、これによって、点ｐのビット列と、点ｑのビット列とのハミング距離が近くなってしまう場合がある。
【００５５】
これに対して、本実施例１に係る検索装置１００は、特徴量ベクトルが超球の南半休に逆立体射影されるパラメータを用いて、逆立体射影を行うため、無限遠点を通るショートカットの影響を除外して、正確に、クエリビット列とビット列とのハミング距離を算出することができる。
【００５６】
ところで、本実施例１では、検索装置１００は、特徴量ベクトルが超球の南半球に逆立体射影されるパラメータを計算していたが、これに限定されるものではない。例えば、検索装置１００は、特徴量ベクトルが超球の東半球に逆立体射影されるパラメータを算出しても良いし、特徴量ベクトルが超球の西半球に逆立体射影されるパラメータを算出しても良い。
【００５７】
図８は、特徴量ベクトルが超球の東半球に逆立体射影されるパラメータの一例を示す図である。図８に示すように、各特徴量ベクトルが特徴量空間Ｖの領域２０ａに分布している場合には、検索装置１００は、領域２０ａの平均値から所定距離左側にｘ０を設定する。なお、第一成分が正となる方向を右とする。このように、検索装置１００がｘ０を設定することで、特徴量ベクトルが超球の東半球２１ａに逆立体射影されるパラメータを求めることが出来る。なお、パラメータｄは、パラメータ設定部１０８と同様の処理を実行して求めることができる。
【００５８】
図９は、特徴量ベクトルが超球の西半球に逆立体射影されるパラメータの一例を示す図である。図９に示すように、各特徴量ベクトルが特徴量空間Ｖの領域２０ｂに分布している場合には、検索装置１００は、領域２０ｂの平均値から所定距離右側にｘ０を設定する。このように、検索装置１００がｘ０を設定することで、特徴量ベクトルが超球の西半球２１ｂに逆立体射影されるパラメータを求めることが出来る。なお、パラメータｄは、パラメータ設定部１０８と同様の処理を実行して求めることができる。
【実施例２】
【００５９】
本実施例２に係る検索装置の構成の一例について説明する。図１０は、本実施例２に係る検索装置の構成を示す機能ブロック図である。図１０に示すように、この検索装置２００は、特徴量記憶部１０１、クエリ記憶部１０２、ビット列記憶部１０３、逆立体射影部１０４ａ，１０４ｂ、ビット列生成部１０５ａ，１０５ｂを有する。また、検索装置１００は、超平面配置部１０６、変換規則生成部１０７、ハミング距離計算部１０９、類似ベクトル特定部１１０、パラメータ設定部２１０を有する。
【００６０】
図１０に示す各処理部のうち、特徴量記憶部１０１、クエリ記憶部１０２、ビット列記憶部１０３、逆立体射影部１０４ａ，１０４ｂ、ビット列生成部１０５ａ，１０５ｂに関する説明は、図１に示した各処理部と同様であるため、同一の符号を付して説明を省略する。また、図１０に示す各処理部のうち、超平面配置部１０６、変換規則生成部１０７、ハミング距離計算部１０９、類似ベクトル特定部１１０に関する説明は、図１に示した各処理部と同様であるため、説明を省略する。
【００６１】
パラメータ設定部２１０は、パラメータｘ０およびｄを算出する処理部である。パラメータ設定部２１０は、算出したパラメータｘ０およびｄを逆立体射影部１０４に出力する。パラメータ設定部２１０の処理について具体的に説明する。
【００６２】
パラメータ設定部２１０が、パラメータｘ０（ｘ０１，ｘ０２，・・・，）を算出する処理について説明する。パラメータ設定部２１０は、特徴量記憶部１０１から各特徴量ベクトルを取得し、各特徴量ベクトルの平均値μを算出する。パラメータ設定部２１０は、平均値μをパラメータｘ０に設定する。
【００６３】
パラメータ設定部２１０が、パラメータｄを算出する処理について説明する。パラメータ設定部２１０は、特徴量記憶部１０１から各特徴量ベクトルを取得し、各特徴量ベクトルの分散共分散列の固有値σｉの平方根を算出する。パラメータ設定部２１０は、各固有値σｉのうち、最大のものをσとして特定する。
【００６４】
パラメータ設定部２１０は、特徴量ベクトルを主成分分析し、累積寄与率を算出する。例えば、パラメータ設定部２１０は、主成分分析を行い、各次元の主成分の広がりを求める。パラメータ設定部２１０は、各次元の主成分の広がりを降順に並べ、広がりの大きいものから順に、σ１、σ２、・・・、σＮとする。パラメータ設定部２１０は、式（５）を基にして、λを算出する。また、パラメータ設定部２１０は、式（６）を基にして、累積寄与率λｍを算出する。
【００６５】
【数４】
2015118639.tif 000006
【００６６】
【数５】
2015118639.tif 000007
【００６７】
パラメータ設定部２１０は、横軸に成分の数「ｉ」、縦軸に対数累積寄与率「ｌｏｇλｍ」とするグラフに、ｉとｌｏｇλｍとの関係をプロットし、プロットした結果から近似直線を特定する。例えば、配置部１０５は、最小二乗法などを用いて近似直線を特定する。図１１は、近似直線の一例を示す図である。パラメータ設定部１０６は、近似直線の傾きを「γ＋１」として算出する。そして、パラメータ設定部２１０は、式（７）を算出することで、パラメータｄを算出する。
【００６８】
ｄ＝σ／（γ＋１）・・・（７）
【００６９】
次に、本実施例２に係る検索装置２００の処理手順について説明する。検索装置２００の処理手順は、図５に示した処理手順と同様である。検索装置２００は、パラメータ特定処理の内容が、実施例１のパラメータ特定処理と異なるため、ここでは、実施例２に係るパラメータ特定処理の処理手順について説明する。
【００７０】
図１２は、本実施例２に係るパラメータ特定処理の処理手順を示すフローチャートである。図１２に示すように、パラメータ設定部２１０は、特徴量記憶部１０１の特徴量ベクトルの平均値μを算出する（ステップＳ２０１）。
【００７１】
パラメータ設定部２１０は、特徴量ベクトルの分散共分散行列の固有値σｉの平方根を算出し、その中で最大のものをσに設定する（ステップＳ２０２）。パラメータ設定部２１０は、特徴量ベクトルを主成分分析し、累積寄与率を算出する（ステップＳ２０３）。
【００７２】
パラメータ設定部２１０は、近似直線の傾きを「γ＋１」として設定する（ステップＳ２０４）。パラメータ設定部２１０は、μの値をｘ０に設定する（ステップＳ２０５）。パラメータ設定部２１０は、σの値をｄに設定する（ステップＳ２０６）。
【００７３】
次に、本実施例２に係る検索装置２００の効果について説明する。検索装置２００は、累積寄与率曲線の傾きを「γ＋１」として設定し、設定した「γ＋１」と分散共分散行列の値とを基にして、パラメータｄを算出する。このパラメータｄを用いて、逆立体射影を行うと、特徴量ベクトルが超球の南半球に対応付けられるため、無限遠点を通るショートカットの影響を除外して、正確に、クエリビット列とビット列とのハミング距離を算出することができる。
【実施例３】
【００７４】
本実施例３に係る検索装置の構成の一例について説明する。図１３は、本実施例３に係る検索装置の構成を示す機能ブロック図である。図１３に示すように、この検索装置３００は、特徴量記憶部１０１、クエリ記憶部１０２、ビット列記憶部１０３、逆立体射影部１０４ａ，１０４ｂ、ビット列生成部１０５ａ，１０５ｂを有する。また、検索装置１００は、超平面配置部１０６、変換規則生成部１０７、ハミング距離計算部１０９、類似ベクトル特定部１１０、パラメータ設定部３１０を有する。
【００７５】
図１３に示す各処理部のうち、特徴量記憶部１０１、クエリ記憶部１０２、ビット列記憶部１０３、逆立体射影部１０４ａ，１０４ｂ、ビット列生成部１０５ａ，１０５ｂに関する説明は、図１に示した各処理部と同様であるため、同一の符号を付して説明を省略する。また、図１３に示す各処理部のうち、超平面配置部１０６、変換規則生成部１０７、ハミング距離計算部１０９、類似ベクトル特定部１１０に関する説明は、図１に示した各処理部と同様であるため、説明を省略する。
【００７６】
パラメータ設定部３１０は、パラメータｘ０およびｄを算出する処理部である。パラメータ設定部３１０は、算出したパラメータｘ０およびｄを立体射影部１０４に出力する。本実施例３に係るパラメータ設定部３１０は、山登り探索、マルコフ連鎖モンテカルロ法、群知能のいずれかを用いて、パラメータｘ０およびｄを算出する。
【００７７】
パラメータ設定部３１０が、「山登り探索」を用いて、パラメータｘ０およびｄを特定する処理の一例について説明する。パラメータ設定部３１０は、パラメータｘ０およびｄの初期値を特定し、この初期値によって算出される各特徴量ベクトルのビット列を、ビット列生成部１０５ｂから取得する。パラメータ設定部３１０は、例えば、実施例１に示したパラメータ１０８と同様の手法により、パラメータｘ０およびｄの初期値を特定する。パラメータ設定部３１０は、各特徴量ベクトルとビット列とを基にして、近似類似検索を実行し、近似精度を計算する。例えば、近似精度は、式（８）によって算出される。
【００７８】
【数６】
2015118639.tif 000008
【００７９】
ここで、近似精度を算出する処理の一例について説明する。例えば、パラメータ設定部３１０は、特徴量記憶部１０１から、ある特徴量ベクトルｖａを選出し、特徴量ベクトルｖａとの距離が、特徴量空間上で最も近い特徴量ベクトルを、第１位から第Ｍ位まで特定する。特徴量ベクトルｖａとの距離が、特徴量空間上で最も近い特徴量ベクトルを特徴量ベクトルｖａ１〜ｖａＭとする。例えば、式（８）において、特徴量ベクトルの数Ｍが、｜Ｒｋ｜に対応する。
【００８０】
パラメータ設定部３１０は、ビット列生成部１０５ｂから特徴量ベクトルｖａに対応するビット列との距離が、最も近いビット列を、第１位から第Ｍ位まで特定し、特定したビット列に対応する特徴量ベクトルｖｂ１〜ｖｂＭを特定する。例えば、パラメータ設定部３１０は、識別情報を基にして、ビット列と特徴量ベクトルを対応付ければよい。パラメータ設定部３１０は、特徴量ベクトルｖｂ１〜ｖｂＭのうち、何個の特徴量ベクトルが、特徴量ベクトルｖａ１〜ｖａＭと同一のものであるかを計数する。この計数した数が、式（８）の｜Ｒｋ∩Ｑｋ｜に対応する。
【００８１】
パラメータ設定部３１０は、初期値のパラメータｘ０およびｄを算出した後に、パラメータｘ０およびｄの近傍値を設定して、逆立体射影部１０４ｂに出力し、近傍値に対する近似精度を算出する。パラメータ設定部３１０は、上記処理を繰り返し実行し、近似精度の最も高いパラメータｘ０およびｄを特定する。
【００８２】
ハミング距離計算部１０９は、パラメータ設定部３１０によって特定された近似精度の最も高いパラメータｘ０およびｄによって算出されたビット列を基にして、ハミング距離を計算する。
【００８３】
続いて、パラメータ設定部３１０が、「マルコフ連鎖モンテカルロ法」を用いて、パラメータｘ０およびｄを特定する処理の一例について説明する。パラメータ設定部３１０は、第１のパラメータｘ０およびｄを特定し、この第１のパラメータｘ０およびｄによって算出される各特徴量ベクトルのビット列を、ビット列生成部１０５ｂから取得する。パラメータ設定部３１０は、例えば、実施例１に示したパラメータ１０８と同様の手法により、第１のパラメータｘ０およびｄの初期値を特定する。パラメータ設定部３１０は、各特徴量ベクトルとビット列とを基にして、近似類似検索を実行し、第１のパラメータの近似精度Ｘ１を計算する。例えば、近似精度は、山登り探索と同様にして、式（８）によって算出される。
【００８４】
パラメータ設定部３１０は、第１のパラメータｘ０およびｄの近傍値を、第２のパラメータｘ０およびｄとして設定する。パラメータ設定部３１０は、この第２のパラメータｘ０およびｄによって算出される各特徴量ベクトルのビット列を、ビット列生成部１０５ｂから取得する。パラメータ設定部３１０は、各特徴量ベクトルとビット列とを基にして、近似類似検索を実行し、第２のパラメータの近似精度Ｘ２を計算する。
【００８５】
パラメータ設定部３１０は、乱数を振り、乱数の値がＸ２／Ｘ１よりも小さい場合に、第２のパラメータｘ０およびｄを第１のパラメータｘ０およびｄに設定する。また、パラメータ設定部３１０は、第１のパラメータｘ０およびｄの近傍値を第２のパラメータｘ０およびｄに設定し、上記処理を繰り返し実行する。
【００８６】
一方、パラメータ設定部３１０は、乱数を振り、乱数の値がＸ２／Ｘ１よりも小さくない場合に、第１のパラメータｘ０およびｄをそのままにする。また、パラメータ設定部３１０は、第１のパラメータｘ０およびｄの新たな近傍値を第２のパラメータｘ０およびｄに設定し、上記処理を繰り返し実行する。
【００８７】
パラメータ設定部３１０が上記処理を所定回数繰り返した後に得られる最終的な第１のパラメータｘ０およびｄを用いて、ハミング距離計算部１０９は、ハミング距離を計算する。
【００８８】
続いて、パラメータ設定部３１０が、「群知能」を用いて、パラメータｘ０およびｄを特定する処理の一例について説明する。パラメータ設定部３１０は、複数のパラメータｘ０およびｄを特定する。例えば、パラメータ設定部３１０は、実施例１に示したパラメータ１０８と同様の手法により、パラメータｘ０およびｄを求め、更に、このパラメータｘ０およびｄの近傍値を複数求めることで、複数のパラメータｘ０およびｄを特定する。
【００８９】
パラメータ設定部３１０は、複数のパラメータｘ０およびｄによって算出される各特徴量ベクトルのビット列を、ビット列生成部１０５ｂから取得する。パラメータ設定部３１０は、各パラメータｘ０およびｄを、荷電粒子の位置と見なし、目的関数を使用して、荷電系探索を実行することで、近似精度の最も高いパラメータｘ０およびｄを特定する。
【００９０】
パラメータｘ０およびｄを荷電粒子の位置とみなすことで、各パラメータｘ０およびｄを移動させる場合に、各パラメータｘ０およびｄが、相互に近づかないような制約を設けることが出来る。そして、所定距離離れた位置で、近似精度が最も大きくなるパラメータｘ０およびｄを、荷電粒子の位置毎に特定することができる。パラメータ設定部３１０は、荷電粒子毎に特定した最大の近似精度となるパラメータｘ０およびｄのうち、最大の近似精度となるパラメータｘ０およびｄを特定する。係るパラメータを使用して、ハミング距離計算部１０９は、ハミング距離を計算する。
【００９１】
なお、荷電系探索の目的関数は、パラメータｘ０およびｄが与えられた場合に、近似精度を算出する関数であり、近似精度を算出する処理の内容は、上述した山登り検索およびマルコフ連鎖モンテカルロ法と同様である。
【００９２】
次に、本実施例３に係る検索装置３００の処理手順について説明する。検索装置３００の処理手順は、図５に示した処理手順と同様である。検索装置３００は、パラメータ特定処理の内容が、実施例１のパラメータ特定処理と異なるため、ここでは、実施例３に係るパラメータ特定処理の処理手順について説明する。以下では、パラメータ特定処理を、山登り探索を用いたパラメータ特定処理、マルコフ連鎖モンテカルロ法を用いたパラメータ特定処理、群知能を用いたパラメータ特定処理について順に説明する。
【００９３】
まず、山登り探索を用いたパラメータ特定処理の処理手順の一例について説明する。図１４は、山登り探索を用いたパラメータ特定処理の処理手順を示すフローチャートである。図１４に示すように、検索装置３００のパラメータ設定部３１０は、パラメータｘ０およびｄを特定する（ステップＳ３０１）。逆立体射影部１０４は、特徴量ベクトルを超球に逆立体射影し、超平面配置部１０６に結果を出力する（ステップＳ３０２）。
【００９４】
検索装置３００は、所定回数処理を繰り返した場合には（ステップＳ３０３，Ｙｅｓ）、パラメータ特定処理を終了する。一方、検索装置３００は、所定回数処理を繰り返していない場合には（ステップＳ３０３，Ｎｏ）、ステップＳ３０４に移行する。
【００９５】
超平面配置部１０６は、超球に超平面を配置し、変換規則生成部１０７は、変換規則を生成する（ステップＳ３０４）。パラメータ設定部３１０は、近似類似検索の近似精度を計算する（ステップＳ３０５）。
【００９６】
パラメータ設定部３１０は、パラメータｄおよびｘ０の近傍値を複数生成し、それぞれを逆立体射影部１０４ｄに出力する（ステップＳ３０６）。逆立体射影部１０４ｂは、それぞれのパラメータｄおよびｘ０を用いて、特徴量ベクトルを超球に逆立体射影し、超平面配置部１０６に出力する（ステップＳ３０７）。
【００９７】
超平面配置部１０６は、超球に超平面を配置し、変換規則を生成する（ステップＳ３０８）。パラメータ設定部３１０は、ビット列生成部１０５ｂからビット列を取得し、各近傍値での近似精度を計算する（ステップＳ３０９）。パラメータ設定部３１０は、最も近似精度の良い値を、パラメータｄおよびｘ０に設定し（ステップＳ３１０）、ステップＳ３０３に移行する。
【００９８】
次に、マルコフ連鎖モンテカルロ法を用いたパラメータ特定処理の処理手順の一例について説明する。図１５は、マルコフ連鎖モンテカルロ法を用いたパラメータ特定処理の処理手順を示すフローチャートである。
【００９９】
図１５に示すように、検索装置３００のパラメータ設定部３１０は、パラメータｘ０およびｄを特定する（ステップＳ４０１）。逆立体射影部１０４は、特徴量ベクトルを超球に逆立体射影し、超平面配置部１０６に結果を出力する（ステップＳ４０２）。
【０１００】
検索装置３００は、所定回数処理を繰り返した場合には（ステップＳ４０３，Ｙｅｓ）、パラメータ特定処理を終了する。一方、検索装置３００は、所定回数処理を繰り返していない場合には（ステップＳ４０３，Ｎｏ）、ステップＳ４０４に移行する。
【０１０１】
超平面配置部１０６は、超球に超平面を配置し、変換規則生成部１０７は、変換規則を生成する（ステップＳ４０４）。パラメータ設定部３１０は、近似類似検索の近似精度を計算する（ステップＳ４０５）。
【０１０２】
パラメータ設定部３１０は、近似類似検索の近似精度Ｘ１を計算する（ステップＳ４０５）。パラメータ設定部３１０は、パラメータｘ０およびｄの近傍値を一つ生成し、逆立体射影部１０４ｂに出力する（ステップＳ４０６）。
【０１０３】
逆立体射影部１０４ｂは、近傍値を用いて、特徴量ベクトルを超球に逆立体射影し、超平面配置部１０６に出力する（ステップＳ４０７）。超平面配置部１０６は、超球に超平面を配置し、変換規則を生成する（ステップＳ４０８）。パラメータ設定部３１０は、ビット列生成部１０５ｂからビット列を取得し、近傍値での近似精度Ｘ２を計算する（ステップＳ４０９）。
【０１０４】
パラメータ設定部３１０は、［０、１］の乱数を割り振り、乱数がＸ２／Ｘ１よりも小さい場合には、近傍値をパラメータｘ０およびｄに設定し、そうでなければ、パラメータｘ０およびｄをそのままにし（ステップＳ４１０）、ステップＳ４０３に移行する。
【０１０５】
次に、群知能を用いたパラメータ特定処理の処理手順の一例について説明する。図１６は、群知能を用いたパラメータ特定処理の処理手順を示すフローチャートである。
【０１０６】
図１６に示すように、検索装置３００のパラメータ設定部３１０は、パラメータｘ０およびｄを特定する（ステップＳ５０１）。逆立体射影部１０４は、特徴量ベクトルを超球に逆立体射影し、超平面配置部１０６に結果を出力する（ステップＳ５０２）。
【０１０７】
検索装置３００は、所定回数処理を繰り返した場合には（ステップＳ５０３，Ｙｅｓ）、パラメータ特定処理を終了する。一方、検索装置３００は、所定回数処理を繰り返していない場合には（ステップＳ５０３，Ｎｏ）、ステップＳ５０４に移行する。
【０１０８】
パラメータ設定部３１０は、それぞれのパラメータを荷電粒子の位置と見なし、目的関数を使用して、荷電系探索を実行し、パラメータｘ０およびｄを特定し（ステップＳ５０４）、ステップＳ５０３に移行する。
【０１０９】
ここで、図１６のステップＳ５０４で示した目的関数の処理手順の一例について説明する。図１７は、目的関数の処理手順の一例を示すフローチャートである。
【０１１０】
図１７に示すように、検索装置３００の超平面配置部１０６は超平面を配置し、変換規則生成部１０７が変換規則を生成する（ステップＳ５１１）。パラメータ設定部３１０は、近似類似検索の近似精度Ｘ１を計算し（ステップＳ５１２）、近似精度Ｘ１を出力する（ステップＳ５１３）。
【０１１１】
次に、本実施例３に係る検索装置３００の効果について説明する。検索装置３００は、パラメータｘ０およびｄを特定する場合に、山登り探索、マルコフ連鎖モンテカルロ法、群知能を用いるため、最適なパラメータｘ０およびｄを効率的に特定することができる。
【０１１２】
ところで、上記実施例では、特徴量空間Ｖの次元よりも１大きい次元の空間に存在する超球Ｓに対して逆立体射影を実行する場合について説明したがこれに限定されるものではない。例えば、特徴量空間Ｖの次元よりも２以上大きい次元の空間に存在するｍ次元球に対して、逆立体射影する場合にも、同様に本願を適用することができる。
【０１１３】
次に、上記実施例に示した検索装置と同様の機能を実現する画像処理装置を実行するコンピュータの一例について説明する。図１８は、検索プログラムを実行するコンピュータの一例を示す図である。
【０１１４】
図１８に示すように、このコンピュータ４００は、各種演算処理を実行するＣＰＵ４０１と、ユーザからのデータの入力を受け付ける入力装置４０２と、ディスプレイ４０３を有する。また、コンピュータ４００は、記憶媒体からプログラム等を読取る読み取り装置４０４と、ネットワークを介して他のコンピュータとの間でデータの授受を行うインターフェース装置４０５とを有する。また、コンピュータ４００は、各種情報を一時記憶するＲＡＭ４０６と、ハードディスク装置４０７を有する。そして、各装置４０１〜４０７は、バス４０８に接続される。
【０１１５】
ハードディスク装置４０７は、検索プログラム４０７ａ、射影プログラム４０７ｂ、生成プログラム４０７ｃ、特定プログラム４０７ｄを有する。ＣＰＵ４０１は、各プログラム４０７ａ〜４０７ｄを読み出してＲＡＭ４０６に展開する。
【０１１６】
検索プログラム４０７ａは、検索プロセス４０６ａとして機能する。射影プログラム４０７ｂは、射影プロセス４０６ｂとして機能する。生成プログラム４０７ｃは、生成プロセス４０６ｃとして機能する。特定プログラム４０７ｄは、特定プロセス４０６ｄとして機能する。
【０１１７】
例えば、検索プロセス４０６ａは、パラメータ設定部１０８に対応する。射影プロセス４０６ｂは、逆立体射影部１０４に対応する。生成プロセス４０６ｃは、ビット列生成部１０５に対応する。特定プロセス４０６ｄは、類似ベクトル特定部１１０に対応する。
【０１１８】
なお、各プログラム４０７ａ〜４０７ｄについては、必ずしも最初からハードディスク装置４０７に記憶させておかなくても良い。例えば、コンピュータ４００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ２００がこれらから各プログラム４０７ａ〜４０７ｄを読み出して実行するようにしてもよい。
【０１１９】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１２０】
（付記１）コンピュータが実行する検索方法であって、
データベースに記憶された第１次元の特徴量ベクトルを取得し、
特徴量空間と、前記特徴量空間の次元よりも１次元以上大きい空間に存在する球を通る直線との交点および前記球の所定点から前記特徴量空間までの距離を含むパラメータを基にして前記特徴量ベクトルを前記球の表面上に射影する場合に、前記球の表面上に射影される特徴量ベクトルの位置が、前記球の半球に集約されるパラメータを検索する
処理を実行することを特徴とする検索方法。
【０１２１】
（付記２）前記検索する処理によって探索されたパラメータを用いて複数の特徴量ベクトルを前記球の表面上に射影し、射影した前記特徴量ベクトルの位置と前記球を分割する複数の超平面との関係から前記特徴量ベクトルのビット列を生成し、生成したビット列を基にして類似する特徴量ベクトルを特定する処理を判定する処理を更に実行することを特徴とする付記１に記載の検索方法。
【０１２２】
（付記３）前記検索する処理は、前記球の表面上に射影される特徴量ベクトルの位置が、前記球の南半球、東半球または西半球に集約される前記パラメータを検索することを特徴とする付記１または２に記載の検索方法。
【０１２３】
（付記４）前記検索する処理は、前記特徴量ベクトルの平均値と、前記特徴量ベクトルの分散共分散行列の固有値の最大値を基にして前記パラメータを検索することを特徴とする付記１または２に記載の検索方法。
【０１２４】
（付記５）前記検索する処理は、前記特徴量ベクトルの主成分分析結果を基にして、累積寄与率曲線を特定し、該累積寄与率曲線を基にして前記パラメータを検索することを特徴とする付記１または２に記載の検索方法。
【０１２５】
（付記６）前記検索する処理は、山登り法、マルコフ連鎖モンテカルロ法または群知能を基にして、パラメータを検索することを特徴とする付記１または２に記載の検索方法。
【０１２６】
（付記７）コンピュータに、
データベースに記憶された第１次元の特徴量ベクトルを取得し、
特徴量空間と、前記特徴量空間の次元よりも１次元以上大きい空間に存在する球を通る直線との交点および前記球の所定点から前記特徴量空間までの距離を含むパラメータを基にして前記特徴量ベクトルを前記球の表面上に射影する場合に、前記球の表面上に射影される特徴量ベクトルの位置が、前記球の半球に集約されるパラメータを検索する
処理を実行させることを特徴とする検索プログラム。
【０１２７】
（付記８）前記検索する処理によって探索されたパラメータを用いて複数の特徴量ベクトルを前記球の表面上に射影し、射影した前記特徴量ベクトルの位置と前記球を分割する複数の超平面との関係から前記特徴量ベクトルのビット列を生成し、生成したビット列を基にして類似する特徴量ベクトルを特定する処理を判定する処理を更に実行することを特徴とする付記７に記載の検索プログラム。
【０１２８】
（付記９）前記検索する処理は、前記球の表面上に射影される特徴量ベクトルの位置が、前記球の南半球、東半球または西半球に集約される前記パラメータを検索することを特徴とする付記７または８に記載の検索プログラム。
【０１２９】
（付記１０）前記検索する処理は、前記特徴量ベクトルの平均値と、前記特徴量ベクトルの分散共分散行列の固有値の最大値を基にして前記パラメータを検索することを特徴とする付記７または８に記載の検索プログラム。
【０１３０】
（付記１１）前記検索する処理は、山登り法、マルコフ連鎖モンテカルロ法または群知能を基にして、パラメータを検索することを特徴とする付記７または８に記載の検索プログラム。
【０１３１】
（付記１２）データベースに記憶された第１次元の特徴量ベクトルを取得し、特徴量空間と、前記特徴量空間の次元よりも１次元以上大きい空間に存在する球を通る直線との交点および前記球の所定点から前記特徴量空間までの距離を含むパラメータを基にして前記特徴量ベクトルを前記球の表面上に射影する場合に、前記球の表面上に射影される特徴量ベクトルの位置が、前記球の半球に集約されるパラメータを検索する検索部
を有することを特徴とする検索装置。
【０１３２】
（付記１３）前記検索部によって探索されたパラメータを用いて複数の特徴量ベクトルを前記球の表面に射影する射影部と、前記射影部に射影された前記球の表面上の前記特徴量ベクトルの位置と前記球を分割する複数の超平面との関係から前記特徴量ベクトルのビット列を生成する生成部と、生成部によって生成されたビット列を基にして類似する特徴量ベクトルを特定する特定部を更に有することを特徴とする付記１２に記載の検索装置。
【０１３３】
（付記１４）前記検索部は、前記球の表面上に射影される特徴量ベクトルの位置が、前記球の南半球、東半球または西半球に集約される前記パラメータを検索することを特徴とする付記１２または１３に記載の検索装置。
【０１３４】
（付記１５）前記検索部は、前記特徴量ベクトルの平均値と、前記特徴量ベクトルの分散共分散行列の固有値の最大値を基にして前記パラメータを検索することを特徴とする付記１２または１３に記載の検索装置。
【０１３５】
（付記１６）前記検索部は、前記特徴量ベクトルの主成分分析結果を基にして、累積寄与率曲線を特定し、該累積寄与率曲線を基にして前記パラメータを検索することを特徴とする付記１２または１３に記載の検索装置。
【０１３６】
（付記１７）前記検索部は、前記特徴量ベクトルの主成分分析結果を基にして、累積寄与率曲線を特定し、該累積寄与率曲線の傾きを基にして前記パラメータを検索することを特徴とする付記１２または１３に記載の検索装置。
【０１３７】
（付記１８）前記検索部は、山登り法、マルコフ連鎖モンテカルロ法または群知能を基にして、パラメータを検索することを特徴とする付記１２または１３に記載の検索装置。
【符号の説明】
【０１３８】
１００，２００，３００  検索装置
１０１  特徴量記憶部
１０２  クエリ記憶部
１０３  ビット列記憶部
１０４ａ，１０４ｂ  逆立体射影部
１０５ａ，１０５ｂ  ビット列生成部
１０６  超平面配置部
１０７  変換規則生成部
１０８，２１０，３１０  パラメータ設定部
１０９  ハミング距離計算部
１１０  類似ベクトル特定部
【図１】
2015118639.tif 000009
【図２Ａ】
2015118639.tif 000010
【図２Ｂ】
2015118639.tif 000011
【図３】
2015118639.tif 000012
【図４】
2015118639.tif 000013
【図５】
2015118639.tif 000014
【図６】
2015118639.tif 000015
【図７】
2015118639.tif 000016
【図８】
2015118639.tif 000017
【図９】
2015118639.tif 000018
【図１０】
2015118639.tif 000019
【図１１】
2015118639.tif 000020
【図１２】
2015118639.tif 000021
【図１３】
2015118639.tif 000022
【図１４】
2015118639.tif 000023
【図１５】
2015118639.tif 000024
【図１６】
2015118639.tif 000025
【図１７】
2015118639.tif 000026
【図１８】
2015118639.tif 000027
【手続補正書】
【提出日】平成26年10月30日(2014.10.30)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
図３および図４は、特徴量空間Ｖと超球Ｓとの関係を示す図である。図３に示すように、逆立体射影を行うと、特徴量空間Ｖ上の点と、超球Ｓ上の点とが対応付けられる。図３に示す例では、特徴量空間Ｖ上の点ｘＶと、超球Ｓ上の点ｘＳとが対応付けられる。超球Ｓの北極ＳＮと南極ＳＳを結ぶ直線と、特徴量空間Ｖとの交点をｘ０と定義する。例えば、北極ＳＮの座標は、（ｘｏ１，ｘｏ２，・・・，ｘｏｍ，１）となり、南極ＳＳの座標は、（ｘｏ１，ｘｏ２，・・・，ｘｏｍ，−１）となる。特徴量空間Ｖから超球Ｓの北極ＳＮまでの高さをｄと定義する。北極ＳＮと、点ｘＶとを通る直線と、超球Ｓの表面との交点が、ｘＳに対応する。また、例えば、図４に示すように、超球Ｓの断面ＳＡは、特徴量空間Ｖの領域ＶＡに対応する。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
【数１】
2015118639.tif 000028
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
【数５】
2015118639.tif 000029
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００６７
【補正方法】変更
【補正の内容】
【００６７】
パラメータ設定部２１０は、横軸に成分の数「ｍ」、縦軸に対数累積寄与率「ｌｏｇλｍ」とするグラフに、ｍとｌｏｇλｍとの関係をプロットし、プロットした結果から近似直線を特定する。例えば、配置部１０５は、最小二乗法などを用いて近似直線を特定する。図１１は、近似直線の一例を示す図である。パラメータ設定部１０６は、近似直線の傾きを「γ＋１」として算出する。そして、パラメータ設定部２１０は、式（７）を算出することで、パラメータｄを算出する。
【手続補正５】
【補正対象書類名】図面
【補正対象項目名】図１１
【補正方法】変更
【補正の内容】
【図１１】
2015118639.tif 000030