(57)【特許請求の範囲】
【請求項１】
画像をセグメント化する方法であって、前記方法は、
前記画像に対する複数のセグメント表示を受信するステップであって、各セグメント表示は、画素領域の集合、及び、前記画素領域の集合と複数のセグメントクラスのうちの関連セグメントクラスとの間の関係を特定する、ステップと、
前記画像に対する複数の境界表示を受信するステップであって、各境界表示は、前記複数のセグメントクラスのうちの異なるセグメントクラスに属する画素間の境界を特定する、ステップと、
前記複数のセグメント表示と前記複数の境界表示の両方に応じて、前記複数のセグメントクラスへ前記画像をセグメント化するステップとを有する、方法。
【請求項２】
前記セグメント化するステップが、
少なくとも第１のセグメント表示によって特定される各画素領域へセグメントクラスリンク値を割り当てるステップであって、前記セグメントクラスリンク値は前記画素領域と前記第１のセグメント表示の関連セグメントクラスとのリンクを示す、ステップと、
前記画像中の未割り当て画素領域にセグメントクラスリンク値を伝播させるステップと、
前記セグメントクラスリンク値の伝播を境界表示において減衰させるステップとを有する、請求項１に記載の方法。
【請求項３】
前記セグメントクラスリンク値の伝播がさらに前記画素領域に対する視覚的特性の類似性に依存する、請求項２に記載の方法。
【請求項４】
前記セグメント化するステップが、
第１のセグメントクラスと関連する少なくとも１つのセグメント表示によって特定される画素領域へ、前記複数のセグメントクラスのうちの前記第１のセグメントクラスに対する第１のセグメントクラスリンク値を割り当てるステップであって、各セグメントクラスリンク値は前記画素領域と前記第１のセグメントクラスとの間のリンク強度表示を与える、ステップと、
画素領域のグループに対する前記第１のセグメントクラスに対するセグメントクラスリンク値を決定するステップと、
前記画素領域のグループのうちの少なくとも一部の画素領域に対して、前記画素領域に対する前記第１のセグメントクラスに対する前記セグメントクラスリンク値に応じて前記複数のセグメントクラスのうちの１つのセグメントクラスを選択するステップとを有し、
前記セグメントクラスリンク値を決定するステップが、
前記画素領域のグループのうちの各画素領域に対するセグメントクラスリンク値を、画素領域の近傍集合のセグメントクラスリンク値の組み合わせとして決定するステップであって、前記組み合わせは境界表示によって前記各画素領域から分離される前記画素領域の近傍集合のうちのいずれかに依存する、ステップを有する、請求項１に記載の方法。
【請求項５】
前記割り当てるステップが、前記第１のセグメントクラスリンク値を割り当てられていない少なくとも一部の画素領域に初期セグメントクラスリンク値を割り当てるステップをさらに有し、前記初期セグメントクラスリンク値は前記第１のセグメントクラスリンク値よりも弱い前記第１のセグメントクラスへのリンクを示す、請求項４に記載の方法。
【請求項６】
前記組み合わせは、前記画素領域の近傍集合のうちの分離画素領域に対するセグメントクラスリンク値の重み付けが減少するようになっており、前記分離画素領域は境界表示によって前記各画素領域から分離される画素領域である、請求項４に記載の方法。
【請求項７】
前記分離画素領域の重み付けがゼロである、請求項６に記載の方法。
【請求項８】
前記画素領域の近傍集合のうちの近傍画素領域に対するセグメントクラスリンク値の重み付けが、前記近傍画素領域の視覚的特性及び前記各画素領域の視覚的特性に対する類似性測定に依存する、請求項４に記載の方法。
【請求項９】
前記画素領域の集合のうちの各画素領域に対するセグメントクラスリンク値を決定するステップが、前記画素領域のグループのうちの各画素領域に対して前記セグメントクラスを選択するステップの前に繰り返される、請求項４に記載の方法。
【請求項１０】
前記複数のセグメントクラスのうちの第２のセグメントクラスに対する第２のセグメントクラスリンク値を、前記第２のセグメントクラスと関連する少なくとも１つのセグメント表示によって特定される画素領域へ割り当てるステップであって、各セグメントクラスリンク値は前記画素領域と前記第２のセグメントクラスとの間のリンク強度表示を与える、ステップと、
前記第２のセグメントクラスに対する画素領域のグループに対するセグメントクラスリンク値を決定するステップとをさらに有し、
前記画素領域のグループのうちの各画素領域に対して前記セグメントクラスを選択するステップが、第１の画素領域に対して前記セグメントクラスを、前記第１のセグメントクラスに対する前記第１の画素領域に対するセグメントクラスリンク値と、前記第２のセグメントクラスに対する前記第１の画素領域に対するセグメントクラスリンク値の比較に応じて、選択するステップを有する、
請求項４に記載の方法。
【請求項１１】
前記画像のセグメンテーションをユーザに提示するステップと、
前記画像に対する新たなセグメント表示と新たな境界表示のうちの少なくとも１つのユーザ入力を受信するステップと、
前記新たなセグメント表示と前記新たな境界表示のうちの少なくとも１つに応じて前記セグメンテーションを更新するステップとをさらに有する、請求項１に記載の方法。
【請求項１２】
いかなる境界表示又はセグメント表示にも基づかない初期セグメンテーションによって画素領域を生成するステップをさらに有する、請求項１に記載の方法。
【請求項１３】
前記セグメント化が奥行きマップのセグメント化である、請求項１に記載の方法。
【請求項１４】
請求項１乃至１３のいずれか一項に記載の方法を実行するためのコンピュータプログラム。
【請求項１５】
画像をセグメント化するための装置であって、前記装置は、
前記画像に対する複数のセグメント表示を受信するための手段であって、各セグメント表示は、画素領域の集合、及び前記画素領域の集合と複数のセグメントクラスのうちの関連セグメントクラスとの関係を示す、手段と、
前記画像に対する複数の境界表示を受信するための手段であって、各境界表示は前記複数のセグメントクラスのうちの異なるセグメントクラスに属する画素間の境界を特定する、手段と、
前記複数のセグメント表示と前記複数の境界表示の両方に応じて前記複数のセグメントクラスへ前記画像をセグメント化するための手段とを有する、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像のセグメンテーションに関し、特に、限定はされないがビデオ信号の画像のセグメンテーションに関する。
【背景技術】
【０００２】
画像のセグメンテーションは多くのデジタル画像処理技術にとって重要なプロセスである。例えば、画像セグメンテーションは三次元画像化のための奥行きマップ生成、オブジェクト識別、人工着色などのために使用され得る。オペレータによる効率的でインタラクティブな画像セグメンテーションは、例えばデジタル写真及び画像処理又はビデオ若しくはデジタル画像の撮影後編集において重要である。例えば立体ビデオの奥行きマップ若しくは視差マップの生成は、奥行き若しくは視差を正確に割り当てるためにオブジェクト境界の指定を必要とする。
【０００３】
インタラクティブな画像セグメンテーションを実行するための方法例は、論文"ＧｒａｂＣｕｔ‐Ｉｎｔｅｒａｃｔｉｖｅ  Ｆｏｒｅｇｒｏｕｎｄ  Ｅｘｔｒａｃｔｉｏｎ  ｕｓｉｎｇ  Ｉｔｅｒａｔｅｄ  Ｇｒａｐｈ  Ｃｕｔｓ"ｂｙ  Ｃａｒｓｔｅｎ  Ｒｏｔｈｅｒ，Ｖｌａｄｉｍｉｒ  Ｋｏｌｍｏｇｏｒｏｖ，Ａｎｄｒｅｗ  Ｂｌａｋｅ，Ａｕｇｕｓｔ  ２００４，ＳＩＧＧＲＡＰＨ（Ｓｐｅｃｉａｌ  Ｉｎｔｅｒｅｓｔ  Ｇｒｏｕｐ  ｏｎ  ＧＲＡＰＨｉｃｓ  ａｎｄ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｔｅｃｈｎｉｑｕｅｓ）２００４（ｈｔｔｐ：／／ｒｅｓｅａｒｃｈ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ／ｖｉｓｉｏｎ／Ｃａｍｂｒｉｄｇｅ／ｐａｐｅｒｓ／ｓｉｇｇｒａｐｈ０４．ｐｄｆで入手できる）に見つけられる。
【０００４】
現在、関心オブジェクトが位置する場所を大まかに特定するためにいわゆる'スクリブル'を置くことに基づく効率的なセグメンテーションのための方法が存在する。スクリブルは通常、特定オブジェクトに属することがわかっている、すなわち同じセグメントに属することがユーザによって示される画素を特定するために、ユーザによって画像上に手動で描かれる曲線である。例えばスクリブルは、下層の画素が画像オブジェクトの一部であることを特定するために画像オブジェクトの内部に描かれ得る。そしてセグメント化領域は、（例えば色遷移の検出によって）オブジェクトのエッジに達したと推定されるまで隣接画素を同じセグメントに割り当てながら、スクリブルから展開し得る。代替的に又は付加的に、特定オブジェクトに属さないことがユーザによって示される、従って画像オブジェクトセグメントに含まれるべきではない複数の画素を特定するスクリブルが描かれ得る（通常は画像オブジェクトセグメントに相補的なセグメントに含まれるべき複数の画素を定義するスクリブルに相当する）。この場合、同じアプローチは、遷移が検出されるまで画像オブジェクトに対応するセグメント以外のセグメントに画素を割り当てるために使用され得る。例えば、オブジェクト外スクリブルは背景画素を定義するために使用され得、オブジェクト内スクリブルは前景オブジェクトに対する前景画素を定義するために使用され得る。こうしたスクリブルを持つ画像の一例が図１に図示される。
【０００５】
しかしながら、こうしたアプローチは画像のセグメンテーションを支援し得るものの、多くの画像に次善の性能を提供し得る。例えば、隣接オブジェクト間の色遷移が非常に小さいか又はない場合、アルゴリズムは異なるセグメント間の最適で明確な分離をもたらさないことが多い。このセグメンテーション精度の低下はさらにより正確で詳細なスクリブルを置くことによって軽減され得るが、これは必要なユーザインタラクションを大幅に増加させ、煩雑で面倒なプロセスをもたらす。
【０００６】
インタラクティブセグメンテーションのために提案されている別のアプローチは、ユーザが異なるオブジェクト間のエッジを直接定義することである。例えば、ユーザは画像オブジェクトの特定の輪郭をトレースし得、セグメンテーションは、輪郭の片側の画素をあるセグメントに、反対側の画素を別のセグメントに割り当てることによって、異なるセグメント間の境界の定義としてこれを使用し得る。しかしながら、このアプローチはユーザにとって非常に難しく時間がかかる傾向があり、セグメンテーションをもたらすためにユーザが手動で多くの（又は全ての）輪郭をトレースすることを要求する。従って、セグメンテーションアプローチは非常に面倒で煩雑である。さらに、ユーザが入力した輪郭は下層のオブジェクトエッジに厳密に一致しない可能性があるため、結果として得られるセグメンテーションはしばしば次善のものであり得る。また、１つよりも多くのセグメントが輪郭の片側にあらわされる場合、個々の画素がどのセグメントに属するかを厳密に特定することは困難であり得る。ユーザ定義輪郭を持つ画像の一例は図２に図示される。
【０００７】
従って、画像セグメンテーションへの改良されたアプローチが有利であり、特に増加した柔軟性、減少した複雑性、減少したユーザインタラクション、改良されたセグメンテーション及び／又は改良された性能を可能にするシステムが有利である。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従って本発明は、好適には上述の欠点の１つ以上を単独で又は任意の組み合わせで軽減、緩和、又は除去しようとする。
【課題を解決するための手段】
【０００９】
本発明の一態様によれば、画像をセグメント化する方法が提供され、該方法は、画像に対する複数のセグメント表示を受信するステップであって、各セグメント表示は、画素領域の集合、及び、画素領域の集合と複数のセグメントクラスのうちの関連セグメントクラスとの間の関係を特定する、ステップと、画像に対する複数の境界表示を受信するステップであって、各境界表示は、複数のセグメントクラスのうちの異なるセグメントクラスに属する画素間の境界を特定する、ステップと、複数のセグメント表示と複数の境界表示の両方に応じて、画像を複数のセグメントクラスにセグメント化するステップとを有する。
【００１０】
本発明は改良されたセグメンテーションを提供し得る。特に、ユーザが提供するセグメント表示と境界表示に基づく改良されたインタラクティブ画像セグメンテーションが実現されることができる。本発明は特に、依然として半自動セグメンテーションを可能にしながら、強い視覚的遷移を示さないオブジェクトエッジ周辺の改良されたセグメンテーションを可能にし得る。所与の画像及びセグメンテーション精度に必要なユーザインタラクションは多くの実施形態において削減され得る。
【００１１】
セグメント化は、画素領域をセグメントクラスに割り当てるときにセグメント表示と画像表示の両方を同時に考慮する複合セグメンテーションであり得る。セグメント化は、セグメント表示からのセグメントクラス割り当ての伝播に基づくセグメントクラスへの画素領域の割り当てによるものであり得、伝播は境界表示によって制約される。
【００１２】
セグメント表示及び／又は境界表示はユーザ定義であり得、ユーザ入力から受信され得る。セグメント表示は具体的にはユーザ入力スクリブルであり得、境界表示はユーザ入力輪郭であり得る。各画素領域は単一画素を有し得るか、又は一部若しくは全ての画素領域が複数の画素を有し得る。セグメントクラスはそれに割り当てられるセグメントを持たないか、１つ又はそれ以上持ち得る。一部の実施形態において、セグメントクラスはそれに割り当てられるセグメントを１つしか持たないかもしれず、従ってセグメント及びセグメントクラスは同等であり得る。
【００１３】
本発明の任意の特徴によれば、セグメント化は、少なくとも第１のセグメント表示によって特定される各画素領域にセグメントクラスリンク値を割り当てるステップであって、セグメントクラスリンク値は画素領域と第１のセグメント表示の割り当てられたセグメントクラスとのリンクを示す、ステップと、セグメントクラスリンク値を画像中の未割り当て画素領域へ伝播させるステップと、セグメントクラスリンク値の伝播を境界表示において減衰させるステップとを有する。
【００１４】
これは改良されたセグメンテーションを提供し、及び／又は操作を容易にし、及び／又は複雑性を減少させ得る。特に、セグメント表示によって示されるセグメントは、適切な画像領域をカバーするために自動的に拡大され得、同時にこの拡大は境界表示によって制約され、その結果改良された画像セグメントエッジ決定をもたらす。該アプローチは、セグメント表示に基づく伝播を管理するために選択的セグメント境界情報が提供されることを可能にし得、それによって、重要なセグメント化が困難な領域における改良されたセグメンテーションを保証する。
【００１５】
該アプローチはセグメント表示と境界表示によって提供される情報の使用の特に有利な組み合わせを提供し得る。特にこれは、複雑性とリソース要件が低い単一アルゴリズムへの表示の効率的統合を提供し得る。該アプローチはさらにセグメンテーションを実行するときにセグメント表示と境界表示からの情報の適切なバランスを提供し得る。
【００１６】
境界表示におけるセグメントクラスリンク値の伝播の減衰は、具体的には境界表示を越えるセグメントクラスリンク値の伝播をブロックし得る。
【００１７】
本発明の任意の特徴によれば、セグメントクラス値の伝播はさらに画素領域に対する視覚的特性の類似性に依存する。
【００１８】
これは改良されたセグメンテーションを提供し、及び／又は操作を容易にし、及び／又は複雑性を減少させ得る。特に、これはセグメント表示と境界表示の使用とよく結びつき得る。
【００１９】
本発明の任意の特徴によれば、セグメント化は、複数のセグメントクラスのうちの第１のセグメントクラスに対する第１のセグメントクラスリンク値を、第１のセグメントクラスと関連する少なくとも１つのセグメント表示によって特定される画素領域に割り当てるステップであって、各セグメントクラスリンク値は画素領域と第１のセグメントクラスとの間のリンク強度表示を与える、ステップと、画素領域のグループに対する第１のセグメントクラスに対するセグメントクラスリンク値を決定するステップと、画素領域のグループのうちの少なくとも一部の画素領域に対し、画素領域に対する第１のセグメントクラスに対するセグメントクラスリンク値に応じて複数のセグメントクラスのうちの１つのセグメントクラスを選択するステップとを有し、セグメントクラスリンク値を決定するステップは、画素領域のグループのうちの各画素領域に対するセグメントクラスリンク値を、画素領域の近傍集合のセグメントクラスリンク値の組み合わせとして決定するステップを有し、組み合わせは、境界表示によって各画素領域から分離される画素領域の近傍集合のうちのいずれかに依存する。
【００２０】
これは改良されたセグメンテーションを提供し、及び／又は操作を容易にし、及び／又は複雑性を減少させ得る。特に、セグメント表示によって示されるセグメントは、適切な画像領域をカバーするために自動的に拡大され得、同時にこの拡大は境界表示によって制約され、その結果改良された画像セグメントエッジ決定をもたらす。該アプローチは、セグメント表示に基づく伝播を管理するために選択的セグメント境界情報が提供されることを可能にし得、それによって、重要なセグメント化が困難な領域における改良されたセグメンテーションを保証する。
【００２１】
該アプローチはセグメント表示と境界表示によって提供される情報の使用の特に有利な組み合わせを提供し得る。特にこれは、複雑性とリソース要件が低い単一アルゴリズムへの表示の効率的統合を提供し得る。該アプローチはさらにセグメンテーションを実行するときにセグメント表示と境界表示からの情報の適切なバランスを提供し得る。
【００２２】
画素領域の近傍集合を用いる伝播は、高品質セグメンテーションを維持しながら、低複雑性、低リソース使用を提供し得る。
【００２３】
画素領域とセグメントクラスに対するセグメントクラスリンク値は、その画素領域がそのセグメントクラスに属する尤度を示し得る。画素領域のグループは画像内の全画素領域を含み得るか、又はその部分集合であり得る。
【００２４】
画素領域のグループは具体的にはセグメント表示に基づくセグメントクラスリンク値を割り当てられる画素領域を除外し得る。画素領域のグループは具体的には画素領域の未割り当て集合に対応し得、画素領域の未割り当て集合はセグメント表示に応じてセグメントクラスリンク値を割り当てられていない画素領域に対応する。画素領域の近傍集合は具体的には、組み合わせが実行される画素領域に対する距離、方向及び／又は位置基準を満たす画素領域の集合であり得る。
【００２５】
本発明の任意の特徴によれば、割り当てるステップは、第１のセグメントクラスリンク値を割り当てられていない少なくともいくつかの画素領域に初期セグメントクラスリンク値を割り当てるステップをさらに有し、初期セグメントクラスリンク値は第１のセグメントクラスリンク値よりも弱い第１のセグメントクラスへのリンクを示す。
【００２６】
これはセグメンテーションを改良し及び／又は容易にし得る。該方法は例えば最初に、セグメントクラスに対するセグメント表示によって特定される画素領域と関連するセグメントクラスリンク値に最大リンク値を割り当て、セグメント表示によって特定されない画素領域と関連するクラスリンク値に最小リンク値を割り当て得る。例えば、画素領域が第１のセグメントクラスに属する確率１に対応するセグメントクラスリンク値が、第１のセグメント表示によって特定される画素領域に割り当てられ得、全ての他の画素領域には確率ゼロが割り当てられる。
【００２７】
本発明の任意の特徴によれば、組み合わせは、画素領域の近傍集合のうちの分離画素領域に対するセグメントクラスリンク値の重み付けが減少するようになっており、分離画素領域は境界表示によって各画素領域から分離される画素領域である。
【００２８】
これはセグメンテーションを改良し及び／又は容易にし得る。
【００２９】
本発明の任意の特徴によれば、分離画素領域の重み付けはゼロである。
【００３０】
これはセグメンテーションを改良し及び／又は容易にし得る。特に、これは伝播をブロックし、それによって強いセグメンテーションエッジを反映し得る。
【００３１】
本発明の任意の特徴によれば、組み合わせは、画素領域の近傍集合のうちの近傍画素領域に対するセグメントクラスリンク値の重み付けが、近傍画素領域の視覚的特性及び各画素領域の視覚的特性に対する類似性測定に依存するようになっている。
【００３２】
これは改良されたセグメンテーションを提供し、及び／又は操作を容易にし、及び／又は複雑性を減少させ得る。特に、これはセグメント表示と境界表示の使用とよく結びつき得る。
【００３３】
本発明の任意の特徴によれば、画素領域の集合のうちの各画素領域に対するセグメントクラスリンク値を決定するステップは、画素領域のグループのうちの各画素領域に対してセグメントクラスを選択するステップの前に繰り返される。
【００３４】
これは改良されたセグメンテーションを提供し、及び／又は操作を容易にし、及び／又は複雑性を減少させ得る。
【００３５】
本発明の任意の特徴によれば、該方法は、複数のセグメントクラスのうちの第２のセグメントクラスに対する第２のセグメントクラスリンク値を、第２のセグメントクラスと関連する少なくとも１つのセグメント表示によって特定される画素領域に割り当てるステップであって、各セグメントクラスリンク値は画素領域と第２のセグメントクラスとの間のリンク強度表示を与える、ステップと、第２のセグメントクラスに対する画素領域のグループに対するセグメントクラスリンク値を決定するステップとをさらに有し、画素領域のグループのうちの各画素領域に対してセグメントクラスを選択するステップは、第１のセグメントクラスに対する第１の画素領域に対するセグメントクラスリンク値と、第２のセグメントクラスに対する第１の画素領域に対するセグメントクラスリンク値との比較に応じて、第１の画素領域に対するセグメントクラスを選択するステップを有する。
【００３６】
これは改良されたセグメンテーションを提供し、及び／又は操作を容易にし、及び／又は複雑性を減少させ得る。特に、これはどのセグメントクラスに個々の画素領域が属するかの改良された選択を可能にし得る。該アプローチは例えば全セグメントクラスに拡張され得る。画素領域に対するセグメントクラスの選択は具体的にはセグメントクラスへの画素領域の最強リンクを示すセグメントクラスリンク値を持つセグメントクラスの選択に対応し得る。
【００３７】
本発明の任意の特徴によれば、該方法はさらに、画像のセグメンテーションをユーザへ提示するステップ、画像に対する新たなセグメント表示と新たな境界表示のうちの少なくとも１つのユーザ入力を受信するステップ、及び新たなセグメンテーション表示と新たな境界表示のうちの少なくとも１つに応じてセグメンテーションを更新するステップをさらに有する。
【００３８】
本発明は改良された反復ユーザインタラクティブセグメンテーションプロセスを提供し得る。該方法は特にセグメンテーション結果をユーザへ提示し得、これはセグメンテーションのための重要領域をユーザが特定することを可能にする。そしてこうした領域のセグメンテーションはユーザがさらなる境界情報を与えることによって改良され得、更新され改良されたセグメンテーションをもたらす。例えば、半自動の伝播に基づくセグメンテーションは追加ユーザ入力によって繰り返し改良され得る。
【００３９】
本発明の任意の特徴によれば、該方法はいかなる境界表示又はセグメント表示にも基づかない初期セグメンテーションによって画素領域を生成するステップをさらに有する。
【００４０】
これは改良されたセグメンテーションを提供し、及び／又は操作を容易にし、及び／又は複雑性を減少させ得る。特に、これは個々の画素に基づく処理が必要ないので削減された計算リソースを可能にし得る。初期セグメンテーションは通常、予想セグメントサイズよりもかなり小さいセグメントを生成し得る。
【００４１】
本発明の任意の特徴によれば、セグメンテーションは奥行きマップセグメンテーションである。
【００４２】
本発明は、例えば三次元画像データの生成に適した改良された奥行きマップセグメンテーションを提供し得る。奥行きマップは奥行き表示、視差表示、又は画像オブジェクト若しくは領域に対する絶対的若しくは相対的奥行きを示す任意の他の特性を有し得る。
【００４３】
本発明の任意の特徴によれば、上記方法を実行するためのコンピュータプログラムが提供される。
【００４４】
本発明の一態様によれば、画像をセグメント化するための装置が提供され、該装置は、画像に対する複数のセグメント表示を受信するための手段であって、各セグメント表示は画素領域の集合、及び画素領域の集合と複数のセグメントクラスのうちの関連セグメントクラスとの間の関係を示す、手段と、画像に対する複数の境界表示を受信するための手段であって、各境界表示は複数のセグメントクラスのうちの異なるセグメントクラスに属する画素間の境界を示す、手段と、複数のセグメント表示と複数の境界表示の両方に応じて複数のセグメントクラスに画像をセグメント化するための手段とを有する。
【００４５】
本発明のこれらの及び他の態様、特徴及び利点は、以下に記載される実施形態から明らかとなり、それらを参照して解明される。
【００４６】
本発明の実施形態はほんの一例として図面を参照して説明される。
【図面の簡単な説明】
【００４７】
【図１】スクリブルを持つ画像の一例が図示される。
【図２】ユーザ定義輪郭を持つ画像の一例が図示される。
【図３】本発明の一部の実施形態にかかる画像をセグメント化するための装置の一実施例を図示する。
【図４】２つの画像オブジェクトを有する画像のセクションの一実施例を図示する。
【図５】本発明の一部の実施形態にかかるインタラクティブ画像セグメンテーションの方法の一実施例を図示する。
【図６】本発明の一部の実施形態にかかるインタラクティブ画像セグメンテーションのための特徴を伝播する方法の一実施例を図示する。
【発明を実施するための形態】
【００４８】
以下は異なる画像オブジェクト若しくは領域に対する異なる奥行きレベル（及び具体的には前景と背景の奥行き）を示す奥行きマップを生成するために画像のセグメンテーションに適用可能な本発明の一実施形態に焦点を合わせる。しかしながら、本発明はこの応用に限定されず、画像セグメンテーションの多くの他の種類及び目的に適用され得ることが理解される。
【００４９】
図３は本発明の一部の実施形態にかかる画像をセグメント化するための装置の一実施例を図示する。
【００５０】
該装置はユーザからの入力を受信することができるユーザ入力３０１と、セグメント化される画像を表示することができるディスプレイ３０３を有する。特定の実施例において、ディスプレイはユーザ入力３０１が表示装置のタッチセンサ部に対応するタッチセンサディスプレイである。他の実施形態において、例えばマウス、タッチパッド又はグラフィックタブレットを含む他の種類のユーザ入力が使用され得ることが理解される。ユーザ入力はセグメントプロセッサ３０５と境界プロセッサ３０７に結合され、これらは共にセグメンテーションプロセッサ３０９に結合され、これはさらにディスプレイ３０３に結合される。
【００５１】
セグメンテーションプロセッサ３０９は、セグメント化されるべき画像をセグメンテーションプロセッサ３０９に供給する画像ソース３１１にさらに結合される。具体的実施例において画像はビデオシーケンスの画像であり、具体的にはビデオ信号のフレームであり得る。しかしながら、他の実施例においてデジタル写真などの単一画像がセグメント化され得ることが理解される。
【００５２】
セグメンテーションプロセッサ３０９はセグメント化されるべき画像をディスプレイ３０３上に提示し得、ユーザはセグメンテーションを支援するためにユーザ入力を供給し得る。具体的には、ユーザは同じセグメントの範囲に入る（又は代わりに外側にある）とみなされる特定画素を示すデータ、並びに異なるセグメント間の境界又はエッジを示す情報を入力し得る。
【００５３】
オペレータは特定セグメントクラスに属すべき画素の集合を示すセグメント表示を入力し得る。具体的には、画像のセグメンテーションは画像を異なるセグメントに分割し、各セグメントは特定セグメントクラスに属し、全て同じセグメントクラスに属する画素の集合はセグメント表示によって特定され得る。
【００５４】
以下の説明は、画像のセグメンテーションが複数のセグメントへなされ、各セグメントは２つのセグメントクラスのうちの１つに属することができる一実施例に焦点を合わせる。該実施例においてバイナリ奥行きセグメンテーションが実行され、１つのセグメントクラスは画像の背景に対応し、別のセグメントクラスは画像の前景に対応する。従って、画像のセグメンテーションは単純に前景画像オブジェクトと背景画像領域へとなされる。しかしながら、他の実施形態において、セグメンテーションは２つよりも多くのセグメントクラスへなされてもよく、セグメンテーションは他の目的を意図する、及び他の特性を考慮するセグメンテーションであってもよいことが理解される。例えば、該アプローチは（例えば動き推定のために）個別の画像オブジェクトを特定するために使用されてもよく、個別のセグメントクラスは各画像オブジェクトと関連する。
【００５５】
ユーザによって与えられるセグメント表示は同じセグメントクラスに属するとみなされる画素の集合を示す。例えば、ユーザは前景セグメントに含まれるべき前景画素の集合を示し得る。同様に、ユーザは背景セグメントに含まれるべき背景画素の集合を示し得る。
【００５６】
具体的実施例として、ユーザは例えば前景セグメントクラスなどのセグメントクラスを最初に選択し得る。その後、ユーザはそのセグメントクラスに属すべきいくつかの画素を手動で示し得る、すなわちいくつかの前景画素を示し得る。この表示は図３のシステムにおいてユーザが直接スタイラスをタッチセンサディスプレイに適用し、例えば前景画素を示す直線又は曲線を描くことによってもたらされる。
【００５７】
ユーザは同じセグメント（若しくはセグメントクラス）又は異なるセグメントクラスに対する各セグメント表示を含む複数のセグメント表示を入力し得る。
【００５８】
一部の実施形態において、セグメント表示は代替的に又は付加的に所与のセグメントクラスに属すべきではない画素の集合を定義し得る。例えば、ユーザは前景セグメントクラスを選択し、そして選択された画素が選択されたセグメントクラスの一部ではないことを反映するオプションを選択し得る。従って、ユーザは代替的に又は付加的に画素が前景画素ではないことを特定するセグメント表示を入力し得る。このような表示は別のセグメントクラスに属する画素の表示に対応し得る（例えば前景と背景のみへのセグメンテーションの場合、ネガティブ前景表示はポジティブ背景表示に対応する）が、必ずしもそうとは限らない。例えば、背景、中景、及び前景セグメントクラスへのセグメンテーションの場合、セグメンテーション表示は前景画素ではない画素を示し得るが、それらが背景又は中景画素であるかどうかは特定しない。
【００５９】
ユーザがセグメント表示を入力するとき、ユーザ入力はセグメントプロセッサ３０５に与えられ、これは次に、選択されたセグメントクラスに対する選択された画素位置の集合を定義するデータを生成する。そしてこのデータは画像をセグメント化するときに使用されるためにセグメンテーションプロセッサ３０９へ転送される。
【００６０】
システムのオペレータは異なるセグメントクラスに属する画素間の境界を示す境界表示も入力することができる。従って、ユーザは異なるセグメントクラスに属する異なるセグメントに属する画像オブジェクト間のエッジを定義し得る。具体的には、オペレータは前景画像オブジェクトと背景画像領域の間の境界を定義し得る。
【００６１】
具体的実施例として、ユーザは境界表示を入力するオプションを最初に選択し得る。その後ユーザは２つのセグメント（及びセグメントクラス）を分離するいくつかの位置を手動で示し得る。この表示は図３のシステムにおいて、ユーザが直接スタイラスをタッチセンサディスプレイに適用し、例えば２つのセグメント間の境界を示す直線又は曲線を描くことによって与えられる。
【００６２】
ユーザは複数の境界表示を入力し得る。さらに、境界表示はゼロ幅を持ってもよく（すなわちこれは画素間にあると決定され得る）、又は１つ以上の画素の幅を持ってもよい（従っていくつかの画素が境界画素になる）。以下の説明は画素間にある境界表示（すなわち境界画素がない実施例）に焦点を合わせる。
【００６３】
図３の装置において、ユーザが境界表示を入力すると、ユーザ入力は境界プロセッサ３０７へ与えられ、これは次にその境界に対する選択された画素間位置の集合を定義するデータを生成する。そしてこのデータは画像をセグメント化するときに使用されるためにセグメンテーションプロセッサ３０９へ転送される。
【００６４】
ユーザは、具体的には特定セグメントクラスに属する位置の集合を特定する直線又は曲線を画像上に描くことによってセグメント表示を提供し得ることが理解される。これはしばしば"スクリブル"と呼ばれる。しかしながら、セグメントクラスに属する個別領域を示す（例えばセグメント又はセグメントクラスに含まれるべき様々な領域を"スタンプすること"に対応する）、例えばブラシツールを用いることを含む他のユーザ入力が使用され得ることもまた理解される。
【００６５】
同様に、ユーザは具体的には異なるセグメントクラスに属する２つのセグメントを分離する位置の集合を特定する直線又は曲線を画像上に描くことによって境界表示を提供し得ることが理解される。これはしばしば"輪郭"と呼ばれる。しかしながら、他のユーザ入力が使用され得ることもまた理解される。
【００６６】
具体的実施例として、図３のシステムは次の２つのユーザ入力モードで動作し得る。
【００６７】
スクリブルモード：このモードにおいて、ユーザは任意オブジェクトの内部にスクリブルを置くことができる。スクリブルは特定セグメントクラスにリンクされる。スクリブルはオブジェクト境界を越えてはならない。
【００６８】
輪郭モード：このモードにおいて、ユーザは２つのオブジェクト間の移行部上に輪郭を置くことができる。具体的には、移行部上の複数の点が選択され得、それらが組み合わされて曲線を形成し得る。
【００６９】
図４は２つの画像オブジェクトＡ及びＢを有する画像のセクションの一実施例を示し、Ａは前景オブジェクトでＢは背景オブジェクトである。実施例において、ユーザは背景スクリブル４０１、前景スクリブル４０３、及び２つの画像オブジェクトに対応するセグメント間の境界を定義する輪郭４０５を入力している。
【００７０】
セグメンテーションプロセッサ３０９は次に、与えられたセグメント表示と境界表示を用いて画像をセグメント化する。システムにおいて、セグメンテーションはセグメント表示と境界表示の両方によって同時に制約される。従って、画像の自動セグメンテーションはセグメンテーション中のユーザ入力なしで（ただし前に与えられたユーザ入力を用いて）実行される。しかしながら自動セグメンテーションは与えられたセグメント表示と境界表示によって制約され、基本的に、セグメント表示の全画素が関連セグメントクラスに属するように、かつセグメントクラス間の境界が境界表示によって示されるところに存在するように、実行される。セグメンテーションプロセッサ３０９による自動セグメンテーションは、具体的には画像の視覚的特性に基づき得る（例えば色の変化に基づく）。
【００７１】
図３の実施例において、反復操作が実施される。従って自動セグメンテーションの結果はセグメンテーションプロセッサ３０９によってディスプレイ上に（例えばディスプレイ画像にセグメントエッジを示す線を重ね合わせることによって）提示される。そしてユーザは、例えばユーザが目的の操作を選択すること、及びタッチセンサディスプレイ上に直接描くことによって、１つ以上のセグメンテーション表示及び／又は境界表示のさらなる入力を与え得る。新たなセグメント表示又は境界表示の入力後（又は例えばユーザが特にそれを要求するとき）、セグメンテーションが更新され、新たなセグメンテーションがディスプレイ上に提示され得る。従って、セグメンテーション結果から、ユーザはセグメンテーションが失敗する（例えばオブジェクト間に明確な色遷移がないためにセグメンテーション表示のみに基づくセグメンテーションが失敗する）重要領域を決定することができる。そしてユーザはこうした重要領域に手動ユーザ入力を集めることができ、具体的には境界表示を入力するために輪郭モードへ切り替え、それによってセグメント間のエッジを手動で定義することができる。
【００７２】
この反復は、オペレータが結果に満足し、画像に対するセグメンテーション操作が終了したことを示すまで繰り返され得る。反復アプローチは改良されたインタラクティブセグメンテーションを提供し得、例えばユーザが必要な数の入力のみにインタラクションを制限することを可能にし得る。最初に表示されるセグメンテーション結果はいかなるセグメント表示又は境界表示も考慮しない完全自動セグメンテーションの結果であり得る。
【００７３】
図３の実施例において、セグメンテーションプロセッサ３０９によって実行されるセグメンテーションは伝播アルゴリズムに基づき、どのセグメントクラスに画素が属する可能性が高いかを示す値が、隣接画素間の伝播によって画像内に広められる。伝播は具体的にはセグメント表示から生じ、セグメント表示の画素から隣接画素へ、これらの隣接画素からその隣接画素へ、といったように広がる／伝播し得る。実施例において伝播は画素の視覚的特性に応じ、伝播は同様の視覚的特性を持つ画素間では強く、非常に異なる視覚的特性を持つ画素間では弱いようになっている。さらに、該アプローチにおいて、値の伝播は境界表示によって示される境界においてブロック（又は減衰）される。
【００７４】
より詳細には、アルゴリズムは画素領域とセグメントクラスとの間のリンクを示すセグメントクラスリンク値に基づき得る。実施例において、各画素は考えられるセグメントクラスの各々に対するセグメントクラスリンク値を持つ、すなわち、具体的実施例において各画素は背景セグメントクラスリンク値と前景セグメントクラスリンク値を持つ。さらに、実施例において、セグメントクラスリンク値は画素がそのセグメントクラスに割り当てられるべき確率を示し、従って各セグメントクラスリンク値は区間［０，１］に属し、０は画素が確実にセグメントクラスに属していないことを示し、１は画素が確実にセグメントクラスに属していることを示す。
【００７５】
最初に、所与のセグメントクラスに対するセグメントクラス値が全画素に割り当てられる。割り当ては、セグメントクラスに対する（ポジティブ）セグメント表示に含まれる任意の画素が所定値（画素がセグメントクラスに属する確率が高いことを示す。典型的には１の値が割り当てられる）を与えられるようになっている。第２の所定値は全ての他の画素に与えられ、第２の所定値は画素がセグメントクラスに属する確率が低いことを示す。例えば０の値が割り当てられる。
【００７６】
そしてセグメンテーションプロセッサ３０９は次に、隣接画素、及び画素と隣接画素との間の視覚的類似性に基づいて画素に対するセグメントクラス値を決定する。このプロセスは何回も（例えば５０回以上）繰り返され、セグメント表示が修正されない（すなわちこれらが１の値を維持する）ことによって特定される画素に対するセグメントクラスリンク値によって制約される。
【００７７】
従って、所与のセグメントクラスに対するセグメント表示に隣接する画素に対して、第１の反復は初期値０を画素間の視覚的差に依存する値へ増加させる。同じような色の画素に対しては、値は１（付近）に変更され得、それによってこれらの画素がセグメンテーション表示によって示される画素と同じセグメントに属する可能性が高いことを示す。その後の反復において、隣接画素の隣接画素はセグメントクラスリンク値を増加させ、従ってセグメントクラス値はセグメント表示から画像内で伝播する。さらに、伝播は視覚的類似性に依存し、はっきりした移行部（例えばはっきりした色遷移）が検出されるとき、移行部がセグメントエッジを示す可能性が高いことを反映するために伝播がブロックされるか又は大幅に減衰されるようになっている。
【００７８】
さらに、視覚的特性への依存に加えて、伝播は境界表示に依存する。具体的には、境界表示が２つの隣接画素間に境界が存在することを示すときはいつでも、これらの間のセグメントクラスリンク値の伝播は大幅に減衰されるか、又は完全にブロックされる。従って伝播は、境界表示によって示される境界を越えるいかなる伝播も大幅に軽減されるか、又は具体的には完全にブロックされ得るようになっている。
【００７９】
境界表示とセグメンテーション表示の複合同時使用は、自動セグメンテーションが低い複雑性と便利なユーザ操作によって所望の結果へ制御されバイアスされることを可能にするため、かなり改良されたセグメンテーションを可能にする。
【００８０】
セグメンテーションプロセッサ３０９は一部の実施形態において上記アルゴリズムを単一のセグメントクラスのみに適用し得る。例えば、伝播は前景セグメントクラスに対してのみ実行され得る。伝播に基づいて、その後各画素は画素に対して得られるセグメントクラスリンク値に基づいて１つのセグメントクラスに割り当てられ得る。例えば、０．５を上回るセグメントクラス値を持つ全画素は前景セグメントクラスに対応するラベルを割り当てられ得、他の全ての画素は背景セグメントクラスに対応するラベルを割り当てられ得る。
【００８１】
図３の具体的実施例において、セグメンテーションプロセッサ３０９は次にセグメントクラスの各々に伝播アルゴリズムを独立して適用する（すなわちこれを前景及び背景セグメントクラスの両方に独立して適用する）。そして個別画素の各々はその後最高セグメントクラス値を持つセグメントクラスに割り当てられる。
【００８２】
以下では、図３のシステムのセグメンテーション操作の具体的実施例が、本発明の一部の実施形態にかかるインタラクティブ画像セグメンテーションの方法の一実施例を図示する図５を参照して説明される。
【００８３】
該システムにおいて、画像は最初に複数の画素領域に分割され、その各々は１つ以上の画素を有し得る。従って、前記実施例における画素への言及は１つよりも多くの画素を有する可能性がある画素領域に等しく当てはまることが理解される。複数の画素を持つ画素領域の使用は特に記載のセグメンテーションにとって複雑性と計算負荷を減少させ得る。
【００８４】
こうして、図５の方法はステップ５０１においてセグメンテーションプロセッサ３０９が初期画像を受信し、適切な数の画素領域を生成するようオーバーセグメンテーションを実行することによって開始する（すなわちセグメンテーションは、各々が１つ以上の画素を有し得るが、インタラクティブ画像セグメンテーションから得られるセグメントよりもかなり小さい可能性が高い画素領域へとなされる）。実施例において、該システムはさらに受信画像をディスプレイ３０３上に表示する。
【００８５】
具体的には、画像は最初に多くの小領域へオーバーセグメント化される。オーバーセグメンテーションを生じることができる多くの異なる方法が知られており、こうした任意の適切な方法がセグメンテーションプロセッサ３０９によって使用され得ることが理解される。
【００８６】
初期オーバーセグメンテーションは、画像の色、画像テクスチャ又は画像の動きなど、任意の画像又はビデオ特性に基づき得る。
【００８７】
従って、画素領域への初期セグメンテーションはいかなるユーザ入力もなく、具体的にはいかなるセグメント表示又は境界表示も考慮せずに実行される。
【００８８】
随意に、図３のシステムは画素領域を生成するためのオーバーセグメンテーション後、次にユーザ入力なしの初期セグメンテーション提案を提供するために画像をセグメント化し得る。このセグメンテーションの結果はオーバレイとして画像の上にプロットされ得、それによってユーザが例えばそれ以上のインタラクティブセグメンテーションをスキップすることを可能にし（結果が既に許容可能である場合）、又は自動セグメンテーションにとってとりわけ困難な領域をハイライトし得る。
【００８９】
ステップ５０１に続いて、ユーザ入力に基づく反復インタラクティブセグメンテーションが初期化される。セグメンテーションは伝播アプローチを使用し、各画素領域は考えられる各セグメントクラスに対するセグメントクラスリンク値を与えられる。セグメンテーションの目的は各画素領域にセグメントラベル（セグメントクラスに対応する）を割り当てることである。具体的実施例において、従って各画素領域は前景又は背景のいずれかを割り当てられる。画素領域及びセグメントクラスに対するセグメントクラスリンク値は画素領域がそのセグメントクラスに割り当てられるべき確率を示す。
【００９０】
ステップ５０１の後ステップ５０３が続き、ユーザからセグメント表示が全く受信されないか、１つ又はそれ以上のセグメント表示が受信され、各セグメント表示はセグメントクラスにリンクされる。前述の通り、セグメント表示はユーザが直接タッチセンサディスプレイ３０１，３０３上に描くことによって生成されるスクリブルであり得る。
【００９１】
ステップ５０３の後ステップ５０５が続き、ユーザから境界表示が全く受信されないか、１つ又はそれ以上の境界表示が受信される。前述の通り、セグメント表示はユーザが直接タッチセンサディスプレイ３０１，３０３上に描くことによって生成される輪郭であり得る。
【００９２】
セグメンテーションの各反復において、１つもないか１つ又はそれ以上のセグメント表示、及び１つもないか１つ又はそれ以上の境界表示が受信され得るが、通常は少なくとも１つのセグメント表示又は境界表示が各反復において受信されることが理解される。
【００９３】
ステップ５０５に続いて、セグメンテーションプロセッサ３０９は伝播に基づくセグメンテーションを開始し、セグメント表示に基づいて割り当てられるセグメントクラスリンク値が、対応するセグメント表示によって特定されない画素領域へ伝播される。さらに、伝播は境界表示、及び実施例においては画素領域間の視覚的特性の類似性にも依存する。伝播は個々のセグメントクラスに対して別々に実行される。
【００９４】
このようにして、ステップ５０５の後ステップ５０７が続き、セグメントクラスリンク値の伝播が１つのセグメントクラスに対して実行される。ステップ５０７の後ステップ５０９が続き、全セグメントクラスが伝播されたかどうかが決定される。そうであれば、方法はステップ５１１に続き、そうでなければステップ５０７へ戻って次のセグメントクラスに対する伝播プロセスを実行する。一部の実施例では単一のセグメントクラスのみがセグメント選択のために使用され、従って場合によっては単一の反復のみが実行され得ることが理解される。
【００９５】
伝播アプローチの一実施例は図６を参照して説明される。
【００９６】
所与のセグメントクラスに対する（例えば背景セグメントクラス又は前景セグメントクラスに対する）伝播はステップ６０１で開始し、セグメントクラスに対するセグメントクラスリンク値は、セグメントクラスに属するようにユーザによって供給される１つ以上のセグメント表示によって特定される画素領域に割り当てられる。
【００９７】
具体的には、セグメントクラスに対するセグメント表示によって特定される各画素領域に対するセグメントクラスリンク値は、画素領域とセグメントクラスとの間の強いリンクを示す、すなわち画素領域がこのセグメントクラスに属する可能性が高いことを示す、所定値を割り当てられる。
【００９８】
具体的には、スクリブルは、スクリブルと交差する全画素領域が、画素領域が対応するセグメントクラスに属するという高い信頼度を示すセグメントクラスリンク値を与えられるという効果を持つ。例えば、ｍがセグメント表示に対するセグメントクラスを示す場合、セグメント表示によって特定される全領域ｊ∈ｉ（ｉは全画素領域の集合である）は、画素領域をそのセグメントクラスに明確に割り当てる値を割り当てられる。例えば画素領域がセグメントクラスに属する確率を示すセグメントクラスリンク値は画素領域がセグメントクラスに属する確実性を示すように設定される。
0005508435.tif 000002
【００９９】
同様に、ネガティブセグメント表示（すなわち特定セグメントクラスに属さない画素領域を示すセグメント表示）に対して、弱いリンク（又はリンクなし）を示す所定値がセグメントクラスリンク値に割り当てられる。例えば画素領域ｋがセグメントクラスに属する確率を示すセグメントクラスリンク値に対して、セグメントクラスリンク値は画素領域がセグメントクラスに属さない確実性を示すように設定される。
0005508435.tif 000003
【０１００】
セグメント表示は同時にネガティブ及びポジティブセグメント表示であることができることが理解される。例えば、前景及び背景にセグメント化する実施例において、背景スクリブルは背景セグメントクラスに対するポジティブセグメント表示と、前景セグメントクラスに対するネガティブセグメント表示の両方を与える。
【０１０１】
このようにして、ステップ６０１の後、複数のセグメントクラスリンク値がいくつかの画素領域に割り当てられている。こられの画素領域は割り当て集合と呼ばれる。さらに、複数の画素領域はいかなる（固定）セグメントクラスリンク値も割り当てられていない（これらはセグメント表示の一部ではないため）。これらの画素領域は未割り当て集合と呼ばれる。
【０１０２】
一部の実施形態において、初期セグメントクラスリンク値は未割り当て集合の画素領域にも割り当てられ得る。例えば、ポジティブセグメント表示に対して使用される値よりもかなり弱いセグメントクラスへのリンクを示す初期値が割り当てられ得る。具体的には、初期セグメントクラスリンク値は全ての未割り当て画素領域に対して０に設定され得る（又は例えば特定セグメントクラスが画素領域において存在するという事前の確信があることを示す０．５に設定され得る）。
【０１０３】
そして方法は次に、具体的には未割り当て集合に対応する画素領域のグループに対するセグメントクラスリンク値を決定する。
【０１０４】
伝播反復はステップ６０３で開始し、未割り当て集合における次の画素領域が選択される。異なる実施形態において、画素領域が更新される異なる順番が使用され得ることが理解される。例えば、一部のシナリオにおいて、画素領域は上から下へ、及び左から右へ処理され得、他の場合において順番は下から上及び右から左であり得、他の場合においてこれはセグメント表示までの距離が増加する順番であり得、他の場合においてこれは例えばランダムであり得る。
【０１０５】
そして方法はステップ６０５に続き、画素領域の近傍集合が現在の画素領域に対して決定される。一部の実施形態において、近傍集合は単に現在の画素に隣接する全画素領域を含み得るが、他の実施形態においては他の集合が使用され得ることが理解される。例えば、一部の実施形態において、近傍集合は非対称で、一方向において他の方向よりも多数の画素領域を含み得る。例えば、既に処理されている方向の画素領域のみが含まれ得る。さらに、一部の実施形態においては、現在の画素領域の近傍における選択画素領域の特定パターン、例えば最大で例えば３画素領域の距離に１つおきの画素領域が選択され得る。
【０１０６】
従って、近傍集合は現在の画素領域に相対的な位置において複数の画素領域を定義する相対位置基準に応じて選択され得る。位置基準は例えば現在の画素に対する近傍集合に含まれるべき画素領域に対する距離及び方向特性を規定し得る。
【０１０７】
ステップ６０５の後ステップ６０７が続き、近傍集合が評価され、その画素領域のいずれかが境界表示によって現在の画素領域から分離されるかどうかを決定する。例えば、垂直輪郭が現在の画素領域のすぐ右隣りにユーザによって置かれている場合、近傍集合の全画素領域は輪郭／境界表示によって現在の画素領域から分離され、従ってこれらの画素領域は分離画素領域として指定される。
【０１０８】
ステップ６０７の後ステップ６０９が続き、現在の画素領域に対するセグメントクラスリンク値が、画素領域の近傍集合のセグメントクラスリンク値の組み合わせとして計算される。さらに、組み合わせは、近傍集合が分離領域を有するかどうかに依存するような組み合わせである。具体的には、任意の分離画素領域からの寄与は、境界表示によって分離されていない場合のその画素領域からの対応する寄与と比べて減少する。
【０１０９】
具体的には、組み合わせは、近傍集合の各画素領域のセグメントクラスリンク値からの寄与が、近傍集合の他の画素領域に対して重み付けされるようになっている。重み付けは２つの画素領域の視覚的類似性に基づき、具体的には色類似性に基づく。このようにして、色が非常に似ている、従って同じセグメントに属する可能性が高い近傍画素領域には高い重み付けが与えられ、一方非常に異なる色を持つ近傍画素領域には低い重み付けが与えられ、その結果これらの画素領域が同じセグメントに属する可能性が低いことを反映することが可能である。
【０１１０】
さらに、近傍画素領域に対する重み付けは、これが境界表示によって分離されるかどうかに依存し、具体的には任意の分離画素領域の重み付けは、画素領域が境界表示によって分離されない場合と比べて減少する。この減少は具体的には、分離画素領域からのいかなる寄与も完全に無視される重みゼロに対応し得る。
【０１１１】
具体的実施例において、セグメントクラスｋに対する画素領域ｉに対するセグメントクラスリンク値は近傍画素領域ｊのセグメントクラスリンク値から計算される。領域ｉに対して、セグメントクラスリンク値は次式を用いて更新される。
0005508435.tif 000004
ｒ，ｇ，ｂはＲＧＢ色表現の赤、緑、青の色の値を示す。値αは所望の伝播特性をもたらすために選択され得る（多くのシナリオにおいておよそα＝０．１の標準値が適切であり得る）。従って近傍画素領域ｊに対する重みは、領域ｉ及びｊが同様の平均色値を持ち境界表示によって分離されない場合、高い。しかしながら、こうした寄与の重みがゼロに設定されるとき、セグメントクラス情報は境界領域を越えて伝播されない。
【０１１２】
このように、現在の画素領域が現在のセグメントクラスに属する可能性を示すセグメントクラスリンク値は近傍画素領域の重み付けされた寄与から決定される。
【０１１３】
一部の実施形態において現在の画素に対するセグメントクラスリンク値は現在の画素に対するセグメントクラスリンク値の前の値からの寄与をさらに含み得る。
【０１１４】
ステップ６０９の後にステップ６１１が続き、未割り当て集合の全画素領域が現在の反復において考慮されたかどうかが決定される。もしそうでなければ、方法はステップ６０３に戻り次の画素領域を処理する。
【０１１５】
全画素領域が処理されている場合、一部の実施形態において伝播は終了し得る。しかしながら、実施例において、伝播はステップ６０３‐６１１を繰り返すことによって達成され、従って方法はこの場合ステップ６１３に続き、十分な反復が実行されたかどうか評価される。もしそうでなければ、方法はステップ６１５において次の反復を初期化し、その後ステップ６０３に戻り次の反復を実行する。
【０１１６】
次の反復の初期化は具体的には画素領域が処理される順番を選択することを含み得る。例えば、改良された伝播はしばしば、異なる反復において画素領域の処理のために異なる順番を用いることによって実現され得る。
【０１１７】
伝播ステップの反復は改良された伝播をもたらし、伝播は通常、適切なセグメンテーションを厳密に反映する画素領域へのセグメントクラスリンク値の安定した割り当てへ向かって収束する。例えば１０‐１００の反復がしばしば適切であり得る。他の実施形態において、他の停止条件が使用され得ることが理解される。
【０１１８】
伝播反復が終了したとき、方法はステップ５０９に続き、伝播が他のセグメントクラスに対して繰り返されるべきかどうかが決定される。そうでなければ、方法はステップ５１１に続き、セグメントクラスが各画素領域に対して選択される。
【０１１９】
具体的実施例として、２つの考えられるセグメントクラス（例えば背景及び前景セグメントクラス）へのセグメンテーションのために１つのセグメントクラスに対してのみ伝播が実行された場合、画素領域に対するセグメントクラスは、伝播されたセグメントクラスリンク値が閾値（例えば０．５）を上回る場合は伝播されたセグメントクラスとして選択され得、そうでなければ相補的セグメントクラスとして選択され得る。
【０１２０】
（例えば異なるセグメントクラスに対して上記伝播を繰り返すことによって）セグメントクラスセグメントリンクが複数の異なるセグメントクラスに対して決定される実施形態において、画素領域に対するセグメントクラスの選択は、異なるセグメントクラス値に対するセグメントクラスリンク値を互いに比較することによって実行され得る。具体的には、セグメントクラスリンク値が最強リンク（例えば最高値）を示すセグメントクラスが選択され得る。
【０１２１】
従ってセグメントクラスの選択後、全画素領域がセグメントクラスを割り当てられている（すなわちこれらが属すると見なされるセグメントクラスでラベルされている）。このようにして、画像のセグメンテーションが完了し、結果として得られるセグメンテーションがステップ５１３においてディスプレイ３０３上に表示され得る。
【０１２２】
そして方法はステップ５１５に続き、ユーザはセグメンテーションが許容可能であるか、又はさらなる更新が実行されるべきかどうかを示す。もしそうなら、方法はステップ５０３に戻りさらなるセグメント表示及び／又は境界表示を受信し、それに応じて伝播及びセグメントクラス選択が更新され、さらに改良されたセグメンテーションをもたらし得る。そうでなければ方法はステップ５１７で終了する。
【０１２３】
前記実施例において、セグメンテーションは境界表示によって制約されるセグメント表示からのセグメントクラス情報の伝播に基づいていた。しかしながら他の実施形態において、境界表示によって示される境界を与えるようにこれを制約しながらセグメンテーション表示によって与えられる情報に基づく他のセグメンテーション手段が使用され得ることが理解される。例えば、上記伝播アプローチの代わりに、セグメンテーションは境界表示によって制約される、セグメンテーション表示に基づくグラフカットアルゴリズムを使用し得る。別の実施例として、処理は焼き鈍し法に基づき得る。
【０１２４】
前記説明において、境界表示は画素間にある、すなわち画素を特定するのではなく異なる画素素子に属する画素を分離するとみなされていた。しかしながら一部の実施形態において、境界表示は幅を持つとみなされ得、具体的にはセグメントの境界又はエッジの一部であるとみなされる１つ以上の画素（又は画素領域）を特定し得る。
【０１２５】
例えばユーザは、その後自動曲線生成アルゴリズムによってつなげられる画像上の複数の点を選択することによって境界表示を入力し得る。そしてこの曲線（例えば１画素又はそれ以上の幅を持ち得る）上にある画素は境界画素として指定される。
【０１２６】
さらに、境界表示はオーバーセグメンテーションを修正するために使用され得、具体的には画素領域を修正するために使用され得る。例えば、境界表示は画素領域を通過し、それによって画素領域を２つ（又はそれ以上）の異なる領域に分割し得る。この場合画素領域は、２つ（又はそれ以上）の分離領域、及び境界画素を有する画素領域に対応する３つ（又はそれ以上）の異なる（より小さな）画素領域に分けられ得る。
【０１２７】
境界画素領域は伝播において考慮され得、具体的には全境界画素領域に対するセグメントクラスリンク値は伝播中にゼロに設定され得る。さらに、近傍集合に含まれる要件を満たす全境界画素領域は単に組み合わせにおいて無視され得る。セグメントクラス選択に続いて、境界領域は適切なセグメントクラスを割り当てられ得る。例えば、一部の実施形態において全境界領域は所定セグメントクラスを割り当てられ得る（例えばこれらは全て前景セグメントクラスを割り当てられる）か、又は例えば境界領域でない最接近画素領域のセグメントクラスを割り当てられ得る。
【０１２８】
明確にするための上記説明は異なる機能ユニット及びプロセッサを参照して本発明の実施形態を説明していることが理解される。しかしながら、異なる機能ユニット又はプロセッサ間の機能の適切な分散が本発明を損なうことなく使用され得ることが理解される。例えば、個別のプロセッサ又はコントローラによって実行されるように図示された機能が同じプロセッサ又はコントローラによって実行され得る。従って、特定の機能ユニットへの言及は、厳密な論理的又は物理的構造又は組織を示すのではなく、記載の機能を提供するための適切な手段への言及とみなされるに過ぎないものとする。
【０１２９】
本発明は、ハードウェア、ソフトウェア、ファームウェア又はこれらの任意の組み合わせを含む任意の適切な形式で実施されることができる。本発明は随意に１つ以上のデータプロセッサ及び／又はデジタル信号プロセッサ上で動くコンピュータソフトウェアとして少なくとも部分的に実施され得る。本発明の一実施形態の素子及び部品は、物理的に、機能的に及び論理的に任意の適切な方法で実施され得る。実際に機能は、単一ユニット、複数のユニット、又は他の機能ユニットの一部として実施され得る。このように、本発明は単一ユニットにおいて実施されてもよく、又は異なるユニット及びプロセッサ間に物理的に及び機能的に分散されてもよい。
【０１３０】
本発明は一部の実施形態に関連して記載されているが、これは本明細書に記載の特定形態に限定されることを意図しない。むしろ、本発明の範囲は添付のクレームにしか限定されない。加えて、特徴が特定の実施形態に関連して記載されているように見えるかもしれないが、当業者は記載の実施形態の様々な特徴が本発明に従って組み合され得ることを理解するだろう。クレームにおいて、"有する"という語は他の要素又はステップの存在を除外しない。
【０１３１】
さらに、個別に列挙されているが、複数の手段、要素又は方法ステップは、例えば単一ユニット又はプロセッサによって実施されてもよい。加えて、個々の特徴は異なるクレームに含まれ得るが、これらは場合によって有利に組み合わされてもよく、異なるクレームへの包含は特徴の組み合わせが実現可能ではない及び／又は有利でないことを示唆するものではない。また、ある特徴をクレームの１つのカテゴリに含めることは、このカテゴリへの限定を示唆するものではなく、その特徴が必要に応じて他のクレームのカテゴリに等しく適用可能であることを示す。さらに、クレームにおける特徴の順番は、その特徴が動かされるべき特定の順番を示唆するものではなく、特に方法クレームにおける個々のステップの順番はそのステップがこの順番で実行されなければならないことを示唆するものではない。むしろ、ステップは任意の適切な順番で実行され得る。加えて、単数の言及は複数を除外しない。従って"ａ"、"ａｎ"、"第１"、"第２"などへの言及は複数を除外しない。クレーム中の参照符号は明確にする実施例として与えられているに過ぎず、決してクレームの範囲を限定するものと解釈されてはならない。
【図１】
0005508435.tif 000005
【図２】
0005508435.tif 000006
【図３】
0005508435.tif 000007
【図４】
0005508435.tif 000008
【図５】
0005508435.tif 000009
【図６】
0005508435.tif 000010