JP2006053921A - ダイナミックプログラミングによる境界マッティング - Google Patents

Abstract

【課題】 ユーザーが過度に関わることなく、抽出した前景画像により効率的で改善された境界マッティングを提供する。
【解決手段】 例えば過度にユーザーが関わることを必要とせず、抽出した前景画像により効率的で改善された境界マッティングを提供する技術を開示する。本明細書で説明する境界マッティング技術は、抽出したオブジェクトの境界線に沿って、比較的連続した透明度（又はアルファ値）を生成する（例えば、色にじみおよび/又はアーチファクトを抑える）。
【選択図】 図６

Description

本発明は、一般的にデジタル画像処理、より具体的には境界マッティングに関係する。

コンピュータ技術が進化するにつれ、より強力なプロセッサと大容量の記憶装置を内蔵するコンピュータシステムがより一般的なものになってきている。このような処理能力と記憶容量の発展に伴い、デジタル画像テクノロジーの実現もより実用的になってきている。例えば、高解像度画像はより短い時間で処理できる。

ある場面のデジタル画像は、直接取得する（例えば、デジタルカメラで）か、又は従来にようにフィルムベースのカメラで撮影して、後でデジタル化してもよい（例えば、スキャナーで）。画像をデジタル形式にしたら、デジタル加工ができる。多くの場合、デジタル画像処理の最初の段階には、ある場面のある一部の選択が関わる。それから選択した部分に、デジタル技術（フィルタリング、複写、貼り付けなど）が応用できる。

現在、ユーザー関与の様々な程度によって、ある場面の前景を抽出するには、多数の技術が採用されている。しかし、抽出した前景は背景からのアーチファクトおよび／又は色にじみが含まれることがある。したがって、現在の前景抽出技術は一般的に、ユーザーが大幅に関与せずに、抽出した前景に相応に滑らかな境界を提供できていない。

このように、例えば背景からアーチファクトおよび／又は色にじみがなく、ある場面の一部のより効率的で改善された滑らかな抽出が望まれている。

例えば、ユーザーが過度に関わることなく、抽出した前景画像により効率的で改善された境界マッティングを提供する技術を開示する。本明細書で開示する境界マッティング技術は、抽出したオブジェクトの境界線に沿って、比較的連続した透明度（又はアルファ値）を生み出す（例えば、色にじみおよび/又はアーチファクトを抑える）。

一実施例において、方法は、前景領域と背景領域を有する分割画像を受信することを含む。この方法は２つの領域の境界線に沿って輪郭線を決定する。輪郭線から広がる未知の領域が決定される（つまり、アルファマップを計算する必要のある領域）。代わりに、輪郭線を、３領域マップから出発して決定することができ、輪郭線は提供される未知の領域で決定される。未知の領域の画素のアルファマップの一又は複数のパラメータに対応するエネルギー関数が定められる。エネルギー関数を最小化して、アルファマップの中心パラメータと幅パラメータを推定する。それから、推定した中心および幅パラメータに対応するアルファマップが計算される。

いくつかの実施例において、製品がコンピュータプログラム製品として提供される。コンピュータプログラム製品の一実施例は、コンピュータシステムによって読取可能で、コンピュータプログラムを符号化するコンピュータプログラム記憶媒体を提供する。コンピュータプログラム製品の別の実施例は、コンピュータシステムによって搬送波に具現され、コンピュータプログラムを符号化するコンピュータデータ信号の形で提供できる。

コンピュータプログラム製品は、コンピュータプロセスをコンピュータシステムで実行するためのコンピュータプログラムを符号化する。コンピュータプロセスは、前景領域と背景領域を有する分割画像を受信する。このプロセスは２つの領域と輪郭線から広がる未知の領域（つまり、アルファマップを計算する必要のある領域）の境界線に沿って輪郭線を決定する。代わりに、輪郭線は３領域マップから出発して決定でき、輪郭線は提供された未知の領域で決定される。新たな未知の領域の画素のアルファマップの一又は複数のパラメータに対応するエネルギー関数が定められる。エネルギー関数を最小化して、アルファマップの中心パラメータと幅パラメータを推定する。それから、推定した中心および幅パラメータに対応するアルファマップを計算する。

本明細書では、他の実施例も説明、列挙される。

以下の開示は一般的に、デジタル画増処理を改善するための技術を説明する。より具体的には、ユーザーが過度に関わることなく、ある場面の抽出した前景部分に適用できる改良された境界マッティングのための技術を開示する。さらに、本明細書で述べる技術は、ある画像の所要のあらゆる部分にも適用できることは予見される（例、オブジェクト、前景など）。

本明細書で説明する境界マッティング技術は、アーチファクト（例、図２Ａ〜Ｂのアーチファクトを参照）を抑えるため、および/又は例えば背景からの色にじみを抑えるなど前景の色の回復が可能なことが予見される。一施例において、境界マッティングはオブジェクトの境界線周囲のアルファマットと前景の画素の色を同時に推定して、滑らかなオブジェクトの境界線に沿ったにじみおよび/又はミクセル（ｍｉｘｅｄ ｐｉｘｅｌｓ）の悪影響を抑えるために適用できる。

（概要）
図１は、ある画像の一部を抽出するための例示的なフロー図１００を図示する。図１に図示されるように、画像１０２は領域１０４内に所要のオブジェクトを含む。領域１０４内のオブジェクトを抽出するために、ユーザーはオブジェクトを囲むための長方形（又は、投げ縄形、多角形、三角形、台形、楕円形、円形等などの別の形状）を描くことによって、所要の領域（１０４）を選択できる。従って、ユーザーは実施例において画像１０２の２点（つまり、始点と終点）を定義することによって、所要の部分を選択する。また、ユーザーは必ずしも厳密に問題の部分をトレースする必要はない。

