"隣接行列が定義できるデータ、指定されたクラスタ数およびパラメータを入力とし、該入力データを前記クラスタ数およびパラメータによってクラスタリングするデータの領域分割装置であって、前記入力データの隣接関係から推移行列を計算する推移行列計算手段と、前記推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算手段と、前記ランダムウォーク特徴量からデータ間の類似度を計算する類似度計算手段と、前記データ間の類似度から初期クラスタを生成する初期クラスタ生成手段と、前記初期クラスタを前記指定されたクラスタ数に統合するクラスタ統合手段と、を備えたことを特徴とするデータの領域分割装置。前記入力されたパラメータを組み合わせてパラメータのバリエーションを生成するパラメータバリエーション生成手段と、前記生成されたパラメータのバリエーション毎に前記領域分割装置がクラスタリングを行なった結果を、各々評価するクラスタ評価手段と、を備えたことを特徴とする請求項1に記載のデータの領域分割装置。前記クラスタ評価手段は、クラスタの境界数を評価値として計算するか、又は前記ランダムウォーク特徴量計算手段により計算されたランダムウォーク特徴量をクラスタ単位に集約して求めたクラスタ間の近接性を用いて、異なるクラスタとの近接性の平均を評価値として計算するか、又は前記クラスタ間の近接性を用いて自クラスタから他クラスタへの近接性の総和を評価値として計算することを特徴とする請求項2に記載のデータの領域分割装置。前記ランダムウォーク特徴量計算手段は、ランダムウォークにより初めてデータのノードiからノードjに到達する時刻をランダムウォーク特徴量として計算し、前記類似度計算手段は、前記ランダムウォーク特徴量である前記初めてノードiからノードjに到達する時刻からデータ間の類似度を計算し、前記クラスタ評価手段は、前記ランダムウォーク特徴量である前記初めてノードiからノードjに到達する時刻をクラスタ単位に集約して求めたクラスタ間の遠隔性を用いて、自クラスタの遠隔性の総和を評価値として計算することを特徴とする請求項2に記載のデータの領域分割装置。隣接行列が定義できるデータ、指定されたクラスタ数およびパラメータを入力とし、該入力データを前記クラスタ数およびパラメータによってクラスタリングするデータの領域分割方法であって、データ入力手段が、隣接行列が定義できるデータ、指定されたクラスタ数およびパラメータの入力を受け付けるデータ入力ステップと、推移行列計算手段が、前記入力データの隣接関係から推移行列を計算する推移行列計算ステップと、ランダムウォーク特徴量計算手段が、前記推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算ステップと、類似度計算手段が、前記ランダムウォーク特徴量からデータ間の類似度を計算する類似度計算ステップと、初期クラスタ生成手段が、前記データ間の類似度から初期クラスタを生成する初期クラスタ生成ステップと、クラスタ統合手段が、前記初期クラスタを前記指定されたクラスタ数に統合するクラスタ統合ステップと、を備えたことを特徴とするデータの領域分割方法。パラメータバリエーション生成手段が、前記入力されたパラメータを組み合わせてパラメータのバリエーションを生成するパラメータバリエーション生成ステップを実行し、前記生成されたパラメータのバリエーション毎に、前記推移行列計算ステップ、ランダムウォーク特徴量計算ステップ、類似度計算ステップ、初期クラスタ生成ステップおよびクラスタ統合ステップを実行してクラスタリングを実施し、クラスタ評価手段が、前記パラメータのバリエーション毎のクラスタリング結果を各々評価するクラスタ評価ステップを実行する、ことを特徴とする請求項5に記載のデータの領域分割方法。前記クラスタ評価ステップは、クラスタの境界数を評価値として計算するか、又は前記ランダムウォーク特徴量計算手段により計算されたランダムウォーク特徴量をクラスタ単位に集約して求めたクラスタ間の近接性を用いて、異なるクラスタとの近接性の平均を評価値として計算するか、又は前記クラスタ間の近接性を用いて自クラスタから他クラスタへの近接性の総和を評価値として計算することを特徴とする請求項6に記載のデータの領域分割方法。前記ランダムウォーク特徴量計算ステップは、ランダムウォークにより初めてデータのノードiからノードjに到達する時刻をランダムウォーク特徴量として計算し、前記類似度計算ステップは、前記ランダムウォーク特徴量である前記初めてノードiからノードjに到達する時刻からデータ間の類似度を計算し、前記クラスタ評価ステップは、前記ランダムウォーク特徴量である前記初めてノードiからノードjに到達する時刻をクラスタ単位に集約して求めたクラスタ間の遠隔性を用いて、自クラスタの遠隔性の総和を評価値として計算することを特徴とする請求項6に記載のデータの領域分割方法。コンピュータを請求項1ないし4のいずれか1項に記載の各手段として機能させるデータの領域分割プログラム。上述した連結成分ラベリングでは、4近傍で連結したピクセルを一つの領域とするので、境界が完全に連結していないと領域を分離することができない。例えば、図7画像2の入力画像データのように境界がとぎれていると、連結成分ラベリング結果は、図8結果2のように外側と内側の領域がつながってしまい適切な領域分割ができない。本発明は上記問題を解決するものであり、その目的は、点線による線画、閉じていない隙間の空いた線画、ノイズを含む画像やぼやけた画像のエッジ抽出結果など、完全に連結していない境界を持つ画像に対しても適切に領域を分割することができるデータの領域分割装置、方法、プログラムを提供することにある。上記課題を解決するための本発明のデータの領域分割装置は、隣接行列が定義できるデータ、指定されたクラスタ数およびパラメータを入力とし、該入力データを前記クラスタ数およびパラメータによってクラスタリングするデータの領域分割装置であって、前記入力データの隣接関係から推移行列を計算する推移行列計算手段と、前記推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算手段と、前記ランダムウォーク特徴量からデータ間の類似度を計算する類似度計算手段と、前記データ間の類似度から初期クラスタを生成する初期クラスタ生成手段と、前記初期クラスタを前記指定されたクラスタ数に統合するクラスタ統合手段と、を備えたことを特徴としている。さらに、前記入力されたパラメータを組み合わせてパラメータのバリエーションを生成するパラメータバリエーション生成手段と、前記生成されたパラメータのバリエーション毎に前記領域分割装置がクラスタリングを行なった結果を、各々評価するクラスタ評価手段と、を備えたことを特徴としている。1請求項1~9に記載の発明によれば、入力データの領域を適切に分割することができる。例えば画像データの場合、点線による線画、閉じていない隙間の空いた線画、ノイズを含む画像やぼやけた画像のエッジ抽出結果など、完全に連結していない境界を持つ画像に対しても適切に領域を分割することができる。2請求項2、6に記載の発明によれば、生成されたクラスタを評価することにより、入力したデータおよびクラスタ数に対してパラメータの最適化を行なうことができる。以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。以下の実施例1~5は、本発明を画像データのクラスタリングに適用した例を示している。図1は実施例1の画像領域分割装置の構成を示し、図2は図1の各部が行なう処理のフローチャートを示している。まず、実施例1の概略を説明する。本実施例1の画像領域分割装置は、入力部101、推移行列計算手段としての推移行列計算部102、ランダムウォーク特徴量計算手段としてのランダムウォーク特徴量計算部103、類似度計算手段としての類似度計算部104、初期クラスタ生成手段としての初期クラスタ生成部105、クラスタ統合手段としてのクラスタ統合部106および出力部107を備えている。入力部101は、ネットワーク又はファイルなどから、例えば装置の利用者が指定した2値画像と、パラメータ、すなわちクラスタ数、初期クラスタ生成部105において使用する固有ベクトル数射影する部分空間の次元数、ランダムウォークのリスタート率、類似度計算のパラメータなどを入力するステップS101。推移行列計算部102は、入力部101により入力された画像データの隣接関係から推移行列を計算するステップS102。ランダムウォーク特徴量計算部103は、前記計算された推移行列からランダムウォーク特徴量を計算するステップS103。類似度計算部104は、前記計算されたランダムウォーク特徴量からデータ間の類似度を計算するステップS104。初期クラスタ生成部105は、前記計算されたデータ間の類似度から初期クラスタ後述の初期クラスタインデックスg0を生成するS105。クラスタ統合部106は、前記生成された初期クラスタを前記指定されたクラスタ数に統合して後述のクラスタインデックスgを求めるステップS106a,S106b。出力部107は、前記クラスタの統合により得られたクラスタインデックスgを、ネットワーク又はファイルなどに出力するステップS107。図1の画像領域分割装置は、例えばコンピュータにより構成され、通常のコンピュータのハードウェアリソース、例えばROM,RAM,CPU、入力装置、出力装置、通信インターフェース、ハードディスク、記録媒体およびその駆動装置を備えている。また、図示省略のネットワークやファイルと接続可能に構成されている。このハードウェアリソースとソフトウェアリソースOS、アプリケーションなどとの協働の結果、本画像領域分割装置は、図1に示すように、入力部101、推移行列計算部102、ランダムウォーク特徴量計算部103、類似度計算部104、初期クラスタ生成部105、クラスタ統合部106および出力部107を実装する。次に、上記のように構成された装置の詳細を説明する。本実施例1では、2値画像f,1≦x≦width,1≦y≦height、クラスタ数K、部分空間の次元数使用する固有ベクトル数C、ランダムウォークのリスタート率β、類似度計算のパラメータσを入力とし、K個のクラスタに分割したクラスタインデックスを出力する。入力部101には、ステップS101において、ネットワーク又はファイルなどから、例えば装置の利用者が指定した2値画像f、クラスタ数K、使用する固有ベクトル数C、ランダムウォークのリスタート率β、類似度計算のパラメータσが入力される。例えば図9の画像データ画像3およびK=2、C=2、σ=50が入力される。次に推移行列計算部102は、ステップS102において推移行列の計算を行なう。まず、2値画像fから領域ピクセルを取り出し、ノード番号を付ける。例えば図9の画像の領域部分を図10のように、左上から順にノード番号を付ける。ノードの数をNとする。次に、ノードiとjが隣接しているかどうかを示す隣接行列Aをとする。すなわちノードi,jが隣接しているときは1とし、隣接していないときは0として図11のように隣接行列を作成する。そして図11の隣接行列を各行の要素の総和が1になるように正規化して、図12のように推移行列Pを作成する。推移行列Pはとなる。次にランダムウォーク特徴量計算部103は、ステップS103において、リスタートありランダムウォークでランダムウォーク特徴量を計算する。リスタートありランダムウォークは次式で示される。rj=1-βPrjβej4ここで、βはリスタート率であり、本実施形態ではβ=0.05の値を用いるが、この値に限るものではない。また、ejはj番目の要素のみ1の列ベクトル、すなわち、ここで、Tは転置。rjは下記の連立方程式で得られる。In-1-βPrj=βej6ここで、Inはn次元の単位行列。この式6をガウスの消去法等を用いて、rj,j=1,nを図13のように計算する。ランダムウォーク特徴量Rは下記の式7のようになる:上記式7中の添字のriはRのi行目の行ベクトルである。ランダムウォーク特徴量計算部103は、境界によって領域ピクセル間の往来が阻害される度合いを計算することで領域ピクセル間の隔たりを適切に評価する。例えば4近傍での最短距離ではノード1と2の間の最短経路は図14のようになる。尚、以下の図14~図21における○囲み数字1~○囲み数字4は、ノード1~ノード4を示すものである。境界があっても、図15のように迂回できる場合は距離が変わらないため、境界の影響を評価できない。これに対して本発明のランダムウォーク特徴量計算部103により求めるランダムウォーク特徴量Rは、図16のように、ノード1と2の全ての経路を考慮する。このため、境界があると図17のように、いくつかの経路が阻害され、境界の影響を評価できる。次に類似度計算部104は、ステップS104において、データ間の類似度、すなわちノードuとvの類似度を下記のように計算する。kuv=exp-σ∥ru-rv∥18ここで、∥∥はl1距離。また、類似度行列Kをとする。例えば図10の画像3の類似度行列は図18のようになる。上記のように、本発明の類似度計算部104では、2つの領域ピクセル間の類似度を2者間の隔たりだけでなく、他の領域との隔たりを含めて計算している。ある領域が他の領域の内側にある場合は、外側の領域では内側の領域の影響でピクセル間の隔たりが大きくなる。しかし、他の領域との隔たりを含めて計算することで、外側の領域は内側の領域と隔たっているという共通の特徴ができ、外側の領域を一つにまとめることを可能とする。例えば、図19のような場合、境界の影響でノード2とノード1,3,4は遠いと判定できるが、ノード1とノード4も遠いと判定されてしまう。そこで、4つのノード間の関係を図20のように特徴量とする。ノード間の類似度をこの特徴量で比較すると、図21のように、ノード2とノード1,3,4の間では共通部分が1以下、ノード1,3,4の間では共通部分が2以上となる。次に初期クラスタ生成部105は、ステップS105において、ノードi=1,nを非線型変換φで高次元空間に写像し、分散が最大となる部分空間に射影する。部分空間への射影は次式で与えられる:zri=φriTwb10分散の最大化は:ここで、γ>0は定数。また、類似度と非線型変換に下記の式13の関係があるので、kij=φriTφrj13これによって、固有値の降順にC個の固有値および固有ベクトルが、例えば表2、表3のように求められる。次にC個の固有ベクトルを並べて、部分空間への射影を得る:すなわち、ノードiの部分空間の射影は下記のようになるzi=αi1,,αiC19初期クラスタインデックスg0は下記のように求める:これによって、図9の画像画像3の初期クラスタは図22のように生成され、表4のような初期クラスタインデックスg0が求められる。次にクラスタ統合部106は、ステップS106a,106bにおいて、下記の表5のAlgorithm2mergeclusterのステップ1~ステップ19に従ってクラスタ候補を統合する。である。前記表5のAlgorithm2のステップ1~10の結果、候補ラベルテーブル、統合テーブルは、各々表6、表7となる。続いて、Algorithm2のステップ11,12の結果、候補クラスタの情報は表8となる。Ncand=3>K=2なのでクラスタを統合する。μuμv,u,v=1,2,3の値は下記となる:最大値を持つクラスタ候補2,3を統合し、番号が小さいクラスタ候補2のクラスタベクトルとノード数を更新し、クラスタ候補3を削除する。統合後のクラスタ候補、及び統合テーブルは、表9、表10となる。このように、クラスタ候補がK=2となったステップS106bの判定結果がyesとなったので統合を終了する。次に、下記表11のAlgorithm3renumberのステップ1~ステップ23に従ってクラスタインデックスgを作成する。これによって、図9の画像画像3のクラスタは図23のように生成され、表12のようなクラスタインデックスgが作成される。次に出力部107は、ステップS107において、ネットワーク、またはファイルなどに、前記作成されたクラスタインデックスgを出力する。図3は実施例2の画像領域分割装置の構成を示し、図4は図3の各部が行なう処理のフローチャートを示している。図3において図1と同一部分は同一符号をもって示している。本実施例2図3において実施例1図1と異なる点は、前記入力されたパラメータを組み合わせてパラメータのバリエーションを生成するパラメータバリエーション生成手段としてのパラメータバリエーション生成部202と、前記生成されたパラメータのバリエーション毎に前記領域分割装置推移行列計算部102、ランダムウォーク特徴量計算部103、類似度計算部104、初期クラスタ生成部105、クラスタ統合部106がクラスタリングを行なった結果を、各々評価するクラスタ評価手段としてのクラスタ評価部204とを備え、入力部201および出力部205の構成を変更した点にある。図3の装置も、前記図1と同様に例えばコンピュータにより構成され、通常のコンピュータのハードウェアリソースとソフトウェアリソースとの協働の結果、実施例2の画像領域分割装置は図3に示すように、入力部201、推移行列計算部102、ランダムウォーク特徴量計算部103、類似度計算部104、初期クラスタ生成部105、クラスタ統合部106、パラメータバリエーション生成部202、クラスタ評価部204および出力部205を実装する。まず入力部201には、ステップS201において、ネットワーク又はファイルなどから、例えば装置の利用者が指定した2値画像f、クラスタ数、ランダムウォークのリスタート率、類似度計算のパラメータの候補σ、使用する固有ベクトル数C式25が入力される。σ=σ1,,σNσC=C1,,CNC25例えば図7の画像データ、クラスタ数K=2、パラメータの候補σ=5,50,500、C=2が入力される。次にパラメータバリエーション生成部202は、ステップS202において、パラメータ候補を組み合わせて、Nσ×NC個のバリエーションを例えば表13のように作成する。次にステップS203において、指定したパラメータによる領域分割がなされる。このステップS203では、推移行列計算部102、ランダムウォーク特徴量計算部103、類似度計算部104、初期クラスタ生成部105およびクラスタ統合部106が前記図1、図2で述べた処理を行って、表13のバリエーション1,2,3についてクラスタインデックスを計算し、各々図24、図25、図26の結果が得られる。次にクラスタ評価部204が、ステップS204a,S204bにおいて、前記クラスタ統合部106により求められた、バリエーション1,2,3の各クラスタインデックスについて、評価値としてクラスタの境界数blenを、下記式26により計算し、出力部205が、blenを最小とする結果を返す出力するステップS205。すなわち、式26に従ってバリエーション1,2,3の評価値blenを表14のように計算し、blenが最小となるバリエーション2の結果図25を出力する。本実施例3では、クラスタ評価部204以外の構成は実施例2図3、図4と同一である。この実施例3におけるクラスタ評価部204は、実施例2のように、評価値としてクラスタ境界数blen式26を求めることに代えて、以下の処理を行なう。前記式7のランダムウォーク特徴量Rをクラスタ単位に集約して、クラスタ間の近接性sijを次の式27のように計算する:そして異なるクラスタとの近接性の平均を評価値roffとする:この式28のroffを最小とするクラスタリングを選択する。本実施例4では、クラスタ評価部204以外の構成は実施例2図3、図4と同一である。この実施例4におけるクラスタ評価部204は、実施例2のように、評価値としてクラスタ境界数blen式26を求めることに代えて、以下の処理を行なう。前記式27でクラスタ間の近接性sijを計算する。そして自クラスタから他クラスタへの近接性の総和を評価値rcutとする:この式29のrcutを最小とするクラスタリングを選択する。本実施例5では、ランダムウォーク特徴量計算部103、類似度計算部104、クラスタ評価部204以外の構成は実施例2図3、図4と同一である。この実施例5におけるランダムウォーク特徴量計算部103は、前記ランダムウォーク特徴量R式7に代えて、初めてノードiからノードjに到達する時刻hittingtimeshijを式30、31のようにランダムウォーク特徴量とする:ここで、πは推移行列の定常分布、すなわち下記の方程式の解。πP=π32また、Z=In-P-Π133さらに、である。そして類似度計算部104は、huとhvの類似度を下記の式35のように計算する。そしてクラスタ評価部204は、式30のランダムウォーク特徴量をクラスタ単位に集約して、クラスタ間の遠隔性sij ́を下記の式36のように計算する:そして自クラスタの遠隔性の総和を評価値rcut’とする:この式37のrcut’を最小とするクラスタリングを選択する。尚、本発明は隣接行列が定義できるデータに対して適用が可能であり、画像以外のデータのクラスタリングを行なうこともできる。また、本実施形態のデータの領域分割装置における各手段の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、本実施形態のデータの領域分割方法における手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えばFDFloppy登録商標Diskや、MOMagneto-Opticaldisk、ROMReadOnlyMemory、メモリカード、CDCompactDisk-ROM、DVDDigitalVersatileDisk-ROM、CD-R、CD-RW、HDD、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。"