(57)【特許請求の範囲】
【請求項１】
メッセージの受け渡しを使用して調整された画像を生成するための、コンピュータにより実施される方法であって、前記方法が、
ｉ）複数の画素を備える入力画像を受信するステップと、各画素は入力値を有し、各入力値はいくつかの候補画素ラベルのうちの１つに対応する、
ｉｉ）各画素をグラフのあるノードおよびノードの１つまたは複数のクリークと関連付けるステップと、
ここにおいて、各候補画素ラベルは単項ポテンシャルと関連付けられ、各クリークの前記ノードと関連付けられる前記画素の候補画素ラベルの各順列について、クリークポテンシャルが関連付けられる、
ｉｉｉ）各クリークについて、そのクリークのノードの各ペアの間の少なくとも１つのメッセージを初期化するステップと、
ｉｖ）各ノードについて、
ａ）そのノードについて、前記単項ポテンシャルが知られている、候補画素ラベルのそれぞれの集合を決定するステップ、
ｂ）前記単項ポテンシャルが知られていない、選択された候補画素ラベルの単項ポテンシャルを計算し、前記選択された候補画素ラベルを含むように候補画素ラベルの前記それぞれの集合を更新するステップ、
ｃ）そのノードが属する各クリークについて、候補画素ラベルの前記更新されたそれぞれの集合と関連付けられる前記単項ポテンシャルに基づいて、そのクリークと関連付けられる前記クリークポテンシャルを調整するステップ、および
ｄ）そのノードが属する各クリークについて、そのクリークと関連付けられる前記調整されたクリークポテンシャルに基づいて、そのノードとそのクリークの他のノードとの間の前記メッセージの少なくとも１つを調整するステップと、
ｖ）収束基準が満たされるまでステップｉｖ）を繰り返すステップと、
ｖｉ）前記調整されたメッセージから決定される画素ラベルを有する調整された画像を生成するステップと、
を実行することを備える、方法。
【請求項２】
ステップｉｖ）がさらに、ステップａ）の後で、およびステップｃ）の前に、候補画素ラベルの前記それぞれの集合を、前記候補画素ラベルのうちの１つを前記それぞれの集合から除去することによって更新することを備える、請求項１に記載の方法。
【請求項３】
そのノードが属する各クリークについて、そのノードとそのクリークの他のノードとの間で受け渡されるメッセージに関する関連するパラメータが存在し、前記パラメータが、そのノードに対する前記候補画素ラベルに依存し、候補画素ラベルの前記それぞれの集合から除去される前記候補画素ラベルのうちの前記１つが、前記関連するパラメータの合計が最大である、候補画素ラベルの前記それぞれの集合のうちの前記候補画素ラベルである、請求項２に記載の方法。
【請求項４】
ステップｃ）において、そのクリークと関連付けられる前記クリークポテンシャルを調整することが、候補画素ラベルの前記それぞれの集合と関連付けられる前記単項ポテンシャルの加重和に基づいて、前記クリークポテンシャルを調整することを備える、請求項１から３のいずれか一項に記載の方法。
【請求項５】
ステップｃ）において、そのクリークと関連付けられる前記クリークポテンシャルを調整することがさらに、候補画素ラベルの前記それぞれの集合に含まれない、各候補画素ラベルに対する前記加重和に定数値を加算することを備える、請求項４に記載の方法。
【請求項６】
ステップｂ）において、前記選択された候補画素ラベルが、候補画素ラベルの候補集合から選択され、候補画素ラベルの前記候補集合が、前記単項ポテンシャルが知られている、隣接ノードの候補画素ラベルの推定される集合に基づく、請求項１から５のいずれか一項に記載の方法。
【請求項７】
収束基準が満たされるまでステップｉｖ）を繰り返すことが、ステップｉｖ）を所定の回数繰り返すことを備える、請求項１から６のいずれか一項に記載の方法。
【請求項８】
収束基準が満たされるまでステップｉｖ）を繰り返すことが、ステップｉｖ）の繰り返しが前記メッセージを変更しなくなるまでステップｉｖ）を繰り返すことを備える、請求項１から６のいずれか一項に記載の方法。
【請求項９】
ステップｂ）において、選択された候補画素ラベルの単項ポテンシャルを計算することが、前記グラフ中の隣接ノードの候補画素ラベルと関連付けられる単項ポテンシャルに基づいて、前記選択された候補画素ラベルの単項ポテンシャルを推定することを備える、請求項１から８のいずれか一項に記載の方法。
【請求項１０】
ステップｄ）において、前記メッセージの少なくとも１つを調整することが、１つまたは複数の所定のメッセージの重みに従って前記メッセージの前記少なくとも１つを調整することを備える、請求項１から９のいずれか一項に記載の方法。
【請求項１１】
前記単項ポテンシャルが、前記入力画像に対して、
セグメント化、
歪みの訂正、
オプティカルフロー、
高密度ステレオ対応、
画像のノイズ除去、ぼかし除去、および拡大
という動作の１つまたは複数を前記方法に実行させるように構成される、請求項１から１０のいずれか一項に記載の方法。
【請求項１２】
前記クリークポテンシャルが、前記入力画像に対して、
セグメント化、
歪みの訂正、
オプティカルフロー、
高密度ステレオ対応、
画像のノイズ除去、ぼかし除去、および拡大
という動作の１つまたは複数を前記方法に実行させるように最初に構成される、請求項１から１１のいずれか一項に記載の方法。
【請求項１３】
請求項１から１２のいずれか一項に記載の方法を実行するようになされる、装置またはシステム。
【請求項１４】
前記装置またはシステムが、
画像を受信するようになされる入力／出力手段と、
請求項１から１２のいずれか一項に記載の方法のステップをプロセッサに実行させるための命令を記憶するメモリと、
請求項１から１２のいずれか一項に記載の方法のステップを実行するためのプロセッサと、
を備える、請求項１３に記載の装置またはシステム。
【請求項１５】
１つまたは複数のプロセッサによって実行されると、請求項１から１２のいずれか一項に記載の方法を前記１つまたは複数のプロセッサに行わせるようになされる機械可読命令を備える、非一時的コンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は画像処理に関する。具体的には、限定はされないが、本開示は、メッセージの受け渡しを使用して画像を調整する方法に関する。
【背景技術】
【０００２】
コンピュータビジョンおよび画像処理システムが複雑になるにつれて、この複雑さにうまく対処することを可能にするような方法でモデルを構築することが、ますます重要になっている。
【０００３】
グラフィカルモデルにおける、特に、複数の画像領域にまたがって定義されるランダムなフィールドにおける最大事後確率（ＭＡＰ）の推測は、コンピュータビジョンおよび関連する分野において最も有用な道具の１つである。目的関数（objective）を定義するすべてのポテンシャルにパラメトリック形状という性質がある場合、いくつかのケースでは、非線形の最適化が最良の効率のために選択すべき方法である。一方、ポテンシャルにパラメトリックな形状という性質がない場合、ループ性の確率伝搬法（ＢＰ）またはその凸の変形が選択すべき方法である。ＢＰおよび関連するアルゴリズムは、状態空間が大きい場合に２つの制約に直面する。第１に、本来のメッセージ受け渡しステップは、状態空間サイズに関して少なくとも線形な時間を必要とし、一般に線形を超える。したがって、これらの方法のランタイムは、状態空間サイズに対して良好にスケーリングしない。第２に、状態空間サイズに対してメモリ消費が線形に増大するので、確率伝搬法は各状態のためのメッセージの管理を必要とする。
【０００４】
状態空間が大きい場合、明示的列挙による非パラメトリックな単項ポテンシャル（unary potential）（通常はデータ項と呼ばれる）を最適化することですら、多くの用途では（たとえば、組込みデバイス上で実装されるとき）計算的に負荷が高すぎることがある。いくつかのデータ項は積分画像（integral images）または累積和を介したより効率的な計算を可能にし、データ項は最大の精度で計算される必要はないことがあるが、これらの方法は非常に特殊な問題の事例にしか適していない。
【０００５】
本発明は、画像を調整するための改善された方法とシステムとを提供しようとするものである。
【発明の概要】
【０００６】
本発明の態様および特徴は、添付の特許請求の範囲において提示される。
【０００７】
本開示の例示的な実施形態が、図面を参照して、単なる例としてここで説明される。
【図面の簡単な説明】
【０００８】
【図１】例示的な装置またはデバイスのアーキテクチャを示す図。
【図２Ａ】４つのノードを備える例示的なグラフを示す図。
【図２Ｂ】４つのノードを備える例示的なグラフを示す図。
【図２Ｃ】４つのノードを備える例示的なグラフを示す図。
【図３】高密度ステレオ対応問題のための画像の受け渡しの数に関する双対のエネルギーの展開を示す図。
【図４Ａ】収束した視差マップを示す図。
【図４Ｂ】収束した視差マップを示す図。
【図５】本明細書で開示される方法による、異なる巡回スケジュールと重みとを使用してある画像にわたる受け渡しの数に関する主エネルギーの展開を示すグラフィカルプロット。
【図６】画像を調整する方法を示すフローチャート。
【図７】図６のプロセスと統合され得る任意選択のプロセスを示すフローチャート。
【図８】ウォールタイムに関する高密度視差推定のための主エネルギーの展開を図示するグラフィカルプロットを示す図。
【図９】収束しつつあるステレオ結果の視覚的な図解。
【図１０】高密度オプティカルフローに対する主エネルギーの展開を示す図。
【図１１】「ヤドリフカノキ」データセットに対するオプティカルフローフィールドの収束の視覚的な図解。
【図１２】様々なデータセットに対する収束しつつあるオプティカルフローフィールドの視覚的な図解。
【発明を実施するための形態】
【０００９】
説明および図面全体において、同様の参照番号は同様の部分を指す。
【００１０】
メッセージの受け渡しを使用して画像を調整するための方法は、画像の各画素をグラフのあるノードおよびノードの１つまたは複数のクリークと関連付けることと、単項ポテンシャルが知られている、候補画素ラベルのそれぞれの集合をグラフのあるノードに対して決定することと、単項ポテンシャルが知られていない、候補画素ラベルの単項ポテンシャルをそのノードに対して計算することと、単項ポテンシャルに基づいて、そのノードが属する各クリークと関連付けられるクリークポテンシャルを調整することと、そのノードが属する各クリークと関連付けられる調整されたクリークポテンシャルに基づいて、そのノードと各クリークの他のノードとの間のメッセージの少なくとも１つを調整することとを備える。収束基準が満たされると、調整されたメッセージから決定される画素ラベルを有する調整された画像が生成される。
【００１１】
メッセージの受け渡しを使用して調整された画像を生成するための、コンピュータで実施される方法が提供される。この方法は、複数の画素を備える入力画像を受信することを備える。各画素は入力値を有し、各入力値はいくつかの候補画素ラベルのうちの１つに対応する。方法はさらに、各画素をグラフのあるノードおよびノードの１つまたは複数のクリークと関連付けることを備える。各候補画素ラベルは単項ポテンシャルに関連し、各クリークのノードと関連付けられる画素の候補画素ラベルの各順列について、クリークポテンシャルが関連付けられる。方法はさらに、各クリークに対して、そのクリークのノードの各ペアの間の少なくとも１つのメッセージを初期化することを備える。
【００１２】
方法はさらに、各ノードについて、ａ）そのノードについて、単項ポテンシャルが知られている、候補画素ラベルのそれぞれの集合を決定することと、ｂ）単項ポテンシャルが知られていない、選択された候補画素ラベルの単項ポテンシャルを計算し、選択された候補画素ラベルを含むように候補画素ラベルのそれぞれの集合を更新することと、ｃ）そのノードが属する各クリークについて、候補画素ラベルの更新されたそれぞれの集合と関連付けられる単項ポテンシャルに基づいて、そのクリークと関連付けられるクリークポテンシャルを調整することと、ｄ）そのノードが属する各クリークについて、そのクリークと関連付けられる調整されたクリークポテンシャルに基づいて、そのノードとそのクリークの他のノードとの間のメッセージの少なくとも１つを調整することとを備える。各ノードについて、収束基準が満たされるまで、ステップａ）〜ｄ）が繰り返される。
【００１３】
方法はさらに、調整されたメッセージから決定される画素ラベルを有する調整された画像を生成することを備える。
【００１４】
単項ポテンシャルはペアから実数値への写像であり、このペアは画素とその画素についてのラベルとを備える。この写像または関数は、関心のある画素の近くの画像値に基づき得る。単項ポテンシャルは、画素ラベルまたは状態または値を画素（ノード）に割り当てることと関連付けられるコストと考えられ得る。クリークのクリークポテンシャルは、１つまたは複数の画素ラベルをそのクリークのノードに割り当てることと関連付けられるコストである。したがって、画像処理の最適化問題において、単項ポテンシャルおよびクリークポテンシャルは、その問題の解が最適な解にどれだけ近いかの尺度として働き得る。したがって、単項ポテンシャルとクリークポテンシャルの最小の和、すなわち、コストが最小となる、画素への画素ラベルの割当てを見つけることによって、最適な解を見つけることを試みることができる。
【００１５】
単項ポテンシャルは、解決されるべき画像処理問題に基づいて定義され得る。たとえば、いくつかの環境では、単項ポテンシャルはすべて、それぞれの候補画素ラベルについて定数値を備え得る。他の環境では、単項ポテンシャルは、多項式の関数によって定義され得る。任意の適切な単項ポテンシャルが使用され得、例は以下の例から明らかになるであろう。
【００１６】
画素ラベルが視差ベクトルまたはフローベクトルを特定するために使用されることになるときなどの、いくつかの状況では、ある特定の画素についての単項ポテンシャルは、基準画像の中のその特定の画素を中心とする画素区画を、ラベル値だけシフトされたその特定の画素を中心とする第２の（「移動」）画像からの画素区画と比較する関数である。
【００１７】
画素ラベルがオブジェクトの分類を特定するために使用されることになるときなどの、いくつかの状況では、単項ポテンシャルは、特定の画素を中心とする画像区画とオブジェクトの分類とを引数として有する関数である。したがって、単項ポテンシャルは、画素をオブジェクトの分類に割り当てることと関連付けられるコストを表す。この関数は、たとえば、機械学習技法を使用して事前に訓練され得る。
【００１８】
本明細書で開示される方法は、オブジェクトのセグメント化、歪みの訂正、ぼかし、拡大などの画像処理動作を実行する、メモリ効率が高く高速な方法を例証する。ステップａ）からｄ）の各繰り返しにおいて、選択された候補画素ラベルについての単項ポテンシャルを計算することによって、この方法が画像処理問題に対する解について収束するようにするために、必ずしもすべての単項ポテンシャルが計算される必要はない。したがって、この方法は、高いレベルの精度を維持しながら、画像処理問題に対する解について収束することを可能にするためにより少量のメモリしか必要としない。
【００１９】
方法はさらに、ステップａ）の後で、およびステップｃ）の前に、候補画素ラベルのそれぞれの集合を、候補画素ラベルのうちの１つを候補画素ラベルのそれぞれの集合から除去することによって更新することを備え得る。任意選択で、ノードが属する各クリークについて、方法は、そのノードとそのクリークの他のノードとの間で受け渡されるメッセージに関する関連するパラメータを使用する。このパラメータは、そのノードに対する候補画素ラベルに依存し得る。候補画素ラベルのそれぞれの集合から除去される候補画素ラベルのうちの１つは、関連するパラメータの合計が最大である、候補画素ラベルのそれぞれの集合のうちの候補画素ラベルであり得る。
【００２０】
ステップｃ）において、そのクリークと関連付けられるクリークポテンシャルを調整することは、候補画素ラベルのそれぞれの集合と関連付けられる単項ポテンシャルの加重和に基づいて、クリークポテンシャルを調整することを備え得る。この重み付けは、均等または不均等な重み付けであり得る。そのクリークと関連付けられるクリークポテンシャルを調整することはさらに、候補画素ラベルのそれぞれの集合に含まれない、各候補画素ラベルに対する加重和に定数値を加算することを備え得る。
【００２１】
ステップｂ）において、選択される候補画素ラベルは、候補画素ラベルの候補集合から選択され得る。候補画素ラベルの候補集合は、単項ポテンシャルが知られている、隣接ノードの候補画素ラベルの推定される集合に基づき得る。
【００２２】
収束基準が満たされるまで各ノードに対してステップａ）〜ｄ）を繰り返すことは、所定の回数ステップａ）〜ｄ）を繰り返すことを備え得る。収束基準が満たされるまで各ノードに対してステップａ）〜ｄ）を繰り返すことは、繰り返しがメッセージを変更しなくなるまでステップａ）〜ｄ）を繰り返すことを備え得る。
【００２３】
ステップｂ）において、選択された候補画素ラベルの単項ポテンシャルを計算することは、グラフ中の隣接ノードの候補画素ラベルと関連付けられる単項ポテンシャルに基づいて、選択された候補画素ラベルの単項ポテンシャルを推定することを備え得る。たとえば、隣接ノードの候補画素ラベルが特定の単項ポテンシャル（たとえば、１などの定数値）と関連付けられる場合、選択された候補画素ラベルの単項ポテンシャルを計算することは、特定の単項ポテンシャル（定数値）を選択された候補画素ラベルに割り当てることを備え得る。そのような割当ては、たとえば、２つの隣接ピクセルが画像において示される同じ面と関連付けられることを示すことによって、隣接ノードが同じ値をとる可能性が高いことを示し得る。
【００２４】
ステップｄ）において、メッセージの少なくとも１つを調整することは、１つまたは複数の所定のメッセージの重みに従ってメッセージの少なくとも１つを調整することを備え得る。たとえば、メッセージは均等に重み付けられ得る。メッセージは不均等に重み付けられ得る。
【００２５】
単項ポテンシャルは、入力画像に対するセグメント化動作を方法に実行させるように構成され得る。単項ポテンシャルは、入力画像に対する歪み訂正動作を方法に実行させるように構成され得る。単項ポテンシャルは、入力画像に対するオプティカルフロー動作を方法に実行させるように構成され得る。単項ポテンシャルは、入力画像に対する高密度ステレオ対応動作（dense stereo correspondence operation）を方法に実行させるように構成され得る。単項ポテンシャルは、入力画像に対するノイズ除去動作を方法に実行させるように構成され得る。単項ポテンシャルは、入力画像に対するぼかし除去および／または拡大動作を方法に実行させるように構成され得る。さらに、クリークポテンシャルは、入力画像に対する前記動作の１つまたは複数を方法に実行させるように最初に構成され得る。
【００２６】
装置またはシステムが提供され、この装置またはシステムは本明細書で開示されるような方法を実行するようになされる。装置またはシステムは、画像を受信するようになされる入力／出力手段を備え得る。装置またはシステムは、本明細書で開示されるような方法のステップをプロセッサに実行させるための命令を記憶するメモリを備え得る。装置またはシステムは、本明細書で開示されるような方法のステップを実行するためのプロセッサを備え得る。
【００２７】
非一時的コンピュータ可読媒体が提供される。このコンピュータ可読媒体は、１つまたは複数のプロセッサによって実行されると、本明細書で開示されるような方法を１つまたは複数のプロセッサに行わせるようになされる機械可読命令を備える。
【００２８】
さらなる任意選択の特徴が、以下の説明から理解されるであろう。
【００２９】
図１は、本明細書で説明される方法を実行するための例示的な装置またはデバイス１００のアーキテクチャを示す。装置またはデバイス１００は、プロセッサ１１０と、メモリ１１５と、ディスプレイ１３５とを備える。これらは任意選択の中央バス構造に接続され、ディスプレイ１３５はディスプレイアダプタ１３０を介して接続される。例示的な装置またはデバイス１００はまた、入力デバイス１２５（マウスおよび／またはキーボードなど）と、装置またはデバイスを他の装置、デバイス、またはネットワークに接続するための通信アダプタ１０５とを備える。入力デバイス１２５および通信アダプタ１０５は中央バス構造にも接続され、入力デバイス１２５は入力デバイスアダプタ１２０を介して接続される。例示的な装置またはデバイス１００はまた、出力デバイス１４５（補助的なディスプレイデバイスおよび／またはサウンドシステムなど）を備える。出力デバイス１４５は、出力デバイスアダプタ１４０を介して中央バス構造に接続される。
【００３０】
動作において、プロセッサ１１０はメモリ１１５に記憶されているコンピュータ実行可能命令を実行することができ、処理の結果はディスプレイ１３５上でユーザに表示され得る。コンピュータの動作を制御するためのユーザ入力は、入力デバイス１２５を介して受信され得る。処理の少なくとも一部の結果も、出力デバイス１４５を介して出力され得る。
【００３１】
ＭＡＰ推測およびグラフィカルモデル
コンピュータビジョンシステムを作成する最初のステップの１つは、最終的な解を計算するために使用される全体的な計算の模範を確立することである。ある解決法を実装するための最も柔軟な方法の１つは、エネルギー関数と最大事後確率（ＭＡＰ）推測との組合せを通じたものである。
【００３２】
ＭＡＰ推測戦略は、条件付き確率分布ｐ（Ｘ｜Ｙ）の定義で始まり、ここで、Ｘは観測結果Ｙから推定されるランダムな変数のベクトルである。ＭＡＰ推測において、実際の推定値Ｘ*は、ｐ（Ｘ｜Ｙ）を最大にするベクトルＸ*を見つけることによって見出される。
【００３３】
エネルギー関数との関連は、ギブス分布としてｐ（Ｘ｜Ｙ）を表現することによって理解されることが可能である。
【数１】
0006448680.tif 000002
ただし、Ｅ（ＸC；Ｙ）はＸの要素の集合ＸCにわたるエネルギー関数を示す。
【００３４】
したがって、指数部の総和は、Ｘの要素の異なる集合にわたる和である。以下で論じられるように、これらの集合の構造は使用されるモデルの特性である。
【００３５】
定数Ｚは、ｐ（Ｘ｜Ｙ）が有効な確率分布であることを確実にする正規化定数であるので、通常はＸ*を見出すのに重要ではない。したがって、ＭＡＰ推測を実行するには、以下のエネルギー関数を最大にするベクトルＸ*を見つけなければならないことが理解され得る。
【数２】
0006448680.tif 000003
【００３６】
画像調整のためのＭＡＰ推測における次のステップは、分布ｐ（Ｘ｜Ｙ）の形式が何であるかを決めることであり、これはグラフィカルモデルを使用するのに有用である。
【００３７】
グラフｇは集合のペアによって定義され、すなわちｇ＝（ν，ε）であり、ノードまたは頂点ｓは頂点の集合νに属し、エッジｅはエッジの集合εに属する。受信された画像の各画素は、グラフ上のノードまたは頂点として表され得る。受信された画像の異なる画素間の関係は、グラフ上のノード間のエッジによって表され得る。
【００３８】
たとえば、ベクトルＸが４画素を備える画像を表し、各画素が２５６個の値またはラベルのうちの１つをとることが可能であると仮定する。ｐ（Ｘ）だけを規定し、観測結果を記述するベクトルＹを無視するとすれば、画素間のあらゆる可能性のある繰り返しを考慮するには、２５６4個のラベルを決定する必要がある。これは図２Ａに示されており、図２Ａは、各ノードが受信された画像の画素を表す、４ノードを備えるグラフを示す。このグラフにおいて、ノードＡはノードＢの隣に位置しており、ノードＣはノードＤの隣に位置している。ノードＡおよびＢはそれぞれ、ノードＣおよびＤの上に位置している。図２Ａのグラフにはエッジがないので、画素間の相互関係は考慮されておらず、またはモデル化されていない。
【００３９】
代わりに、ノード間の相互作用、たとえば水平方向の隣接ノードと垂直方向の隣接ノードとの間の相互作用の一部をモデル化するとすれば、必要とされるラベルの数は減らされる。図２Ｂでは、ノードのペアＡとＢ、ＡとＣ、ＣとＤ、およびＢとＤの間の相互作用がモデル化されるので、４×２５６2個のラベルだけが分布を規定するために考慮される必要がある。必要とされるラベルのこの減少は、対角方向の隣接ノード間の関係が水平方向の隣接ノードおよび垂直方向の隣接ノードによって間接的に得られるという事実によるものである。たとえば、ＢとＣの間の相互作用は規定されない（図２Ｂのグラフ上にはノードＢとＣの間にエッジがない）が、ＢとＣの間の相互作用は、ノードのペアＡとＣおよびＡとＢの間の相互作用、ならびにノードのペアＣとＤおよびＢとＤの間の相互作用を介して、間接的に得られる。
【００４０】
図２Ｃは、４つの画素Ａ、Ｂ、Ｃ、およびＤの別のグラフを示し、図２Ｃではすべてのノード間の相互作用がエッジによって明示的にモデル化されている。図２Ｃのモデルは、図２Ｂのモデルよりも記述的である。
【００４１】
クリークは、完全に接続されているグラフのノード（頂点）の部分集合であり、すなわち、クリークのあらゆる別個のノードがクリークのあらゆる他の別個のノードに隣接している。たとえば、図２Ｂでは、ノードＡとＢが隣接しているので、ノードＡはノードＡとＢとを備えるクリークに属している。ノードＡとノードＣが隣接しているので、ノードＡはノードＡとＣとを備えるクリークにも属している。しかしながら、図２Ｂでは、ノードＡとＤが隣接していない、すなわちエッジによって接続されていないので、ノードＡとＤとを備えるクリークはない。
【００４２】
図２Ｃでは、ノードＡはノードＡとＢとを備えるクリークに属し、クリークはノードＡとＣとを備える。しかしながら、図２Ｃでは、ノードＡとＤが隣接している（ノードＡとＤを接続するエッジがある）ので、ノードＡはノードＡとＤとを備えるクリークにも属している。加えて、ノードＡは、ノードＡとＢとＣとを備えるクリーク、ノードＡとＢとＤとを備えるクリーク、ノードＡとＣとＤとを備えるクリーク、およびノードＡとＢとＣとＤとを備えるクリークに属している。
【００４３】
クリークは、ノード間の直接的な相互作用を緩やかに捉える。たとえば、図２ＢのノードＡが特定の値またはラベルを割り当てられる場合、そのような割当てはノードＢおよびノードＣに対して直接の影響がある。したがって、クリークは、コンピュータビジョンの問題をモデル化するために使用されるモデルに関係がある。
【００４４】
上記を考慮すると、ラベリングまたはＭＡＰ推測の問題は、各ノードｓ∈νにおいて割り当てられる最適なラベルｘs∈Ｌsを決定することであり、ここで、目的関数は単項とクリーク項に関するものである（クリークはギリシャ文字αなどによってインデックス付けされている）。
【数３】
0006448680.tif 000004
ここで、
【数４】
0006448680.tif 000005
であり、ｘαはクリークに属するノードにおいて割り当てられるラベルを備えるｘの部分ベクトルであり、ｘα＝（ｘs）s∈αである。
【００４５】
記号θs（ｘs）は、ラベルｘsをノードｓに割り当てることと関連付けられる単項ポテンシャル、すなわちコストを表す。言い換えると、ポテンシャルθs（ｘs）は、ラベル、または状態ｘsをノードｓに割り当てることと関連付けられる「エネルギー」である。記号θα（ｘα）は、特定のラベル、または状態をクリークαのノードに割り当てることと関連付けられる、クリークポテンシャル、すなわちコストを表す。言い換えると、ポテンシャルθα（ｘα）は、ラベルをクリークαのノードに割り当てることと関連付けられる「エネルギー」であり、ノード間の相互作用と関連付けられるエネルギー項であると考えられ得る。
【００４６】
（式１）のラベル割当て問題は、一般に解くのが難しく、この問題を近似的に解くための１つの大いに成功している方法は、対応する線形計画（ＬＰ）緩和を利用することである。
【数５】
0006448680.tif 000006
ただし、ＥMAP（ｂ）は最小にされるべきエネルギー関数である。（式２）において、ｂα（ｘα）≧０である。表現ｘα＼ｘsは
【数６】
0006448680.tif 000007
の簡略形である。以下では、｛α：ｓ∈α｝の代わりにα∋ｓと書かれる。未知数｛ｂs｝s∈vおよび｛ｂα｝αは、割り当たられたラベルの「ワンホット」の符号化であり、たとえば、ｂ*がＥMAPの最適解であり緩和が厳しい場合、状態ｘsがノードｓにおける最適なラベルである場合にだけ、ｂs（ｘs）は理想的には１であり、それ以外の場合は０である（クリーク状態ｘαに対するものと同様）。制約の第１の集合は通常、周辺化制約の集合と呼ばれ、総計が１となるような制約は通常、正規化制約と呼ばれる。（式２）の線形計画は一意ではなく、それは、冗長な非負性および正規化制約が、最適な解または値に影響を与えることなくＥMAPに追加され得るからである。結果として、文字通り異なる双対の解が得られる。残りにおいて使用される、ＥMAPの特定のＬＰ双対は、
【数７】
0006448680.tif 000008
によって与えられる。
【００４７】
制約の第１の集合はバランス制約と呼ばれ、制約の第２の集合は容量制約と呼ばれる。未知数（ρs）s∈νは補助的な変数の役割を果たすだけであるので、表記を簡単にするために引数として
【数８】
0006448680.tif 000009
へと省略される。一般性を失うことなく、λ≡０が双対実行可能であるように、θ≧０（点ごとに）であることが必要である。
【００４８】
（式３）が凸問題（線形計画）であるとしても、
【数９】
0006448680.tif 000010
を最適化することは単純ではない。汎用的なＬＰコードは、その問題の非常に特殊な構造を利用せず、一次の方法は、なめらかではない目的関数が原因で、実際には収束が遅い。
【００４９】
【数１０】
0006448680.tif 000011
を近似的に解くためのアルゴリズムの成功したクラスは、ブロック座標上昇法（block coordinate ascent）に基づき、これは、未知数の小さな、しかし可変の部分集合にわたって、繰り返し最適化を実行する。双対エネルギーおよび最適化された未知数の部分集合の異なる選択によって、異なるアルゴリズムが得られる。これらのアルゴリズムの成功のための１つの重要な側面は、部分問題がたとえば閉形式で効率的に解かれ得るということである。これらのアルゴリズムは通常、古典的な確率伝搬アルゴリズム（環状グラフ上で実行される場合にはほとんど保証がない）に似ており、包括的な用語である凸確率伝搬法（convex belief propagation）に該当する。これらのアルゴリズムには共通して、双対の目的関数が各々の繰り返しにおいて単調に改善するという性質があり、このことは（
【数１１】
0006448680.tif 000012
の最適値が有限である、すなわち問題が有界であるという穏当な仮定のもとで）アルゴリズムを収束性のものにする。
【００５０】
双対座標上昇法
このセクションでは、各ステップにおいてｓを含むすべてのクリークα（すなわち、ノードｓに入ってくるすべてのメッセージ）に対して、すべての変数λα→sにわたって最適化する、凸確率伝搬アルゴリズムが提供される。このセクションで説明される凸確率伝搬法は、以下で例証されるように、本明細書で説明されるメッセージの受け渡しを使用して画像を調整する方法のいずれとも使用され得る。この凸確率伝搬アルゴリズムは、入ってくるメッセージと出ていくメッセージの両方にわたる最適化と等価であること、すなわち、ブロック座標上昇法が完全な星状の部分グラフ上で実行されることがさらに示される。さらに、ノード巡回スケジュールに応じて観測される性能に対してかなりの影響を有するアルゴリズムにおいて、追加の調整の重みがあることが示される。
【００５１】
ある特定のノードｓを考え、ρsおよび
【数１２】
0006448680.tif 000013
以外のすべての未知数を固定すると、（式３）によって誘導される部分問題は、
【数１３】
0006448680.tif 000014
として解釈される。
不等制約式の右側は、μα→s（ｘs）と定義される。
【数１４】
0006448680.tif 000015
Σα∋sｗα→s＝１となるように（しかしそうでなければ任意に選ばれる）非負の重みｗα→sが導入され、数学的仮説λα→s（ｘs）＝μα→s（ｘs）−ｗα→sδs（ｘs）が、（式４）と等価の問題を得るために、あるδs（ｘs）≧０に対して使用される。
【数１５】
0006448680.tif 000016
【００５２】
これらの重みの選択および収束率に対するその影響は、このセクションにおいて後で論じられる。δs（ｘs）≧０であるので、ρsに対する最大の許容される値は、
【数１６】
0006448680.tif 000017
によって与えられ、δs（ｘs）およびλα→sは続いて
【数１７】
0006448680.tif 000018
【数１８】
0006448680.tif 000019
によって与えられる。
【００５３】
補完的スラック性（complementary slackness）を介して、λが双対最適であるかどうかを確認することは容易であり、そうすると、νs（ｘs）＞ρsは、ＥMAPの主の解においてｂs（ｘs）＝０であることを示唆する。アルゴリズム１は、この凸ＢＰ法を要約したものである。
【数１９】
0006448680.tif 000020
【００５４】
重みｗα→sの選択の影響を論じる前に、以下のことが述べられる。
【００５５】
結果１．アルゴリズム１は、入ってくるメッセージλα→sと逆方向のメッセージλα→t、ｔ∈α＼ｓとの両方に関して双対座標上昇法を実行することと等価である。このことは、固定されたノードｓに対して、ｓを含むすべてのクリークαに対してメッセージλα→tが更新されることを意味する。
【００５６】
結果１の証明：ノードｓおよびその隣接ノードｔ（すなわち、ｓとクリークを共有するノード）に対して、λα→sとλα→tとを更新する。したがって、
【数２０】
0006448680.tif 000021
を最大にし、ただし
【数２１】
0006448680.tif 000022
は再パラメータ化された単項ポテンシャル
【数２２】
0006448680.tif 000023
である。目的関数を変更することなく（または制約を侵すことなく）、（すべてのｔ∈α＼ｓに対して）各ρtをρt−εtで置き換えることができ、ρsをρs＋Σtεtで置換する（λα→s←λα→s＋Σt∈α\sεtおよびλα→t←λα→t＋εtに設定する）ことができることに留意されたい。したがって、一般性を失うことなくρt＝０であり、
【数２３】
0006448680.tif 000024
と仮定することが可能である。これを最大化問題とつなぐことで、以下を得る。
【数２４】
0006448680.tif 000025
【００５７】
双対座標上昇法のこの変形は、入ってくるメッセージλα→sのみにわたる最適化よりも強力ではない。値をすべてのρtに任意に割り当てることは自由であるので、値ρtは定数のままに保たれることが可能であり、すなわち、ρtに関して最大にする必要はまったくない。この場合、λα→tはその古い値に固定され（これは
【数２５】
0006448680.tif 000026
の帰結である）、最大化はρsおよびλα→sだけに関して実行され、したがって両方のメッセージに関する最適化は、アルゴリズム１における元の方法と等価である。
【００５８】
アルゴリズム１のブロック座標法は、たとえば、木ブロック座標１よりも少数の未知数にわたる最適化を行い、最小和拡散またはＭＰＬＰよりも大きな未知数の集合を更新する。
【００５９】
安定点：（厳密にではなく）凸の（または凹の）問題に対して適用されるブロック座標法は、目的関数を単調に改善することだけが保証され、１つの最適解を固定点として得るとは限らないことを思い出されたい。固定点への収束は、単調性の帰結である。固定点についての推論は実際にはあまりにも制約的であり、それは、λが固定点に達するはるかに前から双対目的関数Σsρsが通常は一定になっているからである。したがって、固定点条件を緩和し、簡潔に安定点を導入する。別の軽微な複雑さは、双対目的値ν*＝Σsρsに対する寄与ρsの割当てが一意ではないという事実に起因する。すなわち、目的関数または有効な制約を変更することなく（すなわち、主の解を変更することなく）メッセージを調整することによって、ノード間の量を任意にシフトすることができる。幸運なことに、この曖昧さは、アルゴリズム１の各ノード更新ステップにおいて単一のノードに対するρsだけを更新することによって固定され（すなわち、隣接ノードｔにおけるρtを修正する自由が使用されない）、安定点を次のように定義することができる。
【００６０】
定義１．次の条件が満たされる場合、λは
【数２６】
0006448680.tif 000027
に対する安定点と呼ばれる。
【数２７】
0006448680.tif 000028
（（式５）のようなμα→s（ｘs）の定義を使用する）。
言い換えると、すべてのノードに対して、すべての容量制約が有効である状態が存在する場合、λは安定である。ある意味では、安定点はノード更新のための固定点である。
【００６１】
結果２．λが安定点である場合、（ノードのための任意の巡回スケジュールを伴って）アルゴリズム１を実行することは、双対目的関数
【数２８】
0006448680.tif 000029
を改善しない。
【００６２】
証明を概説する前に、有効状態という考え方が導入される。
【００６３】
定義２．ポテンシャルθおよびメッセージλが与えられるものとする。アルゴリズム１のような考え方を使用して、
【数２９】
0006448680.tif 000030
である場合、状態ｘsは有効であると呼ばれる。
【００６４】
ノードｓにおいて有効である状態ｘsは、ｓを含むクリークに対してすべての容量制約が有効であることを意味するので、Σt∈αλα→t（ｘt）＝θα（ｘα）である。ｗα→s＞０である場合、すなわち、単位単体の内部から重みが選ばれる場合、逆もまた真である。
【００６５】
結果２は次のように理解され得る。すなわち、ｓにおけるノード更新（アルゴリズム１）は、クリークα∋ｓに対する少なくとも１つの容量制約があらゆる以前に有効であった状態に対して無効になる場合、ρsの値だけを改善することができる。そうではない場合、ρs＝Σα∋sλα→s（ｘs）も一定のままであり、λα→s（ｘs）も有効状態に対して一定のままであることを理解するのは容易である。メッセージは無効状態に対しては変化し得る。
【００６６】
巡回スケジュールおよび重みの選択：ノードｓ∈νがどのような順序で巡回されるかというスケジューリングポリシーと、ｗα→sの厳密な選択は、アルゴリズムの未指定のパラメータである。直観的には、ノード巡回スケジュールおよび重みの異なる選択が、収束の速度について有益である可能性があり、それは、関連するメッセージ情報がスケジュールおよび利用される重みによってはより高速に伝搬され得るからである。前方の（ハイパー）エッジにより大きな重みｗα→sを割り当てる、不均等な重みの割当ては、後続のノードｔにおいて入ってくるメッセージがより大きな上限μα→tを有することを意味し、したがって、ノードｔにおける部分問題（式４）はより制約されない。図３では、高密度ステレオ対応問題（dense stereo correspondence problem）のための画像の受け渡しの数に関する双対エネルギーの展開が示されている。「Ｓｅｑ」はスケジュールを指し、このスケジュールでは、順次的な上から下への巡回と左から右への巡回（およびその反転）が交互に現れ、「ｐａｒ」は画像中のあらゆる他の画素を（場合によっては同時に）更新するスケジュールであり、「ｒｏｗ」は画像中のあらゆる他の行を同時に巡回しそれぞれの受け渡しの後でその方向を反転させる、行並列スケジュールを指す。均等な重みの割当てと不均等な重みの割当てに対する結果を示す。組合せ「ｓｅｑ／ｎｏｎ−ｕｎｉｆｏｒｍ」は、直列プロセッサ上で実行されれば、最速の収束速度を有する。ポリシー「ｒｏｗ／ｎｏｎ−ｕｎｉｆｏｒｍ」は並列実装に適しているので、このポリシーを実験において使用する。
【００６７】
「円錐群」データセットの高分解能ステレオペアが、図３のグラフを生成するために使用される。単項ポテンシャルはＮＣＣにより引き起こされるコスト
【数３０】
0006448680.tif 000031
であり、ただしτ＝０．５であり、ＮＣＣスコアは５×５のグレースケール区画上で計算される。ＺＮＣＣは、５×５のグレースケール画像区画の０平均のＮＣＣである。Ｐ1−Ｐ2平滑モデル（smoothness model）が使用される。「弱い正則化」の設定では、Ｐ１＝１／４、Ｐ２＝１が選ばれ、図４Ａは収束した結果を示す。強い正則化を得るために、Ｐ１＝１、Ｐ２＝４が選ばれ、図４（ｂ）は収束した結果を示す。
【００６８】
巡回スケジュールの意味は次の通りである。
【００６９】
・Ｓｅｑ：左上の画素から右下の画素（奇数番目の受け渡しの場合）への、およびその逆方向（偶数番目の受け渡しの場合）の、順次的な走査
・Ｒｏｗ：まず奇数行、次いで偶数行に対する、左から右への順次的な走査。方向は１回の受け渡しごとに右から左に反転される。
・Ｐａｒ：チェッカー柄において白の画素をまず更新し、次いで黒の画素を更新する。
【００７０】
重みは以下に従って割り当てられる。
・Ｕｎｉｆｏｒｍ  ｗｅｉｇｈｔｉｎｇ：すべてのｗα→sが１／ｄｅｇに設定される。
・Ｎｏｎ−ｕｎｉｆｏｒｍ  ｗｅｉｇｈｔｉｎｇ：ｗα→sが巡回スケジュールにおいて後方のエッジに対して１／３２に設定される。「ｓｅｑ」スケジュールでは、重みの総計が１になるように、前方のエッジは重みｗα→s＝１／２−εを有する。「ｒｏｗ」スケジュールでは、前の行と次の行の中の画素に対するエッジは重み１／４を有するので、前方のエッジは重み１−２×１／４−ε＝１／２−εを有する。
【００７１】
遅延評価（Lazy evaluation）および悲観的ポテンシャル
このセクションでは、ポテンシャルは各状態に対して事前に与えられず、必要に応じて計算される必要があると仮定される。１つの戦略は、まだ問い合わされていないポテンシャルに対して代理を利用して、推測を実行する間の後続の要求に対して有望であると考えられる状態を決定することである。したがって、推測手順において生じる再パラメータ化されたコストは、それぞれのポテンシャルの真の値の探索を支配し得る。問い合わされていないポテンシャル、すなわち「悲観的」ポテンシャルの上限を使用することは、この文脈では大いに有益であることが示される。
【００７２】
このセクションは、必要な背景を提供し、計算的に負荷の高い単項ポテンシャルの「遅延評価」に焦点を当てるが、推測アルゴリズムは、メッセージの完全な表現を維持する。次のセクションでは、クリークポテンシャルの遅延評価が圧縮されたメッセージ表現をどのように生むか、およびより効率的な推測をどのように可能にするかが説明される。
【００７３】
悲観的ポテンシャル：θを真の、しかし部分的にしか知られていないポテンシャルとし、悲観的な上限ポテンシャル
【数３１】
0006448680.tif 000032
（点ごとの）が利用可能である。定義により、
【数３２】
0006448680.tif 000033
を得る。
【００７４】
定義３．所与のポテンシャルθに対して、
【数３３】
0006448680.tif 000034
を、すべてのｓおよびｘsに対して
【数３４】
0006448680.tif 000035
となるようなθの再パラメータ化とする。一般性を失うことなく、
【数３５】
0006448680.tif 000036
と設定する。
【００７５】
【数３６】
0006448680.tif 000037
の安定点について推論する代わりに、
【数３７】
0006448680.tif 000038
を扱うのが有益であり、それは、ポテンシャル
【数３８】
0006448680.tif 000039
を修正することは、バランス条件には影響せず、容量制約だけに影響するからである。明瞭にするために、
【数３９】
0006448680.tif 000040
がここで再び記述される。
【００７６】
【数４０】
0006448680.tif 000041
この対応は、
【数４１】
0006448680.tif 000042
などの属性化されたポテンシャルに持ち越される。これらの再パラメータ化されたポテンシャルに対して、λが
【数４２】
0006448680.tif 000043
に対して実行可能である場合、それは
【数４３】
0006448680.tif 000044
に対しても実行可能であることが明らかである。以下のような興味深い疑問がある。
【００７７】
【数４４】
0006448680.tif 000045
に対する安定点λが
【数４５】
0006448680.tif 000046
に対しても安定点であるのはいつか？
【００７８】
結果３．λを
【数４６】
0006448680.tif 000047
に対する安定点とする。
【数４７】
0006448680.tif 000048
が
【数４８】
0006448680.tif 000049
に対して実行可能である場合、
【数４９】
0006448680.tif 000050
も
【数５０】
0006448680.tif 000051
に対する安定点である。
【００７９】
証明．
【数５１】
0006448680.tif 000052
に対する安定点とし、
【数５２】
0006448680.tif 000053
に対して実行可能であるものとする。ノードｓを固定する。
【数５３】
0006448680.tif 000054
に対して適用されるアルゴリズム１における必須の量は
【数５４】
0006448680.tif 000055
である。
【００８０】
【数５５】
0006448680.tif 000056
は
【数５６】
0006448680.tif 000057
に対する固定点であり、
【数５７】
0006448680.tif 000058
を得る。
【００８１】
ポテンシャル
【数５８】
0006448680.tif 000059
に関してｓにおいて今入来しているメッセージを更新することは、
【数５９】
0006448680.tif 000060
および
【数６０】
0006448680.tif 000061
の計算を必要とする。定義から、
【数６１】
0006448680.tif 000062
、
【数６２】
0006448680.tif 000063
、および
【数６３】
0006448680.tif 000064
である。しかし、λが
【数６４】
0006448680.tif 000065
に関して実行可能であるので、
【数６５】
0006448680.tif 000066
、すなわち
【数６６】
0006448680.tif 000067
であることが知られている。このことは、
【数６７】
0006448680.tif 000068
であり、したがって
【数６８】
0006448680.tif 000069
であることを示唆する。したがって、目的関数は、ｓにおいて入ってくるメッセージを更新することでは改善しない。さらに、有効状態
【数６９】
0006448680.tif 000070
に対して、
【数７０】
0006448680.tif 000071
であり（有効状態に対して容量制約が有効であるので）、これを
【数７１】
0006448680.tif 000072
および
【数７２】
0006448680.tif 000073
と組み合わせることで、
【数７３】
0006448680.tif 000074
を得る。
【００８２】
よって、有効状態に対してδs（ｘs）＝０であり、これらの状態に対する更新されたメッセージλα→s（ｘs）は
【数７４】
0006448680.tif 000075
によって与えられ、
【数７５】
0006448680.tif 000076
は
【数７６】
0006448680.tif 000077
に対する安定点である。
【００８３】
我々の環境におけるこの結果の関連性は次の通りである。真のポテンシャルに対する上限が与えられると、連続的なノード更新（またはより広い意味では利用）を介して、真の値のサンプリング（または探索）をＭＡＰ推測とインターリーブすることができ、ただしそれは、そのような探索と利用を組み合わせた戦略でも完全推測問題の安定点をもたらすという制約の範囲内で行われる。また、この結果は、現在のメッセージλが与えられた場合に、どの状態がそれぞれの真のポテンシャルを問い合わせるのに良好な候補であるのかを伝える。すなわち、そのような状態は、対応する容量制約を侵す可能性がより高い状態である。
【００８４】
単項ポテンシャルの遅延評価：通常の環境は、単項ポテンシャルが非パラメトリックでありデータ項を評価するには高コストであり、クリークポテンシャル（通常はペアごとの）がパラメトリックであり計算負荷が低いというものである。したがって、本実施形態では、後続のノード更新において使用される、目に見えないデータ項の「誘導される」評価につながる手法に関心が持たれる。
【００８５】
以下では、単項ポテンシャルに上限がある、たとえば、s,xsθs（ｘs）≦１であると仮定する。上限はｓに依存し得るが、簡単にするために、定数の上限を仮定する。未知のポテンシャルの上限と組み合わされた（単項）ポテンシャルの部分的な知識は、関連するＭＡＰ推測問題をもたらす。
【００８６】
定義４．各ｓ∈νに対して、Ｌ（ｓ）を、真の単項ポテンシャルが知られている常駐状態（resident state）の集合であるとし、
【数７７】
0006448680.tif 000078
は
【数７８】
0006448680.tif 000079
のように構築され、
【数７９】
0006448680.tif 000080
である。
【００８７】
【数８０】
0006448680.tif 000081
に対して、消滅する単項ポテンシャルについて対応する再パラメータ化されたポテンシャル
【数８１】
0006448680.tif 000082
があることに留意されたい（定義３を思い出されたい）。これらの定義により、アルゴリズム２のデータ項の遅延評価を用いて、ＭＡＰ推測のためのメタアルゴリズムを提示することが可能である。
【数８２】
0006448680.tif 000083
【００８８】
ノード巡回スケジュールおよび重みｗα→sの選択について、アルゴリズム１の場合と同じ注釈が当てはまる。極限Ｔ→∞において、アルゴリズムにおけるあらゆる状態が探索され、完全ＭＡＰ推測問題に対する安定点が得られる。アルゴリズムはまた、違反状態がノードのいずれにおいても見つからない場合、より早く停止し得る。最も関連のある適用形態は、Ｔがたとえばランタイムの枠を満たすような定数値であるときである。このことは、θs（ｘs）をインスタンス化することがその後の目的関数の最大の低下をもたらすような状態ｘsをどのように見つけるべきかという、アルゴリズムにおける主要な未決定の設計選択をもたらす。原理を説明するために、ここでは画素ｓにおいてすべての状態が考慮されると仮定する。実際には、候補状態の小さな集合を生成するために隣接する画素が利用され、これは以下の「限られたメモリのＰＭ−ＣＢＰ」と題されるセクションにおいて説明される。単項ポテンシャルが計算されるべき、選択された候補画素ラベル
【数８３】
0006448680.tif 000084
はしたがって、候補画素ラベルの候補集合から選択されてよく、候補画素ラベルの候補集合は、単項ポテンシャルが知られている、隣接ノードの候補画素ラベルの推定される集合に基づく。この例では、単項ポテンシャルを評価すべき状態
【数８４】
0006448680.tif 000085
は、未知数θs（ｘs）の代わりに推定されるコスト
【数８５】
0006448680.tif 000086
を使用することによって、νs（ｘs）の最小値を伴う状態として決定され、すなわち、
【数８６】
0006448680.tif 000087
は
【数８７】
0006448680.tif 000088
に設定され、ただし、
【数８８】
0006448680.tif 000089
は、
【数８９】
0006448680.tif 000090
から、
【数９０】
0006448680.tif 000091
を
【数９１】
0006448680.tif 000092
で置換することによって得られる。
【００８９】
【数９２】
0006448680.tif 000093
は、真のデータ項θs（ｘs）、または結果３に対して維持すべきその下限であるべきことに留意されたい。実際には、近隣からの最小の単項ポテンシャルを推定値として使用することが可能であり、すなわち
【数９３】
0006448680.tif 000094
であり、これは良好に機能するように見える。全体として、（式２０）に従って
【数９４】
0006448680.tif 000095
を決定することは、基本的に、アルゴリズム１の１ノード更新ステップを実行することに相当し、同じランタイムの複雑さを有する。
【００９０】
スケジュールおよび重みが標準的な凸ＢＰの収束速度に影響を与えることが上で示されたが、ＰＭ−ＣＢＰも、アルゴリズムが少数の受け渡しに対して実行される場合には特に有益である。図５は、「ｒｏｗ＋ｎｏｎ−ｕｎｉｆｏｒｍ」の環境が、均等な重みを使用するスケジュールよりもはるかに高速に、より低い主エネルギーを達成することを示している。
【００９１】
図６は、メッセージの受け渡しを使用して画像を調整するためのコンピュータで実施される方法を示すフローチャートである。方法は、たとえば、図１に関して上で説明されたアーキテクチャによって実行され得る。ステップ６１０において、入力画像が受信される。入力画像は複数の画素を備え、各画素は入力値を有し、各入力値はいくつかの候補画素ラベルまたは状態のうちの１つに対応する。
【００９２】
ステップ６１２において、入力画像の各画素が、グラフのあるノードおよびノードの１つまたは複数のクリークと関連付けられる。各候補画素ラベルは、単項ポテンシャルと関連付けられ、各クリークのノードと関連付けられる画素の候補画素ラベルの各順列に対して、クリークポテンシャルが関連付けられる。
【００９３】
ステップ６１４において、グラフの各クリークに対して、そのクリークのノードの各ペアの間の少なくとも１つのメッセージが初期化される。たとえば、上で説明されたアルゴリズム２のように、すべてのメッセージλが０に初期化される。
【００９４】
ステップ６１６において、ノードｓがノード巡回スケジューリングポリシーに従って選択される。たとえば、ノード巡回スケジューリングポリシーは、グラフのノードが毎回同じ順序で順次的に巡回されるべきであることを示し得る。
【００９５】
ステップ６１８において、そのノードについて、単項ポテンシャルが知られている、候補画素ラベルのそれぞれの集合が決定される。言い換えると、そのノードに対して、常駐状態Ｌ（ｓ）の集合が決定される。次いで、アレイ
【数９５】
0006448680.tif 000096
がそれに従って定義され得る（（式１９）参照）。
ステップ６２０において、状態
【数９６】
0006448680.tif 000097
が選択され、この状態
【数９７】
0006448680.tif 000098
は、単項ポテンシャルが知られている、候補画素ラベルのそれぞれの集合に属していない。上で説明されたように、状態
【数９８】
0006448680.tif 000099
は、推定されるコスト
【数９９】
0006448680.tif 000100
を使用することによるνs（ｘs）の最小の値を伴う状態の決定に基づいて選択され得る。
【００９６】
ステップ６２２において、選択された候補画素ラベルの単項ポテンシャルが計算される。
【００９７】
ステップ６２４において、単項ポテンシャルが知られている、候補画素ラベルのそれぞれの集合Ｌ（ｓ）が、選択された状態
【数１００】
0006448680.tif 000101
を含むように更新される。アレイ
【数１０１】
0006448680.tif 000102
がそれに従って更新され得る。
【００９８】
ステップ６２６において、ノードｓが属している各クリークについて、そのクリークと関連付けられるクリークポテンシャルが、候補画素ラベルＬ（ｓ）の更新されたそれぞれの集合に基づいて、調整または再パラメータ化される。たとえば、クリークポテンシャルは、（式１０）のように調整され、（式１０）は単項ポテンシャルが０に調整されることも示している。
【００９９】
ステップ６２８において、調整されたクリークポテンシャルを使用して、ノード更新がアルゴリズム１に従って実行される。このことには、ノードｓが属している各クリークについて、そのクリークと関連付けられる調整されたクリークポテンシャルに基づいて、ノードｓとそのクリークの他のノードとの間のメッセージの少なくとも１つを調整するという効果がある。
【０１００】
ステップ６３０において、収束基準が満たされたかどうかについての決定が行われる。収束基準が満たされていない場合、方法はステップ６３２に進み、そこで、ノード巡回スケジューリングポリシーに従って異なるノードが選択される。方法は次いでステップ６１８に戻る。収束基準は、たとえば、（式１１）の双対問題に対する解が発見されたということであり得る。収束基準は、たとえば、方法が所定の回数すべてのノードを巡回したということであり得る。
【０１０１】
ステップ６３０において、収束基準が満たされたかどうかを決定が行われ、次いで方法はステップ６３４に進み、調整されたメッセージから決定された画素ラベルを有する調整された画像が生成される。たとえば、収束基準が、（式１１）の双対問題に対する解が発見されたというものである場合、調整された画像は、その解を対応する主問題の解に変換し、それに従ってラベルを画素に割り当てることによって生成され得る。
【０１０２】
限られたメモリのＰＭ−ＣＢＰ
基本的なＰＭ−ＣＢＰアルゴリズムの主要な利益は、早期打切りが適用されるときにだけ明らかである。この場合、単項ポテンシャルの部分集合だけが評価され、最終的な凸ＢＰの繰り返しは、部分的に悲観的ポテンシャルを伴う代理ＭＡＰ事例（proxy MAP instance）の解へと収束する。ランタイムの節約は、すべてのデータ項を評価しないこと（これはかなりの節約につながり得る）に起因する。興味深いことに、それをさらに超えて、ＰＭ−ＣＢＰの限られたメモリのバージョンを導くことが可能であり、これは状態とそれぞれのメッセージの数を一定に保つ。このことは、（ｉ）クリークポテンシャルに対する代理の上限を使用することによって、単一の値によってあるノードにおける非常駐状態のためのすべてのメッセージを表すことが可能であるということ、および（ｉｉ）目的関数を低下させることなく少なくとも１つの常駐状態が非常駐にされ得るということの、２つの観測結果を使用して達成される。したがって、ノードごとに３つの常駐状態を維持するだけで十分である。この方法はアルゴリズム２（ここでは枠付きの命令を含む）において概説され、以下でより詳細に説明される。
【０１０３】
グループ状態“*”：基本的な概念は、目に見えない単項ポテンシャル（すなわち、非常駐状態に対する）の上限の使用をクリークポテンシャルに拡張することである。クリーク状態ｘαのいずれの要素も常駐しない（すなわち、Ｌ（ｓ）の中にない）場合、割り当てられるポテンシャル
【数１０２】
0006448680.tif 000103
は真の値の上限である。本明細書で説明される実験では、切り捨てられたペアごとのポテンシャルが使用されるので、上限は簡単に利用可能である。状態ｘsを常駐の集合に追加することは、
【数１０３】
0006448680.tif 000104
（真の値）を更新するだけではなく、ｘαが今、常駐状態だけからなる場合には、置換
【数１０４】
0006448680.tif 000105
にもつながり得る。非常駐状態を伴うあらゆる単項ポテンシャルおよびクリークポテンシャルはすべての状態
【数１０５】
0006448680.tif 000106
に対して一定であるので、このことは、ノード更新後のメッセージλα→s（ｘs）がすべての
【数１０６】
0006448680.tif 000107
に対して同じ値を達成することも示唆する。したがって、メッセージ
【数１０７】
0006448680.tif 000108
の集合は、λα→s（＊）によって示される、単一の値によって表され得る。グループ状態“*”は、すべての非常駐状態を同時に表す。したがって、すべての非常駐状態に対して単一のメッセージを導入することは、基本的なＰＭ−ＣＢＰアルゴリズムの有効性に影響しない。常駐集合Ｌ（ｓ）は、各受け渡しにおいて１つの要素ずつ増える。常駐集合を固定のサイズにするために、「最も有効ではない」状態
【数１０８】
0006448680.tif 000109
、すなわちνs（ｘs）の最大値を伴う状態ｘs∈Ｌ（ｓ）が廃棄される。すなわち、ノードｓが属する各クリークに対して、関連するパラメータμα→s（ｘs）があり、関連するパラメータはノードｓに対する候補画素ラベルに依存する。常駐集合Ｌ（ｓ）から除去される、候補画素ラベル
【数１０９】
0006448680.tif 000110
の１つは、パラメータμα→s（ｘs）の合計νs（ｘs）が最大である、候補画素ラベルである。したがって、Ｌ（ｓ）からの
【数１１０】
0006448680.tif 000111
の除去は目的関数を低下させない。
【０１０４】
【数１１１】
0006448680.tif 000112
の選択：Ｌ（ｓ）に追加すべき状態
【数１１２】
0006448680.tif 000113
は、前のセクションにおけるすべての非常駐状態にわたる走査によって決定された（（式２０）を思い出されたい）。常駐状態Ｌ（ｓ）の小さな集合を維持する場合、この網羅的な走査はランタイムの全体的な複雑さを支配し得る。したがって、近隣のノードｔにおける常駐状態に基づいてノードｓにおける可能性のある候補を生成するのが賢明である。（パラメトリックな）クリークポテンシャルは通常はなめらかさの仮定を符号化するので、密度ｐ（ｘs｜ｘα\s）∝ｅｘｐ（−θα（ｘα））を使用して状態をランダムにサンプリングするのが合理的である。ポテンシャルが較正されることを想定しないので、全体的なＭＡＰの解に影響しない局所的なバイアスの曖昧さ（クリークごとに１度の自由度）に加えて、大域的な規模での曖昧さがある。したがって、実際には、訓練データから分布パラメータを推定することが可能である。訓練データは、全面的な推測によって生成されるグラウンドトゥルース（ground truth）のラベリングまたはＭＡＰの解であり得る。ｓを含まない常駐クリーク状態の集合は
【数１１３】
0006448680.tif 000114
であり、これはランダムな提示集合（proposal set）の定義
【数１１４】
0006448680.tif 000115
を可能にし、Ｃ（ｓ）＝∪α∋sＣs（α）＼Ｌ（ｓ）である。Ｃ（ｓ）は、隣の常駐状態から生成されるランダムな提案の集合（ｓにおける既存の常駐状態を除く）である。最終的に、新たな常駐状態
【数１１５】
0006448680.tif 000116
は（式２０）に対する類推から決定される。
【０１０５】
【数１１６】
0006448680.tif 000117
推定されるコスト
【数１１７】
0006448680.tif 000118
が真のポテンシャル値またはそれぞれの下限であり、
【数１１８】
0006448680.tif 000119
が正の確率をそれぞれの状態に割り当てる結果、Ｔ→∞のときにしばしば、それぞれの状態ｘsがＣ（ｓ）の中に無限にある場合、限られたメモリのＰＭ−ＣＢＰは完全推測問題の安定点に到達する。これは、結果３と、現在のメッセージの実行可能性がしばしば無限に試験されるという事実とに起因する。このことはまた、３つの状態に対するメッセージ、すなわち、グループ状態*に対して１つのメッセージ、有効状態に対して１つのメッセージ、および
【数１１９】
0006448680.tif 000120
に対する１つのスロットを維持することで十分であることを示唆する。
【０１０６】
限られたメモリのＰＭ−ＣＢＰにおけるメッセージのデータ構造は、ただの固定サイズのアレイであり得る。
【０１０７】
【数１２０】
0006448680.tif 000121
に対するスロットは、
【数１２１】
0006448680.tif 000122
に対して再使用され得る。一般に、アルゴリズムは、固定サイズの事前に割り振られたデータ構造しか必要とせず、これはＧＰＵまたは組込み型の実装には大きな利点である。
【０１０８】
任意選択のサブプロセスがここで図７に関して説明され、これは図６に関して上で説明されたプロセス内で行われ得る。したがって、図７は、図６に関して上ですでに説明されており、同じ参照番号を適宜割り振られている、いくつかのステップを示している。
【０１０９】
候補画素ラベルのそれぞれの集合Ｌ（ｓ）がノードｓに対して決定されるステップ６１８の後で、方法はステップ７０２に進み、そこでＬ（ｓ）の状態
【数１２２】
0006448680.tif 000123
が選択される。上で説明されたように、状態
【数１２３】
0006448680.tif 000124
は、νs（ｘs）の最大値を伴う状態の決定に基づいて選択され得る。
【０１１０】
ステップ７０４において、候補画素ラベルＬ（ｓ）のそれぞれの集合が、その集合から候補画素ラベルのうちの１つを除去することによって更新される。したがって、上の（式１９）に関して、アレイ
【数１２４】
0006448680.tif 000125
において、既知の単項ポテンシャル
【数１２５】
0006448680.tif 000126
は１と置き換えられる。上で説明されたように、このことは、メッセージ
【数１２６】
0006448680.tif 000127
がグループ状態λα→s（＊）によって表されることを可能にする。
【０１１１】
ステップ７０４の後で、方法はステップ６２０に進み、そこで、単項ポテンシャルが知られていない状態
【数１２７】
0006448680.tif 000128
が選択され、方法は図６のように進行する。このようにして、常駐集合Ｌ（ｓ）は、ノードｓの各ノード更新（ステップ６２６）に対して一定のサイズのままである。
【０１１２】
適用
本明細書で説明される方法は、以下で説明されるような、いくつかの画像処理のタスクを実行するために使用され得る。具体的には、本明細書で説明される方法を実行することによって、（式２）の問題などの主問題に対する解、または近似的な解が、時間とメモリに関して効率的な方式で発見され得る。画像に対して実行される画像処理タスクは、問題を定義するために使用されるパラメータに依存する。
【０１１３】
高密度対応問題に対する本明細書で説明される方法の実行が例証される。一般的なパラメータは次の通りである。ＰＭ−ＣＢＰが、示された受け渡し回数Ｔに対して５つの常駐状態（すべての非常駐状態を表すにはもう１つ）を用いて実行され、それに続いて、メッセージを洗練するための３２回という固定された回数の凸ＢＰの繰り返しがある。ペアごとの項のために４つの近隣が使用されるので、メモリ消費は、画像解像度の浮動小数点値の６×４＝２４倍である。主の解は、最小限界費用νs（ｘs）が最小となる各画素に対する状態を単に報告することによって、抽出される。このアルゴリズムは、ＯｐｅｎＭＰが有効にされた単純なＣ＋＋において実装され、ランタイムは６４Ｇｂのメインメモリを伴うデュアルＸｅｏｎ  Ｅ５−６２９０システムについて報告されている。ＧＰＵアクセラレーションは利用されていない。
【０１１４】
高密度視差推定（Dense disparity estimation）：Ｍｉｄｄｌｅｂｕｒｙベンチマークデータセットからの、高密度ステレオの事例に対して、結果が示されている。状態空間は、統合視差値（integral disparity）を含み、６０個と２４０個の間の要素（画像ペアに依存する）を有する。データ項（単項ポテンシャル）は、［０；１］の中の値になり、
【数１２８】
0006448680.tif 000129
ｍｉｎ
【数１２９】
0006448680.tif 000130
によって与えられ、ただしＺＮＣＣは５×５のグレースケール画像区画の０平均のＮＣＣである。τは１／２に固定される。２つの関連するペアごとのポテンシャルについて結果が示されている。１つはＰｏｔｔｓ平滑モデル（Potts smoothness model）であり、もう１つはＰ１−Ｐ２なめらかさとしても知られている３通りのペアごとのポテンシャル
【数１３０】
0006448680.tif 000131
である。グラウンドトゥルースの視差マップから、事象の相対的な頻度が、近隣の画素ｓ、ｔに対して、ｘs＝ｘt（≒９４％）、ｘs＝ｘt±１（≒５．８％）、および｜ｘs−ｘt｜≧２（≒０．２％）と推定される。これは、候補状態がアルゴリズム２においてどのようにサンプリングされるかを定義する。図８は、フルスケールの凸ＢＰ（アルゴリズム１）および限られたメモリのＰＭ−ＣＢＰについての、得られる主目的関数の、ウォールクロックタイム（wall clock time）に対する展開を示している。明らかに、ＰＭ−ＣＢＰは、はるかに低いメモリ要件（「テディ」および「円錐群」については５％、「アロエ」については２．５％）で、凸ＢＰよりはるかに高速に、より低いエネルギーを達成する。Ｔ＝４、８、１６、３２、６４、１２８回の受け渡しの後でＰＭ−ＣＢＰによって返される、対応するラベリング結果が図９に示されている。図９は、受け渡しのそれぞれの回数Ｔの後の、（上から順番に）「円錐群」、「テディ」、「円錐群高解像度」、「テディ高解像度」、「アロエ」、「乳児３」に対する収束しつつあるステレオ結果の視覚的な図示である。
【０１１５】
上の議論において最適化される目的関数は、（式２）における元の線形（すなわち、主）プログラムに対する双対プログラムであるので、主の解は補完的スラック性によって抽出され得る。実際には、このことは、（式３）の解が与えられると、（式１）の近似的な解が
【数１３１】
0006448680.tif 000132
と設定することによって得られることを意味する（νs（ｘs）の定義について式７を思い出されたい）。
【０１１６】
高密度視差推定では、未知のラベル値が視差であり、単項ポテンシャルは、基準画像中の現在の画素を中心とする画像区画を、検討対象の視差値だけシフトされた現在の画素を中心とする「移動」画像中の画像区画と比較することによって、計算される。画像区画のこの比較は、切り捨てられた０平均の正規化された相互相関値に基づく。
【０１１７】
オプティカルフロー推定：同様の数値的な実験がオプティカルフローの事例に対して実行された。状態空間は、１／４画素の精度で１６個の画素探索範囲に対応する１２９2個のフローベクトルを含む。元のグレースケール画像は４００％にアップスケーリングされ、高密度ステレオの場合と同じＺＮＣＣベースのスコアが使用された（しかし、アップスケーリングされた画像からの１１×１１の区画に対して計算された）。ペアごとのなめらかさの項は、動きベクトルの水平方向の成分と垂直方向の成分において別々に適用されるＰ1−Ｐ2モデルである。ウォールクロックタイムに対する、それぞれの回数の受け渡しの後で返される解のための主エネルギーの減少が、図１０に示されている。この場合、メモリ消費は、全体の推測を実行することの６／１２９2、すなわち０．０４％未満であり、使用可能な動きフィールドは数秒のＣＰＵ時間後に得られる。対応するフローフィールドの視覚化が、図１１および図１２に示されている。図１１は、ａ）４回、ｂ）８回、ｃ）１６回、ｄ）３２回、ｅ）６４回、およびｆ）１２８回の受け渡しの後の、「ヤドリフカノキ」データセットに対するオプティカルフローフィールドの収束の視覚的な図示である。図１２は、ａ）４回、ｂ）８回、ｃ）１６回、ｄ）３２回、ｅ）６４回、およびｆ）１２８回の受け渡しの後の、様々なデータセットに対する収束しつつあるオプティカルフローフィールドの視覚的な図示である。カラーコーディングはＭｉｄｄｌｅｂｕｒｙデータセットと同様であるが、より良好な視認性のためにより高飽和度の色を使用する。
【０１１８】
オプティカルフローは、高密度視差推定と非常に類似した方法で対処され得る。部分画素動きベクトルを可能にするために、入力画像の元のペアを元のサイズの４００％にアップスケーリングし、この解像度で統合動きベクトルを推定することができる。このことは、元の画像分解能に対して１／４画素の動きベクトルを生む。
【０１１９】
画像のセグメント化：この環境では、推測すべき画素ラベル値は、「空」、「植生」、「道路」、「建物」、「歩行者」、「車」などの物体の分類である（これらの分類は、屋外の画像がセグメント化される場合に有用であり、たとえば医療用の画像では、分類は様々なタイプの組織および器官であり得る）。単項ポテンシャルは通常、機械学習方法を使用してグラウンドトゥルースのデータから訓練されることが可能であり、ペアごとのクリークポテンシャルは通常、Ｐｏｔｔｓ平滑モデルに設定され、ｘs≠ｘtである場合、θst（ｘs，ｘt）＝τであり（τは０より大きい）、それ以外の場合は０である。
【０１２０】
画像のノイズ除去：画像のノイズ除去では、画素ラベル値は未知の画素値である。単項ポテンシャルは撮像センサの（既知のまたは仮定された）ノイズモデルから導出され、ペアごとの（またはより高次の）クリークポテンシャルは所望の画像の統計（たとえば、２つの隣り合う画素値が自然画像の中にどのように存在するか）を符号化する。
【０１２１】
画像のぼかし除去および拡大：画像のぼかし除去および拡大は、画像のノイズ除去と同様の方法を使用して行われ得る。しかしながら、各画素に対する単項ポテンシャルにぼかしカーネルが追加される。
【０１２２】
説明された構成の変形が想起される。たとえば、画像を受信することは、外部データソースからデータを受信することと、画像を生成するために受信されたデータを処理することとを備え得る。画像を受信することは、画像を生成することを備え得る。
【０１２３】
上の議論では、受信された画像は複数の画素を備え、各画素は入力値を有し、各入力値はある数の候補画素ラベルのうちの１つに対応する。画素ラベルの数は、ノードごとに変化してよく、または一定であってよい。候補画素ラベルの数は、本明細書で説明される方法が使用される適用形態に依存し得る。たとえば、マスクが生成されるべきである場合、候補画素ラベルの数は２であってよく、第１の画素ラベルは、画素がオブジェクトに関連するという決定が行われる場合にその画素に割り当てられ、第２の画素ラベルは、画素がオブジェクトに関連しないという決定が行われる場合にその画素に割り当てられる。
【０１２４】
グラフのクリークは、任意の数のノードから形成され得る。任意の２つのクリークが、同じまたは異なる数のノードを含み得る。特定のクリークへのノードの割当ては、解決されるべき問題に基づいて実行され得る。
【０１２５】
上の議論では、アルゴリズム２の過程において、メッセージが０に初期化された。メッセージは任意の適切な値に初期化され得る。
【０１２６】
あるノードにおいて、単項ポテンシャルが知られている、候補画素ラベルのそれぞれの集合を決定することは、メモリからそれぞれの集合に関する情報を取り出すことを備え得る。
【０１２７】
単項ポテンシャルが知られていない、選択された候補画素ラベルの単項ポテンシャルを計算することは、単項ポテンシャルを計算するための任意の適切な方法を備え得る。たとえば、隣接ノードと関連付けられる、候補画素ラベルの１つまたは複数の既知の単項ポテンシャルが考慮されてよく、これらの単項ポテンシャルのうちの適切な１つが、選択された候補画素ラベルと関連付けられ得る。たとえば、有望なラベルは、真のデータ項を問い合わせるための候補状態を順位付けるために、近隣の画素に伝搬され得る。
【０１２８】
選択された候補画素ラベルは、任意の基準に従って選択され得る。上の議論では、νs（ｘs）の最小の値を伴う状態の決定に基づいて、画素ラベル
【数１３２】
0006448680.tif 000133
が選ばれた。しかしながら、選択された候補画素ラベルは、たとえばランダムに選択され得る。
【０１２９】
候補画素ラベルの更新されたそれぞれの集合と関連付けられる単項ポテンシャルに基づいて、ノードが属する各クリークに対するクリークポテンシャルを調整することは、たとえば、単項ポテンシャルを重み付けることを備え得る。たとえば、単項ポテンシャルは、観測対象のノードに隣接するノードの数に従って均等に重み付けられてよく、または不均等に重み付けられてよい。
【０１３０】
調整されたメッセージから決定された画素ラベルを有する調整された画素を生成することは、調整されたメッセージから決定された画素ラベルを有する新たな画像を生成することを備え得る。代替的に、調整された画像を生成することは、受信された入力画像の画素ラベルを変更することを備え得る。
【０１３１】
本明細書で説明される方法は、単項ポテンシャル（データ項）が大半の画素に対して適度に判別可能である場合には、良好に機能する。画像中のより大きな領域（たとえば、高密度深度計算のためのステレオ画像ペアにおける均一な色の空の領域）が判別不可能である場合、アルゴリズムの出力は「むらがある」ように見えることがある。これを避けるために、アルゴリズムは、入力画像のより低解像度のバージョンに対して実行され、それに続いて、得られた結果をアップスケーリングする。この結果は、より精密なレベルで常駐集合の中の１つの状態を初期化するために使用され得る。この計画は再帰的に適用されてよく、すなわち、アルゴリズムは、非常に粗い画像に対して実行され、次いで、初期化するものとして使用される、前のレベルからのアップスケーリングされた結果を用いてより高い解像度で再び実行され得る。
【０１３２】
説明された方法は、コンピュータプログラムによって実施され得る。ウェブアプリケーションまたは「アプリ」の形態であり得るコンピュータプログラムは、説明された方法の１つまたは複数の機能をコンピュータまたはプロセッサに実行させるように、もしくは実行するように命令するようになされる、コンピュータ実行可能命令またはコードを備える。コンピュータプログラムは、コンピュータ可読媒体またはコンピュータプログラム製品上で、コンピュータなどの装置に提供され得る。コンピュータ可読媒体またはコンピュータプログラム製品は、半導体またはソリッドステートメモリ、磁気テープ、リムーバブルコンピュータメモリスティックまたはディスケット、ランダムアクセスメモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）、リジッド磁気ディスク、およびＣＤ−ＲＯＭ、ＣＤ−Ｒ／Ｗ、ＤＶＤ、またはＢｌｕ−ｒａｙ（登録商標）などの光学ディスクなどの、非一時的媒体を備え得る。コンピュータ可読媒体またはコンピュータプログラム製品は、データ送信、たとえばインターネットを通じたコンピュータプログラムのダウンロードのための、送信信号または媒体を備え得る。
【０１３３】
コンピュータなどの装置またはデバイスは、説明された方法の１つまたは複数の機能を実行するように構成され得る。装置またはデバイスは、携帯電話、タブレット、ラップトップ、または他の処理デバイスを備え得る。装置またはデバイスは、データ処理システムの形態をとり得る。データ処理システムは、分散型システムであり得る。たとえば、データ処理システムは、ネットワークにわたって、または専用のローカル接続を通じて分散され得る。
【０１３４】
装置またはデバイスは通常、コンピュータ実行可能命令を記憶するための少なくとも１つのメモリと、コンピュータ実行可能命令を実行するための少なくとも１つのプロセッサとを備える。
【０１３５】
いくつかの構成が説明されてきたが、これらの構成は単なる例として提示されたものであり、本発明の範囲を限定することは意図されていない。実際には、本明細書で説明される方法、装置、およびシステムは、様々な他の形式で具現化されてよく、本明細書で説明される装置の形式において、さらなる様々な省略、置換、および変更が行われてよい。
【図１】
0006448680.tif 000134
【図２Ａ】
0006448680.tif 000135
【図２Ｂ】
0006448680.tif 000136
【図２Ｃ】
0006448680.tif 000137
【図３】
0006448680.tif 000138
【図４Ａ】
0006448680.tif 000139
【図４Ｂ】
0006448680.tif 000140
【図５】
0006448680.tif 000141
【図６】
0006448680.tif 000142
【図７】
0006448680.tif 000143
【図８】
0006448680.tif 000144
【図９】
0006448680.tif 000145
【図１０】
0006448680.tif 000146
【図１１】
0006448680.tif 000147
【図１２】
0006448680.tif 000148