信号分類装置
【課題】多量のメモリを用いずに分類可能な信号分類装置を提供する。
【解決手段】 入力された信号に含まれるN個の識別対象の特徴量を取得する取得部と、 前記特徴量毎に、前記特徴量からk個(1≦k≦N)の前記特徴量を第1近傍特徴として選択する第1の選択部と、互いに類似する前記特徴量から特徴群を生成し、取得したN個の前記特徴量から異なる前記特徴群に属するu個(1≦k+u≦N−2)の前記特徴量を第2の近傍特徴として選択する第2の選択部と、前記特徴量の類似性を比較するための閾値と、前記特徴量毎に算出した周辺密度とを用いて、同じ分類となる前記特徴量を決定する決定部と、前記特徴量の決定結果から分類を行う分類部と、前記閾値を管理する管理部と、を備える。
【解決手段】 入力された信号に含まれるN個の識別対象の特徴量を取得する取得部と、 前記特徴量毎に、前記特徴量からk個(1≦k≦N)の前記特徴量を第1近傍特徴として選択する第1の選択部と、互いに類似する前記特徴量から特徴群を生成し、取得したN個の前記特徴量から異なる前記特徴群に属するu個(1≦k+u≦N−2)の前記特徴量を第2の近傍特徴として選択する第2の選択部と、前記特徴量の類似性を比較するための閾値と、前記特徴量毎に算出した周辺密度とを用いて、同じ分類となる前記特徴量を決定する決定部と、前記特徴量の決定結果から分類を行う分類部と、前記閾値を管理する管理部と、を備える。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、信号分類装置に関する。
【背景技術】
【0002】
クラスタリング技術(信号分類技術)は、識別対象となるサンプル(標本)集合を、類似特徴を持つサンプルで構成される部分集合(クラス)に分類することを目的とする。このクラスタリング技術は、例えば、文字や図形、音声などを対象とした識別処理に適用できる。識別対象が顔画像であるとき、誤りなく識別できれば、一つのクラスは同一人物の顔写真だけで構成され、各クラスは夫々異なる人物の顔写真で構成される。また、識別対象が夫々1人が発話した音声データであるとき、誤りなく識別できれば、一つのクラスは同一話者の音声データで構成され、各クラスは夫々異なる話者の音声データで構成される。この識別処理を高い精度で実現するには、取得する特徴も重要であるが、クラスタリングの精度も重要である。
【0003】
従来方式である非特許文献1乃至3では、特徴空間内にて、同一クラスに属するサンプルは密集して分布することを前提としたクラスタリングを行う。具体的には、各サンプルの特徴を、近傍で潜在的に存在するクラスの分布の中心に更新し、同一クラスに属するサンプルを一箇所に集めることで、クラスタリングを実現する。非特許文献1では、各サンプルは、特徴間の類似度が閾値以上であるサンプル(近傍サンプル)との平均特徴に最も類似したサンプルに更新する。ここで、平均特徴の導出は、特徴空間の次元数が高次元に及ぶほど、演算量が増加する。
【0004】
そこで、非特許文献2及び非特許文献3では、潜在的に存在するクラスの、分布の中心への近さは、各サンプル周辺の密度の高さが表すとしている。周辺密度は例えば近傍サンプルの数で近似する。各サンプルは、周辺密度が高く類似度が閾値以上で、かつ、最も高い類似度を持つサンプルに更新する。特徴の更新には、周辺密度を用いるため、平均特徴を求める非特許文献1よりも演算量を削減できる。
【0005】
非特許文献2及び非特許文献3では、各サンプルに対し、周辺密度を計算する処理と、同じクラスに分類するサンプルを決定する処理とを行うには、サンプル間の類似度情報が必要となる。周辺密度を計算する処理と同じクラスに分類するサンプルを決定する処理とは同時に実行できない。そのため演算の重複を避け、効率的に処理を実行するためには、全ての組み合わせにおけるサンプル間の類似度情報をメモリ(バッファ)に記憶する必要がある。したがって、サンプルの2乗のオーダーとなる大量のメモリが必要である。
【0006】
また、周辺密度を計算する過程で、各サンプルに対して、類似度が閾値以上である近傍サンプルのサンプルIDと類似度を記憶することでも効率化できる。しかし、近傍サンプルの数は事前に予測できない上、閾値が最低値であれば、全てのサンプルが近傍サンプルとなるため、サンプルIDと類似度とを記憶する代替案を用いても、サンプルの2乗のオーダーとなるメモリを確保する必要がある。
【先行技術文献】
【非特許文献】
【0007】
【非特許文献1】“Mode−seeking by Medoidshifts”,Y.A.Sheikh, E.A.Khan and T.Kanade, IEEE International Conference on Computer Vision, 2007.
【非特許文献2】“A Graph−theoretic approach to nonparametric cluter analysis”, W.L.G.Koontz, P.Narendra, and K.Fukunaga, IEEE Trans. on Computer, c−25(9), 1976.
【非特許文献3】“Quick Shift and Kernel Methods for Mode Seeking”, A.Vedaldi and S.Soatto, ECCV2008, PartIV, LNCS5305, pp.705−718, 2008.
【発明の概要】
【発明が解決しようとする課題】
【0008】
本発明は上記問題を鑑み、多量のメモリを用いずに分類可能な信号分類装置を提供することを目的とする。
【課題を解決するための手段】
【0009】
上記目的を達成するために本発明の信号分類装置は、入力された信号に含まれるN個の識別対象の特徴量を取得する取得部と、前記特徴量毎に、前記特徴量からk個(1≦k≦N)の前記特徴量を第1近傍特徴として選択する第1の選択部と、互いに類似する前記特徴量から特徴群を生成し、取得したN個の前記特徴量から異なる前記特徴群に属するu個(1≦k+u≦N−2)の前記特徴量を第2の近傍特徴として選択する第2の選択部と、 前記特徴量の類似性を比較するための閾値と、前記特徴量毎に算出した周辺密度とを用いて、同じ分類となる前記特徴量を決定する決定部と、前記特徴量の決定結果から分類を行う分類部と、前記閾値を管理する管理部と、を備えたことを特徴とする。
【発明の効果】
【0010】
本発明によれば、多量のメモリを用いずに分類可能な信号分類装置を提供できる。
【図面の簡単な説明】
【0011】
【図1】本発明の実施例に係るハードウェア構成を示す図。
【図2】実施例1の機能構成を表わすブロック図。
【図3】実施例1のクラスタリング処理を表わすフローチャート。
【図4】クラスタリング処理の動作例を示す図。
【図5】クラスタリング処理の動作例を示す図。
【図6】クラスタリング処理の動作例を示す図。
【図7】第1近傍特徴選択処理を表わすフローチャート。
【図8】第1近傍特徴集合への特徴追加処理を表わすフローチャート。
【図9】第2近傍特徴選択処理を表わすフローチャート。
【図10】第2近傍特徴集合への特徴追加処理を表わすフローチャート。
【図11】比較実験1と実施例1のクラスタリング処理精度を示す図。
【図12】1次元の特徴量の標本を模式的に示す図。
【図13】実施例2の機能構成を表わすブロック図。
【図14】実施例2のクラスタリング処理を表わすフローチャート。
【図15】第1近傍特徴変更選択処理を表わすフローチャート。
【図16】第2近傍特徴変更選択処理を表わすフローチャート。
【図17】実施例3の機能構成を表わすブロック図。
【図18】実施例3のクラスタリング処理を表わすフローチャート。
【図19】実施例3に係る画像のクラスタリング処理結果の表示例。
【図20】実施例3に係る画像のクラスタリング処理結果の表示例。
【図21】実施例3に係る音声のクラスタリング処理結果の表示例。
【図22】実施例3に係る音楽のクラスタリング処理結果の表示例。
【図23】実施例3に係る音楽のクラスタリング処理結果の表示例。
【図24】実施例4の機能構成を表わすブロック図。
【図25】実施例4のクラスタリング処理を表わすフローチャート。
【図26】同一画像の人物に対するクラスタリング処理を表わす模式図。
【発明を実施するための形態】
【0012】
以下、本実施形態に関する信号処理装置について図面に基づいて説明する。
【0013】
本発明の実施例に関する信号処理装置は、画像中の被写体(たとえば人物)の分類または音響(例えば音楽や人の声)の分類をすることが可能であり、分類結果は、画像中の被写体毎の写真の分類や人物毎の発言の分類に用いることが可能である。したがって、写真や動画などを分類して提示する動画再生装置や静止画を用いたスライドショーなどにも適用可能である。
【実施例1】
【0014】
まず、本実施の形態にかかる信号分類装置のハードウェア構成について図1を用いて説明する。信号分類装置100は、装置全体を制御するCPU(Central Processing Unit)等の制御部101と、各種データや各種プログラムを記憶するROM(Read Only Memory)104やRAM105(Random Access Memory)等の記憶部と、各種データや各種プログラムを記憶するHDD(Hard Disk Drive)やCD(Compact Disk)ドライブ装置等の外部記憶部107と、これらを接続するバス108とを備えており、通常のコンピュータを利用したハードウェア構成となっている。また、信号分類装置100には、画像を表示する表示部103と、ユーザの指示入力を受け付けるキーボードやマウス等の操作部102と、文字、画像、音声党の識別対象を電子信号に変換する入力部106と、外部装置の通信を制御する通信部やI/F(インターフェース)とが有線又は無線により各々接続される。
【0015】
CPU101は、RAM105の所定領域を作業領域として、ROM104に予め記憶された各種制御プログラムとの協働により各種処理を実行し、信号分類装置100を構成する各部の動作を統括的に制御する。また、CPU101は、ROM104に予め記憶された所定のプログラムとの協働により、後述する取得部10、選択部11、作成部12、クラスタリング部13、管理部14の各機能部を実現させる。 操作部102は、各種入力キー等を備え、ユーザから操作入力された情報を入力信号として受け付け、その入力信号をCPU101に出力する。
【0016】
表示部103は、液晶表示装置(LCD:Liquid Crystal Display)等の表示手段により構成され、CPU101からの表示信号に基づいて、各種情報を表示する。なお、表示部103は、操作部102と一体的にタッチパネルを構成する様態としてもよい。
【0017】
ROM104は、信号分類装置100の制御にかかるプログラムや各種設定情報等を書き換え不可能に記憶する。RAM105は、SDRAM等の記憶手段であって、CPU101の作業エリアとして機能し、バッファ等の役割を果たす。
【0018】
入力部106は、音声や文字、図形等の識別対象を電気信号に変換し、PCM(Pulse Code Modulation)等の数値データとしてCPU101に出力する。
【0019】
記憶部107は、磁気的又は光学的に記憶可能な記憶媒体を有し、入力部106を介して取得された信号や、図示しない通信部やI/F(インターフェース)等を介して外部から入力される信号等のデータを記憶する。また、記憶部107は、後述するクラスタリング装置により識別対象の分類結果情報を記憶する。
【0020】
図2は、第1の実施例の信号分類装置100aの機能構成を示したブロック図である。なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、多くの発明を形成できる。例えば、実施形態に示される全構成要素からいくつかの構成要素を削除しても良い。さらに、異なる実施形態にわたる構成要素を適宜組み合わせても良い。
【0021】
本実施例の信号分類装置100aは、取得部10、第1の選択部及び第2の選択部からなる選択部11、決定部12、分類部13及び管理部14等を備えている。
【0022】
取得部10は、入力部106等を介して入力された信号に含まれる識別対象の特徴量を取得する。特徴量とは識別対象となる信号、例えば画像中の人物はたは顔、音の中の声などを個別に認識するための特性を示すものである。識別対象が顔の画像で、人物毎に分類する場合には、特徴量を、画素値を表すベクトルを変換して求める。このとき用いる変換は、例えば、ヒストグラム平坦化などを用いる。識別対象が音声で、話者毎に分類する場合には、例えばLPCケプストラムやMFCC等のケプストラム系特徴量を取得すれば良い。また、Y.Akitaによる“Unsupervised Speaker Indexing using Anchor Models and Automatic Transcription of Discussions”, ISCA 8th European Conference on Speech Communication and Technology(Euro Speech), September 2003に記載された手法を用いてケプストラム系特徴量を加工しても良い。さらに、識別対象の音声は、予め検出した無音毎に分割する、一定時間毎に分割する等の方法により、その個数を増やしても良い。識別対象が音全般で、音楽、音声、雑音といった音の種別を分類する場合には、E.Scheirerらによる“Construction and Evaluation of a Robust Multifeature Speech/Music Discriminator”,IEEE International Conference on Acoustic Speech, and Signal Processing, April 1997に記載された手法を用いても良い。取得部10が取得した特徴量は選択部11に出力される。
【0023】
選択部11は、取得部10が取得したN個の特徴量夫々に対して、取得した特徴量の中から、特徴が類似したk個(1≦k≦N)の第1近傍特徴を選択する第1の選択部と、互いに類似する特徴量から特許群を生成し、異なる特徴群に属するu個の第2近傍特徴を選択する第2の選択部とからなる。特徴群は、取得部10が取得した特徴量の中から、類似した特徴同士を群として纏めたものである。特徴群の生成は、特徴量間の類似度を計算する過程で逐次的に実行できる簡易的な処理であれば良い。選択部11は、取得したN個の特徴量を用いて、複数の特徴群を生成する。選択部11は、選択した第1近傍特徴及び第2近傍特徴を決定部12に出力する。
【0024】
決定部12は、特徴量の類似性を比較するための閾値を参照し、選択部11で選択された第1近傍特徴と第2近傍特徴を用いて、各特徴量に対して周辺密度を算出する。次に、特徴量毎に、第1近傍特徴と第2近傍特徴の中から同じクラス(集合)に分類する特徴量を決定する。特徴量毎に関係する特徴量が参照できるテーブルを作成し、分類部13に出力する。特徴量は表形式で出力するのが好ましいが、特徴量毎に第1近傍特徴と第2近傍特徴から決定された特徴量がわかるような形式ならばこれに限らない。
【0025】
分類部13は、決定部12にて作成されたテーブルを参照し、各特徴量に対して、クラスIDを付与する。クラスIDは同じ集合となるものに付与する。クラスIDの付与結果は管理部14に出力する。
【0026】
管理部14は、決定部12で用いた閾値を管理する。更に閾値を異なる値に変更した場合には、決定部12に変更した閾値を出力する。決定部12は管理部14が変更した閾値を取得した後、再度テーブルを作成する。
【0027】
次に、本実施例の信号分類装置100の動作を説明する。図3は、本実施例の信号分類装置100によるクラスタリング処理の流れを示したフローチャート、図4乃至図6である。以下、図3乃至図6に示した動作例O1乃至O8を参照して、本実施例の信号分類装置について説明する。
まず、入力部106を介して識別対象となる信号が入力される(図3のステップS101)。取得部10は、入力された識別対象から特徴量を取得する(図3のステップS102、図4の動作例O1参照)。取得部10は、取得した特徴量を選択部11に出力する。
【0028】
次いで選択部11は、各特徴量に対して第1近傍特徴を選択する、第1近傍特徴選択処理を実行する(図3のステップS103)。特徴量xiの第1の近傍特徴は、特徴量xiと類似度の高い上位k個の特徴量とする(図4の動作例O2及び図5の動作例O3参照)。
【0029】
ここで、第1近傍特徴選択処理(ステップS103)の詳細な動作を、図7を参照して説明する。なお、取得部10にて取得した特徴量はxi(i=0,1,...,N−1)で表す。
【0030】
まず、第1の選択部は、特徴量の番号を参照できる変数i=1を設定し、2番目の特徴を参照できる状態にする(ステップS11)。同様に、変数j=0を設定し、1番目の特徴を参照できる状態にする(ステップS12)。
【0031】
次いで選択部11は、特徴量xiと特徴量xjの類似度S(i,j)を計算する(ステップS13)。類似度は、特徴量をベクトルとして表現したものである。類似度は特徴量間のユークリッド距離の逆数、最大値からユークリッド距離を引いた値としても良い。また、特徴量同士の内積がなす角の余弦としても良い。
【0032】
次いで第1の選択部は、特徴量xiの第1近傍特徴の集合RFiに特徴量xjを追加するか否かを判定し追加処理を実行する、集合RFiと特徴量xjを対象とした第1の近傍特徴の集合への特徴追加処理を行う(ステップS14)。第1近傍特徴の集合への特徴追加処理の詳細な動作は図8を参照して説明する。
【0033】
第1の選択部は、処理対象となる特徴量xaとして特徴量xiを、第1近傍特徴の集合RFaとして集合RFiを設定する(ステップS21)。次に、集合RFaに追加するか否かを判定し追加処理を実行したい特徴量xbとして、特徴量xjを設定する(ステップS22)。
【0034】
次いで、特徴量xaの第1近傍特徴の集合RFaにk個の特徴量が含まれているか否かを確認する(ステップS23)。k個の特徴量が含まれている場合には(ステップS23のYes)、そのままステップS25に進む。ここで、k個の特徴量が含まれていない場合は(ステップS23のNo)、集合RFaに特徴量xbを加えた後(ステップS24)、処理を終了する。
【0035】
第1の選択部は、集合RFaの中で特徴量xaとの類似度が最も低い特徴量xcを取得する(ステップS25)。次に、特徴量xaと特徴量xbの類似度S(a,b)と、特徴量xaと特徴量xcの類似度S(a,c)を比較する(ステップS26)。S(a,b)がS(a,c)より大きい場合には(ステップS26のYes)、特徴量xcの替わりに、特徴量xbを集合RFaに追加した後(ステップS27)、処理を終了する。S(a,b)がS(a,c)以下である場合には(ステップS26のNo)、そのまま処理を終了する。
【0036】
次いで特徴量xjの第1近傍特徴の集合RFjに特徴量xiを追加するか否かを判定し追加処理を実行する、集合RFjと特徴量xiを対象とした第1近傍特徴の集合への特徴追加処理を行う。この特徴追加処理は、ステップS21とステップS22を除き、ステップS14で行う処理と同様に実行できる。ステップS21では、特徴量xaとして特徴量xj、集合RFaとして集合RFjを設定する。また、ステップS22では、特徴量xbとして、特徴量xiを設定する。
【0037】
図7の、第一近傍特徴選択処理の詳細な動作についての説明に戻る。第1の選択部は、特徴量xiとの類似度を求める特徴量として、次の特徴量を参照するため、j=j+1を設定する(ステップS16)。次に、新たに設定した特徴量xjが特徴量xiと同一のものであるかを判定する(ステップS17)。特徴量xjと特徴量xiが同一のものである場合(ステップS17のYes)、ステップS18に進む。特徴量xjと特徴量xiが異なるものである場合(ステップS17のNo)、類似度計算を行うためステップS13に戻る。
【0038】
第1の選択部は、次の特徴量を参照するため、i=i+1を設定した後(ステップS18)、取得した全ての特徴量に対してステップS12乃至ステップS18の処理を実行したか否かを判定する(ステップS19)。全ての特徴量に対して処理を完了している場合には(ステップS19のYes)、処理を完了する。全ての特徴量に対して処理を完了していない場合は(ステップS19のNo)、ステップS12に戻る。
【0039】
図3に戻って、第1近傍特徴選択処理に続く第2近傍特の選択について説明する。選択部11は、各特徴量に対して第2近傍特徴を選択する、第2近傍特徴選択処理を実行する(図3のステップS104)。特徴量xの第2近傍特徴は、類似度の高い上位u個の特徴量とするが、u個の特徴量はお互いに異なる特徴群に属するとする(図4の動作例O2及び図5の動作例O3参照)。特許群とは、互いに類似する複数個の特徴量からなる集合である。ここで、第2近傍特徴選択処理の詳細な動作を、図9を参照して説明する。
【0040】
まず、第2の選択部は、1番目の特徴量x0を要素に持つ特徴群を新規作成する(ステップS31)。次に、特徴量の番号を参照できる変数i=1を設定し、2番目の特徴量を参照できる状態にする(ステップS32)。同様に、変数j=0、jj=0を設定し、1番目の特徴量を参照できる状態にする(ステップS33)。
【0041】
次いで、第2の選択部は、ステップS11と同様の方法にて、特徴量xiと特徴量xjの類似度S(i,j)を計算する(ステップS34)。次に、第2の選択部は、類似度S(i,j)が閾値thm以上となり、特徴量xiと特徴量xjが同じ特徴群に分類され得るか否かを判定する(ステップS35)。閾値thmを十分信頼できる値とするため、例えば、類似度の最大が1であるときはthm=0.9と設定する。類似度S(i,j)が閾値thm以上である場合には(ステップS35のYes)、特徴量xiを特徴量xjと同じ特徴群に分類した後(ステップS36)、ステップS37に進む。類似度S(i,j)が閾値thm未満である場合には(ステップS35のNo)、そのままステップS37に進む。
【0042】
次いで、第2の選択部は、特徴量xiの第2近傍特徴の集合RSiに特徴量xjを追加するか否かを判定し追加処理を実行する、集合RSiと特徴量xjを対象とした第2近傍特徴の集合への特徴追加処理を行う。ここで、第2の近傍特徴の集合への特徴追加処理の詳細な動作を、図10を参照して説明する。
【0043】
まず、第2の選択部は、処理対象となる特徴量xaとして特徴量xiを、第2近傍特徴の集合RSaとして集合RSiを設定する(ステップS51)。次に、集合RSaに追加するか否かを判定し追加処理を実行したい特徴量xbとして、特徴量xjを設定する(ステップS52)。
【0044】
次いで、第2の選択部は、集合RSaの中で、特徴量xbと同じ特徴群に属する特徴量があるか否かを判定する(ステップS53)。集合RSaの中で、特徴量xbと同じ特徴群に属する特徴量xdが存在した場合(ステップS53のYes)、ステップS54に進む。ステップS54では、特徴量xaと特徴量xbの類似度S(a,b)と、特徴量xaと特徴量xdの類似度S(a,d)を比較する。S(a,b)がS(a,d)より大きい場合には(ステップS54のYes)、特徴量xdの替わりに、特徴量xbを集合RSaに追加した後(ステップS55)、処理を終了する。S(a,b)がS(a,d)以下である場合には(ステップS54のNo)、そのまま処理を終了する。集合RSaの中で、特徴量xbと同じ特徴群に属する特徴がない場合には(ステップS53のNo)、ステップ56に進む。
【0045】
次いで、第2の選択部は、特徴量xaの第2近傍特徴の集合RSaにu個の特徴量が含まれているか否かを確認する(ステップS56)。u個の特徴量が含まれている場合には(ステップS56のYes)、そのままステップS58に進む。ここで、u個の特徴量が含まれていない場合は(ステップS56のNo)、集合RSaに特徴量xbを加えた後(ステップS57)、処理を終了する。
【0046】
次いで、第2の選択部は、集合RSaの中で、特徴量xaとの類似度が最も低い特徴量xcを取得する(ステップS58)。次に、特徴量xaと特徴量xbの類似度S(a,b)と、特徴量xaと特徴量xcの類似度S(a,c)を比較する(ステップS59)。S(a,b)がS(a,c)より大きい場合には(ステップS59のYes)、特徴量xcの替わりに、特徴量xbを集合RSaに追加した後(ステップS60)、処理を終了する。S(a,b)がS(a,c)以下である場合には(ステップS59のNo)、そのまま処理を終了する。
【0047】
図9に戻り、第2近傍特徴選択処理の詳細な動作について説明する。次いで、第2の選択部は、特徴量xiとの類似度を求める特徴量として、次の特徴量を参照するため、j=j+1を設定する(ステップS38)。次に、新たに設定した特徴量xjが特徴量xiと同一のものであるかを判定する(ステップS39)。特徴量xjと特徴量xiが同一のものである場合(ステップS39のYes)、ステップS40に進む。特徴量xjと特徴量xiが異なるものである場合(ステップS39のNo)、類似度計算を行うためステップS33に戻る。
【0048】
次いで、第2の選択部は、特徴量xiが既存の特徴群に分類されたか否かを判定する(ステップS40)。特徴量xiが既存の特徴群に分類されている場合には(ステップS40のYes)、そのままステップS42に進む。特徴量xiが既存の特徴群に分類されていない場合には(ステップS40のNo)、特徴量xiを要素に持つ特徴群を新規作成した後(ステップS41)、ステップS42に進む。
【0049】
次いで、選択部11は、特徴量xjjの第2近傍特徴の集合RSjjに特徴量xiを追加するか否かを判定し追加処理を実行する、集合RFjjと特徴量xiを対象とした第2近傍特徴の集合への特徴追加処理を行う。この特徴追加処理は、ステップS51とステップS52を除き、ステップS37で行う処理と同様に実行できる。ステップS51では、特徴量xaとして特徴量xjj、集合RSaとして集合RSjjを設定する。また、ステップS52では、特徴量xbとして、特徴量xiを設定する。
【0050】
次いで、第2の選択部は、特徴量xiが属する可能性のある次の第2近傍特徴の集合を参照するため、jj=jj+1を設定する(ステップS43)。次に、新たに設定した特徴量xjjが特徴量xiと同一のものであるかを判定する(ステップS44)。特徴量xjjと特徴量xiが同一のものである場合(ステップS44のYes)、ステップS45に進む。特徴量xjjと特徴量xiが異なるものである場合(ステップS44のNo)、第2近傍特徴の集合への特徴追加処理を行うためステップS42に戻る。
【0051】
次いで、第2の選択部は、次の特徴量を参照するため、i=i+1を設定した後(ステップS45)、取得した全ての特徴量に対してステップS33乃至ステップS45の処理を実行したか否かを判定する(ステップS46)。全ての特徴量に対して処理を完了している場合には(ステップS46のYes)、処理を完了する。全ての特徴量に対して処理を完了していない場合は(ステップS46のNo)、ステップS33に戻る。
【0052】
ここで選択部11は、第2近傍特徴選択処理にて、特徴量xiの第2近傍特徴の集合RSiには特徴量xiと同じ特徴群に属する特徴量を含まない制約を加えても良い。あるいは、特徴量xiの第2近傍特徴の集合RSiには第1近傍特徴の集合RFiの特徴量を含まない制約を加えても良い。
【0053】
選択部11は、図7に示した第1近傍特徴選択処理と、図9に示した第2近傍選択処理を並列して実行してもよい。並列実行の際は、まず、ステップS11及びステップS12と、ステップS31乃至ステップS33を順に行う。次に、類似度計算の処理(ステップS13あるいはステップS34)を行った後、ステップS14乃至ステップS17と、ステップS35乃至ステップS39を順に行う。次いで、ステップS40乃至ステップS44を行った後、処理終了に繋がる処理(ステップS18とステップS19、あるいは、ステップ45とステップ46)を行うことが望ましい。
【0054】
選択部11が選択する第1近傍特徴の数kは1以上N−2以下で設定し、第2近傍特徴の数uは、k+uがN−2以下となるように設定する。また、k及びuは、Nの値によらない固定値しても良いし、Nに比例して増やしても良い。さらには、kとuは独立して扱っても良いし、同じ値としても良い。例えば、N=200のとき、kとuをNの1%と設定し、k=2、u=2としてもよい。
【0055】
選択部11は、最後に、選択した第1近傍特徴及び第2近傍特徴の情報を決定部12に出力する。
【0056】
決定部12は、特徴量の類似性を比較するための閾値thsを参照し、選択部11で選択された第1の近傍特徴と第2の近傍特徴の情報を用いて、前記各特徴量に対して周辺密度を決定する(図3のステップS105、図5の動作例O4参照)。
【0057】
決定部12で決定される特徴量xiの周辺密度Piは、閾値thsと、非特許文献1や非特許文献2に記載されているようなガウス関数を用いて、例えば式1で算出できる。式1にて、類似度の最大値は1とし、RFiは特徴量xiの第1近傍特徴の集合、RSiは特徴量xiの第2近傍特徴の集合とする。また、式1にて、αは、第2近傍特徴に対する重みであり、例えば0.5と設定できる。
【数1】
【0058】
次いで、決定部12は、第1近傍特徴及び第2近傍特徴の中から、特徴量毎に同じクラスに分類する特徴量を決定し(図3のステップS106)、決定した結果を参照できるテーブルを作成し(図3のステップS107、図5の動作例O5)、分類部13に出力する。作成されるテーブルは特徴量毎に参照できればよく、識別対象毎にまとめられた形式のデータ構造であっても、識別対象の特性を表わす個々の特徴量毎に参照できる形式であればよい。
【0059】
決定部12にて、特徴量xiと同じクラス(分類)に分類する特徴量y(xi)は、第1近傍特徴の集合RFi及び第2近傍特徴の集合RSiの中で、周辺密度が特徴量xiよりも高く、特徴量xiとの類似度が最も大きい特徴量とする。特徴量xiの周辺密度より高い周辺密度を持つ特徴量が集合RFi及び集合RSiの中に存在しなければ、特徴量y(xi)は特徴量xiとする。また、特徴量の類似性を比較するための閾値thcを参照し、求めた特徴量y(xi)と特徴量xiの類似度が閾値thcを下回った場合には、特徴量y(xi)を特徴量xiに修正する。ここで、閾値thcは閾値thsと同じでも良いし、閾値thsから線形変換によって求めても良い。あるいは閾値thcは、閾値thsと独立して設定してもいい。なお、以下では、特徴量xiから特徴量y(xi)を求めることを特徴量xiに関数yを作用させると表現する。
【0060】
次いで、分類部13は、決定部12で作成された表形式のテーブルを参照し、特徴量毎にクラスIDを付与する(図3のステップS108、図6の動作例O6及びO7参照)。分類部13は、各特徴量のクラスIDを管理部14に出力する。
【0061】
分類部13は、各特徴量xiに対して、特徴量xiと同じクラスに分類する特徴量y(xi)が同じ特徴量を指すか否かを判定し、指せば終了、指さなければxi=y(xi)として再び関数yを作用させる。関数yを作用させる処理は、作用させた結果が変化しなくなるまで繰り返す(図6の動作例O6参照)。そして、関数yを作用させ続けて得られた結果Yが等しい特徴量同士を同じクラスに分類する(図6の動作例O7参照)。
【0062】
分類部13は、テーブルを参照してクラスIDを付与した後、第1近傍特徴及び第2近傍特徴の情報を用いて、類似した特徴量を持つクラスを一つに纏める統合処理を行っても良い。例えば、閾値thnを設定し、特徴量xiの第1近傍特徴の集合RFi及び第2近傍特徴の集合RSiの中で、閾値thn以上の類似度を持ち、異なるクラスIDが付与された特徴量xnが存在した場合(図5の動作例O3における、x0の第2近傍特徴x6参照)、特徴量xiと特徴量xnが所属するクラスを一つに纏める(図6の動作例O8参照)。閾値thnは、類似度の最大値が1であるとき、例えば、0.6に設定できる。
【0063】
管理部14は、閾値ths又は閾値thcを変更する必要があるかをチェックする(図3のステップS109)。閾値ths又は閾値thcの変更が必要な場合には(図3のステップS109のYes)、閾値thsの変更が必要であるかをチェックする(図3のステップS110)。閾値thsの変更が必要な場合には(図3のステップS110のYes)、閾値ths及び閾値thcの値を作成部12に出力し、ステップS105に戻る。閾値thsの変更が必要ない場合は(図3のステップS110のNo)、閾値thcの値を決定部12に出力し、ステップS106に戻る。閾値ths及び閾値thcの変更が必要ない場合には(図3のステップS109のNo)、処理を終了する。なお、管理部14から変更された閾値ths及び閾値thcを取得した決定部12は、閾値にあわせて再度テーブルを作成する。
【0064】
管理部14は、分類部13から取得したクラスIDの付与結果を元に閾値ths及び閾値thcの値を変更しても良い。例えば、クラス数を算出することによって変更してもよい。特徴量数Nに対して、分類されたクラス数が一定の割合以上の個数である場合、クラス数を削減するため、閾値ths及び閾値thcの値を高くする。特徴量数に対して一定の割合以下の個数であれば、クラス数を増やすため、閾値ths及び閾値thcの値を低くする。さらに一定の割合ではなく、所定のクラス数を基準にして閾値ths及び閾値thcの値を変更しても良い。
【0065】
また管理部14は、操作部102を通じてユーザから入力された値を元に閾値ths及び閾値thcの値を変更しても良い。また、閾値ths及び閾値thcの値は一度に限らず何度でも実行することができる。さらには、変更する閾値に閾値thnを加えても良い。なお、閾値thnの変更のみの場合には、ステップS108に戻れば良い。
【0066】
以上のように、本実施例によれば、全ての特徴量の組み合わせにおける類似度情報は必要なく、特徴数Nのオーダー(=k+u倍<N倍)となるメモリを用意することによって、識別対象となる信号のクラスタリング(分類)を行うことができる。
【0067】
また、特徴量間の類似性を比較するための閾値thsを変更した場合、周辺密度の推定には選択した所定個数の特徴量(標本)との類似度のみ参照する。したがって、非常に高速にクラスタリングを行うことが可能である。更に、閾値thsを対話的に変更するインタラクティブ処理が実現できる。
【0068】
ここで、全ての組み合わせにおけるサンプル間の類似度情報をメモリ(バッファ)に記憶した場合(比較実験1)に対して本実施(実験1)を組み込み、特徴量の次元数が5120の顔画像10000枚に対するクラスタリングの処理時間を測定した結果を表1に示した。比較実験1に比べ、実験1はメモリ使用量を削減し、閾値ths変更後の処理時間も短縮できていることが確認できる。
【表1】
【0069】
閾値thcが低い値を取る程、特徴量xiは異なる特徴量に更新されやすい(y(xi)≠xi)。この場合、特徴量の集合が過剰に纏まり、精度劣化に繋がる可能性がある。本実施例の場合、各特徴量は所定個数の特徴量を参照することで特徴量が過剰に纏ることなく精度劣化を低減できる。更に、第1近傍特徴だけでなく、近傍特徴同士が異なる特徴群に属しているかを考慮した第2近傍特徴を用いることで、多くの特徴量を効率的に纏めることができる。これにより閾値thcの値が高いときに精度向上に繋げることができる。図11は、比較実験1と同様の手法で、特徴量の次元数が5120の顔画像828枚(登場人物73人)に対するクラスタリング精度を測定した結果である(閾値thc=閾値ths、閾値thn=∞)。精度は再現率、適合率の調和平均F値(=2*再現率*適合率/(再現率+適合率))で表している。適合率は、各クラスが一人の人物のデータで構成されているか否かを表す尺度である。具体的には、各クラスにて、属する特徴量の中で同一人物に纏められる特徴量数をCとし、対応する同一人物の総特徴量数をRとしたとき、クラス毎に求めたC/Rの平均値を適合率とする。なお、特徴量数Cを設定する際、複数の人物の候補があるならば、最大値を持つ人物を選択する。また、再現率は、各人物が一つのクラスに分類されているか否かを表す尺度である。具体的には、各人物にて総特徴量数をRとしたとき、対応する人物を最も多く含むクラスを一つ選択し、選択したクラスに属する特徴量の中で対応する人物の特徴量数をCとしたとき、人物毎に求めたC/Rの平均値を再現率とする。なお、同じクラスを複数回選択することはできない。図11より、閾値thcが低い値のときと、閾値thcが高い値のときで本発明の効果を確認することができる。
【0070】
また、図12は1次元の特徴量x0からx9を模式的に示したものである。x0からx9を識別対象とした動作例として、比較実験1の手法を用いた結果(表2)、実験2(表3)、実験3(表4)を示した。こおで、ユークリッド距離をDとしたとき、類似度は1/(1+D)で定義し、第2近傍特徴に対する重みαは1、閾値ths及び閾値thcは共に0.27とした。実験3では、第2近傍特徴を用いるため、同じ使用メモリでもより距離の離れた特徴量を参照でき、x0からx7を一つのクラスとみなせる。
【表2】
【表3】
【表4】
【実施例2】
【0071】
次に、第2の実施例に係る信号分類装置100について説明する。なお、上述した第1の実施例と同等の構成については、同一の符号を付与し、その説明を省略する。
【0072】
図13は、第2の実施例に係る信号分類装置100bの機能構成を示したブロック図である。図13に示したように、本実施例の信号分類装置100は、取得部10、選択部21、追加取得部25、更新部26、決定部22、分類部13及び管理部14から構成される。なお、図13において、選択部21、追加取得部25、更新部26及び決定部22は、取得部10、分類部13及び管理部14と同様、CPU101とROM104に予め記録された所定のプログラムとの協働により実現される機能部である。
【0073】
選択部21は、取得部10が取得したN個の特徴量夫々に対して、取得した特徴量の中から、特徴量が類似したk個の第1近傍特徴を選択する第1の選択部と、互いに類似する特徴量から特許群を生成し、異なる特徴群に属するu個の第2近傍特徴を選択する第2の選択部とからなる。選択部11は、特徴量毎に選択した第1近傍特徴及び第2近傍特徴を決定部12に出力し、更新部26にも出力する。
【0074】
追加取得部25は、入力部106等を介して追加入力された識別対象の特性を表す特徴量を取得する。追加取得部25は、取得部10と同様の方法で特徴量を取得し、取得した特徴量を追加特徴量として更新部26に出力する。
【0075】
更新部26は、取得部10で取得した特徴量の数をN、追加取得部25で取得した追加特徴量の数をMとし、各特徴量に対して、追加特徴量の情報を参照して選択部21が選択したk個の第1近傍特徴及びu個の第2近傍特徴を変更する。更新部26は、N+M個の特徴量及び追加特徴量の中から、各追加特徴量に対し、k個の第1近傍特徴及びu個の第2近傍特徴を選択する。更新部26は、特徴量毎に更新した第1近傍特徴及び第2近傍特徴と、追加特徴量毎に選択した第1近傍特徴及び第2近傍特徴を決定部22に出力する。
【0076】
決定部22は、更新部26が更新した特徴量毎の第1近傍特徴及び第2近傍特徴に関する情報と、更新部26が選択した追加特徴量毎の第1近傍特徴及び第2近傍特徴に関する情報とを用いて、前記各特徴量及び前記各追加特徴量に対して周辺密度を推定する。決定部22での周辺密度の推定は、第1の実施例における決定部12と同様の方法である。
【0077】
決定部22は、決定部12と同様に、特徴量及び追加特徴量毎に同じクラスに分類する特徴量または追加特徴量を参照できるテーブルを作成し、分類部13に出力する。
【0078】
次に、本実施例の信号分類装置100の動作を説明する。図14は、本実施例の信号分類装置100によるクラスタリング処理の流れを示したフローチャートである。以下、図14を参照して、本実施例の信号分類装置について説明する。
【0079】
まず、入力部106等を介して識別対象が入力されると(図14のステップS101)、取得部10は、入力された識別対象から特性を表す特徴量を取得する(図14のステップS102)。取得部10は、取得した特徴量を選択部21に出力する。
【0080】
次いで、選択部21は、各特徴量に対して、第1近傍特徴を選択する第1近傍特徴選択処理を実行する(図14のステップS103)。また、選択部21は、各特徴量に対して、第2近傍特徴を選択する第2近傍特徴選択処理を実行する(図14のステップS104)。選択部21は、選択した第1近傍特徴及び第2近傍特徴の情報を決定部22及び更新部26に出力する。
【0081】
次いで、入力部106等を介して識別対象が追加入力されると(図14のステップS201)、追加取得部25は、追加入力された識別対象から特徴量を取得する(図14のステップS202)。追加取得部25は、取得した追加特徴量を更新部26に出力する。
【0082】
次いで、更新部26は、取得部10が取得した特徴量毎に第1近傍特徴を変更する処理と、追加取得部25が取得した追加特徴量毎に第1近傍特徴を選択する、第1近傍特徴変更選択処理を行う(図14のステップS203)。ここで、第1の近傍特徴変更選択処理の詳細な動作を、図14を参照して説明する。なお、取得部10にて取得した特徴量は、xi(i=0,1,...,N−1)で表し、追加取得部25にて取得した追加特徴量は、xi(i=N,N+1,...,N+M−1)で表す。
【0083】
まず、更新部26は、特徴量の番号を参照できる変数i=Nを設定し、1番目の追加特徴量を参照できる状態にする(図15のステップS71)。以下、ステップS12乃至ステップS18は、実施例1の図7のフローチャートにおけるステップS12乃至ステップS18と同様であるので説明を省略する。
【0084】
次いで、更新部26は、取得した全ての追加特徴量に対して、ステップS12乃至ステップS18の処理を実行したか否かを判定する(図15のステップS79)。全ての追加特徴量に対して処理を完了している場合には(ステップS79のYes)、処理を完了する。全ての追加特徴量に対して処理を完了していない場合は(ステップS79のNo)、ステップS12に戻る。
【0085】
続いて、更新部26は、取得部10が取得した特徴量毎に第の近傍特徴を変更する処理と、追加取得部25が取得した追加特徴量毎に第2近傍特徴を選択する、第2近傍特徴変更選択処理を行う(図14のステップS204)。ここで、第2近傍特徴変更選択処理の詳細な動作を、図16を参照して説明する。
【0086】
まず、更新部26は、特徴量の番号を参照できる変数i=Nを設定し、1番目の追加特徴量を参照できる状態にする(ステップS82)。以下、ステップS33乃至ステップS45は、実施例1における図9のフローチャートにおけるステップS33乃至ステップS45と同じであり、同様に実行する。
【0087】
次いで、更新部26は、取得した全ての追加特徴量に対して、ステップS33乃至ステップS45の処理を実行したか否かを判定する(ステップS96)。全ての追加特徴量に対して処理を完了している場合には(ステップS96のYes)、処理を完了する。全ての追加特徴量に対して処理を完了していない場合は(ステップS96のNo)、ステップS33に戻る。なお、更新部26は、第1近傍特徴及び第2近傍特徴を変更又は選択する処理を、選択部11と同様な方法で、並列して実行することができる。
【0088】
更新部26は、特徴量及び追加特徴量の数に応じて、第1近傍特徴の数kと第2近傍特徴の数uを変更することができる。例えばk+uがNの1%で近似できたとき、k+uがN+Mの1%で近似できるように、kとuを夫々増やしても良い。
【0089】
更新部26は、選択した第1近傍特徴と第2近傍特徴の情報を決定部22に出力する。
【0090】
次いで、作成部22は、特徴量及び追加特徴量毎に周辺密度を推定し(図14のステップS205)、第1近傍特徴及び第2近傍特徴の中から、特徴量または追加特徴量毎に同じクラスに分類する特徴量または追加特徴量を決定する(図14のステップS206)。決定部22は決定した結果を参照できるテーブルを作成し(図14のステップS207)、分類部13に出力する。
【0091】
次いで、分類部13は、決定部12で作成されたテーブルを参照し、特徴量及び追加特徴量毎にクラスIDを付与する(図14のステップS208)。分類部13は、各特徴量のクラスID及び各追加特徴量のクラスIDを管理部14に出力する。
【0092】
次いで、管理部14は、閾値ths又は閾値thcを変更する必要があるかをチェックする(図14のステップS209)。閾値ths又は閾値thcの変更が必要な場合には(図14のステップS209のYes)、閾値thsの変更が必要であるかをチェックする(図14のステップS210)。閾値thsの変更が必要な場合には(図14のステップS210のYes)、閾値ths及び閾値thcの値を決定部22に出力し、ステップS205に戻る。閾値thsの変更が必要ない場合は(図14のステップS210のNo)、閾値thcの値を決定部22に出力し、ステップS206に戻る。閾値ths及び閾値thcの変更が必要ない場合には(図14のステップS209のNo)、処理を終了する。
【0093】
なお、決定部22、分類部13及び管理部14は、選択部21から入力された第1近傍特徴及び第2近傍特徴の情報を用いて、図3のステップS105乃至ステップS110の処理を実行し、取得部10が取得した特徴量にクラスIDを付与することもできる。
【0094】
以上のように、本実施例によれば、識別対象を追加する際、追加する以前に処理した結果を利用した、効率的、かつ、高速なクラスタリング処理が可能となる。
【実施例3】
【0095】
次に、第3の実施例に係る信号分類装置100について説明する。なお、第1の実施例と同等の構成については、同一の符号を付与し、その説明を省略する。
【0096】
図17は、第3の実施例の信号分類装置100cの機能構成を示したブロック図である。図17に示したように、本実施例の信号分類装置100は、取得部10、選択部11、決定部12、分類部13、管理部34及び表示部37から構成される。
【0097】
なお、図17において、管理部34及び表示部37は、取得部10、選択部11、作成部12及び分類部13と同様、CPU101とROM104に予め記録された所定のプログラムとの協働により実現される機能部である。
【0098】
管理部34は、分類部13から取得したクラスIDの付与結果を表示部37に出力する。
【0099】
表示部37は、管理部34から取得したクラスIDの付与結果に基づき、表示部103を介し、画像や文字を用いて識別対象の分類結果を表示する。
【0100】
次に、本実施例の信号分類装置100の動作を説明する。図18は、本実施例の信号分類装置100によるクラスタリング処理の流れを示したフローチャートである。以下、図18を参照して、本実施例の信号分類装置について説明する。
【0101】
まず、入力部106等を介して識別対象が入力されると(図18のステップS101)、取得部10は、入力された識別対象から特性を表す特徴量を取得する(図18のステップS102)。取得部10は、取得した特徴量を選択部11に出力する。
【0102】
次いで、選択部11は、各特徴量に対して、第1近傍特徴を選択する第1近傍特徴選択処理を実行する(図18のステップS103)。また、選択部11は、各特徴量に対して、第2近傍特徴を選択する第2近傍特徴選択処理を実行する(図18のステップS104)。選択部11は、選択した第1近傍特徴及び第2近傍特徴の情報を決定部12に出力する。
【0103】
次いで、決定部12は、特徴量毎に周辺密度を推定し(図18のステップS105)、第1近傍特徴及び第2近傍特徴の中から、特徴量毎に同じクラスに分類する特徴量を決定する(図18のステップS106)。決定部12は決定した結果を参照できるテーブルを作成し(図18のステップS107)、分類部13に出力する。
【0104】
次いで、分類部13は、決定部12で作成されたテーブルを参照し、特徴量毎にクラスIDを付与する(図18のステップS108)。分類部13は、各特徴量のクラスIDを管理部34に出力する。
【0105】
次いで、管理部34は、各特徴量のクラスIDを表示部37に出力する。
【0106】
次いで、表示部37は、識別対象の分類結果を表示する(図18のステップS301)。
【0107】
識別対象が顔画像を表す電気信号である場合、表示部37は、例えば図19のように、人物毎に分類し、整理した顔画像一覧を表示できる。また、特定の顔を選択して、同一人物の顔画像一覧を表示し、人物の検索を容易にすることもできる(図20)。このように、表示部37では、識別対象によって一意に定められることなく、各特徴量のクラスIDによる分類結果との組み合わせで複数のバリエーションを持って動作することが可能である。
【0108】
また、識別対象が音声のように画像とは異なる信号の場合には、以下のようになる。例えば、識別する対象となる信号が会議音声である場合、複数の区間に分割してクラスタリング処理(信号分類の処理)を行う。分類結果は、登場話者毎の発言のタイムラインを表示すると共に表示され、特定の再生位置あるいは、特定発言の視聴を容易に行うことができる(図21)。また、識別対象が楽曲信号である場合に、複数の区間に分割してクラスタリング処理を行えば、特定の旋律や曲の最も印象的な部分(サビ)など、特定のパートの聴取を容易に行うことができる(図22)。また、複数の楽曲を識別対象とする場合には、類似楽曲毎に分類し、整理した楽曲一覧を表示することも可能である(図23)。
【0109】
図18の戻り、本実施形態における管理部34について説明する。管理部34は、閾値ths又は閾値thcを変更する必要があるかをチェックする(図18のステップS109)。閾値ths又は閾値thcの変更が必要な場合には(図18のステップS109のYes)、閾値thsの変更が必要であるかをチェックする(図18のステップS110)。閾値thsの変更が必要な場合には(図18のステップS110のYes)、閾値ths及び閾値thcの値を決定部12に出力し、ステップS105に戻る。閾値thsの変更が必要ない場合は(図18のステップS110のNo)、閾値thcの値を決定部12に出力し、ステップS106に戻る。閾値ths及び閾値thcの変更が必要ない場合には(図18のステップS109のNo)、処理を終了する。
【0110】
以上のように、本実施例によれば、識別対象を複数のクラスに分類した後、分類結果を様々な形式で表示することで、視聴や検索、データ整理を容易に行うことができる。
【実施例4】
【0111】
第4の実施例に係る信号分類装置について説明する。なお、第1の実施例と同等の構成については、同一の符号を付与し、その説明を省略する。
【0112】
図24は、第4の実施例に係る信号分類装置100dの機能構成を示したブロック図である。図24に示したように、本実施例の信号分類装置100は、取得部10、選択部11、決定部42、分類部13及び管理部14から構成され、決定部は更に判定部46を有する。なお、図24において、選択部11、決定部42は、取得部10、分類部13及び管理部14と同様、CPU101とROM104に予め記録された所定のプログラムとの協働により実現される機能部である。
【0113】
判定部46は、取得部10で取得した各特徴量に対して、選択部11が選択したk個の第1近傍特徴及びu個の第2近傍特徴の変更を制御する。判定部46は、特徴量毎に更新した第1近傍特徴及び第2近傍特徴と、追加特徴量毎に選択した第1近傍特徴及び第2近傍特徴を決定部22に出力する。
【0114】
決定部42は、判定部46が更新すると判定した特徴量毎の第1近傍特徴及び第2近傍特徴に関する情報を用いて、前記各特徴量及び前記各追加特徴量に対して周辺密度を推定する。決定部42での周辺密度の推定は、第1の実施例における決定部12と同様の方法である。
【0115】
次に、本実施例の信号分類装置100の動作を説明する。図25は、本実施例の信号分類装置100によるクラスタリング処理の流れを示したフローチャートである。以下、図25を参照して、本実施例の信号分類装置について説明する。
【0116】
まず、入力部106等を介して識別対象が入力されると(図25のステップS101)、取得部10は、入力された識別対象から特性を表す特徴量を取得する(図25のステップS102)。取得部10は、取得した特徴量を選択部11に出力する。
【0117】
次いで、選択部11は、各特徴量に対して、第1近傍特徴を選択する第1近傍特徴選択処理を実行する(図25のステップS103)。また、選択部11は、各特徴量に対して、第2近傍特徴を選択する第2近傍特徴選択処理を実行する(図25のステップS104)。選択部11は、選択した第1近傍特徴及び第2近傍特徴の情報を決定部42に出力する。
【0118】
決定部42は、特徴量の類似性を比較するための閾値thsを参照し、選択部11で選択された第1の近傍特徴と第2の近傍特徴の情報を用いて、前記各特徴に対して周辺密度を決定する(図25のステップS105)。
【0119】
次いで、決定部42は、第1近傍特徴及び第2近傍特徴の中から、特徴量毎に同じクラスに分類する特徴量を決定する(図25のステップS106)。以下では、同じ特徴量に分類する特徴量の候補のことを修正候補と記載する。
【0120】
ここで、決定部42が特徴量xiと同じクラスに分類する特徴量xjは、各々の特徴量毎の参照関係に関する情報を用いて決定する。より具体的には、特徴量xiと特徴量xjとはそれぞれが互いの近傍特徴に含まれている、または、特徴量xiと特徴量xjとは共通の近傍特徴を持っているという条件を満たすか否かを判定部46が判定し、条件を満たす場合に、同じクラスに分類する特徴量の候補とする。条件を満たさない場合は互いの修正候補としない(図25のステップS406)。
【0121】
たとえば、図12で用いた1次元の特徴量x0からx9の場合、参照関係の条件を満たさないのは、は表5における太枠部分、x6及びx7の類似度S(8,j)及びS(9,j)である。したがって、x8及びx9にとって、x6及びx7は修正候補とはならない。
【表5】
【0122】
決定部42は決定された特徴量毎に参照できるテーブルを作成し(図25のステップS107)、分類部13に出力する。
【0123】
次いで、分類部13は、決定部42で作成されたテーブルを参照し、特徴量及び追加特徴量毎にクラスIDを付与する(図25のステップS108)。分類部13は、各特徴量のクラスID及び各追加特徴量のクラスIDを管理部14に出力する。
【0124】
次いで、管理部14は、閾値ths又は閾値thcを変更する必要があるかをチェックする(図25ステップS109)。閾値ths又は閾値thcの変更が必要な場合には(図25のステップS109のYes)、閾値thsの変更が必要であるかをチェックする(図25のステップS110)。閾値thsの変更が必要な場合には(図25のステップS110のYes)、閾値ths及び閾値thcの値を決定部42に出力し、ステップS105に戻る。閾値thsの変更が必要ない場合は(図25のステップS110のNo)、閾値thcの値を決定部42に出力し、ステップS106に戻る。閾値ths及び閾値thcの変更が必要ない場合には(図25のステップS109のNo)、処理を終了する。
【0125】
実験4により得た分類結果は、表6のようになる。これは、実験2により得た分類結果(表3)と同じ結果であるが、実験4では閾値thcを0.1のように低く設定しても分類結果は変化しない。一方、実験2では、閾値thcを0.14以下に設定すると、x8の周辺密度よりx7の周辺密度の方が高いために、y(x8)=x7となる。よって、x4からx9のクラスIDは2となり望ましくない分類結果となる(過結合)。
【0126】
以上のように本発明によれば、特徴量の互いの参照関係を考慮することにより、効率を維持したまま、閾値に対する頑健性が増し、クラス分類の精度がより向上する。
【表6】
【0127】
[変更例]
判定部は識別対象のもつ個別情報によって修正候補の判定を行ってもよい。
【0128】
たとえば、複数人の人物の顔を分類するクラスタリング処理を行う場合、識別対象として入力された同一の写真に写る各個人の顔を同じ分類としないように制御してもよい(図26(a)参照)。より具体的には特徴量xi と特徴量xjとが属する写真が同一の場合について説明する。
【0129】
まず、入力信号として、複数の識別対象が入力される際に、同一の写真から得られた識別対象であることを示す写真IDを識別対象に付与する。xiが属する写真IDが、 PI(xi)であるとき、類似した特徴量xiおよび特徴量xjについて、PI(xi)=PI(xj)が成り立つとき、収束するy(xi)は式2によって拘束される。
【0130】
更に、写真IDの異なる特徴量z(xi)についても、y(xi)=z(xi)であるとき、はxiに対して式3を適用する。
【数2】
【数3】
【0131】
これらにより、ひとつのクラスに分類される特徴群(図26(b))を複数のクラスに適切に分離することが可能になり、メモリ容量を要さずにより精度の高い分類が可能となる。
【0132】
なお、写真IDを取らずに、入力手段等を介して同じグループとなる分類か否かの情報をユーザ等が入力してもよい。この場合、ユーザ等が決めた更新情報を更新情報取得部によって取得し、判定部が識別対象が同じ分類とならないように制御する。また、ユーザが別分類としたい識別対象について入力したものに対して異なるIDを付与し、IDが異なるときに式2等を拘束条件として、修正候補の判定をおこなってもよい。
【0133】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、多くの発明を形成できる。例えば、実施形態に示される全構成要素からいくつかの構成要素を削除しても良い。さらに、異なる実施形態にわたる構成要素を適宜組み合わせても良い。
【符号の説明】
【0134】
101・・・制御部、102・・・操作部、103・・・表示部、104、105・・・記憶部、106・・・入力部、107・・・外部記憶装置、108・・・バス
10・・・取得部、11、22・・・選択部、12・・・決定部、13・・・分類部、34、14・・・管理部、25・・・追加取得部、26・・・更新部、37・・・表示部、46・・・判定部
【技術分野】
【0001】
本発明は、信号分類装置に関する。
【背景技術】
【0002】
クラスタリング技術(信号分類技術)は、識別対象となるサンプル(標本)集合を、類似特徴を持つサンプルで構成される部分集合(クラス)に分類することを目的とする。このクラスタリング技術は、例えば、文字や図形、音声などを対象とした識別処理に適用できる。識別対象が顔画像であるとき、誤りなく識別できれば、一つのクラスは同一人物の顔写真だけで構成され、各クラスは夫々異なる人物の顔写真で構成される。また、識別対象が夫々1人が発話した音声データであるとき、誤りなく識別できれば、一つのクラスは同一話者の音声データで構成され、各クラスは夫々異なる話者の音声データで構成される。この識別処理を高い精度で実現するには、取得する特徴も重要であるが、クラスタリングの精度も重要である。
【0003】
従来方式である非特許文献1乃至3では、特徴空間内にて、同一クラスに属するサンプルは密集して分布することを前提としたクラスタリングを行う。具体的には、各サンプルの特徴を、近傍で潜在的に存在するクラスの分布の中心に更新し、同一クラスに属するサンプルを一箇所に集めることで、クラスタリングを実現する。非特許文献1では、各サンプルは、特徴間の類似度が閾値以上であるサンプル(近傍サンプル)との平均特徴に最も類似したサンプルに更新する。ここで、平均特徴の導出は、特徴空間の次元数が高次元に及ぶほど、演算量が増加する。
【0004】
そこで、非特許文献2及び非特許文献3では、潜在的に存在するクラスの、分布の中心への近さは、各サンプル周辺の密度の高さが表すとしている。周辺密度は例えば近傍サンプルの数で近似する。各サンプルは、周辺密度が高く類似度が閾値以上で、かつ、最も高い類似度を持つサンプルに更新する。特徴の更新には、周辺密度を用いるため、平均特徴を求める非特許文献1よりも演算量を削減できる。
【0005】
非特許文献2及び非特許文献3では、各サンプルに対し、周辺密度を計算する処理と、同じクラスに分類するサンプルを決定する処理とを行うには、サンプル間の類似度情報が必要となる。周辺密度を計算する処理と同じクラスに分類するサンプルを決定する処理とは同時に実行できない。そのため演算の重複を避け、効率的に処理を実行するためには、全ての組み合わせにおけるサンプル間の類似度情報をメモリ(バッファ)に記憶する必要がある。したがって、サンプルの2乗のオーダーとなる大量のメモリが必要である。
【0006】
また、周辺密度を計算する過程で、各サンプルに対して、類似度が閾値以上である近傍サンプルのサンプルIDと類似度を記憶することでも効率化できる。しかし、近傍サンプルの数は事前に予測できない上、閾値が最低値であれば、全てのサンプルが近傍サンプルとなるため、サンプルIDと類似度とを記憶する代替案を用いても、サンプルの2乗のオーダーとなるメモリを確保する必要がある。
【先行技術文献】
【非特許文献】
【0007】
【非特許文献1】“Mode−seeking by Medoidshifts”,Y.A.Sheikh, E.A.Khan and T.Kanade, IEEE International Conference on Computer Vision, 2007.
【非特許文献2】“A Graph−theoretic approach to nonparametric cluter analysis”, W.L.G.Koontz, P.Narendra, and K.Fukunaga, IEEE Trans. on Computer, c−25(9), 1976.
【非特許文献3】“Quick Shift and Kernel Methods for Mode Seeking”, A.Vedaldi and S.Soatto, ECCV2008, PartIV, LNCS5305, pp.705−718, 2008.
【発明の概要】
【発明が解決しようとする課題】
【0008】
本発明は上記問題を鑑み、多量のメモリを用いずに分類可能な信号分類装置を提供することを目的とする。
【課題を解決するための手段】
【0009】
上記目的を達成するために本発明の信号分類装置は、入力された信号に含まれるN個の識別対象の特徴量を取得する取得部と、前記特徴量毎に、前記特徴量からk個(1≦k≦N)の前記特徴量を第1近傍特徴として選択する第1の選択部と、互いに類似する前記特徴量から特徴群を生成し、取得したN個の前記特徴量から異なる前記特徴群に属するu個(1≦k+u≦N−2)の前記特徴量を第2の近傍特徴として選択する第2の選択部と、 前記特徴量の類似性を比較するための閾値と、前記特徴量毎に算出した周辺密度とを用いて、同じ分類となる前記特徴量を決定する決定部と、前記特徴量の決定結果から分類を行う分類部と、前記閾値を管理する管理部と、を備えたことを特徴とする。
【発明の効果】
【0010】
本発明によれば、多量のメモリを用いずに分類可能な信号分類装置を提供できる。
【図面の簡単な説明】
【0011】
【図1】本発明の実施例に係るハードウェア構成を示す図。
【図2】実施例1の機能構成を表わすブロック図。
【図3】実施例1のクラスタリング処理を表わすフローチャート。
【図4】クラスタリング処理の動作例を示す図。
【図5】クラスタリング処理の動作例を示す図。
【図6】クラスタリング処理の動作例を示す図。
【図7】第1近傍特徴選択処理を表わすフローチャート。
【図8】第1近傍特徴集合への特徴追加処理を表わすフローチャート。
【図9】第2近傍特徴選択処理を表わすフローチャート。
【図10】第2近傍特徴集合への特徴追加処理を表わすフローチャート。
【図11】比較実験1と実施例1のクラスタリング処理精度を示す図。
【図12】1次元の特徴量の標本を模式的に示す図。
【図13】実施例2の機能構成を表わすブロック図。
【図14】実施例2のクラスタリング処理を表わすフローチャート。
【図15】第1近傍特徴変更選択処理を表わすフローチャート。
【図16】第2近傍特徴変更選択処理を表わすフローチャート。
【図17】実施例3の機能構成を表わすブロック図。
【図18】実施例3のクラスタリング処理を表わすフローチャート。
【図19】実施例3に係る画像のクラスタリング処理結果の表示例。
【図20】実施例3に係る画像のクラスタリング処理結果の表示例。
【図21】実施例3に係る音声のクラスタリング処理結果の表示例。
【図22】実施例3に係る音楽のクラスタリング処理結果の表示例。
【図23】実施例3に係る音楽のクラスタリング処理結果の表示例。
【図24】実施例4の機能構成を表わすブロック図。
【図25】実施例4のクラスタリング処理を表わすフローチャート。
【図26】同一画像の人物に対するクラスタリング処理を表わす模式図。
【発明を実施するための形態】
【0012】
以下、本実施形態に関する信号処理装置について図面に基づいて説明する。
【0013】
本発明の実施例に関する信号処理装置は、画像中の被写体(たとえば人物)の分類または音響(例えば音楽や人の声)の分類をすることが可能であり、分類結果は、画像中の被写体毎の写真の分類や人物毎の発言の分類に用いることが可能である。したがって、写真や動画などを分類して提示する動画再生装置や静止画を用いたスライドショーなどにも適用可能である。
【実施例1】
【0014】
まず、本実施の形態にかかる信号分類装置のハードウェア構成について図1を用いて説明する。信号分類装置100は、装置全体を制御するCPU(Central Processing Unit)等の制御部101と、各種データや各種プログラムを記憶するROM(Read Only Memory)104やRAM105(Random Access Memory)等の記憶部と、各種データや各種プログラムを記憶するHDD(Hard Disk Drive)やCD(Compact Disk)ドライブ装置等の外部記憶部107と、これらを接続するバス108とを備えており、通常のコンピュータを利用したハードウェア構成となっている。また、信号分類装置100には、画像を表示する表示部103と、ユーザの指示入力を受け付けるキーボードやマウス等の操作部102と、文字、画像、音声党の識別対象を電子信号に変換する入力部106と、外部装置の通信を制御する通信部やI/F(インターフェース)とが有線又は無線により各々接続される。
【0015】
CPU101は、RAM105の所定領域を作業領域として、ROM104に予め記憶された各種制御プログラムとの協働により各種処理を実行し、信号分類装置100を構成する各部の動作を統括的に制御する。また、CPU101は、ROM104に予め記憶された所定のプログラムとの協働により、後述する取得部10、選択部11、作成部12、クラスタリング部13、管理部14の各機能部を実現させる。 操作部102は、各種入力キー等を備え、ユーザから操作入力された情報を入力信号として受け付け、その入力信号をCPU101に出力する。
【0016】
表示部103は、液晶表示装置(LCD:Liquid Crystal Display)等の表示手段により構成され、CPU101からの表示信号に基づいて、各種情報を表示する。なお、表示部103は、操作部102と一体的にタッチパネルを構成する様態としてもよい。
【0017】
ROM104は、信号分類装置100の制御にかかるプログラムや各種設定情報等を書き換え不可能に記憶する。RAM105は、SDRAM等の記憶手段であって、CPU101の作業エリアとして機能し、バッファ等の役割を果たす。
【0018】
入力部106は、音声や文字、図形等の識別対象を電気信号に変換し、PCM(Pulse Code Modulation)等の数値データとしてCPU101に出力する。
【0019】
記憶部107は、磁気的又は光学的に記憶可能な記憶媒体を有し、入力部106を介して取得された信号や、図示しない通信部やI/F(インターフェース)等を介して外部から入力される信号等のデータを記憶する。また、記憶部107は、後述するクラスタリング装置により識別対象の分類結果情報を記憶する。
【0020】
図2は、第1の実施例の信号分類装置100aの機能構成を示したブロック図である。なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、多くの発明を形成できる。例えば、実施形態に示される全構成要素からいくつかの構成要素を削除しても良い。さらに、異なる実施形態にわたる構成要素を適宜組み合わせても良い。
【0021】
本実施例の信号分類装置100aは、取得部10、第1の選択部及び第2の選択部からなる選択部11、決定部12、分類部13及び管理部14等を備えている。
【0022】
取得部10は、入力部106等を介して入力された信号に含まれる識別対象の特徴量を取得する。特徴量とは識別対象となる信号、例えば画像中の人物はたは顔、音の中の声などを個別に認識するための特性を示すものである。識別対象が顔の画像で、人物毎に分類する場合には、特徴量を、画素値を表すベクトルを変換して求める。このとき用いる変換は、例えば、ヒストグラム平坦化などを用いる。識別対象が音声で、話者毎に分類する場合には、例えばLPCケプストラムやMFCC等のケプストラム系特徴量を取得すれば良い。また、Y.Akitaによる“Unsupervised Speaker Indexing using Anchor Models and Automatic Transcription of Discussions”, ISCA 8th European Conference on Speech Communication and Technology(Euro Speech), September 2003に記載された手法を用いてケプストラム系特徴量を加工しても良い。さらに、識別対象の音声は、予め検出した無音毎に分割する、一定時間毎に分割する等の方法により、その個数を増やしても良い。識別対象が音全般で、音楽、音声、雑音といった音の種別を分類する場合には、E.Scheirerらによる“Construction and Evaluation of a Robust Multifeature Speech/Music Discriminator”,IEEE International Conference on Acoustic Speech, and Signal Processing, April 1997に記載された手法を用いても良い。取得部10が取得した特徴量は選択部11に出力される。
【0023】
選択部11は、取得部10が取得したN個の特徴量夫々に対して、取得した特徴量の中から、特徴が類似したk個(1≦k≦N)の第1近傍特徴を選択する第1の選択部と、互いに類似する特徴量から特許群を生成し、異なる特徴群に属するu個の第2近傍特徴を選択する第2の選択部とからなる。特徴群は、取得部10が取得した特徴量の中から、類似した特徴同士を群として纏めたものである。特徴群の生成は、特徴量間の類似度を計算する過程で逐次的に実行できる簡易的な処理であれば良い。選択部11は、取得したN個の特徴量を用いて、複数の特徴群を生成する。選択部11は、選択した第1近傍特徴及び第2近傍特徴を決定部12に出力する。
【0024】
決定部12は、特徴量の類似性を比較するための閾値を参照し、選択部11で選択された第1近傍特徴と第2近傍特徴を用いて、各特徴量に対して周辺密度を算出する。次に、特徴量毎に、第1近傍特徴と第2近傍特徴の中から同じクラス(集合)に分類する特徴量を決定する。特徴量毎に関係する特徴量が参照できるテーブルを作成し、分類部13に出力する。特徴量は表形式で出力するのが好ましいが、特徴量毎に第1近傍特徴と第2近傍特徴から決定された特徴量がわかるような形式ならばこれに限らない。
【0025】
分類部13は、決定部12にて作成されたテーブルを参照し、各特徴量に対して、クラスIDを付与する。クラスIDは同じ集合となるものに付与する。クラスIDの付与結果は管理部14に出力する。
【0026】
管理部14は、決定部12で用いた閾値を管理する。更に閾値を異なる値に変更した場合には、決定部12に変更した閾値を出力する。決定部12は管理部14が変更した閾値を取得した後、再度テーブルを作成する。
【0027】
次に、本実施例の信号分類装置100の動作を説明する。図3は、本実施例の信号分類装置100によるクラスタリング処理の流れを示したフローチャート、図4乃至図6である。以下、図3乃至図6に示した動作例O1乃至O8を参照して、本実施例の信号分類装置について説明する。
まず、入力部106を介して識別対象となる信号が入力される(図3のステップS101)。取得部10は、入力された識別対象から特徴量を取得する(図3のステップS102、図4の動作例O1参照)。取得部10は、取得した特徴量を選択部11に出力する。
【0028】
次いで選択部11は、各特徴量に対して第1近傍特徴を選択する、第1近傍特徴選択処理を実行する(図3のステップS103)。特徴量xiの第1の近傍特徴は、特徴量xiと類似度の高い上位k個の特徴量とする(図4の動作例O2及び図5の動作例O3参照)。
【0029】
ここで、第1近傍特徴選択処理(ステップS103)の詳細な動作を、図7を参照して説明する。なお、取得部10にて取得した特徴量はxi(i=0,1,...,N−1)で表す。
【0030】
まず、第1の選択部は、特徴量の番号を参照できる変数i=1を設定し、2番目の特徴を参照できる状態にする(ステップS11)。同様に、変数j=0を設定し、1番目の特徴を参照できる状態にする(ステップS12)。
【0031】
次いで選択部11は、特徴量xiと特徴量xjの類似度S(i,j)を計算する(ステップS13)。類似度は、特徴量をベクトルとして表現したものである。類似度は特徴量間のユークリッド距離の逆数、最大値からユークリッド距離を引いた値としても良い。また、特徴量同士の内積がなす角の余弦としても良い。
【0032】
次いで第1の選択部は、特徴量xiの第1近傍特徴の集合RFiに特徴量xjを追加するか否かを判定し追加処理を実行する、集合RFiと特徴量xjを対象とした第1の近傍特徴の集合への特徴追加処理を行う(ステップS14)。第1近傍特徴の集合への特徴追加処理の詳細な動作は図8を参照して説明する。
【0033】
第1の選択部は、処理対象となる特徴量xaとして特徴量xiを、第1近傍特徴の集合RFaとして集合RFiを設定する(ステップS21)。次に、集合RFaに追加するか否かを判定し追加処理を実行したい特徴量xbとして、特徴量xjを設定する(ステップS22)。
【0034】
次いで、特徴量xaの第1近傍特徴の集合RFaにk個の特徴量が含まれているか否かを確認する(ステップS23)。k個の特徴量が含まれている場合には(ステップS23のYes)、そのままステップS25に進む。ここで、k個の特徴量が含まれていない場合は(ステップS23のNo)、集合RFaに特徴量xbを加えた後(ステップS24)、処理を終了する。
【0035】
第1の選択部は、集合RFaの中で特徴量xaとの類似度が最も低い特徴量xcを取得する(ステップS25)。次に、特徴量xaと特徴量xbの類似度S(a,b)と、特徴量xaと特徴量xcの類似度S(a,c)を比較する(ステップS26)。S(a,b)がS(a,c)より大きい場合には(ステップS26のYes)、特徴量xcの替わりに、特徴量xbを集合RFaに追加した後(ステップS27)、処理を終了する。S(a,b)がS(a,c)以下である場合には(ステップS26のNo)、そのまま処理を終了する。
【0036】
次いで特徴量xjの第1近傍特徴の集合RFjに特徴量xiを追加するか否かを判定し追加処理を実行する、集合RFjと特徴量xiを対象とした第1近傍特徴の集合への特徴追加処理を行う。この特徴追加処理は、ステップS21とステップS22を除き、ステップS14で行う処理と同様に実行できる。ステップS21では、特徴量xaとして特徴量xj、集合RFaとして集合RFjを設定する。また、ステップS22では、特徴量xbとして、特徴量xiを設定する。
【0037】
図7の、第一近傍特徴選択処理の詳細な動作についての説明に戻る。第1の選択部は、特徴量xiとの類似度を求める特徴量として、次の特徴量を参照するため、j=j+1を設定する(ステップS16)。次に、新たに設定した特徴量xjが特徴量xiと同一のものであるかを判定する(ステップS17)。特徴量xjと特徴量xiが同一のものである場合(ステップS17のYes)、ステップS18に進む。特徴量xjと特徴量xiが異なるものである場合(ステップS17のNo)、類似度計算を行うためステップS13に戻る。
【0038】
第1の選択部は、次の特徴量を参照するため、i=i+1を設定した後(ステップS18)、取得した全ての特徴量に対してステップS12乃至ステップS18の処理を実行したか否かを判定する(ステップS19)。全ての特徴量に対して処理を完了している場合には(ステップS19のYes)、処理を完了する。全ての特徴量に対して処理を完了していない場合は(ステップS19のNo)、ステップS12に戻る。
【0039】
図3に戻って、第1近傍特徴選択処理に続く第2近傍特の選択について説明する。選択部11は、各特徴量に対して第2近傍特徴を選択する、第2近傍特徴選択処理を実行する(図3のステップS104)。特徴量xの第2近傍特徴は、類似度の高い上位u個の特徴量とするが、u個の特徴量はお互いに異なる特徴群に属するとする(図4の動作例O2及び図5の動作例O3参照)。特許群とは、互いに類似する複数個の特徴量からなる集合である。ここで、第2近傍特徴選択処理の詳細な動作を、図9を参照して説明する。
【0040】
まず、第2の選択部は、1番目の特徴量x0を要素に持つ特徴群を新規作成する(ステップS31)。次に、特徴量の番号を参照できる変数i=1を設定し、2番目の特徴量を参照できる状態にする(ステップS32)。同様に、変数j=0、jj=0を設定し、1番目の特徴量を参照できる状態にする(ステップS33)。
【0041】
次いで、第2の選択部は、ステップS11と同様の方法にて、特徴量xiと特徴量xjの類似度S(i,j)を計算する(ステップS34)。次に、第2の選択部は、類似度S(i,j)が閾値thm以上となり、特徴量xiと特徴量xjが同じ特徴群に分類され得るか否かを判定する(ステップS35)。閾値thmを十分信頼できる値とするため、例えば、類似度の最大が1であるときはthm=0.9と設定する。類似度S(i,j)が閾値thm以上である場合には(ステップS35のYes)、特徴量xiを特徴量xjと同じ特徴群に分類した後(ステップS36)、ステップS37に進む。類似度S(i,j)が閾値thm未満である場合には(ステップS35のNo)、そのままステップS37に進む。
【0042】
次いで、第2の選択部は、特徴量xiの第2近傍特徴の集合RSiに特徴量xjを追加するか否かを判定し追加処理を実行する、集合RSiと特徴量xjを対象とした第2近傍特徴の集合への特徴追加処理を行う。ここで、第2の近傍特徴の集合への特徴追加処理の詳細な動作を、図10を参照して説明する。
【0043】
まず、第2の選択部は、処理対象となる特徴量xaとして特徴量xiを、第2近傍特徴の集合RSaとして集合RSiを設定する(ステップS51)。次に、集合RSaに追加するか否かを判定し追加処理を実行したい特徴量xbとして、特徴量xjを設定する(ステップS52)。
【0044】
次いで、第2の選択部は、集合RSaの中で、特徴量xbと同じ特徴群に属する特徴量があるか否かを判定する(ステップS53)。集合RSaの中で、特徴量xbと同じ特徴群に属する特徴量xdが存在した場合(ステップS53のYes)、ステップS54に進む。ステップS54では、特徴量xaと特徴量xbの類似度S(a,b)と、特徴量xaと特徴量xdの類似度S(a,d)を比較する。S(a,b)がS(a,d)より大きい場合には(ステップS54のYes)、特徴量xdの替わりに、特徴量xbを集合RSaに追加した後(ステップS55)、処理を終了する。S(a,b)がS(a,d)以下である場合には(ステップS54のNo)、そのまま処理を終了する。集合RSaの中で、特徴量xbと同じ特徴群に属する特徴がない場合には(ステップS53のNo)、ステップ56に進む。
【0045】
次いで、第2の選択部は、特徴量xaの第2近傍特徴の集合RSaにu個の特徴量が含まれているか否かを確認する(ステップS56)。u個の特徴量が含まれている場合には(ステップS56のYes)、そのままステップS58に進む。ここで、u個の特徴量が含まれていない場合は(ステップS56のNo)、集合RSaに特徴量xbを加えた後(ステップS57)、処理を終了する。
【0046】
次いで、第2の選択部は、集合RSaの中で、特徴量xaとの類似度が最も低い特徴量xcを取得する(ステップS58)。次に、特徴量xaと特徴量xbの類似度S(a,b)と、特徴量xaと特徴量xcの類似度S(a,c)を比較する(ステップS59)。S(a,b)がS(a,c)より大きい場合には(ステップS59のYes)、特徴量xcの替わりに、特徴量xbを集合RSaに追加した後(ステップS60)、処理を終了する。S(a,b)がS(a,c)以下である場合には(ステップS59のNo)、そのまま処理を終了する。
【0047】
図9に戻り、第2近傍特徴選択処理の詳細な動作について説明する。次いで、第2の選択部は、特徴量xiとの類似度を求める特徴量として、次の特徴量を参照するため、j=j+1を設定する(ステップS38)。次に、新たに設定した特徴量xjが特徴量xiと同一のものであるかを判定する(ステップS39)。特徴量xjと特徴量xiが同一のものである場合(ステップS39のYes)、ステップS40に進む。特徴量xjと特徴量xiが異なるものである場合(ステップS39のNo)、類似度計算を行うためステップS33に戻る。
【0048】
次いで、第2の選択部は、特徴量xiが既存の特徴群に分類されたか否かを判定する(ステップS40)。特徴量xiが既存の特徴群に分類されている場合には(ステップS40のYes)、そのままステップS42に進む。特徴量xiが既存の特徴群に分類されていない場合には(ステップS40のNo)、特徴量xiを要素に持つ特徴群を新規作成した後(ステップS41)、ステップS42に進む。
【0049】
次いで、選択部11は、特徴量xjjの第2近傍特徴の集合RSjjに特徴量xiを追加するか否かを判定し追加処理を実行する、集合RFjjと特徴量xiを対象とした第2近傍特徴の集合への特徴追加処理を行う。この特徴追加処理は、ステップS51とステップS52を除き、ステップS37で行う処理と同様に実行できる。ステップS51では、特徴量xaとして特徴量xjj、集合RSaとして集合RSjjを設定する。また、ステップS52では、特徴量xbとして、特徴量xiを設定する。
【0050】
次いで、第2の選択部は、特徴量xiが属する可能性のある次の第2近傍特徴の集合を参照するため、jj=jj+1を設定する(ステップS43)。次に、新たに設定した特徴量xjjが特徴量xiと同一のものであるかを判定する(ステップS44)。特徴量xjjと特徴量xiが同一のものである場合(ステップS44のYes)、ステップS45に進む。特徴量xjjと特徴量xiが異なるものである場合(ステップS44のNo)、第2近傍特徴の集合への特徴追加処理を行うためステップS42に戻る。
【0051】
次いで、第2の選択部は、次の特徴量を参照するため、i=i+1を設定した後(ステップS45)、取得した全ての特徴量に対してステップS33乃至ステップS45の処理を実行したか否かを判定する(ステップS46)。全ての特徴量に対して処理を完了している場合には(ステップS46のYes)、処理を完了する。全ての特徴量に対して処理を完了していない場合は(ステップS46のNo)、ステップS33に戻る。
【0052】
ここで選択部11は、第2近傍特徴選択処理にて、特徴量xiの第2近傍特徴の集合RSiには特徴量xiと同じ特徴群に属する特徴量を含まない制約を加えても良い。あるいは、特徴量xiの第2近傍特徴の集合RSiには第1近傍特徴の集合RFiの特徴量を含まない制約を加えても良い。
【0053】
選択部11は、図7に示した第1近傍特徴選択処理と、図9に示した第2近傍選択処理を並列して実行してもよい。並列実行の際は、まず、ステップS11及びステップS12と、ステップS31乃至ステップS33を順に行う。次に、類似度計算の処理(ステップS13あるいはステップS34)を行った後、ステップS14乃至ステップS17と、ステップS35乃至ステップS39を順に行う。次いで、ステップS40乃至ステップS44を行った後、処理終了に繋がる処理(ステップS18とステップS19、あるいは、ステップ45とステップ46)を行うことが望ましい。
【0054】
選択部11が選択する第1近傍特徴の数kは1以上N−2以下で設定し、第2近傍特徴の数uは、k+uがN−2以下となるように設定する。また、k及びuは、Nの値によらない固定値しても良いし、Nに比例して増やしても良い。さらには、kとuは独立して扱っても良いし、同じ値としても良い。例えば、N=200のとき、kとuをNの1%と設定し、k=2、u=2としてもよい。
【0055】
選択部11は、最後に、選択した第1近傍特徴及び第2近傍特徴の情報を決定部12に出力する。
【0056】
決定部12は、特徴量の類似性を比較するための閾値thsを参照し、選択部11で選択された第1の近傍特徴と第2の近傍特徴の情報を用いて、前記各特徴量に対して周辺密度を決定する(図3のステップS105、図5の動作例O4参照)。
【0057】
決定部12で決定される特徴量xiの周辺密度Piは、閾値thsと、非特許文献1や非特許文献2に記載されているようなガウス関数を用いて、例えば式1で算出できる。式1にて、類似度の最大値は1とし、RFiは特徴量xiの第1近傍特徴の集合、RSiは特徴量xiの第2近傍特徴の集合とする。また、式1にて、αは、第2近傍特徴に対する重みであり、例えば0.5と設定できる。
【数1】
【0058】
次いで、決定部12は、第1近傍特徴及び第2近傍特徴の中から、特徴量毎に同じクラスに分類する特徴量を決定し(図3のステップS106)、決定した結果を参照できるテーブルを作成し(図3のステップS107、図5の動作例O5)、分類部13に出力する。作成されるテーブルは特徴量毎に参照できればよく、識別対象毎にまとめられた形式のデータ構造であっても、識別対象の特性を表わす個々の特徴量毎に参照できる形式であればよい。
【0059】
決定部12にて、特徴量xiと同じクラス(分類)に分類する特徴量y(xi)は、第1近傍特徴の集合RFi及び第2近傍特徴の集合RSiの中で、周辺密度が特徴量xiよりも高く、特徴量xiとの類似度が最も大きい特徴量とする。特徴量xiの周辺密度より高い周辺密度を持つ特徴量が集合RFi及び集合RSiの中に存在しなければ、特徴量y(xi)は特徴量xiとする。また、特徴量の類似性を比較するための閾値thcを参照し、求めた特徴量y(xi)と特徴量xiの類似度が閾値thcを下回った場合には、特徴量y(xi)を特徴量xiに修正する。ここで、閾値thcは閾値thsと同じでも良いし、閾値thsから線形変換によって求めても良い。あるいは閾値thcは、閾値thsと独立して設定してもいい。なお、以下では、特徴量xiから特徴量y(xi)を求めることを特徴量xiに関数yを作用させると表現する。
【0060】
次いで、分類部13は、決定部12で作成された表形式のテーブルを参照し、特徴量毎にクラスIDを付与する(図3のステップS108、図6の動作例O6及びO7参照)。分類部13は、各特徴量のクラスIDを管理部14に出力する。
【0061】
分類部13は、各特徴量xiに対して、特徴量xiと同じクラスに分類する特徴量y(xi)が同じ特徴量を指すか否かを判定し、指せば終了、指さなければxi=y(xi)として再び関数yを作用させる。関数yを作用させる処理は、作用させた結果が変化しなくなるまで繰り返す(図6の動作例O6参照)。そして、関数yを作用させ続けて得られた結果Yが等しい特徴量同士を同じクラスに分類する(図6の動作例O7参照)。
【0062】
分類部13は、テーブルを参照してクラスIDを付与した後、第1近傍特徴及び第2近傍特徴の情報を用いて、類似した特徴量を持つクラスを一つに纏める統合処理を行っても良い。例えば、閾値thnを設定し、特徴量xiの第1近傍特徴の集合RFi及び第2近傍特徴の集合RSiの中で、閾値thn以上の類似度を持ち、異なるクラスIDが付与された特徴量xnが存在した場合(図5の動作例O3における、x0の第2近傍特徴x6参照)、特徴量xiと特徴量xnが所属するクラスを一つに纏める(図6の動作例O8参照)。閾値thnは、類似度の最大値が1であるとき、例えば、0.6に設定できる。
【0063】
管理部14は、閾値ths又は閾値thcを変更する必要があるかをチェックする(図3のステップS109)。閾値ths又は閾値thcの変更が必要な場合には(図3のステップS109のYes)、閾値thsの変更が必要であるかをチェックする(図3のステップS110)。閾値thsの変更が必要な場合には(図3のステップS110のYes)、閾値ths及び閾値thcの値を作成部12に出力し、ステップS105に戻る。閾値thsの変更が必要ない場合は(図3のステップS110のNo)、閾値thcの値を決定部12に出力し、ステップS106に戻る。閾値ths及び閾値thcの変更が必要ない場合には(図3のステップS109のNo)、処理を終了する。なお、管理部14から変更された閾値ths及び閾値thcを取得した決定部12は、閾値にあわせて再度テーブルを作成する。
【0064】
管理部14は、分類部13から取得したクラスIDの付与結果を元に閾値ths及び閾値thcの値を変更しても良い。例えば、クラス数を算出することによって変更してもよい。特徴量数Nに対して、分類されたクラス数が一定の割合以上の個数である場合、クラス数を削減するため、閾値ths及び閾値thcの値を高くする。特徴量数に対して一定の割合以下の個数であれば、クラス数を増やすため、閾値ths及び閾値thcの値を低くする。さらに一定の割合ではなく、所定のクラス数を基準にして閾値ths及び閾値thcの値を変更しても良い。
【0065】
また管理部14は、操作部102を通じてユーザから入力された値を元に閾値ths及び閾値thcの値を変更しても良い。また、閾値ths及び閾値thcの値は一度に限らず何度でも実行することができる。さらには、変更する閾値に閾値thnを加えても良い。なお、閾値thnの変更のみの場合には、ステップS108に戻れば良い。
【0066】
以上のように、本実施例によれば、全ての特徴量の組み合わせにおける類似度情報は必要なく、特徴数Nのオーダー(=k+u倍<N倍)となるメモリを用意することによって、識別対象となる信号のクラスタリング(分類)を行うことができる。
【0067】
また、特徴量間の類似性を比較するための閾値thsを変更した場合、周辺密度の推定には選択した所定個数の特徴量(標本)との類似度のみ参照する。したがって、非常に高速にクラスタリングを行うことが可能である。更に、閾値thsを対話的に変更するインタラクティブ処理が実現できる。
【0068】
ここで、全ての組み合わせにおけるサンプル間の類似度情報をメモリ(バッファ)に記憶した場合(比較実験1)に対して本実施(実験1)を組み込み、特徴量の次元数が5120の顔画像10000枚に対するクラスタリングの処理時間を測定した結果を表1に示した。比較実験1に比べ、実験1はメモリ使用量を削減し、閾値ths変更後の処理時間も短縮できていることが確認できる。
【表1】
【0069】
閾値thcが低い値を取る程、特徴量xiは異なる特徴量に更新されやすい(y(xi)≠xi)。この場合、特徴量の集合が過剰に纏まり、精度劣化に繋がる可能性がある。本実施例の場合、各特徴量は所定個数の特徴量を参照することで特徴量が過剰に纏ることなく精度劣化を低減できる。更に、第1近傍特徴だけでなく、近傍特徴同士が異なる特徴群に属しているかを考慮した第2近傍特徴を用いることで、多くの特徴量を効率的に纏めることができる。これにより閾値thcの値が高いときに精度向上に繋げることができる。図11は、比較実験1と同様の手法で、特徴量の次元数が5120の顔画像828枚(登場人物73人)に対するクラスタリング精度を測定した結果である(閾値thc=閾値ths、閾値thn=∞)。精度は再現率、適合率の調和平均F値(=2*再現率*適合率/(再現率+適合率))で表している。適合率は、各クラスが一人の人物のデータで構成されているか否かを表す尺度である。具体的には、各クラスにて、属する特徴量の中で同一人物に纏められる特徴量数をCとし、対応する同一人物の総特徴量数をRとしたとき、クラス毎に求めたC/Rの平均値を適合率とする。なお、特徴量数Cを設定する際、複数の人物の候補があるならば、最大値を持つ人物を選択する。また、再現率は、各人物が一つのクラスに分類されているか否かを表す尺度である。具体的には、各人物にて総特徴量数をRとしたとき、対応する人物を最も多く含むクラスを一つ選択し、選択したクラスに属する特徴量の中で対応する人物の特徴量数をCとしたとき、人物毎に求めたC/Rの平均値を再現率とする。なお、同じクラスを複数回選択することはできない。図11より、閾値thcが低い値のときと、閾値thcが高い値のときで本発明の効果を確認することができる。
【0070】
また、図12は1次元の特徴量x0からx9を模式的に示したものである。x0からx9を識別対象とした動作例として、比較実験1の手法を用いた結果(表2)、実験2(表3)、実験3(表4)を示した。こおで、ユークリッド距離をDとしたとき、類似度は1/(1+D)で定義し、第2近傍特徴に対する重みαは1、閾値ths及び閾値thcは共に0.27とした。実験3では、第2近傍特徴を用いるため、同じ使用メモリでもより距離の離れた特徴量を参照でき、x0からx7を一つのクラスとみなせる。
【表2】
【表3】
【表4】
【実施例2】
【0071】
次に、第2の実施例に係る信号分類装置100について説明する。なお、上述した第1の実施例と同等の構成については、同一の符号を付与し、その説明を省略する。
【0072】
図13は、第2の実施例に係る信号分類装置100bの機能構成を示したブロック図である。図13に示したように、本実施例の信号分類装置100は、取得部10、選択部21、追加取得部25、更新部26、決定部22、分類部13及び管理部14から構成される。なお、図13において、選択部21、追加取得部25、更新部26及び決定部22は、取得部10、分類部13及び管理部14と同様、CPU101とROM104に予め記録された所定のプログラムとの協働により実現される機能部である。
【0073】
選択部21は、取得部10が取得したN個の特徴量夫々に対して、取得した特徴量の中から、特徴量が類似したk個の第1近傍特徴を選択する第1の選択部と、互いに類似する特徴量から特許群を生成し、異なる特徴群に属するu個の第2近傍特徴を選択する第2の選択部とからなる。選択部11は、特徴量毎に選択した第1近傍特徴及び第2近傍特徴を決定部12に出力し、更新部26にも出力する。
【0074】
追加取得部25は、入力部106等を介して追加入力された識別対象の特性を表す特徴量を取得する。追加取得部25は、取得部10と同様の方法で特徴量を取得し、取得した特徴量を追加特徴量として更新部26に出力する。
【0075】
更新部26は、取得部10で取得した特徴量の数をN、追加取得部25で取得した追加特徴量の数をMとし、各特徴量に対して、追加特徴量の情報を参照して選択部21が選択したk個の第1近傍特徴及びu個の第2近傍特徴を変更する。更新部26は、N+M個の特徴量及び追加特徴量の中から、各追加特徴量に対し、k個の第1近傍特徴及びu個の第2近傍特徴を選択する。更新部26は、特徴量毎に更新した第1近傍特徴及び第2近傍特徴と、追加特徴量毎に選択した第1近傍特徴及び第2近傍特徴を決定部22に出力する。
【0076】
決定部22は、更新部26が更新した特徴量毎の第1近傍特徴及び第2近傍特徴に関する情報と、更新部26が選択した追加特徴量毎の第1近傍特徴及び第2近傍特徴に関する情報とを用いて、前記各特徴量及び前記各追加特徴量に対して周辺密度を推定する。決定部22での周辺密度の推定は、第1の実施例における決定部12と同様の方法である。
【0077】
決定部22は、決定部12と同様に、特徴量及び追加特徴量毎に同じクラスに分類する特徴量または追加特徴量を参照できるテーブルを作成し、分類部13に出力する。
【0078】
次に、本実施例の信号分類装置100の動作を説明する。図14は、本実施例の信号分類装置100によるクラスタリング処理の流れを示したフローチャートである。以下、図14を参照して、本実施例の信号分類装置について説明する。
【0079】
まず、入力部106等を介して識別対象が入力されると(図14のステップS101)、取得部10は、入力された識別対象から特性を表す特徴量を取得する(図14のステップS102)。取得部10は、取得した特徴量を選択部21に出力する。
【0080】
次いで、選択部21は、各特徴量に対して、第1近傍特徴を選択する第1近傍特徴選択処理を実行する(図14のステップS103)。また、選択部21は、各特徴量に対して、第2近傍特徴を選択する第2近傍特徴選択処理を実行する(図14のステップS104)。選択部21は、選択した第1近傍特徴及び第2近傍特徴の情報を決定部22及び更新部26に出力する。
【0081】
次いで、入力部106等を介して識別対象が追加入力されると(図14のステップS201)、追加取得部25は、追加入力された識別対象から特徴量を取得する(図14のステップS202)。追加取得部25は、取得した追加特徴量を更新部26に出力する。
【0082】
次いで、更新部26は、取得部10が取得した特徴量毎に第1近傍特徴を変更する処理と、追加取得部25が取得した追加特徴量毎に第1近傍特徴を選択する、第1近傍特徴変更選択処理を行う(図14のステップS203)。ここで、第1の近傍特徴変更選択処理の詳細な動作を、図14を参照して説明する。なお、取得部10にて取得した特徴量は、xi(i=0,1,...,N−1)で表し、追加取得部25にて取得した追加特徴量は、xi(i=N,N+1,...,N+M−1)で表す。
【0083】
まず、更新部26は、特徴量の番号を参照できる変数i=Nを設定し、1番目の追加特徴量を参照できる状態にする(図15のステップS71)。以下、ステップS12乃至ステップS18は、実施例1の図7のフローチャートにおけるステップS12乃至ステップS18と同様であるので説明を省略する。
【0084】
次いで、更新部26は、取得した全ての追加特徴量に対して、ステップS12乃至ステップS18の処理を実行したか否かを判定する(図15のステップS79)。全ての追加特徴量に対して処理を完了している場合には(ステップS79のYes)、処理を完了する。全ての追加特徴量に対して処理を完了していない場合は(ステップS79のNo)、ステップS12に戻る。
【0085】
続いて、更新部26は、取得部10が取得した特徴量毎に第の近傍特徴を変更する処理と、追加取得部25が取得した追加特徴量毎に第2近傍特徴を選択する、第2近傍特徴変更選択処理を行う(図14のステップS204)。ここで、第2近傍特徴変更選択処理の詳細な動作を、図16を参照して説明する。
【0086】
まず、更新部26は、特徴量の番号を参照できる変数i=Nを設定し、1番目の追加特徴量を参照できる状態にする(ステップS82)。以下、ステップS33乃至ステップS45は、実施例1における図9のフローチャートにおけるステップS33乃至ステップS45と同じであり、同様に実行する。
【0087】
次いで、更新部26は、取得した全ての追加特徴量に対して、ステップS33乃至ステップS45の処理を実行したか否かを判定する(ステップS96)。全ての追加特徴量に対して処理を完了している場合には(ステップS96のYes)、処理を完了する。全ての追加特徴量に対して処理を完了していない場合は(ステップS96のNo)、ステップS33に戻る。なお、更新部26は、第1近傍特徴及び第2近傍特徴を変更又は選択する処理を、選択部11と同様な方法で、並列して実行することができる。
【0088】
更新部26は、特徴量及び追加特徴量の数に応じて、第1近傍特徴の数kと第2近傍特徴の数uを変更することができる。例えばk+uがNの1%で近似できたとき、k+uがN+Mの1%で近似できるように、kとuを夫々増やしても良い。
【0089】
更新部26は、選択した第1近傍特徴と第2近傍特徴の情報を決定部22に出力する。
【0090】
次いで、作成部22は、特徴量及び追加特徴量毎に周辺密度を推定し(図14のステップS205)、第1近傍特徴及び第2近傍特徴の中から、特徴量または追加特徴量毎に同じクラスに分類する特徴量または追加特徴量を決定する(図14のステップS206)。決定部22は決定した結果を参照できるテーブルを作成し(図14のステップS207)、分類部13に出力する。
【0091】
次いで、分類部13は、決定部12で作成されたテーブルを参照し、特徴量及び追加特徴量毎にクラスIDを付与する(図14のステップS208)。分類部13は、各特徴量のクラスID及び各追加特徴量のクラスIDを管理部14に出力する。
【0092】
次いで、管理部14は、閾値ths又は閾値thcを変更する必要があるかをチェックする(図14のステップS209)。閾値ths又は閾値thcの変更が必要な場合には(図14のステップS209のYes)、閾値thsの変更が必要であるかをチェックする(図14のステップS210)。閾値thsの変更が必要な場合には(図14のステップS210のYes)、閾値ths及び閾値thcの値を決定部22に出力し、ステップS205に戻る。閾値thsの変更が必要ない場合は(図14のステップS210のNo)、閾値thcの値を決定部22に出力し、ステップS206に戻る。閾値ths及び閾値thcの変更が必要ない場合には(図14のステップS209のNo)、処理を終了する。
【0093】
なお、決定部22、分類部13及び管理部14は、選択部21から入力された第1近傍特徴及び第2近傍特徴の情報を用いて、図3のステップS105乃至ステップS110の処理を実行し、取得部10が取得した特徴量にクラスIDを付与することもできる。
【0094】
以上のように、本実施例によれば、識別対象を追加する際、追加する以前に処理した結果を利用した、効率的、かつ、高速なクラスタリング処理が可能となる。
【実施例3】
【0095】
次に、第3の実施例に係る信号分類装置100について説明する。なお、第1の実施例と同等の構成については、同一の符号を付与し、その説明を省略する。
【0096】
図17は、第3の実施例の信号分類装置100cの機能構成を示したブロック図である。図17に示したように、本実施例の信号分類装置100は、取得部10、選択部11、決定部12、分類部13、管理部34及び表示部37から構成される。
【0097】
なお、図17において、管理部34及び表示部37は、取得部10、選択部11、作成部12及び分類部13と同様、CPU101とROM104に予め記録された所定のプログラムとの協働により実現される機能部である。
【0098】
管理部34は、分類部13から取得したクラスIDの付与結果を表示部37に出力する。
【0099】
表示部37は、管理部34から取得したクラスIDの付与結果に基づき、表示部103を介し、画像や文字を用いて識別対象の分類結果を表示する。
【0100】
次に、本実施例の信号分類装置100の動作を説明する。図18は、本実施例の信号分類装置100によるクラスタリング処理の流れを示したフローチャートである。以下、図18を参照して、本実施例の信号分類装置について説明する。
【0101】
まず、入力部106等を介して識別対象が入力されると(図18のステップS101)、取得部10は、入力された識別対象から特性を表す特徴量を取得する(図18のステップS102)。取得部10は、取得した特徴量を選択部11に出力する。
【0102】
次いで、選択部11は、各特徴量に対して、第1近傍特徴を選択する第1近傍特徴選択処理を実行する(図18のステップS103)。また、選択部11は、各特徴量に対して、第2近傍特徴を選択する第2近傍特徴選択処理を実行する(図18のステップS104)。選択部11は、選択した第1近傍特徴及び第2近傍特徴の情報を決定部12に出力する。
【0103】
次いで、決定部12は、特徴量毎に周辺密度を推定し(図18のステップS105)、第1近傍特徴及び第2近傍特徴の中から、特徴量毎に同じクラスに分類する特徴量を決定する(図18のステップS106)。決定部12は決定した結果を参照できるテーブルを作成し(図18のステップS107)、分類部13に出力する。
【0104】
次いで、分類部13は、決定部12で作成されたテーブルを参照し、特徴量毎にクラスIDを付与する(図18のステップS108)。分類部13は、各特徴量のクラスIDを管理部34に出力する。
【0105】
次いで、管理部34は、各特徴量のクラスIDを表示部37に出力する。
【0106】
次いで、表示部37は、識別対象の分類結果を表示する(図18のステップS301)。
【0107】
識別対象が顔画像を表す電気信号である場合、表示部37は、例えば図19のように、人物毎に分類し、整理した顔画像一覧を表示できる。また、特定の顔を選択して、同一人物の顔画像一覧を表示し、人物の検索を容易にすることもできる(図20)。このように、表示部37では、識別対象によって一意に定められることなく、各特徴量のクラスIDによる分類結果との組み合わせで複数のバリエーションを持って動作することが可能である。
【0108】
また、識別対象が音声のように画像とは異なる信号の場合には、以下のようになる。例えば、識別する対象となる信号が会議音声である場合、複数の区間に分割してクラスタリング処理(信号分類の処理)を行う。分類結果は、登場話者毎の発言のタイムラインを表示すると共に表示され、特定の再生位置あるいは、特定発言の視聴を容易に行うことができる(図21)。また、識別対象が楽曲信号である場合に、複数の区間に分割してクラスタリング処理を行えば、特定の旋律や曲の最も印象的な部分(サビ)など、特定のパートの聴取を容易に行うことができる(図22)。また、複数の楽曲を識別対象とする場合には、類似楽曲毎に分類し、整理した楽曲一覧を表示することも可能である(図23)。
【0109】
図18の戻り、本実施形態における管理部34について説明する。管理部34は、閾値ths又は閾値thcを変更する必要があるかをチェックする(図18のステップS109)。閾値ths又は閾値thcの変更が必要な場合には(図18のステップS109のYes)、閾値thsの変更が必要であるかをチェックする(図18のステップS110)。閾値thsの変更が必要な場合には(図18のステップS110のYes)、閾値ths及び閾値thcの値を決定部12に出力し、ステップS105に戻る。閾値thsの変更が必要ない場合は(図18のステップS110のNo)、閾値thcの値を決定部12に出力し、ステップS106に戻る。閾値ths及び閾値thcの変更が必要ない場合には(図18のステップS109のNo)、処理を終了する。
【0110】
以上のように、本実施例によれば、識別対象を複数のクラスに分類した後、分類結果を様々な形式で表示することで、視聴や検索、データ整理を容易に行うことができる。
【実施例4】
【0111】
第4の実施例に係る信号分類装置について説明する。なお、第1の実施例と同等の構成については、同一の符号を付与し、その説明を省略する。
【0112】
図24は、第4の実施例に係る信号分類装置100dの機能構成を示したブロック図である。図24に示したように、本実施例の信号分類装置100は、取得部10、選択部11、決定部42、分類部13及び管理部14から構成され、決定部は更に判定部46を有する。なお、図24において、選択部11、決定部42は、取得部10、分類部13及び管理部14と同様、CPU101とROM104に予め記録された所定のプログラムとの協働により実現される機能部である。
【0113】
判定部46は、取得部10で取得した各特徴量に対して、選択部11が選択したk個の第1近傍特徴及びu個の第2近傍特徴の変更を制御する。判定部46は、特徴量毎に更新した第1近傍特徴及び第2近傍特徴と、追加特徴量毎に選択した第1近傍特徴及び第2近傍特徴を決定部22に出力する。
【0114】
決定部42は、判定部46が更新すると判定した特徴量毎の第1近傍特徴及び第2近傍特徴に関する情報を用いて、前記各特徴量及び前記各追加特徴量に対して周辺密度を推定する。決定部42での周辺密度の推定は、第1の実施例における決定部12と同様の方法である。
【0115】
次に、本実施例の信号分類装置100の動作を説明する。図25は、本実施例の信号分類装置100によるクラスタリング処理の流れを示したフローチャートである。以下、図25を参照して、本実施例の信号分類装置について説明する。
【0116】
まず、入力部106等を介して識別対象が入力されると(図25のステップS101)、取得部10は、入力された識別対象から特性を表す特徴量を取得する(図25のステップS102)。取得部10は、取得した特徴量を選択部11に出力する。
【0117】
次いで、選択部11は、各特徴量に対して、第1近傍特徴を選択する第1近傍特徴選択処理を実行する(図25のステップS103)。また、選択部11は、各特徴量に対して、第2近傍特徴を選択する第2近傍特徴選択処理を実行する(図25のステップS104)。選択部11は、選択した第1近傍特徴及び第2近傍特徴の情報を決定部42に出力する。
【0118】
決定部42は、特徴量の類似性を比較するための閾値thsを参照し、選択部11で選択された第1の近傍特徴と第2の近傍特徴の情報を用いて、前記各特徴に対して周辺密度を決定する(図25のステップS105)。
【0119】
次いで、決定部42は、第1近傍特徴及び第2近傍特徴の中から、特徴量毎に同じクラスに分類する特徴量を決定する(図25のステップS106)。以下では、同じ特徴量に分類する特徴量の候補のことを修正候補と記載する。
【0120】
ここで、決定部42が特徴量xiと同じクラスに分類する特徴量xjは、各々の特徴量毎の参照関係に関する情報を用いて決定する。より具体的には、特徴量xiと特徴量xjとはそれぞれが互いの近傍特徴に含まれている、または、特徴量xiと特徴量xjとは共通の近傍特徴を持っているという条件を満たすか否かを判定部46が判定し、条件を満たす場合に、同じクラスに分類する特徴量の候補とする。条件を満たさない場合は互いの修正候補としない(図25のステップS406)。
【0121】
たとえば、図12で用いた1次元の特徴量x0からx9の場合、参照関係の条件を満たさないのは、は表5における太枠部分、x6及びx7の類似度S(8,j)及びS(9,j)である。したがって、x8及びx9にとって、x6及びx7は修正候補とはならない。
【表5】
【0122】
決定部42は決定された特徴量毎に参照できるテーブルを作成し(図25のステップS107)、分類部13に出力する。
【0123】
次いで、分類部13は、決定部42で作成されたテーブルを参照し、特徴量及び追加特徴量毎にクラスIDを付与する(図25のステップS108)。分類部13は、各特徴量のクラスID及び各追加特徴量のクラスIDを管理部14に出力する。
【0124】
次いで、管理部14は、閾値ths又は閾値thcを変更する必要があるかをチェックする(図25ステップS109)。閾値ths又は閾値thcの変更が必要な場合には(図25のステップS109のYes)、閾値thsの変更が必要であるかをチェックする(図25のステップS110)。閾値thsの変更が必要な場合には(図25のステップS110のYes)、閾値ths及び閾値thcの値を決定部42に出力し、ステップS105に戻る。閾値thsの変更が必要ない場合は(図25のステップS110のNo)、閾値thcの値を決定部42に出力し、ステップS106に戻る。閾値ths及び閾値thcの変更が必要ない場合には(図25のステップS109のNo)、処理を終了する。
【0125】
実験4により得た分類結果は、表6のようになる。これは、実験2により得た分類結果(表3)と同じ結果であるが、実験4では閾値thcを0.1のように低く設定しても分類結果は変化しない。一方、実験2では、閾値thcを0.14以下に設定すると、x8の周辺密度よりx7の周辺密度の方が高いために、y(x8)=x7となる。よって、x4からx9のクラスIDは2となり望ましくない分類結果となる(過結合)。
【0126】
以上のように本発明によれば、特徴量の互いの参照関係を考慮することにより、効率を維持したまま、閾値に対する頑健性が増し、クラス分類の精度がより向上する。
【表6】
【0127】
[変更例]
判定部は識別対象のもつ個別情報によって修正候補の判定を行ってもよい。
【0128】
たとえば、複数人の人物の顔を分類するクラスタリング処理を行う場合、識別対象として入力された同一の写真に写る各個人の顔を同じ分類としないように制御してもよい(図26(a)参照)。より具体的には特徴量xi と特徴量xjとが属する写真が同一の場合について説明する。
【0129】
まず、入力信号として、複数の識別対象が入力される際に、同一の写真から得られた識別対象であることを示す写真IDを識別対象に付与する。xiが属する写真IDが、 PI(xi)であるとき、類似した特徴量xiおよび特徴量xjについて、PI(xi)=PI(xj)が成り立つとき、収束するy(xi)は式2によって拘束される。
【0130】
更に、写真IDの異なる特徴量z(xi)についても、y(xi)=z(xi)であるとき、はxiに対して式3を適用する。
【数2】
【数3】
【0131】
これらにより、ひとつのクラスに分類される特徴群(図26(b))を複数のクラスに適切に分離することが可能になり、メモリ容量を要さずにより精度の高い分類が可能となる。
【0132】
なお、写真IDを取らずに、入力手段等を介して同じグループとなる分類か否かの情報をユーザ等が入力してもよい。この場合、ユーザ等が決めた更新情報を更新情報取得部によって取得し、判定部が識別対象が同じ分類とならないように制御する。また、ユーザが別分類としたい識別対象について入力したものに対して異なるIDを付与し、IDが異なるときに式2等を拘束条件として、修正候補の判定をおこなってもよい。
【0133】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、多くの発明を形成できる。例えば、実施形態に示される全構成要素からいくつかの構成要素を削除しても良い。さらに、異なる実施形態にわたる構成要素を適宜組み合わせても良い。
【符号の説明】
【0134】
101・・・制御部、102・・・操作部、103・・・表示部、104、105・・・記憶部、106・・・入力部、107・・・外部記憶装置、108・・・バス
10・・・取得部、11、22・・・選択部、12・・・決定部、13・・・分類部、34、14・・・管理部、25・・・追加取得部、26・・・更新部、37・・・表示部、46・・・判定部
【特許請求の範囲】
【請求項1】
入力された信号に含まれるN個の識別対象の特徴量を取得する取得部と、
前記特徴量毎に、前記特徴量からk個(1≦k≦N)の前記特徴量を第1近傍特徴として選択する第1の選択部と、
互いに類似する前記特徴量から特徴群を生成し、取得したN個の前記特徴量から異なる前記特徴群に属するu個(1≦k+u≦N−2)の前記特徴量を第2の近傍特徴として選択する第2の選択部と、
前記特徴量の類似性を比較するための閾値と、前記特徴量毎に算出した周辺密度とを用いて、同じ分類となる前記特徴量を決定する決定部と、
前記特徴量の決定結果から分類を行う分類部と、
前記閾値を管理する管理部と、
を備えたことを特徴とする信号分類装置。
【請求項2】
追加するM個の識別対象の特徴量を取得する追加取得部と、
追加された前記特徴量を含む前記特徴量について、特徴量の類似したk個(1≦k≦N+M−2)の第1の近傍特徴と、前記特徴群が異なるu個(1≦k+u≦N+M−2)の第2の近傍特徴とを選択し、前記追加された特徴量夫々についてk個の第1近傍特徴及びu個の第2近傍特徴を選択する第3の選択部をさらに備えることを特徴とする請求項1記載の信号分類装置。
【請求項3】
前記決定部は前記特徴量の参照関係に関する情報によって、分類を判定する判定部を更に備えることを特徴とする請求項1または2に記載の信号分類装置。
【請求項4】
前記参照関係に関する情報は、前記特徴量が互いの近傍特徴であるか否か、あるいは前記特徴量が共通の近傍特徴を有するか否かであることを特徴とする請求項3に記載の信号分類装置。
【請求項5】
前記取得部は前記入力信号として画像を取得し、
前記参照関係に関する情報が、前記識別対象が同じ前記画像から取得されたものであることを示す情報であることを特徴とする請求項3または4に記載の信号分類装置。
【請求項6】
前記特徴量の参照関係に関する情報を取得する更新情報取得部を更に有することを特徴とする請求項3乃至5いずれか1項記載の信号分類装置。
【請求項7】
前記分類部の分類に基づいて、前記識別対象の分類結果を表示する表示部をさらに備える請求項1乃至6いずれか1項に記載の信号分類装置。
【請求項8】
前記分類部は、前記分類結果の中で類似した特徴量を持つ分類を一つに統合することを特徴とする請求項1乃至7いずれか1項に記載の信号分類装置。
【請求項9】
前記管理部は、前記閾値を新たに取得し取得した値に変更することを特徴とする請求項1乃至8に記載の信号分類装置。
【請求項10】
前記追加取得部は、取得数(M)に応じて、前記第1の近傍特徴の選択数kを変更することを特徴とする請求項2乃至9いずれか1項に記載のクラスタリング装置。
【請求項11】
前記決定部は、前記特徴量と決定した分類とを組とする表形式のデータとして保持し、該当データを用いて分類を行うこと特徴とする請求項1乃至10いずれか1項記載の信号分類装置。
【請求項12】
前記作成部は前記更新部の結果を用いて、前記テーブルを作成することを特徴とする請求項11に記載の信号分類装置。
【請求項1】
入力された信号に含まれるN個の識別対象の特徴量を取得する取得部と、
前記特徴量毎に、前記特徴量からk個(1≦k≦N)の前記特徴量を第1近傍特徴として選択する第1の選択部と、
互いに類似する前記特徴量から特徴群を生成し、取得したN個の前記特徴量から異なる前記特徴群に属するu個(1≦k+u≦N−2)の前記特徴量を第2の近傍特徴として選択する第2の選択部と、
前記特徴量の類似性を比較するための閾値と、前記特徴量毎に算出した周辺密度とを用いて、同じ分類となる前記特徴量を決定する決定部と、
前記特徴量の決定結果から分類を行う分類部と、
前記閾値を管理する管理部と、
を備えたことを特徴とする信号分類装置。
【請求項2】
追加するM個の識別対象の特徴量を取得する追加取得部と、
追加された前記特徴量を含む前記特徴量について、特徴量の類似したk個(1≦k≦N+M−2)の第1の近傍特徴と、前記特徴群が異なるu個(1≦k+u≦N+M−2)の第2の近傍特徴とを選択し、前記追加された特徴量夫々についてk個の第1近傍特徴及びu個の第2近傍特徴を選択する第3の選択部をさらに備えることを特徴とする請求項1記載の信号分類装置。
【請求項3】
前記決定部は前記特徴量の参照関係に関する情報によって、分類を判定する判定部を更に備えることを特徴とする請求項1または2に記載の信号分類装置。
【請求項4】
前記参照関係に関する情報は、前記特徴量が互いの近傍特徴であるか否か、あるいは前記特徴量が共通の近傍特徴を有するか否かであることを特徴とする請求項3に記載の信号分類装置。
【請求項5】
前記取得部は前記入力信号として画像を取得し、
前記参照関係に関する情報が、前記識別対象が同じ前記画像から取得されたものであることを示す情報であることを特徴とする請求項3または4に記載の信号分類装置。
【請求項6】
前記特徴量の参照関係に関する情報を取得する更新情報取得部を更に有することを特徴とする請求項3乃至5いずれか1項記載の信号分類装置。
【請求項7】
前記分類部の分類に基づいて、前記識別対象の分類結果を表示する表示部をさらに備える請求項1乃至6いずれか1項に記載の信号分類装置。
【請求項8】
前記分類部は、前記分類結果の中で類似した特徴量を持つ分類を一つに統合することを特徴とする請求項1乃至7いずれか1項に記載の信号分類装置。
【請求項9】
前記管理部は、前記閾値を新たに取得し取得した値に変更することを特徴とする請求項1乃至8に記載の信号分類装置。
【請求項10】
前記追加取得部は、取得数(M)に応じて、前記第1の近傍特徴の選択数kを変更することを特徴とする請求項2乃至9いずれか1項に記載のクラスタリング装置。
【請求項11】
前記決定部は、前記特徴量と決定した分類とを組とする表形式のデータとして保持し、該当データを用いて分類を行うこと特徴とする請求項1乃至10いずれか1項記載の信号分類装置。
【請求項12】
前記作成部は前記更新部の結果を用いて、前記テーブルを作成することを特徴とする請求項11に記載の信号分類装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図25】
【図26】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図25】
【図26】
【公開番号】特開2011−191824(P2011−191824A)
【公開日】平成23年9月29日(2011.9.29)
【国際特許分類】
【出願番号】特願2010−55103(P2010−55103)
【出願日】平成22年3月11日(2010.3.11)
【出願人】(000003078)株式会社東芝 (54,554)
【Fターム(参考)】
【公開日】平成23年9月29日(2011.9.29)
【国際特許分類】
【出願日】平成22年3月11日(2010.3.11)
【出願人】(000003078)株式会社東芝 (54,554)
【Fターム(参考)】
[ Back to top ]