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