領域１０４が選択されたら、領域１０４内の問題のオブジェクトもしくは部分を、本明細書で述べる技術により抽出することが可能である。（１０６）（例えば、図５および６を参照）。一実施例において、抽出した部分１０６は別の画像に貼り付けした、その他のデジタル処理ができる（例えば、フィルタをかける、色変更などにより）。

（境界マッティング結果の概要）
図２Ａ〜Ｃは、図１を参照して述べた抽出した部分１０６のある断片に境界マッティングを適用した後の様々な結果を図示する。図２Ａはノックアウト２の先行技術に従って境界マッティングした結果を図示する。図２Ｂは、ベイズマット法の先行技術に従って境界マッティングした結果を図示する。図２Ｃは、本明細書で述べる技術に従って境界マッティングした結果を図示する（例えば、図３および４を参照）。図２Ｃに図示するように、本明細書で述べる技術は図２Ａ〜Ｂの技術のいずれよりも明瞭なマットを提供する。

（境界マッティング技術）
図３は、オブジェクトの境界線に沿って連続した透明度（又はアルファ値）を生成するための例示的な境界マッティング法３００を図示する。境界マッティングは、オブジェクトの境界線の周りのアルファマットと前景の画素の色を同時に推定して、滑らかなオブジェクトの境界線に沿ったにじみおよび/又はミクセル(ｍｉｘｅｄ ｐｉｘｅｌｓ)の悪影響を抑えるためにも適用できる。従って、アルファマップは、アーチファクト（例えば図２Ａ〜Ｂのアーチファクトを参照）を生成することなく、および/又は背景から色にじみせずに前景の色の回復のために推定できる。

図３、４Ａおよび４Ｂを参照すると、ある場面が２領域マップ又は３領域マップ（３０２）に分割されると、輪郭線Ｃ４０８を、分割した場面の分割境界線にポリラインをフィットすることにより（又は他の曲線フィッティング技術）決定する（３０４）。２領域マップは２つの領域、つまり前景４０２（Ｔ_F）と背景４０４（Ｔ_B）を含む。３領域マップは未知の領域４０６（Ｔ_U）といわれる追加の領域を含む。３領域マップの場合、輪郭線Ｃ４０８は未知の領域４０６（Ｔ_U）にある。２領域マップ分割を図５〜８を参照して詳しく述べるが、反復型ハードセグメンテーション（例えば、画素×画素）を適用することにより得られる。

２領域マップに関し、未知の領域４０６（Ｔ_U）は、さらに帯状の幅の画素集合から輪郭線Ｃの両側のｗ個の画素を差し引きして計算する（オプション工程３０６）。一実施例において、ｗを６画素の幅に定めることができる。このため、この手順は、前景４０２（Ｔ_F）と、背景４０４（Ｔ_B）と、未知の領域４０６（Ｔ_U）から構成される３領域マップを定義する。

代わりに、工程３０２に関して述べたように、方法３００はこの３領域マップを入力として受信できる。そのため、輪郭線Ｃは、例えば細線化を使うなど、多数の異なる技術を使って計算できる。

Ｔ_Uの各画素のαマップ又はαプロファイル、つまりα_n，ｎ∈Ｔ_Uを定義するために、少数のパラメータに依存する比較的単純なモデルをＴ_U内のαマップの形状について、想定できる。モデルの最適なパラメータを求めるために、エネルギー関数を定義できる。このエネルギー関数は正則化を含むことができる（例えば、推定したαマップの質を高めるため）。ダイナミックプログラミング（ＤＰ）アルゴリズムを使用してエネルギー関数を最小化する、つまりモデルのパラメータ、そのためＴ_U全体でのαを計算することができる。

より具体的には、ｔ＝１，．．．，Ｔを輪郭線Ｃのパラメータ表示とすると、曲線Ｃは一実施例において閉じているため、これは期間Ｔで周期的に現れる。図４Ｂに図示するように、各画素ｎ∈Ｔ_Uにインデックスｔ（ｎ）を割り当てる。αマップをソフトステップ関数ｇになるようにとる（図４Ｃ）。α_n＝ｇ（ｒ_n；Δ_t(n)，σ_t(n)）で、ここでｒ_nは画素ｎから輪郭線Ｃまでの距離である（例えば、図４Ｂを参照）。パラメータΔ、σは、αマップの０から１までの移行のそれぞれ中心と幅を決定する（例えば、図４Ｃを参照）。同じインデックスｔをもつすべての画素はパラメータΔ_t、σ_tの値を共有すると想定する。これらのパラメータ値は、例えばｔ全体でＤＰを使って、以下のエネルギー関数を最小化することによって推定できる。

、ここで

は、以下のとおりのスムージング正則化項である。

スムージング正則化項

の役割は、曲線Ｃに沿って、ｔが増加したときにα値を滑らかに変化させるのを促すことである（例えば、λ₁＝５０かつλ₂＝１０³をとる）。ＤＰ計算のために、Δ_tの値は３０のレベルに離散化し、σ_tは１０のレベルに離散化できる。全体の平滑度項

はｔからｔ＋１に移行するために、プロファイルの数の二乗に比例した時間を必要とするであろうが、特定の正則化項は距離変換を使うことにより線形時間アルゴリズムを可能にする。輪郭線Ｃが閉じているとき、最小化はシングルパスＤＰを使っては正確には行えないが、最初のパスがｔ＝Ｔ／２の最適なプロファイルを与えると想定して、ＤＰの２つのパスを使って近似化する。

データ項は以下のように定義する。

上記の式で、

は平均μと共分散Σのときのｚのガウス確率密度を表す。上記式の平均と共分散は、マッティングのために以下のように定義する。

