(57)【特許請求の範囲】
【請求項１】
隣接行列が定義できるデータ、指定されたクラスタ数およびパラメータを入力とし、該入力データを前記クラスタ数およびパラメータによってクラスタリングするデータの領域分割装置であって、
前記入力データの隣接関係から推移行列を計算する推移行列計算手段と、
前記推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算手段と、
前記ランダムウォーク特徴量からデータ間の類似度を計算する類似度計算手段と、
前記データ間の類似度から初期クラスタを生成する初期クラスタ生成手段と、
前記初期クラスタを前記指定されたクラスタ数に統合するクラスタ統合手段と、を備えたことを特徴とするデータの領域分割装置。
【請求項２】
前記入力されたパラメータを組み合わせてパラメータのバリエーションを生成するパラメータバリエーション生成手段と、
前記生成されたパラメータのバリエーション毎に前記領域分割装置がクラスタリングを行なった結果を、各々評価するクラスタ評価手段と、を備えたことを特徴とする請求項１に記載のデータの領域分割装置。
【請求項３】
前記クラスタ評価手段は、クラスタの境界数を評価値として計算するか、又は前記ランダムウォーク特徴量計算手段により計算されたランダムウォーク特徴量をクラスタ単位に集約して求めたクラスタ間の近接性を用いて、異なるクラスタとの近接性の平均を評価値として計算するか、又は前記クラスタ間の近接性を用いて自クラスタから他クラスタへの近接性の総和を評価値として計算することを特徴とする請求項２に記載のデータの領域分割装置。
【請求項４】
前記ランダムウォーク特徴量計算手段は、ランダムウォークにより初めてデータのノードｉからノードｊに到達する時刻をランダムウォーク特徴量として計算し、
前記類似度計算手段は、前記ランダムウォーク特徴量である前記初めてノードｉからノードｊに到達する時刻からデータ間の類似度を計算し、
前記クラスタ評価手段は、前記ランダムウォーク特徴量である前記初めてノードｉからノードｊに到達する時刻をクラスタ単位に集約して求めたクラスタ間の遠隔性を用いて、自クラスタの遠隔性の総和を評価値として計算することを特徴とする請求項２に記載のデータの領域分割装置。
【請求項５】
隣接行列が定義できるデータ、指定されたクラスタ数およびパラメータを入力とし、該入力データを前記クラスタ数およびパラメータによってクラスタリングするデータの領域分割方法であって、
データ入力手段が、隣接行列が定義できるデータ、指定されたクラスタ数およびパラメータの入力を受け付けるデータ入力ステップと、
推移行列計算手段が、前記入力データの隣接関係から推移行列を計算する推移行列計算ステップと、
ランダムウォーク特徴量計算手段が、前記推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算ステップと、
類似度計算手段が、前記ランダムウォーク特徴量からデータ間の類似度を計算する類似度計算ステップと、
初期クラスタ生成手段が、前記データ間の類似度から初期クラスタを生成する初期クラスタ生成ステップと、
クラスタ統合手段が、前記初期クラスタを前記指定されたクラスタ数に統合するクラスタ統合ステップと、を備えたことを特徴とするデータの領域分割方法。
【請求項６】
パラメータバリエーション生成手段が、前記入力されたパラメータを組み合わせてパラメータのバリエーションを生成するパラメータバリエーション生成ステップを実行し、
前記生成されたパラメータのバリエーション毎に、前記推移行列計算ステップ、ランダムウォーク特徴量計算ステップ、類似度計算ステップ、初期クラスタ生成ステップおよびクラスタ統合ステップを実行してクラスタリングを実施し、
クラスタ評価手段が、前記パラメータのバリエーション毎のクラスタリング結果を各々評価するクラスタ評価ステップを実行する、ことを特徴とする請求項５に記載のデータの領域分割方法。
【請求項７】
前記クラスタ評価ステップは、クラスタの境界数を評価値として計算するか、又は前記ランダムウォーク特徴量計算手段により計算されたランダムウォーク特徴量をクラスタ単位に集約して求めたクラスタ間の近接性を用いて、異なるクラスタとの近接性の平均を評価値として計算するか、又は前記クラスタ間の近接性を用いて自クラスタから他クラスタへの近接性の総和を評価値として計算することを特徴とする請求項６に記載のデータの領域分割方法。
【請求項８】
前記ランダムウォーク特徴量計算ステップは、ランダムウォークにより初めてデータのノードｉからノードｊに到達する時刻をランダムウォーク特徴量として計算し、
前記類似度計算ステップは、前記ランダムウォーク特徴量である前記初めてノードｉからノードｊに到達する時刻からデータ間の類似度を計算し、
前記クラスタ評価ステップは、前記ランダムウォーク特徴量である前記初めてノードｉからノードｊに到達する時刻をクラスタ単位に集約して求めたクラスタ間の遠隔性を用いて、自クラスタの遠隔性の総和を評価値として計算することを特徴とする請求項６に記載のデータの領域分割方法。
【請求項９】
コンピュータを請求項１ないし４のいずれか１項に記載の各手段として機能させるデータの領域分割プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング手法に関し、特に画像を重なりのない領域に分割する画像領域分割手法に関する。
【背景技術】
【０００２】
従来、画像領域分割手法として、非特許文献１に示すように連結成分ラベリングという手法があった。連結成分ラベリングは、線画や一般画像から抽出されたエッジ画像等の２値画像を入力として、線やエッジ等の境界で隔てられた連続した領域を抽出する。
【０００３】
連結成分ラベリングに入力される２値画像は下記の形式である。
【０００４】
【数１】
0005385313.tif 000002
【０００５】
連結成分ラベリングの手法は下記表１の「Ａｌｇｏｒｉｔｈｍ  １  連結成分ラベリング」のステップ１〜ステップ３８のように実施される。
【０００６】
【表１】
0005385313.tif 000003
【０００７】
ここで、図５に示す画像データ（画像１）が入力されたとする。図５において、白いピクセルが領域、黒いピクセルが境界であり、四角形を形成する境界が領域を内側と外側に分離している。
【０００８】
この場合、図５の画像データに対する連結成分ラベリング結果は図６（結果１）となり、図５の境界部分は０、外側の領域は１、内側の領域は２のラベルが付与される。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】田村秀行、「コンピュータ画像処理」、オーム社、２００２年１２月、第５章  ２値画像処理、ｐｐ．１４９−１５０
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述した連結成分ラベリングでは、４近傍で連結したピクセルを一つの領域とするので、境界が完全に連結していないと領域を分離することができない。
【００１１】
例えば、図７（画像２）の入力画像データのように境界がとぎれていると、連結成分ラベリング結果は、図８（結果２）のように外側と内側の領域がつながってしまい適切な領域分割ができない。
【００１２】
本発明は上記問題を解決するものであり、その目的は、点線による線画、閉じていない隙間の空いた線画、ノイズを含む画像やぼやけた画像のエッジ抽出結果など、完全に連結していない境界を持つ画像に対しても適切に領域を分割することができるデータの領域分割装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００１３】
上記課題を解決するための本発明のデータの領域分割装置は、隣接行列が定義できるデータ、指定されたクラスタ数およびパラメータを入力とし、該入力データを前記クラスタ数およびパラメータによってクラスタリングするデータの領域分割装置であって、前記入力データの隣接関係から推移行列を計算する推移行列計算手段と、前記推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算手段と、前記ランダムウォーク特徴量からデータ間の類似度を計算する類似度計算手段と、前記データ間の類似度から初期クラスタを生成する初期クラスタ生成手段と、前記初期クラスタを前記指定されたクラスタ数に統合するクラスタ統合手段と、を備えたことを特徴としている。
【００１４】
さらに、前記入力されたパラメータを組み合わせてパラメータのバリエーションを生成するパラメータバリエーション生成手段と、前記生成されたパラメータのバリエーション毎に前記領域分割装置がクラスタリングを行なった結果を、各々評価するクラスタ評価手段と、を備えたことを特徴としている。
【発明の効果】
【００１５】
（１）請求項１〜９に記載の発明によれば、入力データの領域を適切に分割することができる。例えば画像データの場合、点線による線画、閉じていない隙間の空いた線画、ノイズを含む画像やぼやけた画像のエッジ抽出結果など、完全に連結していない境界を持つ画像に対しても適切に領域を分割することができる。
（２）請求項２、６に記載の発明によれば、生成されたクラスタを評価することにより、入力したデータおよびクラスタ数に対してパラメータの最適化を行なうことができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施例１の装置構成を示すブロック図。
【図２】図１の装置が行なう処理のフローチャート。
【図３】本発明の実施例２の装置構成を示すブロック図。
【図４】図３の装置が行なう処理のフローチャート。
【図５】境界が完全に連結している画像１の説明図。
【図６】図５の画像１に対して連結成分ラベリングを行なった結果１の説明図。
【図７】境界がとぎれている画像２の説明図。
【図８】図７の画像２に対して連結成分ラベリングを行なった結果２の説明図。
【図９】本発明の実施例１において入力される画像３の説明図。
【図１０】本発明の実施例１における、図９の画像３に対するノード番号付与のようすを示す説明図。
【図１１】本発明の実施例１における、図９の画像３について作成された隣接行列のようすを示す説明図。
【図１２】本発明の実施例１における、図９の画像３について作成された推移行列のようすを示す説明図。
【図１３】本発明の実施例１における、図９の画像３について計算されたランダムウォーク特徴量のようすを示す説明図。
【図１４】画像データにおける、ノード１、２間の最短距離の説明図。
【図１５】画像データにおける、境界を迂回できる場合のノード１、２間の最短距離の説明図。
【図１６】本発明におけるランダムウォーク特徴量の説明図。
【図１７】本発明における、境界がある場合のランダムウォーク特徴量の説明図。
【図１８】本発明の実施例１において計算された、図９の画像３の類似度行列の説明図。
【図１９】本発明の実施例１における類似度計算の第１の説明図。
【図２０】本発明の実施例１における類似度計算の第２の説明図。
【図２１】本発明の実施例１における類似度計算の第３の説明図。
【図２２】本発明の実施例１において生成された、図９の画像３の初期クラスタの説明図。
【図２３】本発明の実施例１において生成された、図９の画像３のクラスタ統合結果の説明図。
【図２４】本発明の実施例２におけるバリエーション１についてのクラスタ統合結果の説明図。
【図２５】本発明の実施例２におけるバリエーション２についてのクラスタ統合結果の説明図。
【図２６】本発明の実施例２におけるバリエーション３についてのクラスタ統合結果の説明図。
【発明を実施するための形態】
【００１７】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。以下の実施例１〜５は、本発明を画像データのクラスタリングに適用した例を示している。
【実施例１】
【００１８】
図１は実施例１の画像領域分割装置の構成を示し、図２は図１の各部が行なう処理のフローチャートを示している。
【００１９】
まず、実施例１の概略を説明する。本実施例１の画像領域分割装置は、入力部１０１、推移行列計算手段としての推移行列計算部１０２、ランダムウォーク特徴量計算手段としてのランダムウォーク特徴量計算部１０３、類似度計算手段としての類似度計算部１０４、初期クラスタ生成手段としての初期クラスタ生成部１０５、クラスタ統合手段としてのクラスタ統合部１０６および出力部１０７を備えている。
【００２０】
入力部１０１は、ネットワーク又はファイルなどから、例えば装置の利用者が指定した２値画像と、パラメータ、すなわちクラスタ数、初期クラスタ生成部１０５において使用する固有ベクトル数（射影する部分空間の次元数）、ランダムウォークのリスタート率、類似度計算のパラメータなどを入力する（ステップＳ１０１）。
【００２１】
推移行列計算部１０２は、入力部１０１により入力された画像データの隣接関係から推移行列を計算する（ステップＳ１０２）。
【００２２】
ランダムウォーク特徴量計算部１０３は、前記計算された推移行列からランダムウォーク特徴量を計算する（ステップＳ１０３）。
【００２３】
類似度計算部１０４は、前記計算されたランダムウォーク特徴量からデータ間の類似度を計算する（ステップＳ１０４）。
【００２４】
初期クラスタ生成部１０５は、前記計算されたデータ間の類似度から初期クラスタ（後述の初期クラスタインデックスｇ0）を生成する（Ｓ１０５）。
【００２５】
クラスタ統合部１０６は、前記生成された初期クラスタを前記指定されたクラスタ数に統合して後述のクラスタインデックスｇを求める（ステップＳ１０６ａ，Ｓ１０６ｂ）。
【００２６】
出力部１０７は、前記クラスタの統合により得られたクラスタインデックスｇを、ネットワーク又はファイルなどに出力する（ステップＳ１０７）。
【００２７】
図１の画像領域分割装置は、例えばコンピュータにより構成され、通常のコンピュータのハードウェアリソース、例えばＲＯＭ，ＲＡＭ，ＣＰＵ、入力装置、出力装置、通信インターフェース、ハードディスク、記録媒体およびその駆動装置を備えている。また、図示省略のネットワークやファイルと接続可能に構成されている。
【００２８】
このハードウェアリソースとソフトウェアリソース（ＯＳ、アプリケーションなど）との協働の結果、本画像領域分割装置は、図１に示すように、入力部１０１、推移行列計算部１０２、ランダムウォーク特徴量計算部１０３、類似度計算部１０４、初期クラスタ生成部１０５、クラスタ統合部１０６および出力部１０７を実装する。
【００２９】
次に、上記のように構成された装置の詳細を説明する。本実施例１では、２値画像ｆ(ｙ，ｘ)，１≦ｘ≦ｗｉｄｔｈ，１≦ｙ≦ｈｅｉｇｈｔ、クラスタ数Ｋ、部分空間の次元数（使用する固有ベクトル数）Ｃ、ランダムウォークのリスタート率β、類似度計算のパラメータσを入力とし、Ｋ個のクラスタに分割したクラスタインデックスを出力する。
【００３０】
入力部１０１には、ステップＳ１０１において、ネットワーク又はファイルなどから、例えば装置の利用者が指定した２値画像ｆ、クラスタ数Ｋ、使用する固有ベクトル数Ｃ、ランダムウォークのリスタート率β、類似度計算のパラメータσが入力される。
【００３１】
例えば図９の画像データ（画像３）およびＫ＝２、Ｃ＝２、σ＝５０が入力される。
【００３２】
次に推移行列計算部１０２は、ステップＳ１０２において推移行列の計算を行なう。
【００３３】
まず、２値画像ｆから領域ピクセルを取り出し、ノード番号を付ける。例えば図９の画像の領域部分を図１０のように、左上から順にノード番号を付ける。ノード(領域ピクセル)の数をＮとする。
【００３４】
次に、ノードｉとｊが隣接しているかどうかを示す隣接行列Ａを
【００３５】
【数２】
0005385313.tif 000004
【００３６】
とする。すなわちノードｉ，ｊが隣接しているときは１とし、隣接していないときは０として図１１のように隣接行列を作成する。
【００３７】
そして図１１の隣接行列を各行の要素の総和が１になるように正規化して、図１２のように推移行列Ｐを作成する。
【００３８】
推移行列Ｐは
【００３９】
【数３】
0005385313.tif 000005
【００４０】
となる。
【００４１】
次にランダムウォーク特徴量計算部１０３は、ステップＳ１０３において、リスタートありランダムウォークでランダムウォーク特徴量を計算する。
【００４２】
リスタートありランダムウォークは次式で示される。
【００４３】
ｒj＝（１−β）Ｐｒj＋βｅj    （４）
ここで、βはリスタート率であり、本実施形態ではβ＝０．０５の値を用いるが、この値に限るものではない。
【００４４】
また、ｅjはｊ番目の要素のみ１の列ベクトル、すなわち、
【００４５】
【数４】
0005385313.tif 000006
【００４６】
ここで、・Tは転置。
【００４７】
ｒjは下記の連立方程式で得られる。
【００４８】
（Ｉn−（１−β）Ｐ）ｒj＝βｅj    （６）
ここで、Ｉnはｎ次元の単位行列。
【００４９】
この式（６）をガウスの消去法等を用いて、ｒj，ｊ＝１，・・・ｎを図１３のように計算する。
【００５０】
ランダムウォーク特徴量Ｒは下記の式（７）のようになる：
【００５１】
【数５】
0005385313.tif 000007
【００５２】
上記式（７）中の添字のｒiはＲのｉ行目の行ベクトルである。
【００５３】
ランダムウォーク特徴量計算部１０３は、境界によって領域ピクセル間の往来が阻害される度合いを計算することで領域ピクセル間の隔たりを適切に評価する。例えば４近傍での最短距離(市街地距離)ではノード１と２の間の最短経路は図１４のようになる。
【００５４】
尚、以下の図１４〜図２１における○囲み数字１〜○囲み数字４は、ノード１〜ノード４を示すものである。
【００５５】
境界があっても、図１５のように迂回できる場合は距離が変わらないため、境界の影響を評価できない。これに対して本発明のランダムウォーク特徴量計算部１０３により求めるランダムウォーク特徴量Ｒは、図１６のように、ノード１と２の全ての経路を考慮する。このため、境界があると図１７のように、いくつかの経路が阻害され、境界の影響を評価できる。
【００５６】
次に類似度計算部１０４は、ステップＳ１０４において、データ間の類似度、すなわちノードｕとｖの類似度を下記のように計算する。
【００５７】
ｋuv＝ｅｘｐ{−σ‖ｒu−ｒv‖1}    （８）
ここで、‖・‖はｌ1距離。
【００５８】
また、類似度行列Ｋを
【００５９】
【数６】
0005385313.tif 000008
【００６０】
とする。
【００６１】
例えば図１０の画像３の類似度行列は図１８のようになる。
【００６２】
上記のように、本発明の類似度計算部１０４では、２つの領域ピクセル間の類似度を２者間の隔たりだけでなく、他の領域との隔たりを含めて計算している。ある領域が他の領域の内側にある場合は、外側の領域では内側の領域の影響でピクセル間の隔たりが大きくなる。しかし、他の領域との隔たりを含めて計算することで、外側の領域は内側の領域と隔たっているという共通の特徴ができ、外側の領域を一つにまとめることを可能とする。
【００６３】
例えば、図１９のような場合、境界の影響でノード２(内側)とノード１，３，４(外側)は遠いと判定できるが、ノード１とノード４も遠いと判定されてしまう。そこで、４つのノード間の関係を図２０のように特徴量とする。ノード間の類似度をこの特徴量で比較すると、図２１のように、ノード２とノード１，３，４の間では共通部分が１以下、ノード１，３，４の間では共通部分が２以上となる。
【００６４】
次に初期クラスタ生成部１０５は、ステップＳ１０５において、ノードｉ＝１・・・，ｎを非線型変換φ（・）で高次元空間に写像し、分散が最大となる部分空間に射影する。
【００６５】
部分空間への射影は次式で与えられる：
ｚ（ｒi）＝φ（ｒi）Tｗ＋ｂ    （１０）
分散の最大化は：
【００６６】
【数７】
0005385313.tif 000009
【００６７】
ここで、γ＞０は定数。
【００６８】
また、
【００６９】
【数８】
0005385313.tif 000010
【００７０】
類似度と非線型変換に下記の式（１３）の関係があるので、
ｋij＝φ（ｒi）Tφ（ｒj）    （１３）
【００７１】
【数９】
0005385313.tif 000011
【００７２】
これによって、固有値の降順にＣ個の固有値および固有ベクトルが、例えば表２、表３のように求められる。
【００７３】
【表２】
0005385313.tif 000012
【００７４】
【表３】
0005385313.tif 000013
【００７５】
次にＣ個の固有ベクトルを並べて、部分空間への射影を得る：
【００７６】
【数１０】
0005385313.tif 000014
【００７７】
すなわち、ノードｉの部分空間の射影は下記のようになる:
ｚi＝（αi1，・・・，αiC）    （１９）
初期クラスタインデックスｇ0は下記のように求める：
【００７８】
【数１１】
0005385313.tif 000015
【００７９】
これによって、図９の画像（画像３）の初期クラスタは図２２のように生成され、表４のような初期クラスタインデックスｇ0が求められる。
【００８０】
【表４】
0005385313.tif 000016
【００８１】
次にクラスタ統合部１０６は、ステップＳ１０６ａ，１０６ｂにおいて、下記の表５のＡｌｇｏｒｉｔｈｍ２  ｍｅｒｇｅ  ｃｌｕｓｔｅｒのステップ１〜ステップ１９に従ってクラスタ候補を統合する。
【００８２】
【表５】
0005385313.tif 000017
【００８３】
【数１２】
0005385313.tif 000018
【００８４】
である。
【００８５】
前記表５のＡｌｇｏｒｉｔｈｍ２のステップ１〜１０の結果、候補ラベルテーブル、統合テーブルは、各々表６、表７となる。
【００８６】
【表６】
0005385313.tif 000019
【００８７】
【表７】
0005385313.tif 000020
【００８８】
続いて、Ａｌｇｏｒｉｔｈｍ２のステップ１１，１２の結果、候補クラスタの情報は表８となる。
【００８９】
【表８】
0005385313.tif 000021
【００９０】
Ｎcand（＝３）＞Ｋ（＝２）なのでクラスタを統合する。
【００９１】
μu・μv，ｕ，ｖ＝１，２，３の値は下記となる：
【００９２】
【数１３】
0005385313.tif 000022
【００９３】
最大値を持つクラスタ候補２，３を統合し、番号が小さいクラスタ候補２のクラスタベクトルとノード数を更新し、クラスタ候補３を削除する。
【００９４】
統合後のクラスタ候補、及び統合テーブルは、表９、表１０となる。
【００９５】
【表９】
0005385313.tif 000023
【００９６】
【表１０】
0005385313.tif 000024
【００９７】
このように、クラスタ候補がＫ（＝２）となった（ステップＳ１０６ｂの判定結果がｙｅｓとなった）ので統合を終了する。
【００９８】
次に、下記表１１のＡｌｇｏｒｉｔｈｍ３  ｒｅｎｕｍｂｅｒのステップ１〜ステップ２３に従ってクラスタインデックスｇを作成する。
【００９９】
【表１１】
0005385313.tif 000025
【０１００】
これによって、図９の画像（画像３）のクラスタは図２３のように生成され、表１２のようなクラスタインデックスｇが作成される。
【０１０１】
【表１２】
0005385313.tif 000026
【０１０２】
次に出力部１０７は、ステップＳ１０７において、ネットワーク、またはファイルなどに、前記作成されたクラスタインデックスｇを出力する。
【実施例２】
【０１０３】
図３は実施例２の画像領域分割装置の構成を示し、図４は図３の各部が行なう処理のフローチャートを示している。図３において図１と同一部分は同一符号をもって示している。
【０１０４】
本実施例２（図３）において実施例１（図１）と異なる点は、前記入力されたパラメータを組み合わせてパラメータのバリエーションを生成するパラメータバリエーション生成手段としてのパラメータバリエーション生成部２０２と、前記生成されたパラメータのバリエーション毎に前記領域分割装置（推移行列計算部１０２、ランダムウォーク特徴量計算部１０３、類似度計算部１０４、初期クラスタ生成部１０５、クラスタ統合部１０６）がクラスタリングを行なった結果を、各々評価するクラスタ評価手段としてのクラスタ評価部２０４とを備え、入力部２０１および出力部２０５の構成を変更した点にある。
【０１０５】
図３の装置も、前記図１と同様に例えばコンピュータにより構成され、通常のコンピュータのハードウェアリソースとソフトウェアリソースとの協働の結果、実施例２の画像領域分割装置は図３に示すように、入力部２０１、推移行列計算部１０２、ランダムウォーク特徴量計算部１０３、類似度計算部１０４、初期クラスタ生成部１０５、クラスタ統合部１０６、パラメータバリエーション生成部２０２、クラスタ評価部２０４および出力部２０５を実装する。
【０１０６】
まず入力部２０１には、ステップＳ２０１において、ネットワーク又はファイルなどから、例えば装置の利用者が指定した２値画像ｆ、クラスタ数、ランダムウォークのリスタート率、類似度計算のパラメータの候補σ、使用する固有ベクトル数Ｃ（式（２５））が入力される。
【０１０７】
σ＝{σ1，・・・，σNσ}
Ｃ＝{Ｃ1，・・・，ＣNC}      （２５）
例えば図７の画像データ、クラスタ数Ｋ＝２、パラメータの候補σ＝{５，５０，５００}、Ｃ＝{２}が入力される。
【０１０８】
次にパラメータバリエーション生成部２０２は、ステップＳ２０２において、パラメータ候補を組み合わせて、Ｎσ×ＮC個のバリエーションを例えば表１３のように作成する。
【０１０９】
【表１３】
0005385313.tif 000027
【０１１０】
次にステップＳ２０３において、指定したパラメータによる領域分割がなされる。このステップＳ２０３では、推移行列計算部１０２、ランダムウォーク特徴量計算部１０３、類似度計算部１０４、初期クラスタ生成部１０５およびクラスタ統合部１０６が前記図１、図２で述べた処理を行って、表１３のバリエーション１，２，３についてクラスタインデックスを計算し、各々図２４、図２５、図２６の結果が得られる。
【０１１１】
次にクラスタ評価部２０４が、ステップＳ２０４ａ，Ｓ２０４ｂにおいて、前記クラスタ統合部１０６により求められた、バリエーション１，２，３の各クラスタインデックスについて、評価値としてクラスタの境界数ｂｌｅｎを、下記式（２６）により計算し、出力部２０５が、ｂｌｅｎを最小とする結果を返す（出力する）（ステップＳ２０５）。
【０１１２】
【数１４】
0005385313.tif 000028
【０１１３】
すなわち、式（２６）に従ってバリエーション１，２，３の評価値ｂｌｅｎを表１４のように計算し、ｂｌｅｎが最小となるバリエーション２の結果（図２５)を出力する。
【０１１４】
【表１４】
0005385313.tif 000029
【実施例３】
【０１１５】
本実施例３では、クラスタ評価部２０４以外の構成は実施例２（図３、図４）と同一である。この実施例３におけるクラスタ評価部２０４は、実施例２のように、評価値としてクラスタ境界数ｂｌｅｎ（式（２６））を求めることに代えて、以下の処理を行なう。
【０１１６】
前記式（７）のランダムウォーク特徴量Ｒをクラスタ単位に集約して、クラスタ間の近接性ｓijを次の式（２７）のように計算する：
【０１１７】
【数１５】
0005385313.tif 000030
【０１１８】
そして異なるクラスタとの近接性の平均を評価値ｒｏｆｆとする：
【０１１９】
【数１６】
0005385313.tif 000031
【０１２０】
この式（２８）のｒｏｆｆを最小とするクラスタリングを選択する。
【実施例４】
【０１２１】
本実施例４では、クラスタ評価部２０４以外の構成は実施例２（図３、図４）と同一である。この実施例４におけるクラスタ評価部２０４は、実施例２のように、評価値としてクラスタ境界数ｂｌｅｎ（式（２６））を求めることに代えて、以下の処理を行なう。
【０１２２】
前記式（２７）でクラスタ間の近接性ｓijを計算する。そして自クラスタから他クラスタへの近接性の総和を評価値ｒｃｕｔとする：
【０１２３】
【数１７】
0005385313.tif 000032
【０１２４】
この式（２９）のｒｃｕｔを最小とするクラスタリングを選択する。
【実施例５】
【０１２５】
本実施例５では、ランダムウォーク特徴量計算部１０３、類似度計算部１０４、クラスタ評価部２０４以外の構成は実施例２（図３、図４）と同一である。この実施例５におけるランダムウォーク特徴量計算部１０３は、前記ランダムウォーク特徴量Ｒ（式（７））に代えて、初めてノードｉからノードｊに到達する時刻ｈｉｔｔｉｎｇ  ｔｉｍｅｓ  ｈijを式（３０）、（３１）のようにランダムウォーク特徴量とする：
【０１２６】
【数１８】
0005385313.tif 000033
【０１２７】
ここで、πは推移行列の定常分布、すなわち下記の方程式の解。
【０１２８】
πＰ＝π      （３２）
また、
Ｚ＝（Ｉn−（Ｐ−Π））-1      （３３）
さらに、
【０１２９】
【数１９】
0005385313.tif 000034
【０１３０】
である。
【０１３１】
そして類似度計算部１０４は、ｈuとｈvの類似度を下記の式（３５）のように計算する。
【０１３２】
【数２０】
0005385313.tif 000035
【０１３３】
そしてクラスタ評価部２０４は、式（３０）のランダムウォーク特徴量をクラスタ単位に集約して、クラスタ間の遠隔性ｓij´を下記の式（３６）のように計算する：
【０１３４】
【数２１】
0005385313.tif 000036
【０１３５】
そして自クラスタの遠隔性の総和を評価値ｒｃｕｔ’とする：
【０１３６】
【数２２】
0005385313.tif 000037
【０１３７】
この式（３７）のｒｃｕｔ’を最小とするクラスタリングを選択する。
【０１３８】
尚、本発明は隣接行列が定義できるデータに対して適用が可能であり、画像以外のデータのクラスタリングを行なうこともできる。
【０１３９】
また、本実施形態のデータの領域分割装置における各手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、本実施形態のデータの領域分割方法における手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えばＦＤ（Ｆｌｏｐｐｙ（登録商標）  Ｄｉｓｋ）や、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｋ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、メモリカード、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ）−ＲＯＭ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＨＤＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【符号の説明】
【０１４０】
１０１，２０１…入力部
１０２…推移行列計算部
１０３…ランダムウォーク特徴量計算部
１０４…類似度計算部
１０５…初期クラスタ生成部
１０６…クラスタ統合部
１０７，２０５…出力部
２０２…パラメータバリエーション生成部
２０４…クラスタ評価部
【図１】
0005385313.tif 000038
【図２】
0005385313.tif 000039
【図３】
0005385313.tif 000040
【図４】
0005385313.tif 000041
【図５】
0005385313.tif 000042
【図６】
0005385313.tif 000043
【図７】
0005385313.tif 000044
【図８】
0005385313.tif 000045
【図９】
0005385313.tif 000046
【図１０】
0005385313.tif 000047
【図１１】
0005385313.tif 000048
【図１２】
0005385313.tif 000049
【図１３】
0005385313.tif 000050
【図１４】
0005385313.tif 000051
【図１５】
0005385313.tif 000052
【図１６】
0005385313.tif 000053
【図１７】
0005385313.tif 000054
【図１８】
0005385313.tif 000055
【図１９】
0005385313.tif 000056
【図２０】
0005385313.tif 000057
【図２１】
0005385313.tif 000058
【図２２】
0005385313.tif 000059
【図２３】
0005385313.tif 000060
【図２４】
0005385313.tif 000061
【図２５】
0005385313.tif 000062
【図２６】
0005385313.tif 000063