(57)【要約】【課題】完全に連結していない境界を持つ画像に対しても適切に領域を分割する。【解決手段】本発明に係る画像領域分割装置１００は、入力データの隣接関係から推移行列を計算する推移行列計算部１３１と、推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算部１３２と、ランダムウォーク特徴量から候補間の類似度を計算する類似度計算部１３３と、入力データの隣接関係およびランダムウォーク特徴量から候補間の乖離情報を計算する乖離情報計算部１３４と、候補間の類似度および候補間の乖離情報から候補の特徴量を計算する候補特徴量計算部１３５と、候補の特徴量をクラスタリングする候補クラスタリング部１３６と、ランダムウォーク特徴量、および、クラスタリング結果から領域番号を計算する領域番号計算部１３７とを備える。【選択図】図１
2015090642.tif 000002
【特許請求の範囲】
【請求項１】
入力データを指定された領域数で分割する画像領域分割装置であって、
前記入力データの隣接関係から推移行列を計算する推移行列計算手段と、
前記推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算手段と、
前記ランダムウォーク特徴量から候補間の類似度を計算する類似度計算手段と、
前記入力データの隣接関係および前記ランダムウォーク特徴量から候補間の乖離情報を計算する乖離情報計算手段と、
前記候補間の類似度および前記候補間の乖離情報から候補の特徴量を計算する候補特徴量計算手段と、
前記候補の特徴量をクラスタリングする候補クラスタリング手段と、
前記ランダムウォーク特徴量、および、前記候補クラスタリング手段によるクラスタリング結果から領域番号を計算する領域番号計算手段とを備えることを特徴とする画像領域分割装置。
【請求項２】
入力データを指定された領域数で分割する画像領域分割方法であって、
推移行列計算手段によって、前記入力データの隣接関係から推移行列を計算する推移行列計算ステップと、
ランダムウォーク特徴量計算手段によって、前記推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算ステップと、
類似度計算手段によって、前記ランダムウォーク特徴量から候補間の類似度を計算する類似度計算ステップと、
乖離情報計算手段によって、前記入力データの隣接関係および前記ランダムウォーク特徴量から候補間の乖離情報を計算する乖離情報計算ステップと、
候補特徴量計算手段によって、前記候補間の類似度および前記候補間の乖離情報から候補の特徴量を計算する候補特徴量計算ステップと、
候補クラスタリング手段によって、前記候補の特徴量をクラスタリングする候補クラスタリングステップと、
領域番号計算手段によって、前記ランダムウォーク特徴量、および、前記候補クラスタリングステップによるクラスタリング結果から領域番号を計算する領域番号計算ステップとを含むことを特徴とする画像領域分割方法。
【請求項３】
入力データを指定された領域数で分割する画像領域分割プログラムであって、コンピュータに、
前記入力データの隣接関係から推移行列を計算する推移行列計算ステップと、
前記推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算ステップと、
前記ランダムウォーク特徴量から候補間の類似度を計算する類似度計算ステップと、
前記入力データの隣接関係および前記ランダムウォーク特徴量から候補間の乖離情報を計算する乖離情報計算ステップと、
前記候補間の類似度および前記候補間の乖離情報から候補の特徴量を計算する候補特徴量計算ステップと、
前記候補の特徴量をクラスタリングする候補クラスタリングステップと、
前記ランダムウォーク特徴量、および、前記候補クラスタリングステップによるクラスタリング結果から領域番号を計算する領域番号計算ステップとを実行させるための画像領域分割プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング手法に関し、特に画像を重なりのない領域に分割する画像領域分割装置、画像領域分割方法および画像領域分割プログラムに関する。
【背景技術】
【０００２】
従来、画像領域を分割する手法として、非特許文献１に示すように連結成分ラベリングという手法があった。連結成分ラベリングは、線画や一般画像から抽出されたエッジ画像等の２値画像を入力として、線やエッジ等の境界で隔てられた連続した領域を抽出する。
【０００３】
連結成分ラベリングに入力される２値画像は下記の形式である。
【０００４】
【数１】
2015090642.tif 000003
ここで、１≦ｙ≦ｍ、１≦ｘ≦ｎであり、ｍは高さ、ｎは幅を表す。
【０００５】
連結成分ラベリングのアルゴリズムの一例を下記表１に示す。連結成分ラベリングは、例えば下記表１に示す「Ａｌｇｏｒｉｔｈｍ  １  連結成分ラベリング」のステップ１〜３６のように実行される。
【０００６】
【表１】
2015090642.tif 000004
【０００７】
例えば、図３に示す画像データ（画像１）が、表１に示す連結成分ラベリングのアルゴリズムに入力されたとする。図３において、白いピクセルは領域、黒いピクセルは境界を表す。四角形を形成する境界が領域を内側と外側に分離している。
【０００８】
この場合、連結成分ラベリングの結果は、図４に示すような結果（結果１）となる。境界部分には０、外側の領域には１、内側の領域には２のラベルが付与される。
【０００９】
一方、画像処理の手法として様々な手法が知られている。例えば、画像を細線化する手法として、非特許文献２に示すようなＺｈａｎｇ−Ｓｕｅｎ  Ｔｈｉｎｎｉｎｇ法が知られている。また、クラスタリング手法として、非特許文献３に示すようなｋ−ｍｅａｎｓクラスタリングが知られている。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】田村秀行編著、「コンピュータ画像処理」、第１版、株式会社オーム社、平成１４年１２月、p.149-151
【非特許文献２】T.Y.Zhang and C.Y.Suen, “A Fast Parallel Algorithm for Thinning Digital Patterns”, Communication of the ACM, March 1984, Volume 27, Number 3, pp.236-239
【非特許文献３】Ｃ．Ｍ．ビショップ著、「パターン認識と機械学習  下」、初版、シュプリンガー・ジャパン株式会社、２００８年８月、p.140-143
【発明の概要】
【発明が解決しようとする課題】
【００１１】
上述した連結成分ラベリングでは、４近傍で連結したピクセルを一つの領域とするので、境界が完全に連結していないと領域を分離することができないという問題があった。
【００１２】
例えば、図５に示す画像データ（画像２）の様に境界がとぎれていると、外側と内側の領域がつながってしまい適切な領域分割ができなかった。この場合の、連結成分ラベリングの結果（結果２）を図６に示す。
【００１３】
したがって、かかる点に鑑みてなされた本発明の目的は、点線による線画、閉じていない隙間の空いた線画、ノイズを含む画像やぼやけた画像のエッジ抽出結果など、完全に連結していない境界を持つ画像に対しても適切に領域を分割することができる画像領域分割装置、画像領域分割方法および画像領域分割プログラムを提供することにある。
【課題を解決するための手段】
【００１４】
上記課題を解決するため、本発明に係る画像領域分割装置は、入力データを指定された領域数で分割する画像領域分割装置であって、前記入力データの隣接関係から推移行列を計算する推移行列計算手段と、前記推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算手段と、前記ランダムウォーク特徴量から候補間の類似度を計算する類似度計算手段と、前記入力データの隣接関係および前記ランダムウォーク特徴量から候補間の乖離情報を計算する乖離情報計算手段と、前記候補間の類似度および前記候補間の乖離情報から候補の特徴量を計算する候補特徴量計算手段と、前記候補の特徴量をクラスタリングする候補クラスタリング手段と、前記ランダムウォーク特徴量、および、前記候補クラスタリング手段によるクラスタリング結果から領域番号を計算する領域番号計算手段とを備えるものである。
【００１５】
また、上記課題を解決するため、本発明に係る画像領域分割方法は、入力データを指定された領域数で分割する画像領域分割方法であって、推移行列計算手段によって、前記入力データの隣接関係から推移行列を計算する推移行列計算ステップと、ランダムウォーク特徴量計算手段によって、前記推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算ステップと、類似度計算手段によって、前記ランダムウォーク特徴量から候補間の類似度を計算する類似度計算ステップと、乖離情報計算手段によって、前記入力データの隣接関係および前記ランダムウォーク特徴量から候補間の乖離情報を計算する乖離情報計算ステップと、候補特徴量計算手段によって、前記候補間の類似度および前記候補間の乖離情報から候補の特徴量を計算する候補特徴量計算ステップと、候補クラスタリング手段によって、前記候補の特徴量をクラスタリングする候補クラスタリングステップと、領域番号計算手段によって、前記ランダムウォーク特徴量、および、前記候補クラスタリングステップによるクラスタリング結果から領域番号を計算する領域番号計算ステップとを含むものである。
【００１６】
また、上記課題を解決するため、本発明に係る画像領域分割プログラムは、入力データを指定された領域数で分割する画像領域分割プログラムであって、コンピュータに、前記入力データの隣接関係から推移行列を計算する推移行列計算ステップと、前記推移行列からランダムウォーク特徴量を計算するランダムウォーク特徴量計算ステップと、前記ランダムウォーク特徴量から候補間の類似度を計算する類似度計算ステップと、前記入力データの隣接関係および前記ランダムウォーク特徴量から候補間の乖離情報を計算する乖離情報計算ステップと、前記候補間の類似度および前記候補間の乖離情報から候補の特徴量を計算する候補特徴量計算ステップと、前記候補の特徴量をクラスタリングする候補クラスタリングステップと、前記ランダムウォーク特徴量、および、前記候補クラスタリングステップによるクラスタリング結果から領域番号を計算する領域番号計算ステップとを実行させるものである。
【発明の効果】
【００１７】
本発明によれば、画像入力データの領域を適切に分割することができる。例えば、点線による線画、閉じていない隙間の空いた線画、ノイズを含む画像やぼやけた画像のエッジ抽出結果など、完全に連結していない境界を持つ画像に対しても適切に領域を分割することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施形態に係る画像領域分割装置の概略構成を示す図である。
【図２】本発明の一実施形態に係る画像領域分割装置の動作を示すフローチャートである。
【図３】境界が完全に連結している画像データ（画像１）を示す図である。
【図４】画像１に連結成分ラベリングを実行した結果（結果１）を示す図である。
【図５】境界がとぎれている画像データ（画像２）を示す図である。
【図６】画像２に連結成分ラベリングを実行した結果（結果２）を示す図である。
【図７】画像２に細線化を実行した結果を示す図である。
【図８】図７に示すデータから候補点を取得した様子を示す図である。
【図９】特徴量に対してクラスタリングした結果を示す図である。
【図１０】画像２の領域番号を計算した結果を示す図である。
【図１１】画像２の領域を分割した結果を示す図である。
【図１２】ノード１とノード２の間の最短経路の一例を示す図である。
【図１３】境界がある場合におけるノード１とノード２の間の最短経路の一例を示す図である。
【図１４】ランダムウォーク特徴量を説明する図である。
【図１５】境界がある場合におけるランダムウォーク特徴量を説明する図である。
【発明を実施するための形態】
【００１９】
以下、本発明に係る実施形態について、図面を参照して説明する。
【００２０】
図１は、本発明の一実施形態に係る画像領域分割装置１００の概略構成を示す図である。画像領域分割装置１００は、２値画像Ｉｍａｇｅ（ｙ、ｘ）、画像サイズ（ｍ、ｎ）、クラスタ数Ｎｒ、候補数Ｎｃ、候補尤度の閾値η、特徴量次元数ｄｉｍ、再帰確率ｃ、候補間距離の重み係数τ、乖離情報の重み係数δを入力とし、Ｎｒ個の領域に分割した領域番号を出力するものである。画像領域分割装置１００は、入力部１１０と、記憶部１２０と、演算部１３０と出力部１４０とを備える。
【００２１】
入力部１１０は、ネットワークまたはファイルなどから、２値画像Ｉｍａｇｅ、画像サイズ（ｍ、ｎ）、クラスタ数Ｎｒ、候補数Ｎｃ、候補尤度の閾値η、特徴量次元数ｄｉｍ、再帰確率ｃ、候補間距離の重み係数τ、乖離情報の重み係数δを入力し、記憶部１２０に蓄積する。
【００２２】
記憶部１２０は、入力部１１０に入力されたデータや演算部１３０で計算されたデータを蓄積する。記憶部１２０に蓄積されたデータは演算部１３０から参照される。
【００２３】
演算部１３０は、推移行列計算手段としての推移行列計算部１３１、ランダムウォーク特徴量計算手段としてのランダムウォーク特徴量計算部１３２、類似度計算手段としての類似度計算部１３３、乖離情報計算手段としての乖離情報計算部１３４、候補特徴量計算手段としての候補特徴量計算部１３５、候補クラスタリング手段としての候補クラスタリング部１３６、および、領域番号計算手段としての領域番号計算部１３７を備える。演算部１３０は、記憶部１２０からデータを読み込んで処理し、出力部１４０に出力する。
【００２４】
推移行列計算部１３１は、入力部１１０に入力された２値画像Ｉｍａｇｅを細線化する。細線化には様々な手法があるが、例えば、非特許文献２にＺｈａｎｇ−Ｓｕｅｎ  Ｔｈｉｎｎｉｎｇ法が紹介されている。Ｚｈａｎｇ−Ｓｕｅｎ  Ｔｈｉｎｎｉｎｇ法は、例えば下記表２に示す「Ａｌｇｏｒｉｔｈｍ  ２  Ｚｈａｎｇ−Ｓｕｅｎ  Ｔｈｉｎｎｉｎｇ」のステップ１〜３０のようなアルゴリズムで実行される。
【００２５】
【表２】
2015090642.tif 000005
【００２６】
次に、推移行列計算部１３１は、隣接行列Ａ：Ｎｐ×Ｎｐ、Ｎｐ＝ｍ・ｎを下記のように作成する。
【００２７】
【数２】
2015090642.tif 000006
ここで、ｉ、ｊはノード番号である。また、ノード番号と座標（ｙ、ｘ）との関係は下記のようになる。
【００２８】
【数３】
2015090642.tif 000007
ここで、記号「÷」は整数除算を表し、記号「ｍｏｄ」は剰余を表す。
【００２９】
また、式（２）におけるＢは境界集合であり、境界集合Ｂは、下記のように表される。
【００３０】
【数４】
2015090642.tif 000008
【００３１】
推移行列計算部１３１は、隣接行列Ａから、推移行列Ｐ：Ｎｐ×Ｎｐを下記のように計算する。
【００３２】
【数５】
2015090642.tif 000009
ここで、
【００３３】
【数６】
2015090642.tif 000010
であり、また、
【００３４】
【数７】
2015090642.tif 000011
である。
【００３５】
ランダムウォーク特徴量計算部１３２は、まず、画像からＮｃ個の格子点を取得し、候補点集合σを下記のように作成する。
【００３６】
【数８】
2015090642.tif 000012
【００３７】
次に、ランダムウォーク特徴量計算部１３２は、各候補点を始点とするリスタートありランダムウォークでランダムウォーク特徴量を計算する。σｊを始点とするリスタートありランダムウォークは次式で示される。
【００３８】
【数９】
2015090642.tif 000013
ここで、
【００３９】
【数１０】
2015090642.tif 000014
であり、また、
【００４０】
【数１１】
2015090642.tif 000015
である。ここで、式（１０）におけるｃは、再帰確率（０＜ｃ＜１）である。
【００４１】
また、式（１０）におけるｚｊは、下記の連立方程式を解くことにより得られる。
【００４２】
【数１２】
2015090642.tif 000016
ここで、ＩＮｐはＮｐ次元の単位行列である。
【００４３】
また、ランダムウォーク特徴量Ｚは、下記のようにして得られる。
【００４４】
【数１３】
2015090642.tif 000017
【００４５】
このように、本実施形態に係るランダムウォーク特徴量計算部１３２は、境界によって領域ピクセル間の往来が阻害される度合いを計算することで領域ピクセル間の隔たりを適切に評価することができる。
【００４６】
例えば、４近傍での最短距離（市街地距離）ではノード１とノード２の間の最短経路は図１２のようになる。なお、以下、図１２〜図１５において、ノード１および２は、丸囲み数字で表す。ノード１とノード２の間に境界があっても、図１３のように迂回できる場合は距離が変わらないため、境界の影響を評価できない。
【００４７】
これに対し、本実施形態に係るランダムウォーク特徴量計算部１３２は、図１４に示すように、ノード１とノード２を結ぶ全ての経路を考慮する。このため、図１５に示すように境界があると、いくつかの経路が阻害されるため、ランダムウォーク特徴量計算部１３２は、境界の影響を評価することができる。
【００４８】
類似度計算部１３３は、ランダムウォーク特徴量Ｚから、候補の類似度行列Ｋを下記のように計算する。
【００４９】
【数１４】
2015090642.tif 000018
ここで、
【００５０】
【数１５】
2015090642.tif 000019
である。また、式（１４）のｅｘｐは指数関数、式（１５）のｌｎは自然対数を表す。また、
【００５１】
【数１６】
2015090642.tif 000020
である。
【００５２】
乖離情報計算部１３４は、境界集合Ｂおよびランダムウォーク特徴量Ｚから候補間の乖離情報ｇｉｊを計算する。乖離情報計算部１３４は、まず、ランダムウォーク特徴量Ｚから、候補尤度行列を下記のように計算する。
【００５３】
【数１７】
2015090642.tif 000021
【００５４】
乖離情報計算部１３４は、次に、下記の表３〜表６に示すアルゴリズムの手順に従って乖離情報ｇｉｊを計算する。
【００５５】
【表３】
2015090642.tif 000022
【００５６】
【表４】
2015090642.tif 000023
【００５７】
【表５】
2015090642.tif 000024
【００５８】
【表６】
2015090642.tif 000025
【００５９】
このように、本実施形態に係る乖離情報計算部１３４は、境界における候補間の相関を計算することにより、２つの候補を分離すべき程度を適切に評価することができる。
【００６０】
候補特徴量計算部１３５は、候補点のランダムウォーク特徴量を非線型変換ψ（・）で高次元空間に写像し、分散が最大となる部分空間に射影する。候補特徴量計算部１３５は、この際同時に、境界を挟んだ候補の相関を最小化する。
【００６１】
部分空間への射影は、次式で与えられる。
【００６２】
【数１８】
2015090642.tif 000026
ここで、ｗはψ（・）と同次元のベクトルであり、ｂはスカラー定数である。また、分散の値は下記の式で求められる。
【００６３】
【数１９】
2015090642.tif 000027
ここで、
【００６４】
【数２０】
2015090642.tif 000028
である。
【００６５】
また、境界をはさんだ候補の相関は下記の式で求められる。
【００６６】
【数２１】
2015090642.tif 000029
【００６７】
以上から、目的関数は次式のようになる。
【００６８】
【数２２】
2015090642.tif 000030
ここで、
【００６９】
【数２３】
2015090642.tif 000031
である。
【００７０】
また、式（２２）において、δは乖離情報の重み係数であり、式（２１）において、γは正則化パラメータである。
【００７１】
ここで、類似度と非線型変換には下記の関係がある。
【００７２】
【数２４】
2015090642.tif 000032
【００７３】
したがって、式（２１）は、
【００７４】
【数２５】
2015090642.tif 000033
の固有値問題を解くことで得られる。ここで、
【００７５】
【数２６】
2015090642.tif 000034
である。また、
【００７６】
【数２７】
2015090642.tif 000035
である。固有値λｌの順番は実部の降順とする。すなわち、
【００７７】
【数２８】
2015090642.tif 000036
とする。また、λｌに対応する固有ベクトルをｘｌとすると、候補集合の特徴量Ｆは、
【００７８】
【数２９】
2015090642.tif 000037
となる。ここで、
【００７９】
【数３０】
2015090642.tif 000038
である。
【００８０】
このように、本実施形態に係る候補特徴量計算部１３５は、候補間の類似度と乖離情報という複数の情報を適切に統合することにより、候補のクラスタリングを容易に行うことを可能にする。
【００８１】
候補クラスタリング部１３６は、候補の特徴量Ｆおよび領域数Ｎｒを指定して、階層的クラスタリング（最短距離法）で候補をクラスタリングする。そのアルゴリズムを下記の表７および表８に示す。
【００８２】
【表７】
2015090642.tif 000039
【００８３】
【表８】
2015090642.tif 000040
【００８４】
領域番号計算部１３７は、まず、寄与係数行列Ｃ（Ｎｃ×Ｎｒ）を計算する。寄与係数行列は、下記の連立方程式を解くことで得られる。
【００８５】
【数３１】
2015090642.tif 000041
ここで、Ｚ′は下記に示すような縮小滞在確率行列である。
【００８６】
【数３２】
2015090642.tif 000042
【００８７】
また、Ｑは下記に示すような候補対応行列である。
【００８８】
【数３３】
2015090642.tif 000043
【００８９】
また、ノード番号ｉの領域番号、ｒｅｇｉｏｎ（ｉ）は、
【００９０】
【数３４】
2015090642.tif 000044
となる。ここで、
【００９１】
【数３５】
2015090642.tif 000045
である。
【００９２】
出力部１４０は、領域番号ｒｅｇｉｏｎに対して、細線化で削除した境界を元に戻して領域分割結果を作成し、ネットワークまたはファイルなどに出力する。
【００９３】
続いて、図２に示すフローチャートを参照しながら、本発明の一実施形態に係る画像領域分割装置１００の動作を説明する。
【００９４】
入力部１１０は、ネットワークまたはファイルなどから、データおよびパラメータを入力する（ステップＳ１０１）。
【００９５】
推移行列計算部１３１は、データの隣接関係から推移行列を計算する（ステップＳ１０２）。
【００９６】
ランダムウォーク特徴量計算部１３２は、推移行列からランダムウォーク特徴量を計算する（ステップＳ１０３）。
【００９７】
類似度計算部１３３は、各候補点を始点とするランダムウォーク特徴量の分布を比較して候補間の類似度を計算する（ステップＳ１０４）。
【００９８】
乖離情報計算部１３４は、データの隣接関係およびランダムウォーク特徴量から候補間の乖離情報を計算する（ステップＳ１０５）。この際、境界によって２つの領域（例えば領域ａと領域ｂ）が分離されている場合、境界の一方で、領域ａの尤度（ランダムウォーク特徴量）が大きく、領域ｂの尤度が小さくなり、境界の他方では、領域ａの尤度が小さく、領域ｂの尤度が大きくなる。この性質を利用し、２つの候補ａ、ｂについて下記のように乖離情報を求め、全ての境界についてその情報を統合する。
・境界を挟んで２つの候補ａ、ｂの尤度が大きい。
・境界の同じ側ではａの尤度が大きく、ｂの尤度が小さい。
・境界を挟んで同じ候補は尤度が小さい。
【００９９】
候補特徴量計算部１３５は、候補間の類似度および乖離情報から、類似度が高い候補がより近くに、かつ、乖離情報が大きい候補が遠くに配置されるような候補の特徴量を計算する（ステップＳ１０６）。
【０１００】
候補クラスタリング部１３６は、候補の特徴量をクラスタリングする（ステップＳ１０７）。
【０１０１】
領域番号計算部１３７は、ランダムウォーク特徴量および候補のクラスタリング結果から領域番号を計算する（ステップＳ１０８）。
【０１０２】
出力部１４０は、領域番号を、ネットワークまたはファイルなどに出力する（ステップＳ１０９）。
【０１０３】
続いて、本実施形態に係る画像領域分割装置１００の動作について、具体的な動作例を示して説明する。
【０１０４】
本動作例においては、入力部１１０に、図５に示す画像データ（画像２：ｍ＝１１、ｎ＝１１）、ならびに、Ｎｒ＝２、Ｎｃ＝９、η＝０．０５、ｄｉｍ＝２、ｃ＝０．０５、τ＝２およびδ＝１が入力されたものとする。
【０１０５】
推移行列計算部１３１は、まず、図５に示す画像データ（画像２）を細線化する。図７に、画像２の細線化結果を示す。図７に示すように、境界集合Ｂは、
【０１０６】
【数３６】
2015090642.tif 000046
となる。
【０１０７】
続いて、推移行列計算部１３１は、式（２）によって隣接行列Ａを作成し、また、式（６）によって推移行列Ｐを計算する。
【０１０８】
次に、推移行列計算部１３１は、格子点上から、図８に示すようなＮｃ個の候補点を取得する。取得した候補点は、以下のようになる。
【０１０９】
【数３７】
2015090642.tif 000047
【０１１０】
ランダムウォーク特徴量計算部１３２は、ガウスの消去法等を用いて、式（１２）からｚｊ、ｊ＝１、・・・、Ｎｃを計算する。
【０１１１】
類似度計算部１３３は、式（１４）から、候補間の類似度を計算し、下記表９に示すような類似度行列を得る。
【０１１２】
【表９】
2015090642.tif 000048
【０１１３】
乖離情報計算部１３４は、表３に示した「Ａｌｇｏｒｉｔｈｍ  ３：乖離情報計算」の手順に従って、乖離情報ｇｉｊを計算する。計算された乖離情報ｇｉｊを、下記表１０に示す。
【０１１４】
【表１０】
2015090642.tif 000049
【０１１５】
候補特徴量計算部１３５は、式（２８）から候補特徴量を計算する。計算された候補特徴量を下記表１１に示す。
【０１１６】
【表１１】
2015090642.tif 000050
【０１１７】
候補クラスタリング部１３６は、候補特徴量計算部１３５が計算した表１１に示す特徴量を、表７に示した「Ａｌｇｏｒｉｔｈｍ  ７：階層的クラスタリング（最短距離法）」でクラスタリングする。候補クラスタリング部１３６によるクラスタリングの結果を図９に示す。クラスタ数Ｎｒ＝２が指定されているので、クラスタリング結果は候補５と他の候補となる。また、クラスタインデックスは、以下のようになる。
【０１１８】
【数３８】
2015090642.tif 000051
【０１１９】
領域番号計算部１３７は、式（３２）から領域番号を計算する。計算された領域番号を図１０に示す。
【０１２０】
出力部１４０は、図１１に示すような領域分割結果を出力する。
【０１２１】
（変形例）
以下、本実施形態の変形例について説明する。
【０１２２】
推移行列計算部１３１は、候補点集合の作成方法として、Ｎｃ個のノードをランダムに選択してもよい。
【０１２３】
類似度計算部１３３は、候補の類似度行列を下記のように計算してもよい。
【０１２４】
【数３９】
2015090642.tif 000052
【０１２５】
または、類似度計算部１３３は、候補の類似度行列を下記のように計算してもよい。
【０１２６】
【数４０】
2015090642.tif 000053
【０１２７】
候補クラスタリング部１３６は、候補の特徴量をｋ−ｍｅａｎｓクラスタリングでクラスタリングしてもよい。ｋ−ｍｅａｎｓクラスタリングについては、例えば、非特許文献３に紹介されている。
【０１２８】
このように、本実施形態によれば、点線による線画、閉じていない隙間の空いた線画、ノイズを含む画像やぼやけた画像のエッジ抽出結果など、完全に連結していない境界を持つ画像に対しても適切に領域分割を行うことができる。
【０１２９】
また、本実施形態は隣接行列が定義できるデータに対しても適用が可能であり、画像以外のデータのクラスタリングを行うこともできる。
【０１３０】
さらに、本実施形態は候補の類似度と乖離情報といった複数の情報を統合することが可能であり、データが持つ複数の情報を統合するクラスタリングを行うことができる。
【０１３１】
本発明を諸図面や実施例に基づき説明してきたが、当業者であれば本開示に基づき種々の変形や修正を行うことが容易であることに注意されたい。従って、これらの変形や修正は本発明の範囲に含まれることに留意されたい。例えば、各構成部、各ステップなどに含まれる機能などは論理的に矛盾しないように再配置可能であり、複数の構成部やステップなどを１つに組み合わせたり、或いは分割したりすることが可能である。また、本発明について装置を中心に説明してきたが、本発明は装置が備えるプロセッサにより実行される方法、プログラム、またはプログラムを記録した記憶媒体としても実現し得るものであり、本発明の範囲にはこれらも包含されるものと理解されたい。
【符号の説明】
【０１３２】
１００  画像領域分割装置
１１０  入力部
１２０  記憶部
１３０  演算部
１３１  推移行列計算部
１３２  ランダムウォーク特徴量計算部
１３３  類似度計算部
１３４  乖離情報計算部
１３５  候補特徴量計算部
１３６  候補クラスタリング部
１３７  領域番号計算部
１４０  出力部
【図１】
2015090642.tif 000054
【図２】
2015090642.tif 000055
【図３】
2015090642.tif 000056
【図４】
2015090642.tif 000057
【図５】
2015090642.tif 000058
【図６】
2015090642.tif 000059
【図７】
2015090642.tif 000060
【図８】
2015090642.tif 000061
【図９】
2015090642.tif 000062
【図１０】
2015090642.tif 000063
【図１１】
2015090642.tif 000064
【図１２】
2015090642.tif 000065
【図１３】
2015090642.tif 000066
【図１４】
2015090642.tif 000067
【図１５】
2015090642.tif 000068