(57)【要約】  本発明によれば、画像の画素のそれぞれの属性を定義する最適関数を決定するように、標的属性を現在の繰返しに対して定義する、複数の画素にわたる単一のマーク領域を含む画像の画素を処理することによる、画像に属性を割り当てるコンピュータ実現方法が提供される。本発明の実施形態によれば、それぞれの属性が、最適関数に従って画像の画素に割り当てられ；画素の属性が表示される。また、本発明の好ましい実施形態によれば、マーク領域の厚みは実質的に単一の画素である。【選択図】  図２ａ
2009545052.tif 000002
【特許請求の範囲】
【請求項１】
画像に属性を割り当てるための、コンピュータ実現方法であって、
画像の画素のそれぞれの属性を定義する最適関数を決定するように、標的属性を現在の繰返しに対して定義する、複数の画素にわたる単一のマーク領域を含む画像の画素を処理するステップと、
最適関数に従って画像の画素にそれぞれの属性を割り当てるステップと、
前記画素の属性を表示するステップと、
を含む方法。
【請求項２】
マーク領域の厚みは、実質的に単一の画素である、請求項１に記載の方法。
【請求項３】
マーク領域によって影響される領域の大きさを決定するために、感度尺度を入力するステップをさらに含む、請求項１または２に記載の方法。
【請求項４】
マーク領域の画素が前記標的属性を持つことを余儀なくするステップをさらに含む、請求項１〜３のいずれかに記載の方法。
【請求項５】
画像の画素に追加入力制約を適用するステップをさらに含む、請求項１〜４のいずれかに記載の方法。
【請求項６】
追加入力制約は、画像の画素に対する属性の所与の割当てである、請求項５に記載の方法。
【請求項７】
所与の割当ては、前の繰返しの結果である、請求項６に記載の方法。
【請求項８】
前記入力は、外部コンピュータプログラムからの出力として派生する、請求項６に記載の方法。
【請求項９】
所与の割当ては、境界制約として使用される、請求項５または６に記載の方法。
【請求項１０】
画像または映像空間時間容積の映像シーケンスに特性を割り当てるための方法であって、
コンピュータ選択ツールを用いて、順次繰返し中に、複数の画素にわたる画像または映像空間時間容積のそれぞれの単一領域に対し、前記領域の画素に少なくとも１つの特性が割り当てられるように、マーキングするステップと、
マーク領域の画素の特性を前提とし、かつ前の繰返し時の計算結果を前提として、各繰返し時に画像または映像の画素のそれぞれの特性を算出するステップと、
算出された特性の少なくとも１つをハイライトするように画像を表示するステップと、
を含む方法。
【請求項１１】
特性を算出するステップは、マーク領域に対して割り当てられた特性および前の繰返しにおいて算出された非マーク領域の画素の特性の一部を維持する、請求項１０に記載の方法。
【請求項１２】
画像を複数の領域にセグメント化するための、請求項１〜１１のいずれかに記載の方法の使用であって、割り当てられた特性が、複数のセグメントのうちの１つに対する各画像の画素の分類である、使用。
【請求項１３】
映像シーケンスの空間時間容積を複数の領域にセグメント化するための、請求項１〜１１のいずれかに記載の方法の使用であって、割り当てられた特性が、複数のセグメントのうちの１つに対する各映像フレームでの各画像の画素の分類である、使用。
【請求項１４】
画像のマッティングのための、請求項１〜１１のいずれかに記載の方法の使用であって、各画素について割り当てられた特性が、複数のレイヤの各々にそれが属する部分である、使用。
【請求項１５】
映像のマッティングのための、請求項１〜１１のいずれかに記載の方法の使用であって、各映像フレームの各画素について割り当てられた特性が、複数のレイヤの各々にそれが属する部分である、使用。
【請求項１６】
画像または映像シーケンスに色を増やすための、請求項１〜１１のいずれかに記載の方法の使用であって、各画素について割り当てられた特性が画素の色である、使用。
【請求項１７】
画像または映像シーケンスの色を変えるための、請求項１〜１１のいずれかに記載の方法の使用であって、各画素について割り当てられた特性が画素の新しい色である、使用。
【請求項１８】
赤目効果を映像および画像から除去するための、請求項１７に記載の方法の使用。
【請求項１９】
前記プログラムがコンピュータで実行されるときに請求項１〜１８のいずれかに記載の方法を実行するためのコンピュータプログラムコード手段を含む、コンピュータプログラム。
【請求項２０】
コンピュータ可読媒体で具体化される、請求項１９に記載のコンピュータプログラム。
【請求項２１】
特性を画像または映像シーケンスに割り当てるためのシステム（３０）であって、
順次繰返し中に複数の画素にわたる画像または映像空間時間容積のそれぞれの単一領域に対し、前記領域の画素に特性が割り当てられるように、マーキングを行なうマーキングツール（３３）と、
マーク領域の特性および追加入力制約に応答して、各繰返し時に画像または映像の画素のそれぞれの特性を算出するための計算ユニット（３１）と、
計算ユニットに結合され、画像または映像を表示するための表示ユニット（３６）と、
を備えたシステム。
【請求項２２】
追加入力制約は、画像の画素に対する属性の所与の割当てである、請求項２１に記載のシステム。
【請求項２３】
所与の割当ては、前の繰返しの結果である、請求項２２に記載のシステム。
【請求項２４】
所与の割当ては、境界制約として使用される、請求項２２または２３に記載のシステム。
【請求項２５】
前記入力は、外部コンピュータプログラムからの出力として派生する、請求項２１に記載のシステム。
【請求項２６】
計算ユニットは、マーク領域に対して割り当てられた特性が維持され、かつ前の繰返しにおいて算出された非マーク領域の画素の特性の一部を維持するように、前記特性を計算するように適応される、請求項２１に記載のシステム。
【請求項２７】
計算ユニットに結合され、特性が前記領域に対して作成されたマーキングから伝搬する距離の感度を調整するための感度セレクタ（３５）をさらに備える、請求項２１〜２６のいずれかに記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本願は、２００６年７月２５日に出願した仮出願第６０／８２０２３２号の特典を主張し、その内容を参照によって本書に援用する。
【０００２】
発明の分野
本発明は、グラフィック編集に関する。
【背景技術】
【０００３】
従来技術
本発明の背景として関連すると考えられる従来技術の文献を以下に列挙し、それらの内容を参照によって本書に援用する。追加の文献は、上記の米国特許仮出願第号６０／８２０２３２号に示されており、それらの内容を参照によって本書に援用する。本書における参考文献の認知は、それらが本書に開示する発明の特許性に何らかの点で関係しているという意味を示唆するものではない。各文献は角括弧で囲んだ数字により識別され、したがって明細書全体を通して、従来技術は角括弧で囲んだ数字により参照される。
［１］  Ｒｏｔｈｅｒ，Ｃ．、Ｋｏｌｍｏｇｏｒｏｖ，Ｖ．およびＢｌａｋｅ，Ａ．ＧｒａｂＣｕｔ−Ｉｎｔｅｒａｃｔｉｖｅ  Ｆｏｒｅｇｒｏｕｎｄ  Ｅｘｔｒａｃｔｉｏｎ  ｕｓｉｎｇ  Ｉｔｅｒａｔｅｄ  Ｇｒａｐｈ  Ｃｕｔｓ，ＳＩＧＧＲＡＰＨ，ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｇｒａｐｈｉｃｓ，Ａｕｇ  ２００４．
［２］  Ｌｅｏ  ＧｒａｄｙおよびＧａｒｅｔｈ  Ｆｕｎｋａ−Ｌｅａ  Ｍｕｌｔｉ−Ｌａｂｅｌ  Ｉｍａｇｅ  Ｓｅｇｍｅｎｔａｔｉｏｎ  ｆｏｒ  Ｍｅｄｉｃａｌ  Ａｐｐｌｉｃａｔｉｏｎｓ  Ｂａｓｅｄ  ｏｎ  Ｇｒａｐｈ−Ｔｈｅｏｒｅｔｉｃ  Ｅｌｅｃｔｒｉｃａｌ  Ｐｏｔｅｎｔｉａｌｓ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ８ｔｈ  ＥＣＣＶ０４，Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  Ａｐｐｒｏａｃｈｅｓ  ｔｏ  Ｍｅｄｉｃａｌ  Ｉｍａｇｅ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｔｈｅｍａｔｉｃａｌ  Ｍｅｔｈｏｄｓ  ｉｎ  Ｂｉｏｍｅｄｉｃａｌ  Ｉｍａｇｅ  Ａｎａｌｙｓｉｓ，ｐ．２３０−２４５，Ｍａｙ  １５ｔｈ，２００４，Ｐｒａｇｕｅ，Ｃｚｅｃｈ  Ｒｅｐｕｂｌｉｃ，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ．
［３］  Ａ．Ｌｅｖｉｎ  Ｄ．ＬｉｓｃｈｉｎｓｋｉおよびＹ．Ｗｅｉｓｓ  Ｃｏｌｏｒｉｚａｔｉｏｎ  ｕｓｉｎｇ  Ｏｐｔｉｍｉｚａｔｉｏｎ．ＳＩＧＧＲＡＰＨ，ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｇｒａｐｈｉｃｓ，Ａｕｇ  ２００４．
［４］  Ｌｉｒｏｎ  ＹａｔｚｉｖおよびＧｕｉｌｌｅｒｍｏ  Ｓａｐｉｒｏ  Ｆａｓｔ  Ｉｍａｇｅ  ａｎｄ  Ｖｉｄｅｏ  Ｃｏｌｏｒｉｚａｔｉｏｎ  ｕｓｉｎｇ  Ｃｈｒｏｍｉｎａｎｃｅ  Ｂｌｅｎｄｉｎｇ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，ｖｏｌ．１５，ｎｏ．５，ｐｐ．１１２０−１１２９，Ｍａｙ  ２００６．
［５］  Ａ．Ｌｅｖｉｎ  Ｄ．ＬｉｓｃｈｉｎｓｋｉおよびＹ．Ｗｅｉｓｓ  Ａ  Ｃｌｏｓｅｄ  Ｆｏｒｍ  Ｓｏｌｕｔｉｏｎ  ｔｏ  Ｎａｔｕｒａｌ  Ｉｍａｇｅ  Ｍａｔｔｉｎｇ  ｉｎ  ＩＥＥＥ  Ｃｏｎｆ．ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ（ＣＶＰＲ），Ｊｕｎｅ  ２００６，Ｎｅｗ  Ｙｏｒｋ
［６］  ＵＳ  ２００６／０１４７１１５  Ｓｙｓｔｅｍ  ａｎｄ  ｍｅｔｈｏｄ  ｆｏｒ  ｉｍａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ  ｂｙ  ａ  ｗｅｉｇｈｔｅｄ  ｍｕｌｔｉｇｒｉｄ  ｓｏｌｖｅｒ
［７］  ＵＳ  ２００６／００５０９５９  Ｓｙｓｔｅｍ  ａｎｄ  ｍｅｔｈｏｄ  ｆｏｒ  ｉｍａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ  ｂｙ  ｓｏｌｖｉｎｇ  ａｎ  ｉｎｈｏｍｏｇｅｎｏｕｓ  ｄｉｒｉｃｈｌｅｔ  ｐｒｏｂｌｅｍ
［８］  ＵＳ  ２００６／０１５９３４３  Ｓｙｓｔｅｍ  ａｎｄ  ｍｅｔｈｏｄ  ｆｏｒ  ｍｕｌｔｉ−ｌａｂｅｌ  ｉｍａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ  ｏｆ  ｄｉｇｉｔａｌ  ｐｈｏｔｏｇｒａｐｈｓ
［９］  ＵＳ  ２００６／００３９６１１  Ｂｏｒｄｅｒ  ｍａｔｔｉｎｇ  ｂｙ  ｄｙｎａｍｉｃ  ｐｒｏｇｒａｍｍｉｎｇ
［１０］  ＵＳ  ２００４／０００８８８６  Ｕｓｉｎｇ  ｇｒａｐｈ  ｃｕｔｓ  ｆｏｒ  ｅｄｉｔｉｎｇ  ｐｈｏｔｏｇｒａｐｈｓ
［１１］  ＵＳ  ２００２／００４８４０１  Ｇｒａｐｈ  ｃｕｔｓ  ｆｏｒ  ｂｉｎａｒｙ  ｓｅｇｍｅｎｔａｔｉｏｎ  ｏｆ  ｎ−ｄｉｍｅｎｓｉｏｎａｌ  ｉｍａｇｅｓ  ｆｒｏｍ  ｏｂｊｅｃｔ  ａｎｄ  ｂａｃｋｇｒｏｕｎｄ  ｓｅｅｄｓ
［１２］  ＵＳ特許第６，７４４，９２３号  Ｓｙｓｔｅｍ  ａｎｄ  ｍｅｔｈｏｄ  ｆｏｒ  ｆａｓｔ  ａｐｐｒｏｘｉｍａｔｅ  ｅｎｅｒｇｙ  ｍｉｎｉｍｉｚａｔｉｏｎ  ｖｉａ  ｇｒａｐｈ  ｃｕｔｓ
［１３］  Ｙｕｒｉ  ＢｏｙｋｏｖおよびＶｌａｄｉｍｉｒ  Ｋｏｌｍｏｇｏｒｏｖ，Ａｎ  Ｅｘｐｅｒｉｍｅｎｔａｌ  Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  Ｍｉｎ−Ｃｕｔ／Ｍａｘ−Ｆｌｏｗ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｅｎｅｒｇｙ  Ｍｉｎｉｍｉｚａｔｉｏｎ  ｉｎ  Ｖｉｓｉｏｎ  ｉｎ  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ（ＰＡＭＩ），Ｓｅｐｔｅｍｂｅｒ  ２００４．
【０００４】
発明の背景
画像に対する特性の対話型割当てに関しては、多くの研究が存在する。１つの手法として、最初に画像をセグメント化し、次いで各セグメントの全画素に異なる特性を関連付けることができる。最新技術の対話型セグメンテーション手法に関する包括的な背景については、［１］を参照されたい。１つの特に関連する手法では、ユーザをしてオブジェクトの内部の画素にマーキングせしめることによって、画像／映像をセグメント化し、または画像／映像に特性を割り当てる。以下の手法は、特によく知られた方法に関する。
【０００５】
Ｍａｇｉｃ  Ｗａｎｄ［１］は、ポイントにマーキングすることによって、ユーザが領域を選択することを可能にする。米国カリフォルニア州フレモント、ＡｒｃＳｏｆｔ社のＡｒｃＳｏｆｔ  ＰｈｏｔｏＳｔｕｄｉｏ（登録商標）のような、この技術を使用するグラフィックスプログラムでは、マジックワンドを使用してポイントを選択すると、画像の他の非連続領域が選択されることが分かっている。これは望ましくない。
【０００６】
スクリブル（ｓｃｒｉｂｂｌｅ）に基づく他の公知の手法は、同じ問題を生じる傾向がある。例えば図１は、カラー化、すなわちグレースケール画像への色の指定に基づく、［３］に記載するようなスクリブルをベースとする選択を用いて、一部分だけを選択するように要求される画像のスクリーンショットである。カラー画像でより明瞭に見える通り、単一のピンクのスクリブルは、画像全体にピンクの色相を割り当てる。しかし、実際には、花のような画像の一部分だけを、割り当てられたピンク色に塗るように要求されることがより一般的である。［３］に記載された方法は、ユーザが１組のスクリブルを維持し、かつ時々スクリブルまたはその一部分を削除するように要求されるので、ユーザの経験が限定される。
【０００７】
Ｂａｙｅｓ  マッティング、Ｋｎｏｃｋｏｕｔ  ２［１］および他のマルチスクリブル手法［２〜１１］は、ユーザに複数のスクリブルを記させることによって、画像をセグメント化し、または特性を割り当てる。これらの方法により有用な結果をもたらすためには、ユーザが、少なくとも２つの異なる特性をもたらす複数のスクリブル（「シード」とも言う）を記さなければならない。例えば［２、５］に教示される画像マッティングまたはセグメンテーションにおいて、ユーザは全てのセグメントに対してスクリブルを提供しなければならない。例えば［３、４］に教示されるカラー化では、ユーザは複数の色に対してスクリブルを提供しなければならない。これらの方法の作業の流れは、ユーザが各繰返し時にスクリブルを追加または除去することによって複数のスクリブルを徐々に構築することを可能にする。さらに詳しくは、これらの手法はユーザには漸増的に見えるかもしれないが、実際には、スクリブルの全体を提供する集約情報を用いて、色の割当てを算出する。換言すると、ユーザの観点からは、システムに提供される入力は複数のスクリブルの集約セットである。したがって、たとえスクリブルセットが漸増的に構築される場合でも、かつたとえユーザが各繰返し時に単一のスクリブルを追加する場合でも、これらの方法は全て、各繰返しで複数のスクリブルの総和全体を使用する。したがって、ユーザは、これらの方法を制御するために、複数のスクリブルの全セットを知る必要がある。新しいスクリブルが最終結果にどのように影響を及ぼすかをユーザがよりよく判断することができるように、各繰返しの結果が、後続繰返しの始点として役立つようにすると好ましいことは明らかである。
【発明の概要】
【０００８】
本発明の１態様では、画像に属性を割り当てるための、コンピュータ実現方法であって、
画像の画素のそれぞれの属性を定義する最適関数を決定するように、標的属性を現在の繰返しに対して定義する、複数の画素にわたる単一のマーク領域を含む画像の画素を処理するステップと、
最適関数に従って画像の画素にそれぞれの属性を割り当てるステップと、
前記画素の属性を表示するステップと、
を含む方法を提供する。
【０００９】
本発明の変形例では、画像または映像空間時間容積の映像シーケンスに特性を割り当てるための方法であって、
コンピュータ選択ツールを用いて、順次繰返し中に、複数の画素にわたる画像または映像空間時間容積のそれぞれの単一領域に対し、前記領域の画素に少なくとも１つの特性が割り当てられるように、マーキングするステップと、
マーク領域の画素の特性を前提とし、かつ前の繰返し時の計算結果を前提として、各繰返し時に画像または映像の画素のそれぞれの特性を算出するステップと、
算出された特性の少なくとも１つをハイライトするように画像を表示するステップと、
を含む方法を提供する。
【００１０】
本発明の別の態様では、特性を画像または映像シーケンスに割り当てるためのシステムであって、
順次繰返し中に複数の画素にわたる画像または映像空間時間容積のそれぞれの単一領域に対し、前記領域の画素に特性が割り当てられるように、マーキングを行なうマーキングツールと、
マーク領域の特性および追加入力制約に応答して、各繰返し時に画像または映像の画素のそれぞれの特性を算出するための計算ユニットと、
計算ユニットに結合され、画像または映像を表示するための表示ユニットと、
を備えたシステムを提供する。
【００１１】
画素に適用される場合の用語「属性」は、色、彩度、色相などのような画素の特性を指す。用語「属性」および「特性」は、互換的に使用される。属性のタイプは用途に依存する。例えば、レイヤ分離またはセグメンテーションでは、属性は特定のセグメント／レイヤへの画素の割当とすることができる。カラー化では、属性は画素の色とすることができる。マッティングでは、属性は、マットレイヤの各々に割り当てられる各画素の相対部分とすることができる。色補正では、属性は各画素の色値に適用される特定の色変換とすることができる。動き割当てでは、特性は各画素に関連付けられる幾何学的変換とすることができる。深度割当てでは、特性は各画素に関連付けられる表面パッチの深度または法線ベクトルなどとすることができる。
【００１２】
したがって、本発明は、単一のマーク領域のみを使用して、画像、１組の画像、または映像における画素に対し属性を対話方式で割り当てるための方法を提供する。本発明は、画像の一部分、映像の一部分、または画像の組の一部分に適用することができる。本発明に係る方法により、ユーザは，我々が「スクリブル」と呼ぶコンピュータ実現ツール（例えばブラシ）を用いて，領域にマーキングを行なう。これらのスクリブルは、マーキングされた画素に何らかの単数または複数の特性を関連付けるために使用される。
【００１３】
さらに詳しくは、これまで提案された上述の方法とは対照的に、本発明の実施形態では、ツールは複数のセグメントへのセグメンテーションを可能にする。しかし、本発明はセグメンテーションより一般的であり、画像を離散的セグメントの組に明示的にセグメント化することなく、ユーザが連続特性を割り当てることを可能にする。さらに、かつ再びこれまで提案された方法とは対照的に、本発明に係る方法は、前回に算出した結果を追加入力として使用して、各繰返し時に単一スクリブルを使用することができる。ユーザは複数のスクリブルを提供し、あるいは漸増的に構築される１組のスクリブルを維持する必要が無い。
【００１４】
一部の実施形態では、半自動レイヤ選択ツールが設けられる。例えば「現在の」レイヤの概念を使用することができ、それによって新しくマーキングされたスクリブルが「現在の」レイヤに関連付けられる。レイヤが選択されないことも可能であり、その場合、次二マーキングされたスクリブルは新しいレイヤに関連付けられる。
【００１５】
本発明に係るこの方法は非常に直感的であり、使い易い。「関連」属性を選択するための高度なアルゴリズムと組み合わせることもできる。その結果、ユーザは高品質のマッティング、カラー化、深度割当て等を容易に実行することができる。
【００１６】
本発明を理解するため、かつそれをいかに実施することができるかを示すために、次に幾つかの実施形態を、単なる非限定的実施例として、添付の図面に関連して説明する。
【図面の簡単な説明】
【００１７】
【図１】選択された領域に属性を割り当てるための従来技術のグラフィックスツールの結果を示すスクリーンダンプである。
【図２ａ】選択された領域の画素に属性を割り当てるための本発明の実施形態に係る方法によって実行される主要な操作を示す流れ図である。
【図２ｂ】選択された領域の画素に属性を割り当てるための本発明の実施形態に係る方法によって実行される主要な操作を示す流れ図である。
【図３】属性を割り当てるための本発明に係る処理前の従来の画像を示すスクリーンダンプである。
【図４】単一スクリブルを用いて選択された図２に示す画像の領域を示すスクリーンダンプである。
【図５】図３で選択された領域を画定する算出された境界を示すスクリーンダンプである。
【図６】異なる領域を選択するための第２スクリブルの追加を示すスクリーンダンプである。
【図７】図６で選択された領域を画定する算出された境界を示すスクリーンダンプである。
【図８】算出された領域に適用される誤り訂正の結果を示すスクリーンダンプである。
【図９】誤りを訂正するための編集オプションを示す一連のスクリーンダンプである。
【図１０】マーク領域に適用された本発明の実施形態に係るマッティングの結果を示すスクリーンダンプである。
【図１１】マーク領域に適用された本発明の実施形態に係るマッティングの結果を示すスクリーンダンプである。
【図１２】算出された領域に適用された誤り訂正の結果を示すスクリーンダンプである。
【図１３】算出された領域に適用された誤り訂正の結果を示すスクリーンダンプである。
【図１４】選択された領域の画素に属性を割り当てるための本発明の実施形態に係るシステムの機能性を示すブロック図である。
【図１５】本発明の異なる態様に係る２Ｄ画像の画素に対応付けられる深度情報を示す絵画的表現である。
【図１６】２Ｄ画像に深度を加えるために使用される平面深度ツールに関する絵画的表現である。
【発明を実施するための形態】
【００１８】
図２ａは、図３ないし５の処理の様々な段階で示される、画像１０の選択された領域の画素に属性を割り当てるための本発明の実施形態に係る方法によって実行される、主要な操作を示す流れ図である。提示された作業の流れを説明するために、画像セグメンテーションの特定の例（例えばレイヤへのセグメンテーション）に焦点を合わせる。ユーザは、単一のスクリブルを所望の領域に適用することによって、画像の領域を手動で選択する。ユーザによってマーキングされた画素は、適切な有意水準内で共通の画素属性が、マーキングされた画素に属するとみなされる領域、またはマーキングされた画素がこの属性を持つことを余儀なくされる領域を画定する。本発明の他の適用例、例えばセグメンテーションに関係しない適用例では、ユーザは、類似属性を有する画素にマーキングする必要があるかもしれない。したがって、スクリブルは標的属性を定義する単一のマーク領域を画定する。本発明の広い態様では、図３に示す画像の画素は、マーク領域の全ての画素が定義された標的属性を持つことを余儀なくする一方で、画像の画素のそれぞれの属性を定義する最適関数を決定するように処理される。このようにして決定されたそれぞれの属性は、最適関数に従って画像の画素に割り当てられ、画素の属性が表示される。
【００１９】
図２ｂは、画像または映像空間時間容積の映像シーケンスに特性を割り当てるための上述した方法の変形例を示す流れ図である。順次繰返し中に画像または映像空間時間容積のそれぞれの単一領域に対し、マーク領域の画素に少なくとも１つの特性が割り当てられるようにマーキングするために、ポインタのようなコンピュータ選択ツールが使用される。各繰返し時に、マーク領域の特性が与えられ、前の繰返し時の算出結果が与えられて、画像または映像の画素のそれぞれの特性が算出される。算出された特性の少なくとも１つをハイライトするように、画像が表示される。
【００２０】
さらに図３ないし５に関連して、図３は、湖１２と芝生１３を含む沿岸領域と森１４とを含む基本的に３つの別個の領域を有する背景に対する、前景の少女１１の原画像１０のマークを付加する前の状態を示す。当初、いずれかのセグメントに属する画素は存在しない。
【００２１】
図４は、湖１２の領域のみに制限される単一の第１スクリブル１５が付加された、第１回の繰返しを示す。図５は、画像がセクション１およびセクション２と識別される２つのセグメント化されたレイヤに分割された、第１スクリブル後の結果を示す。画像のその後にマーキングされた領域を、特定のレイヤに関連付けることを可能にするために、画像の全てのレイヤが、ディスプレイの脇に示されるユーザ選択可能リスト１６に列挙され、レイヤにはユーザが、例えば「背景」および「前景」のように、命名することができる。その後選択された領域は、リスト１６でハイライトされたレイヤに関連付けることができ、デフォルトとして第１レイヤがハイライトされる。スクリブル領域および関連画素は新しいレイヤを作成するために使用されるか、あるいは既存のレイヤの１つに追加される。画素が追加されるレイヤは、既存のレイヤのリストからユーザによって選択され、現在選択されているレイヤが無い場合には、新しいレイヤに追加される。セクション１は、湖の境界内に制限されるマーク領域を含み、セクション２は、少女および沿岸領域をはじめとする画像の残部を含む。したがってレイヤは、複数の連結成分を含むことができることが注目される。画像または映像のセグメントへの分割は、例えば［１１］に記載される通り標準的手順である。１つのセグメントは、スクリブル（またはその一部分）およびそれに関連する全ての画素を含み、もう１つのセグメントは、残りの画素を含む。本発明は各繰返し時に単一スクリブルをマーキングすることに限定されないことに留意されたい。ユーザは、同一レイヤに属するかもしれず属さないかもしれない、複数のスクリブルをマーキングすることができる。複数のスクリブルをマーキングする場合、ソフトウェアは、マーキングされたスクリブルに対する画素の関係に従って、画像を２つ以上のレイヤに分割する。したがって、本発明に係る方法は単一スクリブルにより機能することができるが、単一スクリブルに限定されない。さらに、複数のスクリブルが使用される場合でも、前の計算結果が現在マーキングされているスクリブルと共に入力として使用されるが、上述の通り、これまで提案されてきた方法は、全ての繰返しでマーキングされたスクリブルの集約セットを使用し、前の計算結果を無視する。
【００２２】
図６は、芝生と湖との間の境界を交差する第２スクリブル２０が追加された、第２回の繰返しを示す。図７は第２スクリブル後の結果を示し、セクション１として識別される第１レイヤは延長され、湖の境界内に制限されたマーク領域の一部を含み、セクション２は、少女および沿岸領域をはじめとする画像の残部を含む。アルゴリズムは背景の一部を割り当てただけであるので、この繰返しの結果がまだ完全な最終結果ではないことは理解されるであろう。湖および芝生を同一セグメントに割り当てる、所望の結果を達成するためには、ユーザとのさらなる対話が必要である。２回の繰返しでは最終結果を達成するのに充分でないという意味で、これは対話型セグメンテーションアルゴリズムにかなり典型的である。結果はまた、底部のスライダによって決定される感度尺度にも依存する。
【００２３】
図８は、計算された領域に適用された誤り訂正の結果を表わすスクリーンダンプを示す。ユーザはピンクのスクリブルを花の上に描くことによって操作を開始する。ユーザが誤って、またはおそらく意図的に、花の外にスクリブルをマーキングする。ここで、ユーザは誤った領域に緑のスクリブルを引くことによって、これを克服しようとする。これは、［３］のようなこれまで提案された方法では、緑色のスクリブルがピンクのスクリブルに上書きされるが、ピンクのスクリブルの一部が残り、花の外側の領域の一部がピンクのまま残るので、うまく機能しない。これまで提案されたツールによりこれを修正する従来の方法は、ピンクのスクリブルのレイヤに戻り、ピンクのスクリブルを花から消去し、レイヤを再び計算する。誤ったスクリブルを消去する必要があるということから、古いスクリブルを全部表示し、かつ「消去」ツールを提供するための他の方法が必要になる。古いスクリブルを表示し、それらの一部を消去しなければならないということは、全てのユーザにとって直感的ではないないかもしれないことが明らかになっている。
【００２４】
対照的に、本発明に係る方法について、誤りを訂正するための編集オプションを表示する一連のスクリーンダンプを示す図９を参照しながら、今度は画像セグメンテーションの文脈で実証する。ユーザは背景にスクリブルをマーキングするが、偶発的に前景にマーキングする。本発明を使用して、ユーザは、図９に示すように前景のスクリブルにマーキングすることによって、これを修正する。左上の写真で、ユーザは少女を指定するスクリブルをマーキングするが、偶発的に芝生にもマーキングする。その結果、算出されたレイヤは、右上に示す通り、少女の画素のみならず、芝生の画素をも含む。この誤りを訂正するために、ユーザは単に、右下に示すように（ソフトウェアアプリケーションウィンドウの右上のレイヤリストに「セクション２」と定義された）芝生レイヤを選択した後、芝生領域にスクリブルするだけでよい。その結果、右下の写真に示す通り、芝生画素は全部、それらの正しいレイヤに再割当てされる。これは、ユーザが前にマーキングしたスクリブルを削除する必要のある、［３］のようなこれまで提案された方法とは対照的である。
【００２５】
実現
ここで、本発明を実現する１つの方法を提案する。ＧＵＩモジュールは、ユーザに前の繰返しの結果を提示し、各々その特性に関連付けられた１つまたはそれ以上のスクリブルをユーザにマーキングさせる。例えば、画像セグメンテーションでは、スクリブルはセグメントインデックスに関連付けられる。さらに、いわゆる感度尺度を定義することができる。直感的に、この尺度は、特性がスクリブルから伝搬していく画素の数で測定される距離に影響する。ボトルの例では、一方の極端では、スクリブル自体のみがオレンジ色になるが、反対側の極端では、画像全体がオレンジ色になり、他の感度値の場合、ボトルの一部分が着色されるか、ボトル自体だけが着色されるか、あるいはボトルを越えて着色され、全てが感度尺度に依存する。したがって、直感的に、感度因子は「オレンジ色」が伝搬する距離を決定する。感度尺度は様々な手段により、例えばＧＵＩのスライダを用いて決定することができる。
【００２６】
ソフトウェアのアルゴリズムモジュールは、マーキングされたスクリブル（単数または複数）、ソース画像／映像、および前の繰返しの結果（またはこれが最初の繰返しであるという標識）、ならびにおそらく感度尺度のような追加パラメータを入力として受け取る。
【００２７】
アルゴリズムモジュールの詳細な実現例を提示する前に、代替的実現を使用することができること、およびこの実現は、提示する発明を効率的に実現することができるようにするために提示するものであることを、強調しておきたい。
【００２８】
提案する実現は次の２段階を含む。
Ａ．マーキングされた単数または複数のスクリブルの近傍の「塗りつぶし領域」を算出する。以下で、「塗りつぶし領域」の意味、およびそれがいかに算出されるかをさらに説明する。
Ｂ．特性割当てアルゴリズムを「塗りつぶし領域」に適用する。
【００２９】
特定のアルゴリズムの詳細を論じる前に、特性割当てアルゴリズムは、赤目に関連付けられる画像の領域を識別し、次いでマーク領域に黒色属性を割り当てることによって、赤目効果を映像および画像から除去するために使用することができることを記載しておきたい。
【００３０】
段階Ａは、例えば単数または複数のスクリブルから測地的距離マップのような距離マップを算出し、所与の閾値より小さい全ての距離が塗りつぶし領域内とみなされるように、距離を２値化することによって、実現することができる。閾値は、例えばＧＵＩのスライダを用いて決定することのできる、上述した感度尺度によって決定することができる。１組のスクリブルからの測地的距離マップ算出の詳細な実現は、文献［３］に見ることができる。塗りつぶしは２値化による測地的距離マップに限定されないことを記載しておきたい。例えば塗りつぶしは、スクリブルの領域内の画素の色分布、またはスクリブルの領域内の画素関数の分布の表現に基づいて、定義することができる。さらに詳しくは、塗りつぶしは、距離マップ算出で画素の色差を用いる代わりに、スクリブル領域内の画素差の分布で充分に頻繁に見ることのできる最近接色差を画素の色差から引いたものを使用するように、距離マップを再定義することによって実現することができる。代替的に、距離マップ算出で画素色差を使用する代わりに、スクリブル領域内の画素差の分布に画素色差頻度の関数を使用することが可能である（例えば、ｆが色差分布における頻度である場合、ｌｏｇ（ｆ＋１）を使用する）。
【００３１】
なお、本発明は、スクリブルマーキングの前、後、または途中に、感度尺度を変更することが可能である。換言すると、ユーザは、例えば最初にスクリブルをマーキングし、次いでユーザが結果に満足するまで、（例えばスライダを動かすことによって）感度尺度を変更することができる。代替的に、ユーザはスクリブルを引く間に感度尺度を操作することができる。例えばソフトウェアは、マーキングされたスクリブルの特性に応じて、例えばその総面積によって、感度尺度を決定するかもしれない。
【００３２】
段階Ｂについては、２つの実現を提案する。１つは画像／映像に離散的特性を割り当てる場合であり、１つは連続的特性を割り当てる場合である。
【００３３】
段階Ｂの実現：離散的特性の場合
有向グラフＧ＝（Ｖ，Ｅ）を定義する。グラフＶにおけるノードの集合は、３つの部分集合の和集合であるＶ＝Ｖ１ＵＶ２ＵＶ３である。Ｖ１はスクリブルでマーキングされた画素の集合であり、Ｖ２はスクリブルでマーキングされない塗りつぶし領域内部の画素の集合であり、Ｖ３は塗りつぶし領域の境界上および塗りつぶし領域でない画素の集合である。
【００３４】
グラフにおけるエッジＥの集合は、画像／映像で隣接している、Ｖ×Ｖからの画素の全ての対を含む。画像／映像における近傍とは、多くの方法で定義することができる。例えば８近傍では、画素が全ての座標で最大限１だけ異なる場合に、隣接画素と定義する。実際にはＶ３から２つの頂点を含む対をＥに含める必要はない。さらに、各画素に対し１組の離散値の１つを定義するラベル付け関数Ｌ（ｐ）を定義する（画像セグメンテーションでは、Ｌ（ｐ）はセグメントインデックスを表わす）。
【００３５】
グラフは、ソフトウェアで多くの方法で表わすことができる。グラフ表現およびグラフ全体の最適化の例は、文献［１２］に見ることができる。
【００３６】
上記グラフおよびラベル付けに対してコスト関数を定義し、その最適値を求める。単一スクリブルがマーキングされるだけの場合、または全てのスクリブルが同一特性に関連付けられる場合、下に示すように、近似式を最小カット最大フロー問題として定式化することができ、それに対して多くの最適化解が存在する［１３］。
【００３７】
異なる特性に関連付けられる複数のスクリブルがマーキングされる場合、解は、［１］で同様のタスクに行なわれたように、マルチラベルオプティマイザ、例えば繰返しグラフカット［１２］を用いて達成することができる。
【００３８】
マルチラベルオプティマイザによる解
一般的な場合、解は［１］で同様のタスクに行なわれたように、マルチラベルオプティマイザ、例えば繰返しグラフカット（［１２］参照）を用いて達成することができる。解は次のコスト関数を最適化することによって見出される。
2009545052.tif 000003
【００３９】
ここで、Ｌは画像／映像画素のその特性へのラベル付けである。
【００４０】
関数ｆＮ、ｆＳ、ｆＢは、用途によって異なる。例えば画像セグメンテーションでは、ｆＮは、２つの画素Ｌ（ｐ１）、Ｌ（ｐ２）のラベル付けが異なる場合には、弱い逆単調（ｗｅａｋｌｙ  ｉｎｖｅｒｓｅ  ｍｏｎｏｔｏｎｉｃ）の方向微分（ｄｉｒｅｃｔｉｏｎａｌ  ｄｅｒｉｖａｔｉｖｅ）、それ以外では零と定義することができる。我々の実現では、例えば、Ｌ∞ノルム下で、画素ｐ１、ｐ２の色差のスケーリングされた負の指数を採用した。
2009545052.tif 000004
ここでｋは、実験的に例えば１／２５５に設定するこのできるスケーリングパラメータである。
【００４１】
ｆＢは、全ての画素の全てのラベルに０を設定することができるが、画素を特定の特性に関連付けることを選好する何らかの事前の想定を表現するために、異なる値に設定することができる。
【００４２】
ｆＳは一般的に、スクリブルの制約を表わす。ＩＬ（ｐ）を次のように定義しよう。ｐがＶ１にある場合には、ＩＬ（ｐ）はスクリブルに関連付けられるラベルである。ｐがＶ３にある場合には、ＩＬ（ｐ）は、前の繰返しにおけるｐのラベル（またはこれが最初の繰返しである場合は、新しいラベル）である。次いで、ｆＳは次のように定義される。
2009545052.tif 000005
【００４３】
ここで、∞はコンピュータ実現において非常に大きい数字を表わす。直感的に、これはスクリブルが解に対し強い制約を課すことを意味する。代替的に、無限大に相当する数字を、異なる画素に対して異なることのできるより小さい数字に置き換えることによって、より弱い制約を使用することができる。
【００４４】
最適化のための解が見つかると、現在の繰返しの結果を算出することができる。これは、前の繰返しの結果に最適化解からの塗りつぶし領域の画素のラベル付けをコピーする（または、最初の繰返し時には、最適化解を最初の繰返し結果として設定する）ことによって行なわれる。
【００４５】
最小カットによる解
現在の繰返しで単一スクリブルがマーキングされる場合、またはマーキングされた全てのスクリブルが同一特性を有する場合、２つのラベルを持つコスト関数を定義することができる。そのようなコスト関数は、下で示すように、最小カット最大フロー［６］を用いて最小化することができる。最小カット最適化では、２つのノードＳ、Ｔを追加し、最適化はグラフの頂点を、Ｓに接続された組およびＴに接続された組の２組に分割する。基本的概念は、Ｓに接続されていることが明らかになる頂点には、スクリブルのラベルが割り当てられる一方、残りの頂点は前の繰返しからのそれらの割当てが維持される（または該方法が最初の繰返し内にある場合、新しい値が割り当てられる）というものである。簡潔にするために、Ｖ３を２組に分割する。Ｖ３Ａは前の繰返しの結果で単数または複数のスクリブルに関連付けられた特性を有するＶ３内の頂点の集合であり、Ｖ３Ｂ＝Ｖ３＼Ｖ３Ａである。
【００４６】
集合Ｅ内のエッジＣ（ｐ１，ｐ２）の容量は、Ｃ（ｐ１，ｐ２）＝ｆＮ（（ｐ１，ｐ２，Ｌ）と設定される。ＴをＶの画素に接続する全てのエッジの容量は０に設定され、同様にＶの画素をＳに接続する全てのエッジの容量は０に設定される。
【００４７】
ＳをＶ１またはＶ３Ａの画素ｐに接続するエッジの容量Ｃ（Ｓ，ｐ）は、∞になるように設定される。
【００４８】
Ｖ１またはＶ３Ｂの画素ｐをＴに接続するエッジの容量Ｃ（ｐ，Ｔ）は、∞になるように設定される。
【００４９】
頂点をＴにまたはＳから接続する全ての他のエッジは、容量０を有する。
【００５０】
ここで、∞はコンピュータ実現において非常に大きい数字を表わす。直感的に、これはスクリブルが解に対し強い制約を課すことを意味する。代替的に、∞数字をより小さい数字に置き換えることによって、より弱い制約を使用することができる。
【００５１】
別の実現では、画素をスクリブル特性に関連付けることを選好する何らかの事前の想定を表現するために、Ｖ２における頂点をＳから接続するエッジの容量は、正の値を持つように設定することができる。同様に、画素をスクリブル特性に関連付けることを選好する何らかの事前の想定を表現するために、Ｖ２における頂点をＴに接続するエッジの容量は、正の値を持つように設定することができる。
【００５２】
ここで、最小カット問題の解（またはマルチラベルオプティマイザ）を使用して、画像セグメンテーションを設定する。最小カット最適化によってＳに接続されることが明らかになる全ての画素には、スクリブル特性が割り当てられる。他の画素には、前の繰返しの結果得たラベルが割り当てられる（または、最初の繰返し時には、新しいラベルが割り当てられる）。
【００５３】
段階Ｂの実現：連続的特性
［４、５］でカラー化およびマッティングタスクに適用されるような連続的事例について１つの実現を提示する。これらの文献は、１組の１次方程式を解くことによって、連続関数に対してコスト関数を最小化する最適化技術を使用している。マッティングおよびカラー化以外の用途は、最小化されるコスト関数を単に変更することによって、この手法で実現することができることに留意されたい。段階Ｂの我々の実現は、１つの工夫を除くと、上記文献と同一である。上記文献では、全ての強い制約が、ユーザによってマーキングされるスクリブルによって定義される。我々の実現では、ユーザによってマーキングされたスクリブルを１組の制約として使用し、Ｖ３の各画素に対して追加の制約を生成する。換言すると、我々の解は簡約化（ｒｅｄｕｃｔｉｏｎ）によって達成することができる。［４］、［５］の方法を実現し、前の繰返しのラベル付けによりＶ３の各画素にスクリブルを追加する。この方式は、［１１］に記載されているバイナリ画像セグメンテーションのような離散した２ラベルのタスクを、連続的画像マッティングに一般化するのに有用である。
【００５４】
本発明の操作をより明確にするために、ここで、セグメンテーション（レイヤ化）の場合のプロセスを説明することによって、実施例を提示する。これに続いて、連続的特性を割り当てるカラー化の文脈内の異なる実施例を提示する。
【００５５】
したがって、ユーザが、ボトルによって定義される輪郭内の画像オブジェクトを選択したい場合を仮定する。ユーザは、ボトルの内側にスクリブルをマーキングすることによって開始する。ユーザにとって起きているように見えるものは、画像が２つの領域に分割され、あたかもスクリブルが拡張したかのように見えることである。この拡張は、全ての方向に対称的ではなく、むしろ、画像変動性が強い方向に停止するかのように見える。例えばボトルの色の変化が非常に小さく、かつボトルエッジが強い場合には、スクリブルはボトルエッジまで拡張する。他方、ボトルがテクスチャのある外観を有する場合、スクリブルは関心領域の一部分だけを含むように拡張する（図３に示した少女の写真の芝生の場合のように）。ユーザには、拡張の程度を制御するスライダ（感度セレクタを構成する）が提供される。
【００５６】
この段階の結果は、画像が２つのレイヤにセグメント化することである。
【００５７】
我々の実現の水面下で起きることは、次の２段階のプロセスである。
Ａ．画像を３つの領域、すなわち１）スクリブル、２）拡張スクリブルから原スクリブルを差し引いた部分、３）画像の残部に分割する、「スクリブル拡張」のためのアルゴリズムを適用する。
Ｂ．２つのセグメント間の上記領域２）内の最も顕著な境界を見出すアルゴリズムを適用する。これは数学的に、不明領域内の画素へのセグメント値の割当てを探索し、この割当てが最も顕著な境界を誘発するようにすることと同等である。
【００５８】
後続の繰返し中に、各スクリブルは、既存のレイヤの１つまたは新しいレイヤのいずれかに関連付けられ、我々はそれをレイヤＬで表わす。ユーザは、既存のセグメントの部分を「侵食」するように見えるスクリブルをマーキングして、レイヤＬを大きくする。
【００５９】
我々の実現の水面下で起きることは、領域３）が前の繰返しからの元のラベル付けを維持することを除き、上述したものと同様である。最も顕著な境界を見出す際に（上記段階Ｂ）、前の繰返しのセグメンテーション結果はレイヤＬと他のレイヤとの間の境界が存在する場所に影響を及ぼすので、アルゴリズムは該セグメンテーション結果も考慮に入れることに留意されたい。
【００６０】
カラー化において、プロセスは同様であるが、ここでは各画素に連続色相値を割り当てる。これは一般的に、スクリブル領域自体を除き、画像に割り当てられた色の大部分がスクリブルの色と同じにならないことを意味する。最初の繰返しにおいて、ユーザがボトルにオレンジ色のスクリブルをマーキングした場合、ボトルはいっそうオレンジ色になり、画像の他の部分は灰色がかったままであるが、ボトル全体が全て厳密に同一色相にはならないことが分かるであろう（ボトル領域の内側のテクスチャに比較して、ボトル境界がいかに強いかに依存する）。
【００６１】
図１０および１１は、ボトルに対してではなく、単一スクリブルがマーキングされた鳥に対して、上述の通りマーク領域に適用された、本発明の実施形態に係るカラー化の結果を示すスクリーンダンプである。スクリブルは、グレースケールでそれをより見易くする明るい領域によって表わされる。図１１は割り当て結果の可視化を示し、そこで各画素に、その色相がどれだけ強くオレンジ色になるかを示す０から１の間の連続体の数字が割り当てられる。
【００６２】
ここでの実現は、段階Ｂが変更されることを除き、上記と同様とすることができる。最も顕著な境界を探す代わりに、色相の変化が原入力画像におけるエッジ／勾配に対応するように、不明領域（領域２）の全ての画素に対する色相の割当てを探索するアルゴリズムを使用する。これは、エッジが不鮮明のぼやけた画像では、色相遷移が漸進的になることを意味する。
【００６３】
追加のツール：領域への特性の再割当て
画像に特性を再割当てするための別の組のツールを提案する。本発明で提示するような対話型特性割当てアプリケーションで作業をしていると仮定しよう。提案するツールは、ユーザが領域にマーキングし、したがってこの領域のみの特性割当てを再計算するように要求することを可能にする。我々が複数のツールと呼んでいるのは、これらのツールが幾つかの態様を変化させることができるためである。
（ｉ）このツールで使用されるアルゴリズムは、アプリケーションの前の繰返しで使用されたアルゴリズムと異なるかもしれず、異ならないかもしれない。
（ｉｉ）この領域を再計算するときに、マーク領域の境界は考慮されるかもしれず、されないかもしれない。
（ｉｉｉ）ツールは、例えばユーザにスクリブルをマーク領域内に引かせることによって、さらに制約を追加するオプションを含むかもしれず、含まないかもしれない。
【００６４】
図１２および１３は、画像セグメンテーションの文脈における本発明のそのような実施形態に係る再割当てツールの作用を示す画像である。図１２は、上述した対話型画像セグメンテーションアプリケーションにおける前の繰返しのセグメンテーション結果を示す。さらなる実施形態では、ユーザが領域にマーキングを行ない、マーク領域に特性を再割当てするように要求することを可能にするツールを提案する。実施例では、これは、関心領域の周りに境界曲線を引くことによって、画像を再セグメント化するために行なわれる。
【００６５】
図１３は再計算の結果を示す。この特定の実施例では、前の繰返しのセグメンテーション結果がマーク領域の境界に対して制約として使用され、前節で段階Ｂに記載したアルゴリズムを使用して連続セグメンテーションを割り当て、次いでそれらを０．５で２値化することによって、マーク領域のセグメンテーションが再計算された。前の繰返しでは、セグメンテーションアルゴリズムは離散的特性を想定していた。
【００６６】
ツールの１つの実現は、上記の「実現」の節で記載した段階Ｂの実現を使用することによって簡単になる。段階Ｂは、前記の節で、「特性割当てアルゴリズムを『塗りつぶし領域』に適用すること」と定義された。提案する再割当てツールでは、代わりに、ユーザによってマーキングされた領域に特性割当てアルゴリズムを適用する。
【００６７】
上記態様（ｉｉ）についてさらに説明するために、離散的特性に対して段階Ｂを使用することを考える。この実現では、上記態様（ｉｉ）は、頂点Ｖ３に対する近傍制約ｆＮを含めることができることを意味する。そのような場合、我々は確かに境界を考慮に入れる。代替的に、制約を含めないことを選択することができ、その場合には境界を考慮に入れない。
【００６８】
図１４は、属性を画像に割り当てるための本発明の実施形態に係るシステム３０の機能を示すブロック図である。システム３０は、メモリ３２に格納された画像の画素を処理し、かつかつ画像の画素のそれぞれの属性を定義する最適な関数を決定するように、現在の繰返しの標的属性を画定する単一のマーク領域を含めるためのプロセッサ３１を備える。これは、マーク領域の画素が前記標的属性を持つように制約しながら行なわれる。マーキングツール３３は、現在の繰返しに対して画像をマーキングするために使用されるが、事前にマーキングされた画像をシステム３０への入力として使用することもできる。属性割当てユニット３４は、最適関数に従って、それぞれの属性を画像の画素に割り当てるためにプロセッサ３１に結合される。特性がスクリブルから伝搬する距離の感度を調整するために、感度セレクタ３５をプロセッサ３１に結合することができる。プロセッサ３１に結合されたディスプレイユニット３６は、格納された画像と共に画素の属性を表示する。
【００６９】
本発明に係る方法は一般的に反復プロセスとして実行され、各順次繰返しで前の繰返しの結果である制約が適用されるので、順次繰返しは所望の結果に収束する。最も一般的には、順次繰返しは、発明の方法に従って動作するように適応されたアプリケーションプログラムによって実行される。しかし、そのようなアプリケーションプログラムは、異なるプログラムの出力または前に生成された同一プログラムの出力さえも、入力として受け取るように適応させることができる。
【００７０】
深度ツール
本発明のこの態様は、２Ｄ画像または画像の一部を、画像＋深度マップとして表わされる３Ｄモデルに変換するための完全な作業の流れを含む。提示する基本的な作業の流れは、初期３Ｄモデルと、ユーザが所望の透視図から３Ｄモデルを見ることを可能にする標準３Ｄ  ＧＵＩとを、ユーザに提供する。次いで、豊富なツールの集合を用いて、ユーザは、画像に深度値を割り当てることによって、３Ｄモデルを形成することができる。
【００７１】
提案する発明を理解する鍵は、図１５に示すように、データ表現およびレンダリングにある。画像の画素の深度値は、我々が「カノニックパースペクティブ（ｃａｎｏｎｉｃ  ｐｅｒｓｐｅｃｔｉｖｅ））」と呼ぶものに関連して表わされる。直感的に、カノニックパースペクティブは、２Ｄ画像を取り込む元になるビューイングパースペクティブを模しており、撮影用カメラの位置、向き、および他の特性、例えば視界およびズームを含む。実際には、平面に画像テクスチャを配置することによって仮想世界を構築し（それをテクスチャ平面と呼ぶ；例えば平面Ｚ＝０）、画像のフルテクスチャを正確に取り込むようにカノニックパースペクティブを配置する。例えば、テクスチャ平面からのカノニックパースペクティブの任意の距離を決定し、フル画像テクスチャを正確に取り込むように、カノニックパースペクティブの視界を設定することができる（高校の三角法を用いて容易に計算することのできる詳細は省く）。
【００７２】
便宜上、Ｚ軸がカノニックパースペクティブの光軸となり、世界のＸ、Ｙ軸の方向が取り込まれる画像のＸ、Ｙ軸の方向となり、かつ原点がカノニックパースペクティブのピンホールとなるように、世界座標を設定する。この表現において、３Ｄ点の深度値は単にこの点のＺ座標であり、世界座標系のＺ軸は、テクスチャ座標系の原点で画像テクスチャ平面と交差する。
【００７３】
便宜上、我々はこの座標系を選択するが、本発明は代替座標で実現することができることに留意されたい。例えば、他の座標系を使用する場合、座標系の変化を考慮する追加的変換を含めることができる。
【００７４】
我々が提案するツールは、画像の画素に関連付けられる深度値の組を編集する。この組の値を深度マップと呼ぶことにする。次いで、３Ｄモデルを２Ｄにするか、あるいは他の方法で使用することが必要になった場合いつでも、これは、修正透視画法（Ｃｏｒｒｅｃｔｅｄ−ｐｅｒｓｐｅｃｔｉｖｅ−ｒｅｐｒｅｓｅｎｔａｔｉｏｎ＝ＣＰＲ）と呼ぶ新しい表現法で行なうことができる。ＣＰＲは、レンダリングの一部として明示的にまたは黙示的に形成することができる。ＣＰＲ表現は次のように形成される。すなわち、図１５に示すように、（Ｘ，Ｙ）を画像テクスチャ座標とし、Ｚをその関連深度値とし、ｄを画像テクスチャ平面の深度とする。対応するＣＰＲ点は（Ｘ／ｄ＊Ｚ，Ｙ／ｄ＊Ｚ，Ｚ）によって与えられる。
【００７５】
深度編集ツール
平面深度ツール
このツールは、ユーザが画像テクスチャの特定領域に平面幾何学を割り当てることを可能にする。ユーザが３Ｄモデルの任意の位置に配置することのできる２つの制御点がユーザに提供される。３Ｄ  ＧＵＩにおける現在のビューイングパースペクティブを前提として、該方法は、各制御点のビューイング光線を現在の３Ｄモデルと交差させる。この交差は、各制御点に対し、テクスチャ座標（Ｘ，Ｙ）および深度マップ値Ｚを定義する。
【００７６】
ここで、ユーザは制御点をドラッグして、対話的にモデルに対するこれの作用を見ることができる。スクリーン上のドラッグは、「ドラッグ面」と呼ぶものを用いて３Ｄ制御点のドラッグに変換される。ドラッグ面を前提として、例えばマウスで制御点を移動させることによって、該方法は、マウス位置のビューイング光線をドラッグ面と交差させることによって、スクリーン上のマウスの位置をドラッグ面上の位置と関連付ける。ドラッグ面は、該方法によって、３Ｄ  ＧＵＩにおける現在の視認方向と直交する平面、またはそれに近接する何らかの平面となり、いずれの場合も制御点がこの平面に入射するように、自動的に設定することができる。１つの実現では、ドラッグ面は、現在の視認方向と直交する平面に最も近い、｛ＸＹ，ＸＺ，ＹＺ｝の１つとなるように選択される。
【００７７】
制御点をドラッグすると、例えばＸ軸またはＹ軸の方向にドラッグすることにより、その関連テクスチャ座標（Ｘ，Ｙ）、または深度マップ値（Ｚ軸上でドラッグすることにより）のいずれかを変化させることができる。
【００７８】
ここで、２つの制御点の位置が付与されると、ツールは深度マップ上の２つの制御点間に勾配を描くことによって、深度マップを更新する。深度マップの値は、以下の方法で決定される。
【００７９】
（Ｘ１，Ｙ１）、（Ｘ２，Ｙ２）を２つの制御点のテクスチャ座標とし、かつＺ１、Ｚ２を２つの制御点の深度値とする。
次のように定義する。
2009545052.tif 000006
点（Ｘ，Ｙ）が与えられるとその深度Ｚは、次の関数（または同様のもの）：
2009545052.tif 000007
によって、または単に、次式：
2009545052.tif 000008
によって決定することができる。
【００８０】
図１６ａ、１６ｂ、および１６ｃは、平面深度ツールの絵画的表現である。図１６ａは、カノニックパースペクティブからの画像テクスチャの図である。画像テクスチャは２つの領域にセグメント化されており、平面深度ツールは標識セグメントに適用される。着色レンディションでは、標識が選択されたことを示すために、それが青色になることが分かる。図１６ｂは、異なるパースペクティブからの３Ｄモデルのツールを適用する前の図であり、図１６ｃはツールを適用した直後の同じ図を示す。
【００８１】
本発明に係るシステムは、適切にプログラムされたコンピュータとすることができることも理解されるであろう。同様に本発明は、本発明の方法を実行するためにコンピュータによって可読であるコンピュータプログラムを企図する。本発明はさらに、本発明の方法を実行するために機械によって実行可能な命令のプログラムを具体的に具現する機械可読メモリを企図する。
【図２ａ】
2009545052.tif 000009
【図２ｂ】
2009545052.tif 000010
【図１４】
2009545052.tif 000011
【図１】
2009545052.tif 000012
【図３】
2009545052.tif 000013
【図４】
2009545052.tif 000014
【図５】
2009545052.tif 000015
【図６】
2009545052.tif 000016
【図７】
2009545052.tif 000017
【図８】
2009545052.tif 000018
【図９】
2009545052.tif 000019
【図１０】
2009545052.tif 000020
【図１１】
2009545052.tif 000021
【図１２】
2009545052.tif 000022
【図１３】
2009545052.tif 000023
【図１５】
2009545052.tif 000024
【図１６】
2009545052.tif 000025
【国際調査報告】
2009545052.tif 000026