ガウスパラメータμ_t（α）、Σ_t（α）、前景と背景のα＝０，１は、Ｆ_t＝Ｓ_t∩Ｔ_FかつＢ_t＝Ｓ_t∩Ｔ_Bとして定義される領域Ｆ_tとＢ_tのそれぞれからのサンプル平均と共分散として推定される。ここでＳ_tは、ｔのとき分割境界線Ｃの中心にあるサイズＬ×Ｌの画素の平方領域である（例えば、Ｌ＝４１）。従って、このアプローチは、アルファ値が与えられたときの未知の領域の画素に、データ尤度推定値を提供する。

図３に戻って、また前述したように、エネルギー関数（Ｅ）は、スムージング正則化項（

）とデータ尤度項（

）を用いて定義される（３０８）。定義されたエネルギー関数を最小化することにより、αマップの中心と幅のパラメータ（それぞれΔ、σ）を推定する（３１０）。推定したパラメータをαマップの計算に利用する（３１２）。

（前景の推定）
αマップの計算に加えて（３１２）、境界マッティングの結果は、前景の画素の色を推定して（３１４）改善でき、原画の背景からの色にじみを抑える又は除去することができる。にじみは、使用する確率的アルゴリズムがミクセル（ｍｉｘｅｄ ｐｉｘｅｌｓ）から背景成分を切り離すことを目的としている。しかし、それを正確にできないために、一部の先行技術（ベイズマッティング法など、例えば図２Ｂを参照）で生じることがある。切り離しプロセスで残ったものが色にじみとして現れることがある。一実施例において、にじみは、前景Ｔ_Fから画素を借用することによって回避できる。まず、ベイズマットアルゴリズムを、画素ｎ∈Ｔ_Uの前景の色

の推定値を求めるために適用できる。それから、近傍Ｆ_t(n)（前述のとおり）から、

に最も類似した画素の色を借用して、前景の色ｆ_nを作る。正則化したアルファ計算と前景の画素の借用の両方を用いて得られた境界マッティングの結果を、図２Ｃに図示する。

反復グラフカットを使用した前景抽出
図５は、ユーザー定義の２領域マップ又は３領域マップに適用されるグラフカットを用いて、画像の一部を抽出するための例示的な方法５００を図示する。方法５００では、ユーザーはまず画像を２領域マップ又は３領域マップに分割する（５０２）。一実施例において、ユーザーの関与の必要を少なくすることによってユーザーを支援するために、２領域マップ（３領域マップの代わりに）を利用することが予見される。２領域マップ分割では、ユーザーは背景部分と未知の部分（本明細書で詳しく述べるように、それぞれＴ_B、Ｔ_UはＢおよびＵ）を定義できる。３領域マップ分割では、ユーザーは画像の３領域マップを手で初期設定できる。３領域マップは領域Ｔ_B、Ｔ_U、およびＴ_Fを含み、ここでＴ_BとＴ_Fはそれぞれ背景領域と前景領域で、Ｔ_Uは残りの領域（未知の領域）である。簡素化のために、Ｔ_B、Ｔ_U、およびＴ_Fは本明細書において、それぞれＢ、Ｕ、およびＦ領域と呼ぶことがある。ユーザーはＴ_BとＴ_Uを供給することによって２領域マップを初期設定できる（図１を参照して述べたように）。さらに、Ｔ_UおよびＴ_Fは当初同じ値をもつ（例えば、図１の方形（１０４）の内部）。画像データは以下に述べるようにモデル化できる。

グラフカットのためのエネルギーの指定
画像は、それぞれ色空間にある画素ｚ_nを含むと考える。色空間は赤緑青（ＲＧＢ）色空間でよい。混合ガウスモデル（ＧＭＭ）のような確率分布などの分布を用いて、色空間における色分布を実装できる。例えば、各ＧＭＭ（１つが背景用で１つが前景用）をＫ成分（例Ｋ＝５）をもつ全相関混合正規確率分布と考えることができる。また、ヒストグラムを利用してもよい（例えば、白黒実装の場合）。分布の代わりに、識別法を用いて、ある色分布に属する画素の尤度を定義することもできる。以下詳細に述べるように、他の画像特徴や特性を用いることもできる。

ＧＭＭを扱いやすくするために、最適化フレームワークでは、ｋ_n∈｛１，．．．，Ｋ｝として追加ベクトルｋ＝｛ｋ₁，．．．ｋ_n，．．．，Ｋ_N｝を用いて、不透明度値（これは画像のハードセグメンテーションを表す）としてα_n＝０又は１に従い、各画素に固有のＧＭＭ成分（背景又は前景モデルのうちのいずれかから１成分）を割り当てる。

そのため、ＧＭＭ成分はＴ_Uの各ｎの画素に、以下のように割り当てることができる。

図５を参照して、前景分布と背景分布の特性を判断する（５０４）。これら特性は、ユーザーが５０２で定義する手元、前景および/又は背景の領域に関する情報を含むことができる。色、にじみ等などの多くの様々な特徴も特性として利用できることが予見される。一実施例において、ＧＭＭパラメータは以下詳細に述べるようにデータｚから分かる。

分割のギブスのエネルギーは以下のように定義できる（５０６）。

ここでパラメータ

は画像の前景および背景分布（例えば、工程５０４で分かる）を表し、Ｖは色空間のユークリッド距離で計算するコントラスト項を使った平滑度項であり、Ｕは不透明度分布

のデータｚへの適合度を評価し、パラメータ

を与えて、色ＧＭＭモデルを考慮すると、以下の通りになる。

ここで

で、

はガウス確率分布、

は混合加重係数であり、そのため（定数まで含めて）以下のようになる。

そのため、モデルのパラメータは次のようになる。

（したがって、モデルのパラメータは、背景および前景分布の２Ｋガウス成分の加重π、平均μ、共分散Σである。）。平滑度項Ｖ項は次のように計算する（定数項を色空間のユークリッド距離を用いて計算する場合）。

