(57)【要約】【課題】高速に、クエリ特徴ベクトルと類似するリファレンス特徴ベクトルを抽出することができる。【解決手段】サブベクトル分割部３０で特徴ベクトルを分割し、クラスタリング部３２で、サブベクトル毎に、複数のリファレンス特徴ベクトルのサブベクトルを複数のクラスタに分類し、複数のクラスタの各々についてセントロイドを求め、サブベクトル類似度算出部３６で、クエリ特徴ベクトルのサブベクトルの各々について、複数のセントロイドの各々との類似度を算出し、セントロイドソート部３８で、類似度順にセントロイドをソートし、類似特徴ベクトル抽出部４０で、類似度の降順に、セントロイドのクラスタに属するリファレンス特徴ベクトルＩＤを取得し、取得したリファレンス特徴ベクトルＩＤに対してカウントアップを行い、所定のカウント数に到達したリファレンス特徴ベクトルＩＤを抽出する。【選択図】図１
2015207047.tif 000002
【特許請求の範囲】
【請求項１】
特徴ベクトルである複数のリファレンス特徴ベクトルから、前記特徴ベクトルであるクエリ特徴ベクトルとの類似度が高いリファレンス特徴ベクトルを抽出する類似特徴抽出装置であって、
入力された前記複数のリファレンス特徴ベクトルを受け付けるリファレンス特徴ベクトル入力部と、
入力された前記クエリ特徴ベクトルを受け付けるクエリ特徴ベクトル入力部と、
前記リファレンス特徴ベクトル入力部により受け付けた前記複数のリファレンス特徴ベクトルと前記クエリ特徴ベクトルにより受け付けたクエリ特徴ベクトルとの各々を、複数のサブベクトルに分割するサブベクトル分割部と、
前記複数のサブベクトルの各々について、前記サブベクトル分割部により分割された前記複数のリファレンス特徴ベクトルの各々の前記サブベクトルを、複数のクラスタに分類し、前記複数のクラスタの各々について、前記クラスタのセントロイドを求めるクラスタリング部と、
前記複数のサブベクトルの各々について、前記サブベクトル分割部により分割された前記クエリ特徴ベクトルの各々の前記サブベクトルと、前記クラスタリング部により求めた前記サブベクトルの前記複数のクラスタの前記セントロイドの各々との類似度を算出するサブベクトル類似度算出部と、
前記サブベクトル類似度算出部により前記複数のサブベクトルの各々について算出した前記複数のクラスタのセントロイドの各々との類似度に基づいて、前記セントロイドを類似度順にソートするセントロイドソート部と、
前記セントロイドソート部によるソート結果に基づいて、類似度の降順に前記セントロイドのクラスタに属するリファレンス特徴ベクトルの各々に対してカウントアップを行い、予め定められたカウント数に到達した所定個のリファレンス特徴ベクトルを、前記クエリ特徴ベクトルとの類似度が高いリファレンス特徴ベクトルとして抽出する類似特徴ベクトル抽出部と、
を備える類似特徴抽出装置。
【請求項２】
前記複数のサブベクトルの各々について、前記サブベクトル類似度算出部により前記サブベクトルについて算出した前記複数のクラスタのセントロイドの各々との類似度の分布に基づいて、前記サブベクトルについて算出した前記複数のクラスタのセントロイドの各々との類似度を補正するサブベクトル類似度補正部を更に含み、
前記セントロイドソート部は、前記サブベクトル類似度補正部により前記複数のサブベクトルの各々について補正した前記複数のクラスタのセントロイドの各々との類似度に基づいて、前記セントロイドを類似度順にソートする請求項１記載の類似特徴抽出装置。
【請求項３】
特徴ベクトルである複数のリファレンス特徴ベクトルから、前記特徴ベクトルであるクエリ特徴ベクトルとの類似度が高いリファレンス特徴ベクトルを抽出する類似特徴抽出方法であって、
リファレンス特徴ベクトル入力部が、入力された前記複数のリファレンス特徴ベクトルを受け付けるステップと、
サブベクトル分割部が、前記リファレンス特徴ベクトル入力部により受け付けた前記複数のリファレンス特徴ベクトルの各々を、複数のサブベクトルに分割するステップと、
クラスタリング部が、前記複数のサブベクトルの各々について、前記サブベクトル分割部により分割された前記複数のリファレンス特徴ベクトルの各々の前記サブベクトルを、複数のクラスタに分類し、前記複数のクラスタの各々について、前記クラスタのセントロイドを求めるステップと、
クエリ特徴ベクトル入力部が、入力された前記クエリ特徴ベクトルを受け付けるステップと、
前記サブベクトル分割部が、前記クエリ特徴ベクトル入力部により受け付けたクエリ特徴ベクトルを複数のサブベクトルに分割するステップと、
サブベクトル類似度算出部が、前記複数のサブベクトルの各々について、前記サブベクトル分割部により分割された前記クエリ特徴ベクトルの各々の前記サブベクトルと、前記クラスタリング部により求めた前記サブベクトルの前記複数のクラスタの前記セントロイドの各々との類似度を算出するステップと、
セントロイドソート部が、前記サブベクトル類似度算出部により前記複数のサブベクトルの各々について算出した前記複数のクラスタのセントロイドの各々との類似度に基づいて、前記セントロイドを類似度順にソートするステップと、
類似特徴ベクトル抽出部が、前記セントロイドソート部によるソート結果に基づいて、類似度の降順に前記セントロイドのクラスタに属するリファレンス特徴ベクトルの各々に対してカウントアップを行い、予め定められたカウント数に到達した所定個のリファレンス特徴ベクトルを、前記クエリ特徴ベクトルとの類似度が高いリファレンス特徴ベクトルとして抽出するステップと、
を含む類似特徴抽出方法。
【請求項４】
サブベクトル類似度補正部によって、前記複数のサブベクトルの各々について、前記サブベクトル類似度算出部により前記サブベクトルについて算出した前記複数のクラスタのセントロイドの各々との類似度の分布に基づいて、前記サブベクトルについて算出した前記複数のクラスタのセントロイドの各々との類似度を補正するステップを更に含み、
前記セントロイドソート部によって前記セントロイドを類似度順にソートするステップは、前記サブベクトル類似度補正部により前記複数のサブベクトルの各々について補正した前記複数のクラスタのセントロイドの各々との類似度に基づいて、前記セントロイドを類似度順にソートする請求項３記載の類似特徴抽出方法。
【請求項５】
コンピュータを、請求項１又は請求項２に記載の類似特徴抽出装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似特徴抽出装置、方法、及びプログラムに係り、特に、複数のリファレンス特徴ベクトルから、クエリ特徴ベクトルと類似するリファレンス特徴ベクトルを抽出するための類似特徴抽出装置、方法及びプログラムに関する。
【背景技術】
【０００２】
従来より、画像などのメディアの特徴を複数の数値列からなる特徴ベクトルで表現し、ベクトル間の類似度をメディア間の類似度として算出する手法が知られている。
【０００３】
例えば、色情報に基づき画像間の類似度を算出する手法として、色ヒストグラムを用いた手法がある（非特許文献１）。この手法では、画像を構成する画素の色を分類し、色別にその色に対応する画素数の割合を並べたものを特徴ベクトルとしている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】M.J. Swain and D.H. Ballard. “Color indexing,” International Journal of Computer Vision,Vol.7, No.1, pp. 11-32, 1991.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１の手法では、画像から作成される色ヒストグラムの特徴ベクトルは、通常数十〜数百次元となる。そのため、２枚の画像の特徴ベクトル間の類似度を算出するのにかかる時間はわずかである。しかし、この処理にかかる時間は画像の枚数に比例し、画像が非常に大量に存在する場合には無視することができないという問題がある。
【０００６】
例えば、特徴ベクトルの次元数が１００次元、リファレンス画像の枚数が１００万枚であった場合には、入力されたクエリ画像との特徴ベクトルの類似度を算出するためには１億回以上の四則演算が必要になる。そのため、リファレンス画像が大量にある場合に高速な類似度算出を可能にするためには、類似度算出にかかる時間を短縮することが課題となる。
【０００７】
本発明は、上記問題点を解決するために成されたものであり、リファレンス特徴ベクトルの数が多い場合であっても、高速に、クエリ特徴ベクトルと類似するリファレンス特徴ベクトルを抽出することができる類似特徴抽出装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、第１の発明に係る類似特徴抽出装置は、特徴ベクトルである複数のリファレンス特徴ベクトルから、前記特徴ベクトルであるクエリ特徴ベクトルとの類似度が高いリファレンス特徴ベクトルを抽出する類似特徴抽出装置であって、入力された前記複数のリファレンス特徴ベクトルを受け付けるリファレンス特徴ベクトル入力部と、入力された前記クエリ特徴ベクトルを受け付けるクエリ特徴ベクトル入力部と、前記リファレンス特徴ベクトル入力部により受け付けた前記複数のリファレンス特徴ベクトルと前記クエリ特徴ベクトルにより受け付けたクエリ特徴ベクトルとの各々を、複数のサブベクトルに分割するサブベクトル分割部と、前記複数のサブベクトルの各々について、前記サブベクトル分割部により分割された前記複数のリファレンス特徴ベクトルの各々の前記サブベクトルを、複数のクラスタに分類し、前記複数のクラスタの各々について、前記クラスタのセントロイドを求めるクラスタリング部と、前記複数のサブベクトルの各々について、前記サブベクトル分割部により分割された前記クエリ特徴ベクトルの各々の前記サブベクトルと、前記クラスタリング部により求めた前記サブベクトルの前記複数のクラスタの前記セントロイドの各々との類似度を算出するサブベクトル類似度算出部と、前記サブベクトル類似度算出部により前記複数のサブベクトルの各々について算出した前記複数のクラスタのセントロイドの各々との類似度に基づいて、前記セントロイドを類似度順にソートするセントロイドソート部と、前記セントロイドソート部によるソート結果に基づいて、類似度の降順に前記セントロイドのクラスタに属するリファレンス特徴ベクトルの各々に対してカウントアップを行い、予め定められたカウント数に到達した所定個のリファレンス特徴ベクトルを、前記クエリ特徴ベクトルとの類似度が高いリファレンス特徴ベクトルとして抽出する類似特徴ベクトル抽出部と、を含んで構成されている。
【０００９】
また、第１の発明に係る類似特徴抽出装置において、前記複数のサブベクトルの各々について、前記サブベクトル類似度算出部により前記サブベクトルについて算出した前記複数のクラスタのセントロイドの各々との類似度の分布に基づいて、前記サブベクトルについて算出した前記複数のクラスタのセントロイドの各々との類似度を補正するサブベクトル類似度補正部を更に含み、前記セントロイドソート部は、前記サブベクトル類似度補正部により前記複数のサブベクトルの各々について補正した前記複数のクラスタのセントロイドの各々との類似度に基づいて、前記セントロイドを類似度順にソートしてもよい。
【００１０】
第１の発明に係る類似特徴抽出方法は、特徴ベクトルである複数のリファレンス特徴ベクトルから、前記特徴ベクトルであるクエリ特徴ベクトルとの類似度が高いリファレンス特徴ベクトルを抽出する類似特徴抽出方法であって、リファレンス特徴ベクトル入力部が、入力された前記複数のリファレンス特徴ベクトルを受け付けるステップと、サブベクトル分割部が、前記リファレンス特徴ベクトル入力部により受け付けた前記複数のリファレンス特徴ベクトルの各々を、複数のサブベクトルに分割するステップと、クラスタリング部が、前記複数のサブベクトルの各々について、前記サブベクトル分割部により分割された前記複数のリファレンス特徴ベクトルの各々の前記サブベクトルを、複数のクラスタに分類し、前記複数のクラスタの各々について、前記クラスタのセントロイドを求めるステップと、クエリ特徴ベクトル入力部が、入力された前記クエリ特徴ベクトルを受け付けるステップと、前記サブベクトル分割部が、前記クエリ特徴ベクトル入力部により受け付けたクエリ特徴ベクトルを複数のサブベクトルに分割するステップと、サブベクトル類似度算出部が、前記複数のサブベクトルの各々について、前記サブベクトル分割部により分割された前記クエリ特徴ベクトルの各々の前記サブベクトルと、前記クラスタリング部により求めた前記サブベクトルの前記複数のクラスタの前記セントロイドの各々との類似度を算出するステップと、セントロイドソート部が、前記サブベクトル類似度算出部により前記複数のサブベクトルの各々について算出した前記複数のクラスタのセントロイドの各々との類似度に基づいて、前記セントロイドを類似度順にソートするステップと、類似特徴ベクトル抽出部が、前記セントロイドソート部によるソート結果に基づいて、類似度の降順に前記セントロイドのクラスタに属するリファレンス特徴ベクトルの各々に対してカウントアップを行い、予め定められたカウント数に到達した所定個のリファレンス特徴ベクトルを、前記クエリ特徴ベクトルとの類似度が高いリファレンス特徴ベクトルとして抽出するステップと、を含んで実行することを特徴とする。
【００１１】
また、第１の発明に係る類似特徴抽出方法において、サブベクトル類似度補正部によって、前記複数のサブベクトルの各々について、前記サブベクトル類似度算出部により前記サブベクトルについて算出した前記複数のクラスタのセントロイドの各々との類似度の分布に基づいて、前記サブベクトルについて算出した前記複数のクラスタのセントロイドの各々との類似度を補正するステップを更に含み、前記セントロイドソート部によって前記セントロイドを類似度順にソートするステップは、前記サブベクトル類似度補正部により前記複数のサブベクトルの各々について補正した前記複数のクラスタのセントロイドの各々との類似度に基づいて、前記セントロイドを類似度順にソートしてもよい。
【発明の効果】
【００１２】
本発明の類似特徴抽出装置、方法、及びプログラムによれば、複数のリファレンス特徴ベクトルのサブベクトルを複数のクラスタに分類し、複数のクラスタの各々についてセントロイドを求め、クエリ特徴ベクトルのサブベクトルの各々について、複数のセントロイドの各々との類似度を算出し、類似度順にセントロイドをソートし、類似度の降順に、セントロイドのクラスタに属するリファレンス特徴ベクトルに対してカウントアップを行い、所定のカウント数に到達したリファレンス特徴ベクトルを抽出することで、リファレンス特徴ベクトルの数が多い場合であっても、高速に、クエリ特徴ベクトルと類似するリファレンス特徴ベクトルを抽出することができる、という効果が得られる。
【図面の簡単な説明】
【００１３】
【図１】本発明の第１の実施の形態に係る類似特徴抽出装置の一構成例を示すブロック図である。
【図２】特徴ベクトルをサブベクトルに分割する処理を示す概念図である。
【図３】サブベクトルのクラスタリング結果を示す概念図である。
【図４】サブベクトルのクラスタリング結果の管理テーブルを示す概念図である。
【図５】サブベクトルの類似度を算出する処理を示す概念図である。
【図６】セントロイドのソート及びカウントアップの処理を示す概念図である。
【図７】本発明の第１及び第２の実施の形態に係る類似特徴抽出装置のリファレンス特徴ベクトル登録処理ルーチンの内容を示すブロック図である。
【図８】本発明の第１の実施の形態に係る類似特徴抽出装置の類似特徴抽出処理ルーチンの内容を示すブロック図である。
【図９】本発明の第２の実施の形態に係る類似特徴抽出装置の一構成例を示すブロック図である。
【図１０】サブベクトルの類似度を補正する処理を示す概念図である。
【図１１】補正後のセントロイドのソート及びカウントアップの処理を示す概念図である。
【図１２】本発明の第２の実施の形態に係る類似特徴抽出装置の類似特徴抽出処理ルーチンの内容を示すブロック図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１５】
＜第１の実施の形態に係る類似特徴抽出装置の構成＞
【００１６】
第１の実施の形態に係る類似特徴抽出装置の構成について説明する。図１に示すように、本発明に係る類似特徴抽出装置１０は、ＣＰＵと、ＲＡＭと、後述するリファレンス特徴ベクトル登録処理ルーチン及び類似特徴抽出処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この類似特徴抽出装置１０は、機能的には図１に示すように演算部２０と、リファレンス特徴ベクトル入力部２２と、クエリ特徴ベクトル入力部２４と、出力部５０とを備えている。
【００１７】
リファレンス特徴ベクトル入力部２２は、特徴ベクトルである複数のリファレンス特徴ベクトルを受け付ける。また、受け付けた複数のリファレンス特徴ベクトルはメモリ（図示省略）に記憶される。なお、特徴ベクトルとしては、色ヒストグラムや局所特徴量など、数値列として表現された任意の特徴量を用いることができる。
【００１８】
クエリ特徴ベクトル入力部２４は、リファレンス特徴ベクトルと同じ次元数の特徴ベクトルであるクエリ特徴ベクトルを受け付ける。また、クエリ特徴ベクトル入力部２４は、演算部２０の類似特徴ベクトル抽出部４０により抽出するリファレンス特徴ベクトルの出力数を指定する設定値の入力を受け付ける。なお、出力数の設定値の入力を受け付けるのではなく、出力数を予め設定しておいてもよい。
【００１９】
演算部２０は、サブベクトル分割部３０と、クラスタリング部３２と、セントロイド記憶部３４と、サブベクトル類似度算出部３６と、セントロイドソート部３８と、類似特徴ベクトル抽出部４０とを含んで構成されている。
【００２０】
サブベクトル分割部３０は、受け付けた複数のリファレンス特徴ベクトルとクエリ特徴ベクトルとの各々を複数のサブベクトルに分割する。特徴ベクトルの次元数およびサブベクトルの分割数を、任意の値に設定してもよい。本実施の形態では、特徴ベクトルの次元数を９次元、サブベクトルの分割数を３とする。図２は、特徴ベクトルからサブベクトルへの分割処理の例である。
【００２１】
クラスタリング部３２は、サブベクトル毎に、サブベクトル分割部３０において分割された複数のリファレンス特徴ベクトルの各々の当該サブベクトルについて、クラスタリングを行って、当該サブベクトルの各々を、複数のクラスタの何れかに分類する。クラスタリングの際のクラスタ数は、任意の値に設定することができる。本実施の形態では、クラスタ数を２とする。そして、クラスタリング部３２は、複数のクラスタの各々について、クラスタのセントロイドを求める。本実施の形態において、セントロイドは、クラスタに属するサブベクトルの重心を求めたベクトルである。図３は、サブベクトルの各々をクラスタリングした結果の例である。
【００２２】
次に、クラスタリング部３２は、サブベクトル毎のクラスタリングの結果を、セントロイド記憶部３４に格納する。本実施の形態では、クラスタリングの結果は、図４（Ａ）、（Ｂ）に示すように、セントロイド管理テーブル及びセントロイド―リファレンス特徴ベクトル管理テーブルの形式で格納される。セントロイド管理テーブルには、サブベクトルＩＤ、クラスタのセントロイドＩＤ、及び当該クラスタのセントロイドの組み合わせが格納される。セントロイド―リファレンス特徴ベクトル関係管理テーブルには、サブベクトルＩＤ、クラスタのセントロイドＩＤ、及び当該クラスタに属するリファレンス特徴ベクトルＩＤリストの組み合わせが格納される。
【００２３】
なお、図４に示したクラスタリング結果の格納形式は一例であり、属性や名称が異なっていてもよい。また、テキストファイル形式などのテーブル以外の形式で保存されていてもよい。
【００２４】
サブベクトル類似度算出部３６は、サブベクトル分割部３０で分割されたクエリ特徴ベクトルのサブベクトルの各々について、当該サブベクトルと、セントロイド記憶部３４に記憶している当該サブベクトルの各クラスタのセントロイドの各々とに基づいて、各クラスタのセントロイドの各々との類似度を算出する。
【００２５】
類似度は従来既知の手法により算出したものを用いればよい。本実施の形態では、類似度尺度として、Ｈｉｓｔｏｇｒａｍ Ｉｎｔｅｒｓｅｃｔｉｏｎを利用する。当該類似度尺度において、ｎ次元の特徴ベクトルＶ１およびＶ２の類似度Ｒ（Ｖ１，Ｖ２）の値は以下の（１）式によって算出される。ただし、特徴ベクトルはサブベクトルへの分割前に正規化されており、Ｖｉ１，Ｖｉ２はそれぞれ、Ｖ１，Ｖ２におけるｉ次元目の値を表す。
【００２６】
【数１】
2015207047.tif 000003
【００２７】
また、Ｌ２ノルムなどの距離尺度を類似度尺度として用いてもよい。当該距離尺度において、ｎ次元の特徴ベクトルＶ１およびＶ２の距離Ｄ（Ｖ１，Ｖ２）の値は以下の（２）式によって算出される。
【００２８】
【数２】
2015207047.tif 000004
【００２９】
なお、距離尺度を用いた場合、距離が近いほど類似度が高い。そのため、後述するセントロイドソート部３８において類似度の降順にソートする際には、距離の近い順にソートを行う。
【００３０】
図５は、クエリ特徴ベクトルのサブベクトルの各々と、各クラスタのセントロイドの各々との類似度を算出した例である。
【００３１】
セントロイドソート部３８は、サブベクトル類似度算出部３６により複数のサブベクトルの各々について算出した複数のクラスタのセントロイドの各々との類似度に基づいて、全てのセントロイドを類似度の降順にソートする。
【００３２】
類似特徴ベクトル抽出部４０は、セントロイドソート部３８によるソート結果と、セントロイド記憶部３４に記憶しているセントロイド−リファレンス特徴ベクトル関係管理テーブルとに基づいて、類似度の降順に、セントロイドのクラスタに属するリファレンス特徴ベクトルに対してカウントアップを行い、カウント数に基づいて、リファレンス特徴ベクトルを抽出する。具体的な処理としては、類似度の降順に、セントロイドを選択し、選択したセントロイドのクラスタに属するリファレンス特徴ベクトルＩＤを、セントロイド記憶部３４のセントロイド−リファレンス特徴ベクトル関係管理テーブルから取得し、取得したリファレンス特徴ベクトルＩＤの各々に対してカウントアップを行う。カウント数がサブベクトルの分割数と同値に到達したリファレンス特徴ベクトルＩＤが存在する場合には、当該リファレンス特徴ベクトルＩＤを、抽出結果として追加する。以上の、セントロイドの取得、リファレンス特徴ベクトルＩＤのカウントアップ、抽出結果への追加の処理を繰り返す。そして、全てのセントロイドについて処理を終えるか、抽出結果として追加されたリファレンス特徴ベクトルＩＤの数が、指定された出力数になった場合に、抽出結果として追加されたリファレンス特徴ベクトルＩＤを、出力部５０により出力する。
【００３３】
ここで、６つのセントロイドのソート結果を用いて、リファレンス特徴ベクトルを抽出する例を、図６を用いて説明する。（１）において、最も類似度が高かった、サブベクトルＩＤ＝３、セントロイドＩＤ＝２のクラスタに属するリファレンス特徴ベクトルＩＤ２及びＩＤ３を取得する。そして、リファレンス特徴ベクトルＩＤ２及びＩＤ３のカウント数をそれぞれ０から１にカウントアップする。同様の処理を（２）、（３）において繰り返すと、（３）の処理後には、リファレンス特徴ベクトルＩＤ３のカウント数がサブベクトルの分割数と同じ３回に到達する。そこで、分割数と同じカウント数となったリファレンス特徴ベクトルＩＤ３を抽出結果として追加する。次に、（４）の処理後には、同様にリファレンス特徴ベクトルＩＤ２が抽出結果として追加される。このとき、出力数の設定値が２であったとする。この場合、抽出結果として追加された数が、設定された出力数に達したため、（５）及び（６）については処理をせず、リファレンス特徴ベクトルＩＤ２及びＩＤ３を、類似度が高いリファレンス特徴ベクトルの抽出結果として、出力部５０により出力する。
【００３４】
＜第１の実施の形態に係る類似特徴抽出装置の作用＞
【００３５】
次に、第１の実施の形態に係る類似特徴抽出装置１０の作用について、まず、リファレンス特徴ベクトル登録処理ルーチンについて説明する。リファレンス特徴ベクトル入力部２２において複数のリファレンス特徴ベクトルの入力を受け付けると、類似特徴抽出装置１０は、図７に示すリファレンス特徴ベクトル登録処理ルーチンを実行する。
【００３６】
まず、ステップＳ１００では、リファレンス特徴ベクトル入力部２２において受け付けたリファレンス特徴ベクトルを取得する。
【００３７】
次に、ステップＳ１０２では、ステップＳ１００で取得したリファレンス特徴ベクトルを複数のサブベクトルに分割する。ステップＳ１０４では、全てのリファレンス特徴ベクトルについてステップＳ１０２の処理が終了したかを判定し、終了していなければステップＳ１００へ戻って処理を繰り返し、終了していればステップＳ１０６へ移行する。
【００３８】
次に、ステップＳ１０６では、サブベクトル毎に、ステップＳ１０２で分割した複数のリファレンス特徴ベクトルの当該サブベクトルについて、クラスタリングを行って、当該サブベクトルの各々を複数のクラスタの何れかに分類し、複数のクラスタの各々について、クラスタのセントロイドを求める。
【００３９】
そして、ステップＳ１０８において、ステップＳ１０６におけるサブベクトル毎のクラスタリング結果をセントロイド記憶部３４に記憶し、処理を終了する。
【００４０】
次に、類似特徴抽出処理ルーチンについて説明する。クエリ特徴ベクトル入力部２４においてクエリ特徴ベクトル及び出力数の設定値の入力を受け付けると、類似特徴抽出装置１０は、図８に示す類似特徴抽出処理ルーチンを実行する。
【００４１】
まず、ステップＳ２００では、クエリ特徴ベクトル入力部２４において入力を受け付けたクエリ特徴ベクトルを取得する。次に、ステップＳ２０２では、ステップＳ２００で取得したクエリ特徴ベクトルを複数のサブベクトルに分割する。
【００４２】
ステップＳ２０４では、ステップＳ２０２で分割されたクエリ特徴ベクトルの複数のサブベクトルの各々について、当該サブベクトルと、セントロイド記憶部３４に記憶している当該サブベクトルの複数のクラスタに対する複数のセントロイドの各々との類似度を算出する。
【００４３】
ステップＳ２０６では、ステップＳ２０４で、複数のサブベクトルの各々について算出した複数のクラスタのセントロイドの各々との類似度に基づいて、全てのセントロイドを類似度の降順にソートする。
【００４４】
ステップＳ２０８では、ステップＳ２０６によるソート結果とセントロイド記憶部３４に記憶しているセントロイド−リファレンス特徴ベクトル関係管理テーブルとに基づいて、類似度の降順にセントロイドを選択し、選択したセントロイドのクラスタに属するリファレンス特徴ベクトルＩＤを、セントロイド記憶部３４のセントロイド−リファレンス特徴ベクトル関係管理テーブルから取得する。ステップＳ２１０では、ステップＳ２０８で取得したリファレンス特徴ベクトルＩＤの各々に対してカウントアップを行う。
【００４５】
そして、ステップＳ２１２では、カウント数が分割数と同値となるリファレンス特徴ベクトルＩＤがあるかを判定し、ない場合にはステップＳ２０８へ戻って処理を繰り返し、ある場合には、ステップＳ２１４へ移行する。
【００４６】
ステップＳ２１４では、リファレンス特徴ベクトルＩＤのカウント数が分割数と同値となるリファレンス特徴ベクトルＩＤを抽出結果として追加する。次に、ステップＳ２１６では、ステップＳ２１４で抽出結果として追加したリファレンス特徴ベクトルＩＤのカウント数が、クエリ特徴ベクトル入力部２４で入力を受け付けて設定した出力数と同値かを判定し、同値でなければステップＳ２１８へ移行し、同値であればステップＳ２２０へ移行する。
【００４７】
ステップＳ２１８では、すべてのセントロイドについてステップＳ２１０の処理を終了したかを判定し、終了していなければステップＳ２０８へ戻って処理を繰り返し、終了していればステップＳ２２０へ移行する。
【００４８】
そして、ステップＳ２２０において、ステップＳ２１４で抽出結果として追加したリファレンス特徴ベクトルＩＤを出力部５０により出力し、処理を終了する。
【００４９】
以上説明したように、第１の実施の形態に係る類似特徴抽出装置によれば、サブベクトル毎に、複数のリファレンス特徴ベクトルのサブベクトルを複数のクラスタに分類し、複数のクラスタの各々についてセントロイドを求め、クエリ特徴ベクトルのサブベクトルの各々について、複数のセントロイドの各々との類似度を算出し、類似度順にセントロイドをソートし、類似度の降順に、セントロイドのクラスタに属するリファレンス特徴ベクトルＩＤを取得し、取得したリファレンス特徴ベクトルＩＤに対してカウントアップを行い、所定のカウント数に到達したリファレンス特徴ベクトルＩＤを抽出することで、リファレンス特徴ベクトルの数が多い場合であっても、高速に、クエリ特徴ベクトルと類似するリファレンス特徴ベクトルを抽出することができる。
【００５０】
＜第２の実施の形態に係る類似特徴抽出装置の構成＞
【００５１】
次に、第２の実施の形態に係る類似特徴抽出装置について説明する。第２の実施の形態では、サブベクトルの類似度を補正するサブベクトル類似度補正部を備えている点が、第１の実施の形態と異なっている。なお、第１の実施の形態に係る類似特徴抽出装置１０と同一の構成となる部分については、同一符号を付して、詳細な説明を省略する。
【００５２】
図９に示すように、第２の実施の形態に係る類似特徴抽出装置２００は、演算部２２０と、リファレンス特徴ベクトル入力部２２と、クエリ特徴ベクトル入力部２４と、出力部５０とを備えている。
【００５３】
演算部２２０は、サブベクトル分割部３０と、クラスタリング部３２と、セントロイド記憶部３４と、サブベクトル類似度算出部３６と、サブベクトル類似度補正部２３０と、セントロイドソート部３８と、類似特徴ベクトル抽出部４０とを含んで構成されている。
【００５４】
サブベクトル間で類似度の分布のばらつきが大きいとき、次のような問題が起きる可能性がある。例えば、図１０に示す、クエリ特徴ベクトルでは、サブベクトルＩＤ＝１及びサブベクトルＩＤ＝２における各クラスタのセントロイドとの類似度が０．１５〜０．２８の範囲をとっているのに対して、サブベクトルＩＤ＝３における各クラスタのセントロイドとの類似度がセントロイドＩＤ＝１、ＩＤ＝２ともに０．００となっている。そのため、このような場合には、サブベクトルＩＤ＝３のセントロイドに対する類似特徴ベクトル抽出部４０における処理順序が遅くなってしまい処理に時間が掛かるだけでなく、類似度の大小が、サブベクトルＩＤ＝３における各クラスタのセントロイドの類似度のみに依存して決まってしまうという問題が起きる。
【００５５】
そこで、本実施の形態では、サブベクトル類似度補正部２３０は、複数のサブベクトルの各々に対し、サブベクトル類似度算出部３６により当該サブベクトルについて算出した複数のクラスタのセントロイドの各々との類似度の分布に基づいて、当該サブベクトルの複数のクラスタの各々について、当該クラスタのセントロイドとの類似度を補正する。
【００５６】
具体的な処理としては、図１０に示すように、サブベクトル毎に、当該サブベクトルについての各クラスタのセントロイドとの類似度のうち、最も高い類似度の値を、各クラスタのセントロイドとの類似度の各々の値から減算した値を、補正後の各クラスタのセントロイドとの類似度の各々の値とする。
【００５７】
図１１に、補正後の類似度を用いて、セントロイドソート部３８におけるセントロイドのソート、及び類似特徴ベクトル抽出部４０におけるリファレンス特徴ベクトルＩＤに対するカウントアップを行った例を示す。サブベクトルの各々の類似度を補正したことにより、サブベクトルＩＤ＝３のセントロイドの処理順序が遅くなることなく、（４）の処理後に、リファレンス特徴ベクトルＩＤ＝３が、最も類似度が高いリファレンス特徴ベクトルの抽出結果として、出力部５０により出力される。
【００５８】
＜第２の実施の形態に係る類似特徴抽出装置の作用＞
【００５９】
次に、第２の実施の形態に係る類似特徴抽出装置２００の作用について説明する。クエリ特徴ベクトル入力部２４においてクエリ特徴ベクトル及び出力数の設定値の入力を受け付けると、類似特徴抽出装置２００は、図１２に示す類似特徴抽出処理ルーチンを実行する。
【００６０】
ステップＳ３００では、複数のサブベクトルの各々について、以下の処理を行う。ステップＳ２０４で当該サブベクトルについて算出した複数のクラスタのセントロイドの各々との類似度のうち、セントロイド最も高い類似度に基づいて、複数のクラスタの各々について、当該クラスタのセントロイドの各々との類似度を補正する。
【００６１】
なお、第２の実施の形態に係る類似特徴抽出装置２００の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【００６２】
以上説明したように、第２の実施の形態に係る類似特徴抽出装置によれば、サブベクトル間で類似度の分布のばらつきが大きい場合であっても、クエリ特徴ベクトルと類似するリファレンス特徴ベクトルを精度よく抽出することができる。
【００６３】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【００６４】
２０、２２０  演算部
２２   リファレンス特徴ベクトル入力部
２４   クエリ特徴ベクトル入力部
３０   サブベクトル分割部
３２   クラスタリング部
３４   セントロイド記憶部
３６   サブベクトル類似度算出部
２３０ サブベクトル類似度補正部
３８   セントロイドソート部
４０   類似特徴ベクトル抽出部
５０   出力部
１０、２００  類似特徴抽出装置
【図１】
2015207047.tif 000005
【図２】
2015207047.tif 000006
【図３】
2015207047.tif 000007
【図４】
2015207047.tif 000008
【図５】
2015207047.tif 000009
【図６】
2015207047.tif 000010
【図７】
2015207047.tif 000011
【図８】
2015207047.tif 000012
【図９】
2015207047.tif 000013
【図１０】
2015207047.tif 000014
【図１１】
2015207047.tif 000015
【図１２】
2015207047.tif 000016