(57)【要約】【課題】階層グラフに基づく画像マッティングおよび前景推定の方法およびシステムを提供する。【解決手段】階層グラフモデルに基づく画像マッティング方法は、複数の画像要素を含む入力画像を受信することと；入力画像に基づいて、それぞれ１組の画像要素を含む複数のマッティングセルを生成することと；入力画像に基づいて、複数のマッティングセルのアフィニティ値を計算することと；複数のマッティングセルおよびアフィニティ値に基づいて、マッティングセルを示す複数のノードおよびマッティングセルのアフィニティ値と関連する複数のエッジを含むグラフを形成することと；グラフに基づいて、入力画像の複数のマッティングコンポーネントを生成することを含む。【選択図】図１３
2016062588.tif 000002
【特許請求の範囲】
【請求項１】
複数の画像要素を含む入力画像を受信することと、
前記入力画像に基づいて、それぞれ１組の前記画像要素を含む複数のマッティングセルを生成することと、
前記入力画像に基づいて、前記マッティングセルのアフィニティ値を計算することと、
前記マッティングセルおよび前記アフィニティ値に基づいて、前記マッティングセルを示す複数のノードおよび前記マッティングセルの前記アフィニティ値と関連する複数のエッジを含むグラフを形成することと、
前記グラフに基づいて、前記入力画像の複数のマッティングコンポーネントを生成することと
を含む階層グラフモデルに基づく画像マッティングおよび前景推定の方法。
【請求項２】
前記入力画像の前景領域に属する前記マッティングコンポーネントの中の少なくとも１つを識別することをさらに含む請求項１に記載の方法。
【請求項３】
前記グラフが、第１グラフであり、前記マッティングセルを生成する前記ステップが、さらに、
前記入力画像に基づいて、前記画像要素を示す複数の第２ノードおよび前記画像要素間のアフィニティ情報を示す複数の第２エッジを含む第２グラフを形成することと、
前記第２グラフに基づいて、前記入力画像から収縮画像を生成することと
を含む請求項１に記載の方法。
【請求項４】
前記画像要素の正規座標を定義することと、
前記画像要素の前記正規座標および前記アフィニティ情報に基づいて、前記画像要素の収縮座標を計算することと
をさらに含む請求項３に記載の方法。
【請求項５】
前記画像要素の前記収縮座標に部分的に基づいて、前記マッティングセルを生成することをさらに含む請求項４に記載の方法。
【請求項６】
前記画像要素の前記収縮座標および色値に基づいて、座標システムを定義することと、
前記座標システムに基づいて、前記画像要素を前記マッティングセルにマッピングして、前記マッティングセルを生成することと
をさらに含む請求項５に記載の方法。
【請求項７】
前記マッティングセルの前記アフィニティ値を計算する前記ステップが、さらに、
前記入力画像から複数のダウンサンプリング画像を生成することと、
前記ダウンサンプリング画像および前記入力画像から複数の画像パッチを抽出することと、
前記画像パッチに基づいて、前記マッティングセルの前記アフィニティ値を確定することと
を含む請求項１に記載の方法。
【請求項８】
前記マッティングセル内の画像要素に基づいて、前記各マッティングセルの特徴ベクトルを確定することと、
前記特徴ベクトルにアフィン変換を応用して、前記セルの前記アフィニティ値を計算することと
をさらに含む請求項７に記載の方法。
【請求項９】
前記グラフが、第１グラフであり、前記方法が、さらに、
前記マッティングセルの前記アフィニティ値に基づいて、全体的誤差関数を定義することと、
前記マッティングセルに基づいて、第２グラフを形成することと、
前記全体的誤差関数に基づいて、前記第２グラフのラプラシアン行列を確定することと
を含む請求項８に記載の方法。
【請求項１０】
前記全面的誤差関数を定義する前記ステップが、さらに、
前記各画像パッチの誤差関数を定義することと、
前記画像パッチの前記誤差関数の加重和を計算することにより、前記全面的誤差関数を定義することと
を含み、前記全面的誤差関数が、前記画像パッチの相対的重要性を示す前記各画像パッチのウェイトを含む請求項９に記載の方法。
【請求項１１】
次数行列を用いて前記ラプラシアン行列を正規化することをさらに含む請求項９に記載の方法。
【請求項１２】
前記マッティングセルを生成する前記ステップが、さらに、
前記正規化されたラプラシアン行列に基づいて、前記グラフに対してスペクトラルクラスタリングを行い、前記グラフから複数のセグメントを生成することと、
前記セグメントを精緻化することによって、前記セグメントから前記マッティングコンポーネントを生成することと
を含む請求項１１に記載の方法。
【請求項１３】
前記マッティングコンポーネント間のアフィニティ関係に基づいて、前記マッティングコンポーネントをグループ化し、複数のレイヤーを生成することをさらに含む請求項１２に記載の方法。
【請求項１４】
前記マッティングコンポーネントが前記入力画像の前記前景領域に属する確率を確定することをさらに含む請求項２に記載の方法。
【請求項１５】
前記グラフが、第１グラフであり、前記方法が、さらに、
前記マッティングコンポーネントに基づいて、前記マッティングコンポーネントを示す複数の第２ノードおよび前記マッティングコンポーネント間のアフィニティ関係を示す複数の第２エッジを含む第２グラフを形成することと、
前記第２グラフに基づいて、ラプラシアン行列を計算することと、
前記ラプラシアン行列に基づいて、前記確率を確定することと
を含む請求項１４に記載の方法。
【請求項１６】
前記ラプラシアン行列に基づいて、不一致性測度を定義することと、
前記不一致性測度に基づいて、前記確率を確定することと
を含む請求項１５に記載の方法。
【請求項１７】
複数の画像要素を含む入力画像を受信することと、
前記入力画像に基づいて、前記画像要素を示す複数の第１ノードおよび前記画像要素間のアフィニティ関係を示す複数の第１エッジを含む第１グラフを形成することと、
前記画像要素を複数のセルにグループ化して、前記セルを示す複数の第２ノードおよび前記セル間のアフィニティ関係を示す複数の第２エッジを含む第２グラフを形成することと、
前記第２グラフを複数のマッティングコンポーネントに分解して、前記マッティングコンポーネントを示す複数の第３ノードおよび前記マッティングコンポーネント間のアフィニティ関係を示す複数のエッジを含む第３グラフを形成することと、
前記第３グラフに基づいて、前記マッティングコンポーネントが前記入力画像の前景領域に属する確率を確定することと
を含む階層グラフモデルに基づく画像マッティングおよび前景推定の方法。
【請求項１８】
前記第２グラフを形成する前記ステップが、さらに、
前記入力画像に収縮プロセスを応用することと、
前記収縮した入力画像および前記第１グラフに基づいて、前記画像要素を前記セルにマッピングすることと
を含む請求項１７に記載の方法。
【請求項１９】
前記第２グラフを形成する前記ステップが、さらに、
前記入力画像に対してダウンサンプリングを再帰的に行うことによって、画像ピラミッドを生成することと、
前記画像ピラミッドから複数の画像パッチを抽出することと、
前記画像パッチに基づいて、前記セル間の前記アフィニティ関係を確定することと
を含む請求項１７に記載の方法。
【請求項２０】
プロセッサで実行する時に、階層グラフに基づく画像マッティングおよび前景推定の方法を前記プロセッサに実行させる指令を記憶する非一時的なコンピュータ可読記憶媒体であって、前記方法が、
複数の画像要素を含む入力画像を受信することと、
前記入力画像に基づいて、それぞれ１組の画像要素を含む複数のマッティングセルを生成することと、
前記入力画像に基づいて、前記マッティングセルのアフィニティ値を計算することと、
前記マッティングセルおよび前記アフィニティ値に基づいて、前記マッティングセルを示す複数のノードおよび前記マッティングセルのアフィニティ情報を示す複数のエッジを含むグラフを形成することと、
前記グラフに基づいて、前記入力画像の複数のマッティングコンポーネントを生成することと
を含む非一時的なコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像マッティング（image matting）に関するものであり、特に、階層（hierarchical）グラフに基づく画像マッティングおよび前景推定に関するものである。
【背景技術】
【０００２】
画像マッティングは、アルファマットと称されるパラメータとともに画像から前景物体を抽出するプロセスである。このプロセスは、例えば、画像や映像の編集、画像レイヤー分解、シーン解析等の有益な応用につながる。画像マッティングにおいて、ピクセルｉのピクセル値Ｉｉは、以下のように、前景色値Ｆｉと背景色値Ｂｉの線形結合をモデルとすることができる。
【０００３】
【数１】
2016062588.tif 000003
【０００４】
式中、αiは、前景色の不透明度（opacity）に対応するアルファマット値を示す。
【０００５】
従来の画像マッティング技術は、一般的に、教師あり（supervised）マッティングと教師なし（unsupervised）マッティングの２種類に分けることができる。教師ありマッティングは、ユーザーの指示により、いくつかのピクセルを「前景」または「背景」のいずれかに標記する。教師ありマッティング法は、これらの標記されたピクセルに基づいて、残りの標記されていないピクセルのアルファマット値を推定する。反対に、教師なしマッティングは、ユーザーの指示なしに入力画像から自動的にアルファマットを推定するのが目的である。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来の画像マッティング技術には、いくつかの欠点がある。まず、従来の教師なしマッティング技術は、計算集約型である。必要とされる計算を減らすための画像処理スキームは既に提案されているが、これらの既存のスキームは、画像品質を低下させる可能性がある。
【０００７】
第２に、従来の画像マッティング技術により作り出される結果は、常に一致しているとは限らない。マッティング過程中に全体的な（global）情報が欠乏すると、乱雑な情景を有する画像を取り扱う時に、一致した結果を作り出すのが難しくなる。
【０００８】
第３に、従来の教師なしマッティング技術は、画像内容の２分割（binary partitioning）に焦点を当てている。画像は、１つ以上の前景物体を含むことができるため、これらの従来の教師なしマッティング技術により作り出される結果は、あまり実用的なものではない。
【課題を解決するための手段】
【０００９】
本発明の１つの実施形態において、階層グラフモデルに基づく画像マッティング方法は、複数の画像要素（element）を含む入力画像を受信することと；入力画像に基づいて、それぞれ１組の画像要素を含む複数のマッティングセルを生成することと；入力画像に基づいて、複数のマッティングセルのアフィニティ値を計算することと；複数のマッティングセルおよびアフィニティ値に基づいて、マッティングセルを示す複数のノードおよびマッティングセルのアフィニティ値と関連する複数のエッジを含むグラフを形成することと；グラフに基づいて、入力画像の複数のマッティングコンポーネントを生成することを含む。
【００１０】
本発明の別の実施形態において、階層グラフに基づく画像マッティング方法は、複数の画像要素を含む入力画像を受信することと；入力画像に基づいて、画像要素を表示する複数の第１ノードおよび画像要素間のアフィニティ関係を表示する複数の第１エッジを含む第１グラフを形成することと；画像要素を複数のセルにグループ化して、セルを表示する複数の第２ノードおよびセル間のアフィニティ関係を表示する複数の第２エッジを含む第２グラフを形成することと；第２グラフを複数のマッティングコンポーネントに分解して、マッティングコンポーネントを表示する複数の第３ノードおよびマッティングコンポーネント間のアフィニティ関係を表示する複数のエッジを含む第３グラフを形成することと；第３グラフに基づいて、マッティングコンポーネントが入力画像の前景領域に属する確率を確定することを含む。
【００１１】
本発明の別の実施形態において、非一時的なコンピュータ可読記憶媒体は、プロセッサで実行する時に、階層グラフに基づく画像マッティング方法をプロセッサに実行させる指令を記憶する。前記方法は、複数の画像要素を含む入力画像を受信することと；入力画像に基づいて、それぞれ１組の画像要素を含む複数のマッティングセルを生成することと；入力画像に基づいて、複数のマッティングセルのアフィニティ値を計算することと；複数のマッティングセルおよびアフィニティ値に基づいて、マッティングセルを表示する複数のノードおよびマッティングセルのアフィニティ情報を表示する複数のエッジを含むグラフを形成することと；グラフに基づいて、入力画像の複数のマッティングコンポーネントを生成することを含む。
【００１２】
本発明の他の特徴および利点が以下の説明において部分的に述べられ、これらの特徴および利点は、説明から部分的に明らかになり、あるいは、本発明の実施例によって習得されるであろう。これらの特徴および利点は、添付の特許請求の範囲において特別に指摘した要素および組み合わせによって実現および達成されるであろう。
【００１３】
上記の一般的な記載および以下の詳細な説明は、例示的および解釈的なものであり、本発明を限定するものではないことを理解されたい。
【００１４】
本明細書に含まれ、且つ本明細書の一部を構成する添付の図面は、いくつかの実施形態を示すものであり、その記述と共に本発明の原理を説明するために用いられる。
【発明の効果】
【００１５】
以上のように、本発明は、必要な計算を減らすことができ、且つ画像品質を低下させない。さらに、乱雑な情景を有する画像を取り扱う時に、一致した結果を作り出すことができる。
【図面の簡単な説明】
【００１６】
【図１】（ａ）は、本発明の１つの実施形態に係る階層グラフに基づく画像マッティングの例示的システムのブロック図である。（ｂ）は、本発明の１つの実施形態に係る図１（ａ）のシステムを実施するコンピュータシステムの概略図である。
【図２】本発明の１つの実施形態に係るピクセルレベルグラフに基づく例示的収縮プロセスを示したものである。
【図３】本発明の１つの実施形態に係る収縮プロセスを例示的入力画像に応用した時の結果を示したものである。
【図４】本発明の１つの実施形態に係る特徴空間に基づくピクセルからセルへのマッピングプロセスを示したものである。
【図５】（ａ）〜（ｄ）は、セルレベルグラフモデルの固定解像度スキームおよび多重解像度スキームの例示的実施形態を示したものである。
【図６】本発明の１つの実施形態に係る多重解像度画像パッチに基づくセルレベル処理を示したものである。
【図７】本発明の１つの実施形態に係るセルからコンポーネントへのマッピングを示したものである。
【図８】入力画像、マッティングセグメントおよびマッティングコンポーネントの例示的実施形態を示したものである。
【図９】コンポーネントレベルグラフの１つの例示的実施形態を示したものである。
【図１０】本発明の１つの実施形態に係るコンポーネントからレイヤーへのマッピングを示したものである。
【図１１】（ａ）は、本発明の１つの実施形態に係るセルからレイヤーへの直接マッピングに基づくマッティング結果を示したものである。（ｂ）は、本発明の１つの実施形態に係るセルからコンポーネントへ、それからレイヤーへの多重解像度マッピングに基づくマッティング結果を示したものである。
【図１２】マッティングレイヤーの例示的実施形態および入力画像の前景領域の可能性図を示したものである。
【図１３】本発明の１つの実施形態に係る階層グラフに基づく画像マッティングおよび前景推定のプロセスを示したものである。
【図１４】本発明の別の実施形態に係る階層グラフに基づく画像マッティングおよび前景推定のプロセスを示したものである。
【発明を実施するための形態】
【００１７】
以下、添付の図面を例として、本発明の実施形態を詳細に説明する。各図面および関連説明において、同一または類似する構成要素には、同一の参照番号を使用する。
【００１８】
本発明のいくつかの実施形態に基づき、教師ありマッティングおよび教師なしマッティングを含む画像マッティングを実行する階層フレームワークを開示する。ボトムアップ（bottom-up）のメカニズムに基づき、階層フレームワークは、ピクセル（pixel）からセル（cell）へ、セルからコンポーネント（component）へ、最後はコンポーネントからマッティングレイヤー（matting layer）へと画像データを段階的に圧縮する。さらに具体的に説明すると、階層フレームワークの第１レベル（すなわち、ピクセルレベル）において、まず、画像ピクセルをピクセルからセルへのマッピングによりセルに圧縮する。このマッピングは、特徴空間における隣接データは類似するマッティング値を共有する傾向にあるという仮説に基づいて行われる。この圧縮プロセスは、明らかな品質低下を生じさせずに、スペクトル解析に必要とされる計算を大幅に減らすことができる。
【００１９】
第２レベル（すなわち、セルレベル）において、セルベースの構造は、セルレベルグラスに基づいて、多重スケール（multi-scale）アフィニティ学習（affinity learning）を提供する。乱雑な情景の画像を扱う時、多重スケールアフィニティ学習は、スペクトル解析の性能を効果的に改善することができる。グラフ分割の問題を解決することによって、マッティングコンポーネントは、セルレベルのグラフから自動的に抽出される。
【００２０】
第３レベル（すなわち、コンポーネントレベル）において、コンポーネントレベルグラフを生成し、複数のマッティングレイヤーの推定を行う。さらなる実施形態において、前景確率分布モデルを応用して、可能な前景マットのリストを確率的に生成し、マッティングレイヤーの前景可能性を推定する。
【００２１】
図１（ａ）は、本発明の１つの実施形態に係る階層グラフに基づく画像マッティングのシステム１００を示したものである。システム１００は、ピクセル処理モジュール１０２と、セル処理モジュール１０４と、コンポーネント処理モジュール１０６と、レイヤー処理モジュール１０８と、前景推定モジュール１１０とを含む。モジュール１０２〜１１０は直列に配置され、ピクセル処理モジュール１０２は、入力データ１１２を受信し、前景推定モジュール１１０は、出力データ１１４を生成する。セル処理モジュール１０４、コンポーネント処理モジュール１０６およびレイヤー処理モジュール１０８は、図１（ａ）に示した順番に基づいて、中間処理ステップを実行する。モジュール１０２〜１１０のうちの１つまたは複数は、システム１００から省略してもよい。例えば、レイヤー処理モジュール１０８を省略し、前景推定モジュール１１０がコンポーネント処理モジュール１０６から提供されたデータに基づいて出力データを生成してもよい。
【００２２】
１つの実施形態において、図１（ａ）に示したモジュール１０２〜１１０は、図１（ｂ）に示したプロセッサ１２２および非一時的なコンピュータ可読媒体１２４を含むコンピュータシステム１２０により実施してもよい。プロセッサ１２２は、例えば、インテル（INTEL）プロセッサ、ＡＭＤ（Advanced Micro Devices）プロセッサまたは本分野において周知の他のプロセッサ等の中央処理装置（central processing unit, CPU）であってもよい。コンピュータ可読媒体１２４は、ハードディスク、フラッシュドライブ、ＣＤ（compact disc）、ＤＶＤ（digital Versatile Disc）、ＲＡＭ（random access memory）、ＲＯＭ（read-only memory）等を含んでもよく、上述したコンピュータ可読媒体１２４を配置することにより、ここで開示した画像マッティング技術に関連する指令およびデータを記憶する。上述した指令は、Ｃ、Ｃ＋＋、ＢＡＳＩＣ、ＦＯＲＴＲＡＮ、ＪＡＶＡ、または本分野において周知の他のプログラミング言語で書かれてもよい。プロセッサ１２２は、コンピュータ可読媒体１２４からの指令およびデータを受信して、ここで開示したモジュール１０２〜１１０の機能を実行する。
【００２３】
別の実施形態において、モジュール１０２〜１１０は、例えば、プログラマブルロジックアレイ、フィールドプログラマブルゲートアレイ、特定用途向け集積回路（ＡＳＩＣ）等のプログラマブル集積回路により実施することができる。
【００２４】
システム１００は、さらに、例えば、ディスプレイ１２８、キーボード１２６、マウス、タッチパッド、タッチスクリーン等のユーザー入力／出力（input/output, I/O）装置１２６および１２８を含んでもよい。例えば、システム１００は、キーボード１２６によりユーザー入力を受信し、ユーザー入力に基づいて、画像マッティング技術を入力データに応用する。システム１００は、ディスプレイ１２８により出力データをユーザーに提供する。
【００２５】
入力データ１１２はユーザーまたは外部システムにより提供された、または、例えば、ハードディスク、フラッシュドライブ、ＣＤ、ＤＶＤ、ＲＡＭ、ＲＯＭ等の記憶媒体から受信した画像データまたは映像データを含んでもよい。入力データ１１２は、撮像システム（例えば、カメラまたはビデオカメラ）によって取り込まれた任意の自然情景の画像または映像フレームを表示することができる。入力データ１１２は、コンピュータにより生成された合成または人工情景の画像または映像フレームを表示してもよい。入力データ１１２により表示される情景は、画像または映像フレームを取り込む撮像システムに比較的近い１つまたは複数の前景物体を含む。上述した情景は、画像または映像フレームを取り込む撮像システムから比較的遠く離れた１つまたは複数の背景物体を含んでもよい。
【００２６】
入力データ１１２における画像または映像フレームは、例えば、ピクセル等の行と列を含む１つまたは複数の規則的配列構造に配列された画像要素により表示される。各画像要素は、例えば、ＲＧＢ（Red Green Blue）色空間、ＣＭＹＫ（Cyan Magenta Yellow Key (Black)）色空間、または本分野において周知の他の色空間等の色空間に基づいて定義された１つまたは複数の値を含む。１つの実施形態において、各画像要素は、前景物体の中の１つまたは背景物体の中の１つのいずれかと関連するため、画像要素は、一部の前景物体または背景物体を表示する。別の実施形態において、各画像要素は、前景物体の中の１つおよび背景物体の中の１つの組み合わせと関連するため、画像要素は、前景物体と背景物体の間の画像境界に存在する。
【００２７】
出力データ１１４は、入力データにおける前景物体および／または背景物体と関連する画像要素を識別することができる。１つの実施形態において、出力データ１１４は、複数の要素を有するマスク（mask）を含む。上述したマスクの各要素は、入力データ１１２の画像要素と関連し、例えば、アルファマット値等の１つの値を含み、上述したアルファマット値は、前景物体の中の1つの不透明度に対応する。例えば、値が０のマスクの要素は、完全に透明な前景物体または欠乏した前景物体として識別されるため、関連する画像要素は、背景物体と関連する。値が１のマスクの要素は、完全に不透明な前景物体に対応するため、関連する画像要素は、前景物体と関連する。分数値を有するマスクの要素は、前景物体と背景物体の組み合わせに対応することができる。これは、前景物体が部分的に透明である、または画像要素が前景物体と背景物体の間の画像境界に存在する時に発生する。分数値は、関連する画像要素に対する前景物体の貢献を示す。
【００２８】
本発明の本実施形態において、システム１００は、階層グラフモデルに基づいて、画像マッティングプロセスを入力データ１１２に適用する。階層グラフモデルは、例えば、ピクセルレベル、セルレベルおよびコンポーネントレベル等の複数のレベルを含む。したがって、本発明において開示するプロセスは、対応するモジュール１０２〜１１０により実行される複数の段階を含む。これらの段階は、例えば、ピクセルレベル処理段階、セルレベル処理段階およびコンポーネントレベル処理段階を含む。コンポーネント処理モジュール１０６により生成されたデータは、さらに、レイヤー処理モジュール１０８および前掲推定モジュール１１０により処理され、出力データ１１４を生成することができる。これらの段階によりプロセスを進行するに従って、処理されたデータにおける要素の数は、次第に減少するため、前景および入力データ１１２のアルファマットの有効且つ正確な推定を提供することができる。以下、モジュール１０２〜１１０の詳細について、図２〜図１０を参照しながらさらに説明を行う。
【００２９】
収縮（contraction）プロセス
１つの実施形態において、ピクセルレベル処理段階は、階層グラフモデルに基づいて、画像マッティングプロセスの第１段階を形成する。ピクセルレベル処理段階は、ピクセル処理モジュール１０２により実行される。ピクセル処理モジュール１０２は、入力データ１１２の中の画像要素（例えば、ピクセル）を密集したセルに圧縮して、後の段階において必要とされる計算を減らすよう構成される。ここで使用する単語「圧縮」は、類似する画像ピクセルを空間的に一つにまとめるプロセスを指す。
【００３０】
ピクセルを圧縮するため、ピクセル処理モジュール１０２は、グラフベースのエネルギー関数の最小化に基づいて、局所収縮プロセスを応用する。以下、局所収縮プロセスの詳細について説明する。
【００３１】
局所収縮プロセスにおいて、入力データ１１２（例えば、入力画像）は、まず、グラフを表示する。グラフの頂点（vertex）は、ピクセルごと（pixel-wise）の強度データを表示し、１対の頂点間の各エッジは、対応するピクセルペアの間の関連を表示する。ここで、２つのピクセルｉとｊの間のアフィニティ値Ａq（ｉ，ｊ）は、以下のように定義される。
【００３２】
【数２】
2016062588.tif 000004
【００３３】
上記の等式（２）において、ＩiおよびＩjは、ピクセルｉとｊにおける入力画像Ｉの色値を示し、μqは、ピクセルのウィンドウωqにおける３×１平均（mean）色ベクトルを示し、Σqは、３×３共分散行列（covariance matrix）を示し、|ωq|は、局所ウィンドウωqにおけるピクセルの数を示し、Ｕは、３×３単位行列（identity matrix）を示し、εは、平滑領域における過剰適合を防ぐための正則化項（regularization term）を示す。例えば、平滑領域において、Σqにおけるエントリー（entry）は、相対的に小さい値を有するため、ノイズによって生じた比較的小さな偏差がアフィニティ値を大きく変化させる可能性がある。比較的小さな値のεを適切に追加することによって、平滑領域におけるアフィニティ値の変動を効果的に抑制することができる。等式（２）に基づいて、２つのピクセルが類似する色外観を有する場合、これら２者間のアフィニティ値は相対的に大きい。局所ウィンドウωqは、画像全体をスキャンすることによって入力画像における各エッジのいくつかのアフィニティ値を生成する。各エッジのこれらのアフィニティ値から平均値を求めて、ピクセルレベルグラフモデルを生成する。
【００３４】
2016062588.tif 000005
【００３５】
【数３】
2016062588.tif 000006
【００３６】
2016062588.tif 000007
【００３７】
【数４】
2016062588.tif 000008
【００３８】
関数（３）、（４）のそれぞれにおいて、右手側の第１項は、ピクセルを空間的により近くに引く傾向にあるペアワイズ凝集力（pair-wise cohesion force）に対応し、右手側の第２項は、オリジナル画像構造を維持しようとする偏差コスト（deviation cost）に対応する。パラメータλxおよびλyは、収縮の強度を制御するために使用される。
【００３９】
2016062588.tif 000009
【００４０】
【数５】
2016062588.tif 000010
【００４１】
2016062588.tif 000011
【００４２】
【数６】
2016062588.tif 000012
【００４３】
最適な解決方法は、方程式（７）、（８）の上記の線形システムに基づいて解決される。
【００４４】
図２は、本発明の１つの実施形態に係る例示的局所収縮プロセスを示したものである。図２において、入力データ１１２における入力画像は、初期グラフ２０２により表示される。各頂点２０６は、その色値を有する画像ピクセルを示し、各エッジ２０８は、１対の隣接する画素間のアフィニティ関係を示す。初期グラフ２０２に収縮プログラムを応用して収縮グラフ２０４を生成する。このグラフにおいて、相対的に高いアフィニティ値を有するピクセルは、互いに収縮する。
【００４５】
図３は、例示的な入力画像３０２および局所収縮プロセス後の収縮画像３０４である。収縮プロセスの後、類似する外観を有するピクセルは互いに収集するが、類似しない外観を有するピクセルは互いに離れる傾向にあることがわかる。
【００４６】
2016062588.tif 000013
【００４７】
2016062588.tif 000014
【００４８】
収縮画像全体のピクセルからセルへのマッピングは、Ｎ×Ｐ二値行列Ｍに記録され、ＮおよびＰは、それぞれ画像ピクセルおよびセルの総数を示す。ここで、第ｉピクセルが第ｊセルにマッピングされた場合、全てのｋ≠ｊに対し、Ｍ（ｉ，ｊ）＝１であり、且つＭ（ｉ，ｋ）＝０である。
【００４９】
１つの実施形態において、パラメータｂsおよびｂcは、１５に設定されるため、セルＰの数は、１０，０００〜２０，０００である。別の実施形態において、パラメータｂsおよびｂcは、１０〜２０の間の任意の値に設定してもよい。さらに別の実施形態において、パラメータｂsおよびｂcは、状況に応じて、その他の任意の値に設定してもよい。
【００５０】
多重スケールアフィニティおよびセルレベルグラフ
ピクセル処理モジュール１０２が画像ピクセルをセルに併合した後、セルをセル処理モジュール１０４に出力し、セル処理モジュール１０４により各対のセル間のセルのアフィニティ値を確定して、セルレベルグラフモデルを構築する。１つの実施形態において、セル処理モジュール１０４は、多重スケール（multi-scale）または多重解像度（multi-resolution）方法を応用して、画像ピラミッド（pyramid）からアフィニティ情報を確定する。以下、多重スケールのセルレベルグラフモデルについて、さらに詳しく説明する。
【００５１】
図５（ａ）〜図５（ｄ）は、固定解像度スキームおよび多重解像度スキームのセルレベルグラフモデルの例示的実施形態を示したものである。このスキームは、異なる空間範囲にあるセル間のアフィニティ値を確定することができる。図５（ａ）の左側の画像は、正方形の孔を有する円形物体５０２および小三角形物体５０４を含む人工情景の画像を示したものである。図５（ａ）の中間および右側の画像は、それぞれ、ピクセルレベルおよびセルレベルにおける対応する特徴分布を示したものである。ここで、球体は、個々のピクセルを示し、立方体は、個々のセルを示す。
【００５２】
図５（ｂ）および図５（ｃ）は、異なる局所ウィンドウを使用した異なる実施形態を示したものである。局所ウィンドウは、それぞれ３×３のサンプリングピクセルを含み、画像ピクセル周辺のアフィニティ情報を調べる。ここで、各「」の符号は、サンプリングピクセルを示す。図５（ｂ）の左側の図面における局所ウィンドウは、直接隣接するピクセルのみを含む相対的に小さい空間領域を覆い、図５（ｃ）の左側の画像における局所ウィンドウは、より遠くのピクセルを含む相対的に大きな空間領域を覆う。
【００５３】
等式（２）に基づいて、９個のサンプリングピクセルの中の各対のアフィニティ値を決定することができる。図５（ｂ）の中間画像は、特徴空間におけるピクセルペアの被覆率を示したものである。この状況では、隣接するサンプリングピクセルのアフィニティ値しか確定できず、遠範囲のアフィニティ、例えば、孔内のピクセルと円形物体５０２の外側のピクセルの間のアフィニティは、計算されない。反対に、図２（ｃ）の実施形態では、遠いサンプリングピクセル間のアフィニティを計算するが、例えば、三角形物体５０４と円形物体５０２の間の関係のように、細部が失われる可能性もある。
【００５４】
図５（ｂ）および図５（ｃ）の右側の画像は、画像ピクセル併合後のセル間のアフィニティを示したものである。同様にして、スケールの小さいサンプリングウィンドウは、セル間の近範囲のアフィニティを提供し、スケールの大きいサンプリングウィンドウは、セル間の遠範囲のアフィニティを提供する。
【００５５】
近範囲と遠範囲の両方のアフィニティを調べるため、図５（ｄ）の実施形態は、多重スケール方法を使用し、スケールの小さいウィンドウとスケールの大きいウィンドウの両者を使用して、入力画像に対してサンプリングを行う。図５（ｄ）の右側の画像からわかるように、セル間の近範囲および遠範囲のアフィニティ情報は、多重スケールサンプリングスキームに基づいて同時に決定することができる。また、ピクセルレベルのアフィニティ推定と比較して、セルレベルでは、多くの不必要なアフィニティ計算を省略することができる。
【００５６】
別の実施形態に基づくと、多重スケールアフィニティ推定は、１組の多重解像度画像パッチ（patch）におけるアフィニティを計算して実施される。図６は、１つの実施形態の多重解像度画像パッチに基づくセルレベル処理を示したものである。例えば、ガウス（Gaussian）画像ピラミッド６０４から多重解像度画像パッチ６０２をサンプリングする。ここで、画像ピラミッド６０４は、セル処理モジュール１０４がｘ軸およびｙ軸に沿ってダウンサンプリング（down-sampling）プロセスをサンプリング率ｄsで再帰的に行うことによって、入力画像３０２から生成される。得られた画像ピラミッド６０４は、最粗画像６０４Ａ、１つまたは複数の中間解像度画像６０４Ｂおよび最精細画像６０４Ｃを含み、最精細画像は、例えば、入力画像３０２である。スライディングウィンドウ（sliding window）を使用して、画像ピラミッド６０４における画像６０４Ａ〜６０４Ｃのそれぞれから画像パッチを抽出する。
【００５７】
画像パッチ（例えば、画像パッチ６０２）に対し、セル処理モジュール１０４は、局所アフィニティ学習プロセスを応用して、セル間のアフィニティ値を推定する。最粗レイヤー（すなわち、画像６０４Ａ）において、アフィニティ情報の推定は、図５（ｃ）に示した遠範囲状況と類似しており、アフィニティ情報のいくつかの細部が失われる可能性がある。しかしながら、モジュール１０４が上述した画像を低解像度画像から高解像度画像に徐々にスキャンするに従って、アフィニティ情報のより多くの細部が得られる。一般的に、大部分のアフィニティ情報は、低解像度画像から抽出することができ、僅かな細部アフィニティ情報のみが高解像度画像から抽出される。そのため、１つの実施形態において、スライディングウィンドウは、最低解像度画像（すなわち、最粗画像６０４Ａ）からの画像パッチを完全にスキャンし、比較的高い解像度画像（すなわち、画像６０４Ｂおよび６０４Ｃ）からの画像パッチのサブセット（subset）のみをスキャンして、セルレベルアフィニティ情報を確定する。
【００５８】
比較的高い解像度画像（すなわち、画像６０４Ｂおよび６０４Ｃ）における画像パッチのサンプリングに対し、セル処理モジュール１０４は、残留ベース（residual-based）のスキームに基づいて、ダウンサンプリングプロセスによる欠損した細部を補償することができる。さらに詳しく説明すると、モジュール１０４は、個々の低解像度ピクセルおよび高解像度ピクセルをグリッドセルにマッピングして、２組のセルを形成する。この２組のセル間の差は、ダウンサンプリングプロセス後の欠損情報を示す。残留セルに基づいて、セル処理モジュール１０４は、対応するピクセルを識別し、これらのピクセル周辺にサンプリングパッチを置く。さらに具体的に説明すると、残留セルへマッピングしたピクセルに対し、各ピクセルの中心にある１組のｒ×ｒウィンドウを高解像度画像に置いて、高解像度サンプリングパッチを得る。また、１組のスライディングウィンドウを低解像度画像に置いて、低解像度サンプリングパッチを得る。その後、サンプリングパッチからセルレベルアフィニティ情報を計算する。
【００５９】
2016062588.tif 000015
【００６０】
2016062588.tif 000016
【００６１】
【数７】
2016062588.tif 000017
【００６２】
2016062588.tif 000018
【００６３】
【数８】
2016062588.tif 000019
【００６４】
等式（１０）は、Ｑにおける全てのセルのアルファマット値を対応する画像特徴と関連させる。αqとΦqの両者を与えると仮定すると、最適なβおよびβ0は、下記の二次コスト関数Ｅ（β，β0）を最小化することによって導かれる。
【００６５】
【数９】
2016062588.tif 000020
【００６６】
2016062588.tif 000021
【００６７】
【数１０】
2016062588.tif 000022
【００６８】
2016062588.tif 000023
【００６９】
【数１１】
2016062588.tif 000024
【００７０】
2016062588.tif 000025
【００７１】
【数１２】
2016062588.tif 000026
【００７２】
等式（１４）において、Ｉqは、Ｎq×Ｎq単位行列である。Ωqにおけるセルの局所ラプラシアン行列は、Ｎq×Ｎq行列であり、以下のように定義される。
【００７３】
【数１３】
2016062588.tif 000027
【００７４】
グラフΓqを定義すると仮定すると、頂点は、Ωqにおけるセルを示し、１対の頂点間のエッジは、対応するセルペア間のアフィニティ関係を示す。Γqに対し、対応するグラフラプラシアン行列は、以下のように定義される。
【００７５】
【数１４】
2016062588.tif 000028
【００７６】
Ｄqは、次数行列であり、Ａqは、アフィニティ行列である。エントリーＡq（ｉ，ｊ）は、セルｉとｊの間のアフィニティ値を示し、次数行列Ｄqは、対角行列である。その対角エントリーは、以下のように定義される。
【００７７】
【数１５】
2016062588.tif 000029
【００７８】
１つの実施形態に基づくと、セルレベルグラフのアフィニティ行列は、明確に定義されない。代りに、上述したアフィニティ情報は、等式（１４）に示した局所学習スキームに基づいて導かれる。また、等式（１４）におけるコスト関数Ｊqは、以下のように解釈してもよい。
【００７９】
【数１６】
2016062588.tif 000030
【００８０】
2016062588.tif 000031
【００８１】
単一の画像パッチωq内の等式（１４）で定義したコスト関数Ｊqに基づいて局所ラプラシアン行列を確定した後、セル処理モジュール１０４は、パッチセットＳpatch全体における局所コスト関数を積分して、さらに全体的なコスト関数を確定する。ここで、等式（１４）のコスト関数Ｊqは、以下のように書き換えてもよい。
【００８２】
【数１７】
2016062588.tif 000032
【００８３】
2016062588.tif 000033
【００８４】
【数１８】
2016062588.tif 000034
【００８５】
2016062588.tif 000035
【００８６】
【数１９】
2016062588.tif 000036
【００８７】
また、等式（２０）は、より簡潔な形で書き換えることができる。
【００８８】
【数２０】
2016062588.tif 000037
【００８９】
2016062588.tif 000038
【００９０】
【数２１】
2016062588.tif 000039
【００９１】
等式（２４）において、対角行列Ｄは、ＣＭＬのＰ×Ｐ次数行列を表示する。
【００９２】
コンポーネントレベルグラフ
図７は、１つの実施形態に係るセルからコンポーネントへのマッピングを示したものである。セル処理モジュール１０４が図６に示したセルレベルグラフ６０６を取得した後、セルレベルグラフ６０６は、コンポーネント処理モジュール１０６に出力される。このコンポーネント処理モジュール１０６は、図７に示すように、上述したセルレベルグラフ６０６を１組のマッティングコンポーネント７０２に分解し、コンポーネントレベルグラフを形成して、前景マットの推定に用いる。コンポーネントレベルグラフを構築している間、前景モデルに関するいくつかの先行情報を中に含ませることができる。
【００９３】
セルレベルグラフ６０６を図７に示したマッティングコンポーネント７０２に分解するため、コンポーネント処理モジュール１０６は、スペクトラルクラスタリングを行って、硬判定（hard-decision）マッティングセグメントを生成した後、最適化プロセスを応用して、硬判定マッティングセグメントを軟判定（soft-decision）マッティングコンポーネントに変換または精緻化（refining）する。図８は、入力画像８０２、マッティングセグメント８０４およびコンポーネント処理モジュール１０６により生成されたマッティングコンポーネント８０６の例示的実施例を示したものである。
【００９４】
2016062588.tif 000040
【００９５】
2016062588.tif 000041
【００９６】
【数２２】
2016062588.tif 000042
【００９７】
2016062588.tif 000043
【００９８】
【数２３】
2016062588.tif 000044
【００９９】
式中、Ｉcは、Ｐ×Ｐ単位行列を示す。図８からわかるように、より詳細なマッティング値は、初期マッティングセグメント８０４よりもマッティングコンポーネント８０６において得られる。
【０１００】
マッティングコンポーネントが確定した後、コンポーネント処理モジュール１０６は、コンポーネントレベルグラフを生成する。コンポーネント処理モジュール１０６は、セルレベルグラフを圧縮することにより、またはダイバージェンスベース（divergence-based）のプロセスにより、コンポーネントレベルグラフを生成する。１つの実施形態において、コンポーネント処理モジュール１０６は、セルレベルマッティングラプラシアン行列をコンポーネントレベルマッティングラプラシアンLcondensedに圧縮することにより、コンポーネントレベルグラフを生成する。ここで、Ｔ＝［α1，...，αK］がＫ個のマッティングコンポーネントのアルファマットベクトルにより形成されたＰ×Ｋ個の行列を示すと仮定し、以下のように、この行列をコンポーネントレベルマッティングラプラシアンＬcondensedの計算に用いる。
【０１０１】
【数２４】
2016062588.tif 000045
【０１０２】
2016062588.tif 000046
【０１０３】
2016062588.tif 000047
【０１０４】
【数２５】
2016062588.tif 000048
【０１０５】
2016062588.tif 000049
【０１０６】
【数２６】
2016062588.tif 000050
【０１０７】
式中、ＤKLは、対角次数行列であり、以下のように定義される。
【０１０８】
【数２７】
2016062588.tif 000051
【０１０９】
任意のコンポーネントペアに対し、高ダイバージェンス値は、低アフィニティ値に対応する。したがって、コンポーネント処理モジュール１０６は、シグモイド（sigmoid）関数を使用して、コンポーネントｍとｎのアフィニティＡKL（ｍ、ｎ）を以下のように定義する。
【０１１０】
【数２８】
2016062588.tif 000052
【０１１１】
2016062588.tif 000053
【０１１２】
【数２９】
2016062588.tif 000054
【０１１３】
最後に、ダイバージェンスベースのラプラシアン行列ＬKLは、以下のように計算される。
【０１１４】
【数３０】
2016062588.tif 000055
【０１１５】
コンポーネント処理モジュール１０６は、その後、ダイバージェンスベースのラプラシアンＬKLを圧縮したマッティングラプラシアンＬcondensedと併合することによって、コンポーネントレベルグラフラプラシアンＬcompを計算する。
【０１１６】
【数３１】
2016062588.tif 000056
【０１１７】
等式（３３）において、λKLは、ＬcondensedとＬKLの間の貢献を平衡させるためのパラメータである。コンポーネント処理モジュール１０６は、圧縮したマッティングアフィニティ度の合計とＫＬアフィニティ度の合計の間の比率に基づいて、以下のようにλKLを計算する。
【０１１８】
【数３２】
2016062588.tif 000057
【０１１９】
図９は、図７のマッティングコンポーネント７０２に基づいてコンポーネント処理モジュール１０６により生成された例示的コンポーネントレベルグラフ９０２を示したものである。
【０１２０】
コンポーネントからレイヤーへのマッピング
１つの実施形態に基づき、コンポーネント処理モジュール１０６は、上述したコンポーネントレベルグラフラプラシアンＬcompを計算した後、レイヤー処理モジュール１０８は、データを受信し、コンポーネントレベルのスペクトラルクラスタリングに基づいて、コンポーネントからレイヤーへのマッピングプロセスを応用する。図１０は、コンポーネントからレイヤーへのマッピングプロセスの例示的実施形態を示したものであり、図７に示したマッティングコンポーネントは、コンポーネントレベルグラフ９０２に基づいて、複数のレイヤー１００２にマッピングされる。
【０１２１】
2016062588.tif 000058
【０１２２】
【数３３】
2016062588.tif 000059
【０１２３】
システム１００は、セルからマッティングレイヤーに直接クラスタリングを行わず、セルからコンポーネントへのマッピングとコンポーネントからレイヤーへのマッピングにより、画像データに対してスペクトラルクラスタリングを２回行う。具体的に説明すると、システム１００は、まず、セルをコンポーネントにクラスタリングしてから、コンポーネントをレイヤーにクラスタリングする。例えば、図６のグラフ６０６等のセルレベルグラフに基づいて、システム１００は、多重解像度の局所アフィニティ学習スキームに基づいて、グラフ頂点のアフィニティ値を局所的に計算し、より短範囲のアフィニティ情報を調べる。また、例えば、図９のグラフ９０２等のコンポーネントレベルグラフに基づいて、システム１００は、各対のコンポーネント間のアフィニティ値を計算し、近範囲と遠範囲アフィニティ情報の両方を含む完全結合グラフ（fully connected graph）を生成する。この完全結合グラフに基づいて、システム１００は、セルレベル分析のみを行う場合と比較して、より全体的なスケールにおいてアフィニティ情報を調べることができる。図１１（ａ）は、１つの実施形態に係るセルからレイヤーへのマッピングに基づくマッティング結果を示したものである。図１１（ａ）において、セルは、直接２レイヤー、３レイヤー、４レイヤーおよび５レイヤーにクラスタリングされる。これと比較して、図１１（ｂ）は、１つの実施形態に係るセルからコンポーネント、レイヤーへの多重解像度マッピングに基づくマッティング結果を示したものである。図１１（ｂ）において、まず、セルをコンポーネントに分解してからコンポーネントをレイヤーにクラスタリングすることによって、セルに対して２段階のクラスタリングを応用する。まず、画像をより多くのコンポーネントに分解した後、コンポーネントからレイヤーへのマッピングを行うことにより、システム１００は、より合理的な結果を得る。
【０１２４】
2016062588.tif 000060
【０１２５】
【数３４】
2016062588.tif 000061
【０１２６】
2016062588.tif 000062
【０１２７】
前景推定
レイヤー処理モジュール１０８においてマッティングレイヤーを生成した後、前景推定モジュール１１０は、マッティングレイヤーを受信し、マッティングレイヤーに対して確率推定プログラムを応用して、前景情報を推定する。ここで、前景推定モジュール１１０は、関連するマッティングコンポーネントに基づいて各マッティングレイヤーを処理するとともに、各マッティングコンポーネントに対して確率スキーム（probabilistic scheme）を応用して、前景物体の一部の確立を推定する。
【０１２８】
さらに具体的に説明すると、前景推定モジュール１１０は、確率分布モデルｐ（ｂ）＝ｐ（ｂ1，...，ｂK）を生成する（式中、1≦ｋ≦Ｋに対し，ｂk∈[０，１]）。マッティングコンポーネントｋに対し、このコンポーネントが前景コンポーネントであると識別された時、前景推定モジュール１１０は、ｂk＝１に設定する；そうでない時は、ｂk＝０に設定する。上述した定義に基づいて、各ベクトルｂは、前景マット仮定を示し、マッティングコンポーネントの集合に対応する。前景推定モジュール１１０が全ての可能なｂ’ｓ確立分布モデルｐ（ｂ）を導き出すと、前景推定モジュール１１０は、前景マットを示す可能性がより高いｂ’ｓのサブセットを選択する。
【０１２９】
１つの実施形態に基づき、分布モデルｐ（ｂ）は、相対的に高アフィニティを有する１対のコンポーネントは同じ前景インデックスを共有するという一致性の仮定に基づく。したがって、これら２つのコンポーネントは、いずれも前景であるか、いずれも背景である傾向にある。図３の入力画像３０２を１つの実例として使用し、正面の２つの花を２つのマッティングコンポーネントに分けると仮定する。上述した２つのマッティングコンポーネントのうちの１つが前景コンポーネントに分類されると、同時にもう１つも前景コンポーネントであるという確率が比較的高い。
【０１３０】
この一致性の仮定に基づき、前景推定モジュール１１０は、コンポーネントレベルラプラシアン行列Ｌcompに基づいて与えられたベクトルを評価し、以下のように定義される「不一致性（inconsistency）」の測度を確定する。
【０１３１】
【数３５】
2016062588.tif 000063
【０１３２】
等式（３８）の定義に基づき、不一致性値ｄfb（ｂ）が比較的低いベクトルｂは、対応するマッティングコンポーネントの集合が前景マットの一部である確率が比較的高い。しかしながら、これは、この測定のみにより適切な前景ベクトルが簡単に見つかるという意味ではない。１つの実例において、エントリーが全て１（または全て０）のｂベクトルは、ゼロ不一致性に対応し、望ましい結果ではない可能性がある。
【０１３３】
別の実施形態に基づくと、上述した問題を回避するため、前景推定モジュール１１０は、さらに、前景領域と背景領域の間の比率は過度に不均衡になるべきではないという仮定に基づいて、バランシングウェイト（balancing weight）を応用する。バランシングウェイトη（ｂ）は、以下のように定義される。
【０１３４】
【数３６】
2016062588.tif 000064
【０１３５】
2016062588.tif 000065
【０１３６】
【数３７】
2016062588.tif 000066
【０１３７】
この加重された不一致性測度を利用して、確率分布モデルは、以下のように定義される。
【０１３８】
【数３８】
2016062588.tif 000067
【０１３９】
2016062588.tif 000068
【０１４０】
１つの実施形態に基づくと、システム１００は、入力画像の相対的に小さい数（通常、１０〜２０）のマッティングコンポーネントを生成する。したがって、前景推定モジュール１１０は、全ての可能なｂ’ｓを生成することができ、各ベクトルｂに対して対応するｄfb（ｂ）をチェックする。別の実施形態に基づくと、前景推定モジュール１１０は、相対的に大きなｄfb（ｂ）値を有するｂ’ｓを無視して、相対的に小さなｄfb（ｂ）値を有するｂ’ｓのみに焦点を合わせることにより、計算効率を向上させることができる。
【０１４１】
等式（４０）および（４１）に基づいて、前景推定モジュール１１０は、マッティングコンポーネントの組み合わせがコンポーネントラプラシアン行列Ｌcompと一致し、残りのコンポーネントと平衡を保っている場合、対応するｐf（ｂ）は、相対的に大きな値を有する。しかしながら、任意のｂおよびその補集合（１-ｂ）に対して、ｐf（ｂ）とｐf（１-ｂ）の値は、実際には等しい。そのため、前景および背景マッティングは、等式（４０）における不一致性測度に基づいて簡単に互いを区別することができない。別の実施形態に基づくと、前景推定モジュール１１０は、さらに、マットの凸性（convexity）およびその補集合（complement）の凸性を評価する。前景推定モジュール１１０は、その後、前景マットは通常凸状になる傾向があるという仮定に基づいて、前景マットを識別する。ここで、凸性は、マットとその対応する凸包（convex hull）の間の面積比に基づいて測定される。任意のｂと１-ｂの間の凸性を比較することによって、前景推定モジュール１１０は、凸性が相対的に低いマッティングコンポーネントを除去する。
【０１４２】
図１２は、マッティングレイヤー１２０２〜１２２０の例示的実施形態および入力画像３０２の前景領域の可能性図１２２２を示したものである。入力画像３０２のマッティングコンポーネント１２０２〜１２１８は、最大ｐf（ｂ）値を有する１０個のｂ’ｓ（すなわち、ランク１〜ランク１０）に対応する。これらのマットは、通常、前景領域（つまり、花の領域）と大きく重複する。したがって、ξが最大ｐf（ｂ）値を有する主要な前景ベクトルセットを示す場合、前景推定モジュール１１０は、以下のように、前景ベクトルｂFGをξにおけるｂベクトルの期待値として定義される。
【０１４３】
【数３９】
2016062588.tif 000069
【０１４４】
等式（４２）に基づいて、前景推定モジュール１１０は、以下のように、前景マットの前景可能性図をコンポーネントレベルアルファマット値の加重和として計算する。
【０１４５】
【数４０】
2016062588.tif 000070
【０１４６】
図１２に示すように、例示的可能性図１２２２は、画像ピクセルが入力画像３０２の前景領域に属する可能性を反映する。
【０１４７】
2016062588.tif 000071
【０１４８】
【数４１】
2016062588.tif 000072
【０１４９】
式中、1Pは、Ｐ×１個の全ての１ベクトルを示す。図１１（ｂ）は、各マッティングレイヤーの前景因子の値を示す。一般的に、相対的に大きな前景因子を有するマッティングレイヤーは、前景領域の一部である可能性がさらに高い。
【０１５０】
図１３は、１つの実施形態に係る階層グラフに基づく画像マッティングおよび前景推定のプロセス１３００のフローチャートである。プロセス１３００は、上述した技術に基づいて、システム１００において実施される。具体的に説明すると、プロセス１３００に基づき、ステップＳ１３０２において、入力画像を受信する。入力画像は、例えば、ピクセル等の複数の画像要素を含む。各ピクセルは、例えば、色空間に基づいて定義された色値を含む。ステップ１３０４において、入力画像に基づいて、複数のマッティングセルを生成する。各マッティングセルは、１組の画像要素を含む。マッティングセルは、まず、入力画像に対して収縮プロセスを応用した後、画像要素の中のアフィニティ関係に基づいて、収縮画像要素をマッティングセルにマッピングすることにより生成される。
【０１５１】
ステップ１３０６において、入力画像に基づいて複数のマッティングセルにアフィニティ値を計算する。アフィニティ値は、各対のマッティングセル間の類似性を示す。セルのアフィニティ値は、図５および図６で説明した多重解析度局所アフィニティ学習スキームに基づいて計算される。
【０１５２】
ステップ１３０８において、複数のマッティングセルおよびアフィニティ値に基づいて、例えば、上述したセルレベルグラフ等の第１グラフを形成する。第１グラフは、マッティングセルを示す複数の第１ノードまたは頂点、およびマッティングセルのアフィニティ値と関連する複数の第１エッジを含む。ステップ１３１０において、第１グラフに基づいて入力画像の複数のマッティングコンポーネントを生成する。マッティングコンポーネントは、マッティングセルのアフィニティ値に基づいて第１グラフを分解することによって生成される。マッティングコンポーネントの中の１つまたは複数は、その後、入力画像の前景領域に属するものと識別される。
【０１５３】
図１４は、別の実施形態に係る階層グラフに基づく画像マッティングおよび前景推定のプロセス１４００のフローチャートである。プロセス１４００は、上述した技術に基づいて、システム１００において実施される。具体的に説明すると、プロセス１４００に基づき、ステップＳ１３０２において、入力画像を受信する。入力画像は、例えば、ピクセル等の複数の画像要素を含む。
【０１５４】
ステップ１４０４において、入力画像に基づいて、例えば、上述したピクセルレベルグラフ等の第１グラフを形成する。第１グラフは、画像要素を示す複数の第１ノードまたは頂点、および画像要素の中のアフィニティ関係を示す複数の第１エッジを含む。ステップ１４０６において、第１グラフに基づいて画像要素を複数のセルにグループ化することによって、例えば、上述したセルレベルグラフ等の第２グラフを形成する。第２グラフは、セルを示す複数の第２ノードまたは頂点、およびセルの中のアフィニティ関係を示す複数の第２エッジを含む。
【０１５５】
ステップ１４０８において、第２グラフを複数のマッティングコンポーネントに分解することによって、例えば、上述したコンポーネントレベルグラフ等の第３グラフを形成する。第３グラフは、マッティングコンポーネントを示す複数の第３ノードまたは頂点、およびマッティングコンポーネントの中のアフィニティ関係を示す複数のエッジを含む。ステップ１４１０において、第３グラフに基づいて確率値を確定する。確率値は、マッティングコンポーネントが入力画像の前景領域に属する確率を示す。
【０１５６】
本発明の他の実施形態は、ここに開示された本発明の明細書および実施に対する考察から当業者には明かであろう。本明細書は単に例示のためであり、本発明の真の範囲および精神は、以下の特許請求の範囲に示される。
【０１５７】
以上のごとく、この発明を実施形態により開示したが、もとより、この発明を限定するためのものではなく、当業者であれば容易に理解できるように、この発明の技術思想の範囲内において、適当な変更ならびに修正が当然なされうるものであるから、その特許権保護の範囲は、特許請求の範囲および、それと均等な領域を基準として定めなければならない。
【産業上の利用可能性】
【０１５８】
本発明は、例えば、画像や映像の編集、画像レイヤー分解、シーン解析等の応用に、画像マッティングおよび前景推定を提供することができる。
【符号の説明】
【０１５９】
１００  システム
１０２  ピクセル処理モジュール
１０４  セル処理モジュール
１０６  コンポーネント処理モジュール
１０８  レイヤー処理モジュール
１１０  前景推定モジュール
１１２  入力データ
１１４  出力データ
１２０  コンピュータシステム
１２２  プロセッサ
１２４  コンピュータ可読媒体
２０２  初期グラフ
２０４  収縮グラフ
２０６  頂点
２０８  エッジ
３０２、８０２  入力画像
３０４  収縮画像
４０２  特徴空間
５０２  円形物体
５０４  小三角形物体
５０６、５０８  サンプリングピクセル
６０２  多重解像度画像パッチ
６０４  ピクセルピラミッド
６０４Ａ  最粗画像
６０４Ｂ  中間解像度画像
６０４Ｃ  最精細画像
６０６  セルレベルグラフ
７０２、８０６  マッティングコンポーネント
８０４  マッティングセグメント
９０２  コンポーネントレベルグラフ
１００２、１２０２〜１２２０  レイヤー
１２２２  可能性図
１３００、１４００  プロセス
１３０２〜１３１０、１４０２〜１４１０  ステップ
【図１】
2016062588.tif 000073
【図１３】
2016062588.tif 000074
【図１４】
2016062588.tif 000075
【図２】
2016062588.tif 000076
【図３】
2016062588.tif 000077
【図４】
2016062588.tif 000078
【図５】
2016062588.tif 000079
【図６】
2016062588.tif 000080
【図７】
2016062588.tif 000081
【図８】
2016062588.tif 000082
【図９】
2016062588.tif 000083
【図１０】
2016062588.tif 000084
【図１１】
2016062588.tif 000085
【図１２】
2016062588.tif 000086