ここでＣは隣接する画素対の集合である。定数β＝０のとき、平滑度項は、定数γで決まる程度まで、あらゆる場所で平滑度を促す単によく知られたイジングプライヤ（Ｉｓｉｎｇ Ｐｒｉｏｒ）である。一実施例において、βを０より大きくして、ハイコントラストの領域で平滑への傾向を緩和してもよい。定数βは次のように決めることができる。

ここで＜（ｚ_m−ｚ_n）²＞はある画像サンプルにおける期待値を表す。一実施例において、このようなβの選択が、Ｖの指数項を適切にハイコントラストとローコントラストに切り換えさせる。

前述のエネルギーモデルを考慮に入れると、分割は大域最小値として以下のように推定できる。

従って、最小化は標準最小カットアルゴリズムを用いて行える。一実施例において、ワンショット最小カット推定アルゴリズムの代わりに、推定とパラメータ学習を交互にする反復技術を用いる（次項で詳細に述べる）。方法５００は前景および背景部分の計算によって続け（５０８）、これがエネルギー最小化の結果

となる。３領域マップ領域Ｔ_Bのすべての画素を背景に割り当て、Ｔ_Fのすべての画素を前景に割り当てる。Ｔ_Uの画素は、結果

によって、前景又は背景のいずれかに割り当てる。

反復エネルギー最小化による分割
図６は、反復グラフカットを用いて画像の部分を抽出するための例示的な方法６００を図示する。方法６００への入力は、背景部分と前景部分と図５を参照して述べたような特性であり（６０２）、さらにユーザー定義の２領域マップ又は３領域マップである。前景および背景部分を用いて、前景および背景特性を更新する（６０４）（例えば、図５の工程５０８で計算した部分に基づいて）。この更新プロセスは以下詳細に述べる。以下詳細に述べるように、前景および背景特性は、更新された前景および背景部分（最初に計算した背景および前景部分ではなく）に基づいて更新することもできる。

更新した前景および背景特性に基づいて（６０４）、前景および背景部分を更新する（６０６）。例えば、更新の工程は、最小カットアルゴリズムを実行して行うことができる（例えば、図５を参照して述べたワンショットバージョンや反復バージョン）。このプロセスは、新たな前景又は背景ラベルを推測する未知の領域Ｕを決定するために、初期のユーザー定義の２領域マップ又は３領域マップを使う。ユーザーインタラクションの場合（以下を参照）、ユーザーが編集した新たな２領域マップ又は３領域マップを使う。

方法６００は、収束が得られたと判断されるまで（６０８）、工程６０４から６０６を繰り返す。一実施例において、コンピュータプログラム（図１０を参照して述べるものなど）が収束が得られたかどうかを判断する（例えば、閾値を設定して）。収束が得られたと判断されたら、前景および/又は背景部分が出力される（６１０）。従って、方法６００は、一実施例において前景および背景特性と前景および背景部分を繰り返し更新することにより、ある画像の所要の部分を提供する。

一実施例において、方法６００の構造が、適切な収束特性（つまり、極小値に対し）を保証する。これは反復最小化の工程６０４から６０６のそれぞれが、

という３つの変数のセットに対して順番に全エネルギーＥの最小化になると示せるからである。そのため、Ｅは単調に減少し、これは以下詳細に述べるように、実際図８に図示される。

反復最小化は、ワンショットグラフカットアプローチに比べ、分割タスクを完了するのに必要なユーザーインタラクションの量を減らせることが予見される。これは２つの方法で明らかである。まず、初期設定と最適化の後に必要なユーザー編集の程度が減る。次に、初期のインタラクションは、例えば以下に説明するようにユーザーにより完全にラベリングしなくてよいことから、より簡単にできる。

まとめると、初期の３領域マップのＴ_U領域から新たにラベル付けした画素を用いて、前述の色ＧＭＭパラメータ

を精緻化する。そして、反復エネルギー最小化で、不透明度

つまり前景および背景部分の自動精緻化ができる。

前景および背景特性のモデル化と更新
図７は、前景および背景特性（例えば、図５の工程５０４を参照して述べたような）を決定するための例示的な方法７００を図示する。２領域マップ又は３領域マップの初期設定の後（図５を参照して述べたように）、モデル成分ｋ_n∈｛１，．．．，Ｋ｝を、各画素ｎに割り当てる（７０２）。工程７０２は、各画素ｎのｋ_n値の単純数え上げ法により行うことができる

（つまり、

）。

モデル化パラメータの集合（例えば、ガウス分布）を、データｚから以下のように求める（７０４）。

工程７０４は、以下のように、ガウス分布のパラメータ集合の推定手順として実施できる（これは期待値最大化（ＥＭ）としても知られる）。例えば前景モデルのあるＧＭＭ成分ｋの場合、画素の部分集合Ｆ（ｋ）＝｛ｚ_n：ｋ_n＝ｋかつα_n＝１｝が定義される。平均μ（α，ｋ）と共分散Σ（α，ｋ）は、サンプルの平均として標準的な方法で推定し、Ｆ（ｋ）の画素の値の共分散と加重は、次のように推定する。

ここで、｜Ｓ｜は集合Ｓのサイズを表す。

モデルのパラメータを計算した後、画素はモデル成分ｋ_n∈｛１，．．．，Ｋ｝に再割り当てできる。一実施例において、工程７０２および７０４を、収束（７０６）が得られるまで繰り返す。従って、この方法は、一実施例において極小値まで収束することを保証する。

方法７００の出力（７０８）はモデルのパラメータである（つまり、前景又は背景いずれかの特性）。この繰り返しアルゴリズムは、一実施例において前景と背景の特性を得るために個別に実施する。

