(57)【要約】【課題】多量のメモリを用いずに分類可能な信号分類装置を提供する。【解決手段】  入力された信号に含まれるＮ個の識別対象の特徴量を取得する取得部と、  前記特徴量毎に、前記特徴量からｋ個（１≦ｋ≦Ｎ）の前記特徴量を第１近傍特徴として選択する第１の選択部と、互いに類似する前記特徴量から特徴群を生成し、取得したＮ個の前記特徴量から異なる前記特徴群に属するｕ個（１≦ｋ＋ｕ≦Ｎ−２）の前記特徴量を第２の近傍特徴として選択する第２の選択部と、前記特徴量の類似性を比較するための閾値と、前記特徴量毎に算出した周辺密度とを用いて、同じ分類となる前記特徴量を決定する決定部と、前記特徴量の決定結果から分類を行う分類部と、前記閾値を管理する管理部と、を備える。【選択図】      図２
2011191824.tif 000002
【特許請求の範囲】
【請求項１】
入力された信号に含まれるＮ個の識別対象の特徴量を取得する取得部と、
前記特徴量毎に、前記特徴量からｋ個（１≦ｋ≦Ｎ）の前記特徴量を第１近傍特徴として選択する第１の選択部と、
互いに類似する前記特徴量から特徴群を生成し、取得したＮ個の前記特徴量から異なる前記特徴群に属するｕ個（１≦ｋ＋ｕ≦Ｎ−２）の前記特徴量を第２の近傍特徴として選択する第２の選択部と、
前記特徴量の類似性を比較するための閾値と、前記特徴量毎に算出した周辺密度とを用いて、同じ分類となる前記特徴量を決定する決定部と、
前記特徴量の決定結果から分類を行う分類部と、
前記閾値を管理する管理部と、
を備えたことを特徴とする信号分類装置。
【請求項２】
追加するＭ個の識別対象の特徴量を取得する追加取得部と、
追加された前記特徴量を含む前記特徴量について、特徴量の類似したｋ個（１≦ｋ≦Ｎ＋Ｍ−２）の第１の近傍特徴と、前記特徴群が異なるｕ個（１≦ｋ＋ｕ≦Ｎ＋Ｍ−２）の第２の近傍特徴とを選択し、前記追加された特徴量夫々についてｋ個の第１近傍特徴及びｕ個の第２近傍特徴を選択する第３の選択部をさらに備えることを特徴とする請求項１記載の信号分類装置。
【請求項３】
前記決定部は前記特徴量の参照関係に関する情報によって、分類を判定する判定部を更に備えることを特徴とする請求項１または２に記載の信号分類装置。
【請求項４】
前記参照関係に関する情報は、前記特徴量が互いの近傍特徴であるか否か、あるいは前記特徴量が共通の近傍特徴を有するか否かであることを特徴とする請求項３に記載の信号分類装置。
【請求項５】
前記取得部は前記入力信号として画像を取得し、
前記参照関係に関する情報が、前記識別対象が同じ前記画像から取得されたものであることを示す情報であることを特徴とする請求項３または４に記載の信号分類装置。
【請求項６】
前記特徴量の参照関係に関する情報を取得する更新情報取得部を更に有することを特徴とする請求項３乃至５いずれか１項記載の信号分類装置。
【請求項７】
前記分類部の分類に基づいて、前記識別対象の分類結果を表示する表示部をさらに備える請求項１乃至６いずれか１項に記載の信号分類装置。
【請求項８】
前記分類部は、前記分類結果の中で類似した特徴量を持つ分類を一つに統合することを特徴とする請求項１乃至７いずれか１項に記載の信号分類装置。
【請求項９】
前記管理部は、前記閾値を新たに取得し取得した値に変更することを特徴とする請求項１乃至８に記載の信号分類装置。
【請求項１０】
前記追加取得部は、取得数（Ｍ）に応じて、前記第１の近傍特徴の選択数ｋを変更することを特徴とする請求項２乃至９いずれか１項に記載のクラスタリング装置。
【請求項１１】
前記決定部は、前記特徴量と決定した分類とを組とする表形式のデータとして保持し、該当データを用いて分類を行うこと特徴とする請求項１乃至１０いずれか１項記載の信号分類装置。
【請求項１２】
前記作成部は前記更新部の結果を用いて、前記テーブルを作成することを特徴とする請求項１１に記載の信号分類装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、信号分類装置に関する。
【背景技術】
【０００２】
クラスタリング技術（信号分類技術）は、識別対象となるサンプル（標本）集合を、類似特徴を持つサンプルで構成される部分集合（クラス）に分類することを目的とする。このクラスタリング技術は、例えば、文字や図形、音声などを対象とした識別処理に適用できる。識別対象が顔画像であるとき、誤りなく識別できれば、一つのクラスは同一人物の顔写真だけで構成され、各クラスは夫々異なる人物の顔写真で構成される。また、識別対象が夫々１人が発話した音声データであるとき、誤りなく識別できれば、一つのクラスは同一話者の音声データで構成され、各クラスは夫々異なる話者の音声データで構成される。この識別処理を高い精度で実現するには、取得する特徴も重要であるが、クラスタリングの精度も重要である。
【０００３】
従来方式である非特許文献１乃至３では、特徴空間内にて、同一クラスに属するサンプルは密集して分布することを前提としたクラスタリングを行う。具体的には、各サンプルの特徴を、近傍で潜在的に存在するクラスの分布の中心に更新し、同一クラスに属するサンプルを一箇所に集めることで、クラスタリングを実現する。非特許文献１では、各サンプルは、特徴間の類似度が閾値以上であるサンプル（近傍サンプル）との平均特徴に最も類似したサンプルに更新する。ここで、平均特徴の導出は、特徴空間の次元数が高次元に及ぶほど、演算量が増加する。
【０００４】
そこで、非特許文献２及び非特許文献３では、潜在的に存在するクラスの、分布の中心への近さは、各サンプル周辺の密度の高さが表すとしている。周辺密度は例えば近傍サンプルの数で近似する。各サンプルは、周辺密度が高く類似度が閾値以上で、かつ、最も高い類似度を持つサンプルに更新する。特徴の更新には、周辺密度を用いるため、平均特徴を求める非特許文献１よりも演算量を削減できる。
【０００５】
非特許文献２及び非特許文献３では、各サンプルに対し、周辺密度を計算する処理と、同じクラスに分類するサンプルを決定する処理とを行うには、サンプル間の類似度情報が必要となる。周辺密度を計算する処理と同じクラスに分類するサンプルを決定する処理とは同時に実行できない。そのため演算の重複を避け、効率的に処理を実行するためには、全ての組み合わせにおけるサンプル間の類似度情報をメモリ（バッファ）に記憶する必要がある。したがって、サンプルの２乗のオーダーとなる大量のメモリが必要である。
【０００６】
また、周辺密度を計算する過程で、各サンプルに対して、類似度が閾値以上である近傍サンプルのサンプルＩＤと類似度を記憶することでも効率化できる。しかし、近傍サンプルの数は事前に予測できない上、閾値が最低値であれば、全てのサンプルが近傍サンプルとなるため、サンプルＩＤと類似度とを記憶する代替案を用いても、サンプルの２乗のオーダーとなるメモリを確保する必要がある。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】“Ｍｏｄｅ−ｓｅｅｋｉｎｇ  ｂｙ  Ｍｅｄｏｉｄｓｈｉｆｔｓ”，Ｙ．Ａ．Ｓｈｅｉｋｈ，  Ｅ．Ａ．Ｋｈａｎ  ａｎｄ  Ｔ．Ｋａｎａｄｅ，  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，  ２００７．
【非特許文献２】“Ａ  Ｇｒａｐｈ−ｔｈｅｏｒｅｔｉｃ  ａｐｐｒｏａｃｈ  ｔｏ  ｎｏｎｐａｒａｍｅｔｒｉｃ  ｃｌｕｔｅｒ  ａｎａｌｙｓｉｓ”，  Ｗ．Ｌ．Ｇ．Ｋｏｏｎｔｚ，  Ｐ．Ｎａｒｅｎｄｒａ，  ａｎｄ  Ｋ．Ｆｕｋｕｎａｇａ，  ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｃｏｍｐｕｔｅｒ，  ｃ−２５（９），  １９７６．
【非特許文献３】“Ｑｕｉｃｋ  Ｓｈｉｆｔ  ａｎｄ  Ｋｅｒｎｅｌ  Ｍｅｔｈｏｄｓ  ｆｏｒ  Ｍｏｄｅ  Ｓｅｅｋｉｎｇ”，  Ａ．Ｖｅｄａｌｄｉ  ａｎｄ  Ｓ．Ｓｏａｔｔｏ，  ＥＣＣＶ２００８，  ＰａｒｔＩＶ，  ＬＮＣＳ５３０５，  ｐｐ．７０５−７１８，  ２００８．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は上記問題を鑑み、多量のメモリを用いずに分類可能な信号分類装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために本発明の信号分類装置は、入力された信号に含まれるＮ個の識別対象の特徴量を取得する取得部と、前記特徴量毎に、前記特徴量からｋ個（１≦ｋ≦Ｎ）の前記特徴量を第１近傍特徴として選択する第１の選択部と、互いに類似する前記特徴量から特徴群を生成し、取得したＮ個の前記特徴量から異なる前記特徴群に属するｕ個（１≦ｋ＋ｕ≦Ｎ−２）の前記特徴量を第２の近傍特徴として選択する第２の選択部と、  前記特徴量の類似性を比較するための閾値と、前記特徴量毎に算出した周辺密度とを用いて、同じ分類となる前記特徴量を決定する決定部と、前記特徴量の決定結果から分類を行う分類部と、前記閾値を管理する管理部と、を備えたことを特徴とする。
【発明の効果】
【００１０】
本発明によれば、多量のメモリを用いずに分類可能な信号分類装置を提供できる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施例に係るハードウェア構成を示す図。
【図２】実施例１の機能構成を表わすブロック図。
【図３】実施例１のクラスタリング処理を表わすフローチャート。
【図４】クラスタリング処理の動作例を示す図。
【図５】クラスタリング処理の動作例を示す図。
【図６】クラスタリング処理の動作例を示す図。
【図７】第１近傍特徴選択処理を表わすフローチャート。
【図８】第１近傍特徴集合への特徴追加処理を表わすフローチャート。
【図９】第２近傍特徴選択処理を表わすフローチャート。
【図１０】第２近傍特徴集合への特徴追加処理を表わすフローチャート。
【図１１】比較実験１と実施例１のクラスタリング処理精度を示す図。
【図１２】１次元の特徴量の標本を模式的に示す図。
【図１３】実施例２の機能構成を表わすブロック図。
【図１４】実施例２のクラスタリング処理を表わすフローチャート。
【図１５】第１近傍特徴変更選択処理を表わすフローチャート。
【図１６】第２近傍特徴変更選択処理を表わすフローチャート。
【図１７】実施例３の機能構成を表わすブロック図。
【図１８】実施例３のクラスタリング処理を表わすフローチャート。
【図１９】実施例３に係る画像のクラスタリング処理結果の表示例。
【図２０】実施例３に係る画像のクラスタリング処理結果の表示例。
【図２１】実施例３に係る音声のクラスタリング処理結果の表示例。
【図２２】実施例３に係る音楽のクラスタリング処理結果の表示例。
【図２３】実施例３に係る音楽のクラスタリング処理結果の表示例。
【図２４】実施例４の機能構成を表わすブロック図。
【図２５】実施例４のクラスタリング処理を表わすフローチャート。
【図２６】同一画像の人物に対するクラスタリング処理を表わす模式図。
【発明を実施するための形態】
【００１２】
以下、本実施形態に関する信号処理装置について図面に基づいて説明する。
【００１３】
本発明の実施例に関する信号処理装置は、画像中の被写体（たとえば人物）の分類または音響（例えば音楽や人の声）の分類をすることが可能であり、分類結果は、画像中の被写体毎の写真の分類や人物毎の発言の分類に用いることが可能である。したがって、写真や動画などを分類して提示する動画再生装置や静止画を用いたスライドショーなどにも適用可能である。
【実施例１】
【００１４】
まず、本実施の形態にかかる信号分類装置のハードウェア構成について図１を用いて説明する。信号分類装置１００は、装置全体を制御するＣＰＵ（Central Processing Unit）等の制御部１０１と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）１０４やＲＡＭ１０５（Random Access Memory）等の記憶部と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶部１０７と、これらを接続するバス１０８とを備えており、通常のコンピュータを利用したハードウェア構成となっている。また、信号分類装置１００には、画像を表示する表示部１０３と、ユーザの指示入力を受け付けるキーボードやマウス等の操作部１０２と、文字、画像、音声党の識別対象を電子信号に変換する入力部１０６と、外部装置の通信を制御する通信部やＩ／Ｆ（インターフェース）とが有線又は無線により各々接続される。
【００１５】
ＣＰＵ１０１は、ＲＡＭ１０５の所定領域を作業領域として、ＲＯＭ１０４に予め記憶された各種制御プログラムとの協働により各種処理を実行し、信号分類装置１００を構成する各部の動作を統括的に制御する。また、ＣＰＵ１０１は、ＲＯＭ１０４に予め記憶された所定のプログラムとの協働により、後述する取得部１０、選択部１１、作成部１２、クラスタリング部１３、管理部１４の各機能部を実現させる。  操作部１０２は、各種入力キー等を備え、ユーザから操作入力された情報を入力信号として受け付け、その入力信号をＣＰＵ１０１に出力する。
【００１６】
表示部１０３は、液晶表示装置（ＬＣＤ：Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）等の表示手段により構成され、ＣＰＵ１０１からの表示信号に基づいて、各種情報を表示する。なお、表示部１０３は、操作部１０２と一体的にタッチパネルを構成する様態としてもよい。
【００１７】
ＲＯＭ１０４は、信号分類装置１００の制御にかかるプログラムや各種設定情報等を書き換え不可能に記憶する。ＲＡＭ１０５は、ＳＤＲＡＭ等の記憶手段であって、ＣＰＵ１０１の作業エリアとして機能し、バッファ等の役割を果たす。
【００１８】
入力部１０６は、音声や文字、図形等の識別対象を電気信号に変換し、ＰＣＭ（Ｐｕｌｓｅ  Ｃｏｄｅ  Ｍｏｄｕｌａｔｉｏｎ）等の数値データとしてＣＰＵ１０１に出力する。
【００１９】
記憶部１０７は、磁気的又は光学的に記憶可能な記憶媒体を有し、入力部１０６を介して取得された信号や、図示しない通信部やＩ／Ｆ（インターフェース）等を介して外部から入力される信号等のデータを記憶する。また、記憶部１０７は、後述するクラスタリング装置により識別対象の分類結果情報を記憶する。
【００２０】
図２は、第１の実施例の信号分類装置１００ａの機能構成を示したブロック図である。なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、多くの発明を形成できる。例えば、実施形態に示される全構成要素からいくつかの構成要素を削除しても良い。さらに、異なる実施形態にわたる構成要素を適宜組み合わせても良い。
【００２１】
本実施例の信号分類装置１００ａは、取得部１０、第１の選択部及び第２の選択部からなる選択部１１、決定部１２、分類部１３及び管理部１４等を備えている。
【００２２】
取得部１０は、入力部１０６等を介して入力された信号に含まれる識別対象の特徴量を取得する。特徴量とは識別対象となる信号、例えば画像中の人物はたは顔、音の中の声などを個別に認識するための特性を示すものである。識別対象が顔の画像で、人物毎に分類する場合には、特徴量を、画素値を表すベクトルを変換して求める。このとき用いる変換は、例えば、ヒストグラム平坦化などを用いる。識別対象が音声で、話者毎に分類する場合には、例えばＬＰＣケプストラムやＭＦＣＣ等のケプストラム系特徴量を取得すれば良い。また、Ｙ．Ａｋｉｔａによる“Ｕｎｓｕｐｅｒｖｉｓｅｄ  Ｓｐｅａｋｅｒ  Ｉｎｄｅｘｉｎｇ  ｕｓｉｎｇ  Ａｎｃｈｏｒ  Ｍｏｄｅｌｓ  ａｎｄ  Ａｕｔｏｍａｔｉｃ  Ｔｒａｎｓｃｒｉｐｔｉｏｎ  ｏｆ  Ｄｉｓｃｕｓｓｉｏｎｓ”，  ＩＳＣＡ  ８ｔｈ  Ｅｕｒｏｐｅａｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｓｐｅｅｃｈ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ（Ｅｕｒｏ  Ｓｐｅｅｃｈ），  Ｓｅｐｔｅｍｂｅｒ  ２００３に記載された手法を用いてケプストラム系特徴量を加工しても良い。さらに、識別対象の音声は、予め検出した無音毎に分割する、一定時間毎に分割する等の方法により、その個数を増やしても良い。識別対象が音全般で、音楽、音声、雑音といった音の種別を分類する場合には、Ｅ．Ｓｃｈｅｉｒｅｒらによる“Ｃｏｎｓｔｒｕｃｔｉｏｎ  ａｎｄ  Ｅｖａｌｕａｔｉｏｎ  ｏｆ  ａ  Ｒｏｂｕｓｔ  Ｍｕｌｔｉｆｅａｔｕｒｅ  Ｓｐｅｅｃｈ／Ｍｕｓｉｃ  Ｄｉｓｃｒｉｍｉｎａｔｏｒ”，ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｃｏｕｓｔｉｃ  Ｓｐｅｅｃｈ，  ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ，  Ａｐｒｉｌ  １９９７に記載された手法を用いても良い。取得部１０が取得した特徴量は選択部１１に出力される。
【００２３】
選択部１１は、取得部１０が取得したＮ個の特徴量夫々に対して、取得した特徴量の中から、特徴が類似したｋ個（１≦ｋ≦Ｎ）の第１近傍特徴を選択する第１の選択部と、互いに類似する特徴量から特許群を生成し、異なる特徴群に属するｕ個の第２近傍特徴を選択する第２の選択部とからなる。特徴群は、取得部１０が取得した特徴量の中から、類似した特徴同士を群として纏めたものである。特徴群の生成は、特徴量間の類似度を計算する過程で逐次的に実行できる簡易的な処理であれば良い。選択部１１は、取得したＮ個の特徴量を用いて、複数の特徴群を生成する。選択部１１は、選択した第１近傍特徴及び第２近傍特徴を決定部１２に出力する。
【００２４】
決定部１２は、特徴量の類似性を比較するための閾値を参照し、選択部１１で選択された第１近傍特徴と第２近傍特徴を用いて、各特徴量に対して周辺密度を算出する。次に、特徴量毎に、第１近傍特徴と第２近傍特徴の中から同じクラス（集合）に分類する特徴量を決定する。特徴量毎に関係する特徴量が参照できるテーブルを作成し、分類部１３に出力する。特徴量は表形式で出力するのが好ましいが、特徴量毎に第１近傍特徴と第２近傍特徴から決定された特徴量がわかるような形式ならばこれに限らない。
【００２５】
分類部１３は、決定部１２にて作成されたテーブルを参照し、各特徴量に対して、クラスＩＤを付与する。クラスＩＤは同じ集合となるものに付与する。クラスＩＤの付与結果は管理部１４に出力する。
【００２６】
管理部１４は、決定部１２で用いた閾値を管理する。更に閾値を異なる値に変更した場合には、決定部１２に変更した閾値を出力する。決定部１２は管理部１４が変更した閾値を取得した後、再度テーブルを作成する。
【００２７】
次に、本実施例の信号分類装置１００の動作を説明する。図３は、本実施例の信号分類装置１００によるクラスタリング処理の流れを示したフローチャート、図４乃至図６である。以下、図３乃至図６に示した動作例Ｏ１乃至Ｏ８を参照して、本実施例の信号分類装置について説明する。 
まず、入力部１０６を介して識別対象となる信号が入力される（図３のステップＳ１０１）。取得部１０は、入力された識別対象から特徴量を取得する（図３のステップＳ１０２、図４の動作例Ｏ１参照）。取得部１０は、取得した特徴量を選択部１１に出力する。
【００２８】
次いで選択部１１は、各特徴量に対して第１近傍特徴を選択する、第１近傍特徴選択処理を実行する（図３のステップＳ１０３）。特徴量ｘｉの第１の近傍特徴は、特徴量ｘｉと類似度の高い上位ｋ個の特徴量とする（図４の動作例Ｏ２及び図５の動作例Ｏ３参照）。
【００２９】
ここで、第１近傍特徴選択処理（ステップＳ１０３）の詳細な動作を、図７を参照して説明する。なお、取得部１０にて取得した特徴量はｘｉ（ｉ＝０，１，．．．，Ｎ−１）で表す。
【００３０】
まず、第１の選択部は、特徴量の番号を参照できる変数ｉ＝１を設定し、２番目の特徴を参照できる状態にする（ステップＳ１１）。同様に、変数ｊ＝０を設定し、１番目の特徴を参照できる状態にする（ステップＳ１２）。
【００３１】
次いで選択部１１は、特徴量ｘｉと特徴量ｘｊの類似度Ｓ（ｉ，ｊ）を計算する（ステップＳ１３）。類似度は、特徴量をベクトルとして表現したものである。類似度は特徴量間のユークリッド距離の逆数、最大値からユークリッド距離を引いた値としても良い。また、特徴量同士の内積がなす角の余弦としても良い。
【００３２】
次いで第１の選択部は、特徴量ｘｉの第１近傍特徴の集合ＲＦｉに特徴量ｘｊを追加するか否かを判定し追加処理を実行する、集合ＲＦｉと特徴量ｘｊを対象とした第１の近傍特徴の集合への特徴追加処理を行う（ステップＳ１４）。第１近傍特徴の集合への特徴追加処理の詳細な動作は図８を参照して説明する。
【００３３】
第１の選択部は、処理対象となる特徴量ｘａとして特徴量ｘｉを、第１近傍特徴の集合ＲＦａとして集合ＲＦｉを設定する（ステップＳ２１）。次に、集合ＲＦａに追加するか否かを判定し追加処理を実行したい特徴量ｘｂとして、特徴量ｘｊを設定する（ステップＳ２２）。
【００３４】
次いで、特徴量ｘａの第１近傍特徴の集合ＲＦａにｋ個の特徴量が含まれているか否かを確認する（ステップＳ２３）。ｋ個の特徴量が含まれている場合には（ステップＳ２３のＹｅｓ）、そのままステップＳ２５に進む。ここで、ｋ個の特徴量が含まれていない場合は（ステップＳ２３のＮｏ）、集合ＲＦａに特徴量ｘｂを加えた後（ステップＳ２４）、処理を終了する。
【００３５】
第１の選択部は、集合ＲＦａの中で特徴量ｘａとの類似度が最も低い特徴量ｘｃを取得する（ステップＳ２５）。次に、特徴量ｘａと特徴量ｘｂの類似度Ｓ（ａ，ｂ）と、特徴量ｘａと特徴量ｘｃの類似度Ｓ（ａ，ｃ）を比較する（ステップＳ２６）。Ｓ（ａ，ｂ）がＳ（ａ，ｃ）より大きい場合には（ステップＳ２６のＹｅｓ）、特徴量ｘｃの替わりに、特徴量ｘｂを集合ＲＦａに追加した後（ステップＳ２７）、処理を終了する。Ｓ（ａ，ｂ）がＳ（ａ，ｃ）以下である場合には（ステップＳ２６のＮｏ）、そのまま処理を終了する。
【００３６】
次いで特徴量ｘｊの第１近傍特徴の集合ＲＦｊに特徴量ｘｉを追加するか否かを判定し追加処理を実行する、集合ＲＦｊと特徴量ｘｉを対象とした第１近傍特徴の集合への特徴追加処理を行う。この特徴追加処理は、ステップＳ２１とステップＳ２２を除き、ステップＳ１４で行う処理と同様に実行できる。ステップＳ２１では、特徴量ｘａとして特徴量ｘｊ、集合ＲＦａとして集合ＲＦｊを設定する。また、ステップＳ２２では、特徴量ｘｂとして、特徴量ｘｉを設定する。
【００３７】
図７の、第一近傍特徴選択処理の詳細な動作についての説明に戻る。第１の選択部は、特徴量ｘｉとの類似度を求める特徴量として、次の特徴量を参照するため、ｊ＝ｊ＋１を設定する（ステップＳ１６）。次に、新たに設定した特徴量ｘｊが特徴量ｘｉと同一のものであるかを判定する（ステップＳ１７）。特徴量ｘｊと特徴量ｘｉが同一のものである場合（ステップＳ１７のＹｅｓ）、ステップＳ１８に進む。特徴量ｘｊと特徴量ｘｉが異なるものである場合（ステップＳ１７のＮｏ）、類似度計算を行うためステップＳ１３に戻る。
【００３８】
第１の選択部は、次の特徴量を参照するため、ｉ＝ｉ＋１を設定した後（ステップＳ１８）、取得した全ての特徴量に対してステップＳ１２乃至ステップＳ１８の処理を実行したか否かを判定する（ステップＳ１９）。全ての特徴量に対して処理を完了している場合には（ステップＳ１９のＹｅｓ）、処理を完了する。全ての特徴量に対して処理を完了していない場合は（ステップＳ１９のＮｏ）、ステップＳ１２に戻る。
【００３９】
図３に戻って、第１近傍特徴選択処理に続く第２近傍特の選択について説明する。選択部１１は、各特徴量に対して第２近傍特徴を選択する、第２近傍特徴選択処理を実行する（図３のステップＳ１０４）。特徴量ｘの第２近傍特徴は、類似度の高い上位ｕ個の特徴量とするが、ｕ個の特徴量はお互いに異なる特徴群に属するとする（図４の動作例Ｏ２及び図５の動作例Ｏ３参照）。特許群とは、互いに類似する複数個の特徴量からなる集合である。ここで、第２近傍特徴選択処理の詳細な動作を、図９を参照して説明する。
【００４０】
まず、第２の選択部は、１番目の特徴量ｘ０を要素に持つ特徴群を新規作成する（ステップＳ３１）。次に、特徴量の番号を参照できる変数ｉ＝１を設定し、２番目の特徴量を参照できる状態にする（ステップＳ３２）。同様に、変数ｊ＝０、ｊｊ＝０を設定し、１番目の特徴量を参照できる状態にする（ステップＳ３３）。
【００４１】
次いで、第２の選択部は、ステップＳ１１と同様の方法にて、特徴量ｘｉと特徴量ｘｊの類似度Ｓ（ｉ，ｊ）を計算する（ステップＳ３４）。次に、第２の選択部は、類似度Ｓ（ｉ，ｊ）が閾値ｔｈｍ以上となり、特徴量ｘｉと特徴量ｘｊが同じ特徴群に分類され得るか否かを判定する（ステップＳ３５）。閾値ｔｈｍを十分信頼できる値とするため、例えば、類似度の最大が１であるときはｔｈｍ＝０．９と設定する。類似度Ｓ（ｉ，ｊ）が閾値ｔｈｍ以上である場合には（ステップＳ３５のＹｅｓ）、特徴量ｘｉを特徴量ｘｊと同じ特徴群に分類した後（ステップＳ３６）、ステップＳ３７に進む。類似度Ｓ（ｉ，ｊ）が閾値ｔｈｍ未満である場合には（ステップＳ３５のＮｏ）、そのままステップＳ３７に進む。
【００４２】
次いで、第２の選択部は、特徴量ｘｉの第２近傍特徴の集合ＲＳｉに特徴量ｘｊを追加するか否かを判定し追加処理を実行する、集合ＲＳｉと特徴量ｘｊを対象とした第２近傍特徴の集合への特徴追加処理を行う。ここで、第２の近傍特徴の集合への特徴追加処理の詳細な動作を、図１０を参照して説明する。
【００４３】
まず、第２の選択部は、処理対象となる特徴量ｘａとして特徴量ｘｉを、第２近傍特徴の集合ＲＳａとして集合ＲＳｉを設定する（ステップＳ５１）。次に、集合ＲＳａに追加するか否かを判定し追加処理を実行したい特徴量ｘｂとして、特徴量ｘｊを設定する（ステップＳ５２）。
【００４４】
次いで、第２の選択部は、集合ＲＳａの中で、特徴量ｘｂと同じ特徴群に属する特徴量があるか否かを判定する（ステップＳ５３）。集合ＲＳａの中で、特徴量ｘｂと同じ特徴群に属する特徴量ｘｄが存在した場合（ステップＳ５３のＹｅｓ）、ステップＳ５４に進む。ステップＳ５４では、特徴量ｘａと特徴量ｘｂの類似度Ｓ（ａ，ｂ）と、特徴量ｘａと特徴量ｘｄの類似度Ｓ（ａ，ｄ）を比較する。Ｓ（ａ，ｂ）がＳ（ａ，ｄ）より大きい場合には（ステップＳ５４のＹｅｓ）、特徴量ｘｄの替わりに、特徴量ｘｂを集合ＲＳａに追加した後（ステップＳ５５）、処理を終了する。Ｓ（ａ，ｂ）がＳ（ａ，ｄ）以下である場合には（ステップＳ５４のＮｏ）、そのまま処理を終了する。集合ＲＳａの中で、特徴量ｘｂと同じ特徴群に属する特徴がない場合には（ステップＳ５３のＮｏ）、ステップ５６に進む。
【００４５】
次いで、第２の選択部は、特徴量ｘａの第２近傍特徴の集合ＲＳａにｕ個の特徴量が含まれているか否かを確認する（ステップＳ５６）。ｕ個の特徴量が含まれている場合には（ステップＳ５６のＹｅｓ）、そのままステップＳ５８に進む。ここで、ｕ個の特徴量が含まれていない場合は（ステップＳ５６のＮｏ）、集合ＲＳａに特徴量ｘｂを加えた後（ステップＳ５７）、処理を終了する。
【００４６】
次いで、第２の選択部は、集合ＲＳａの中で、特徴量ｘａとの類似度が最も低い特徴量ｘｃを取得する（ステップＳ５８）。次に、特徴量ｘａと特徴量ｘｂの類似度Ｓ（ａ，ｂ）と、特徴量ｘａと特徴量ｘｃの類似度Ｓ（ａ，ｃ）を比較する（ステップＳ５９）。Ｓ（ａ，ｂ）がＳ（ａ，ｃ）より大きい場合には（ステップＳ５９のＹｅｓ）、特徴量ｘｃの替わりに、特徴量ｘｂを集合ＲＳａに追加した後（ステップＳ６０）、処理を終了する。Ｓ（ａ，ｂ）がＳ（ａ，ｃ）以下である場合には（ステップＳ５９のＮｏ）、そのまま処理を終了する。
【００４７】
図９に戻り、第２近傍特徴選択処理の詳細な動作について説明する。次いで、第２の選択部は、特徴量ｘｉとの類似度を求める特徴量として、次の特徴量を参照するため、ｊ＝ｊ＋１を設定する（ステップＳ３８）。次に、新たに設定した特徴量ｘｊが特徴量ｘｉと同一のものであるかを判定する（ステップＳ３９）。特徴量ｘｊと特徴量ｘｉが同一のものである場合（ステップＳ３９のＹｅｓ）、ステップＳ４０に進む。特徴量ｘｊと特徴量ｘｉが異なるものである場合（ステップＳ３９のＮｏ）、類似度計算を行うためステップＳ３３に戻る。
【００４８】
次いで、第２の選択部は、特徴量ｘｉが既存の特徴群に分類されたか否かを判定する（ステップＳ４０）。特徴量ｘｉが既存の特徴群に分類されている場合には（ステップＳ４０のＹｅｓ）、そのままステップＳ４２に進む。特徴量ｘｉが既存の特徴群に分類されていない場合には（ステップＳ４０のＮｏ）、特徴量ｘｉを要素に持つ特徴群を新規作成した後（ステップＳ４１）、ステップＳ４２に進む。
【００４９】
次いで、選択部１１は、特徴量ｘｊｊの第２近傍特徴の集合ＲＳｊｊに特徴量ｘｉを追加するか否かを判定し追加処理を実行する、集合ＲＦｊｊと特徴量ｘｉを対象とした第２近傍特徴の集合への特徴追加処理を行う。この特徴追加処理は、ステップＳ５１とステップＳ５２を除き、ステップＳ３７で行う処理と同様に実行できる。ステップＳ５１では、特徴量ｘａとして特徴量ｘｊｊ、集合ＲＳａとして集合ＲＳｊｊを設定する。また、ステップＳ５２では、特徴量ｘｂとして、特徴量ｘｉを設定する。
【００５０】
次いで、第２の選択部は、特徴量ｘｉが属する可能性のある次の第２近傍特徴の集合を参照するため、ｊｊ＝ｊｊ＋１を設定する（ステップＳ４３）。次に、新たに設定した特徴量ｘｊｊが特徴量ｘｉと同一のものであるかを判定する（ステップＳ４４）。特徴量ｘｊｊと特徴量ｘｉが同一のものである場合（ステップＳ４４のＹｅｓ）、ステップＳ４５に進む。特徴量ｘｊｊと特徴量ｘｉが異なるものである場合（ステップＳ４４のＮｏ）、第２近傍特徴の集合への特徴追加処理を行うためステップＳ４２に戻る。
【００５１】
次いで、第２の選択部は、次の特徴量を参照するため、ｉ＝ｉ＋１を設定した後（ステップＳ４５）、取得した全ての特徴量に対してステップＳ３３乃至ステップＳ４５の処理を実行したか否かを判定する（ステップＳ４６）。全ての特徴量に対して処理を完了している場合には（ステップＳ４６のＹｅｓ）、処理を完了する。全ての特徴量に対して処理を完了していない場合は（ステップＳ４６のＮｏ）、ステップＳ３３に戻る。
【００５２】
ここで選択部１１は、第２近傍特徴選択処理にて、特徴量ｘｉの第２近傍特徴の集合ＲＳｉには特徴量ｘｉと同じ特徴群に属する特徴量を含まない制約を加えても良い。あるいは、特徴量ｘｉの第２近傍特徴の集合ＲＳｉには第１近傍特徴の集合ＲＦｉの特徴量を含まない制約を加えても良い。
【００５３】
選択部１１は、図７に示した第１近傍特徴選択処理と、図９に示した第２近傍選択処理を並列して実行してもよい。並列実行の際は、まず、ステップＳ１１及びステップＳ１２と、ステップＳ３１乃至ステップＳ３３を順に行う。次に、類似度計算の処理（ステップＳ１３あるいはステップＳ３４）を行った後、ステップＳ１４乃至ステップＳ１７と、ステップＳ３５乃至ステップＳ３９を順に行う。次いで、ステップＳ４０乃至ステップＳ４４を行った後、処理終了に繋がる処理（ステップＳ１８とステップＳ１９、あるいは、ステップ４５とステップ４６）を行うことが望ましい。
【００５４】
選択部１１が選択する第１近傍特徴の数ｋは１以上Ｎ−２以下で設定し、第２近傍特徴の数ｕは、ｋ＋ｕがＮ−２以下となるように設定する。また、ｋ及びｕは、Ｎの値によらない固定値しても良いし、Ｎに比例して増やしても良い。さらには、ｋとｕは独立して扱っても良いし、同じ値としても良い。例えば、Ｎ＝２００のとき、ｋとｕをＮの１％と設定し、ｋ＝２、ｕ＝２としてもよい。
【００５５】
選択部１１は、最後に、選択した第１近傍特徴及び第２近傍特徴の情報を決定部１２に出力する。
【００５６】
決定部１２は、特徴量の類似性を比較するための閾値ｔｈｓを参照し、選択部１１で選択された第１の近傍特徴と第２の近傍特徴の情報を用いて、前記各特徴量に対して周辺密度を決定する（図３のステップＳ１０５、図５の動作例Ｏ４参照）。
【００５７】
決定部１２で決定される特徴量ｘｉの周辺密度Ｐｉは、閾値ｔｈｓと、非特許文献１や非特許文献２に記載されているようなガウス関数を用いて、例えば式１で算出できる。式１にて、類似度の最大値は１とし、ＲＦｉは特徴量ｘｉの第１近傍特徴の集合、ＲＳｉは特徴量ｘｉの第２近傍特徴の集合とする。また、式１にて、αは、第２近傍特徴に対する重みであり、例えば０．５と設定できる。
【数１】
2011191824.tif 000003
【００５８】
次いで、決定部１２は、第１近傍特徴及び第２近傍特徴の中から、特徴量毎に同じクラスに分類する特徴量を決定し（図３のステップＳ１０６）、決定した結果を参照できるテーブルを作成し（図３のステップＳ１０７、図５の動作例Ｏ５）、分類部１３に出力する。作成されるテーブルは特徴量毎に参照できればよく、識別対象毎にまとめられた形式のデータ構造であっても、識別対象の特性を表わす個々の特徴量毎に参照できる形式であればよい。
【００５９】
決定部１２にて、特徴量ｘｉと同じクラス（分類）に分類する特徴量ｙ（ｘｉ）は、第１近傍特徴の集合ＲＦｉ及び第２近傍特徴の集合ＲＳｉの中で、周辺密度が特徴量ｘｉよりも高く、特徴量ｘｉとの類似度が最も大きい特徴量とする。特徴量ｘｉの周辺密度より高い周辺密度を持つ特徴量が集合ＲＦｉ及び集合ＲＳｉの中に存在しなければ、特徴量ｙ（ｘｉ）は特徴量ｘｉとする。また、特徴量の類似性を比較するための閾値ｔｈｃを参照し、求めた特徴量ｙ（ｘｉ）と特徴量ｘｉの類似度が閾値ｔｈｃを下回った場合には、特徴量ｙ（ｘｉ）を特徴量ｘｉに修正する。ここで、閾値ｔｈｃは閾値ｔｈｓと同じでも良いし、閾値ｔｈｓから線形変換によって求めても良い。あるいは閾値ｔｈｃは、閾値ｔｈｓと独立して設定してもいい。なお、以下では、特徴量ｘｉから特徴量ｙ（ｘｉ）を求めることを特徴量ｘｉに関数ｙを作用させると表現する。
【００６０】
次いで、分類部１３は、決定部１２で作成された表形式のテーブルを参照し、特徴量毎にクラスＩＤを付与する（図３のステップＳ１０８、図６の動作例Ｏ６及びＯ７参照）。分類部１３は、各特徴量のクラスＩＤを管理部１４に出力する。
【００６１】
分類部１３は、各特徴量ｘｉに対して、特徴量ｘｉと同じクラスに分類する特徴量ｙ（ｘｉ）が同じ特徴量を指すか否かを判定し、指せば終了、指さなければｘｉ＝ｙ（ｘｉ）として再び関数ｙを作用させる。関数ｙを作用させる処理は、作用させた結果が変化しなくなるまで繰り返す（図６の動作例Ｏ６参照）。そして、関数ｙを作用させ続けて得られた結果Ｙが等しい特徴量同士を同じクラスに分類する（図６の動作例Ｏ７参照）。
【００６２】
分類部１３は、テーブルを参照してクラスＩＤを付与した後、第１近傍特徴及び第２近傍特徴の情報を用いて、類似した特徴量を持つクラスを一つに纏める統合処理を行っても良い。例えば、閾値ｔｈｎを設定し、特徴量ｘｉの第１近傍特徴の集合ＲＦｉ及び第２近傍特徴の集合ＲＳｉの中で、閾値ｔｈｎ以上の類似度を持ち、異なるクラスＩＤが付与された特徴量ｘｎが存在した場合（図５の動作例Ｏ３における、ｘ０の第２近傍特徴ｘ６参照）、特徴量ｘｉと特徴量ｘｎが所属するクラスを一つに纏める（図６の動作例Ｏ８参照）。閾値ｔｈｎは、類似度の最大値が１であるとき、例えば、０．６に設定できる。
【００６３】
管理部１４は、閾値ｔｈｓ又は閾値ｔｈｃを変更する必要があるかをチェックする（図３のステップＳ１０９）。閾値ｔｈｓ又は閾値ｔｈｃの変更が必要な場合には（図３のステップＳ１０９のＹｅｓ）、閾値ｔｈｓの変更が必要であるかをチェックする（図３のステップＳ１１０）。閾値ｔｈｓの変更が必要な場合には（図３のステップＳ１１０のＹｅｓ）、閾値ｔｈｓ及び閾値ｔｈｃの値を作成部１２に出力し、ステップＳ１０５に戻る。閾値ｔｈｓの変更が必要ない場合は（図３のステップＳ１１０のＮｏ）、閾値ｔｈｃの値を決定部１２に出力し、ステップＳ１０６に戻る。閾値ｔｈｓ及び閾値ｔｈｃの変更が必要ない場合には（図３のステップＳ１０９のＮｏ）、処理を終了する。なお、管理部１４から変更された閾値ｔｈｓ及び閾値ｔｈｃを取得した決定部１２は、閾値にあわせて再度テーブルを作成する。
【００６４】
管理部１４は、分類部１３から取得したクラスＩＤの付与結果を元に閾値ｔｈｓ及び閾値ｔｈｃの値を変更しても良い。例えば、クラス数を算出することによって変更してもよい。特徴量数Ｎに対して、分類されたクラス数が一定の割合以上の個数である場合、クラス数を削減するため、閾値ｔｈｓ及び閾値ｔｈｃの値を高くする。特徴量数に対して一定の割合以下の個数であれば、クラス数を増やすため、閾値ｔｈｓ及び閾値ｔｈｃの値を低くする。さらに一定の割合ではなく、所定のクラス数を基準にして閾値ｔｈｓ及び閾値ｔｈｃの値を変更しても良い。
【００６５】
また管理部１４は、操作部１０２を通じてユーザから入力された値を元に閾値ｔｈｓ及び閾値ｔｈｃの値を変更しても良い。また、閾値ｔｈｓ及び閾値ｔｈｃの値は一度に限らず何度でも実行することができる。さらには、変更する閾値に閾値ｔｈｎを加えても良い。なお、閾値ｔｈｎの変更のみの場合には、ステップＳ１０８に戻れば良い。
【００６６】
以上のように、本実施例によれば、全ての特徴量の組み合わせにおける類似度情報は必要なく、特徴数Ｎのオーダー（＝ｋ＋ｕ倍＜Ｎ倍）となるメモリを用意することによって、識別対象となる信号のクラスタリング（分類）を行うことができる。
【００６７】
また、特徴量間の類似性を比較するための閾値ｔｈｓを変更した場合、周辺密度の推定には選択した所定個数の特徴量（標本）との類似度のみ参照する。したがって、非常に高速にクラスタリングを行うことが可能である。更に、閾値ｔｈｓを対話的に変更するインタラクティブ処理が実現できる。
【００６８】
ここで、全ての組み合わせにおけるサンプル間の類似度情報をメモリ（バッファ）に記憶した場合（比較実験１）に対して本実施（実験1）を組み込み、特徴量の次元数が５１２０の顔画像１００００枚に対するクラスタリングの処理時間を測定した結果を表１に示した。比較実験１に比べ、実験１はメモリ使用量を削減し、閾値ｔｈｓ変更後の処理時間も短縮できていることが確認できる。
【表１】
2011191824.tif 000004
【００６９】
閾値ｔｈｃが低い値を取る程、特徴量ｘｉは異なる特徴量に更新されやすい（ｙ（ｘｉ）≠ｘｉ）。この場合、特徴量の集合が過剰に纏まり、精度劣化に繋がる可能性がある。本実施例の場合、各特徴量は所定個数の特徴量を参照することで特徴量が過剰に纏ることなく精度劣化を低減できる。更に、第１近傍特徴だけでなく、近傍特徴同士が異なる特徴群に属しているかを考慮した第２近傍特徴を用いることで、多くの特徴量を効率的に纏めることができる。これにより閾値ｔｈｃの値が高いときに精度向上に繋げることができる。図１１は、比較実験１と同様の手法で、特徴量の次元数が５１２０の顔画像８２８枚（登場人物７３人）に対するクラスタリング精度を測定した結果である（閾値ｔｈｃ＝閾値ｔｈｓ、閾値ｔｈｎ＝∞）。精度は再現率、適合率の調和平均Ｆ値（＝２＊再現率＊適合率／（再現率＋適合率））で表している。適合率は、各クラスが一人の人物のデータで構成されているか否かを表す尺度である。具体的には、各クラスにて、属する特徴量の中で同一人物に纏められる特徴量数をＣとし、対応する同一人物の総特徴量数をＲとしたとき、クラス毎に求めたＣ／Ｒの平均値を適合率とする。なお、特徴量数Ｃを設定する際、複数の人物の候補があるならば、最大値を持つ人物を選択する。また、再現率は、各人物が一つのクラスに分類されているか否かを表す尺度である。具体的には、各人物にて総特徴量数をＲとしたとき、対応する人物を最も多く含むクラスを一つ選択し、選択したクラスに属する特徴量の中で対応する人物の特徴量数をＣとしたとき、人物毎に求めたＣ／Ｒの平均値を再現率とする。なお、同じクラスを複数回選択することはできない。図１１より、閾値ｔｈｃが低い値のときと、閾値ｔｈｃが高い値のときで本発明の効果を確認することができる。
【００７０】
また、図１２は１次元の特徴量ｘ０からｘ９を模式的に示したものである。ｘ０からｘ９を識別対象とした動作例として、比較実験１の手法を用いた結果（表２）、実験２（表３）、実験３（表４）を示した。こおで、ユークリッド距離をＤとしたとき、類似度は１／（１＋Ｄ）で定義し、第２近傍特徴に対する重みαは１、閾値ｔｈｓ及び閾値ｔｈｃは共に０．２７とした。実験３では、第２近傍特徴を用いるため、同じ使用メモリでもより距離の離れた特徴量を参照でき、ｘ０からｘ７を一つのクラスとみなせる。
【表２】
2011191824.tif 000005
【表３】
2011191824.tif 000006
【表４】
2011191824.tif 000007
【実施例２】
【００７１】
次に、第２の実施例に係る信号分類装置１００について説明する。なお、上述した第１の実施例と同等の構成については、同一の符号を付与し、その説明を省略する。
【００７２】
図１３は、第２の実施例に係る信号分類装置１００ｂの機能構成を示したブロック図である。図１３に示したように、本実施例の信号分類装置１００は、取得部１０、選択部２１、追加取得部２５、更新部２６、決定部２２、分類部１３及び管理部１４から構成される。なお、図１３において、選択部２１、追加取得部２５、更新部２６及び決定部２２は、取得部１０、分類部１３及び管理部１４と同様、ＣＰＵ１０１とＲＯＭ１０４に予め記録された所定のプログラムとの協働により実現される機能部である。
【００７３】
選択部２１は、取得部１０が取得したＮ個の特徴量夫々に対して、取得した特徴量の中から、特徴量が類似したｋ個の第１近傍特徴を選択する第１の選択部と、互いに類似する特徴量から特許群を生成し、異なる特徴群に属するｕ個の第２近傍特徴を選択する第２の選択部とからなる。選択部１１は、特徴量毎に選択した第１近傍特徴及び第２近傍特徴を決定部１２に出力し、更新部２６にも出力する。
【００７４】
追加取得部２５は、入力部１０６等を介して追加入力された識別対象の特性を表す特徴量を取得する。追加取得部２５は、取得部１０と同様の方法で特徴量を取得し、取得した特徴量を追加特徴量として更新部２６に出力する。
【００７５】
更新部２６は、取得部１０で取得した特徴量の数をＮ、追加取得部２５で取得した追加特徴量の数をＭとし、各特徴量に対して、追加特徴量の情報を参照して選択部２１が選択したｋ個の第１近傍特徴及びｕ個の第２近傍特徴を変更する。更新部２６は、Ｎ＋Ｍ個の特徴量及び追加特徴量の中から、各追加特徴量に対し、ｋ個の第１近傍特徴及びｕ個の第２近傍特徴を選択する。更新部２６は、特徴量毎に更新した第１近傍特徴及び第２近傍特徴と、追加特徴量毎に選択した第１近傍特徴及び第２近傍特徴を決定部２２に出力する。
【００７６】
決定部２２は、更新部２６が更新した特徴量毎の第１近傍特徴及び第２近傍特徴に関する情報と、更新部２６が選択した追加特徴量毎の第１近傍特徴及び第２近傍特徴に関する情報とを用いて、前記各特徴量及び前記各追加特徴量に対して周辺密度を推定する。決定部２２での周辺密度の推定は、第１の実施例における決定部１２と同様の方法である。
【００７７】
決定部２２は、決定部１２と同様に、特徴量及び追加特徴量毎に同じクラスに分類する特徴量または追加特徴量を参照できるテーブルを作成し、分類部１３に出力する。
【００７８】
次に、本実施例の信号分類装置１００の動作を説明する。図１４は、本実施例の信号分類装置１００によるクラスタリング処理の流れを示したフローチャートである。以下、図１４を参照して、本実施例の信号分類装置について説明する。
【００７９】
まず、入力部１０６等を介して識別対象が入力されると（図１４のステップＳ１０１）、取得部１０は、入力された識別対象から特性を表す特徴量を取得する（図１４のステップＳ１０２）。取得部１０は、取得した特徴量を選択部２１に出力する。
【００８０】
次いで、選択部２１は、各特徴量に対して、第１近傍特徴を選択する第１近傍特徴選択処理を実行する（図１４のステップＳ１０３）。また、選択部２１は、各特徴量に対して、第２近傍特徴を選択する第２近傍特徴選択処理を実行する（図１４のステップＳ１０４）。選択部２１は、選択した第１近傍特徴及び第２近傍特徴の情報を決定部２２及び更新部２６に出力する。
【００８１】
次いで、入力部１０６等を介して識別対象が追加入力されると（図１４のステップＳ２０１）、追加取得部２５は、追加入力された識別対象から特徴量を取得する（図１４のステップＳ２０２）。追加取得部２５は、取得した追加特徴量を更新部２６に出力する。
【００８２】
次いで、更新部２６は、取得部１０が取得した特徴量毎に第１近傍特徴を変更する処理と、追加取得部２５が取得した追加特徴量毎に第１近傍特徴を選択する、第１近傍特徴変更選択処理を行う（図１４のステップＳ２０３）。ここで、第１の近傍特徴変更選択処理の詳細な動作を、図１４を参照して説明する。なお、取得部１０にて取得した特徴量は、ｘｉ（ｉ＝０，１，．．．，Ｎ−１）で表し、追加取得部２５にて取得した追加特徴量は、ｘｉ（ｉ＝Ｎ，Ｎ＋１，．．．，Ｎ＋Ｍ−１）で表す。
【００８３】
まず、更新部２６は、特徴量の番号を参照できる変数ｉ＝Ｎを設定し、１番目の追加特徴量を参照できる状態にする（図１５のステップＳ７１）。以下、ステップＳ１２乃至ステップＳ１８は、実施例１の図７のフローチャートにおけるステップＳ１２乃至ステップＳ１８と同様であるので説明を省略する。
【００８４】
次いで、更新部２６は、取得した全ての追加特徴量に対して、ステップＳ１２乃至ステップＳ１８の処理を実行したか否かを判定する（図１５のステップＳ７９）。全ての追加特徴量に対して処理を完了している場合には（ステップＳ７９のＹｅｓ）、処理を完了する。全ての追加特徴量に対して処理を完了していない場合は（ステップＳ７９のＮｏ）、ステップＳ１２に戻る。
【００８５】
続いて、更新部２６は、取得部１０が取得した特徴量毎に第の近傍特徴を変更する処理と、追加取得部２５が取得した追加特徴量毎に第２近傍特徴を選択する、第２近傍特徴変更選択処理を行う（図１４のステップＳ２０４）。ここで、第２近傍特徴変更選択処理の詳細な動作を、図１６を参照して説明する。
【００８６】
まず、更新部２６は、特徴量の番号を参照できる変数ｉ＝Ｎを設定し、１番目の追加特徴量を参照できる状態にする（ステップＳ８２）。以下、ステップＳ３３乃至ステップＳ４５は、実施例１における図９のフローチャートにおけるステップＳ３３乃至ステップＳ４５と同じであり、同様に実行する。
【００８７】
次いで、更新部２６は、取得した全ての追加特徴量に対して、ステップＳ３３乃至ステップＳ４５の処理を実行したか否かを判定する（ステップＳ９６）。全ての追加特徴量に対して処理を完了している場合には（ステップＳ９６のＹｅｓ）、処理を完了する。全ての追加特徴量に対して処理を完了していない場合は（ステップＳ９６のＮｏ）、ステップＳ３３に戻る。なお、更新部２６は、第１近傍特徴及び第２近傍特徴を変更又は選択する処理を、選択部１１と同様な方法で、並列して実行することができる。
【００８８】
更新部２６は、特徴量及び追加特徴量の数に応じて、第１近傍特徴の数ｋと第２近傍特徴の数ｕを変更することができる。例えばｋ＋ｕがＮの１％で近似できたとき、ｋ＋ｕがＮ＋Ｍの１％で近似できるように、ｋとｕを夫々増やしても良い。
【００８９】
更新部２６は、選択した第１近傍特徴と第２近傍特徴の情報を決定部２２に出力する。
【００９０】
次いで、作成部２２は、特徴量及び追加特徴量毎に周辺密度を推定し（図１４のステップＳ２０５）、第１近傍特徴及び第２近傍特徴の中から、特徴量または追加特徴量毎に同じクラスに分類する特徴量または追加特徴量を決定する（図１４のステップＳ２０６）。決定部２２は決定した結果を参照できるテーブルを作成し（図１４のステップＳ２０７）、分類部１３に出力する。
【００９１】
次いで、分類部１３は、決定部１２で作成されたテーブルを参照し、特徴量及び追加特徴量毎にクラスＩＤを付与する（図１４のステップＳ２０８）。分類部１３は、各特徴量のクラスＩＤ及び各追加特徴量のクラスＩＤを管理部１４に出力する。
【００９２】
次いで、管理部１４は、閾値ｔｈｓ又は閾値ｔｈｃを変更する必要があるかをチェックする（図１４のステップＳ２０９）。閾値ｔｈｓ又は閾値ｔｈｃの変更が必要な場合には（図１４のステップＳ２０９のＹｅｓ）、閾値ｔｈｓの変更が必要であるかをチェックする（図１４のステップＳ２１０）。閾値ｔｈｓの変更が必要な場合には（図１４のステップＳ２１０のＹｅｓ）、閾値ｔｈｓ及び閾値ｔｈｃの値を決定部２２に出力し、ステップＳ２０５に戻る。閾値ｔｈｓの変更が必要ない場合は（図１４のステップＳ２１０のＮｏ）、閾値ｔｈｃの値を決定部２２に出力し、ステップＳ２０６に戻る。閾値ｔｈｓ及び閾値ｔｈｃの変更が必要ない場合には（図１４のステップＳ２０９のＮｏ）、処理を終了する。
【００９３】
なお、決定部２２、分類部１３及び管理部１４は、選択部２１から入力された第１近傍特徴及び第２近傍特徴の情報を用いて、図３のステップＳ１０５乃至ステップＳ１１０の処理を実行し、取得部１０が取得した特徴量にクラスＩＤを付与することもできる。
【００９４】
以上のように、本実施例によれば、識別対象を追加する際、追加する以前に処理した結果を利用した、効率的、かつ、高速なクラスタリング処理が可能となる。
【実施例３】
【００９５】
次に、第３の実施例に係る信号分類装置１００について説明する。なお、第１の実施例と同等の構成については、同一の符号を付与し、その説明を省略する。
【００９６】
図１７は、第３の実施例の信号分類装置１００ｃの機能構成を示したブロック図である。図１７に示したように、本実施例の信号分類装置１００は、取得部１０、選択部１１、決定部１２、分類部１３、管理部３４及び表示部３７から構成される。
【００９７】
なお、図１７において、管理部３４及び表示部３７は、取得部１０、選択部１１、作成部１２及び分類部１３と同様、ＣＰＵ１０１とＲＯＭ１０４に予め記録された所定のプログラムとの協働により実現される機能部である。
【００９８】
管理部３４は、分類部１３から取得したクラスＩＤの付与結果を表示部３７に出力する。
【００９９】
表示部３７は、管理部３４から取得したクラスＩＤの付与結果に基づき、表示部１０３を介し、画像や文字を用いて識別対象の分類結果を表示する。
【０１００】
次に、本実施例の信号分類装置１００の動作を説明する。図１８は、本実施例の信号分類装置１００によるクラスタリング処理の流れを示したフローチャートである。以下、図１８を参照して、本実施例の信号分類装置について説明する。
【０１０１】
まず、入力部１０６等を介して識別対象が入力されると（図１８のステップＳ１０１）、取得部１０は、入力された識別対象から特性を表す特徴量を取得する（図１８のステップＳ１０２）。取得部１０は、取得した特徴量を選択部１１に出力する。
【０１０２】
次いで、選択部１１は、各特徴量に対して、第１近傍特徴を選択する第１近傍特徴選択処理を実行する（図１８のステップＳ１０３）。また、選択部１１は、各特徴量に対して、第２近傍特徴を選択する第２近傍特徴選択処理を実行する（図１８のステップＳ１０４）。選択部１１は、選択した第１近傍特徴及び第２近傍特徴の情報を決定部１２に出力する。
【０１０３】
次いで、決定部１２は、特徴量毎に周辺密度を推定し（図１８のステップＳ１０５）、第１近傍特徴及び第２近傍特徴の中から、特徴量毎に同じクラスに分類する特徴量を決定する（図１８のステップＳ１０６）。決定部１２は決定した結果を参照できるテーブルを作成し（図１８のステップＳ１０７）、分類部１３に出力する。
【０１０４】
次いで、分類部１３は、決定部１２で作成されたテーブルを参照し、特徴量毎にクラスＩＤを付与する（図１８のステップＳ１０８）。分類部１３は、各特徴量のクラスＩＤを管理部３４に出力する。
【０１０５】
次いで、管理部３４は、各特徴量のクラスＩＤを表示部３７に出力する。
【０１０６】
次いで、表示部３７は、識別対象の分類結果を表示する（図１８のステップＳ３０１）。
【０１０７】
識別対象が顔画像を表す電気信号である場合、表示部３７は、例えば図１９のように、人物毎に分類し、整理した顔画像一覧を表示できる。また、特定の顔を選択して、同一人物の顔画像一覧を表示し、人物の検索を容易にすることもできる（図２０）。このように、表示部３７では、識別対象によって一意に定められることなく、各特徴量のクラスＩＤによる分類結果との組み合わせで複数のバリエーションを持って動作することが可能である。
【０１０８】
また、識別対象が音声のように画像とは異なる信号の場合には、以下のようになる。例えば、識別する対象となる信号が会議音声である場合、複数の区間に分割してクラスタリング処理（信号分類の処理）を行う。分類結果は、登場話者毎の発言のタイムラインを表示すると共に表示され、特定の再生位置あるいは、特定発言の視聴を容易に行うことができる（図２１）。また、識別対象が楽曲信号である場合に、複数の区間に分割してクラスタリング処理を行えば、特定の旋律や曲の最も印象的な部分（サビ）など、特定のパートの聴取を容易に行うことができる（図２２）。また、複数の楽曲を識別対象とする場合には、類似楽曲毎に分類し、整理した楽曲一覧を表示することも可能である（図２３）。
【０１０９】
図１８の戻り、本実施形態における管理部３４について説明する。管理部３４は、閾値ｔｈｓ又は閾値ｔｈｃを変更する必要があるかをチェックする（図１８のステップＳ１０９）。閾値ｔｈｓ又は閾値ｔｈｃの変更が必要な場合には（図１８のステップＳ１０９のＹｅｓ）、閾値ｔｈｓの変更が必要であるかをチェックする（図１８のステップＳ１１０）。閾値ｔｈｓの変更が必要な場合には（図１８のステップＳ１１０のＹｅｓ）、閾値ｔｈｓ及び閾値ｔｈｃの値を決定部１２に出力し、ステップＳ１０５に戻る。閾値ｔｈｓの変更が必要ない場合は（図１８のステップＳ１１０のＮｏ）、閾値ｔｈｃの値を決定部１２に出力し、ステップＳ１０６に戻る。閾値ｔｈｓ及び閾値ｔｈｃの変更が必要ない場合には（図１８のステップＳ１０９のＮｏ）、処理を終了する。
【０１１０】
以上のように、本実施例によれば、識別対象を複数のクラスに分類した後、分類結果を様々な形式で表示することで、視聴や検索、データ整理を容易に行うことができる。
【実施例４】
【０１１１】
第４の実施例に係る信号分類装置について説明する。なお、第１の実施例と同等の構成については、同一の符号を付与し、その説明を省略する。
【０１１２】
図２４は、第４の実施例に係る信号分類装置１００ｄの機能構成を示したブロック図である。図２４に示したように、本実施例の信号分類装置１００は、取得部１０、選択部１１、決定部４２、分類部１３及び管理部１４から構成され、決定部は更に判定部４６を有する。なお、図２４において、選択部１１、決定部４２は、取得部１０、分類部１３及び管理部１４と同様、ＣＰＵ１０１とＲＯＭ１０４に予め記録された所定のプログラムとの協働により実現される機能部である。
【０１１３】
判定部４６は、取得部１０で取得した各特徴量に対して、選択部１１が選択したｋ個の第１近傍特徴及びｕ個の第２近傍特徴の変更を制御する。判定部４６は、特徴量毎に更新した第１近傍特徴及び第２近傍特徴と、追加特徴量毎に選択した第１近傍特徴及び第２近傍特徴を決定部２２に出力する。
【０１１４】
決定部４２は、判定部４６が更新すると判定した特徴量毎の第１近傍特徴及び第２近傍特徴に関する情報を用いて、前記各特徴量及び前記各追加特徴量に対して周辺密度を推定する。決定部４２での周辺密度の推定は、第１の実施例における決定部１２と同様の方法である。
【０１１５】
次に、本実施例の信号分類装置１００の動作を説明する。図２５は、本実施例の信号分類装置１００によるクラスタリング処理の流れを示したフローチャートである。以下、図２５を参照して、本実施例の信号分類装置について説明する。
【０１１６】
まず、入力部１０６等を介して識別対象が入力されると（図２５のステップＳ１０１）、取得部１０は、入力された識別対象から特性を表す特徴量を取得する（図２５のステップＳ１０２）。取得部１０は、取得した特徴量を選択部１１に出力する。
【０１１７】
次いで、選択部１１は、各特徴量に対して、第１近傍特徴を選択する第１近傍特徴選択処理を実行する（図２５のステップＳ１０３）。また、選択部１１は、各特徴量に対して、第２近傍特徴を選択する第２近傍特徴選択処理を実行する（図２５のステップＳ１０４）。選択部１１は、選択した第１近傍特徴及び第２近傍特徴の情報を決定部４２に出力する。
【０１１８】
決定部４２は、特徴量の類似性を比較するための閾値ｔｈｓを参照し、選択部１１で選択された第１の近傍特徴と第２の近傍特徴の情報を用いて、前記各特徴に対して周辺密度を決定する（図２５のステップＳ１０５）。
【０１１９】
次いで、決定部４２は、第１近傍特徴及び第２近傍特徴の中から、特徴量毎に同じクラスに分類する特徴量を決定する（図２５のステップＳ１０６）。以下では、同じ特徴量に分類する特徴量の候補のことを修正候補と記載する。
【０１２０】
ここで、決定部４２が特徴量ｘｉと同じクラスに分類する特徴量ｘｊは、各々の特徴量毎の参照関係に関する情報を用いて決定する。より具体的には、特徴量ｘｉと特徴量ｘｊとはそれぞれが互いの近傍特徴に含まれている、または、特徴量ｘｉと特徴量ｘｊとは共通の近傍特徴を持っているという条件を満たすか否かを判定部４６が判定し、条件を満たす場合に、同じクラスに分類する特徴量の候補とする。条件を満たさない場合は互いの修正候補としない（図２５のステップＳ４０６）。
【０１２１】
たとえば、図１２で用いた１次元の特徴量ｘ０からｘ９の場合、参照関係の条件を満たさないのは、は表５における太枠部分、ｘ６及びｘ７の類似度Ｓ（８，ｊ）及びＳ（９，ｊ）である。したがって、ｘ８及びｘ９にとって、ｘ６及びｘ７は修正候補とはならない。
【表５】
2011191824.tif 000008
【０１２２】
決定部４２は決定された特徴量毎に参照できるテーブルを作成し（図２５のステップＳ１０７）、分類部１３に出力する。
【０１２３】
次いで、分類部１３は、決定部４２で作成されたテーブルを参照し、特徴量及び追加特徴量毎にクラスＩＤを付与する（図２５のステップＳ１０８）。分類部１３は、各特徴量のクラスＩＤ及び各追加特徴量のクラスＩＤを管理部１４に出力する。
【０１２４】
次いで、管理部１４は、閾値ｔｈｓ又は閾値ｔｈｃを変更する必要があるかをチェックする（図２５ステップＳ１０９）。閾値ｔｈｓ又は閾値ｔｈｃの変更が必要な場合には（図２５のステップＳ１０９のＹｅｓ）、閾値ｔｈｓの変更が必要であるかをチェックする（図２５のステップＳ１１０）。閾値ｔｈｓの変更が必要な場合には（図２５のステップＳ１１０のＹｅｓ）、閾値ｔｈｓ及び閾値ｔｈｃの値を決定部４２に出力し、ステップＳ１０５に戻る。閾値ｔｈｓの変更が必要ない場合は（図２５のステップＳ１１０のＮｏ）、閾値ｔｈｃの値を決定部４２に出力し、ステップＳ１０６に戻る。閾値ｔｈｓ及び閾値ｔｈｃの変更が必要ない場合には（図２５のステップＳ１０９のＮｏ）、処理を終了する。
【０１２５】
実験４により得た分類結果は、表６のようになる。これは、実験２により得た分類結果（表３）と同じ結果であるが、実験４では閾値ｔｈｃを０．１のように低く設定しても分類結果は変化しない。一方、実験２では、閾値ｔｈｃを０．１４以下に設定すると、ｘ８の周辺密度よりｘ７の周辺密度の方が高いために、ｙ（ｘ８）＝ｘ７となる。よって、ｘ４からｘ９のクラスＩＤは２となり望ましくない分類結果となる（過結合）。
【０１２６】
以上のように本発明によれば、特徴量の互いの参照関係を考慮することにより、効率を維持したまま、閾値に対する頑健性が増し、クラス分類の精度がより向上する。
【表６】
2011191824.tif 000009
【０１２７】
[変更例]
判定部は識別対象のもつ個別情報によって修正候補の判定を行ってもよい。
【０１２８】
たとえば、複数人の人物の顔を分類するクラスタリング処理を行う場合、識別対象として入力された同一の写真に写る各個人の顔を同じ分類としないように制御してもよい（図２６（ａ）参照）。より具体的には特徴量ｘi と特徴量ｘｊとが属する写真が同一の場合について説明する。
【０１２９】
まず、入力信号として、複数の識別対象が入力される際に、同一の写真から得られた識別対象であることを示す写真ＩＤを識別対象に付与する。ｘiが属する写真ＩＤが、 ＰＩ（ｘi）であるとき、類似した特徴量ｘiおよび特徴量ｘｊについて、ＰＩ（ｘi）＝ＰＩ（ｘｊ）が成り立つとき、収束するｙ（ｘi）は式２によって拘束される。
【０１３０】
更に、写真ＩＤの異なる特徴量ｚ（ｘi）についても、ｙ（ｘi）＝ｚ（ｘi）であるとき、はｘiに対して式３を適用する。
【数２】
2011191824.tif 000010
【数３】
2011191824.tif 000011
【０１３１】
これらにより、ひとつのクラスに分類される特徴群（図２６(b)）を複数のクラスに適切に分離することが可能になり、メモリ容量を要さずにより精度の高い分類が可能となる。
【０１３２】
なお、写真ＩＤを取らずに、入力手段等を介して同じグループとなる分類か否かの情報をユーザ等が入力してもよい。この場合、ユーザ等が決めた更新情報を更新情報取得部によって取得し、判定部が識別対象が同じ分類とならないように制御する。また、ユーザが別分類としたい識別対象について入力したものに対して異なるＩＤを付与し、ＩＤが異なるときに式２等を拘束条件として、修正候補の判定をおこなってもよい。
【０１３３】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、多くの発明を形成できる。例えば、実施形態に示される全構成要素からいくつかの構成要素を削除しても良い。さらに、異なる実施形態にわたる構成要素を適宜組み合わせても良い。
【符号の説明】
【０１３４】
１０１・・・制御部、１０２・・・操作部、１０３・・・表示部、１０４、１０５・・・記憶部、１０６・・・入力部、１０７・・・外部記憶装置、１０８・・・バス
１０・・・取得部、１１、２２・・・選択部、１２・・・決定部、１３・・・分類部、３４、１４・・・管理部、２５・・・追加取得部、２６・・・更新部、３７・・・表示部、４６・・・判定部
【図１】
2011191824.tif 000012
【図２】
2011191824.tif 000013
【図３】
2011191824.tif 000014
【図４】
2011191824.tif 000015
【図５】
2011191824.tif 000016
【図６】
2011191824.tif 000017
【図７】
2011191824.tif 000018
【図８】
2011191824.tif 000019
【図９】
2011191824.tif 000020
【図１０】
2011191824.tif 000021
【図１１】
2011191824.tif 000022
【図１２】
2011191824.tif 000023
【図１３】
2011191824.tif 000024
【図１４】
2011191824.tif 000025
【図１５】
2011191824.tif 000026
【図１６】
2011191824.tif 000027
【図１７】
2011191824.tif 000028
【図１８】
2011191824.tif 000029
【図１９】
2011191824.tif 000030
【図２０】
2011191824.tif 000031
【図２１】
2011191824.tif 000032
【図２２】
2011191824.tif 000033
【図２３】
2011191824.tif 000034
【図２４】
2011191824.tif 000035
【図２５】
2011191824.tif 000036
【図２６】
2011191824.tif 000037