(57)【特許請求の範囲】
【請求項１】
検索クエリデータと類似したデータを登録済みの検索対象データから検索する類似データ検索システムにおいて、
データから特徴量を抽出して特徴量ベクトルを生成する特徴量抽出部と、
検索対象データの特徴量ベクトルを複数のクラスタに分類するクラスタリング部と、
各クラスタに割り振られた一意的な連続番号であるクラスタ番号及び各クラスタのクラスタ代表値を管理すると共に、前記クラスタに含まれる特徴量ベクトルを記憶媒体の連続した領域に格納し、クラスタ数が所定の数に達する毎に、前記クラスタのクラスタ代表値とクラスタ番号を保存するデータ格納部と、
与えられたデータから抽出した特徴量ベクトルとベクトル空間中で距離の近いクラスタ代表値を持つクラスタを検索する類似クラスタ検索部と、
前記クラスタのメンバ数が予め設定された上限を超えた場合に該当クラスタを分割するクラスタ分割部と、
特定番号を持つクラスタのクラスタ代表値と前後のクラスタのクラスタ代表値とのベクトル間距離１と、前記特定番号を持つクラスタのクラスタ代表値と前記保存しているクラスタのクラスタ代表値とのベクトル間距離２を計算するエネルギー関数計算部とを有し、
検索対象として新規データを追加登録する時、前記記憶媒体に格納されたクラスタの中から前記特徴量抽出部によって抽出した当該新規データの特徴量ベクトルとベクトル空間中で距離の近いクラスタ代表値を持つ所定個数のクラスタを前記類似クラスタ検索部によって検索し、前記新規データの特徴量ベクトルと前記検索された所定個数のクラスタに含まれる特徴量ベクトルを対象に前記クラスタリング部でクラスタリングを行って複数のクラスタに再分類し、前記エネルギー関数計算部で前記ベクトル間距離１と前記ベクトル間距離２の和が小さくなるように前記再分類された複数のクラスタの前記記録媒体上における格納位置を求め、求めた格納位置に前記再分類されたクラスタに含まれる特徴量ベクトルを格納することを特徴とする類似データ検索システム。
【請求項２】
請求項１記載の類似データ検索システムにおいて、類似特徴量検索部と、検索結果出力部とを有し、
前記類似クラスタ検索部は、前記記憶媒体に格納されたクラスタの中から、検索クエリデータから抽出した特徴量ベクトルとベクトル空間中で距離の近いクラスタ代表値を持つクラスタを検索し、
前記類似特徴量検索部は、前記類似クラスタ検索部によって検索されたクラスタに含まれるクラスタメンバの中から前記検索クエリデータから抽出した特徴量ベクトルとベクトル空間中で距離の近い特徴量ベクトルを持つデータを検索し、
前記検索結果出力部は前記類似特徴量検索部によって検索されたデータを出力することを特徴とする類似データ検索システム。
【請求項３】
クラスタ番号として一意的な連続した番号を割り振られた複数のクラスタに分類されたデータ及びその特徴量ベクトル、現在のクラスタのクラスタ番号とクラスタ代表値の情報及び前記クラスタ数が所定数の時のクラスタのクラスタ番号とクラスタ代表値の情報を格納した記憶部と、特徴量抽出部と、類似クラスタ検索部と、検索対象データの特徴量ベクトルを複数のクラスタに分類するクラスタリング部と、クラスタ分割部と、データ格納部と、特定番号を持つクラスタのクラスタ代表値と前後のクラスタのクラスタ代表値とのベクトル間距離１と、前記特定番号を持つクラスタのクラスタ代表値と保存しているクラスタのクラスタ代表値とのベクトル間距離２を計算するエネルギー関数計算部とを有する類似データ検索システムを用い、検索クエリデータと類似したデータを登録済みの検索対象データから検索する類似データ検索方法であって、
新規登録データから前記特徴量抽出部によって特徴量を抽出して特徴量ベクトルを生成する工程と、
前記類似クラスタ検索部によって、前記記憶部に記憶された現在のクラスタの情報をもとに前記新規登録データから抽出した特徴量ベクトルとベクトル空間中で距離の近いクラスタ代表値を持つ所定数のクラスタを検索する工程と、
前記クラスタリング部によって、前記新規登録データの特徴ベクトルと前記所定数の類似クラスタに含まれるクラスタメンバの特徴ベクトルを対象にクラスタリングを行って複数のクラスタに分類する工程と、
前記クラスタのメンバ数が前記予め設定された上限を超えた場合に前記クラスタ分割部によって該当クラスタを分割する工程と、
前記エネルギー関数計算部によって、前記ベクトル間距離１と前記ベクトル間距離２の和が小さくなるように、前記クラスタリング部によって分類された複数のクラスタに含まれている特徴量ベクトルの前記記憶媒体上における格納位置を交換する工程と、
前記データ格納部によって、前記クラスタに含まれる特徴量ベクトルを記憶媒体の連続した領域に格納し、クラスタ数が所定の数に達する毎に、前記クラスタのクラスタ代表値とクラスタ番号を前記記憶部に保存する工程と
を有することを特徴とする類似データ検索方法。
【請求項４】
請求項３記載の類似データ検索方法において、前記類似データ検索システムは更に類似特徴量検索部と、検索結果出力部とを有し、
前記類似クラスタ検索部によって、前記記憶媒体に格納された現在のクラスタの中から、検索クエリデータから抽出した特徴量ベクトルとベクトル空間中で距離の近いクラスタ代表値を持つクラスタを検索する工程と、
前記類似特徴量検索部によって、前記検索されたクラスタに含まれるクラスタメンバの中から前記検索クエリデータから抽出した特徴量ベクトルとベクトル空間中で距離の近い特徴量ベクトルを持つデータを検索する工程と、
前記検索結果出力部によって、前記類似特徴量検索部によって検索されたデータを出力する工程と
を有することを特徴とする類似データ検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似データ検索システムに関し、類似データ検索における計算機上でのデータ配置最適化方式に関する。
【背景技術】
【０００２】
ネットワークのブロードバンド化や記憶装置の大容量化に伴って、ユーザがアクセス可能な画像や映像の量は、日々増加の一途を辿っている。こうした流れの中で、膨大な画像・映像コンテンツから、如何にして所望するものにアクセスすべきかという問題が生じている。従来は、人手もしくは半自動的にコンテンツに対してテキスト情報を付与することによってキーワード検索を可能とし、この問題を解決していた。しかし、それが可能となるのは大量のコンテンツの一部のみであり、そもそもテキスト情報だけでは画像の持つ情報を的確に表すことができないという問題もある。
【０００３】
そこで、画像の色の分布や形状等、画像自体が持つ情報を自動的に抽出し、高次元のベクトル情報として表現した画像特徴量に基づき、画像間の類似性を評価して検索を行う類似画像検索技術が提案されている。類似画像検索の主要処理である類似ベクトル検索処理では、検索のキーとなるデータと、ベクトル空間中で距離が小さいデータの検索、すなわち、ベクトル空間中での近傍検索が行われる。例えば、静止画像の類似検索では、画像中の色分布のヒストグラムや形状パターン等が、データを特徴付ける特徴量ベクトルとして用いられる。
【０００４】
近傍検索では、ベクトル間の距離を知る必要がある。距離計算の対象データ数をＮ、特徴量ベクトルの次元数をＭとすれば、検索キーデータと距離計算の対象データとの間でＮ回の距離計算が必要となり、かつ、各距離計算に必要となる時間は、Ｍに比例する。従って、近傍検索を線形探索で実現した場合、Ｎ×Ｍに比例した計算時間が必要となる。よって、大規模高次元データを検索対象にする場合、膨大な計算時間が必要となるため、最近接検索処理の高速化が必須である。
【０００５】
最近接検索の処理を高速化する手法として、検索クエリデータに応じて距離計算の対象データを絞り込む方法が複数提案されている。多次元インデキシングと総称される一群の手法は、データベースの分野で利用されているバランス木の概念を多次元空間の処理に拡張したものである。多次元インデキシングでは、空間中の領域が木構造で管理される。そして、検索クエリデータが与えられると、その検索クエリデータを含む領域が定義されたリーフLog Ｎのオーダで検索する。一方、パターン認識の分野では、距離が近いもの同士を予め分類しておく、クラスタリングに基づく高速化がしばしば用いられる。具体的な分類の手法としては、k-means法が一般的である。
【０００６】
一般的なデータベースシステムでは、特徴量ベクトルは２次記憶上に格納されていることが多い。そこで、２次記憶上の特徴量ベクトに対して、随時Ｉ／Ｏを行いながら類似ベクトルを検索する必要がある。ただし、２次記憶上でのＩ／Ｏは１次記憶上でのＩ／Ｏと比較して多大な時間を要するため、特徴量ベクトル同士の距離計算を高速化しても、対象となる特徴量ベクトルへのアクセス速度が遅いと意味がなくなってしまう。
【０００７】
そこで、２次記憶上のデータのＩ／Ｏ速度を向上するために、以下に示す手法が提案されている。
【０００８】
一般に、類似性が高い特徴量ベクトルは、検索時及び検索対象データ更新時に同時に参照される可能性が高い。したがって、類似性が高い特徴量ベクトル同士が、２次記憶上でなるべく近傍に集まるように配置すれば、ディスク走査の負荷を低減できると考えられる。
【０００９】
また、通常、ディスクアクセスは一度に一定の範囲のデータ全てに対して行われる。したがって、類似したデータが２次記憶上の近傍に集まっていれば、検索を行う際にディスクアクセスは行われたが最終的な検索結果として表示されなかったデータがディスクキャッシュに読み込まれた状態になる。よって、類似した検索キーデータを用いて複数回検索する際に、ディスクキャッシュ内に類似したデータが読み込まれているため、ディスクアクセスの回数が減り、検索の高速化を図ることができる。類似した検索キーデータを用いて複数回検索するようなことは、検索結果画面に表示されている画像を新たに検索キーデータとして用いる場合に、生じやすい。
【００１０】
そこで、２次記憶媒体を１次元配列とみなし、類似した特徴量ベクトル同士を１次元配列上で近傍に配置し、類似していない特徴量ベクトル同士は１次元配列上で遠い領域に配置するようなデータ配置処理を行うことによって、ディスクアクセスの高速化を図ることができると考えられる。
【００１１】
しかし、既存の木構造や階層型クラスタリングなどでは、類似した特徴量ベクトル同士を１次元配列上の近傍に配置することができない。例えば木構造において、各クラスタを最下層の葉ノードとして木構造を構築した場合、各ノードの下に存在するクラスタ同士は類似していると言うことができる。しかし、木構造はノードの上下関係のみを規定する抽象的な構造であり、類似した特徴量ベクトル同士を近傍に配置するような関係を実現するものではない。
【００１２】
特許文献１では、ニューラルネットワークの一種である自己組織化マップを用いて、特徴量ベクトルを高次元ベクトル空間中の距離を保存したままで、１次元の配列上にマッピングする手法が提案されている。ここでは、自己組織化マップが持つ高次元空間での近傍関係を出来る限り保ちつつ低次元空間へデータを配置する特徴を利用している。自己組織化マップの出力層のユニット数をｋとすると、全検索対象特徴量ベクトルはｋ個のクラスタに分割され、類似したクラスタ同士が１次元配列上で近傍に配置される。クラスタ同士の類似度はクラスタの持つ参照ベクトル間の距離によって定義される。そして、全検索対象特徴量ベクトルを距離が最も近いクラスタに格納する。このとき、各クラスタの参照ベクトルはメモリ上に保持され、各クラスタに属する特徴量ベクトルは２次記憶上の連続した領域に格納される。
【００１３】
特許文献２では、k-means法に基づくクラスタリング手法を用いて類似した特徴量ベクトル同士をまとめたクラスタを作成し、類似したクラスタ同士が１次元配列上で近傍領域に配置されるようにデータ配置処理を行う。クラスタの代表値のみを１次記憶上に保持し、特徴量ベクトルは２次記憶上に格納する。ここで、クラスタ内に含まれる特徴量ベクトルの平均値をクラスタ代表値とし、以下クラスタ平均と呼ぶ。また、各クラスタメンバの２次記憶上の格納領域を連続的に確保するために、クラスタ生成時に所定の量の記憶領域を確保する。それに従い、各クラスタメンバの最大数も制限される。
【００１４】
ただし、新規特徴量ベクトルを登録するたびに、全特徴量ベクトルのクラスタリングを行ったのでは、実用的な処理時間で登録処理を行うことは不可能である。そこで、以下に示す逐次クラスタリングを行う。新規データ登録時に、新規データから抽出した新規特徴量ベクトルとベクトル間距離が近いクラスタ平均を持つクラスタを、近接クラスタとして所定の個数検索し、検索された近接クラスタに含まれる特徴量ベクトル及び新規特徴量ベクトルのみを対象にしてk-means法による最適化を実行する。さらに、各クラスタのメンバ数に上限を設け、上限を超えた場合はクラスタを２分割し、新たに生成されたクラスタを近接クラスタの集合に加える。よって、登録データ数が増加するにつれて、クラスタ数も増加することになる。
【００１５】
そして、以下に示すエネルギー関数Ｅ1を利用して、類似したクラスタを１次元配列上の近傍領域に配置する。
【００１６】
【数１】
0005155025.tif 000002
【００１７】
式（１）は、クラスタ位置の再配列の手続きを定義するためのエネルギー関数Ｅ1である。Ｎcはクラスタ数、ｖiはｉ番目の位置にあるクラスタの平均ベクトルを表す。本エネルギー関数は、相前後する位置にあるクラスタ平均の２乗距離の総和として定義されている。
【００１８】
ただし、両端の位置、すなわち１番目の位置とＮc番目のクラスタについての境界条件は、片側のみを定義している。具体的には、存在しない０番目の位置のクラスタと１番目のクラスタとのクラスタ平均同士の距離は０とし、存在しないＮc＋１番目の位置のクラスタとＮ番目の位置のクラスタとのクラスタ平均同士の距離も０とする。この時、ｉ番目の位置にあるクラスタとｊ番目の位置にあるクラスタを交換した場合のエネルギー関数の変化量は、式（２）によって算出される。ただし、ｊ＞ｉとする。
【００１９】
【数２】
0005155025.tif 000003
【００２０】
上記のエネルギー変化量に基づいてエネルギー関数が減少するように、現在更新対象となっている近接クラスタ集合中のクラスタの位置を更新すれば、配列中で隣り合う位置に存在するクラスタ同士の距離が相対的に小さい状態が実現できる。
【００２１】
以上の処理を新規データ登録のたびに繰り返すことによって、類似クラスタ同士が１次元配列の近傍領域に配置される。
【００２２】
【特許文献１】特開２００４−４６６１２号公報
【特許文献２】特開２００７−３３４４０２号公報
【発明の開示】
【発明が解決しようとする課題】
【００２３】
類似したベクトルデータを記憶媒体上の近傍領域に配置することを目的とする従来のデータ配置最適化方式には、以下に示す問題点が存在していた。
【００２４】
自己組織化マップを用いて高次元ベクトルデータを１次元配列上にマッピングする場合、新規データの追加に柔軟に対応することができない。なぜなら、自己組織化マップを用いてマッピングを行う際には大量の処理時間を必要とするため、新規データを追加するたびに再マッピングを行うことは実用上不可能である。例えば、監視カメラで撮影された画像中の人物を検索対象とする場合、検索対象となる人物画像が逐次的に生成されるため、新規データを逐次的に登録する必要があり、極めて短時間の内に再マッピングを行わなければならなくなってしまう。
【００２５】
相前後する位置にあるベクトルデータの２乗距離の総和として定義されるエネルギー関数を利用して高次元ベクトルデータを１次元配列上に配置する場合、類似度の大きい特徴量ベクトル同士が隣接するように配置することはある程度可能である。しかし、１次元配列上の距離が一定以上離れたクラスタ同士の類似度は、１次元配列上の距離とは関係なく、ランダムに等しい状態になってしまう。つまり、この手法が有効なのは１次元配列上の一定範囲内のクラスタのみに留まる。また、近傍に集まるクラスタ数のオーダは全クラスタ数に因らず一定（Ｏ(１)）のため、クラスタ数が増加するにつれて、近傍に集まるクラスタ数が相対的に少なくなる。したがって、局所的に最適化されたクラスタ群が複数箇所に散在してしまうという問題が生じる。この理由として、最近接クラスタ間の距離のみからエネルギー関数を計算してクラスタ位置を決定しているため、１次元配列全体におけるクラスタ位置が不定になることが挙げられる。
【００２６】
そこで、本発明は、記憶媒体上のデータのＩ／Ｏ速度を向上するために、近傍に集まるデータ数のオーダが全データ数Ｎcに依存してＯ(Ｎc)となるように、高次元ベクトルデータを１次元配列上に配置する手段を提供することを目的とする。
【課題を解決するための手段】
【００２７】
エネルギー関数を利用して高次元ベクトルデータを１次元配列（以下、この１次元配列をクラスタ配列と呼ぶ）上に配置する場合、クラスタ配列全体におけるクラスタ位置が不定になることを避けるためには、隣接クラスタ同士の関係だけでなく、各クラスタがクラスタ配列全体において、どこに配置されるべきかという情報もエネルギー関数に加える必要がある。そのために特徴量ベクトルの分布情報を利用して、クラスタ配列の近傍領域に類似したクラスタが集まり、類似していないクラスタ同士はクラスタ配列の中で離れた領域に配置されるようにする。
【００２８】
新規データ登録時には特許文献２の方法を用いて逐次クラスタリングを行う。新規データから抽出した特徴量ベクトルとベクトル間距離が近いクラスタ平均を持つクラスタを、近接クラスタとして所定の個数検索し、検索された近接クラスタ内に含まれる特徴量ベクトル及び新規特徴量ベクトルのみを対象にしてk-means法による最適化を実行する。さらに、各クラスタのメンバ数に上限を設け、上限を超えた場合はクラスタを２分割し、新たに生成されたクラスタを近接クラスタの集合に加える。よって、登録データ数が増加するにつれて、クラスタ数も増加することになる。
【００２９】
クラスタ数Ｎcが少数の場合（例えばＮc＜４）は、更新対象クラスタに対して、特許文献２と同様のエネルギー関数Ｅ1を用いてクラスタ配置の更新を行う。これに加えて、クラスタ情報としてクラスタ平均とクラスタ位置の組を保存しておく。ここでクラスタ位置とは、クラスタ配列上の配列番号である。
【００３０】
クラスタ数Ｎcが増加した場合（例えばＮc≧４）、現在のクラスタ平均と保存している過去のクラスタ平均とのベクトル間距離の２乗をエネルギー関数Ｅ1に加える。具体的には、まず、保存している過去のクラスタについて、ある時点の過去クラスタ配列に着目する。次に、着目した過去クラスタ配列内のクラスタ番号を最小値が１、最大値がＮcとなるように変換する。そして、現在クラスタ配列内のクラスタのクラスタ番号と、最も近い変換後のクラスタ番号を持つ過去クラスタ配列内のクラスタを取得し、それらのクラスタのクラスタ平均のベクトル間距離の２乗をエネルギー関数に加算する。また、クラスタ数Ｎcが少数の場合と同様に、クラスタ情報の保存を行う。
【００３１】
本発明では、新規登録データから抽出された特徴量ベクトルとベクトル空間中で距離の近いクラスタ代表値を持つクラスタを検索し、新規登録データと類似クラスタに含まれるデータを複数のクラスタに分類し、各クラスタのメンバ数に上限を設け、上限を超えた場合は該当クラスタを分割し、各クラスタに含まれる特徴量ベクトルを記憶媒体の連続した領域に格納し、各クラスタに一意的な連続した番号を割り振って、クラスタ番号として管理し、各クラスタに含まれる特徴量ベクトルからベクトルデータであるクラスタ代表値を計算し、各クラスタのクラスタ代表値とクラスタ番号を保存し、特定番号を持つクラスタのクラスタ代表値と前後のクラスタのクラスタ代表値とのベクトル間距離１を計算し、特定番号を持つクラスタのクラスタ代表値と保存しているクラスタのクラスタ代表値とのベクトル間距離２を計算し、ベクトル間距離１とベクトル間距離２の和が小さくなるように、クラスタに含まれている特徴量ベクトルの記憶媒体上における格納位置を交換することによって、類似したクラスタ代表値を持つクラスタを記憶媒体の近傍領域に格納する。
【発明の効果】
【００３２】
本発明にかかる類似データ検索におけるデータ配置最適化方式によれば、記憶媒体を１次元配列とみなし、類似したデータ同士を１次元配列上の近傍領域に配置することによって、記憶媒体上の類似データのＩ／Ｏ速度を向上することができる。さらに、近傍領域に集まる類似データ数は、全データ数Ｎcに依存してＯ(Ｎc)となる。
【発明を実施するための最良の形態】
【００３３】
以下、本発明の実施の一形態として、画像を対象とした類似検索システムにおけるデータ配置処理について説明する。
【００３４】
図１は、本発明による類似データ検索システムのシステム構成例を示す図である。検索エンジンが稼動するサーバ計算機１１０は、通信基盤１２０を経由して、アプリケーションプログラムが稼動するクライアント計算機１３０と接続され、クライアント計算機１３０に検索等のサービスを提供する。通信基盤１２０は、サーバ計算機１１０とクライアント計算機１３０とを接続するネットワーク（例えば、ＩＰネットワーク）である。サーバ計算機１１０は、少なくとも、相互に接続されたインターフェース（Ｉ／Ｆ）１５１、ＣＰＵ１５２、メモリ１５３及び２次記憶、例えばハードディスク１５４を備える。
【００３５】
Ｉ／Ｆ１５１は、通信基盤１２０に接続され、サーバ計算機１１０とクライアント計算機１３０の間の通信に使用される。ＣＰＵ１５２は、メモリ１５３に格納されたプログラムを実行するプロセッサである。メモリ１５３は、ＣＰＵ１５２によって実行されるプログラム及びＣＰＵ１５２によって参照されるデータを格納する記憶装置である。本実施の形態のメモリ１５３は、いわゆる主記憶装置であり、例えば、ランダムアクセス可能な半導体記憶装置である。本実施の形態のメモリ１５３は、少なくとも、検索サーバプロセス１１１を実現するためのサーバ・プログラム及びデータを格納する。
【００３６】
ハードディスク１５４は、一つ以上のハードディスクドライブ（ＨＤＤ）からなる記憶装置である。本実施の形態のハードディスク１５４は、画像サーバ１４０に格納された画像の特徴量ベクトルに関する情報を特徴量データ１１４及びクラスタ管理情報１１５として格納する。なお、本実施の形態のハードディスク１５４は、光ディスク装置、フラッシュメモリのような半導体記憶装置、又は、その他のいかなる種類の記憶装置によって置き換えられてもよい。
【００３７】
特徴量ベクトルとは、画像サーバ１４０に格納されている画像の特徴をベクトルデータとして数値化したものである。特徴量ベクトルは、従来から知られている種々の方法によって算出することができる。例えば、エッジパターン特徴量と呼ばれるものを用いることができる。エッジパターン特徴量を抽出するためには、まず、特徴的なエッジパターンを予め複数設定する。そして、顔画像に対して格子状に構図分割を行い、各領域内に含まれるエッジパターン数を計数する。このエッジパターン数からヒストグラムを生成し、多次元ベクトルとすることによって特徴量ベクトルを得る。また、検索対象画像の全領域に対して格子状に構図分割を行い、分割された各領域の色ヒストグラムから作られる多次元ベクトルを特徴量ベクトルとして用いてもよい。さらにこれらの多次元ベクトルを組み合わせたものを特徴量ベクトルとして使用してもよい。
【００３８】
本実施の形態において、各特徴量ベクトルは、複数のクラスタのいずれかに分類される。相互に距離が近い特徴量ベクトルは、同じクラスタに分類されることが望ましい。特徴量ベクトルは、どのような方法でクラスタに分類されてもよいが、本実施の形態では、k-means法によって分類される。
【００３９】
特徴量データ１１４は、一つのクラスタに分類された一つ以上の画像を識別するデータＩＤと、そのＩＤによって識別される画像データの特徴量ベクトルと、の組を含む。尚、各クラスタに分類された画像及び特徴量ベクトルは、クラスタメンバとも記載する。
【００４０】
クラスタ管理情報１１５は、各クラスタを識別するクラスタＩＤと、そのクラスタＩＤによって識別されるクラスタの代表値と、の組を含む。現在の情報及び全クラスタ数Ｎcが特定の数のときの情報が格納されている。本実施の形態では、クラスタ数Ｎcが２のべき乗のときにクラスタ情報を格納する。
【００４１】
本実施の形態において、各クラスタの代表値とは、各クラスタに含まれる特徴量ベクトルの平均ベクトル（クラスタ平均）である。尚、平均ベクトル以外の値がクラスタの代表値として使用されてもよい。例えば、平均ベクトルに近接するクラスタメンバの特徴量ベクトルが使用されてもよいし、k-means法による最適化を実行する際に指定されるシード値が使用されてもよい。k-means法による最適化の結果、各特徴量ベクトルは、その特徴量ベクトルと最も距離が近い代表値を含むクラスタに含まれる。
【００４２】
画像サーバ１４０は、画像データを格納する記憶装置を備え、通信基盤１２０に接続される計算機である。クライアント計算機１３０又はサーバ計算機１１０から通信基盤１２０を通して画像データへのアクセスがあった場合に、画像データの入出力を行う。尚、画像サーバ１４０は、サーバ計算機１１０もしくはクライアント計算機１３０に含まれていても良い。
【００４３】
サーバ計算機１１０内の検索サーバプロセス１１１は、クラスタリングされた（すなわち、クラスタに分類された）検索対象を管理している。システム稼動時には、クラスタ管理情報１１５は、サーバ計算機のメモリ１５３内にクラスタ管理情報１１２として展開されている。各クラスタ情報１１３として、各クラスタＩＤ、そのＩＤによって識別されるクラスタの代表値である平均ベクトル、及び、クラスタメンバを識別するデータＩＤ列等が格納されている。各クラスタメンバの特徴量ベクトルは、特徴量データ１１４として一括してハードディスク１５４上で管理される。このため、メモリ１５３内のクラスタ情報１１３として、さらに、各クラスタメンバの特徴量ベクトルを格納したハードディスク上の位置が格納されている。
【００４４】
尚、クラスタ管理情報１１２は、ハードディスク１５４上に記録されたクラスタ管理情報のコピーである。このため、クラスタに対する更新が生じた場合、クラスタ管理情報１１２だけでなく、ハードディスク１５４上のクラスタ管理情報１１５も更新される。しかし、検索処理においてクラスタ管理情報１１５が直接参照されることはない。
【００４５】
クライアント計算機１３０は、通信基盤１２０に接続される計算機である。図１には２つのクライアント計算機１３０を示すが、本類似データ検索システムは任意の数のクライアント計算機１３０を備えてもよい。尚、クライアント計算機１３０と同等の機能をサーバ計算機１１０が備えている場合、全ての処理をサーバ計算機で行っても良い。
【００４６】
クライアント計算機１３０は、いかなる構成の計算機であってもよい。図１には、典型的なクライアント計算機１３０の構成を示す。すなわち、図１のクライアント計算機１３０は、ＣＰＵ１３１、メモリ１３２、Ｉ／Ｆ１３３、入力装置１３４及び出力装置１３５を備える。
【００４７】
ＣＰＵ１３１は、メモリ１３２に格納されたプログラムを実行するプロセッサである。メモリ１３２は、ＣＰＵ１３１によって実行されるプログラム等を格納する記憶装置である。Ｉ／Ｆ１３３は、通信基盤１２０に接続され、クライアント計算機１３０とサーバ計算機１１０との間の通信に使用されるインターフェースである。入力装置１３４は、クライアント計算機１３０のユーザから入力を受け付ける装置である。入力装置１３４は、例えば、キーボード、ポインティングデバイス又は画像スキャナ等を含んでもよい。出力装置１３５は、クライアント計算機１３０のユーザに情報を表示する装置である。具体的には、例えば、類似データ検索の結果として取得された画像が出力装置１３５に表示される。出力装置１３５は、例えばＣＲＴ又は液晶ディスプレイのような画像表示装置である。
【００４８】
次に、本実施の形態の検索システムにおける類似データ検索時の処理について説明する。図２は、本発明の実施の形態において、類似データ検索時に実行される処理の実行部を示すブロック図である。同図に示すように、本実施の形態の類似データ検索処理は、画像入力部２１０、画像特徴量抽出部２１１、類似クラスタ検索部２１２、類似特徴量検索部２１３、検索結果出力部２１４で構成される。
【００４９】
画像入力部２１０では、検索目標画像の入力処理を行う。ここで、検索目標画像は、検索しようとする物体や人物が写された画像データや、検索したいテクスチャが描かれた画像データである。これらの画像データは、デジタルカメラや補助記憶装置、マウス等によるユーザの描画によって供給される。
【００５０】
画像特徴量抽出部２１１では、検索目標画像から画像特徴量を抽出する。本実施例では、画像特徴量としてエッジパターン特徴量と呼ばれるものを用いる。エッジパターン特徴量を抽出するためには、まず、特徴的なエッジパターンを予め複数設定する。そして、画像データに対して格子状に構図分割を行い、各領域内に含まれるエッジパターン数を計数する。このエッジパターン数からヒストグラムを生成し、多次元ベクトルとすることによって、画像特徴量を作成する。他にも色ヒストグラムを画像特徴量として用いても良い。
【００５１】
類似クラスタ検索部２１２では、クラスタ管理情報１１２の持つクラスタＩＤとクラスタ平均を用いて、検索目標画像から抽出した画像特徴量ベクトルとベクトル空間中で距離の近いクラスタ平均を持つクラスタを所定の個数検索する。
【００５２】
類似特徴量検索部２１３では、特徴量データ１１４の持つ特徴量ベクトルを用いて、前記類似クラスタ検索部２１２で取得した類似クラスタ内に含まれるクラスタメンバの中から、検索目標画像から抽出した画像特徴量ベクトルとベクトル空間中で距離の近い特徴量ベクトルを持つデータを検索する。
【００５３】
検索結果出力部２１４では、前記類似特徴量検索部２１３で検索されたデータの画像データを画像サーバ１４０から取得し、検索結果として出力する。尚、画像サーバ１４０を用いずに、データＩＤを検索結果として表示しても良い。
【００５４】
ここで、画像特徴量抽出部２１１、類似クラスタ検索部２１２、類似特徴量検索部２１３は、サーバ計算機１１０のメモリ１５３に展開されたプログラムによって検索サーバプロセス１１１の一部として実現され、その処理が実行される。
【００５５】
次に、本実施の形態の類似データ検索システムにおける新規データ登録時の処理について説明する。図３は、本発明の実施の形態において、新規データ登録時に実行される処理の実行部を示すブロック図である。同図に示すように、本実施の形態の新規データ登録処理は、画像入力部３１０、画像特徴量抽出部３１１、類似クラスタ検索部３１２、クラスタリング部３１３、クラスタ分割部３１４、エネルギー関数計算部３１５、データ格納部３１６、で構成される。
【００５６】
画像入力部３１０では、新規登録画像の入力処理を行う。画像データは、デジタルカメラや補助記憶装置、マウス等によるユーザの描画によって供給される。画像特徴量抽出部３１１では、登録画像を対象に、画像特徴量抽出部２１１と同様に画像特徴量を抽出する。類似クラスタ検索部３１２、クラスタリング部３１３、クラスタ分割部３１４では、特許文献２の方法を用いて逐次クラスタリングを行う。
【００５７】
類似クラスタ検索部３１２では、類似クラスタ検索部２１２と同様に、クラスタ管理情報１１２の持つクラスタＩＤとクラスタ平均を用いて、新規登録画像から抽出した画像特徴量ベクトルとベクトル空間中で距離の近いクラスタ平均を持つクラスタを所定の個数検索する。尚、検索結果として得るクラスタの数は、類似クラスタ検索部２１２と異なっても良い。クラスタリング部３１３では、類似クラスタ検索部３１２で取得した類似クラスタ内に含まれるクラスタメンバの特徴量ベクトルのみを特徴量データ１１４から取得し、これらの特徴量データと新規登録画像の特徴量ベクトルのみを対象に、k-means法に基づいたクラスタリングを行う。
【００５８】
クラスタ分割部３１４では、クラスタの分割を行う。クラスタに含まれるクラスタメンバ数には、予め最大数が設定されており、クラスタメンバ数が最大値を超えたクラスタを、二つに分割する。この処理によって新しいクラスタが生成されるため、登録データ数が増加するにつれて、クラスタ数が増加することになる。クラスタを生成する際には、各クラスタのメンバのハードディスク上の格納領域を、物理的にも連続的に確保するために、所定の量のディスク領域を確保する。このときに確保するディスク領域の量によって、各クラスタメンバの最大数が制限されることになる。
【００５９】
エネルギー関数計算部３１５では、後述するエネルギー関数に基づいて、エネルギーを計算する。データ格納部３１６では、前記クラスタリング部３１３でクラスタリングを行った特徴量ベクトルを、特徴量データ１１４に格納する。このとき、後述するエネルギー関数が最も小さくなる位置に格納する。さらに、クラスタ数が特定の数の時に、全クラスタのクラスタＩＤとクラスタ平均をクラスタ管理情報１１２に保存する。
【００６０】
ここで、画像特徴量抽出部３１１、類似クラスタ検索部３１２、クラスタリング部３１３、クラスタ分割部３１４、エネルギー関数計算部３１５、データ格納部３１６は、サーバ計算機１１０のメモリ１５３に展開されたプログラムによって検索サーバプロセス１１１の一部として実現され、その処理が実行される。
【００６１】
図４は、本発明の実施の形態において新規データ登録時にサーバ上で実行される処理を示すフローチャートである。ここでは、類似クラスタ検索部３１２、クラスタリング部３１３、クラスタ分割部３１４、で実行される処理について、詳細に説明する。
【００６２】
図４に示す処理は、検索サーバプロセス１１１を実現するサーバ・プログラムの一部として実行される。従って、図４に示す処理は、ＣＰＵ１５２によって実行される。
【００６３】
ＣＰＵ１５２は、登録対象の新規データｘが与えられると、まず、近接クラスタを検索し、近接クラスタの集合Ｃ*を取得する（Ｓ４１０）。具体的には、ＣＰＵ１５２は、各クラスタの平均ベクトルと新規データｘとを比較し、新規データｘと距離が近い平均ベクトルによって代表されるクラスタから順に、所定の数のクラスタを近接クラスタの集合Ｃ*として取得する。次に、ＣＰＵ１５２は、近接クラスタの集合Ｃ*の中の最近接クラスタｃ*（すなわち、新規データｘと最も距離が近い平均ベクトルによって代表されるクラスタ）に、新規データｘを追加する（Ｓ４２０）。
【００６４】
次に、ＣＰＵ１５２は、パラメータｔ及びパラメータｉを、それぞれ、「０」及び「１」に初期化する（Ｓ４２１、Ｓ４２２）。パラメータｔは、k-means法の更新の反復回数を計数するために使用される。パラメータｉは、近接クラスタの集合Ｃ*に要素として含まれるクラスタを指示するために使用される。その後、ステップ４３０以降に示す、k-means法による最適化のループに入る。
【００６５】
まず、ＣＰＵ１５２は、近接クラスタの集合Ｃ*の要素である各クラスタについて、クラスタのメンバ数が制限Ｍmaxを超えるか否かを判定する。Ｍmaxはクラスタ内メンバ数の最大値である。具体的には、ＣＰＵ１５２は、ステップ４３０において、パラメータｉが集合Ｃ*の要素数以下であるか否かを判定する。ステップ４３０において、パラメータｉが集合Ｃ*の要素数以下であると判定された場合、ＣＰＵ１５２は、集合Ｃ*のｉ番目の要素であるクラスタｃを対象として（Ｓ４３４）、クラスタｃのメンバ数がＭmaxを超えるか否かを判定する（Ｓ４３１）。尚、最適化ループに入った時点では、新規データｘが追加された最近接クラスタｃ*以外のクラスタは、メンバ数制限を超えないことが前提となる。
【００６６】
仮に最近接クラスタｃ*のメンバ数がＭmaxを超えた場合、ＣＰＵ１５２は、そのクラスタを２分割し（Ｓ４３２）、新たに生成されたクラスタｄを近接クラスタの集合Ｃ*の要素に加える（Ｓ４３３）。クラスタを２分割する方法としては、種々の方法が考えられる。本実施の形態では、そのクラスタ内のベクトル分布に関して主軸を求め、各メンバのベクトルの主軸への射影が、クラスタ平均ベクトルの射影のどちら側に存在するかを判定することによって、メンバを二つのクラスタに分割する。
【００６７】
ステップ４３３が実行された後、ＣＰＵ１５２の処理は、ステップ４３１に戻る。ステップ４３１では、分割後のクラスタのメンバ数がＭmaxを超えているか否かが判定される。分割後のクラスタのメンバ数がＭmaxを超えていると判定された場合、そのクラスタをさらに分割するために、処理はステップ４３２に進む。一方、分割後のクラスタのメンバ数がＭmaxを超えていないと判定された場合、次のクラスタについてステップ４３１の判定を実行するために、ＣＰＵ１５２は、パラメータｉの値に１を加算して（Ｓ４３５）、ステップ４３０に戻る。
【００６８】
ステップ４３０において、パラメータｉが集合Ｃ*の要素数を超えたと判定された場合、集合Ｃ*の要素である全てのクラスタのメンバ数がＭmax以内であることが確認された。この場合、ＣＰＵ１５２は、k-means法による最適化の反復回数ｔをチェックする（Ｓ４４０）。
【００６９】
本システムにおいて、図４に示す最適化は、あくまでクラスタの部分集合を対象としたものであり、クラスタ全体での最適化を意味しない。また、データの追加は、その後も繰り返し行われることを想定しており、その度に最適化が実行される。従って、ある時点での最適化を極端に重視する必要はなく、反復の最大数ｔmaxは、数回程度で十分である。
【００７０】
ステップ４４０において、反復回数を示すパラメータｔが反復の最大数ｔmax以上であると判定された場合、k-means法による最適化が所定の回数実行されたため、図４の処理が終了する。あるいは、ステップ４４０において、集合Ｃ*が変化していないと判定された場合、さらに最適化を実行する必要がないと考えられる。従って、この場合も、図４の処理が終了する。
【００７１】
一方、ステップ４４０において、反復回数を示すパラメータｔが反復の最大数ｔmaxより小さく、かつ、集合Ｃ*が変化していると判定された場合、クラスタの最適化を実行する必要があるため、ＣＰＵ１５２は、k-means法によって集合Ｃ*を更新する（Ｓ４５０）。
【００７２】
ステップ４５０の処理は、通常のk-means法と同様である。すなわち、近接クラスタに含まれる全データは、その時点での最も近接したクラスタ平均を持つクラスタに配分される。これによって、各近接クラスタのメンバ、及び、クラスタ平均が更新され、ステップ４３０に戻る。このとき、ステップ４５１で反復回数を示すパラメータｔの値に１が加算される。最適化ループに入った時点とは異なり、今回は、大きくクラスタの状態が変化した場合、複数のクラスタがメンバ数の上限を超える可能性がある。また、２分割しただけでは不十分であるため、再度分割が必要となる場合、あるいは、新たに生成されたクラスタが上限を超える場合も生じる可能性がある。このため、ＣＰＵ１５２は、全てのクラスタのメンバ数が上限Ｍmax以下となるように処理（ステップ４３０からステップ４３５）した後、ステップ４４０に移行する。ステップ４４０で、反復数が最大数ｔmaxに達したか、あるいは、近接クラスタの集合Ｃ*の状態に全く変化がない場合、処理を終了する。
【００７３】
以上の処理によって、登録データ数が増加するにつれて、クラスタ数も増加することになる。新クラスタが追加されるのは、クラスタ内のメンバ数がクラスタメンバ最大数を超えたときのため、（クラスタメンバ最大数）回に１回程度の頻度となる。図４に示した一連の処理は、メモリ１５３上の作業領域で実行され、近接クラスタの集合が更新される。
【００７４】
次に、本類似検索システムにおけるデータ配置処理について説明する。一般に、類似性が高いクラスタは、更新時、及び、検索時に同時に参照される可能性が高い。従って、類似性が高いクラスタ同士が、２次記憶媒体上でなるべく近傍に集まるように配列すれば、ディスク走査の負荷を低減できるはずである。そこで、２次記憶媒体を１次元配列とみなし、類似したクラスタ同士を１次元配列上で近傍に配置し、類似していないクラスタ同士は１次元配列上で遠い領域に配置する。
【００７５】
クラスタ数Ｎcが少数の場合（例えばＮc＜４）は、更新対象クラスタに対して、特許文献２と同様のエネルギー関数Ｅ1を用いてクラスタ配置の更新を行う。
【００７６】
クラスタ数Ｎcが増加した場合（例えばＮc≧４）、式（３）に示されるエネルギー関数Ｅ2を用いて、クラスタ配置の更新を行う。
【００７７】
【数３】
0005155025.tif 000004
【００７８】
式（３）は、クラスタ位置の再配列の手続きを定義するためのエネルギー関数Ｅ2である。Ｎcはクラスタ数、ｖiはｉ番目の位置にあるクラスタの平均ベクトルであり、ｕlqはクラスタ数がｍのｌ乗（ｍ、ｌは自然数）の時のｑ番目の位置にあるクラスタの平均ベクトルを表す。以下では例として、ｍ＝２としたときについて説明する。ｐは式（４）を満たす最大の整数であり、ｐのオーダはＯ(log(Ｎc))となる。また、ｑは式（５）を満たす。尚、ｕlqはクラスタ管理情報１１５に保存されている。
【００７９】
本エネルギー関数Ｅ2は、相前後する位置にあるクラスタ平均の２乗距離の総和を表す項と、逐次クラスタリングの結果として得られ、クラスタ管理情報１１５に保存している過去クラスタ平均と現在のクラスタ平均の２乗距離の総和を表す項の和として定義されている。具体的には、まず、保存している過去のクラスタについて、ある時点の過去クラスタ配列に着目する。次に、着目した過去クラスタ配列内のクラスタ番号を最小値が１、最大値がＮcとなるように、式（５）を用いて変換する。そして、現在クラスタ配列内のクラスタのクラスタ番号と、最も近い変換後のクラスタ番号を持つ過去クラスタ配列内のクラスタを取得し、それらのクラスタのクラスタ平均のベクトル間距離の２乗をエネルギー関数に加算する。
【００８０】
ただし、両端の位置、すなわち１番目の位置とＮc番目のクラスタについての境界条件は、片側のみを定義している。具体的には、存在しない０番目の位置のクラスタと１番目のクラスタとのクラスタ平均同士の距離は０とし、存在しないＮc＋１番目の位置のクラスタとＮc番目の位置のクラスタとのクラスタ平均同士の距離も０とする。
【００８１】
本エネルギー関数Ｅ2では、ｉ番目のクラスタとｉ−１番目のクラスタ及びｉ＋１番目のクラスタの類似度が大きければ、前半の項が小さくなり、ｉ番目のクラスタが過去のクラスタ平均に対応した位置に配置されれば、後半の項は小さくなる。
【００８２】
このとき、ｉ番目の位置にあるクラスタとｊ番目の位置にあるクラスタを交換した場合のエネルギー関数の変化量は、式（６）によって算出される。ただし、ｊ＞ｉとする。
【００８３】
【数４】
0005155025.tif 000005
【００８４】
上記のエネルギー変化量に基づいてエネルギー関数が減少するように、現在更新対象となっている近接クラスタ集合中のクラスタの位置を更新する。逐次クラスタリング処理によってクラスタ数が増加した場合、新規クラスタはクラスタ配列の末尾に配置されていたとみなして、クラスタ配列の再配列処理を行う。
【００８５】
さらに、更新された各クラスタに、クラスタ配列の順番に対応するように、全クラスタを通して一意的な連続番号であるクラスタ番号を割り振り、クラスタ平均と共に、クラスタ管理情報１１２で管理する。このとき割り振られる番号は、ステップ４１０で取得した最近接クラスタの集合Ｃ*に含まれるクラスタのクラスタ番号である。また、クラスタメンバ数の上限を超えたためにクラスタの分割が行われた場合は、増加したクラスタの数だけ新規にクラスタ番号を割り当てる。
【００８６】
最後に、クラスタ数が特定の数の場合、全クラスタのクラスタ平均とクラスタ番号の組をクラスタ情報として保存する。本実施の形態では、クラスタ数が２のｌ乗（ｌは自然数）の時に保存することとする。
【００８７】
以下では、現在のクラスタ平均と逐次クラスタリングの結果として得られた過去クラスタ平均の２乗距離の総和を表す項をエネルギー関数に加える理由について、詳細に説明する。
【００８８】
まず、クラスタ配列の近傍領域に類似したクラスタが集まり、類似していないクラスタ同士がクラスタ配列の中で離れた領域に配置されているという関係が全てのクラスタに対して成立している理想的なクラスタ配列について考える。理想的なクラスタ配列に含まれる各クラスタについて、ベクトル空間内におけるクラスタ平均ベクトル同士の距離とクラスタ配列上の距離との関係を図５に示す。ここで、クラスタ配列上の距離とは、クラスタ配列の配列番号の差分を表す。さらに、図５に示す関係が成立している理想的なクラスタ配列が持つ階層的な構造を図６に表す。ここでは例として、クラスタ数Ｎcが１２の時について示す。最下層の矩形（６３０）が理想状態のクラスタ配列のクラスタ平均を表す。上層のクラスタ平均の平均値（６１０、６２０）とは、下層のクラスタ配列を複数の領域に区切った際に、各領域に含まれるクラスタ平均の平均値を表す。ここで、各層のクラスタ平均の平均値同士は、最下層のクラスタ配列と同様に図５に示す関係が成立し、このような関係は階層的に成立していると考えられる。
【００８９】
ここで、理想的な状態のクラスタ配列から得られるクラスタ平均の平均値は、画像特徴量分布全体を、クラスタ平均の平均値の個数と同じ数に分割する最適なクラスタリング結果とほぼ等しいと仮定することができる。例えば、クラスタ平均の平均値の数が４つならば、そのときのクラスタ平均の平均値は、画像特徴量ベクトルのベクトル空間全体を４つに分割するクラスタリング結果から得られるクラスタ平均に等しいと見做せる。なぜならば、理想状態のクラスタ平均の平均値は、画像特徴量の分布にしたがって、クラスタ配列を適切に分割しているからである。
【００９０】
したがって、クラスタ平均の平均値を事前に知ることが出来れば、各クラスタ平均の平均値を基準として、それらの値に距離が近いクラスタ平均を持つクラスタを各クラスタ平均の平均値に対応する領域に集めることができる。これは、クラスタ平均とクラスタ平均の平均値とのベクトル間距離をエネルギー関数に加えることに相当する。この操作によって、実際にクラスタを配置する際に、クラスタ配列全体における凡その位置を決定することが可能になると考えられる。
【００９１】
しかしながら、図６に示す構造は理想状態におけるものであるため、クラスタ平均の平均値は本質的に未知である。それゆえに、何らかの手段を用いてクラスタ平均の平均値を求める必要がある。
【００９２】
そこで、前述したk-means法を用いた逐次クラスタリング処理に着目する。逐次クラスタリング処理では、新規データを逐次的に登録する際に、部分的なクラスタリングを繰り返し行うことによって、全体のクラスタリングを実行する。また、クラスタメンバ数の上限を予め決めているため、データ数が増加するにつれてクラスタ数も同様に増加するという特徴を持つ。
【００９３】
ここで得られるクラスタ平均の系列は、登録データ数が増加してクラスタ数が増えるにつれて、画像特徴量の分布全体を粗く近似している状態から、細かく近似している状態になるとみなせる。つまり、特徴量分布中において、画像特徴量が多く存在している領域には多くのクラスタ平均が存在し、逆に画像特徴量があまり存在していない領域には少数のクラスタ平均しか存在しないと言える。これは特徴量分布全体を、各分割領域内の画像特徴量の生起確率を一定とするベクトル量子化によって、離散的に表すことと等しいと考えることができる。よって、登録するデータのランダム性を仮定すると、逐次クラスタリングの結果として得られるクラスタ平均は、全画像特徴量をクラスタリングした結果の近似値を与えると考えることができる。
【００９４】
したがって、画像特徴量分布全体を理想的な状態のクラスタ平均の平均値の個数と同じ数に分割する逐次クラスタリングの結果として得られるクラスタ平均を、理想的な状態のクラスタ平均の平均値の近似値として用いることができる。
【００９５】
以上のことから、クラスタ平均と逐次クラスタリングの結果として得られた過去クラスタ平均の２乗距離の総和を表す項をエネルギー関数に加えれば、類似したクラスタ同士をクラスタ配列上で近傍に配置し、類似していないクラスタ同士はクラスタ配列上で遠い領域に配置することができる。
【００９６】
図７は、本発明の実施の形態において実行されるクラスタ位置の再配列の処理を示すフローチャートである。ここでは、エネルギー関数計算部３１５、データ格納部３１６、で実行される処理について、詳細に説明する。図７に示す処理は、検索サーバプロセス１１１を実現するサーバ・プログラムの一部として実行される。したがって、図７に示す処理は、ＣＰＵ１５２によって実行される。
【００９７】
まず、ＣＰＵ１５２は、現在更新対象となっている近接クラスタの集合Ｃ*から、式（３）によって算出されるエネルギーの減少量が最大となるクラスタの組を探す（Ｓ７１０）。次に、ＣＰＵ１５２は、ステップ７１０の条件に該当するクラスタの組を発見したか否かを判定する（Ｓ７２０）。該当するクラスタの組が発見されない場合、現在のクラスタの配列のエネルギーが最も小さく、各クラスタは最適に配置されていると考えられるため、処理を終了する。
【００９８】
一方、該当するクラスタの組が発見された場合、ＣＰＵ１５２は、その位置を交換することによって配列を更新し（Ｓ７３０）、次のクラスタの組を探すためにステップ７１０に戻る。最終的には、こうして得られた配列上の位置に従って、クラスタメンバの特徴量ベクトルをハードディスク１５４上へ保存する。さらに、クラスタ数が２のｌ乗（ｌは自然数）の場合（Ｓ７４０）、クラスタ情報としてクラスタ平均とクラスタ位置の組をハードディスク１５４上のクラスタ管理情報１１５へ保存する（Ｓ７５０）。尚、クラスタ数が２のｌ乗ではなく、他の特定の数の時に保存しても良い。
【００９９】
本発明と特許文献２に示される手法によって実現されるクラスタ配列の違いを明確化するために５００万件のベクトルデータを用いて実験を行い、１２２４５個のクラスタからなるクラスタ配列を得た。図５と同様に、クラスタ配列内の各クラスタについて、ベクトル空間内におけるクラスタ平均ベクトル同士の距離とクラスタ配列上の距離との関係を、図８、図９、図１０、図１１に示す。これは、クラスタ配列上の距離が等しいクラスタの組を求め、各組のクラスタ同士のクラスタ平均のベクトル間距離を計算し、それらの平均値をプロットしたものである。縦軸がクラスタ平均のベクトル間距離であり、横軸がクラスタ配列上の距離である。
【０１００】
図８は、特許文献２に示される手法によって実現されるクラスタ同士の関係を示すものであり、クラスタ数Ｎcが、５１２、２０４８、８１９２、１２２４５の時を示している。また、図９は、クラスタ配列上の距離が５０以内のクラスタ同士の関係のみを拡大表示したものである。
【０１０１】
図８、図９のグラフから、クラスタ配列上の距離が約１０より近い場所に配置されているクラスタのクラスタ平均同士の距離の平均値は、クラスタ配列上の距離に比例していることが分かる。また、クラスタ配列上の距離が約１０より遠い場所に配置されているクラスタのクラスタ平均同士の距離の平均値が、ほぼ一定になっていることが分かる。複数データの平均値が一定ということは、それらのデータは、クラスタ配列上の距離と関係なく、ほぼランダムに近い状態で分布していると考えることができる。したがって、特許文献２に示される手法では、類似度の大きいクラスタ同士が隣接するように配置することはある程度可能だが、クラスタ配列上の距離が一定以上離れたクラスタ同士の類似度は、クラスタ配列上の距離に依存せずに、ランダムに等しい状態になってしまう。さらに、クラスタ平均同士の距離の平均値がクラスタ配列上の距離と比例している範囲は、全クラスタ数に関係なく一定であることが図９から分かる。したがって、近傍に集まるクラスタの数は、全クラスタ数が増加するにつれて相対的に少なくなると言える。
【０１０２】
図１０は、本実施の形態に示される手法によって実現されるクラスタ同士の関係を示すものであり、クラスタ数Ｎcが、５１２、２０４８、８１９２、１２２４５、の時を示している。また、図１１は、クラスタ配列上の距離が５０以内のクラスタ同士の関係のみを拡大表示したものである。これは特許文献２の手法を用いた実験と同様に、クラスタ配列上の距離が等しいクラスタの組を求め、各組のクラスタ同士のクラスタ平均間の距離を計算し、それらの平均値をプロットしたものである。縦軸がクラスタ平均の距離であり、横軸がクラスタ配列上の距離である。
【０１０３】
図１０、図１１のグラフから、クラスタ平均同士の距離の平均値がクラスタ配列上の距離と比例している範囲が、Ｎcが５１２の時は約１００、Ｎcが２０４８の時は約４００、Ｎcが８１９２の時は約１６００、Ｎcが１２２４５の時は約２４００、というように、全クラスタ数に比例して増加している様子が分かる。したがって、近傍に集まるクラスタの数は、全クラスタ数に依存してＯ（Ｎ）であると言える。
【０１０４】
以上の本発明の実施の形態は、検索対象のベクトルデータが画像の特徴量ベクトルである場合を例として説明したが、本発明は、いかなる種類のベクトルデータの類似検索に対しても適用することができる。類似画像検索以外の類似データ検索の例として、連想文書検索装置がある。連想文書検索装置は、予め検索対象となる文書群を形態素解析し、文書の意味を各単語の意味を単位ベクトルとし、各文書の意味をそれらの総和として多次元ベクトルに展開し、ある文書と他の文書との類似をそれら多次元ベクトルの距離で判定する。よって、ユーザが入力した問い合わせ文と最も近いベクトルを持つ文書を検索することが可能になる。
【図面の簡単な説明】
【０１０５】
【図１】本発明の類似検索システムの構成例を示すブロック図。
【図２】本発明の類似検索システムにおける類似データ検索処理の構成例を示すブロック図。
【図３】本発明の類似検索システムにおける新規データ登録処理の構成例を示すブロック図。
【図４】データ登録時に実行される処理を示すフローチャート。
【図５】クラスタ配列に含まれる任意のクラスタについての、クラスタ平均ベクトル同士の距離とクラスタ配列上の距離との理想的な関係を示す図。
【図６】図５に示す理想的な関係が成立しているクラスタ配列の持つ構造を表す図。
【図７】クラスタ位置の再配列の処理を示すフローチャート。
【図８】従来法によって得られるクラスタ配列に含まれる任意のクラスタについての、クラスタ平均ベクトル同士の距離とクラスタ配列上の距離との関係を示す図。
【図９】図８の近傍領域を拡大して示した図。
【図１０】本発明によって得られるクラスタ配列に含まれる任意のクラスタについての、クラスタ平均ベクトル同士の距離とクラスタ配列上の距離との関係を示す図。
【図１１】図１０の近傍領域を拡大して示した図。
【符号の説明】
【０１０６】
１１０：サーバ計算機
１１１：検索サーバプロセス
１１２：クラスタ管理情報
１１３：クラスタ情報
１１４：クラスタメンバの特徴量データ
１１５：記録されたクラスタ管理情報
１２０：通信基盤
１３０：クライアント計算機
１３１，１５２：ＣＰＵ
１３２，１５３：メモリ
１３３，１５１：インターフェース
１３４：入力装置
１３５：出力装置
１４０：画像サーバ
１５４：ハードディスク
２１０：画像入力部
２１１：画像特徴量抽出部
２１２：類似クラスタ検索部
２１３：類似特徴量検索部
２１４：検索結果出力部
３１０：画像入力部
３１１：画像特徴量抽出部
３１２：類似クラスタ検索部
３１３：クラスタリング部
３１４：クラスタ分割部
３１５：エネルギー関数計算部
３１６：データ格納部
６１０，６２０：理想的なクラスタ配列のクラスタ平均の平均値
６３０：理想的なクラスタ配列のクラスタ平均
【図１】
0005155025.tif 000006
【図２】
0005155025.tif 000007
【図３】
0005155025.tif 000008
【図４】
0005155025.tif 000009
【図５】
0005155025.tif 000010
【図６】
0005155025.tif 000011
【図７】
0005155025.tif 000012
【図８】
0005155025.tif 000013
【図９】
0005155025.tif 000014
【図１０】
0005155025.tif 000015
【図１１】
0005155025.tif 000016