反復最小化の収束
図８Ａは、エネルギーＥの例示的な単調減少と対応する背景および前景の分離を図示する。そして、初期設定時（図８Ｂ）と収束後（図８Ｃ）のＲＧＢ色空間（赤と緑を表示する側面）のＧＭＭが図示されている。背景（例、８０２）と前景（例、８０４）の両方に５混合成分に等しいＫを使用した。当初（図８Ｂ）、ＧＭＭは両方ともかなり重なり合っていたが、前景／背景のラベリングが正確になるにつれて、収束後（図８Ｃ）にはよりよく分離する。

ユーザーインタラクションと不完全な３領域マップ
反復最小化方法７００で、ユーザーインタラクションの使いやすさを増すことができる。特に、不完全なラベリングが実行可能になり、完全な３領域マップＴの代わりに、ユーザーはＴ_F＝０としたまま背景領域Ｔ_B、つまり２領域マップを指定するだけでよい（例えば、図２の工程５０２を参照して述べたように）。厳密な前景ラベリングは一切必要ない。

一実施例において、反復最小化（図７）は、この不完全性を、後述するように後で取外せる一部の画素に仮のラベルをつけることによって処理する。

その後のユーザー編集
初期の不完全なユーザーラベリングは、多くの場合完全な分割を自動的に完了させるのに十分であることが予見される。代わりに、画素のブラッシング、それを固定した前景又は固定した背景のいずれかに拘束して、その後ユーザー編集を行ってもよい。ブラッシングの後、図５のようなワンショット分割を適用できる。さらに、ユーザー編集後に、色モデルも更新するオプションの「精緻化」を適用してもよい。つまり、反復グラフカットは図６に関して述べるように適用されるということである。これが、一部の実施例で有益な方法で編集操作の効果を高める。さらに、分割は、知能ハサミ（ｉｎｔｅｌｌｉｇｅｎｔ ｓｃｉｓｓｏｒｓ）（別名、ライブワイヤ（ｌｉｖｅ ｗｉｒｅ）又はマグネット投げ縄（ｍａｇｎｅｔｉｃ ｌａｓｓｏ））などの既存のツールで変更できることが予見される。

一実施例において、ユーザー編集を適用して、オブジェクト抽出を改善できる。例えば、ユーザー編集を次のように適用できる。（１）前景から背景への移行部分でコントラストが低い領域が存在する場所、（２）真の前景および背景分布が色空間で部分的に重なり合っているように見える状況、又は（３）選択したユーザーの方形内の背景素材が、背景領域にたまたま十分に現れない場合。

図９に例示的なケースを示す。初期のユーザーインタラクションと分割の後（それぞれ、９０２と９０４）、その後のユーザー編集（９０６）が所要の結果を提供する。一実施例において、間違ってラベル付けしたエリアの部分だけを大まかにブラッシングすればよい（９０６）。ブラッシングの後、推定工程７０６を適用して、所要の結果が得られる、つまり不正確にラベル付けしたエリアでブラッシングしたラベル（９０６から）を適切に伝播する。

ハードウェアの実装
図１０は、本明細書で説明する技術を実施するために使用できる一般的なコンピュータ環境１０００を図示する。例えば、コンピュータ環境１０００を利用して、これ以前の図に対して述べたタスクの実施に関連した命令を実行できる。コンピュータ環境１０００はコンピューティング環境の単なる１例であり、使用の範囲やコンピュータおよびネットワーク・アーキテクチャの機能性に関して、制限を示唆するつもりはない。コンピュータ環境１０００を、例示的なコンピュータ環境１０００に図示される成分のいずれか１つ又はその組合せに関して、従属性又は必要条件をもつと解釈してはならない。

コンピュータ環境１０００は、コンピュータ１００２の形態の汎用コンピューティングデバイスを備える。コンピュータ１００２のコンポーネントは、一又は複数のプロセッサもしくはプロセッシングユニット１００４（オプションで、暗号プロセッサ又は共同プロセッサを備える）と、システムメモリ１００６と、プロセッサ１００４などの様々なシステムコンポートントをシステムメモリ１００６に連結するシステムバス１００８とを備えるが、それだけに限定されない。

システムバス１００８は、メモリバスやメモリコントローラー、周辺バス、アクセラレイテッドグラフィックスポート（グラフィック専用高速バス）、様々なバスアーキテクチャのいずれかを使用するプロセッサやローカルバスなど、数種類のバス構造のいずれか一又は複数を表す。例として、前記アーキテクチャとして、ＩＳＡ（Ｉｎｄｕｓｔｒｙ Ｓｔａｎｄａｒｄ Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＭＣＡ（Ｍｉｃｒｏ Ｃｈａｎｎｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、拡張ＩＳＡ（ＥＩＳＡ）バス、ＶＥＳＡ（Ｖｉｄｅｏ Ｅｌｅｃｔｒｏｎｉｃｓ Ｓｔａｎｄａｒｄｓ Ａｓｓｏｃｉａｔｉｏｎ）ローカルバス、メザニン（Ｍｅｚｚａｎｉｎｅ）バスとしても知られるＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔｓ）バスがあげられよう。

コンピュータ１００２は典型的には、様々なコンピュータ読取可能媒体を備える。前記媒体はコンピュータ１００２からアクセス可能な利用できるあらゆる媒体で、揮発性および不揮発性媒体、取外し可能および取外し不可能な媒体のどちらも含む。

システムメモリ１００６は、ランダムアクセスメモリ（ＲＡＭ）１０１０などの揮発性メモリ形態、および/又は読取専用メモリ（ＲＯＭ）１０１２などの不揮発性メモリの形態のコンピュータ読取可能媒体を備える。起動時などにコンピュータ１００２内のエレメント間で情報を伝送するのに役立つ基本ルーチンを内蔵する基本入出力システム（ＢＩＯＳ）１０１４がＲＯＭ１０１２に記憶される。ＲＡＭ１０１０は典型的には、プロセッシングユニット１００４に即座にアクセス可能な、および/又はプロセッシングユニット１００４で現在動作しているデータおよび/又はプログラムモジュールを内蔵する。

