(57)【要約】【課題】特徴量ベクトルを用いた類似検索を精度良く実行すること。【解決手段】本実施例に係る検索装置１００は、逆立体射影部１０４が、特徴量ベクトルを複数の超平面で分割した超球に逆立体射影し、その結果を基にしてビット列生成部１０５が、ビット列を特定する場合に、配置部１０６が、各超平面の初期位置を設定する。例えば、配置部１０６は、各超平面の初期位置を各超平面の交点が超球Ｓ内に収まるように超平面の初期位置を設定する。【選択図】図１
2015118464.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.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来技術では、特徴量ベクトルを用いた類似検索を精度良く実行できないという問題がある。
【０００８】
例えば、超球を用いて特徴量ベクトルをハッシュベクトルに変換すると、ワームホールの影響により、大きく異なる特徴量ベクトル同士であっても、ハッシュベクトル変換後のハミング距離が小さくなる場合がある。このため、異なる特徴量ベクトル同士を、類似する特量ベクトルとして誤判定する場合がある。
【０００９】
ここで、ワームホールについて説明する。図１３〜図１５は、ワームホールを説明するための図である。例えば、ｍ次元の特徴量空間Ｖを超球を用いて分割し、分割された領域が超球の内部か外部かに応じてビット列を割り振ることを考える。超球の配置によっては、図１３に示すように、領域Ａと、領域Ｂとが同一のビット列（０，０，０）を持つが、領域Ａと領域Ｂとは連結していない。
【００１０】
図１３に示す現象が起こる場合には、特徴量ベクトルに割り振られたビット列間のハミング距離により、特徴量ベクトルの類似性を評価する際に、特徴量ベクトルが大きく離れていてもハミング距離が小さくなる。この非連結性を理解するためには、図１４に示すように、領域Ａと領域Ｂとを結ぶチューブ１０が存在していると考えるのがよい。このチューブを一般相対論の特殊解になぞらえてワームホールと呼ぶ。
【００１１】
図１５に、一次元の特徴量空間の超球Ｓによる領域分割を行った時の非連結領域の発生とその間を結ぶワームホール１１を示す。超球Ｓは、超平面１２ａおよび１２ｂによって分割されている。例えば、超平面１２ａよりも左の領域は、１ビット目に１が割り振られ、超平面１２ａよりも右の領域は、１ビット目に０が割り振られる。また、超平面１２ｂよりも右の領域には、２ビット目に１が割り振られ、超平面１２ｂよりも左の領域には、２ビット目に０が割り振られる。そうすると、図１５の南極付近と北極付近は連結していないが、同じビット列（０，０）が割り振られてしまう。これは、超球Ｓの南極付近と北極付近とを結ぶワームホール１１が発生したためである。
【００１２】
１つの側面では、特徴量ベクトルを用いた類似検索を精度良く実行できる空間分割方法、空間分割装置および空間分割プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
第１の案では、コンピュータが下記の処理を実行する。コンピュータが、特徴量空間の次元よりも１次元以上大きい次元の空間に存在する球を分割する複数の超平面を配置した場合の各超平面の交点位置が前記球の内部にあるような交点位置を特定し、設定した交点位置を通る複数の超平面を初期配置する。
【発明の効果】
【００１４】
本発明の１実施態様によれば、特徴量ベクトルを用いた類似検索を精度良く実行できるという効果を奏する。
【図面の簡単な説明】
【００１５】
【図１】図１は、本実施例に係る検索装置の構成を示す機能ブロック図である。
【図２】図２は、特徴量記憶部のデータ構造の一例を示す図である。
【図３】図３は、ビット列記憶部のデータ構造の一例を示す図である。
【図４】図４は、特徴量空間Ｖと超球Ｓとの関係を示す図（１）である。
【図５】図５は、特徴量空間Ｖと超球Ｓとの関係を示す図（２）である。
【図６】図６は、近似直線の一例を示す図である。
【図７】図７は、超球Ｓの赤道の立体射影による像の円の半径の一例を示す図である。
【図８】図８は、本実施例に係る検索装置の処理手順を示すフローチャートである。
【図９】図９は、超平面の初期位置設定処理の処理手順を示すフローチャートである。
【図１０】図１０は、本実施例に係る検索装置の効果を説明するための図である。
【図１１】図１１は、超平面のその他の初期位置設定処理の処理手順を示すフローチャートである。
【図１２】図１２は、空間分割プログラムを実行するコンピュータの一例を示す図である。
【図１３】図１３は、ワームホールを説明するための図（１）である。
【図１４】図１４は、ワームホールを説明するための図（２）である。
【図１５】図１５は、ワームホールを説明するための図（３）である。
【発明を実施するための形態】
【００１６】
以下に、本願の開示する空間分割方法、空間分割装置および空間分割プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００１７】
本実施例１に係る検索装置の構成の一例について説明する。検索装置は、空間分割装置の一例である。図１は、本実施例に係る検索装置の構成を示す機能ブロック図である。図１に示すように、この検索装置１００は、特徴量記憶部１０１、クエリ記憶部１０２、ビット列記憶部１０３、逆立体射影部１０４ａ，１０４ｂ、ビット列生成部１０５ａ，１０５ｂを有する。また、検索装置１００は、配置部１０６、ハミング距離計算部１０７、類似ベクトル特定部１０８を有する。
【００１８】
特徴量記憶部１０１は、複数の特徴量ベクトルを記憶する記憶部である。図２は、特徴量記憶部のデータ構造の一例を示す図である。図２に示すように、この特徴量記憶部１０１は、識別情報と、特徴量ベクトルとを対応付けて記憶する。識別情報は、特徴量ベクトルを一意に識別する情報である。特徴量ベクトルは、例えば、ユーザの生体情報から得られるｍ次元の特徴量のデータである。生体情報から特徴量ベクトルを求める手法は、如何なる従来技術を用いても良い。例えば、ｍは１以上の整数である。
【００１９】
クエリ記憶部１０２は、クエリとなる特徴量ベクトルを記憶する記憶部である。検索装置１００は、クエリとなる特徴量ベクトルに類似する特徴量ベクトルを、特徴量記憶部１０１から検索する。
【００２０】
ビット列記憶部１０３は、後述するビット列生成部１０５から取得するビット列を記憶する記憶部である。図３は、ビット列記憶部のデータ構造の一例を示す図である。図３に示すように、このビット列記憶部１０３は、識別情報と、ビット列とを対応付けて記憶する。識別情報は、ビット列の生成元となった特徴量ベクトルを一意に識別する情報である。ビット列は、特徴量ベクトルを基にして生成されるビット列である。
【００２１】
逆立体射影部１０４ａ，１０４ｂは、ｍ次元の特徴量空間Ｖに対して逆立体射影を行うことで、ｍ次元よりもｐ次元高い空間Ｗに埋め込まれた（ｍ＋ｐ−１）次元の超球Ｓと特徴量空間Ｖとを対応付ける処理部である。ｐは、１以上の整数である。以下の説明では、逆立体射影部１０４ａ，１０４ｂをまとめて適宜、逆立体射影部１０４と表記する。
【００２２】
図４および図５は、特徴量空間Ｖと超球Ｓとの関係を示す図である。図４に示すように、逆立体射影を行うと、特徴量空間Ｖ上の点と、超球Ｓ上の点とが対応付けられる。図４に示す例では、特徴量空間Ｖ上の点ｘＶと、超球Ｓ上の点ｘＳとが対応付けられる。超球Ｓの北極ＳＮと南極ＳＳを結ぶ直線と、特徴量空間Ｖとの交点をｘ０と定義する。例えば、北極ＳＮの座標は、（ｘＳ１，ｘＳ２，・・・，ｘＳｍ，１）となり、南極の座標は、（ｘＳ１，ｘＳ２，・・・，ｘＳｍ，−１）となる。
【００２３】
特徴量空間Ｖから超球Ｓの北極ＳＮまでの高さをｄと定義する。北極ＳＮと、点ｘＶとを通る直線と、超球Ｓの表面との交点が、ｘＳに対応する。また、例えば、図５に示すように、超球Ｓの断面ＳＡは、特徴量空間Ｖの領域ＶＡに対応する。
【００２４】
ここで、逆立体射影は、立体射影の逆射影である。立体射影は、図４のように超球Ｓと特徴量空間Ｖとを配置し、北極ＳＮから超球Ｓと交わる直線を引いたとき、超球Ｓと直線との交点ｘＳから直線と特徴量空間Ｖとの交点ｘＶへの写像と定義される。なお、図４に示す例は、ｐの値が１である場合を示す。
【００２５】
特徴量空間Ｖの特徴量ベクトル（座標）を（ｘ１，ｘ２，・・・、ｘｍ）とするとき、逆立体射影「ｆ−１：Ｖ→Ｗ」を、式（１）とする。ただし、式（１）のｒ２は、式（２）で定義される。
【００２６】
【数１】
2015118464.tif 000003
【００２７】
【数２】
2015118464.tif 000004
【００２８】
式（１）および式（２）において、ｘ０およびｄはパラメータである。パラメータｘ０およびｄは、図４に示すｘ０およびｄに対応するものである。パラメータｘ０は、超球Ｓの南極ＳＳに写像される特徴量空間Ｖの点の座標である。パラメータｄは、立体射影のスケールを調整するパラメータであり、超球Ｓの赤道が特徴量空間Ｖに写像された時の超球Ｓの半径に相当するものである。なお、超球Ｓの赤道の座標は、（ｘＳ１，ｘＳ２，・・・，ｘＳｍ，０）となる。
【００２９】
逆立体射影部１０４は、指定されるパラメータｘ０およびパラメータｄと式（１）とを基にして、特徴量ベクトルの逆立体射影を行う。なお、逆立体射影部１０４は、パラメータｘ０およびパラメータｄの情報を予め保持しておいても良い。
【００３０】
逆立体射影部１０４ａは、クエリ記憶部１０２に記憶された特徴量ベクトルと式（１）とを基にして、逆立体射影を行い、特徴量ベクトルに対応する超球Ｓ上の座標を算出する。逆立体射影部１０４ａは、算出した座標を、ビット列生成部１０５ａに出力する。
【００３１】
逆立体射影部１０４ｂは、特徴量記憶部１０１に記憶された各特徴量ベクトルと式（１）とを基にして、逆立体射影を行い、各特徴量ベクトルに対応する超球Ｓ上の複数の座標を算出する。逆立体射影部１０４ｂは、算出した座標を、ビット列生成部１０５ｂに出力する。
【００３２】
ビット列生成部１０５ａ，１０５ｂは、超球Ｓ上の座標を変換規則に従って、ビット列に変換する処理部である。このビット列は、ハッシュベクトルに対応する。以下の説明では、ビット列生成部１０５ａ，１０５ｂをまとめて適宜、ビット列生成部１０５と表記する。ビット列生成部１０５は、生成部の一例である。
【００３３】
式（３）において、ｎ×（ｍ＋１）行列の情報「Ｗ１１，Ｗ１２,・・・，Ｗｎ（ｍ＋１）」およびｎ×１の情報「ｃ１，ｃ２，・・・，ｃｎ」は、変換規則である。ビット列生成部１０５は、変換規則を、後述する配置部１０６から取得する。式（３）において、「ｘ１，ｘ２，・・・，ｘｍ＋１」の情報は、超球Ｓ上の座標である。
【００３４】
【数３】
2015118464.tif 000005
【００３５】
ビット列生成部１０５は、式（３）を計算することで、「ｂ１，ｂ２，ｂ３，・・・、ｂｎ」を算出する。例えば、ビット列生成部１０５は、ｂＮを式（４）のように計算する。
【００３６】
ｂＮ＝（ＷＮ１×ｘ１＋ＷＮ２×ｘ２＋・・・＋ＷＮ、ｍ＋１×ｘｍ＋１）＋ｃＮ・・・（４）
【００３７】
ビット列生成部１０５は、「ｂ１，ｂ２，ｂ３，・・・、ｂｎ」を算出した後に、ｂＮの値が正であれば、ｂＮを「１」に変換し、ｂＮの値が正でない場合には、ｂＮを「０」に変換することで、ビット列を算出する。例えば、「ｂ１，ｂ２，ｂ３，・・・，ｂｎ」の値がそれぞれ正、負、正、・・・、正の場合には、ビット列生成部１０５は、ビット列「１，０，１，・・・，１」を生成する。
【００３８】
ビット列生成部１０５ａは、逆立体射影部１０４ａから取得した座標を基にして、ビット列を生成し、生成したビット列をハミング距離計算部１０７に出力する。
【００３９】
ビット列生成部１０５ｂは、逆立体射影部１０４ｂから取得する各座標を基にして、複数のビット列を生成し、生成した複数のビット列をビット列記憶部１０３に出力する。
【００４０】
配置部１０６は、（ｍ＋ｐ−１）次元の超球Ｓを横切る超平面をｎ個、超球Ｓに配置する処理部である。また、配置部１０６は、配置した結果を基にして変換規則を生成する。以下において、配置部１０６が各超平面の初期配置を特定する処理、配置部１０６が変換規則を生成する処理について順に説明する。
【００４１】
配置部１０６が、各超平面の初期配置を特定する処理について説明する。配置部１０６は、特徴量記憶部１０１から各特徴量ベクトルを取得し、各特徴量ベクトルの分散共分散行列の固有値の平方根を算出する。配置部１０６は、各固有値のうち、最大のものをσとして特定する。また、配置部１０６は、特定したσの方向を「ｖｅｃＮ」とする。
【００４２】
配置部１０６は、ｖｅｃＮ方向の三次モーメントを計算し、計算結果をνとする。例えば配置部１０６は、式（５）を基にして三次モーメントを計算する。式（５）において、ｘｉは、特徴量ベクトルのｉビット目に対応する。また、ｕは、特徴量ベクトルの１ビット目からｍビット目までの値の平均値に対応する。
【００４３】
【数４】
2015118464.tif 000006
【００４４】
続いて、配置部１０６は、特徴量ベクトルを主成分分析し、累積寄与率を算出する。例えば、配置部１０６は、主成分分析を行い、第１主成分から第Ｎ主成分の広がりを求める。配置部１０６は、各主成分の広がりを降順に並べ、広がりの大きいものから順に、σ１、σ２、・・・σＮとする。配置部１０６は、式（６）を基にして、λを算出する。また、配置部１０６は、式（７）を基にして、累積寄与率λｍを算出する。
【００４５】
【数５】
2015118464.tif 000007
【００４６】
【数６】
2015118464.tif 000008
【００４７】
配置部１０６は、横軸に成分の数「ｉ」、縦軸に対数累積寄与率「ｌｏｇλｍ」とするグラフに、ｉとｌｏｇλｍとの関係をプロットし、プロットした結果から近似直線を特定する。例えば、配置部１０６は、最小二乗法などを用いて近似直線を特定する。図６は、近似直線の一例を示す図である。配置部１０６は、近似直線の傾きを「γ＋１」として算出する。
【００４８】
配置部１０６は、超球Ｓの赤道の立体射影による像の円の半径をＲとする。図７は、超球Ｓの赤道の立体射影による像の円の半径の一例を示す図である。図７に示すように、超球Ｓの赤道ＳＥの立体射影による像の円は、ＶＡＡとなる。そして、円ＶＡＡの半径がＲとなる。
【００４９】
配置部１０６は、式（８）を基にしてｃ１を算出し、式（９）を基にしてｃ２を算出する。
【００５０】
ｃ１＝２／（１＋ｅｘｐ（σ／γ＋１）／Ｒ））−１・・・（８）
【００５１】
ｃ２＝ｓｇｎ（ν）｜ν｜１／３Ｒ・・・（９）
【００５２】
配置部１０６は、各超平面の共通交点の位置を超球Ｓの中心から第ｍ＋１次元方向にｃ１、ｖｅｃＮ方向にｃ２ずらした位置に設定する。また、配置部１０６は、ｎ個の法線ベクトルを多次元標準正規分布からサンプリングする。配置部１０６は、サンプリングした法線ベクトルを持ち、共通交点を通る超平面を、初期位置として設定する。
【００５３】
次に、配置部１０６が変換規則を生成する処理について説明する。配置部１０６は、超平面の法線ベクトルおよび超平面のオフセット量の情報を基にして、変換規則の情報を生成する。配置部１０６は、ｎ個の法線ベクトルを並べることで、ｎ×（ｍ＋１）行列の情報「Ｗ１１，Ｗ１２,・・・、Ｗｎ（ｍ＋１）」を生成する。例えば、式（３）のｎ×（ｍ＋１）行列の各行がそれぞれ、法線ベクトルに対応する。なお、配置部１０６は、ｎ×（ｍ＋１）行列の情報のうち、不足する次元の値には、ランダム値を割り当てる。また、配置部１０６は、オフセット座標を、ｎ×１の情報として生成する。
【００５４】
配置部１０６は、ｎ×（ｍ＋１）行列の情報およびｎ×１の情報を、ビット列生成部１０５に出力する。
【００５５】
ハミング距離計算部１０７は、ビット列生成部１０５ａから取得するビット列と、ビット列記憶部１０３に格納された各ビット列とのハミング距離を算出する処理部である。ハミング距離は、桁数の同じ２つの２進数を比較した場合の、異なる桁の個数である。以下の説明において、ビット列生成部１０５ａから取得するビット列をクエリビット列と表記する。
【００５６】
ハミング距離計算部１０７は、クエリビット列とビット列記憶部１０３の各ビット列とのハミング距離の算出結果を、類似ベクトル特定部１０８に出力する。
【００５７】
類似ベクトル特定部１０８は、ハミング距離計算部１０７のハミング距離の算出結果を取得し、クエリビット列とのハミング距離が近い順に、各ビット列に対して順位付けを行う。類似ベクトル特定部１０８は、順位付けした各ビット列のうち、上位のビット列を、クエリビット列に対応するビット列として出力しても良いし、順位付けの結果を出力しても良い。
【００５８】
次に、本実施例に係る検索装置１００の処理手順の一例について説明する。図８は、本実施例に係る検索装置の処理手順を示すフローチャートである。図８に示すように、検索装置１００の配置部１０６は、超平面の初期位置設定処理を実行する（ステップＳ１０１）。
【００５９】
検索装置１００の逆立体射影部１０４ａは、クエリの特徴量ベクトルを逆立体射影し、クエリビット列を生成する（ステップＳ１０２）。逆立体射影部１０４ｂは、特徴量記憶部１０１の各特徴量ベクトルを逆立体射影し、ビット列を生成する（ステップＳ１０３）。
【００６０】
検索装置１００のハミング距離計算部１０７が、クエリビット列とビット列記憶部１０３のビット列とのハミング距離を計算し、類似ベクトル特定部１０８が、クエリビット列に類似するビット列を特定する（ステップＳ１０４）。
【００６１】
次に、図８のステップＳ１０１に示した超平面の初期位置設定処理について説明する。図９は、超平面の初期位置設定処理の処理手順を示すフローチャートである。図９に示すように、配置部１０６は、特徴量ベクトルの分散共分散行列の固有値の最大値の平方根σｉを求め、その中で最大のものをσに設定する（ステップＳ２０１）。
【００６２】
配置部１０６は、σの方向をｖｅｃＮに設定する（ステップＳ２０２）。配置部１０６は、特徴量ベクトルを主成分分析し累積寄与率を算出する（ステップＳ２０３）。配置部１０６は、横軸に成分、縦軸に対数累積寄与率としてプロットした場合の近似直線を特定する（ステップＳ２０４）。
【００６３】
配置部１０６は、近似直線の傾きをγ＋１に設定する（ステップＳ２０５）。配置部１０６は、超球Ｓの赤道の立体射影による像の円の半径をＲに設定する（ステップＳ２０７）。
【００６４】
配置部１０６は、ｃ１およびｃ２を算出する（ステップＳ２０７）。ステップＳについて、配置部１０６は、式（８）および式（９）を基にして、ｃ１およびｃ２を算出する。
【００６５】
配置部１０６は、共通交点の位置ｃを、超球Ｓの中心から第ｍ＋１次元方向にｃ１、ｖｅｃＮ方向にｃ２ずらした位置とする（ステップＳ２０８）。
【００６６】
配置部１０６は、ｎ個の法線ベクトルを多次元標準正規分布からサンプリングする（ステップＳ２０９）。配置部１０６は、サンプリングした法線ベクトルを持ち、共通交点を通る超平面を、初期の超平面の位置として設定する（ステップＳ２１０）。
【００６７】
次に、本実施例に係る検索装置１００の効果について説明する。検索装置１００は、特徴量ベクトルを複数の超平面で分割した超球に逆立体射影してビット列を特定する場合に、各超平面の初期位置を各超平面の交点が超球Ｓ内に収まるように設定する。このように、各超平面の初期位置を各超平面の交点が超球内に収まるように設定することで、ワームホールの発生を防止し、これによって、大きく異なる特徴量ベクトル同士であっても、ハッシュベクトル変換後のハミング距離が小さくなるということが無くなる。従って、検索装置１００によれば、特徴量ベクトルを用いた類似検索を精度良く実行することができる。
【００６８】
図１０は、本実施例に係る検索装置の効果を説明するための図である。図１０に示す例では、超球Ｓの内側に、超平面１３ａ，１３ｂ，１３ｃの交点が存在している。そうすると、ワームホールが無くなり、図１５で説明したように、特徴量ベクトルが大きく離れているにも関わらず、同一のビット列を割り当ててしまうという問題を解消できる。
【００６９】
ところで、配置部１０６が、超平面の初期位置を設定する処理は、上記の処理に限られるものではない。以下では、配置部１０６が、超平面の初期位置を設定するその他の処理について説明する。
【００７０】
配置部１０６は、ｎ個の法線ベクトルとオフセットを標準正規分布からサンプリングし、サンプリングした法線ベクトルとオフセットとを基にして、ｎ個の超平面の配置を定める。配置部１０６は、ｎ個の超平面について、無限遠点に交点がある場合には、サンプリングを再度行い、ｎ個の超平面の配置を定める。
【００７１】
配置部１０６は、ｎ個の超平面について、無限遠点に交点がない場合には、全ての交点が超球Ｓの内部にあるか否かを判定する。配置部１０６は、全ての交点が超球Ｓの内部に無い場合には、ｎ個の超平面のオフセットを半分にし、再度、全ての交点が超球Ｓの内部にあるか否かを判定する。
【００７２】
配置部１０６は、全ての読点が超球Ｓの内部にある場合には、現在の各超平面の位置を初期位置として特定する。
【００７３】
図１１は、超平面のその他の初期位置設定処理の処理手順を示すフローチャートである。図１１に示すように、配置部１０６は、法線ベクトルとオフセットを標準正規分布からサンプリングし、超平面の配置を特定し（ステップＳ３０１）、無限遠点に交点があるか否かを判定する（ステップＳ３０２）。配置部１０６は、無限遠点に交点がある場合には（ステップＳ３０２，Ｙｅｓ）、ステップＳ３０１に移行する。
【００７４】
一方、配置部１０６は、無限遠点に交点がない場合には（ステップＳ３０２，Ｎｏ）、超平面による全ての交点が超球Ｓの内部に存在するか否かを判定する（ステップＳ３０３）。配置部１０６は、超平面による全ての交点が超球Ｓの内部に存在しない場合には（ステップＳ３０３，Ｎｏ）、全ての超平面のオフセットを１／２にして（ステップＳ３０４）、ステップＳ３０３に移行する。
【００７５】
一方、配置部１０６は、超平面による全ての交点が超球Ｓの内部に存在する場合には（ステップＳ３０３，Ｙｅｓ）、現在の超平面の位置を初期位置に設定する（ステップＳ３０５）。
【００７６】
このように、配置部１０６が、超平面の初期位置を特定することで、各超平面の交点が超球Ｓの内部に含まれるため、ワームホールの発生を防止し、これによって、大きく異なる特徴量ベクトル同士であっても、ハッシュベクトル変換後のハミング距離が小さくなるということが無くなる。従って、検索装置１００によれば、特徴量ベクトルを用いた類似検索を精度良く実行することができる。
【００７７】
ところで、上記実施例では、特徴量空間Ｖの次元よりも１大きい次元の空間に存在する超球Ｓに対して逆立体射影を実行する場合について説明したがこれに限定されるものではない。例えば、特徴量空間Ｖの次元よりも２以上大きい次元の空間に存在するｍ次元球に対して、逆立体射影する場合にも、同様に本願を適用することができる。
【００７８】
次に、上記実施例に示した検索装置１００と同様の機能を実現する画像処理装置を実行するコンピュータの一例について説明する。図１２は、空間分割プログラムを実行するコンピュータの一例を示す図である。
【００７９】
図１２に示すように、このコンピュータ２００は、各種演算処理を実行するＣＰＵ２０１と、ユーザからのデータの入力を受け付ける入力装置２０２と、ディスプレイ２０３を有する。また、コンピュータ２００は、記憶媒体からプログラム等を読取る読み取り装置２０４と、ネットワークを介して他のコンピュータとの間でデータの授受を行うインターフェース装置２０５とを有する。また、コンピュータ２００は、各種情報を一時記憶するＲＡＭ２０６と、ハードディスク装置２０７を有する。そして、各装置２０１〜２０７は、バス２０８に接続される。
【００８０】
ハードディスク装置２０７は、配置プログラム２０７ａを有する。ＣＰＵ２０１は、プログラム２０７ａを読み出してＲＡＭ２０６に展開する。配置プログラム２０７ａは、配置プロセス２０６ａとして機能する。例えば、配置プロセス２０６ａは、配置部１０６に対応する。
【００８１】
なお、配置プログラム２０７ａについては、必ずしも最初からハードディスク装置２０７に記憶させておかなくても良い。例えば、コンピュータ２００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」にプログラムを記憶させておく。そして、コンピュータ２００がこれらから配置プログラム２０７ａを読み出して実行するようにしてもよい。
【００８２】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００８３】
（付記１）コンピュータが実行する空間分割方法であって、
特徴量空間の次元よりも１次元以上大きい次元の空間に存在する球を分割する複数の超平面を配置した場合の各超平面の交点位置が前記球の内部にあるような交点位置を特定し、
設定した交点位置を通る複数の超平面を初期配置する
処理を実行することを特徴とする空間分割方法。
【００８４】
（付記２）前記特定する処理は、特徴量ベクトルのモーメントから定められる一点を前記交点位置として特定することを特徴とする付記１に記載の空間分割方法。
【００８５】
（付記３）前記特定する処理は、複数の超平面のオフセット量を調整して、前記球の内側に含まれる複数の超平面の交点位置を特定することを特徴とする付記１に記載の空間分割方法。
【００８６】
（付記４）特徴量空間の次元よりも１次元以上大きい次元の空間に存在する球を分割する複数の超平面を配置した場合の各超平面の交点位置が前記球の内部にあるような交点位置を特定し、設定した交点位置を通る複数の超平面を初期配置する配置部
を有することを特徴とする空間分割装置。
【００８７】
（付記５）前記配置部は、前記特定する処理は、特徴量ベクトルのモーメントから定められる一点を前記交点位置として特定することを特徴とする付記４に記載の空間分割装置。
【００８８】
（付記６）前記配置部は、複数の超平面のオフセット量を調整して、前記球の内側に含まれる複数の超平面の交点位置を特定することを特徴とする付記４に記載の空間分割装置。
【００８９】
（付記７）コンピュータに、
特徴量空間の次元よりも１次元以上大きい次元の空間に存在する球を分割する複数の超平面を配置した場合の各超平面の交点位置が前記球の内部にあるような交点位置を特定し、
設定した交点位置を通る複数の超平面を初期配置する
処理を実行させることを特徴とする空間分割プログラム。
【００９０】
（付記８）前記特定する処理は、特徴量ベクトルのモーメントから定められる一点を前記交点位置として特定することを特徴とする付記７に記載の空間分割プログラム。
【００９１】
（付記９）前記特定する処理は、複数の超平面のオフセット量を調整して、前記球の内側に含まれる複数の超平面の交点位置を特定することを特徴とする付記７に記載の空間分割プログラム。
【符号の説明】
【００９２】
１００  検索装置
１０４ａ，１０４ｂ  逆立体射影部
１０５ａ，１０５ｂ  ビット列生成部
１０６  配置部
１０７  ハミング距離計算部
１０８  類似ベクトル特定部
【図１】
2015118464.tif 000009
【図２】
2015118464.tif 000010
【図３】
2015118464.tif 000011
【図４】
2015118464.tif 000012
【図５】
2015118464.tif 000013
【図６】
2015118464.tif 000014
【図７】
2015118464.tif 000015
【図８】
2015118464.tif 000016
【図９】
2015118464.tif 000017
【図１０】
2015118464.tif 000018
【図１１】
2015118464.tif 000019
【図１２】
2015118464.tif 000020
【図１３】
2015118464.tif 000021
【図１４】
2015118464.tif 000022
【図１５】
2015118464.tif 000023
【手続補正書】
【提出日】平成26年10月30日(2014.10.30)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
しかしながら、従来技術では、ハッシュベクトルを用いた類似検索を精度良く実行できないという問題がある。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
【数１】
2015118464.tif 000024
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００４２
【補正方法】変更
【補正の内容】
【００４２】
配置部１０６は、ｖｅｃＮ方向の三次モーメントを計算し、計算結果をνとする。例えば配置部１０６は、式（５）を基にして三次モーメントを計算する。式（５）において、ｘｉ(k)は、ｋ番目の特徴量ベクトルのｉ成分に対応する。また、ｕは、特徴量ベクトルの平均ベクトルに対応する。Ｋは特徴量ベクトルの個数に対応する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００４３
【補正方法】変更
【補正の内容】
【００４３】
【数４】
2015118464.tif 000025
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００４５
【補正方法】変更
【補正の内容】
【００４５】
【数５】
2015118464.tif 000026
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００４６
【補正方法】変更
【補正の内容】
【００４６】
【数６】
2015118464.tif 000027
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
配置部１０６は、横軸に成分の数「ｉ」、縦軸に対数累積寄与率「ｌｏｇλｉ」とするグラフに、ｉとｌｏｇλｉとの関係をプロットし、プロットした結果から近似直線を特定する。例えば、配置部１０６は、最小二乗法などを用いて近似直線を特定する。図６は、近似直線の一例を示す図である。配置部１０６は、近似直線の傾きを「γ＋１」として算出する。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００５０
【補正方法】変更
【補正の内容】
【００５０】
ｃ１＝２／（１＋ｅｘｐ（σ／((γ＋１)Ｒ)））−１・・・（８）
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
ｃ２＝ｓｇｎ（ν）｜ν｜１／３／Ｒ・・・（９）
【手続補正１０】
【補正対象書類名】図面
【補正対象項目名】図６
【補正方法】変更
【補正の内容】
【図６】
2015118464.tif 000028