(57)【要約】【課題】少ないハードウェア資源を用いて高速な類似検索を実現する。【解決手段】  クライアント端末が、特徴量データと、特徴量データのうちのどれが代表データかを示す代表データ情報と、各代表データと各特徴量データの類似度或いは距離を示す距離テーブルとをデータベースに格納し、特徴量データの中から１つを選択する登録用特徴量選択部と、選択した特徴量データと、検索用特徴量との類似度或いは距離を算出する類似度算出部と、算出した類似度或いは距離に基づき、選択したデータと抽出した特徴量とが類似するかを判定する判定部と、判定部による判定結果に応じた処理を行なう処理部と、を備える。登録用特徴量選択部は、未登録用特徴量データのうちから、代表データと非代表データとを交互に、距離テーブルを用いて選択する。【選択図】  図１
2011034254.tif 000002
【特許請求の範囲】
【請求項１】
マルチメディアデータに類似するデータを検索する類似検索装置であって、
複数の登録用特徴量データを格納する記憶部と、
前記マルチメディアデータより抽出された検索用特徴量を取得する手段と、
前記複数の登録用特徴量データの中から、１つを選択する登録用特徴量選択部と、
選択した前記登録用特徴量データと、前記検索用特徴量との、特徴量空間における類似度或いは距離を算出する類似度算出部と、
算出した前記類似度或いは距離に基づき、前記選択した登録用特徴量データと前記検索用特徴量とが類似するか否かを判定する判定部と、
前記判定部による判定結果に応じた処理を行う処理部と、
を備え、
前記記憶部は、さらに、前記複数の登録用特徴量データのうち選択された代表データがどれであるかを示す代表データ情報と、各代表データと各登録用特徴量データの特徴量空間における類似度或いは距離を格納しており、
前記登録用特徴量選択部は、まだ選択されていない登録用特徴量データである未選択登録用特徴量データのうちから、前記代表データと、前記代表データ以外の前記登録用特徴量データである非代表データとを、それぞれ所定の数ごとに交互に、前記記憶部に格納された各代表データと各登録用特徴量データの特徴量空間における類似度或いは距離を用いて選択し、
前記判定部は、前記判定の結果、類似しない場合には、前記登録用特徴量選択部により登録用特徴量データを選択させ、前記類似度算出部により前記類似度或いは距離を算出させて、前記判定を行うという一連の処理を、類似判定がなされるか、あるいは前記登録用特徴量データ全てに対して判定がなされるまで繰り返すことを特徴とする類似検索装置。
【請求項２】
請求項１に記載の類似検索装置であって、
前記記憶部に格納された各代表データと各登録用特徴量データの特徴量空間における前記類似度或いは距離を用いて、前記検索用特徴量と、前記非代表データとの相関を第一の相関として算出する相関計算部を備え、
前記登録用特徴量選択部が、前記非代表データを選択する際には、算出した前記第一の相関に基づき選択することを特徴とする類似検索装置。
【請求項３】
請求項２に記載の類似検索装置であって、
前記相関計算部は、
前記検索用特徴量と前記代表データとの類似度或いは距離を表す距離ベクトルと、前記非代表データと前記代表データとの類似度或いは距離を表す距離ベクトルを用いて、前記第一の相関を算出することを特徴とする類似検索装置。
【請求項４】
請求項２または請求項３に記載の類似検索装置であって、
前記相関計算部が、前記検索用特徴量と、前記代表データとの相関を第二の相関として算出し、
前記登録用特徴量選択部が、前記代表データを選択する際には、算出した前記第二の相関に基づき選択することを特徴とする類似検索装置。
【請求項５】
請求項４に記載の類似検索装置であって、
前記相関計算部が、
前記検索用特徴量と、前記登録用特徴量選択部により既に選択された前記登録用特徴量データとの距離を表す距離ベクトルと、前記代表データと、前記既に選択された登録用特徴量データとの距離を表す距離ベクトルを用いて、前記第二の相関を算出することを特徴とする類似検索装置。
【請求項６】
請求項４に記載の類似検索装置であって、
前記相関計算部が、
前記検索用特徴量と、前記登録用特徴量選択部により既に選択された前記非代表データとの距離を表す距離ベクトルと、前記代表データと、前記既に選択された非代表データとの距離を表す距離ベクトルを用いて、前記第二の相関を算出することを特徴とする類似検索装置。
【請求項７】
請求項２または請求項３に記載の類似検索装置であって、
前記登録用特徴量選択部が、前記代表データを選択する際には、予め定められた所定の順序で選択することを特徴とする類似検索装置。
【請求項８】
請求項１ないし請求項７のいずれか１つに記載の類似検索装置であって、
前記判定部が、
前記類似度算出部が算出した、選択した前記登録用特徴量データと前記検索用特徴量との特徴量空間における類似度が、所定の閾値より大きい場合、或いは距離が、所定の閾値より小さい場合に、類似すると判定することを特徴とする類似検索装置。
【請求項９】
請求項８に記載の類似検索装置であって、
前記未選択登録用特徴量データについて、前記登録用特徴量選択部が選択した前記登録用特徴量データとの特徴量空間における類似度或いは距離と、
前記類似度算出部が算出した、選択した前記登録用特徴量データと前記検索用特徴量との特徴量空間における類似度或いは距離との差が、
所定の閾値より大きい場合に、
前記未選択登録用特徴量データを、前記特徴量選択部が類似検索の対象として選択しないものと決定する枝刈り部を備えることを特徴とする類似検索装置。
【請求項１０】
請求項１ないし請求項９のいずれか１つに記載の類似検索装置であって、
前記マルチメディアデータは、認証対象とするユーザの生体情報であることを特徴とする類似検索装置。
【請求項１１】
請求項１ないし請求項１０のいずれか１つに記載の類似検索装置であって、
前記検索用特徴量を取得する手段として、
前記マルチメディアデータを入力として受け付ける生データ取得部と、
入力として受け付けた前記マルチメディアデータから、特徴量を抽出する特徴量抽出部と、
を備えることを特徴とする類似検索装置。
【請求項１２】
請求項１ないし請求項１０のいずれか１つに記載の類似検索装置であって、
ネットワークを介して端末装置と接続されており、
前記端末装置が、
前記マルチメディアデータを入力として受け付ける生データ取得部と、
入力として受け付けた前記マルチメディアデータから、前記検索用特徴量を抽出する特徴量抽出部と、抽出した前記特徴量を前記装置に送信する手段と、
を備え、
前記類似検索装置が、前記端末装置よりネットワークを介して受信することによって前記特徴量を取得することを特徴とする類似検索装置。
【請求項１３】
請求項１ないし請求項１０のいずれか１つに記載の類似検索装置と、登録端末装置と、記憶部を備えるサーバ装置と、を備える類似検索システムであって、
前記登録端末装置が、
前記マルチメディアデータを入力として受け付ける手段と、
取得した前記マルチメディアデータより登録用特徴量データを抽出する手段と、
前記抽出した登録用特徴量データを前記サーバに送信する手段と、
を備え、
前記サーバ装置が、
受信した前記複数の登録用特徴量データの中から、複数の代表データを選択する手段と、
選択した前記複数の代表データがどれであるかを示す代表データ情報と、前記複数の登録用特徴量データとを、前記類似検索装置に送信する手段と、
を備えることを特徴とする類似検索システム。
【請求項１４】
請求項１３に記載の類似検索システムであって、
前記サーバ装置が、
各代表データと各登録用特徴量データの特徴量空間における類似度或いは距離を算出する手段と、
算出した前記類似度或いは距離を、前記類似検索装置に送信する手段と
を備えることを特徴とする類似検索システム。
【請求項１５】
マルチメディアデータに類似するデータを検索する類似検索方法であって、
前記マルチメディアデータより抽出された検索用特徴量を取得するステップと、
記憶部に格納された前記複数の登録用特徴量データの中から、１つを選択する登録用特徴量選択ステップと、
選択した前記登録用特徴量データと、前記検索用特徴量との、特徴量空間における類似度或いは距離を算出する類似度算出ステップと、
算出した前記類似度或いは距離に基づき、前記選択した登録用特徴量データと前記検索用特徴量とが類似するか否かを判定する判定ステップと、
前記判定部による判定結果に応じた処理を行う処理ステップと、
を備え、
前記登録用特徴量選択ステップにおいて、前記記憶部にさらに格納された、前記複数の登録用特徴量データのうち選択された代表データがどれであるかを示す代表データ情報と、各代表データと各登録用特徴量データの特徴量空間における類似度或いは距離とを用いて、まだ選択されていない登録用特徴量データである未選択登録用特徴量データのうちから、前記代表データと、前記代表データ以外の前記登録用特徴量データである非代表データとを、それぞれ所定の数ごとに交互に選択し、
前記判定ステップの判定の結果、類似しない場合には、前記登録用特徴量選択ステップ、前記類似度算出ステップ、および前記判定ステップを、類似判定がなされるか、あるいは前記登録用特徴量データ全てに対して判定がなされるまで繰り返すことを特徴とする類似検索方法。
【請求項１６】
コンピュータを、請求項１ないし請求項１４のいずれか１つに記載の装置の各手段として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチメディアデータに類似するデータを検索する技術に関する。
【背景技術】
【０００２】
デジタル化された画像、動画、音楽、文書などのマルチメディアデータに対して、それに類似するマルチメディアデータを検索することを類似検索と呼ぶ。類似検索は、一般には、抽出対象とするマルチメディアデータ（以後、生データ）から、類似度或いは距離の算出に用いられる、特徴量と呼ばれる情報を抽出し、特徴量同士の一致度合いを示す類似度が大きいもの、或いは、特徴量同士の不一致度合いを示す距離が小さいものを、類似すると見なすことにより行なわれる。
【０００３】
類似の定義としては、類似検索の用途によって、例えば、データベースなどに登録されたマルチメディアデータの中で、入力として受け付けたマルチメディアデータの特徴量との類似度が最も大きい特徴量を持つデータを、類似すると定義する場合や、類似度がある閾値より大きい特徴量を持つ、複数のデータについて、類似すると定義する場合などがある。
【０００４】
類似検索の対象としてデータベースなどに登録された特徴量（以後、登録用特徴量）の総数をＮとすると、全ての登録用特徴量に対して類似度を算出する場合、Ｎ回の類似度計算が必要である。一般に、類似度計算には大きな時間コストが必要とされるため、登録用特徴量数Ｎが増加すれば、それに比例して検索に時間がかかる。
【０００５】
これに対して、あらかじめ登録用特徴量同士の類似度を算出し、これを用いて効率的に登録用特徴量の探索を行なうことで、類似度を算出する回数を削減する技術が提案されている（特許文献１）。
【０００６】
特許文献１の段落００１１から段落００１７には、登録データを複数のグループに分類し、グループ毎に各登録データ同士の照合度（類似度）が記述された行列（以後、照合度テーブル）を用意しておき、検索時には、それらを用いて効率的に登録データの探索を行ない、照合度の計算回数を削減する技術が開示されている。
【０００７】
また、非特許文献１には、Ｎ個の登録用特徴量の中から、代表とする登録用特徴量（以後、ｐｉｖｏｔ）をＭ個選択し、各ｐｉｖｏｔと各登録用特徴量との、特徴量空間における距離を記述した行列（以後、距離テーブル）を用意しておき、これを用いて、最初は入力されたデータと各ｐｉｖｏｔとの距離を算出しながら、いくつかの登録用特徴量を選択対象から除外する枝刈りを行ない、距離を求める、或いは枝刈りを行なう、という処理が、全てのｐｉｖｏｔに対して施された後に、ｐｉｖｏｔ以外の登録用特徴量（以後、ｎｏｎ−ｐｉｖｏｔ）に対して、入力されたデータとの距離を求めることで、類似検索における距離の計算回数を削減する、ＬＡＥＳＡと呼ばれる技術が記載されている。
【０００８】
また、別の類似検索技術として、Ｎ個の登録データ同士の距離を記述したＮ×Ｎの行列を用意しておき、検索時には、それらを用いて効率的に登録データの探索及び枝刈りを行ない、距離の計算回数を削減する、ＡＥＳＡと呼ばれる技術が従来より提案されており、これらの類似検索技術についてサーベイが行われている（非特許文献２）。
【０００９】
非特許文献２のｐ．７８−８０には、ＡＥＳＡにおいて距離を算出する回数が登録データの総数Ｎに対して一定である、即ちＯ（１）であること、及び非特許文献１に記載のＬＡＥＳＡにおいて距離を算出する回数はＭ＋Ｏ（１）であることが記載されている。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開2007-286970号公報
【非特許文献】
【００１１】
【非特許文献１】Ｌ．Ｍｉｃｏ  ｅｔ  ａｌ．，  “Ａｎ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｆｉｎｄｉｎｇ  ｎｅａｒｅｓｔ  ｎｅｉｇｈｂｏｕｒｓ  ｉｎ  ｃｏｎｓｔａｎｔ  ａｖｅｒａｇｅ  ｔｉｍｅ  ｗｉｔｈ  ａ  ｌｉｎｅａｒ  ｓｐａｃｅ  ｃｏｍｐｌｅｘｉｔｙ，”  Ｐｒｏｃ．  ＩＣＰＲ  １９９２，  ｐｐ．５５７−５６０  （１９９２）
【非特許文献２】Ｐ．  Ｚｅｚｕｌａ  ｅｔ  ａｌ．，  Ｓｉｍｉｌａｒｉｔｙ  Ｓｅａｒｃｈ  −  Ｔｈｅ  Ｍｅｔｒｉｃ  Ｓｐａｃｅ  Ａｐｐｒｏａｃｈ，  Ｓｐｒｉｎｇｅｒ  （２００６）
【発明の概要】
【発明が解決しようとする課題】
【００１２】
特許文献１では、グループ数をＧとすると、照合度テーブルのサイズはＯ（Ｎ２／Ｇ）である。従って、もしグループ数Ｇを一定とすると、照合度テーブルのサイズはＯ（Ｎ２）となり、登録データ数Ｎの増加に伴って照合度テーブルのサイズが飛躍的に増加するため、大容量のハードウェア資源が必要になるという課題がある。
【００１３】
一方、照合度テーブルのサイズを抑えるためにグループ数Ｇを増加させた場合には、それに比例して照合度を算出する回数が増加する。特許文献１においてグループ数Ｇを１とすると、前述のＡＥＳＡにおいて、枝刈り処理を行なわない場合と等価である。枝刈り処理を行なわない場合には、算出を行う回数が増える可能性があるため、特許文献１においてグループ数Ｇを１とした場合、類似度を算出する回数はＯ（１）以上となる。
【００１４】
グループ数Ｇを増やすと、各グループの検索にそれぞれＯ（１）以上の回数の算出を行なうことになるため、合計ではＯ（Ｇ）以上の算出回数、すなわち検索時間がかかる。従って、例えば、登録用特徴量数Ｎの増加に比例してグループ数Ｇを増加させた場合、類似度テーブルのサイズはＯ（Ｎ）となり、ＡＥＳＡにおける距離テーブルのサイズと同じオーダーとなるが、類似度を算出する回数は、登録用特徴量数Ｎに比例して増加してしまうという課題がある。
【００１５】
また、非特許文献１に記載のＬＡＥＳＡにおいて距離を算出する回数はＭ＋Ｏ（１）であるため、登録用特徴量数Ｎが大きい場合、ＬＡＥＳＡにおける距離の算出回数は、特許文献１で登録用特徴量数Ｎに比例してグループ数Ｇを増加させた場合における類似度の算出回数と比べては、はるかに少ない。
【００１６】
しかしながら、非特許文献１に記載のＬＡＥＳＡでは、距離を求める、或いは枝刈りを行なう、という処理を、全てのｐｉｖｏｔに対して施してから、ｎｏｎ−ｐｉｖｏｔとの距離を求めている。この場合、類似する登録用特徴量がｎｏｎ−ｐｉｖｏｔであった場合、そのｎｏｎ−ｐｉｖｏｔとの距離を求めるために、全てのｐｉｖｏｔに対して距離を求めておく、或いは枝刈りを行なっておく必要があり、距離を算出する回数を削減する上では改良の余地があった。
【００１７】
企業により運営される類似画像検索サービスなど、大規模な類似検索システムにおいては、登録用特徴量数Ｎが膨大になることが考えられる。また、例えば入退室管理のための生体認証などにおいては、限られたハードウェア資源を用いて、かつ短時間で類似検索を行なうことが要求される。
【００１８】
したがって、必要なハードウェア資源を削減し、かつ検索時間の短縮を実現する類似検索技術の提供が望まれている。
【課題を解決するための手段】
【００１９】
本発明は、マルチメディアデータに類似するデータを検索する類似検索装置であって、複数の登録用特徴量データを格納する記憶部と、マルチメディアデータより抽出された特徴量を取得する手段と、複数の登録用特徴量データの中から、１つを選択する登録用特徴量選択部と、選択した登録用特徴量データと、抽出した特徴量との、特徴量空間における類似度或いは距離を算出する類似度算出部と、算出した類似度或いは距離に基づき、選択した登録用特徴量データと抽出した特徴量とが類似するか否かを判定する判定部と、判定部による判定結果に応じた処理を行なう処理部と、を備える。
【００２０】
記憶部は、さらに、複数の登録用特徴量データのうち、ｐｉｖｏｔ（代表データ）がどれであるかを示す代表データ情報と、各ｐｉｖｏｔと各登録用特徴量データの特徴量空間における類似度或いは距離を格納しており、登録用特徴量選択部は、まだ選択していない登録用特徴量データのうちから、ｐｉｖｏｔとｎｏｎ−ｐｉｖｏｔ（非代表データ）とを、それぞれ所定の数ごとに交互に、記憶部に格納された各ｐｉｖｏｔと各登録用特徴量データの特徴量空間における類似度或いは距離を用いて選択し、判定部による判定の結果、類似しない場合には、判定部が、登録用特徴量選択部により登録用特徴量データを選択させ、類似度算出部により類似度或いは距離を算出させて、判定を行うという一連の処理を、類似判定がなされるか、あるいは登録用特徴量データ全てに対して判定がなされるまで繰り返すことを特徴とする。
【発明の効果】
【００２１】
本発明によれば、少ないハードウェア資源を用いて、高速な類似検索が可能である。
【図面の簡単な説明】
【００２２】
【図１】本発明の第一の実施形態の機能構成を例示するブロック図である。
【図２】本発明の第一、第二、第三の実施形態のハードウェア構成を例示するブロック図である。
【図３】本発明の第一、第二の実施形態の登録処理を例示するフロー図である。
【図４】本発明の第一の実施形態の事前処理を例示するフロー図である。
【図５】本発明の第一の実施形態の検索処理を例示するフロー図である。
【図６（ａ）】距離が対称性を満たす場合の距離テーブルを例示する概略図である。
【図６（ｂ）】距離が対称性を満たさない場合の距離テーブルを例示する概略図である。
【図７】ｑ−ｅ間距離ベクトルとｐ−ｅ間距離ベクトルを例示する概略図である。
【図８】ｑ−ｐ間距離ベクトルとｎ−ｐ間距離ベクトルを例示する概略図である。
【図９】本発明の第二の実施形態の機能構成を例示するブロック図である。
【図１０】本発明の第二、第三の実施形態の事前処理を例示するフロー図である。
【図１１】本発明の第二の実施形態の検索処理を例示するフロー図である。
【図１２】本発明の第三の実施形態の機能構成を例示するブロック図である。
【図１３】本発明の第三の実施形態の検索処理を例示するフロー図である。
【発明を実施するための形態】
【００２３】
以下に、図面を用いて実施形態について詳細に説明する。
【実施例１】
【００２４】
以下、図面を参照して、１つ目の実施形態について説明する。本実施形態の類似検索システムは、認証を試みるユーザ（以後、認証ユーザ）がクライアント端末に生体情報を入力し、システムがクライアント端末内のデータベースから類似する生体情報データを検索することで、認証ユーザがデータベースに登録されているユーザ（以後、登録ユーザ）のうち誰であるか（或いは誰でもないか）を識別し、その結果に基づいて認証を行なう生体認証システムである。
【００２５】
特徴量の類似度としては、例えば特徴量空間における距離（非類似度）に−１をかけたものを用いる方法がある。以降、「距離」とは特徴量空間における距離を意味する。また、２つの特徴量が類似しているか否かの判定基準として、類似度ではなく距離そのものを用いても良い。この場合、類似度を用いる場合と大小関係が逆になり、距離が小さいものを類似すると見なすことになる。
【００２６】
クライアント端末が、データベースに登録された登録用特徴量データのうち、ｐｉｖｏｔがどれであるかを示すｐｉｖｏｔ情報と、各ｐｉｖｏｔと各登録用特徴量データの特徴量空間における距離を示す距離テーブルとを備え、ｐｉｖｏｔとｎｏｎ−ｐｉｖｏｔとを、それぞれ所定の数ごとに交互に、距離テーブルを用いて選択して、入力された生体情報データに類似するデータを検索する。
【００２７】
これにより、メモリやＨＤＤの容量が制限される場合にも、多数の登録用特徴量データを対象とした高速な類似検索を可能とする。
【００２８】
また、入力された生体情報データより抽出した特徴量（以後、検索用特徴量）との距離を算出する登録用特徴量データは、距離テーブルを用いて算出した特徴量同士の相関の大きさに基づいて選択する。
【００２９】
図１に、本実施形態の類似検索システムの構成例を示す。本実施形態では、生データはデジタル化された生体情報である。
このシステムは、ユーザから取得した登録情報をサーバ端末へ送信する登録端末１００と、登録情報を保存するサーバ端末２００と、ユーザが入力した検索用の生データを基に類似検索を行なうクライアント端末３００と、ネットワーク４００とを備える。クライアント端末は１台でも良いし、複数台存在しても良い。ネットワーク４００は、ＷＡＮやＬＡＮなどのネットワーク、ＵＳＢやＩＥＥＥ１３９４などを用いた機器間の通信、あるいは携帯電話網やＢｌｕｅＴｏｏｔｈ（登録商標）などの無線通信を用いても良い。
【００３０】
例えば、企業内の入退室管理システムの場合、登録端末１００は登録センター（登録用に確保された居室など）内に置かれたＰＣと生体情報入力センサ、クライアント端末３００は居室のドア付近に設置されたドアコントローラと生体情報入力センサ、サーバ端末２００はサーバ室に置かれたサーバ、ネットワーク４００は社内イントラネットとする構成が考えられる。また、企業内の勤怠管理システムの場合、登録端末１００は登録センター内に置かれたＰＣと生体情報入力センサ、クライアント端末３００は居室に設置されたＰＣと生体情報入力センサ、サーバ端末２００はサーバ室に置かれたサーバ、ネットワーク４００は社内イントラネットとする構成が考えられる。
【００３１】
これらの例においては、後述するグループＩＤ２１０及びグループＩＤ３１０は居室毎に異なる値となるように設定しても良い。このようにグループ分けすることで、１グループにおける登録用特徴量数Ｎを少なくすることができ、その分、距離を算出する回数を削減することができ、より高速な検索が可能となる。また、グループＩＤ２１０及びグループＩＤ３１０は無くても良い。
【００３２】
登録端末１００は、グループＩＤや登録データＩＤを取得するＩＤ取得部１０１と、生データを取得する生データ取得部１０２と、登録用の生データから登録用の特徴量を抽出する特徴量抽出部１０３と、通信Ｉ／Ｆ１０４とを備える。ＩＤ取得部１０１は、キーボードなどを用いて実現される。生データ取得部１０２は、本実施形態においては生体情報入力センサを用いて実現される。取得する生体情報の種類としては、指紋、虹彩、声紋、静脈などが考えられる。特徴量抽出部１０３は、サーバ端末２００側にあっても良い。抽出する特徴量としては、例えば指紋の場合であれば、指紋画像より抽出する、指紋の隆線の端点および分岐点であるマニューシャ、虹彩の場合であれば、虹彩画像から作成するアイリスコード（虹彩コード）と呼ばれるビット列などが考えられる。
【００３３】
サーバ端末２００は、グループＩＤ２１０毎にＮ個の登録情報２２０の中からＭ個のｐｉｖｏｔを決定するｐｉｖｏｔ決定部２０１と、グループＩＤ２１０毎に各ｐｉｖｏｔの特徴量と各登録用特徴量データの特徴量間の距離を算出する距離テーブル作成部２０２と、通信Ｉ／Ｆ２０３と、データベース２０４とを備える。登録用特徴量数Ｎ及びｐｉｖｏｔ数ＭはグループＩＤ２１０毎に異なっていても良い。また、２つの特徴量間の距離としては、例えばマニューシャを特徴量とした場合は、各特徴点の位置と隆線の方向を用いて照合を行なうマニューシャ・マッチング方式によって求めた距離、アイリスコードを特徴量とした場合は、コード間のハミング距離などが考えられる。
【００３４】
データベース２０４は、グループＩＤ２１０毎にマスタデータ２０５を保持する。グループＩＤ２１０は、ユーザが出入りする居室のＩＤとするなどの方法が考えられる。マスタデータ２０５は、グループＩＤ２１０と、各登録ユーザの登録情報２２０と、補助情報２３０とを含む。登録情報２２０は、登録データＩＤ２２１と、生データ２２２と、特徴量データ２２３とを含む。登録データＩＤ２２１は、ユーザの従業員番号とするなどの方法が考えられる。
【００３５】
また、生データ２２２は無くても良い。但し、生データ２２２があれば、特徴量抽出部１０３がバージョンアップされた場合に、生データ２２２から最新の特徴量を抽出できるため、生データの再登録をしなくて済むというメリットがある。補助情報２３０は、登録情報２２０の特徴量データ２２３のうちどれがｐｉｖｏｔであるかが記されたｐｉｖｏｔ情報２３１と、各ｐｉｖｏｔと各登録情報２２０の特徴量データ２２３間の距離が記された距離テーブル２３２とを含んで構成される。
【００３６】
クライアント端末３００は、生データを取得する生データ取得部３０１と、検索用の生データから検索用の特徴量を抽出する特徴量抽出部３０２と、検索用特徴量とｐｉｖｏｔとの相関を計算する検索用特徴量−ｐｉｖｏｔ間相関計算部３０３と、検索用特徴量とｎｏｎ−ｐｉｖｏｔとの相関を計算する検索用特徴量−ｎｏｎ−ｐｉｖｏｔ間相関計算部３０４と、検索用特徴量との距離を算出する登録情報３２０を選択する登録用特徴量選択部３０５と、検索用特徴量と登録情報３２０の特徴量データ３２３との距離を算出する類似度算出部３０６と、算出した距離を基に選択した登録情報３２０の特徴量データ３２３が検索用特徴量に類似しているかなどを判定する判定部３０７と、まだ検索用特徴量との距離を求めておらず、枝刈りもされていないｐｉｖｏｔ及びｎｏｎ−ｐｉｖｏｔに対して、枝刈り処理を行なう枝刈り部３０７ａと、通信Ｉ／Ｆ３０８と、データベース３０９とを備える。
【００３７】
相関計算部３０３、３０４による相関の計算は、以下の距離ベクトルについて行なう。検索用特徴量と、探索済みの全登録用特徴量データとの距離で構成されるベクトルを「ｑ−ｅ間距離ベクトル」、ｐｉｖｏｔと、探索済み全登録用特徴量データとの距離で構成されるベクトルを「ｐ−ｅ間距離ベクトル」、検索用特徴量と、探索済みの全ｐｉｖｏｔとの距離で構成されるベクトルを「ｑ−ｐ間距離ベクトル」、ｎｏｎ−ｐｉｖｏｔと、探索済みの全ｐｉｖｏｔとの距離で構成されるベクトルを「ｎ−ｐ間距離ベクトル」と定義する。上記以外の他のベクトルとして定義したものを用いても良い。
【００３８】
検索用特徴量−ｐｉｖｏｔ間相関計算部３０３は、ｑ−ｅ間距離ベクトルとｐ−ｅ間距離ベクトルとの相関を、検索用特徴量−ｎｏｎ−ｐｉｖｏｔ間相関計算部３０４は、ｑ−ｐ間距離ベクトルとｎ−ｐ間距離ベクトルとの相関をそれぞれ計算する。相関の計算の詳細については後述する。検索用特徴量−ｐｉｖｏｔ間相関計算部３０３、及び枝刈り部３０７ａは無くても良い。
【００３９】
データベース３０９は、グループＩＤ３１０と、各登録ユーザの登録情報３２０と、補助情報３３０とを含む。登録情報３２０は、登録データＩＤ３２１と、生データ３２２と、特徴量データ３２３とを含む。生データ３２２は無くても良い。補助情報３３０は、登録情報３２０の特徴量データ３２３のうちどれがｐｉｖｏｔであるかが記されたｐｉｖｏｔ情報３３１と、各ｐｉｖｏｔと各登録情報３２０の特徴量データ３２３間の距離が記された距離テーブル３３２とを含む。
【００４０】
登録情報３２０及び補助情報３３０は、同一のグループＩＤを持つサーバ端末２００のマスタデータ２０５の登録情報２２０及び補助情報２３０と同一のものである。例えば、入退室管理システムであって、クライアント端末３００が居室のドア付近に設置されている場合には、クライアント端末３００に、その居室を示すグループＩＤ２１０が紐付けられており、同一のグループＩＤを持つ登録情報及び補助情報を、サーバ端末２００より取得することが考えられる。このような構成をとることにより、入退室を許可するユーザを、居室ごとに管理することができる。また、各クライアント端末３００は、システムに登録されているデータのうち、自身が認証する対象のデータのみを格納するため、より少ない容量のＨＤＤおよびメモリを備える装置で実現できる。
【００４１】
登録情報３２０及び補助情報３３０は、例えば、クライアント端末３００が、システムがユーザにより利用されない夜間に、通信Ｉ／Ｆ３０８によりネットワークを介してサーバ端末２００よりダウンロードすることにより取得する。
【００４２】
また、上記の機能部以外に、判定部３０７の判定結果に基づいて、システムの用途に応じた処理を行なう処理部を備える。例えば入退室管理システムであって、クライアント端末３００がドアコントローラを含む場合には、判定部３０７の判定結果に基づいて、ドアのロックを制御する処理部を備える。また、勤怠管理システムであって、クライアント端末３００がＰＣを含む場合には、判定部３０７の判定結果に応じて、類似すると判定された特徴量データ３２３に紐付けられた登録データＩＤを、認証を行なった時刻とともにログとしてデータベースに記録する処理部などを備える。
【００４３】
図２に、本実施形態における登録端末１００、サーバ端末２００、クライアント端末３００のハードウェア構成を示す。これらの端末は、ＣＰＵ５００と、メモリ５０１と、ＨＤＤ５０２と、入力装置５０３と、出力装置５０４と、通信装置５０５と、可搬性のある記憶媒体５０７の読取装置５０６を備える構成とすることができる。
【００４４】
登録端末１００の入力装置５０３は、例えばキーボードおよび生体情報入力センサであり、出力装置５０４はディスプレイである。サーバ端末２００の入力装置５０３は、例えばキーボードであり、出力装置５０４は同様にディスプレイである。クライアント端末３００の入力装置５０３は、例えばキーボードおよび生体情報入力センサであり、出力装置５０４はディスプレイである。
【００４５】
前述した、登録端末１００、サーバ端末２００、およびクライアント端末３００が備える各機能部は、ＣＰＵ５００が、例えばＨＤＤ５０２からメモリ５０１に読み出して実行する各プログラムによって実現される。各プログラムは、あらかじめ、各端末内のＨＤＤ５０２に格納されていても良いし、必要に応じ、各端末が利用可能な媒体を介して、他の装置からＨＤＤ５０２に導入されてもよい。媒体とは、例えば、読取装置５０６に着脱可能な記憶媒体５０７、または、ネットワークや、ネットワークを伝搬する搬送波やデジタル信号などの通信媒体を指す。
【００４６】
図３に、本実施形態における登録の処理手順およびデータの流れを示す。以下に示す登録処理は、登録端末１００のＣＰＵ５００が、ＨＤＤ５０２からメモリ５０１に読み出して実行するプログラムによって実現される。そしてこのプログラムは、以下に説明される各種の動作を行うためのコードから構成されている。
【００４７】
まず登録端末１００のＩＤ取得部１０１が、ユーザ操作によりグループＩＤ及び登録データＩＤを入力として受け付ける（ステップＳ１０１）。
登録端末１００の生データ取得部１０２が、ユーザ操作により登録用の生データを取得する（ステップＳ１０２）。
登録端末１００の特徴量抽出部１０３が、登録用の生データから登録用の特徴量を抽出する（ステップＳ１０３）。
登録端末１００は、グループＩＤ、登録データＩＤ、登録用の生データ、および抽出した登録用特徴量データを、通信Ｉ／Ｆ１０４によりネットワーク４００を介してサーバ端末２００に送信する（ステップＳ１０４）。
サーバ端末２００は、登録端末１００から受信したグループＩＤと同一のグループＩＤ２１０を持つマスタデータ２０５に、受信した登録データＩＤ、登録用の生データ、および登録用特徴量データを、登録情報２２０として追加する（ステップＳ１０５）。
【００４８】
特徴量抽出部１０３をサーバ端末２００が備える場合は、ステップＳ１０４ではクライアント端末３００は登録ＩＤおよび生データのみを送信し、受信したサーバ端末２００の特徴量抽出部１０３が、ステップＳ１０３の特徴量抽出処理を行なえば良い。
【００４９】
図４に、本実施形態における事前処理の処理手順およびデータの流れを示す。本処理は、登録処理を行なってから検索処理を行なうまでの間に行なう。例えば、登録を行なった日の夜間に行なう、などの方法が考えられる。以下に示す事前処理は、サーバ端末２００のＣＰＵ５００が、ＨＤＤ５０２からメモリ５０１に読み出して実行するプログラムによって実現される。そしてこのプログラムは、以下に説明される各種の動作を行うためのコードから構成されている。
【００５０】
サーバ端末２００のデータベース２０４において、グループＩＤ２１０毎に、前回の事前処理の実行時以降で、登録情報２２０が追加されたマスタデータ２０５があれば、ｐｉｖｏｔ決定部２０１が、そのマスタデータ２０５中のＮ個の登録情報２２０の特徴量データ２２３の中から、Ｍ個をｐｉｖｏｔとして選択する処理を行なう（ステップＳ２０１）。Ｍの値は、たとえばシステムの管理者の操作などにより予め設定されている。ｐｉｖｏｔの決定方法の詳細は後述する。
【００５１】
サーバ端末２００の距離テーブル作成部２０２は、ｐｉｖｏｔ決定部２０１により決定された各ｐｉｖｏｔと、同一マスタデータ２０５内の各登録情報２２０の特徴量データ２２３との距離を算出し、距離テーブルを作成する（ステップＳ２０２）。
【００５２】
図６(a),(b)に距離テーブルの例を示す。ここで、Ｘ１、Ｘ２、・・・、ＸＭはｐｉｖｏｔ、Ｙ１、Ｙ２、・・・、ＹＮ−Ｍはｎｏｎ−ｐｉｖｏｔを表す。例えば、図６(b)では、Ｘ２からＹ１への距離ｄ（Ｘ２，Ｙ１）＝２５、Ｙ１からＸ２への距離ｄ（Ｙ１，Ｘ２）＝２７となっている。距離が対称性を満たす場合（即ち、ｄ（Ａ，Ｂ）＝ｄ（Ｂ，Ａ）の場合）は、図６(a)のようにどちらか一方の距離情報を記憶しておけばよい。逆に対称性を満たさない場合は、図６(b)のように両方の距離情報を記憶しておく。対称性を満たす距離の例としては、ハミング距離などが挙げられる。対称性を満たさない距離の例としては、マニューシャ・マッチング方式によって求めた距離などが挙げられる。
【００５３】
本実施形態の類似検索システムでは、距離テーブル中の要素数は、非対称の距離尺度を用いる場合は２ＭＮ−Ｍ（Ｍ−１）個、対称の距離尺度を用いる場合にはＭＮ−Ｍ（Ｍ−１）／２個であり、どちらの場合においても距離テーブルのサイズはＯ（Ｎ）と小さい。従って、登録用特徴量数Ｎの上昇に伴う距離テーブルのサイズの増加を抑えることができ、データベースの容量及び必要なメモリの空き容量を削減できるという効果が得られる。
【００５４】
例えば入退室管理システムなどの場合、クライアント端末３００にあたるドアコントローラは、一般にメモリやＨＤＤの容量などが非常に制限されるため、本実施形態の適用が特に有用であると考えられる。
【００５５】
サーバ端末２００のｐｉｖｏｔ決定部２０１および距離テーブル作成部２０２は、ステップＳ２０１で決定したＭ個のｐｉｖｏｔに関するｐｉｖｏｔ情報（登録情報２２０の特徴量データ２２３のうちどれがｐｉｖｏｔであるか）と、ステップＳ２０２で求めた距離テーブルとを、それぞれマスタデータ２０５の補助情報２３０に上書きで保存する（ステップＳ２０３）。
【００５６】
クライアント端末３００は、サーバ端末２００にグループＩＤ３１０を送信し、送信したグループＩＤと同一のグループＩＤ２１０を持つマスタデータ２０５の登録情報２２０と補助情報２３０をサーバ端末２００から受信する。受信したデータはデータベース３０９に登録情報３２０と補助情報３３０として保存する（ステップＳ２０４）。
【００５７】
図５に、本実施形態における検索の処理手順およびデータの流れを示す。以下に示す検索処理は、サーバ端末２００のＣＰＵ５００が、ＨＤＤ５０２からメモリ５０１に読み出して実行するプログラムによって実現される。そしてこのプログラムは、以下に説明される各種の動作を行うためのコードから構成されている。また、以下は一実施形態であり、検索の処理手順はこれに限定されるものではない。
クライアント端末３００のＣＰＵ５００が、データベース３０９から登録情報３２０と補助情報３３０を読み出し、メモリ５０１に展開する（ステップＳ３０１）。
クライアント端末３００の生データ取得部３０１が、ユーザから検索用の生データを取得する（ステップＳ３０２）。
クライアント端末３００の特徴量抽出部３０２が、検索用の生データから検索用特徴量を抽出する（ステップＳ３０３）。
クライアント端末３００の判定部３０７が、距離算出回数ｉを０に、されていないｐｉｖｏｔ数Ｍ’をＭに、それぞれ初期化する（ステップＳ３０４）。ここで判定部３０７は、距離算出回数ｉが２Ｍ’未満であればステップＳ３０６に、２Ｍ’以上であればステップＳ３１０に進む（ステップＳ３０５）。
【００５８】
ステップＳ３０６では、距離算出回数ｉが偶数であればステップＳ３０７に、奇数であればステップＳ３０９に進む。
ステップＳ３０７では、ｐｉｖｏｔの中から１つを選択するために、クライアント端末３００の検索用特徴量−ｐｉｖｏｔ間相関計算部が、ｑ−ｅ間距離ベクトルと、まだ検索用特徴量との距離を求めておらず、枝刈りもされていない各ｐｉｖｏｔにおけるｐ−ｅ間距離ベクトルとの相関を計算する。ｑ−ｅ間距離ベクトルとｐ−ｅ間距離ベクトルとの相関の計算方法の詳細は後述する。また、このステップは実行しなくても良い。
【００５９】
クライアント端末３００の登録用特徴量選択部３０５は、まだ距離を求めておらず、枝刈りもされていないｐｉｖｏｔのうち、ステップＳ３０７で計算した相関が最も大きいデータを、距離を算出する対象として選択する（ステップＳ３０８）。ステップＳ３０７を実行しない場合は、本検索処理前にあらかじめ定めておいた順序に従って、ｐｉｖｏｔを選択する。ｐｉｖｏｔの選択順序は、例えば擬似乱数生成器を用いてランダムに決定する方法がある。この順序はデータベース２０４のマスタデータ２０５に保持させておき、ステップＳ２０４でクライアント端末３００がその他の情報とともに受信、保存して、ステップＳ３０１においてデータベース３０９より読み出すようにすれば良い。
【００６０】
一方、ステップＳ３０９では、ｎｏｎ−ｐｉｖｏｔの中から１つを選択するために、クライアント端末３００の検索用特徴量−ｎｏｎ−ｐｉｖｏｔ間相関計算部が、ｑ−ｐ間距離ベクトルと、まだ距離を求めておらず、枝刈りもされていない各ｎｏｎ−ｐｉｖｏｔにおけるｎ−ｐ間距離ベクトルとの相関を計算する。ｑ−ｐ間距離ベクトルとｎ−ｐ間距離ベクトルとの相関の計算方法の詳細は後述する。
【００６１】
クライアント端末３００の登録用特徴量選択部３０５は、まだ距離を求めておらず、枝刈りもされていないｎｏｎ−ｐｉｖｏｔのうち、ステップＳ３０９で計算した相関が最も大きいデータを、距離を算出する対象として選択する（ステップＳ３１０）。
【００６２】
クライアント端末３００の判定部３０７は、距離算出回数ｉを１増やす（ステップＳ３１１）。
クライアント端末３００の類似度算出部３０６は、検索用の特徴量（Ｑとする）と選択した登録情報３２０の特徴量データ３２３（Ｚｉとする）との距離ｄ（Ｑ，Ｚｉ）を算出する（ステップＳ３１２）。
ステップＳ３１３では、クライアント端末３００の判定部３０７が、ステップＳ３１２で算出した距離ｄ（Ｑ，Ｚｉ）が所定の閾値τより小さければ、類似すると判定し、ステップＳ３１４に進む。閾値τ以上であれば、類似しないと判定し、ステップＳ３１５に進む。
【００６３】
類似すると判定した場合、クライアント端末３００は、検索用特徴量に類似する登録用特徴量データ３２３を持つ登録情報３２０を発見した場合の処理を行なう（ステップＳ３１４）。
【００６４】
生体認証の用途に応じて、この登録情報３２０を検索結果として検索終了としても良いし、あるいはステップＳ３０５に戻って、他の登録情報３２０の検索を引き続き行なっても良い。前者の手法は、類似する登録情報３２０が存在するか否かをできる限り短時間で判定したい場合において有効である。後者の手法は、類似すると判定した登録情報３２０全て出力したい場合や、最も類似する登録情報３２０を検索したい場合などにおいて有効である。
【００６５】
例えば、認証ユーザがデータベースに登録されているか否かをチェックすることを目的とした入退室管理システムの場合には、このステップの時点で検索終了とし、ロックされていた居室のドアをアンロックする処理が考えられる。また、認証ユーザが誰なのかを出来る限り正確に把握することを目的とした勤怠管理システムの場合には、判定結果をメモリ５０１に保存し、ステップＳ３０５に戻って他の登録情報３２０の検索を引き続き行なう方法が考えられる。
【００６６】
ステップＳ３１３において判定部３０７が類似しないと判定した場合、クライアント端末３００の枝刈り部３０７ａは、まだ距離を求めておらず、枝刈りもされていないｐｉｖｏｔ及びｎｏｎ−ｐｉｖｏｔに対して、枝刈り処理を行なう（ステップＳ３１５）。枝刈り処理の詳細は後述する。また、このステップは実行しなくても良い。
【００６７】
クライアント端末３００の判定部３０７が、距離算出回数ｉを参照し、距離算出回数ｉが距離算出回数の上限値ｉｍａｘであればステップＳ３１７に進み、ｉｍａｘでなければステップＳ３０５に戻る（ステップＳ３１６）。本実施形態では、距離算出回数はｉｍａｘを超えることがないので、ｉｍａｘの設定によって検索時間の最悪値（最大値）が決まる。従って、システムに応じて、検索にかけることができる時間の条件を満たすよう、検索前にあらかじめシステム管理者がｉｍａｘの値を設定しておく。
【００６８】
検索を終了するとしてステップＳ３１７に進んだ場合は、クライアント端末３００は、検索終了時の処理を行なう。検索用の特徴量に類似する登録用の特徴量データ３２３を持つ登録情報３２０が見つからなかった場合には、検索失敗時の処理を行なう。例えば、入退室管理システムの場合、入退室を認められたユーザではないとして、ドアをロックしたままにすることが考えられる。勤怠管理システムの場合は、ユーザに生体情報の再入力を促すメッセージを、出力装置５０４に出力することが考えられる。
【００６９】
類似する（１つ以上の）登録情報３２０が見つかった場合は、認証システムの用途に応じて、複数の登録情報３２０を検索結果としてもよいし、その中で最も小さい距離を実現した登録情報３２０のみを検索結果としてもよい。例えば、勤怠管理システムの場合、類似すると判定した複数の登録情報３２０の登録データＩＤ３２１を出力装置５０４に出力し、その中から正しいものを認証ユーザに選択させ、選択を入力として受け付けた登録データＩＤ３２１を、現在時刻と共にログとしてデータベース３０９（あるいは２０４）に保存する、といった処理が考えられる。或いは、類似する登録情報３２０の中で最も小さい距離を実現した登録情報３２０の登録データＩＤ３２１を、現在時刻と共にログとして保存するようにしても良い。検索終了時の処理については、システムの用途に応じた処理を行なう処理部を備える。
【００７０】
このように、本実施形態の類似検索システムでは、ステップＳ３０５〜ステップＳ３１０に記されているように、まずｐｉｖｏｔとｎｏｎ−ｐｉｖｏｔとを交互に選択し、ｐｉｖｏｔに対して、距離を求める、或いは枝刈りを行なう、という処理が施された後に、まだ枝刈りされていないｎｏｎ−ｐｉｖｏｔの距離を求める。このような手法をとることで、ｎｏｎ−ｐｉｖｏｔの距離を求めるために、全てのｐｉｖｏｔに対して距離を求めておく、或いは枝刈りを行なっておく必要がなくなるため、距離を算出する回数が削減され、より高速な検索を可能にするという効果が得られる。
【００７１】
また、本実施形態は、ｐｉｖｏｔとｎｏｎ−ｐｉｖｏｔとを、１つずつ交互に選択することとしたが、選択のルールはこれに限らず、例えばそれぞれ所定の数ずつ交互に選択することとしても良い。例えば、それぞれ２つずつ交互に選択するのであれば、ステップＳ３０６ではｉの値を４で割った余りによって、０または１であればｐｉｖｏｔを選択、２または３であればｎｏｎ−ｐｉｖｏｔを選択するなどとすればよい。また、ｐｉｖｏｔを１つ選んだ後にｎｏｎ−ｐｉｖｏｔを２つ選ぶとする場合には、ステップＳ３０５においてはｉ＜３Ｍ’であるかを判定し、ステップＳ３０６では、ｉの値を３で割った余りによって、０であればｐｉｖｏｔを選択、１または２であればｎｏｎ−ｐｉｖｏｔを選択する、などの手法を適宜用いればよい。
【００７２】
以下、ｐｉｖｏｔの決定方法について、その詳細を述べる。ｐｉｖｏｔの決定は、非特許文献１記載の手法を踏襲する。即ち、以下のようにｐｉｖｏｔを決定する。以下の処理は、サーバ端末２００のｐｉｖｏｔ決定部が行なう。すなわち、サーバ端末２００のＣＰＵ５００が、ＨＤＤ５０２からメモリ５０１に読み出して実行するプログラムによって実現される。そしてこのプログラムは、以下に説明される各種の動作を行うためのコードから構成されている。
（１）１番目のｐｉｖｏｔの決定
Ｎ個の登録情報２２０の特徴量データ２２３からランダムに１つ選択し、それを１番目のｐｉｖｏｔとする。
（２）ａ＋１番目（ａ＞＝１）のｐｉｖｏｔの決定
既にｐｉｖｏｔとして選択された登録情報２２０の特徴量データ２２３をＰ１、・・・、Ｐａとし、選択されていない登録情報２２０の特徴量データ２２３をＥ１、・・・、ＥＮ−ａとする。このとき、以下のようにしてＰａ＋１を決定する。
【数１】
2011034254.tif 000003
【００７３】
非対称な距離尺度を用いている場合、数１の代わりに以下の式を用いても良い。
【数２】
2011034254.tif 000004
【００７４】
以下、ステップＳ３０７における、検索用特徴量−ｐｉｖｏｔ間相関計算部３０３によるｑ−ｅ間距離ベクトルとｐ−ｅ間距離ベクトルとの相関の計算方法、及びステップＳ３０９における、検索用特徴量−ｎｏｎ−ｐｉｖｏｔ間相関計算部３０４によるｑ−ｐ間距離ベクトルとｎ−ｐ間距離ベクトルとの相関の計算方法について、その詳細を述べる。
【００７５】
図７にｑ−ｅ間距離ベクトルとｐ−ｅ間距離ベクトルの例を、図８にｑ−ｐ間距離ベクトルとｎ−ｐ間距離ベクトルの例を示す。距離テーブルの斜線部は、既に選択し距離を求めた、或いは枝刈りを行なった登録用データである。
【００７６】
１つ目の距離ベクトルをｘ＝（ｘ１、ｘ２、・・・、ｘｍ）とし、２つ目の距離ベクトルをｙ＝（ｙ１、ｙ２、・・・、ｙｍ）とする。これらの相関の計算方法としては、特許文献１記載の手法を踏襲する方法が考えられる。即ち、相関Ｒ（ｘ，ｙ）を、
【数３】
2011034254.tif 000005
Ｒ（ｑｅ，ｐｅ）＝Ｓｘｙ／（Ｓｘｘ＋Ｓｙｙ）
として求める。但し、
【数４】
2011034254.tif 000006
【数５】
2011034254.tif 000007
【数６】
2011034254.tif 000008
である。或いは、特許文献１に記載されているように、
【数７】
2011034254.tif 000009
として求めても良いし、
【数８】
2011034254.tif 000010
として求めても良い。但し、
【数９】
2011034254.tif 000011
である。数９はＤｘｙとして市街地距離を用いたものと等価であるが、その他、ユークリッド距離、チェビシェフ距離、二次形式距離などの距離尺度を用いても良い。
【００７７】
また、非特許文献１のようにベクトル間の相関ではなく、ベクトル間の距離を求め、それをそのまま登録情報３２０の特徴量データ３２３の選択基準として用いることとしても良い。この場合、ステップＳ３０８やステップＳ３１０におけるｐｉｖｏｔ、ｎｏｎ−ｐｉｖｏｔの選択基準は、「相関が最も大きいもの」ではなく、「距離が最も小さいもの」となる。また、非特許文献１では距離尺度としてチェビシェフ距離を用いているが、その他、市街地距離、ユークリッド距離、二次形式距離などの距離尺度を用いても良い。
【００７８】
ｑ−ｅ間距離ベクトル、ｐ−ｅ間距離ベクトル、ｑ−ｐ間距離ベクトル、ｎ−ｐ間距離ベクトルとしては、前述した以外の他のベクトルとして定義したものを用いても良い。例えば、ｑ−ｅ間距離ベクトルとして、検索用の特徴量と、探索済みの全ｎｏｎ−ｐｉｖｏｔとの距離で構成されるベクトルを、またｐ−ｅ間距離ベクトルとして、ｐｉｖｏｔと、探索済みの全ｎｏｎ−ｐｉｖｏｔとの距離で構成されるベクトルを用いても良い。この場合、距離テーブルに格納された距離情報のうち、ｐｉｖｏｔ同士の距離は用いられなくなるため、距離テーブルのサイズをさらに減らすことが可能となる。また、ステップＳ３０７を実行しない場合には、ｑ−ｅ間距離ベクトル、ｐ−ｅ間距離ベクトルは用いなくて良い。
【００７９】
以下、ステップＳ３１５における、枝刈り部３０７ａによる枝刈り処理について、その詳細を述べる。枝刈り処理は、非特許文献１記載の手法を踏襲する方法が考えられる。即ち、以下のように枝刈り処理を行なう。
（１）枝刈り判定を行なうデータ集合の作成
枝刈りをする否かの判定を行なう登録情報３２０の特徴量データ３２３の集合Ａ＊を作成する。Ａ＊の作成方法としては、例えば以下の方法がある。
ａ）まだ距離を求めておらず、枝刈りもされていない全ｎｏｎ−ｐｉｖｏｔの集合をＡ＊とする。
ｂ）Ｍ／２以上の数のｐｉｖｏｔに対して距離を求めていればｄ）と同じ、そうでなければａ）と同じ方法でＡ＊を作成する。
ｃ）Ｍ／３以上の数のｐｉｖｏｔに対して距離を求めていればｄ）と同じ、そうでなければａ）と同じ方法でＡ＊を作成する。
ｄ）まだ距離を求めておらず、枝刈りもされていない全ｐｉｖｏｔ及びｎｏｎ−ｐｉｖｏｔの集合をＡ＊とする。
（２）枝刈り判定を行なうデータの選択
Ａ＊から特徴量データ３２３（Ａとする）を１つ選択する。選択したものはＡ＊から除く。但し、Ａ＊が空であれば、枝刈り処理を終了する。
（３）距離ｄ’の算出
距離テーブルから、距離ｄ（Ｚｉ，Ａ）を求める。
（４）枝刈り判定
｜ｄ（Ｑ，Ｚｉ）−ｄ（Ｚｉ，Ａ）｜＞＝τであれば、その特徴量データ３２３Ａに対して類似検索の対象として選択しないものとする枝刈りを行なう。このときの特徴量データ３２３がｐｉｖｏｔの場合、Ｍ’をＭ’−１とする。（２）へ戻る。
【００８０】
用いる距離尺度が三角不等式を満たす場合（ハミング距離など）、認証用の特徴量Ｑと枝刈りされた特徴量データ３２３との距離はτ以上であることが保証される。従って、誤って距離がτ未満の特徴量データ３２３を枝刈りすることなく、距離算出対象の特徴量データ３２３の数を減らすことができる。これにより、認証時間のさらなる短縮が実現でき、その結果、利便性がさらに向上する効果が得られる。
【００８１】
以上、距離を用いる手法について説明したが、距離でなく類似度を用いて類似検索を行なっても良い。例えば、距離テーブルの代わりに各ｐｉｖｏｔと各登録用特徴量データの特徴量空間における類似度を示す類似度テーブルを備え、相関計算部３０３、３０４が、各距離ベクトルの代わりに、特徴量同士の類似度で構成される類似度ベクトルを用いて相関を計算することとしても良い。また、類似度算出部３０６が、距離でなく類似度を算出する、あるいは算出した距離に−１をかけることにより類似度を算出することとし、判定部３０７が、検索用特徴量と登録用特徴量との類似度が所定の閾値より大きい場合に、両者が類似すると判定し、枝刈り部３０７ａは、ＱとＺｉの類似度とＺｉとＡの類似度との差が所定の閾値τ以上である場合に、Ａに対し枝刈りを行なうこととしても良い。
【実施例２】
【００８２】
以下、図面を参照して、２つ目の実施形態について説明する。本実施形態の類似検索システムは、認証ユーザが生体情報を入力し、システムがサーバ端末内のデータベースから類似する生体情報を検索することで、認証ユーザが登録ユーザのうち誰か（或いは誰でもないか）を識別し、その結果に基づいて認証を行なう生体認証システムである。
【００８３】
図９に、本実施形態の類似検索システムの構成例を示す。ここでは、図１と異なる点について述べる。
【００８４】
このシステムは、ユーザから取得した登録情報をサーバ端末へ送信する登録端末１００と、登録情報を保存し、検索用特徴量を基に類似検索を行なうサーバ端末２００と、ユーザが入力した検索用の生データから抽出した特徴量をサーバ端末２００に送信するクライアント端末３００と、ネットワーク４００を含んで構成される。例えば、企業内のＰＣログイン時における認証や、業務システムへのアクセス時における認証などの情報アクセス制御をサーバ側で行なうシステム（以後、情報アクセス制御システム）の場合、登録端末１００は登録センター（登録用に確保された居室など）内に置かれたＰＣと生体情報入力センサ、クライアント端末２００は居室内のＰＣと生体情報入力センサ、サーバ端末３００はサーバ室に置かれたサーバ、ネットワーク４００は社内イントラネットとする構成が考えられる。この例においては、グループＩＤ２１０は居室毎、サブネット毎、或いはクライアント端末２００毎に異なる値となるように設定しても良い。
【００８５】
検索用特徴量−ｐｉｖｏｔ間相関計算部３０３、検索用特徴量−ｎｏｎ−ｐｉｖｏｔ間相関計算部３０４、登録用特徴量選択部３０５、類似度算出部３０６、判定部３０７、枝刈り部３０７ａはクライアント端末３００ではなくサーバ端末２００に備える。但し、枝刈り部３０７ａは無くても良い。また、クライアント端末３００はデータベースを持たない。
【００８６】
また、特徴量抽出部１０３及び特徴量抽出部３０２は、実施形態３のようにサーバ端末２００側にあっても良い。この場合、登録端末１００及びクライアント端末３００は特徴量を送信せずに生データを送信し、その後、サーバ端末２００が受信した生データから特徴量を抽出すれば良い。
【００８７】
本実施形態における登録端末１００、サーバ端末２００、クライアント端末３００のハードウェア構成は図２と同じである。
【００８８】
本実施形態における登録の処理手順およびデータの流れは図３と同じである。
【００８９】
図１０に、本実施形態における事前処理の処理手順およびデータの流れを示す。図１０のステップＳ２０１〜Ｓ２０３は、図４のステップＳ２０１〜Ｓ２０３と同じである。
【００９０】
図１１に、本実施形態における検索の処理手順およびデータの流れを示す。ここでは、図５との違いについてのみ述べる。
サーバ端末２００のＣＰＵ５００が、データベース２０４からマスタデータ２０５を読み出し、メモリ５０１に展開する（ステップＳ３０１）。また、この処理は行なわず、代わりにステップＳ３０３ａの直後に、受信したグループＩＤを持つマスタデータ２０５の登録情報２２０と補助情報２３０をデータベース２０４から読み出し、メモリ５０１に展開しても良い。前者はより短時間での検索ができるというメリットがあり、後者は必要なメモリの空き容量がより少ないというメリットがある。
【００９１】
クライアント端末３００は、グループＩＤ及び検索用の特徴量をサーバ端末２００に送信する（ステップＳ３０３ａ）。
ステップＳ３０４〜Ｓ３１７はクライアント端末３００ではなく、サーバ端末２００が行なう。ここでの登録情報２２０と補助情報２３０は、ステップＳ３０３ａにおいて受信したグループＩＤを持つマスタデータ２０５のものを用いる。
【００９２】
ステップＳ３１４で検索終了とする場合、及びステップ３１７では、サーバ端末２００は、クライアント端末３００に検索結果を送信する。例えば、クライアント端末３００へのログイン時における、認証ユーザがＤＢに登録されているか否かのみをチェックすることを目的とした認証の場合は、アクセスを許可する旨をクライアント端末３００に送信する方法が考えられる。また、業務システムへのアクセス時における、認証ユーザが誰なのかを出来る限り正確に把握することを目的とした認証の場合は、今まで検索した中で最も小さい距離を実現した登録用の特徴量データ２２３を持つ登録データＩＤ２２１を業務システムに送信し、業務システムが登録データＩＤ２２１としてのアクセスを許可する旨をクライアント端末３００に送信する方法が考えられる。クライアント端末３００は、サーバ端末３００からの受信内容に応じた処理を行なう。たとえば、クライアント端末３００へのログインを許可する旨を受信した場合には、ログインを実行する。
【実施例３】
【００９３】
以下、図面を参照して、３つ目の実施形態について説明する。本実施形態の類似検索システムは、ユーザが画像を入力し、システムがサーバ端末内のデータベースから類似する画像を検索する類似画像検索システムである。
【００９４】
図１２に本実施形態の類似検索システムの構成例を示す。ここでは、図９と異なる点について述べる。本実施形態では、生データは画像データである。
【００９５】
このシステムは、登録情報２２０をデータベース２０４に保存し、検索用特徴量を基に類似検索を行なうサーバ端末２００と、ユーザから検索用の生データを入力として受付、サーバ端末２００に送信するクライアント端末３００と、ネットワーク４００とを含んで構成される。例えば、サーバ端末２００は企業が運用するサーバ、クライアント端末３００はユーザが持つ自宅のＰＣ、ネットワーク４００は社内イントラネットとする構成が考えられる。
【００９６】
このシステムは登録端末１００、グループIＤ２１０を持たない。また、特徴量抽出部３０２はサーバ端末２００に持たせておく。抽出する特徴量としては、例えばカラーヒストグラムなどが考えられ、２つの特徴量間の距離としては、例えば二次形式距離などが考えられる。
【００９７】
登録情報２２０としては、例えばサーバ端末２００が、インターネットから収集した画像を生データ２２２として格納し、登録用データＩＤ２２１を付与し、特徴量抽出部３０２を用いて生データ２２２から特徴量データ２２３を抽出しておく、などの方法が考えられる。或いは、実施例１、２のように、ユーザが登録端末を用いて登録できることとしても良い。
【００９８】
本実施形態における登録端末１００、サーバ端末２００、クライアント端末３００のハードウェア構成は図２と同じである。
【００９９】
本実施形態における事前処理の処理手順およびデータの流れは図１０と同じである。
【０１００】
図１３に、本実施形態における検索の処理手順およびデータの流れを示す。ここでは、図５との違いについてのみ述べる。
クライアント端末３００は、通信Ｉ／Ｆ３０８によりネットワーク４００を介して検索用の生データをサーバ端末２００に送信する（ステップＳ３０２ａ）。
特徴量抽出処理（ステップＳ３０３）はクライアント端末３００ではなく、サーバ端末２００の特徴量抽出部３０２が行なう。
【０１０１】
ステップＳ３１４で検索終了とする場合、及びステップ３１７では、サーバ端末２００は、クライアント端末３００に検索結果を送信し、クライアント端末３００が出力装置５０４に検索結果を出力する。このとき、閾値より小さい距離を実現した１つ以上の登録用の生データ２２２を検索結果とする方法もあるし、その中で最も小さい距離を実現した生データ２２２を検索結果とする方法もある。前者の場合、距離の小さい順に生データ２２２をランク付けし、生データ２２２をランクと共に送信し、クライアント端末３００が出力装置５０４に表示することとにしても良い。
【０１０２】
なお、本発明は、上記各実施形態に限定されるものでなく、要旨を逸脱しない範囲で適宜変形することが可能である。
【産業上の利用可能性】
【０１０３】
本発明は、画像、動画、音楽、文書などのマルチメディアデータの類似検索を行なう任意のアプリケーションに対して適用可能である。例えば、類似画像検索システム、類似動画検索システム、類似音楽検索システム、類似文書検索システム、生体認証による入退室管理システムや勤怠管理システム、ＰＣログインシステムなどへの適用が可能である。
【符号の説明】
【０１０４】
１００  登録端末
１０１  ＩＤ取得部
１０２  生データ取得部
１０３  特徴量抽出部
２００  サーバ端末
２０１  ｐｉｖｏｔ決定部
２０２  距離テーブル作成部
２０５  マスタデータ
２１０  グループＩＤ
２２０  登録情報
２２１  登録データＩＤ
２２２  生データ
２２３  特徴量
２３１  ｐｉｖｏｔ情報
２３２  距離テーブル
３００  クライアント端末
３０３  検索用特徴量−ｐｉｖｏｔ間相関計算部
３０４  検索用特徴量−ｎｏｎ−ｐｉｖｏｔ間相関計算部
３０５  登録用特徴量選択部
３０６  類似度算出部
３０７  判定部
３０７ａ  枝刈り部
【図１】
2011034254.tif 000012
【図２】
2011034254.tif 000013
【図３】
2011034254.tif 000014
【図４】
2011034254.tif 000015
【図５】
2011034254.tif 000016
【図６（ａ）】
2011034254.tif 000017
【図６（ｂ）】
2011034254.tif 000018
【図７】
2011034254.tif 000019
【図８】
2011034254.tif 000020
【図９】
2011034254.tif 000021
【図１０】
2011034254.tif 000022
【図１１】
2011034254.tif 000023
【図１２】
2011034254.tif 000024
【図１３】
2011034254.tif 000025