コンピュータ１００２は、他の取外し可能／取外し不可能な、揮発性／不揮発性のコンピュータ記憶媒体を備えてもよい。例として、図１０は、取外し不可能な不揮発性磁気媒体（図示せず）に対して読取りと書き込みをするためのハードディスクドライブ１０１６と、取外し可能な不揮発性磁気ディスク１０２０（例えば、「フロッピー（登録商標）ディスク」）に対して読取りと書き込みをするための磁気ディスクドライブ１０１８と、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、又はその他の光学媒体などの取外し可能な不揮発性光学ディスク１０２４に対して読取りおよび/又は書き込みをするための光学ディスクドライブ１０２２を図示する。ハードディスクドライブ１０１６、磁気ディスクドライブ１０１８、および光学ディスクドライブ１０２２はそれぞれ、一又は複数のデータ媒体インターフェース１０２６でシステムバス１００８に接続される。代わりに、ハードディスクドライブ１０１６、磁気ディスクドライブ１０１８、および光学ディスクドライブ１０２２は、一又は複数のインターフェース（図示せず）によりシステムバス１００８に接続することができる。

ディスクドライブとその関連のコンピュータ読取可能媒体は、コンピュータ読取可能命令、データ構造、プログラムモジュール、およびコンピュータ１００２のその他のデータの不揮発性記憶装置となる。例はハードディスク１０１６、取外し可能磁気ディスク１０２０、および取外し可能光学ディスク１０２４を図示しているが、磁気カセットやその他磁気記憶装置、フラッシュメモリーカード、ＣＤ−ＲＯＭ、ＤＶＤ（ｄｉｇｉｔａｌ ｖｅｒｓａｔｉｌｅ ｄｉｓｋｓ）やその他光学記憶装置、ランダムアクセスメモリ（ＲＡＭ）、読取専用メモリ（ＲＯＭ）、電気消去及びＥＥＰＲＯＭ（ｅｌｅｃｔｒｉｃａｌｌｙ ｅｒａｓａｂｌｅ ｐｒｏｇｒａｍｍａｂｌｅ ｒｅａｄ−ｏｎｌｙ ｍｅｍｏｒｙ）等など、コンピュータがアクセス可能なデータを記憶できる他の種類のコンピュータ読取可能媒体も、例示的なコンピューティングシステムおよび環境を実施するのに利用できることは理解されるべきである。

ハードディスク１０１６、磁気ディスク１０２０、光学ディスク１０２４、ＲＯＭ１０１２、および/又はＲＡＭ１０１０には、例としてオペレーティングシステム１０２６、一又は複数のアプリケーションプログラム１０２８、他のプログラムモジュール１０３０、およびプログラムデータ１０３２を始めとし、任意の数のプログラムモジュールが記憶できる。前記オペレーティングシステム１０２６、一又は複数のアプリケーションプログラム１０２８、他のプログラムモジュール１０３０、およびプログラムデータ１０３２（又はそのいくつかの組合せ）のそれぞれは、分散ファイルシステムをサポートする常駐コンポーネントの全部もしくは一部を実装できる。

ユーザーはキーボード１０３４やポインティングデバイス１０３６（例えば、「マウス」）などの入力デバイスを介して、コマンドと情報をコンピュータ１００２に入力できる。その他の入力デバイス１０３８（具体的には図示せず）としては、マイクロフォン、ジョイスティック、ゲームパッド、衛星アンテナ、シリアルポート、スキャナー、および/又は同様の物があげられよう。上記およびその他の入力デバイスは、システムバス１００８に連結される入出力インターフェース１０４０を介してプロセッシングユニット１００４に接続されるが、パラレルポート、ゲームポート、又はユニバーサルシリアルバス（ＵＳＢ）などの他のインターフェースやバス構造で接続してもよい。

モニター１０４２又は他の種類のディスプレイ装置も、ビデオアダプタ１０４４などのインターフェースを介してシステムバス１００８に接続できる。モニター１０４２に加えて、他の出力用周辺機器として、入出力インターフェース１０４０を介してコンピュータ１００２に接続できるスピーカー（図示せず）やプリンター１０４６などのコンポーネントがあげられよう。

コンピュータ１００２は、リモート・コンピューティング・デバイス１０４８などの一又は複数のリモートコンピュータへの論理接続を使用して、ネットワーク接続環境で動作できる。例として、リモート・コンピューティング・デバイス１０４８は、パーソナルコンピュータ、携帯型コンピュータ、サーバー、ルーター、ネットワークコンピュータ、ピアデバイスやその他共有ネットワークノード、ゲーム機などがあろう。リモート・コンピューティング・デバイス１０４８は、コンピュータ１００２に関連した本明細書で述べる要素および特徴の多くもしくはすべてを内蔵できる携帯型コンピュータとして図示される。

コンピュータ１００２とリモートコンピュータ１０４８の論理接続は、ローカルエリアネットワーク（ＬＡＮ）１０５０と汎用広域ネットワーク（ＷＡＮ）１０５２として図示される。前記ネットワーク接続環境は、職場、企業内コンピュータネットワーク、イントラネット、およびインターネットにおいて一般的である。

ＬＡＮネットワーク接続環境に実装するとき、コンピュータ１００２はネットワークインターフェース又はアダプタ１０５４を介してローカルネットワーク１０５０に接続される。ＷＡＮネットワーク接続環境に実装するとき、コンピュータ１００２は典型的には、モデム１０５６又は広域ネットワーク１０５２で通信を確立するための他の手段を備える。モデム１０５６は、コンピュータ１００２の内部にあっても外部接続してもよいが、入出力インターフェース１０４０又はその他適切なメカニズムを介してシステムバス１００８に接続できる。図示するネットワーク接続は例示的なものであり、コンピュータ１００２と１０４８の間の通信リンクを確立する他の手段も採用できることは理解されるべきである。

