(57)【特許請求の範囲】
【請求項１】
画像をスーパーピクセルにセグメント化する方法であって、
頂点が枝によって連結されたグラフを構築するステップであって、各頂点は、前記画像内のピクセルに対応し、各枝は、該対応するピクセルの類似度を示す重みに関連付けられる、構築するステップと、
前記グラフ内の枝の部分集合を選択するステップであって、前記グラフを複数の部分グラフにセグメント化し、該選択することは目的関数を最大にし、該目的関数は劣モジュラであり、該目的関数は、一様なスーパーピクセルを生成するための前記グラフ上のランダムウォークのエントロピーレートと、バランス項とを含み、該バランス項は、同様のサイズのセグメントの数を最大にするセグメントのメンバーシップの分布のエントロピーコンポーネントと、セグメントの数を最小にする連結された部分グラフのコンポーネントの数とを含む、選択するステップと、
部分グラフの数が或るしきい値に等しくなるまで、最大利得を有する前記枝を前記グラフに追加するステップと、前記部分グラフの数が前記しきい値未満の場合には、前記選択するステップ及び前記追加するステップを繰り返すステップと、
を含み、
各前記ステップはプロセッサが実行する、画像をスーパーピクセルにセグメント化する方法。
【請求項２】
各部分グラフは、一様なかつ同様のサイズのスーパーピクセルを含む、請求項１に記載の方法。
【請求項３】
前記エントロピーレートは、劣モジュラ及び単調増加である、請求項１に記載の方法。
【請求項４】
前記バランス項は、劣モジュラ及び単調増加である、請求項１に記載の方法。
【請求項５】
無閉路グラフにおける部分グラフの数に対する制約がマトロイドである、請求項１に記載の方法。
【請求項６】
目的関数は、或る制約を条件として、貪欲プロセスを用いて最大にされる、請求項１に記載の方法。
【請求項７】
最適性が、前記目的関数の大域的最小値の１／２となるように保証される、請求項１に記載の方法。
【請求項８】
前記貪欲プロセスは、ヒープ構造を用いて実施される、請求項６に記載の方法。
【請求項９】
前記セグメント化は階層的に達成される、請求項１に記載の方法。
【請求項１０】
前記階層は、前記画像の複数のセグメント化を同時に形成する、請求項９に記載の方法。
【請求項１１】
前記バランス項のバランスパラメータは、自動的に調節される、請求項１に記載の方法。
【請求項１２】
前記バランス項のバランスパラメータは、セグメント化をカスタマイズするようにユーザーによって変更される、請求項１に記載の方法。
【請求項１３】
前記セグメント化は、ユーザーの監視を伴って対話的に実行される、請求項１に記載の方法。
【請求項１４】
非画像領域における一般的なクラスタリング問題が解かれる、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、ピクセルをセグメント化することに関し、より詳細には、スーパーピクセルを用いて画像をセグメント化することに関する。
【背景技術】
【０００２】
本技術分野では一般に、スーパーピクセルとは、デジタル画像において、単一のピクセルよりも大きな多角形ピクセルクラスターであり、同じ色及び明るさでレンダリングすることができる（米国特許第７，７４４，１８５号を参照）。
【０００３】
スーパーピクセルのセグメント化は、物体認識、画像セグメント化、及び３Ｄ再構築の用途において用いられる。スーパーピクセルを用いる１つの主な利点は、計算効率である。スーパーピクセル表現は、ピクセル表現と比較して、必要とされる画像プリミティブの数を大幅に削減する。
【０００４】
例えば、Ｌラベルラベリング問題では、ピクセル表現の解空間はＬｎであり、ここで、ｎはピクセル数であり、通常１０６個である。一方、スーパーピクセル表現の解空間はＬｍであり、ここで、ｍはスーパーピクセル数であり、通常１０２個である。
【０００５】
スーパーピクセルは単一の物体からの一組のピクセルであると一般に仮定される。これは、スーパーピクセルセグメント化の実際的な定義につながり、この定義は、画像内のピクセルを、知覚的に一貫したクラスターに分割する。一貫した知覚的特性は、スーパーピクセルの境界が物体の境界を維持していることを暗に意味する。
【０００６】
ほとんどのクラスタリングプロセスは、スーパーピクセルセグメント化として特徴付けることができる。しかしながら、従来のプロセスのほとんどはクラスターの一般的側面をモデル化し、スーパーピクセルセグメント化用に最適化されていない。その上、多くのプロセスは、集中的な計算を必要とし、セグメント化には適していない。
【０００７】
１つの方法は、グラフに基づくスーパーピクセルセグメント化を用いるものである。画像は近傍グラフにマッピングされる。この方法は、境界述語（boundary predicate）を用いて、スーパーピクセルを構築するために枝（edges）を順次切断する。この方法は、高速ではあるが、不規則な形状及びサイズを有するスーパーピクセルを生成する。
【０００８】
平均値シフト法（mean-shift method）は、局所的な変動には正確であるが、この方法もスーパーピクセルが不規則になるという問題を欠点として有する（特許文献１を参照）。
【０００９】
スーパーピクセルセグメント化のための別の方法は、ＮＣｕｔである（特許文献２を参照）。ＮＣｕｔは、同様のサイズ及びコンパクトな形状を有するスーパーピクセルを生成する。しかしながら、この方法も、計算コストが高く、適度なサイズの画像、例えば４８１×３２１ピクセルであっても数分を要する。
【００１０】
ターボピクセル（TurboPixel）は、同様の規則性を達成する効率的な代替手段である。ターボピクセルは、画像に一様に配置されたシードから曲線を展開することに基づいている。ターボピクセルは、曲線展開中にさまざまな制約を用いて、スーパーピクセルの規則性を実施する。
【００１１】
グラフ切断は、高密度パッチ割当て技法を通じて規則的なスーパーピクセルを達成するのに用いることができる。別の方法では、スーパーピクセルは、切断コストを規定する確率的境界マップを用いて規則的なグリッドと一致する。この方法で用いられている目的関数によって、画像間の同形写像が可能になる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】米国特許出願公開第２０１００２８４６０７号
【特許文献２】米国特許出願公開第２０１１００１３８３７号
【発明の概要】
【００１３】
本発明の実施の形態は、クラスタリング目的関数を用いて、画像をスーパーピクセルにセグメント化する方法を提供する。この目的関数は、２つの構成要素、すなわち、ランダムウォークのエントロピーレート（entropy rate of a random walk）と、バランス関数（balancing function）とを含む。エントロピーレートは、コンパクトで一様な（homogeneous）クラスターを形成する一方、バランス関数は、同様のサイズを有するクラスターを生成する。
【００１４】
クラスタリングについて、データ点（data point）が頂点に対応し、ペアワイズ類似度（pair-wise similarities）が枝重み（edge weights）に対応するグラフを構築する。本発明は、マトロイド制約を条件として、目的関数を最大にすることによってグラフを分割する。
【００１５】
本発明は、貪欲プロセス（greedy process）を用いて目的関数を解き、目的関数の劣モジュラ性（submodularity）及び単調性（monotonicity）を利用して、一定の近似限界を証明する。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態に係る、枝がクラスター形成において未選択な場合の重みの一例を示した概略図である。
【図２】本発明の一実施形態に係る、ランダムウォークのエントロピーレートの例（Ａ）〜（Ｄ）を示した概略図である。
【図３】本発明の一実施形態に係る、同様のサイズのクラスターを得る際のバランス関数の例（Ａ）〜（Ｂ）を示した概略図である。
【図４】本発明の一実施形態に係る、解放のアルゴリズムを示した概略図である。
【図５】本発明の一実施形態に係る、セグメント化中のスーパーピクセル階層を生成する凝集性を示した概略図である。
【図６】本発明の一実施形態に係る、基本的なステップと示した概略図である。
【発明を実施するための形態】
【００１７】
グラフ表現
本発明は、画像内のピクセルを表す無向グラフ（undirected graph）には、従来の表記Ｇ＝（Ｖ，Ｅ）を用いる。ここで、Ｖはピクセルに対応する頂点集合であり、Ｅは枝集合である。Ｖのｉ番目の頂点はｖｉによって表され、頂点ｖｉと頂点ｖｊとを接続する枝はｅｉ，ｊによって表される。重み関数ｗは、枝によって連結された２つの頂点間の類似度を与える。無向グラフでは、枝のインデックスは交換可能であり、ｅｉ，ｊ＝ｅｊ，ｉであり、枝重みは対称的であり、ｗｉ，ｊ＝ｗｊ，ｉである。
【００１８】
グラフ分割
グラフ分割Ｓとは、集合Ｖを互いに素な部分集合Ｓ＝｛Ｓ１，Ｓ２，．．．，ＳＫ｝に分割することをいう。互いに素な部分集合Ｓは、
【数１】
0005734235.tif 000002
となる集合である。グラフ分割は部分集合選択問題である。本発明の目的（goal）は、結果のグラフ（Ｖ，Ａ）がＫ個の連結部分グラフ（連結構成要素）を有するように、集合Ｅ内の枝の部分集合Ａを選択することである。結果の各部分グラフがスーパーピクセルに対応する。
【００１９】
エントロピー
エントロピーＨは、確率変数の不確実性の尺度を示す。条件付き確率質量関数ｐＸを有する離散確率変数Ｘのエントロピーは、下記の式（１）で求めることができる。
【００２０】
【数２】
0005734235.tif 000003
【００２１】
ここで、
【数３】
0005734235.tif 000004
は確率変数Ｘの台集合（support）である。条件付きエントロピーＨ（Ｘ｜Ｙ）は、相関確率変数Ｙの値が既知であるとすると、確率変数Ｘの残りの不確実性を定量化する。条件付きエントロピーＨ（Ｘ｜Ｙ）は、下記の式（２）で定義される。
【００２２】
【数４】
0005734235.tif 000005
【００２３】
ここで、
【数５】
0005734235.tif 000006
は、Ｙの台集合であり、ｐＸ｜Ｙは条件付き確率質量関数である。
【００２４】
エントロピーレート
エントロピーレートは、確率過程Ｘ＝｛Ｘｔ，ｔ∈Ｔ｝の不確実性を定量化する。ここで、Ｔはインデックス集合である。離散ランダム過程の場合、エントロピーレートは、下記の式（３）で示される漸近測度として、定義される。
【００２５】
【数６】
0005734235.tif 000007
【００２６】
エントロピーレートは、過去の先行する軌線を観測した後のランダム過程の残りの不確実性の尺度を示す。定常確率過程の場合、式３における極限が常に存在する。定常１次マルコフ過程の場合、エントロピーレートは、下式の形を有する。
【００２７】
【数７】
0005734235.tif 000008
【００２８】
最初の等式は、１次マルコフ性に起因するものであり、２番目の等式は、定常性の帰結である。Ｈ（Ｘ２｜Ｘ１）は時間非依存であるので、本発明においては、極限（limit）を省くことにする。
【００２９】
ランダムウォーク
ランダムウォークは、グラフ上の確率過程である。非負の類似尺度ｗを有するグラフＧ＝（Ｖ，Ｅ）上のランダムウォークをＸ＝｛Ｘｔ，ｔ∈Ｔ，Ｘｔ∈Ｖ｝とする。ランダムウォークＸは、１つの頂点から他の頂点への連続したランダムなジャンプで構成される軌線である。本発明においては、従来の構築法を用いることにする。頂点ｖｉからｖｊへの遷移確率は、関連付けられた枝重みに比例し、下記の式（４）で定義される。
【００３０】
【数８】
0005734235.tif 000009
【００３１】
ここで、
【００３２】
【数９】
0005734235.tif 000010
【００３３】
は、ｖｉのインシデント重み（incident weight：付帯する重み）の和である。
【００３４】
定常分布は、下記の式（５）である。
【００３５】
【数１０】
0005734235.tif 000011
【００３６】
ここで、
【数１１】
0005734235.tif 000012
は、正規化定数である。
【００３７】
特定の頂点上のランダムウォークが、頂点の総インシデント重みに比例する確率について説明する。非連結グラフの場合、定常分布は唯一のものとはならない。しかしながら、式（５）のμは、常に定常分布である。これは、μ＝ＰＴμを通じて検証することができる。ここで、Ｐ＝［ｐ］ｉ，ｊは遷移行列である。ランダムウォークのエントロピーレートは、式（２）を適用することによって、下記の式（６）で求めることができる。
【００３８】
【数１２】
0005734235.tif 000013
【００３９】
劣モジュラ性
劣モジュラ関数の定義を用いることにする。有限集合をＥとする。集合関数Ｆは、全ての
【数１３】
0005734235.tif 000014
について、下記の（７）式である場合に、劣モジュラである。
【００４０】
【数１４】
0005734235.tif 000015
【００４１】
この特性は、収量逓減特性（diminishing return property）としての別名を有し、すなわち、モジュールの影響は、後段で用いられる場合に後段になるほど小さくなる。
【００４２】
厳密単調増加集合関数
集合関数Ｆは、
【数１５】
0005734235.tif 000016
である場合に、厳密単調増加である。
【００４３】
マトロイド
マトロイドは、有限集合Ｅと、次の３つの条件を満たす集合Ｅの部分集合の系（collection）Ｉとを含む順序対Ｍ＝（Ｅ，Ｉ）である。
【数１６】
0005734235.tif 000017
【数１７】
0005734235.tif 000018
【数１８】
0005734235.tif 000019
【００４４】
本発明の目的関数は、単調増加及び劣モジュラである。これを示すために、エントロピーレート及びエントロピーの等価な集合関数を説明することにする。単調増加劣モジュラ関数を最大にすることはＮＰ困難である。しかしながら、マトロイド表現を用いてグラフ分割問題を定式化し、単純な貪欲プロセスが１／２近似限界を与えることを証明することにする。
【００４５】
エントロピーレートクラスタリング
グラフ構築
ピクセルを示す頂点と、類似度行列の形で与えられるペアワイズ類似度を示す枝重みとを有する連結グラフＧ＝（Ｖ，Ｅ）を画像から構築する。また、グラフのあらゆる頂点が０の重みを有する自己ループを有するものと仮定する。グラフを分割するように枝の部分集合を選択すると、未選択の枝の重みは、結果のグラフ内に配分されて戻される。ループがデフォルトで選択され、集合Ｅには存在しない。選択されていない枝ごとに、各頂点の総インシデント重みが定数を維持するように、関連付けられた頂点のループの枝重みを増加させる。
【００４６】
図１に示すように、枝ｅｉ，ｊ１０１がクラスター形成において未選択である場合、対応する重みｗｉ，ｊは、２つの頂点のループ１０２に再配分される。
【００４７】
この構築は式（５）を変えることはない。これは、枝が順次選択される反復プロセスにとって重要である。このグラフ構築の下では、遷移確率の等価な集合関数ｐｉ，ｊは、下記の式（８）である。
【００４８】
【数１９】
0005734235.tif 000020
【００４９】
ここで、Ａは分割のために選択された枝の集合である。その結果、ランダムウォークのエントロピーレートは、下記の（９）式で示される等価な集合関数を有する。
【００５０】
【数２０】
0005734235.tif 000021
【００５１】
エントロピーレート
図２Ａ〜図２Ｄに示すように、ランダムウォークのエントロピーレートを、その関連付けられたグラフ上で、一様かつコンパクトなクラスターを得るための判定基準として用いる。図２Ａ及び図２Ｂは１つのデータセットに対応する一方、図２Ｃ及び図２Ｄは別のデータセットに対応する。あらゆる頂点がループを有するが、これらのループは図示されていない。図２Ａにおけるコンパクトなクラスターのエントロピーレートは、図２Ｂにおけるコンパクト性に劣るクラスターのエントロピーレートよりも高い目的値（objective value）を有する。図２Ｃにおける一様なクラスターのエントロピーレートは、図２Ｄにおける一様性に劣るクラスターよりも高い目的値を有する。
【００５２】
本発明は、ガウスカーネルを用いて、距離を類似度に変換する。これらのグラフ分割のそれぞれにおいて、連結構成要素として４つの異なるクラスターが示される。一様かつコンパクトなクラスターは、より大きなエントロピーレートを与える。どの枝の選択も或る値だけエントロピーレートを増加させるが、この増加は、コンパクトかつ一様なクラスターから枝を選択する場合に、より大きなものとなる。
【００５３】
本発明で提案されたグラフ構築法の下でのランダムウォークのエントロピーレートは単調増加劣モジュラ関数である。枝を追加することによって、不確実性が増加するので、エントロピーレートは単調増加である。収量逓減特性は、枝を選択することによる不確実性の増加が、後段になるほど小さくなるということに由来する。その理由は、後段は、より多くの枝と共有されるからである。
【００５４】
したがって、グラフ上のランダムウォーク
【数２１】
0005734235.tif 000022
は、本発明のグラフ構築法の下では単調増加劣モジュラ関数である。
【００５５】
バランス関数
同様のサイズを有するクラスターを促進するバランス関数を説明する。選択された枝集合をＡとし、グラフ内の連結された部分グラフの数をＮＡとし、クラスターメンバーシップの分布をＺＡとする。分割｛Ｓ１，Ｓ２，．．．，ＳNA｝について、ＺＡの分布は、下記の式（１０）に等しく、
【００５６】
【数２２】
0005734235.tif 000023
【００５７】
バランス項は、下記の式（１１），（１２）によって与えられる。
【００５８】
【数２３】
0005734235.tif 000024
【００５９】
エントロピーＨ（ＺＡ）は、同様のサイズを有するクラスターに有利に働くのに対して、ＮＡはより少ない数のクラスターに有利に働く。
【００６０】
図３Ａ及び図３Ｂは、同様のサイズのクラスターを得る際のバランス関数の役割を示している。連結構成要素は、データセット内のさまざまなクラスターを示している。バランス関数は、図３Ｂにおけるバランス性に劣るクラスタリングと比較して、図３Ａにおけるバランスされたクラスタリングに対してより高い目的値を有する。
【００６１】
エントロピーレートと同様に、バランス関数も単調増加劣モジュラ関数である。
【００６２】
本発明では、エントロピーレート及びバランス関数を組み合わせて、コンパクトで一様でかつバランスされたクラスターを求める、下記の式（１３）で示される部分集合選択問題を解く。
【００６３】
【数２４】
0005734235.tif 000025
【００６４】
式（１３）におけるパラメーターλ＞０は、バランス重みであり、このバランス重みは、クラスタリングをバランスさせるときの優先権（preference）を制御するのに用いられる。
【００６５】
上記に基づくと、下記の式（１４）の目的関数は、単調増加劣モジュラ関数である。
【００６６】
【数２５】
0005734235.tif 000026
【００６７】
クラスターを結合することは、バランス項の利得（gain）になるので、全ての局所最適解において正確にＫ個のクラスターが存在することが保証される。
【００６８】
貪欲ヒューリスティック
劣モジュラ集合関数を最大にする１つのプロセスは貪欲プロセスを用いる。このプロセスは、空集合（完全非連結グラフ、
【数２６】
0005734235.tif 000027
）から開始し、枝を集合に順次追加する。各反復において、このプロセスは最大の利得を与える枝を追加する。反復は、連結された部分グラフの数が事前に設定された数ＮＡ＝Ｋに達すると停止する。
【００６９】
更なる高速化を達成するために、枝集合Ａが閉路を含むことができないように、枝集合Ａに対して付加的な制約を課す。この制約は、連結された部分グラフ内の付加的な枝を直ちに無視し、貪欲探索における評価の回数を削減する。これらの枝はグラフの分割を変更しない。この制約によって、解空間は、元の問題と比較してより小さくなり（木構造の部分グラフのみが許容される）、実際に、クラスタリング結果は非常に類似する。
【００７０】
クラスター数の制約ＮＡ≧Ｋとともに、この無閉路制約によって、マトロイドＭ＝（Ｅ，Ｉ）を含む独立集合の定義が得られる。枝Ｅが枝集合であり、かつ、Ｅの部分集合Ａのうちの、枝集合Ａが無閉路である集合がＩであり、Ｋ個以上の連結構成要素を有するグラフ分割を構成する場合、対Ｍ＝（Ｅ，Ｉ）はマトロイドである。
【００７１】
グラフ分割問題を再定式化したものは、下記の式（１５）であり、解法のアルゴリズムは図４に示されている。
【００７２】
【数２７】
0005734235.tif 000028
【００７３】
貪欲プロセスは、マトロイド制約を条件として、非減少劣モジュラ関数を最大にする１／２近似を与えるので、図４に示すようなプロセスは、式（１５）を解く１／２近似を示している。
【００７４】
効率的な実施態様
本発明は、最初に、各枝をＡに追加する利得を計算し、ヒープを構築する。各反復において、最大利得を有する枝がヒープから除去され、Ａに含められる。この枝を含めることは、ヒープ内の残りの枝のうちのいくつかのものの利得に影響を与える。したがって、ヒープを更新する必要がある。しかしながら、劣モジュラ特性によって、ヒープ構造の効率的な更新が可能になる。重要な知見は、全体にわたって、すなわち、各枝の利得は決して増加することができないということであり、すなわち（i.e.）、収量逓減特性である。したがって、最も上の要素の利得は更新されるが、他の要素は必ずしも更新されない場合、ヒープを維持することで十分である。ヒープの最も上の要素は更新され、他の要素の値は減少することしかできないので、最も上の要素は最大値である。
【００７５】
実際には、このプロセスは、単純な機器（implementation）よりもはるかに高速に動作する。平均すると、各反復において、ヒープに対して更新はほとんど行わない。本発明における実験では、このプロセスは、画像サイズ４８１×３２１に対して２００倍〜３００倍の高速化を提供する。
【００７６】
図６は、本発明の１つの実施形態の基本的なステップを示している。入力は画像６０１である。本発明においては、頂点が枝によって連結されたグラフを構築する（６１０）。各頂点は画像内のピクセルに対応し、各枝は、該対応するピクセルの類似度を示す重みに関連付けられる。最初に、グラフは枝も一切含んでいない。目的関数は、枝をグラフに順次追加する貪欲プロセスを用いて最大にされる。
【００７７】
本発明では、目的関数に基づいて、各枝をグラフに追加する利得を求める（６２０）。目的関数は、エントロピーレート及びバランス項を含む（６０２）。
【００７８】
利得に従って枝をソートし（６３０）、最大利得を有する枝をグラフに追加する（６４０）。
【００７９】
本発明では、連結された部分グラフの数が或るしきい値Ｋに等しいか否かを判断する。偽である場合、ステップ６２０、ステップ６３０、及びステップ６４０を繰り返す。真である場合、所望のスーパーピクセルが得られる（６０３）。
【００８０】
方法６００のステップは、当該技術分野において知られているように、メモリ及び入出力インターフェースに接続されたプロセッサにおいて実行することができる。
【００８１】
自動パラメーター調節
本発明では、バランスパラメーターλを自動的に調整する方法を説明することにする。ユーザーが指定した初期値λ’が与えられると、最終的なバランスパラメーターλは、（１）スーパーピクセルの数Ｋ、及び（２）入力画像から計算されるデータ依存動的パラメーターβに基づいて調整される。クラスター数Ｋは、多数のスーパーピクセルが必要とされるときに、バランス項をより重要視するために導入される。データ依存項は、単一の枝をグラフに含めたときの最大限のエントロピーレートの増加と最大限のバランス項の増加との比は、下記の式によって与えられ、
【００８２】
【数２８】
0005734235.tif 000029
【００８３】
目的関数におけるこれらの２つの項の大きさの差（magnitude difference）を補償する。最終的なバランスパラメーターは、λ＝βＫλ’によって与えられる。
【００８４】
スーパーピクセル階層
セグメント化プロセスは、別々のクラスターとしての各ピクセルから開始し、クラスターを次第に結合して、より大きなスーパーピクセルを構築する。このセグメント化階層は、画像の複数のセグメント化を同時に引き起こす。用途に基づいて、セグメント化におけるスーパーピクセルの正確な数を選択することができる。図５は、セグメント化中のスーパーピクセル階層を生成するこの凝集性を示している。
【００８５】
階層は、対話型編集、又は複数のスーパーピクセルのセグメント化からの情報を利用するアルゴリズム等の多くの視覚アプリケーションにとって有用である。初期セグメント化が完了した後、ユーザーは、特定のスーパーピクセルを選択し、階層に基づいてこれらのスーパーピクセルを更に統合又は分割することができる。これは、スーパーピクセルが複数の器官を含む場合があり、そのスーパーピクセルの更なるグループ化／セグメント化が器官の分離を引き起こす医療用のセグメント化等の対話型解析にとって重要である。
【００８６】
一般的なクラスタリング
本発明を画像セグメント化について説明してきたが、本方法は、どのクラスタリング問題にも適用される。画像のピクセルの代わりに点の集合が与えられると、それらの点の間の類似度を距離メトリックに基づいて定義することができる。その後、同じグラフ構築法が、点がグラフの頂点であるとともに枝が点をそのＬ個の最近傍点に接続するこの一般的な点の集合に適用される。説明したアルゴリズムは、この点集合のクラスタリングを引き起こす。
【００８７】
一般的なクラスタリングの領域は、データマイニング、財務、バイオインフォマティクス、医薬、神経科学等を含むが、これらに限定されるものではない。
【００８８】
発明の効果
本発明は、スーパーピクセルを生成する新規なクラスタリング目的関数を提供する。クラスタリング目的関数は、グラフ上のランダムウォークのエントロピーレートとバランス関数との組み合わせを最大にすることに基づいている。目的関数の劣モジュラ性及びマトロイド表現を用い、貪欲プロセスを用いて目的関数を最大にする問題を解く。
【図１】
0005734235.tif 000030
【図２】
0005734235.tif 000031
【図３】
0005734235.tif 000032
【図４】
0005734235.tif 000033
【図５】
0005734235.tif 000034
【図６】
0005734235.tif 000035