(57)【要約】【課題】クラスタ状態の時間的変化が起こったとしてもこの変化を正確に検知することが可能なクラスタリング装置及びクラスタリング方法を得る。【解決手段】通信プロセス検知部１は通信プロセスを検知する。通信グループ推定部２は通信プロセスのグループを推定する。メンバシップ関数共通化部３は通信プロセスそれぞれが持つプロセスグループを表すメンバシップ関数を共通化する。その後、メンバシップ関数ランダム摂動部４は、通信プロセスについてそれぞれのメンバシップ関数にランダム摂動処理を実行する。続いて、プロセスグループ指定部５は通信が密に行われているプロセスグループを検知する。最後に、プロセス再配置部６は通信密のプロセスグループに応じてプロセスの実行プロセッサを再配置する。【選択図】　　　　図１
2004102572.tif 000002
【特許請求の範囲】
【請求項１】
クラスタ状態が時間経過とともに変化する複数の物理的要素をクラスタ分類するクラスタリング装置であって、前記複数の物理的要素それぞれに対し複数のグループそれぞれの帰属度を示すメンバシップ関数が割り当てられ、
前記複数の物理的要素のうち、所定の条件を満足する物理的要素からなる部分集合を規定する外部情報を、経時変化に伴い順次入力する外部情報入力部と、
前記外部情報に基づき、前記複数のグループから前記部分集合に該当する少なくとも一つのグループを推定グループとして規定するグループ推定情報を得るグループ推定部と、
前記外部情報及び前記グループ推定情報に基づき、前記部分集合のうち前記推定グループにおける前記メンバシップ関数の帰属度を高める共通化処理を行い、共通化処理後のメンバシップ関数情報を得るメンバシップ関数共通化部と、
前記外部情報及び前記メンバシップ関数情報に基づき、前記複数のグループから所定の選択内容で選択した第１の選択グループと、前記第１の選択グループを除く前記複数のグループから任意に選択した第２の選択グループとを選択し、前記部分集合内において前記第１及び第２の選択グループ間で、前記メンバシップ関数共通化処理後のメンバシップ関数値を入れ替えるランダム摂動処理を行うメンバシップ関数ランダム摂動部と、
を備えるクラスタリング装置。
【請求項２】
請求項１記載のクラスタリング装置であって、
前記ランダム摂動処理後の前記メンバシップ関数に基づき、前記複数の物理的要素をクラスタ分類するクラスタ分類決定部、
をさらに備えるクラスタリング装置。
【請求項３】
請求項１あるいは請求項２記載のクラスタリング装置であって、
前記メンバシップ関数ランダム摂動部は前記推定グループ情報をさらに受け、
前記第１の選択グループは、前記推定グループ情報で規定された前記推定グループのうちの一のグループを含む、
クラスタリング装置。
【請求項４】
請求項１ないし請求項３のうち、いずれか１項に記載のクラスタリング装置であって、
前記物理的要素はプロセッサの処理する実行単位であるプロセスを含み、
前記所定の条件は２以上のプロセス間で共通のデータ通信を行うことを含み、
前記部分集合は共通のデータ通信を行うプロセスの集合を含む、
クラスタリング装置。
【請求項５】
請求項１ないし請求項３のうち、いずれか１項に記載のクラスタリング装置であって、
前記物理的要素は動画像の基本単位である画素を含み、
前記所定の条件は所定の画像領域抽出方法により抽出されることを含み、
前記部分集合は前記複数の画像のうち前記所定の画像領域抽出方法により抽出された画素の集合を含む、
クラスタリング装置。
【請求項６】
請求項５記載のクラスタリング装置であって、
前記所定の画像領域抽出方法は、抽出の判定基準となった情報を前記部分集合の各画素に付加する方法を含み、
前記メンバシップ関数共通化部は、前記判定基準を考慮して部分集合の各画素に対する前記共通化処理を行う、
クラスタリング装置。
【請求項７】
クラスタ状態が時間経過とともに変化する複数の物理的要素をクラスタ分類するクラスタリング方法であって、前記複数の物理的要素それぞれに対し複数のグループそれぞれの帰属度を示すメンバシップ関数が割り当てられ、
（ａ）　前記複数の物理的要素のうち、所定の条件を満足する物理的要素からなる部分集合を規定する外部情報を入力するステップと、
（ｂ）　前記外部情報に基づき、前記複数のグループから前記部分集合に該当する少なくとも一つのグループを推定グループとして規定するグループ推定情報を得るステップと、
（ｃ）　前記外部情報及び前記グループ推定情報に基づき、前記部分集合のうち前記推定グループにおける前記メンバシップ関数の帰属度を高める共通化処理を行い、共通化処理後のメンバシップ関数情報を得るステップと、
（ｄ）　前記外部情報及び前記メンバシップ関数情報に基づき、前記複数のグループから所定の選択内容で選択した第１の選択グループと、前記第１の選択グループを除く前記複数のグループから任意に選択した第２の選択グループとを選択し、前記部分集合内において前記第１及び第２の選択グループ間で、前記メンバシップ関数共通化処理後のメンバシップ関数値を入れ替えるランダム摂動処理を行うステップとを備え、
前記ステップ（ａ）〜（ｄ）　は、新たな前記外部情報がステップ（ａ）　で入力される毎に繰り返し実行されることを特徴とする、
クラスタリング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、構成要素のグループ分けが時間的に変化する状況を推定するクラスタリング方法に関するものである。
【０００２】
【従来の技術】
図１４は、例えば、特許文献１に開示された、従来のクラスタリング装置を示したブロック図である。
【０００３】
同図に示すように、クラスタ作成装置１０１が、プロトタイプデータＤＢ１０４を用いてクラスタ１０５を生成する。クラスタリング実行装置１０２は、生成されたクラスタ１０５を用いて、入力された入力データ１０６をクラスタリングし、クラスタリング結果１０７を出力する。クラスタリング結果監視装置１０３は、出力されたクラスタリング結果１０７を監視し、入力データ１０６のクラスタリング結果１０７に含まれる誤差が、ある一定値以上の値であり、明らかに誤分類であると判断した時、その入力データ１０６を誤分類入力データＤＢ１０８に追加し、誤分類入力データＤＢ１０８に溜まったデータの数をカウントする。この誤分類入力データＤＢ１０８内のデータがある一定数を超えた時、クラスタ作成装置１０１に、この誤分類入力データＤＢ１０８を用いて、クラスタを作成するように指示する。
【０００４】
このように、図１４で示したクラスタリング装置は、新たに入力される入力データの動的変化に対応して自動的にクラスタを作成することができる。
【０００５】
【特許文献１】
特開２００１−２８３１８４号公報（図１）
【０００６】
【発明が解決しようとする課題】
従来のクラスタリング装置あるいは方法では、いったんクラスタリングされた構成要素がそのクラスタの状態を変化させるということを配慮していない。図１４を用いて示したクラスタリング装置においても、既にクラスタリングされたデータ（要素）に対する新たなクラスタリングは行っていない。
【０００７】
したがって、もしも、いったんクラスタリングされた要素がそのグループ分けの状態を変化させ、例えば二つのグループに分かれるなどの細分化を起こしたとすると、図１４で示したクラスタリング装置ではこのことを検知することは不可能である。従来のクラスタリング方法あるいは装置では、個々の要素の類似性にもとづいてクラスタが決められるため、いったん同一クラスタに所属すると認定された構成要素を分離することが困難であった。
【０００８】
つまり、従来のクラスタリング方法では、クラスタの状態に新規なクラスタの発生や、既存のクラスタの分裂などのという時間的に変化が起こった場合、クラスタの全体的状態の変化を知らせる外部情報を与えるか、一旦クラスタリング情報をリセットしてクラスタ分類をやり直す必要が生じてしまうというも問題点があった。
【０００９】
この発明は、上記のような問題点を解決するためになされたものであり、クラスタの分裂などによるクラスタ状態の時間的変化が起こったとしてもこの変化を正確に検知することが可能なクラスタリング装置及びクラスタリング方法を得ることを目的とする。
【００１０】
【課題を解決するための手段】
この発明に係る請求項１記載のクラスタリング装置は、クラスタ状態が時間経過とともに変化する複数の物理的要素をクラスタ分類しする装置であって、前記複数の物理的要素それぞれに対し複数のグループそれぞれの帰属度を示すメンバシップ関数が割り当てられ、前記複数の物理的要素のうち、所定の条件を満足する物理的要素からなる部分集合を規定する外部情報を、経時変化に伴い順次入力する外部情報入力部と、前記外部情報に基づき、前記複数のグループから前記部分集合に該当する少なくとも一つのグループを推定グループとして規定するグループ推定情報を得るグループ推定部と、前記外部情報及び前記グループ推定情報に基づき、前記部分集合のうち前記推定グループにおける前記メンバシップ関数の帰属度を高める共通化処理を行い、共通化処理後のメンバシップ関数情報を得るメンバシップ関数共通化部と、前記外部情報及び前記メンバシップ関数情報に基づき、前記複数のグループから所定の選択内容で選択した第１の選択グループと、前記第１の選択グループを除く前記複数のグループから任意に選択した第２の選択グループとを選択し、前記部分集合内において前記第１及び第２の選択グループ間で、前記メンバシップ関数共通化処理後のメンバシップ関数値を入れ替えるランダム摂動処理を行うメンバシップ関数ランダム摂動部と、を備えている。
【００１１】
また、請求項２の発明は、請求項１記載のクラスタリング装置であって、前記ランダム摂動処理後の前記メンバシップ関数に基づき、前記複数の物理的要素をクラスタ分類するクラスタ分類決定部をさらに備えている。
【００１２】
また、請求項３の発明は、請求項１あるいは請求項２記載のクラスタリング装置であって、前記メンバシップ関数ランダム摂動部は前記推定グループ情報をさらに受け、前記第１の選択グループは、前記推定グループ情報で規定された前記推定グループのうちの一のグループを含む。
【００１３】
また、請求項４の発明は、請求項１ないし請求項３のうち、いずれか１項に記載のクラスタリング装置であって、前記物理的要素はプロセッサの処理する実行単位であるプロセスを含み、前記所定の条件は２以上のプロセス間で共通のデータ通信を行うことを含み、前記部分集合は共通のデータ通信を行うプロセスの集合を含む。
【００１４】
また、請求項５の発明は、請求項１ないし請求項３のうち、いずれか１項に記載のクラスタリング装置であって、前記物理的要素は動画像の基本単位である画素を含み、前記所定の条件は所定の画像領域抽出方法により抽出されることを含み、前記部分集合は前記複数の画像のうち前記所定の画像領域抽出方法により抽出された画素の集合を含む。
【００１５】
また、請求項６の発明は、請求項５記載のクラスタリング装置であって、前記所定の画像領域抽出方法は、抽出の判定基準となった情報を前記部分集合の各画素に付加する方法を含み、前記メンバシップ関数共通化部は、前記判定基準を考慮して部分集合の各画素に対する前記共通化処理を行う。
【００１６】
この発明に係る請求項７記載のクラスタリング方法は、クラスタ状態が時間経過とともに変化する複数の物理的要素をクラスタ分類する方法であって、前記複数の物理的要素それぞれに対し複数のグループそれぞれの帰属度を示すメンバシップ関数が割り当てられ、（ａ）　前記複数の物理的要素のうち、所定の条件を満足する物理的要素からなる部分集合を規定する外部情報を入力するステップと、（ｂ）　前記外部情報に基づき、前記複数のグループから前記部分集合に該当する少なくとも一つのグループを推定グループとして規定するグループ推定情報を得るステップと、（ｃ）　前記外部情報及び前記グループ推定情報に基づき、前記部分集合のうち前記推定グループにおける前記メンバシップ関数の帰属度を高める共通化処理を行い、共通化処理後のメンバシップ関数情報を得るステップと、（ｄ）　前記外部情報及び前記メンバシップ関数情報に基づき、前記複数のグループから所定の選択内容で選択した第１の選択グループと、前記第１の選択グループを除く前記複数のグループから任意に選択した第２の選択グループとを選択し、前記部分集合内において前記第１及び第２の選択グループ間で、前記メンバシップ関数共通化処理後のメンバシップ関数値を入れ替えるランダム摂動処理を行うステップとを備え、前記ステップ（ａ）〜（ｄ）　は、新たな前記外部情報がステップ（ａ）　で入力される毎に繰り返し実行される。
【００１７】
【発明の実施の形態】
＜実施の形態１＞
図１はこの発明の実施の形態１であるクラスタリング装置の構成を示すブロック図である。
【００１８】
なお、実施の形態１では、並列分散計算機システムにおいて、ネットワーク通信状態を解析し、プロセスの再配置を行う問題に関して本発明を適用した場合を示している。さらに、本実施の形態における前提として、計算実行を行う複数のプロセッサとプロセッサ間の通信を行う通信手段とがあり、各プロセッサは処理の実行単位である計算プロセスを実行する。したがって、論理的に考えると、複数の（計算）プロセスがそれぞれ幾つかの特定のプロセスとの間で一般には多対多のデータ通信を行いながら並列に実行されていることになる。ただし、それぞれのプロセスの通信相手は、時間的に変化する場合があるとする。
【００１９】
図２は状態１におけるプロセルグループを示す説明図である。図３は状態１から所定時間経過後の状態２におけるプロセスグループを示す説明図である。
【００２０】
図２及び図３において、○印は実行中の計算プロセス８を示し、計算プロセス８，８間を結ぶ実線はプロセス間で通信が有ったことを示すプロセス間通信９を示している。そして、図２では、図示した全ての計算プロセス８はプロセスグループ１０に属する。図３では、図示した半数の計算プロセス８がプロセスグループ１１に属し、残りの半数がプロセスグループ１２に属する。このように、１０〜１２で示す点線は、点線内のプロセスが同一グループを成している状態を示している。
【００２１】
図２及び図３で示すように、複数の計算プロセスがそれぞれ幾つかの特定のプロセスとの間で一般には多対多のデータ通信を行いながら並列に実行され、そのプロセスグループが時間の経過と共に変化する並列分散計算機システムが本実施の形態の前提条件となっている。
【００２２】
図１に戻って、通信プロセス検知部１は並列に実行されている計算プロセス同士が行う通信の送り手と受け手となる通信プロセスを検知して通信プロセス情報Ｄ１を通信グループ推定部２に出力する。
【００２３】
通信グループ推定部２は、通信プロセス情報Ｄ１で規定された通信プロセスのグループを推定してグループ推定情報Ｄ２をメンバシップ関数共通化部３に出力する。
【００２４】
メンバシップ関数共通化部３は通信プロセス情報Ｄ１及びグループ推定情報Ｄ２に基づき通信プロセスそれぞれが持つプロセスグループを表すメンバシップ関数を共通化して、共通化後のメンバシップ関数情報Ｄ３をメンバシップ関数ランダム摂動部４に出力する。
【００２５】
メンバシップ関数ランダム摂動部４は、通信プロセス情報Ｄ１及びグループ推定情報Ｄ２に基づき通信プロセスについてそれぞれのメンバシップ関数（メンバシップ関数情報Ｄ３で共通化処理を経た後のメンバシップ関数）のランダム摂動処理を実行し、摂動処理後のメンバシップ関数情報Ｄ４をプロセスグループ指定部５に出力する。
【００２６】
プロセスグループ指定部５はメンバシップ関数情報Ｄ４に基づき全てのプロセスのメンバシップ関数を調べ、通信が密に行われているプロセスグループを検知し、検知した通信密プロセスグループを規定した通信密プロセスグループ情報Ｄ５をプロセス再配置部６に出力する。
【００２７】
プロセス再配置部６は通信密プロセスグループ情報Ｄ５に基づき、プロセスグループに応じてプロセスの実行プロセッサを再配置する。
【００２８】
図４は実施の形態１のクラスタリング装置によるクラスタリング方法の処理手順を示すフローチャートである。
【００２９】
まず、図４で示したフローチャートのアルゴリズムについての詳細の理解を容易にするために、幾つかの定義を行う。
【００３０】
まず、プロセス全体の集合を「Ｅ」で表し、個々のプロセスを「ｅ」で表す。次にプロセスグループを表す便宜的なラベルを「ｃ」としその全体を表す集合を「Ｇ」と表す。Ｎｇ　を便宜的なクラスタ数とする。プロセス「ｅ」がプロセスグループ「ｃ」に属する帰属度はメンバシップ関数　ｇｃ（ｅ）　で表す。
【００３１】
ここで注意する点は、プロセスグループは幾つかのプロセスをひとまとまりにすることによってできるもので、あらかじめそれぞれのラベルで表されるプロセスグループが存在しているわけではないため、プロセスグループ数やプロセスグループを表すラベルは、あくまでも便宜的なものである。また、具体的に説明するために、一般性を損なうことなく、メンバシップ関数　ｇｃ（ｅ）　はその値が大きいほど要素　ｅ　がプロセスグループ　ｃ　に属する帰属度が大きいことにし、またメンバシップ関数は全ての要素　ｅ　について以下の（１）式を満足して正規化されていることにする。
【００３２】
【数１】
2004102572.tif 000003
【００３３】
以下、図４を参照して、本実施の形態のクラスタリング装置の動作を上記定義を用いながら説明する。
【００３４】
まず、ステップＳ１で、通信プロセス検知部１は、並列に実行されている計算プロセス同士が行う通信の送り手と受け手となる通信プロセスを検知して通信プロセス情報Ｄ１を得る。
【００３５】
ステップＳ１によって検知された通信プロセスの集合をΓ（ｔ）とする。ただし時間をｔで表す。同時刻に複数の通信に付いて検知が行われた場合、複数のプロセスグループに属するプロセス集合が検知されることになるが、通信が行われた時刻が同じであっても同一のデータのやりとりであるか否かによってプロセス間の通信が独立に行われたか否かを区別できるので、便宜的にそれぞれ独立な通信を別々の時刻に行われた通信であるとしても一般性は失われない。よってΓ（ｔ）は、ある一つのプロセスグループに属するプロセスの部分集合で、時刻　ｔ　に通信を行ったものであると仮定する。
【００３６】
すなわち、通信プロセス情報Ｄ１で規定される情報としてΓ（ｔ）が与えられる。Γ（ｔ）を提供するものは図中に含まれないが、それは何であっても良い。Γ（ｔ）がどのプロセスグループの構成要素からなるものであるか、すなわち、プロセスグループを特定する情報はΓ（ｔ）の他に提供されていても良いが、提供されていなくても良い。
【００３７】
そして、ステップＳ２で通信グループ推定部２は通信プロセス情報Ｄ１の他にプロセスグループを推定する情報の有無を判断する。推定する情報が存在する場合は、直ちにステップＳ４のメンバシップ関数の共通化プロセスを実行可能であるため、予め設定されたクラスタグループの推定結果をそのままグループ推定情報Ｄ２としてステップＳ４に移行する。一方、プロセスグループを推定する情報が通信プロセス情報Ｄ１に明示されていない場合はステップＳ３に移行する。
【００３８】
ステップＳ３において、通信グループ推定部２は通信プロセス情報Ｄ１に基づき通信プロセスのプロセスグループを推定し、推定したプロセスグループを規定するグループ推定情報Ｄ２とし、ステップＳ４に移行する。
【００３９】
以下、ステップＳ３のプロセスグループ推定処理を詳述する。通信グループ推定部２はΓ（ｔ）とメンバシップ関数に基づきプロセスグループ推定処理を実行する。この処理では、Γ（ｔ）が属するクラスタの推定は例えば多数決によって行う。つまり以下の式（２）〜式（５）を実行する。
【００４０】
【数２】
2004102572.tif 000004
【００４１】
【数３】
2004102572.tif 000005
【００４２】
【数４】
2004102572.tif 000006
【００４３】
【数５】
2004102572.tif 000007
【００４４】
式（２）は「ｃ」で規定される各プロセスグループそれぞれにおいて、時刻ｔに通信が行われていた各プロセスのメンバシップ関数の総和Ｓｃを求めている。
【００４５】
式（３），式（４）は総和Ｓｃが大きい順にプロセスグループをソーティングしている。
【００４６】
式（５）は大きい方からＲ（＜Ｎｇ）番目を多数決の勝者とし、大きい順に１番〜Ｒ番目のプロセスグループである勝者の集合を求めている。
【００４７】
このように、式（２）〜式（５）を実行することにより求められたＴＲを多数決で選ばれたΓ（ｔ）の元となるクラスタグループの推定結果とする。なお、ステップＳ２でグループ推定情報が有りと判断された場合は、このＴＲが式（２）〜式（４）を経ることなく直接与えられることになる。
【００４８】
その後、ステップＳ４において、メンバシップ関数共通化部３は通信プロセス情報Ｄ１に基づき通信プロセスそれぞれのプロセスが持つプロセスグループを表すメンバシップ関数を共通化して、共通化後のメンバシップ関数を規定したメンバシップ関数情報Ｄ３を得る。
【００４９】
メンバシップ関数共通化部３は、メンバシップ関数を以下の式（６）及び式（７）を実行することにより、メンバシップ関数の共通化を実行する。
【００５０】
【数６】
2004102572.tif 000008
【００５１】
【数７】
2004102572.tif 000009
【００５２】
なお、式（６），（７）の「ｋ」はグループの便宜的なラベルを示しており、式（６）の「β」は、前時刻から引き継ぐ情報の度合いを制御するパラメータで０≦β＜１であり、メンバシップ関数　ｇ　の上付き変数　ｔ　は時刻を表す。式（７）によってΓ（ｔ）の元となったと推定されたクラスタグループに関して均一にΓ（ｔ）に含まれる要素のメンバシップ関数値が増大されている。なお、式（７）を変形して勝者の集合ＴＲの順位に基づいたクラスタラベルことに異なる重み付けをもってメンバシップ関数を増大させる方法も考えられる。
【００５３】
ステップＳ５において、メンバシップ関数ランダム摂動部４は、通信プロセス情報Ｄ１及びグループ推定情報Ｄ２に基づき通信プロセスそれぞれにおいて、メンバシップ関数情報Ｄ３で規定されたメンバシップ関数にランダム摂動を加え、摂動処理後のメンバシップ関数を規定したメンバシップ関数情報Ｄ４を得る。
【００５４】
図５は図４のステップＳ５の処理の詳細を示すフローチャートである。同図を参照して、ステップＳ１１においてメンバシップ関数値交換相手のグループラベルをランダムに選択する。すなわち、集合ＴＲのＲ番目すなわちνＲのグループを第１の選択グループとし、νＲのグループを除いたグループラベルの中から、確率的或いは擬似確率的方法によってラベルをランダムに一つ選択する。選択されたラベルをγのグループを第２の選択グループとする。
【００５５】
次に、ステップＳ１２において、第１及び第２の選択グループ間でメンバシップ関数のグループラベル交換処理を実行する。すなわち、グループラベルを使って全てのΓ（ｔ）に含まれる要素　ｅ　に対して、以下の式（８）〜式（１１）を順次実行し、　ｇνＲ（ｅ）　の値とｇＹ（ｅ）　の値との入れ替えを行う。
【００５６】
【数８】
2004102572.tif 000010
【００５７】
【数９】
2004102572.tif 000011
【００５８】
【数１０】
2004102572.tif 000012
【００５９】
【数１１】
2004102572.tif 000013
【００６０】
このように、式（８）〜式（１１）を実行することにより、必ず集合ＴＲのＲ番目のグループのメンバシップ関数が交換対象となっている。一方、ランダムに選ばれる交換相手が、もしＴＲに含まれ、すなわち、より上位のグループのメンバシップ関数であれば、ｇνＲ（ｅ）　は強化され、反対にＴＲに含まれないより下位のグループのメンバシップ関数であれば、ｇνＲ（ｅ）　は弱められる。
【００６１】
一般に、ＴＲはグループラベル全体の中では少数なので、ｇνＲ（ｅ）　は弱められ下位に落ちる傾向が強い。この時、他のグループラベルがＲ番目の位置に入れ替わって入ることになる。
【００６２】
したがって、第Ｒ番目の位置は不安定であることがわかる。不安定であるが、一方でより下位にあるグループラベルはこの位置に引き寄せられる効果も存在する。つまり、第Ｒ番目の位置は、吸引力が有ると同時に上位の位置に上がっていく際の障壁となっている。
【００６３】
このようなメンバシップ関数摂動処理を行うと、シミュレーション結果から、複数のプロセスのクラスタ状態の動的変化を検知可能なメンバシップ関数を得ることがわかっている。
【００６４】
なお、本実施の形態では、メンバシップ関数の交換を内部で確率的あるいは疑似確率的に行ったが、外部から提供される情報に基づいて決定論的に行っても良い。また、両者を組み合わせた方法で行っても良い。
【００６５】
図４に戻って、ステップＳ６において、プロセスグループ指定部５は全てのプロセスのメンバシップ関数を調べ、通信が密に行われているプロセスグループを検知して通信密プロセスグループ情報Ｄ５を得る。
【００６６】
図６は図４のステップＳ６の処理の詳細を示すフローチャートである。以下、同図を参照してステップＳ６のプロセスグループ指定処理を説明する。
【００６７】
まず、ステップＳ２１において、プロセス全体Ｇを検査するグループラベル検査変数ｙの初期化を行う。すなわち、適当なグループラベルを選びこれをグループラベル検査変数ｙの初期値とする。
【００６８】
次に、ステップＳ２２において、検査変数ｙに基づきプロセスを選択する。以下、その詳細を説明する。
【００６９】
適当な閾値θを予め設定し、この閾値θに対してＧ’ｙ　＝｛　ｅ｜　ｇｙ（ｅ）　＞　θ｝なるプロセスの集合は、共通のグループラベルに対してメンバシップ関数が一定値より大きい値を持つので、ほぼ同一のプロセスグループであると見なすことができる。この　Ｇ’ｙ　を求める処理がステップＳ２２である。
【００７０】
そして、ステップＳ２３において、ステップＳ２２で選択されたプロセスが同一グループにあるかどうかを検証する。
【００７１】
ステップＳ４のメンバシップ関数の共通化処理における式（６），式（７）の実行によって、メンバシップ関数は冗長にプロセスグループを表すようになるため、Ｇ’ｙにはｇｙ（ｅ）　＞　θではあっても同一のプロセスグループには属さないプロセス、すなわち他のグループラベルに対しては、Ｇ’ｙ　の大多数のプロセスとは異なるメンバシップ関数値をとるプロセスが含まれている場合がある。これを排除するのがステップＳ２３の処理である。ステップＳ２３の具体的処理内容としては様々なスタンダードな方法がある。ここではその一例として多数決による方法を示す。
【００７２】
図７は、多数決計算を元にＧ’ｙ　からメンバシップ関数形が大きく異なるプロセスを取り除くステップＳ２３の処理を詳細に示したフローチャートである。
【００７３】
同図を参照して、ステップＳ３１において、ステップＳ２２で得たＧ’ｙをグループラベルｙに関してプロセスグループを成すプロセスグループ候補とする選択処理を実行する。
【００７４】
ステップＳ３２において、ステップＳ３１で選択されたプロセスグループ候補に該当する全てのプロセスｅについてグループラベルの多数決投票処理を行う。以下、その詳細を説明する。
【００７５】
ステップＳ４の処理（式（６）式（７）に基づく処理）によってＲ個のグループラベルのメンバシップ関数が強化されるため、このＲよりも小さい適当な数Ｐに対して、Ｇ’ｙ　の全てのプロセスｅに対し、プロセスｅのグループラベルｃを固定してメンバシップ関数ｇｃ（ｅ）の値が大きなものからＰ個を選びその数を数える投票処理を行う。この投票処理をＧ’ｙ　に含まれる全てのプロセスに対して行う。すなわち、以下の式（１２）を満足するように、投票処理が実行される。
【００７６】
【数１２】
2004102572.tif 000014
【００７７】
なお、式（１２）において、ｍｋ（ｅ）はプロセス（要素）ｅに関するメンバシップ関数のうち第ｋ番目に大きな値をとるグループラベルを意味し、ｖ（ｃ）　はグループラベルｃで規定されるグループへの投票数を表す。なお、ステップＳ３２の実行開始時に、ｖ（ｃ）　は全て“０”に初期化される。すなわち、各プロセスｅにおいて、ｈｃ（ｅ）（ｇｃ（ｅ））を大きい順に並べた場合、上位Ｐ個となるグループラベルに票を投じてインクリメント（図中の「＋＋」はインクリメントを意味する）する投票処理である。
【００７８】
次に、ステップＳ３３において、ステップＳ３２の投票結果を集計する。ステップＳ３３では、投票結果を元に上位からＰ番目までの得票数のあったグループラベルをまとめて勝者の集合Ｈｙとする。なおこのＰは他の適当な値でも構わない。このＨｙが最終的にプロセスグループを代表するグループラベルの集合Ｈｙとなる。
【００７９】
続いて、ステップＳ３４において、ステップＳ３３の集計結果に基づき、集合Ｈｙに含まれなかったプロセスを、メンバシップ関数形が大きく異なるプロセスとして選択し、このプロセスグループから排除する排除処理を実行する。
【００８０】
ステップＳ３４では、集合Ｈｙ　に照らし合わせて、Ｈｙのプロセスグループに属さないプロセスを排除する。すなわち｛　ｍｋ（ｅ）　｜　ｋ　＝１　．．．　Ｐ　｝の内適当な数Ｌ個以上が　Ｈｙ　に含まれていれば、ｅ　はこのプロセスグループに含まれると判定し、そうでないならば　ｅ　をこのプロセスグループから排除する。この排除処理はＧ’ｙ　に含まれる全てのプロセスに対して行われる。
【００８１】
続いて、ステップＳ３５において、最終的なプロセスグループを決定する処理を実行する。すなわち、集合Ｇ’ｙのプロセスｅのうち、ステップＳ３４で排除されずに残ったプロセスからなる集合をＧｙとして決定する。この集合Ｇｙが図６のステップＳ２４によるプロセスグループ検証に合格した集合となる。
【００８２】
図６に戻って、ステップＳ２４において、未検査のグループラベルの有無を調べ、未検査のグループラベルが無い場合は処理を終了し、未検査のグループラベルが存在する場合はステップＳ２５に移行する。
【００８３】
ステップＳ２５において、未だ処理されていないグループラベルをグループラベル検査変数ｙに代入し、ステップＳ２２に移行する。以降、ステップＳ２４で未検査のグループラベルが無しと判定されるまで、ステップＳ２２〜Ｓ２５を繰り返す。
【００８４】
便宜的に儲けたグループラベル数は全部でＮｇ個であるが、ステップＳ２２〜Ｓ２５の処理によって全てのグループラベルに対して行われる。
【００８５】
図６に示した処理によって、各グループラベルにおける集合Ｇｙを規定した情報が通信密プロセスグループ情報Ｄ５となる。
【００８６】
図４に戻って、ステップＳ７において、プロセス再配置部６は通信密プロセスグループ情報Ｄ５に基づき、通信が密に行われているプロセスグループに応じてプロセスの実行プロセッサを再配置する。すなわち、同一グループに属するプロセスを分散並列計算機上の近傍、すなわち通信コストが低くなるような位置に再配置する。この再配置によって計算処理全体の実行が効率化される効果を奏する。
【００８７】
本実施の形態のクラスタリング装置は、メンバシップ関数共通化部３で共通化処理を実行した後、メンバシップ関数ランダム摂動部４によりランダム摂動処理を行うことにより、メンバシップ関数を引き離す力を内部的に発生させることにより、動的なクラスタ状態の変化に追随することが可能なメンバシップ関数を得ることができる。
【００８８】
したがって、プロセスグループ指定部５は、ランダム摂動処理後のメンバシップ関数に基づきクラスタ分類を正確に行うことができ、プロセス再配置部６によってプロセスの再配置を正確に行うことができる。
【００８９】
＜実施の形態２＞
次に、本発明の対象を時間的に継続して撮影したデータすなわち対象の動画像を元に、それぞれの画像において前時刻の処理結果を用いながら領域の切り分けを行い領域抽出を継続することで領域追跡を行う問題に適用した実施の形態２について述べる。
【００９０】
図８は領域抽出と追跡問題に関して対象となる入力動画像の典型的な例について示した図である。図８において、画像オブジェクト３０はある時刻に撮影された状態１の画像オブジェクトであり、画像オブジェクト３１，３２は状態１から時間経過２９の後の状態２の時に撮影された画像オブジェクトである。これら画像オブジェクト３０〜３２は共通の画像フレーム２８内に撮像される。
【００９１】
図８に示すように、画像オブジェクト３０が時間経過２９と共に画像フレーム２８内を右に移動したと同時に、二つに分裂することにより、画像オブジェクト３１，３２となる。すなわち、画像オブジェクト３１，３２の元が画像オブジェクト３０である。
【００９２】
本実施の形態に関する詳細を述べる前に、本実施の形態における画像領域追跡法の基本的な考え方や前提となる条件等について説明する。本実施の形態における動画像領域追跡法では、前時刻までの結果を基に変化に応じた画素の再クラスタリングを行う。
【００９３】
したがって、画像オブジェクト３０の段階でオブジェクト内の画素とその他の画素は領域抽出が行われ、画素ラベルとグループラベルを変数とするメンバシップ関数の形で領域情報が得られていたとする。すなわち、現在の時刻ｔに対し、直前の時刻（ｔ−１）において、全ての画素ラベルｅとグループラベル　ｃ　に対して、ｇｔ−１ｃ（ｅ）が得られていたとする。
【００９４】
このメンバシップ関数の表すクラスタリングは、同一画像オブジェクト内の画素が類似の関数形を共有することでクラスタを成し、その他の画素とは異なるクラスタに属すると判定されている。新たな入力画像があるとこれを適当な画像処理法によって処理し、その幾つかの画像領域について、それぞれに属する必ずしも画像領域全体ではない画素集合が入力情報として与えられるとする。画像オブジェクト画像領域抽出や追跡をおこなう画像処理には様々な手法が存在するが、本実施の形態は上記入力情報を提供する任意の画像処理法に関して適用される。画像領域抽出では、隣り合う画素が同一領域に属するか否かを判定しこれを拡大することを原理とする処理法が多くあるが、こうした方法はその多くがこの実施形態の適用範囲である。
【００９５】
本実施の形態での目標は、図８に示すような画像オブジェクトが分裂するなど画像領域に対応する画素のクラスタに時間的変化が起こったとき、クラスタリング処理結果があるべきクラスタに追従して元々は画像オブジェクト３０のようにまとまっていた画素クラスタを分けることである。
【００９６】
図９はこの発明の実施の形態２であるクラスタリング装置の構成を示すブロック図である。
【００９７】
画像集合入力部２１は画像処理によって同一画像領域に含まれる必ずしも画像領域全体ではない画素の集合を入力画像情報Ｄ１１として画像オブジェクト推定部２２に付与する。なお、入力画像情報Ｄ１１には適当な範囲のエラーが含まれていても構わない。
【００９８】
画像オブジェクト推定部２２は、入力画像情報Ｄ１１が属する画像オブジェクトを推定して画像領域情報Ｄ１２をメンバシップ関数共通化部２３に出力する。
【００９９】
メンバシップ関数共通化部２３は入力画像情報Ｄ１１及び画像領域情報Ｄ１２に基づき画像領域が持つ画素グループを表すメンバシップ関数を共通化して、共通化後のメンバシップ関数情報Ｄ１３をメンバシップ関数ランダム摂動部２４に出力する。
【０１００】
メンバシップ関数ランダム摂動部２４は、入力画像情報Ｄ１１及び画像領域情報Ｄ１２に基づき、決定される画像領域における各画素のメンバシップ関数（メンバシップ関数情報Ｄ１３によって規定）に摂動を加え、摂動処理後のメンバシップ関数情報Ｄ２４を得る。
【０１０１】
図１０は実施の形態２のクラスタリング装置によるクラスタリング方法の処理手順を示すフローチャートである。以下、図９及び図１０を参照してその処理手順を説明する。
【０１０２】
まず、ステップＳ４１において、画像集合入力部２１は画像処理によって同一画像領域に含まれる必ずしも画像領域全体ではない画素の集合を規定した入力画像情報Ｄ１１を画像オブジェクト推定部２２に付与する。
【０１０３】
入力画像情報Ｄ１１で規定される画像領域における画素の集合をΓ（ｔ）とする。同時刻に複数の領域に関する画素集合が外部から入力される場合もあるが、その場合は適当な順序を決めることができるので、ここでは、一般性を失うことなく、ある時刻に入力される画像領域に属する画素集合は一つであると仮定する。
【０１０４】
次に、ステップＳ４２において、画像オブジェクト推定部２２は入力画像情報Ｄ１１に基づき画像オブジェクトを推定する。すなわち、Γ（ｔ）が属する画像オブジェクトを推定し、その推定結果を画像領域情報Ｄ１２として得る。この処理は実施の形態１で述べた式（２）〜式（５）を実行することによって行われる。
【０１０５】
なお、実施の形態２おいて、式（１）〜式（５）等で用いるパラメータは以下の内容となる。画素全体の集合を「Ｅ」で表し、個々の画素を「ｅ」で表す。次に画像オブジェクトグループを表す便宜的なラベルを　「ｃ」としその全体を表す集合を「Ｇ」と表す。Ｎｇ　を便宜的なクラスタ数とする。画素「ｅ」がオブジェクトグループ「ｃ」に属する帰属度はメンバシップ関数　ｇｃ（ｅ）　で表す。
【０１０６】
そして、ステップＳ４３において、メンバシップ関数共通化部２３は入力画像情報Ｄ１１及び画像領域情報Ｄ１２に基づき、画像領域の各画素が持つ画像オブジェクトを表すメンバシップ関数を共通化して、共通化後のメンバシップ関数を規定したメンバシップ関数情報Ｄ１３を得る。
【０１０７】
メンバシップ関数共通化部２３は、メンバシップ関数を実施の形態１の式（６）及び式（７）を実行することにより、メンバシップ関数の共通化を実行する。
【０１０８】
ステップＳ４４において、メンバシップ関数ランダム摂動部２４は、入力画像情報Ｄ１１及び画像領域情報Ｄ１２に基づき入力画像の画素それぞれにおいて、メンバシップ関数情報Ｄ１３で規定されたメンバシップ関数にランダム摂動を加え、摂動処理後のメンバシップ関数を規定したメンバシップ関数情報を得る。
【０１０９】
すなわち、メンバシップ関数ランダム摂動部２４によって、画像領域を示すラベルを使って全てのΓ（ｔ）に含まれる画素　ｅ　に対して、実施の形態１で示した式（８）〜式（１１）を順次実行し、　ｇνＲ（ｅ）　の値と　ｇγ（ｅ）　の値を入れ替えを行う。
【０１１０】
この処理を、ステップＳ４１で新たなΓ（ｔ）が入力されるたびに行うことによって、同一の画像オブジェクトに属する画素のメンバシップ関数は共通の形を保ち続け、また、画像領域が分裂したような場合で分裂直後はメンバシップ関数が全て共通であっても、ステップＳ４４の効果により、画像オブジェクト３０が、画像オブジェクト３１，３２の様に分裂したことを外部から明示的に情報入力することなしに、自動的にそれぞれの画像領域毎に異なった形のメンバシップ関数が属する画素によって共有されるようになる。
【０１１１】
＜実施の形態３＞
実施の形態２では、外部から与えられる画素の集合は、それが元々どの領域のものであるかについては全く情報が与えられていなかった。これに対して、Γ（ｔ）を判定する元となった情報に、例えば図８において画素の輝度に基づく画像処理と画素の色に基づく画像処理が行われていて、それそれ独立に領域抽出が行われ、切り出された画素の集合Γ（ｔ）において、各画素には輝度による判定か或いは色による判定が情報として提供されているとする。
【０１１２】
この場合、図１０のステップＳ４３おいてメンバシップ関数の共通性の強化を、輝度か色かであらかじめ定めた、以下の式（１３）のような要素が“０”あるいは“１”からなる異なる向きのバイアスベクトルｂｉ（輝度対応）とｂｃ（色対応）をそれぞれ用意しておき、図１０のステップＳ４３におけるメンバシップ関数更新を、例えば以下の式（１４）のように、このバイアスベクトルを施すことによって、画素の判定基準が輝度か色かで共通化処理を異ならせることにより、効率的に分裂の検知を行うことが可能になる。
【０１１３】
【数１３】
2004102572.tif 000015
【０１１４】
【数１４】
2004102572.tif 000016
【０１１５】
ただし、式（１４）における「ｍ」は入力情報が輝度に基づく場合は　ｉ　で、色に基づく場合はｃを選ぶ。
【０１１６】
このように、実施の形態３のクラスタリング装置は、領域抽出の判断基準を考慮して部分集合の各画素に対する共通化処理を行うことにより、より精度の高い共通化処理が行える。
【０１１７】
＜実施の形態４＞
実施の形態１と実施の形態２及び実施の形態３とは全く異なる分野の動的クラスタリング問題に関する実施の形態であるが、その核心となる部分は同値の形を持っている。実施の形態４ではこの核心部分を抽出して説明する。
【０１１８】
図１１はこの発明の実施の形態４であるクラスタリング装置の構成を示すブロック図である。
【０１１９】
外部情報入力部４１はプロセス，画素等の物理的要素となりうるクラスタ要素の部分集合を示す外部入力情報Ｄ２１をクラスタ推定部４２に付与する。
【０１２０】
クラスタ推定部４２は、外部入力情報Ｄ２１で規定される部分集合が属するクラスタを推定してクラスタ推定情報Ｄ２２をメンバシップ関数共通化部４３に出力する。
【０１２１】
メンバシップ関数共通化部４３は外部入力情報Ｄ２１及びクラスタ推定情報Ｄ２２に基づき、外部入力情報Ｄ２１が規定した部分集合のクラスタ要素のグループを表すメンバシップ関数を共通化して、共通化後のメンバシップ関数情報Ｄ２３をメンバシップ関数ランダム摂動部４４に出力する。
【０１２２】
メンバシップ関数ランダム摂動部４４は、外部入力情報Ｄ２１、クラスタ推定情報Ｄ２２及びメンバシップ関数情報Ｄ２３に基づき、外部入力情報Ｄ２１によって規定される部分集合における各クラスタ要素のメンバシップ関数に摂動を加え、摂動処理後のメンバシップ関数情報Ｄ２４を得る。
【０１２３】
図１２は実施の形態４のクラスタリング装置によるクラスタリング方法の処理手順を示すフローチャートである。以下、図１１及び図１２を参照してその処理手順を説明する。
【０１２４】
本実施の形態における前提として、各時刻に一つ或いは複数の、その時刻に存在するクラスタの必ずしも全部ではないクラスタ要素のリスト（部分集合）が外部情報として提供されているとする。
【０１２５】
ステップＳ５１において、外部情報入力部４１はクラスタ要素の部分集合を規定した外部情報をクラスタ推定部４２に付与する。
【０１２６】
ステップＳ５２において、クラスタ推定部４２は外部入力情報Ｄ２１に基づき、部分集合中のクラスタ要素がどのクラスタに属するかを推定してクラスタ推定情報Ｄ２２を得る。
【０１２７】
そして、ステップＳ５３において、メンバシップ関数共通化部４３は外部入力情報Ｄ２１及びクラスタ推定情報Ｄ２２に基づき、ステップＳ４２で推定されたクラスタのへの帰属度がより強くなるように、部分集合内のクラスタ要素が持つクラスタを表すメンバシップ関数を共通化して、共通化後のメンバシップ関数を規定したメンバシップ関数情報Ｄ２３を得る。
【０１２８】
ステップＳ５４において、メンバシップ関数ランダム摂動部４４は、外部入力情報Ｄ２１、クラスタ推定情報Ｄ２２及びメンバシップ関数情報Ｄ２３に基づき、外部入力情報Ｄ２１で規定された部分集合のクラスタ要素それぞれにおいて、メンバシップ関数情報Ｄ２３で規定されたメンバシップ関数にランダム摂動（クラスタ推定情報Ｄ２２に基づきメンバシップ関数値を交換するグループを選択）を加え、摂動処理後のメンバシップ関数を規定したメンバシップ関数情報を得る。
【０１２９】
図１２で示すフローチャートのアルゴリズムを詳しく説明するために実施の形態１と共通の定義を使う。外部入力情報Ｄ２１において、各時刻に外部から提供されるあるクラスタの必ずしも全体ではないクラスタ要素の部分集合がΓ（ｔ）として規定される。すなわち、ステップＳ５１で与えられる外部情報で規定される部分集合がΓ（ｔ）に相当する。
【０１３０】
Γ（ｔ）を提供するものは図中に含まれないが、物理的現象を構成する要素であれば何であっても良い。実施の形態１ではプロセス間のデータ通信を行うプロセスの集合が与えられ、実施の形態２では画像処理における画像領域抽出によって得られた画像領域における画素の集合が与えられていたが、適用対象によって適した外部処理によってΓ（ｔ）を規定する外部情報が与えられる。Γ（ｔ）がどのクラスタのクラスタ要素からなるものであるかはΓ（ｔ）の他に提供されていても良いが、これが提供されていなくても良い。いずれにせよΓ（ｔ）とメンバシップ関数を元にその推定を行う。この処理がステップＳ５２に相当する。
【０１３１】
Γ（ｔ）が属するクラスタの推定は例えば式（２）〜（５）のように多数決によって行うことができる。これにより求められたＴＲを多数決で選ばれたΓ（ｔ）の元となるクラスタの推定結果とし、これを元にメンバシップ関数を式（６），（７）用に通り変更し、Γ（ｔ）に属するクラスタ要素のメンバシップ関数の共通化を行うプロセスがステップＳ５３である。
【０１３２】
ステップＳ５４で実行されるメンバシップ関数のランダム摂動はその詳細を図５で示したフローが共通に用いられる。その詳細も実施の形態１　で述べたものをそのまま使用できる。
【０１３３】
ステップＳ５１〜Ｓ５４の処理を、時々刻々与えられるΓ（ｔ）毎に適用することでメンバシップ関数　ｇｃ（ｅ）　は、クラスタ要素が存在すると、それぞれのグループに属するクラスタ要素は、グループ（クラスタ）毎に幾つかの共通のクラスタラベル　ｃ　に対して　ｇｃ（ｅ）　が“０”よりも充分大きな値をとり、このクラスタに所属しない要素に関して　ｇｃ（ｅ）　は“０”に近い値を取るようになる。
【０１３４】
この結果に、クラスタ要素のクラスタ状態が明示的に表される。このクラスタリング結果は、たとえクラスタ状態に動的変化が起こり、例えばクラスタが新規に生成したり、既存のクラスタが分裂したり、あるいは処理結果の誤りなどの理由から、一時的に本来異なるクラスタに属するクラスタ要素が同一クラスタにあると判定されたとしても、ランダム摂動の効果によって異なるクラスタに属するクラスタ要素のメンバシップ関数がその共通性を奪われるため、自動的に正しいクラスタリングをあらわす結果に遷移する。
【０１３５】
図１３は実施の形態４のクラスタリング装置によるクラスタ分類のシミュレーション結果を示すグラフである。同図において、期間０〜１０００及び２０００以降の時間帯が２のクラスタが存在している期間、期間１０００〜２０００の時間帯が１のクラスタ存在している期間である。
【０１３６】
同図に示すように、ランダム摂動処理を行わない従来のクラスタリング装置によって検出されるクラスタ間距離Ｌ０は、期間２０００以降のクラスタ数の１→２の変化に追随できず、“０”近傍（すなわち、クラスタ数１と認識）となっている。一方、ランダム摂動処理を行う実施の形態４のクラスタリング装置によって検出されるクラスタ間距離Ｌ１は、期間２０００以降のクラスタ数の１→２の変化に追随して、比較的大きな値を示している。なお、クラスタ間距離とは、初期状態の２つのクラスタ（グループ）それぞれに属する物理的要素のメンバシップ関数のクラスタ平均同士の距離であり、クラスタ間距離が大きいと両者は異なるグループであることを示し、“０”に近いと両者は異なるグループであることを示す。
【０１３７】
上述したシミュレーション結果から明らかなように、実施の形態４のクラスタリング装置は、クラスタ数の２→１→２の変化に追随したクラスタ分類を行うことができる。
【０１３８】
【発明の効果】
以上説明したように、この発明における請求項１記載のクラスタリング装置はメンバシップ関数共通化部で共通化処理を実行した後、メンバシップ関数ランダム摂動部によりランダム摂動処理を行うことにより、メンバシップ関数を引き離す力を内部的に発生させることにより、動的なクラスタ状態の変化に追随することが可能なメンバシップ関数を得ることができる。
【０１３９】
請求項２記載のクラスタリング装置のクラスタ分類決定部はランダム摂動処理後のメンバシップ関数に基づきクラスタ分類を正確に行う行うことができる。
【０１４０】
請求項３記載のクラスタリング装置は、推定グループのうちの一のグループの位置を吸引力があると同時に上位の位置に上がっていく障壁とすることができ、その結果、クラスタ状態の時間的変化を正確に検知なメンバシップ関数を得ることができる。
【０１４１】
請求項４記載のクラスタリング装置は、複数のプロセスのクラスタ分類を正確に行うことができる。
【０１４２】
請求項５記載のクラスタリング装置は、動画像を構成する複数の画素のクラスタ分類を正確に行うことができる。
【０１４３】
請求項６記載のクラスタリング装置は、判断基準を考慮して部分集合の各画素に対する共通化処理を行うことにより、より精度の高い共通化処理が行える。
【０１４４】
この発明における請求項７記載のクラスタリング方法は、ステップ（ｃ）　で共通化処理を実行した後、ステップ（ｄ）　でランダム摂動処理を行うことにより、メンバシップ関数を引き離す力を内部的に発生させることにより、動的なクラスタ状態の変化に追随することが可能なメンバシップ関数を得ることができる。
【図面の簡単な説明】
【図１】この発明の実施の形態１であるクラスタリング装置の構成を示すブロック図である。
【図２】状態１におけるプロセルグループを示す説明図である。
【図３】状態１から所定時間経過後の状態２におけるプロセスグループを示す説明図である。
【図４】実施の形態１のクラスタリング装置によるクラスタリング方法の処理手順を示すフローチャートである。
【図５】図４のステップＳ５の処理の詳細を示すフローチャートである。
【図６】図４のステップＳ６の処理の詳細を示すフローチャートである。
【図７】多数決計算を元にＧ’ｙ　からメンバシップ関数形が大きく異なるプロセスを取り除くステップＳ２３の処理を詳細に示したフローチャートである。
【図８】領域抽出と追跡問題に関して対象となる入力動画像の典型的な例について示した図である。
【図９】この発明の実施の形態２であるクラスタリング装置の構成を示すブロック図である。
【図１０】実施の形態２のクラスタリング装置によるクラスタリング方法の処理手順を示すフローチャートである。
【図１１】この発明の実施の形態４であるクラスタリング装置の構成を示すブロック図である。
【図１２】実施の形態４のクラスタリング装置によるクラスタリング方法の処理手順を示すフローチャートである。
【図１３】実施の形態４のクラスタリング装置によるシミュレーション結果を示すグラフである。
【図１４】例えば特開２００１−２８３１８４（特願２０００−９１８６３）に開示された、従来のクラスタリング装置を示したブロック図である。
【符号の説明】
１　通信プロセス検知部、２　通信グループ推定部、３，２３，４３　メンバシップ関数共通化部、４，２４，４４　メンバシップ関数ランダム摂動部、５　プロセスグループ指定部、６　プロセス再配置部、２１　画像集合入力部、２２画像領域推定部、４１　外部情報入力部、４２　クラスタ推定部。
【図１】
2004102572.tif 000017
【図２】
2004102572.tif 000018
【図３】
2004102572.tif 000019
【図４】
2004102572.tif 000020
【図５】
2004102572.tif 000021
【図６】
2004102572.tif 000022
【図７】
2004102572.tif 000023
【図８】
2004102572.tif 000024
【図９】
2004102572.tif 000025
【図１０】
2004102572.tif 000026
【図１１】
2004102572.tif 000027
【図１２】
2004102572.tif 000028
【図１３】
2004102572.tif 000029
【図１４】
2004102572.tif 000030