(57)【要約】【課題】確率伝播法における動的スケジューリングをより高速に行うことができる。【解決手段】ラベリング装置１０は、グラフ上のノード間にメッセージを伝播させて推論を行う確率伝播法を基にグラフ上の各ノードにラベルを割り当てるラベリング装置であって、第１のスケールのメッセージと、第１のスケールと異なるレベルである第２のスケールのメッセージとの間のスケール間メッセージ更新差分量を計算するスケール間メッセージ差分量計算部１４と、スケール間メッセージ更新差分量に基づくメッセージの更新優先度を用いて確率伝播法を実行し、メッセージの更新順序を制御するメッセージ更新順序制御部１５と、メッセージの更新順序にしたがって全ノードにおけるメッセージの収束計算を行い、確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルをノードに最適なラベルとして求める推定ラベル計算部１６と、を有する。【選択図】図１
2019003305.tif 000002
【特許請求の範囲】
【請求項１】
グラフ上のノード間にメッセージを伝播させて推論を行う確率伝播法に基づいてグラフ上の各ノードにラベルを割り当てるラベリング装置であって、
第１のスケールのメッセージと、前記第１のスケールと異なるレベルである第２のスケールのメッセージとの間のスケール間メッセージ更新差分量を計算するスケール間メッセージ差分量計算部と、
前記スケール間メッセージ更新差分量に基づく前記メッセージの更新優先度を用いて前記確率伝播法を実行し、前記メッセージの更新順序を制御するメッセージ更新順序制御部と、
前記メッセージの更新順序にしたがって全ノードにおけるメッセージの収束計算を行い、前記確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルを、前記ノードに最適なラベルとして求める推定ラベル計算部と、
を有することを特徴とするラベリング装置。
【請求項２】
前記メッセージ更新順序制御部は、前記スケール間メッセージ差分量計算部で計算された前記スケール間のメッセージの更新差分量を前記更新優先度として用いて、前記確率伝播法を実行することを特徴とする請求項１に記載のラベリング装置。
【請求項３】
前記第２のスケールは、前記第１のスケールのレベルと異なるレベルのスケールであることを特徴とする請求項１または２に記載のラベリング装置。
【請求項４】
前記スケール間メッセージ差分量計算部は、最も低いレベルのスケールにおけるメッセージに対する計算結果を用いて、更に高いレベルのスケールにおける前記スケール間メッセージ更新差分量を計算することを特徴とする請求項１〜３のいずれか一つに記載のラベリング装置。
【請求項５】
グラフ上のノード間にメッセージを伝播させて推論を行う確率伝播法に基づいてグラフ上の各ノードにラベルを割り当てるラベリング装置が行うラベリング方法であって、
第１のスケールのメッセージと、前記第１のスケールと異なるレベルである第２のスケールのメッセージとの間のスケール間メッセージ更新差分量を計算する工程と、
前記スケール間メッセージ更新差分量に基づく前記メッセージの更新優先度を用いて前記確率伝播法を実行し、前記メッセージの更新順序を制御する工程と、
前記メッセージの更新順序にしたがって全ノードにおけるメッセージの収束計算を行い、前記確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルを、前記ノードに最適なラベルとして求める工程と、
を含んだことを特徴とするラベリング方法。
【請求項６】
コンピュータを、請求項１〜４のいずれか一つに記載のラベリング装置として機能させるためのラベリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ラベリング装置、ラベリング方法およびラベリングプログラムに関する。
【背景技術】
【０００２】
自然画像全体の背後に隠れている統計的性質をモデル化する手段として、マルコフ確率場（Markov  Random  Field：ＭＲＦ）（例えば、非特許文献１参照）によるモデリングがある。ＭＲＦでは、画像全体を、画素をノード、近傍画素間の統計的性質をエッジとするグラフとして捉えることによって、様々なタスクをグラフにおけるラベリング問題として表現する。
【０００３】
このラベリング問題は、エネルギー最小化問題として定式化され、確率伝播法、平均場近似などの最適化アルゴリズムによって解くことができる。応用先の例としては、オプティカルフロー推定（移動方向推定）処理、ステレオ視におけるステレオマッチ（深度推定）処理、画像領域分割処理、画像復元処理などがあり、ラベリング問題に帰着できる広範な問題に適用可能である。これらのタスクにおいて、ＭＲＦでは、画素間の依存関係をモデルに組み込むことによって、従来の画素を独立して扱う処理手法と比較して、精度が高い結果が得られることが特徴である。
【０００４】
ここで、確率伝播法の最適化アルゴリズムを用いた場合、最適化に係る計算時間が非常に大きいことが欠点の一つとして挙げられる。最適化アルゴリズムの一つである確率伝播法（例えば、非特許文献２，３参照）では、グラフ上をメッセージと呼ばれる量を伝播させることにより最適化を行う。このメッセージの計算にはＣを最大クリークサイズ、Ｌをラベル数としてＯ（ＬＣ）の計算時間がかかり、全てのノードについて計算が収束するまでにはＮをノード数、Ｔを収束までの反復回数としてＯ（ＮＬＣＴ）の計算量がかかることが知られている。
【０００５】
この確率伝播法の計算高速化では，メッセージの更新順序が収束に大きく影響することが議論されてきた。このメッセージのスケジューリングに関しては、更新差分に基づいて更新順序を動的に決定することにより、収束を高速化する方法（Residual  Belief  Propagation：ＲＢＰ）（例えば、非特許文献４参照）が提案されている。この動的なスケジューリングは、静的なスケジューリングに比べて非常に高速に収束する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Li,  S.  Z.,  “Markov  Random  Field  Modeling  in  Computer  Vision”,  Springer  Science  &  Business  Media,  1995.
【非特許文献２】Judea  Pearl,  “Reverend  Bayes  on  Inference  Engines:  A  Distributed  Hierarchical  Approach”,  AAAI.1982.
【非特許文献３】Kevin  P.  Murphy,  Yair  Weiss,  and  Michael  I.  Jordan，  “Loopy  Belief  Propagation  for  Approximate  Inference:  An  Empirical  Study”，  Proceedings  of  the  Fifteenth  conference  on  Uncertainty  in  arti_cial  intelligence  (UAI).  1999.
【非特許文献４】Gal  Elidan,  Ian  McGraw,  Daphne  Koller,  “Residual  Belief  Propagation:  Informed  Scheduling  for  Asynchronous  Message  Passing”,  in  Proceedings  of  the  Twenty-second  Conference  on  Uncertainty  in  arti_cial  intelligence  (UAI).  2006.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、このＲＢＰ法では、更新順序を決定する計算部分のコストが高いため、確率伝播法における動的スケジューリングをより高速に行うことができないという問題がある。
【０００８】
本発明は、上記に鑑みてなされたものであって、確率伝播法における動的スケジューリングをより高速に行うことができるラベリング装置、ラベリング方法およびラベリングプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するために、本発明に係るラベリング装置は、グラフ上のノード間にメッセージを伝播させて推論を行う確率伝播法に基づいてグラフ上の各ノードにラベルを割り当てるラベリング装置であって、第１のスケールのメッセージと、第１のスケールと異なるレベルである第２のスケールのメッセージとの間のスケール間メッセージ更新差分量を計算するスケール間メッセージ差分量計算部と、スケール間メッセージ更新差分量に基づくメッセージの更新優先度を用いて確率伝播法を実行し、メッセージの更新順序を制御するメッセージ更新順序制御部と、メッセージの更新順序にしたがって全ノードにおけるメッセージの収束計算を行い、確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルを、ノードに最適なラベルとして求める推定ラベル計算部と、を有することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、確率伝播法における動的スケジューリングをより高速に行うことができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、本実施の形態に係るラベリング装置の要部構成の一例を示すブロック図である。
【図２】図２は、図１に示すラベリング装置が使用するアルゴリズムを示す図である。
【図３】図３は、本実施の形態に係るラベリング処理の処理手順を示すフローチャートである。
【図４】図４は、プログラムが実行されることにより、ラベリング装置が実現されるコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して、本発明の一実施の形態を詳細に説明する。なお、この実施の形態により本発明が限定されるものではない。また、図面の記載において、同一部分には同一の符号を付して示している。
【００１３】
［主な記号の定義］
実施の形態で用いる主な記号を下表に示す。以下、実施の形態の数理的背景、実施の形態の各説明において、同一の記号を用いる。
【００１４】
【表１】
2019003305.tif 000003
【００１５】
［数理的背景］
まず、以降の説明において必要となる数理的背景を説明する。まず、ＭＲＦでは、画像全体を、画素をノード、近傍画素間の統計的性質をエッジとするグラフとして捉えることによって、様々なタスクをグラフにおけるラベリング問題として表現する。そして、確率伝播法に基づくエネルギー最小化問題を解いてグラフ上の各ノードにラベル割り当てを行う場合、ラベリング対象であるグラフＧに紐付けられる確率変数のベクトルを、Ｘ＝（Ｘ１，Ｘ２，・・・，ＸＮ）とする。そして、Ｘがある値ｘ＝（ｘ１，ｘ２，・・・，ｘＮ）Ｔをとった場合の結合確率分布をＰ（ｘ）とする。この場合、Ｐ（ｘ）を、以下の式（１）で表す。
【００１６】
【数１】
2019003305.tif 000004
【００１７】
すなわち、ＭＲＦにおける結合確率分布Ｐ（ｘ）は、クリークＣ上のノードが取るラベルの値ｘｃによって定まる関数（チルダ）Ψｃ（ｘｃ）によって記される。例えば、Ｃ＝２のpairwise  ＭＲＦにおいて、式（１）は、以下の式（２）と書ける。
【００１８】
【数２】
2019003305.tif 000005
【００１９】
Ψｉ，Ψｉ，ｊの分布としては、一般に指数分布族が用いられる。ここで、Ｄｉ（ｘｉ）＝−ｌｎΦｉ（ｘｉ），Ｖｉｊ（ｘｉ，ｘｊ）＝ｌｎΨｉｊ（ｘｉ，ｘｊ）とおくことで、式（２）は、以下の式（３），式（４）のように、エネルギー関数Ｅ（ｘ）を用いて再定義できる。
【００２０】
【数３】
2019003305.tif 000006
【数４】
2019003305.tif 000007
【００２１】
ここで、Ｄｉ（ｘｉ），Ｖｉｊ（ｘｉ，ｘｊ）をそれぞれデータ項、平滑化項（相互作用項）とよぶ。このとき、Ｐ（ｘ）を最大化するラベルｘの組み合わせｘ＊は、式（４）のエネルギー最小化問題を解くことによって間接的に求められる。
【００２２】
最適化アルゴリズムの一つである確率伝播法では、グラフ上をメッセージと呼ばれる量を伝播させることによって推論を行う。本実施形態では分かりやすさのために、以下は全てＣ＝２の構造を持つpairwise  ＭＲＦを例に説明する。確率伝播法において、ノードｉからｊへ送られるメッセージｍｉｊは、式（５）のように表され（Max-Product  Algorithm)、周辺ノードから再帰的に計算される。
【００２３】
【数５】
2019003305.tif 000008
【００２４】
次に、全てのノードにおいてメッセージの収束が計算した後、以下の式（６）を最大化するｘ＊を選ぶことで、全体としてエネルギー最小となるラベルの組み合わせが推定される。
【００２５】
【数６】
2019003305.tif 000009
【００２６】
［本実施の形態における数理的背景］
本実施の形態では、代表的な動的スケジューリング手法であるＲＢＰに基づく。ＲＢＰでは、メッセージの更新差分量をもとに各メッセージの更新優先度を決定する。
【００２７】
１回の更新によって生じるメッセージｍｔｉｊとｍｔ−１ｉｊとの差分量ｅｉｊは、式（７）として与えられる。
【００２８】
【数７】
2019003305.tif 000010
【００２９】
そして、メッセージｍｉｊの更新優先度ｒ（ｍｉｊ）は、式（８）によって定義される。
【００３０】
【数８】
2019003305.tif 000011
【００３１】
つまり、ＲＢＰでは各ラベルｘｊに対応するｅｉｊ（ｘｊ）の中で最も大きい代表値を更新優先度として用いる。この更新優先度を用いた動的なスケジューリングは、事前に更新順序が決定された静的なスケジューリングよりも高速に収束することがわかっている（詳細は、非特許文献４参照）。
【００３２】
しかしながら、更新優先度を決定するためには、全てのメッセージについて２度更新を行う必要がありＯ（２ＮＫＣ）の計算量がかかってしまう。
【００３３】
そこで本実施の形態では、式（８）によって定義される更新優先度に加え、階層（スケール）間のメッセージ継承における更新優先度を新たに導入し、低解像度のメッセージを利用して高解像度における更新優先度計算を高速に行う。
【００３４】
まず、Ｇ０，Ｇ１，・・・，ＧＳ−１を各解像度におけるグラフであるとする。なお、Ｇ０＝Ｇも対応している。Ｇｓ（０≦ｓ≦Ｓ）におけるそれぞれのノードは、オリジナルの解像度におけるε×εの画素ブロックに対応する。スケールｓにおける単項ポテンシャルΦｓｉｊは、式（９）のように定義される。
【００３５】
【数９】
2019003305.tif 000012
【００３６】
Ｇｓ＋１のノードからｇｓのノードへ送られるメッセージは、式（１０）のように表現できる。
【００３７】
【数１０】
2019003305.tif 000013
【００３８】
このとき、スケールｓ，ｓ＋１間の更新優先度は、式（８）と同様に、以下の式（１１）と定義できる。
【００３９】
【数１１】
2019003305.tif 000014
【００４０】
本実施の形態では、この階層（スケール）間における更新優先度を新たに定義し、スケール間で変化量が大きいメッセージの更新優先度を高くし、スケール間で変化量が大きいメッセージを集中的に更新できるように更新順序を制御する。言い換えると、本実施の形態では、全てのノードに対して一様に更新を行う従来法と比して、新たに定義したスケール間におけるスケール間メッセージ更新差分値に基づくメッセージの更新優先度にしたがって確率伝播法を実行する。すなわち、本実施の形態では、更新順序を算出する際の確率伝播法を用いた演算処理において、各メッセージに対する演算を、スケール間におけるスケール間メッセージ更新差分値に基づく更新優先度順に実行する。このため、本実施によれば、従来行っていた余分なiterationが減るとともに、動的スケジューリングをマルチスケールで行えるように拡張できる。
【００４１】
［ラベリング装置の構成］
上記の実施の形態の数理的背景を踏まえ、本実施の形態に係るラベリング装置などについて説明する。なお、以下の実施の形態は、一例を示すに過ぎない。図１は、本実施の形態に係るラベリング装置の要部構成の一例を示すブロック図である。図１に示すラベリング装置１０は、確率伝播法に基づくエネルギー最小化問題を解いてグラフ上の各ノードにラベル割り当てを行う。図１に示すように、ラベリング装置１０は、グラフ集合作成部１１、第１更新順序制御部１２、第１メッセージ更新差分量計算部１３、スケール間メッセージ差分量計算部１４、メッセージ更新順序制御部１５及び推定ラベル計算部１６を有する。
【００４２】
グラフ集合作成部１１は、オリジナルのグラフ集合Ｇ＝（ν，ε）を入力とし、低解像度から高解像度のグラフ群を作成し、第１更新順序制御部１２に出力する。
【００４３】
第１更新順序制御部１２及び第１メッセージ更新差分量計算部１３は、メッセージの更新順序の初期計算として、まず、最も低いレベルのスケール、すなわち、低解像度のグラフにおける各メッセージを計算し、メッセージの更新差分値を基に低解像度における更新順序を出力する繰り返し計算を行う。
【００４４】
スケール間メッセージ差分量計算部１４は、第１のスケールのメッセージと、第１のスケールと異なるレベルである第２のスケールのメッセージとの間のスケール間メッセージ更新差分量を計算する。具体的には、スケール間メッセージ差分量計算部１４は、低解像度のメッセージと高解像度のメッセージを入力とし、そのスケール間メッセージ更新差分量をメッセージ更新順序制御部１５に出力する。また、例えば、第２のスケールは、第１のスケールのレベルと異なるレベルのスケールである。ここで、スケール間メッセージ差分量計算部１４は、初期のスケール間メッセージ更新差分量を計算する際に、最も低いレベルのスケール（Ｓ−１）におけるメッセージに対する計算結果を用いる。スケール間メッセージ差分量計算部１４は、最も低いレベルのスケール（Ｓ−１）におけるメッセージに対する計算結果を初期のスケール間メッセージ更新差分量として使用し、計算の高速化を図る。すなわち、スケール間メッセージ差分量計算部１４は、最も低いレベルのスケールにおけるメッセージに対する計算結果を用いて、更に高いレベルのスケールにおけるスケール間メッセージ更新差分量を計算する。
【００４５】
メッセージ更新順序制御部１５は、スケール間のメッセージのスケール間メッセージ更新差分量に基づくメッセージの更新優先度を用いて確率伝播法を実行し、メッセージの更新順序を制御する。メッセージ更新順序制御部１５は、スケール間メッセージ差分量計算部１４で計算されたスケール間のメッセージのスケール間メッセージ更新差分量を更新優先度として用いて、確率伝播法を実行する。メッセージ更新順序制御部１５は、更新順序を算出する際の確率伝播法を用いた演算処理において、各メッセージに対する演算を、スケール間におけるスケール間メッセージ更新差分値に基づく更新優先度順に実行する。メッセージ更新順序制御部１５は、スケール間のメッセージのスケール間メッセージ更新差分量である更新優先度を入力とし、高解像度における更新順序を出力する繰り返し計算を行う。
【００４６】
メッセージ更新順序制御部１５は、第２更新順序制御部１７及び第２メッセージ更新差分量計算部１８を有する。第２メッセージ更新差分量計算部１８は、高低解像度のグラフにおける各メッセージを計算する。そして、第２更新順序制御部１７は、メッセージの更新差分値を基に高解像度における更新順序を出力する。第２更新順序制御部１７及び第２メッセージ更新差分量計算部１８は、各メッセージについて、これらの計算を繰り返し行う。第２更新順序制御部１７及び第２メッセージ更新差分量計算部１８は、更新差分値に基づく更新優先度が高いメッセージから順に、これらの繰り返し計算を行う。
【００４７】
推定ラベル計算部１６は、メッセージの更新順序にしたがって全ノードにおけるメッセージの収束計算を行い、確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルを、ノードに最適なラベルとして求める。推定ラベル計算部１６は、メッセージの更新スケジューリングにしたがって全ノードにおけるメッセージの収束計算を行う。推定ラベル計算部１６は、確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルを求め、該求めたラベルを前記ノードに最適なラベルとして推定する。
【００４８】
［アルゴリズム］
次に、ラベリング装置１０が使用するアルゴリズムについて説明する。図２は、図１に示すラベリング装置１０が使用するアルゴリズムを示す図である。
【００４９】
まず、アルゴリズムは、グラフ集合Ｇ＝（ν，ε）を入力（Input）とし、グラフＧの各ノードにおける最適なラベルセットｘを出力（Output）とする。そして、スケール（Ｓ−１）から０の更新順序の制御を行うため、以下の演算を実行する。
【００５０】
まず、グラフ集合作成部１１は、式（９）から、高解像度のグラフＧから低解像度のグラフ群（Ｇ０，Ｇ１，・・・，ＧＳ−１）を作成する（図２の１行目）。続いて、第１更新順序制御部１２は、全てのメッセージの初期化を行う（図２の２行目）。
【００５１】
そして、第１更新順序制御部１２及び第１メッセージ更新差分量計算部１３は、更新優先度を格納した優先度付きキューＱを、スケール（Ｓ−１）、すなわち、低解像度において作成する（図２の６〜９行目）。具体的には、第１更新順序制御部１２及び第１メッセージ更新差分量計算部１３は、全てのメッセージｍｉｊについて、式（５）を用いて計算したメッセージ更新差分から、式（８）によって更新優先度ｒ（ｍｉｊ）を計算し、優先度付きキューＱにｍｉｊと、ｒ（ｍｉｊ）とを格納する。このとき、第１更新順序制御部１２及び第１メッセージ更新差分量計算部１３は、ｒ（ｍｉｊ）を更新優先度としてＱに格納する。
【００５２】
続いて、第１更新順序制御部１２及び第１メッセージ更新差分量計算部１３は、スケール（Ｓ―１）において更新優先度に基づいた確率伝播法を実行する（図２の１７〜２５行目）。すなわち、メッセージｍｉｊを更新するために、優先度付きキューＱからｍｉｊに依存するｍｊｋを除去し、式（５）によってメッセージｍｊｋを計算し、その優先度ｒ（ｍｊｋ）を式（８）によって計算し、優先度付きキューＱに、メッセージｍｊｋとその優先度ｒ（ｍｊｋ）とを格納する。このように、第１更新順序制御部１２及び第１メッセージ更新差分量計算部１３は、低解像度のグラフにおけるメッセージ更新差分から、低解像度における更新順序を出力する繰り返し計算を行う。
【００５３】
なお、後述するメッセージの計算（図２の１２行目）は単に値が計算されたことを意味し、本処理におけるメッセージの更新（図２の１９行目）によって、初めてその値が更新される。この処理は全てのメッセージに対して実行される。
【００５４】
次に、スケール間メッセージ差分量計算部１４は、高解像度のスケールｓにおいて、スケール間のメッセージ及び更新優先度の計算を行う（図２の１２〜１４行目）。まず、スケール間メッセージ差分量計算部１４は、スケールｓとスケール（ｓ＋１）のデータペアを入力とし、高解像度のスケールｓにおいて、式（１０）を用いてスケール間のメッセージｍｓｉｊを計算する。スケール間メッセージ差分量計算部１４は、式（１１）を用いて、スケール間のスケール間メッセージ更新差分量である更新差分ｒ（ｍｓｉｊ，ｍｓ＋１ｉ/ε，ｊ/ε）を計算する。ここで、スケール間メッセージ差分量計算部１４は、初期の更新差分量を計算する際に、最も低いレベルのスケール（Ｓ−１）におけるメッセージに対する計算結果を用いて、計算の高速化を図る。
【００５５】
そして、スケール間メッセージ差分量計算部１４は、優先度付きキューＱにｍｉｊと、ｒ（ｍｓｉｊ，ｍｓ＋１ｉ/ε，ｊ/ε）とを格納する。このとき、第１更新順序制御部１２及び第１メッセージ更新差分量計算部１３は、ｒ（ｍｓｉｊ，ｍｓ＋１ｉ/ε，ｊ/ε）を更新優先度としてＱに格納する。この処理は全てのメッセージに対して実行される。
【００５６】
そして、メッセージ更新順序制御部１５は、更新優先度ｒ（ｍｓｉｊ，ｍｓ＋１ｉ/ε，ｊ/ε）を格納した優先度付きキューＱ（図２の１４行目）を用いて、優先度に基づいた確率伝播法を実行し（図２の１７〜２５行目）、高解像度のグラフにおけるメッセージの更新順序を出力する繰り返し計算を行う。すなわち、メッセージ更新順序制御部１５は、メッセージｍｉｊを更新するために、更新優先度ｒ（ｍｓｉｊ，ｍｓ＋１ｉ/ε，ｊ/ε）を格納した優先度付きキューＱからｍｉｊに依存するｍｊｋを除去し、式（５）によってメッセージｍｊｋを計算し、その優先度ｒ（ｍｊｋ）を式（８）によって計算し、優先度付きキューＱに、メッセージｍｊｋとその優先度ｒ（ｍｊｋ）とを格納する。メッセージｍｊｋとその優先度ｒ（ｍｊｋ）とを格納する優先度付きキューＱは、メッセージの更新スケジューリングに相当し、推定ラベル計算部１６に出力される。
【００５７】
スケール間メッセージ差分量計算部１４は、次のスケールｓとスケール（ｓ＋１）のデータペアがある場合には、１２行目に戻り、スケール間のメッセージ及びスケール間メッセージ更新差分量（優先度）の計算を行う。そして、メッセージ更新順序制御部１５は、更新優先度にしたがって確率伝播法を実行し、メッセージの更新順序を出力する。また、推定ラベル計算部１６は、メッセージ更新順序制御部１５から出力された優先度付きキューＱが示す更新スケジューリングにしたがって、全ノードにおけるメッセージの収束計算を行う。そして、推定ラベル計算部１６は、確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルを求め、該求めたラベルをノードに最適なラベルとして推定する。
【００５８】
［ラベリング処理］
次に、図３を参照して、ラベリング装置１０が実行するラベリング処理について説明する。図３は、本実施の形態に係るラベリング処理の処理手順を示すフローチャートである。図３に示すラベリング処理の処理手順は、図２に示すアルゴリズムに対応する。
【００５９】
ラベリング装置１０では、まず、グラフ集合Ｇ＝（ν，ε）を入力として受付けると（ステップＳ１）、グラフ集合作成部１１が、ラベリング対象となるグラフ集合Ｇについて、グラフ集合Ｓ（Ｇ）＝｛Ｇ（０），Ｇ（１），・・・，Ｇ（Ｓ）｝を作成する（ステップＳ２）。ステップＳ２の処理は、アルゴリズムの１行目に対応する。
【００６０】
そして、第１更新順序制御部１２及び第１メッセージ更新差分量計算部１３は、低解像度のグラフにおけるメッセージ更新順序を制御する処理を行う（ステップＳ３）。ステップＳ３では、第１更新順序制御部１２及び第１メッセージ更新差分量計算部１３は、低解像度のグラフにおける各メッセージを計算し、メッセージの更新差分値を基に低解像度における更新順序を出力する繰り返し計算を行う。具体的には、第１更新順序制御部１２及び第１メッセージ更新差分量計算部１３は、低解像度における更新優先度を格納した優先度付きキューＱを作成する。ステップＳ３の処理は、アルゴリズムの５〜９行目及び１７〜２５行目に対応する。
【００６１】
そして、スケール間メッセージ差分量計算部１４は、異なるレベルのスケールのデータペアが入力されると（ステップＳ４）、これらのスケール間のスケール間メッセージ更新差分量を計算する（ステップＳ５）。スケール間メッセージ差分量計算部１４は、スケール間のメッセージのスケール間メッセージ更新差分量を更新優先度としてメッセージ更新順序制御部１５に出力する。なお、ステップＳ５は、アルゴリズムの１２〜１５行目に対応する。また、スケール間メッセージ差分量計算部１４は、初期の更新差分量を計算する際に、最も低いレベルのスケール（Ｓ−１）におけるメッセージに対する計算結果を用いて、計算の高速化を図る。
【００６２】
続いて、メッセージ更新順序制御部１５は、スケール間におけるスケール間メッセージ更新差分値に基づくメッセージの更新優先度を用いて確率伝播法を実行し、高解像度のグラフにおけるメッセージの更新順序を制御する処理を行う（ステップＳ６）。具体的には、メッセージ更新順序制御部１５は、高解像度における更新優先度を格納した優先度付きキューＱを作成し、推定ラベル計算部１６に出力する。なお、ステップＳ６は、アルゴリズムの１７〜２５行目に対応する。
【００６３】
そして、スケール間メッセージ差分量計算部１４は、次の計算対象となるスケールのデータペアがあるか否かを判定する（ステップＳ７）。スケール間メッセージ差分量計算部１４は、次のスケールのデータペアがあると判定した場合（ステップＳ７：Ｙｅｓ）、次のスケールのデータペアの入力を受け付け（ステップＳ４）、スケール間のメッセージのスケール間メッセージ更新差分量を計算する（ステップＳ５）。
【００６４】
一方、次の計算対象となるスケールのデータペアがないとスケール間メッセージ差分量計算部１４が判定した場合（ステップＳ７：Ｎｏ）、推定ラベル計算部１６は、推定ラベル計算処理を行う（ステップＳ８）。推定ラベル計算処理は、メッセージの更新順序にしたがって全ノードにおけるメッセージの収束計算を行い、確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルを、ノードに最適なラベルとして求める処理である。この際、推定ラベル計算部１６は、メッセージの更新順序、すなわち、メッセージ更新順序制御部１５による高解像度における更新優先度を格納した優先度付きキューＱにしたがって全ノードにおけるメッセージの収束計算を行う。そして、推定ラベル計算部１６は、この処理結果を出力する。
【００６５】
［実施の形態の効果］
本実施の形態では、全てのノードに対して一様に更新を行う従来法と比して、新たにスケール間におけるスケール間メッセージ更新差分値を定義し、このスケール間におけるスケール間メッセージ更新差分値に基づくメッセージの更新優先度を用いて確率伝播法を実行し、更新順序を制御する。言い換えると、本実施の形態では、このスケール間におけるスケール間メッセージ更新優先度を新たに定義し、スケール間で変化量が大きいメッセージの優先度を高くし、スケール間で変化量が大きいメッセージを集中的に更新できるように更新順序の制御処理を実行する。このため、本実施によれば、従来行っていた更新順序決定のための余分なiterationが減るとともに、動的スケジューリングをマルチスケールで行えるように拡張できる。
【００６６】
また、本実施の形態では、ラベリング装置１０では、スケール間メッセージ差分量計算部１４は、初期の更新差分量を計算する際に、最も低いレベルのスケール（Ｓ−１）におけるメッセージに対する計算結果を用いるため、確率伝播法における動的スケジューリングをより高速化に行うことができる。
【００６７】
［実施の形態のシステム構成について］
図１に示したラベリング装置１０の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、ラベリング装置１０の機能の分散および統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散または統合して構成することができる。
【００６８】
また、ラベリング装置１０において行われる各処理は、全部または任意の一部が、ＣＰＵ（Central  Processing  Unit）およびＣＰＵにより解析実行されるプログラムにて実現されてもよい。また、ラベリング装置１０においておこなわれる各処理は、ワイヤードロジックによるハードウェアとして実現されてもよい。
【００６９】
また、実施の形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的に行うこともできる。もしくは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上述および図示の処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて適宜変更することができる。
【００７０】
［プログラム］
図４は、プログラムが実行されることにより、ラベリング装置が実現されるコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。
【００７１】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１及びＲＡＭ（Random  Access  Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。
【００７２】
ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、ラベリング装置１０の各処理を規定するプログラムは、コンピュータ１０００により実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、ラベリング装置１０における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤ（Solid  State  Drive）により代替されてもよい。
【００７３】
また、上述した実施の形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して実行する。
【００７４】
なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３及びプログラムデータ１０９４は、ネットワーク（ＬＡＮ、ＷＡＮ等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３及びプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【００７５】
以上、本発明者によってなされた発明を適用した実施の形態について説明したが、本実施の形態による本発明の開示の一部をなす記述及び図面により本発明は限定されることはない。すなわち、本実施の形態に基づいて当業者等によりなされる他の実施の形態、実施例及び運用技術等は全て本発明の範疇に含まれる。
【符号の説明】
【００７６】
１０  ラベリング装置
１１  グラフ集合作成部
１２  第１更新順序制御部
１３  第１メッセージ更新差分量計算部
１４  スケール間メッセージ差分量計算部
１５  メッセージ更新順序制御部
１６  推定ラベル計算部
１７  第２更新順序制御部
１８  第２メッセージ更新差分量計算部
【図１】
2019003305.tif 000015
【図２】
2019003305.tif 000016
【図３】
2019003305.tif 000017
【図４】
2019003305.tif 000018