コンピューティング環境１０００とともに図示するもののようなネットワーク接続環境において、コンピュータ１００２に関連して描かれるプログラムモジュール、もしくはその一部は、リモートメモリデバイスに記憶できる。例として、リモートアプリケーションプログラム１０５８がリモートコンピュータ１０４８のメモリ装置に常駐する。分かりやすくするために、アプリケーションプログラムや、オペレーティングシステムなどのその他実行可能プログラムコンポーネントが本明細書では個別のブロックとして図示されているが、前記プログラムやコンポーネントは様々な場合においてコンピューティングデバイス１００２の様々な記憶コンポーネントに存在し、コンピュータのデータプロセッサで実行されることは認められる。

一又は複数のコンピュータやその他のデバイスで実行するプログラムモジュールなど、コンピュータ実行可能命令の一般的な状況において、様々なモジュールや技術が本明細書で説明できる。一般的に、プログラムモジュールは、特定のタスクを実行したり、特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。典型的には、プログラムモジュールの機能性は、様々な実装に相応しいように組合せ又は分散できる。

これらモジュールおよび技術の実装は、ある形態のコンピュータ読取可能媒体に記憶、又は伝送できる。コンピュータ読取可能媒体は、コンピュータでアクセス可能な利用できるあらゆる媒体が考えられる。限定するのではなく、例示すると、コンピュータ読取可能媒体は、「コンピュータ記憶媒体」と「通信媒体」から構成できる。

「コンピュータ記憶媒体」には、コンピュータ読取可能命令、データ構造、プログラムモジュール、又はその他のデータなどの情報を記憶するためのあらゆる方法又は技術で実施される揮発性および不揮発性、取外し可能および取外し不可能な媒体が含まれる。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリやその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）又はその他光学記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置又はその他磁気記憶装置、あるいは所望の情報を記憶するために使え、コンピュータでアクセスできるあらゆるその他の媒体が含まれるが、それだけに限定されない。

「通信媒体」には、代表的にはコンピュータ読取可能命令、データ構造、プログラムモジュール、搬送波やその他伝達メカニズムなどの変調データ信号におけるその他のデータが含まれる。通信媒体はあらゆる情報配信媒体も含まれる。「変調データ信号」という用語は、その特徴集合のうち一又は複数をもち、又は信号の情報を符号化するためのような方法で変更した信号を意味する。限定するものではなく、例示すると、通信媒体には、ワイヤードネットワークやダイレクトワイヤ接続などのワイヤード媒体、音響、無線周波数（ＲＦ）、赤外線（ＩＲ）、ワイヤレス標準規格に準拠した製品（例えば、ＩＥＥＥ ８０２．１１ｂのワイヤレスネットワーク接続（Ｗｉ−Ｆｉ）、セルラー、ブルートゥース使用可能媒体、およびその他ワイヤレス媒体が含まれる。上記いくつかの組合せも、コンピュータ読取可能媒体の範囲に含まれる。

ある画像の一部を抽出するための例示的なフロー図を示す図である。 図１を参照して述べた抽出した部分１０６の断片に境界マッティングを適用した後の様々な結果を示す図である。 図１を参照して述べた抽出した部分１０６の断片に境界マッティングを適用した後の様々な結果を示す図である。 図１を参照して述べた抽出した部分１０６の断片に境界マッティングを適用した後の様々な結果を示す図である。 オブジェクトの境界に沿って連続する透明度（又はアルファ値）を生成するための例示的な境界マッティング法を示す図である。 ３領域マップに分割された原画を示す図である。 輪郭線Ｃに関連した輪郭線のパラメータ化と距離マップの表記法を示す図である。 図４Ａの画像に対応する中心Δ、幅σのときのαプロファイルｇのソフトステップ関数を示す図である。 ユーザー定義の２領域マップ又は３領域マップに適用されるグラフカットを使って画像の一部を抽出するための例示的な方法を示す図である。 反復グラフカットを使って画像の一部を抽出するための例示的な方法を示す図である。 前景および背景特性の判断のための例示的な方法を示す図である。 （Ａ）はエネルギーＥを示す図であり、（Ｂ）は初期のエネルギーＥに対応する背景および前景の分離を示す図であり、（Ｃ）は収束したエネルギーＥに対応する背景および前景の分離を示す図である。 ユーザー編集の例示的な結果を示す図である。 本明細書で説明する技術を実装するために使える一般的なコンピュータ環境を示す図である。

Claims (28)

1. 前景領域と背景領域を有する分割した画像を受信することと、
   前景領域と背景領域との境界線に沿って輪郭線を判断することと、
   輪郭線から広がる未知の領域の画素のアルファマップの一又は複数のパラメータに対応するエネルギー関数を定義することと、
   定義したエネルギー関数を最小化することによって、アルファマップの中心パラメータと幅パラメータを推定すること、および
   推定した中心パラメータと幅パラメータに対応するアルファマップを計算すること、
   を備えたことを特徴とする方法。
2. 請求項１に記載の方法において、画像を２領域マップ又は３領域マップとして分割することを特徴とする方法。
3. 請求項１に記載の方法において、未知の領域を３領域マップで定義することを特徴とする方法。
4. 請求項１に記載の方法において、エネルギー関数が、スムージング正則化項とデータ尤度項からなるグループから選択される一又は複数の項を有することを特徴とする方法。
5. 請求項１に記載の方法において、輪郭線を未知の領域の境界線に曲線フィッティング技術を適用して求めることを特徴とする方法。
6. 請求項１に記載の方法において、輪郭線を未知の領域の境界にポリラインをフィットして求めることを特徴とする方法。
7. 請求項１に記載の方法において、分割した画像をハードセグメンテーションによって提供することを特徴とする方法。
8. 請求項１に記載の方法において、エネルギー最小化をダイナミックプログラミングによって行うことを特徴とする方法。
9. 請求項１に記載の方法において、画像分割をユーザーが定義することを特徴とする方法。
10. 請求項１に記載の方法において、２領域マップ分割画像の場合、輪郭線から広がる未知の領域を決定することをさらに備えたことを特徴とする方法。
11. 請求項１に記載の方法において、背景領域からの色にじみを抑えるために、一又は複数の前景の画素の色を推定することをさらに備えたことを特徴とする方法。
12. 請求項１に記載の方法において、背景領域からの色にじみを抑えるために一又は複数の前景の画素の色を推定することをさらに備え、前景の画素の色を推定することが、
    第１画素の前景の色の推定値を得るためにベイズマット法を適用すること、および
    第１画素の推定した前景の色に色が最も類似した第１画素の近傍にある第２前景画素から画素の色を借用すること、
    を備えたことを特徴とする方法。
13. 前景領域と背景領域を有する２領域マップ分割画像を受信することと、
    前景領域と背景領域との境界線に沿って輪郭線を判断することと、
    輪郭線から広がる未知の領域を決定することと、
    未知の領域の画素のエネルギー関数を定義することであって、前記エネルギー関数は、スムージング正則化項とデータ尤度項を含むグループから選択した一又は複数の項を有することと、
    定義したエネルギー関数を最小化することによって、アルファマップの中心パラメータと幅パラメータを推定すること、および
    推定した中心パラメータと幅パラメータに対応するアルファマップを計算すること、
    を備えたことを特徴とする方法。
14. 請求項１３に記載の方法において、曲線フィッティング技術を未知の領域の境界線に適用して輪郭線を求めることを特徴とする方法。
15. 請求項１３に記載の方法において、２領域マップがハードセグメンテーションで提供されることを特徴とする方法。
16. 請求項１３に記載の方法において、エネルギー最小化をダイナミックプログラミングにより行うことを特徴とする方法。
17. 請求項１３に記載の方法がさらに、背景領域からの色にじみを抑えるために、一又は複数の前景の画素の色を推定することからなることを特徴とする方法。
18. 請求項１３に記載の方法がさらに、背景領域からの色にじみを抑えるために一又は複数の前景の画素の色を推定することからなり、前景の画素の色を推定することが、
    第１画素の前景の色の推定値を得るためにベイズマット法を適用すること、および
    第１画素の推定した前景の色に色が最も類似した第１画素の近傍にある第２前景画素から画素の色を借用すること、
    からなることを特徴とする方法。
19. 実行時に機械に動作を行うよう指示する命令を記憶する一又は複数のコンピュータ読取可能媒体であって、前記動作は、
    前景領域と背景領域を有する分割した画像を受信することと、
    前景領域と背景領域との境界線に沿って輪郭線を判断することと、
    輪郭線から広がる未知の領域の画素のアルファマップの一又は複数のパラメータに対応するエネルギー関数を定義することと、
    定義したエネルギー関数を最小化することによって、アルファマップの中心パラメータと幅パラメータを推定すること、および
    推定した中心パラメータと幅パラメータに対応するアルファマップを計算すること、
    を備えたことを特徴とする一又は複数のコンピュータ読取可能媒体。
20. 請求項１９に記載の一又は複数のコンピュータ読取可能媒体において、画像を２領域マップ又は３領域マップとして分割することを特徴とする一又は複数のコンピュータ読取可能媒体。
21. 請求項１９に記載の一又は複数のコンピュータ読取可能媒体において、未知の領域を３領域マップで定義することを特徴とする一又は複数のコンピュータ読取可能媒体。
22. 請求項１９に記載の一又は複数のコンピュータ読取可能媒体において、エネルギー関数が、スムージング正則化項とデータ尤度項からなるグループから選択した一又は複数の項を有することを特徴とする一又は複数のコンピュータ読取可能媒体。
23. 請求項１９に記載の一又は複数のコンピュータ読取可能媒体において、未知の領域の境界線に曲線フィッティング技術を適用して輪郭線を決定することを特徴とする一又は複数のコンピュータ読取可能媒体。
24. 請求項１９に記載の一又は複数のコンピュータ読取可能媒体において、分割した画像がハードセグメンテーションで提供されることを特徴とする一又は複数のコンピュータ読取可能媒体。
25. 請求項１９に記載の一又は複数のコンピュータ読取可能媒体において、エネルギー最小化をダイナミックプログラミングにより行うことを特徴とする一又は複数のコンピュータ読取可能媒体。
26. 請求項１９に記載の一又は複数のコンピュータ読取可能媒体において、画像分割をユーザーが定義することを特徴とする一又は複数のコンピュータ読取可能媒体。
27. 請求項１９に記載の一又は複数のコンピュータ読取可能媒体において、動作がさらに、背景領域からの色にじみを抑えるために、一又は複数の前景の画素の色を推定するための工程からなることを特徴とする一又は複数のコンピュータ読取可能媒体。
28. 請求項１９に記載の一又は複数のコンピュータ読取可能媒体において、動作がさらに、背景領域からの色にじみを抑えるために、一又は複数の前景の画素の色を推定することからなり、前景の画素の色を推定することが、
    第１画素の前景の色の推定値を得るために、ベイズマット法を適用すること、および
    第１画素の推定した前景の色に色が最も類似した第１画素の近傍にある第２前景画素から画素の色を借用すること、
    からなることを特徴とする一又は複数のコンピュータ読取可能媒体。