(57)【要約】【課題】確率伝播法に基づく収束計算を行ってグラフ上の各ノードにラベルを割り当てるラベリングにおいて、計算の高速化と、精度との双方を担保しながら、従来必要であったユーザによるパラメータ調整処理を削除できる。【解決手段】ラベリング装置１０は、確率伝播法に基づく収束計算を行ってグラフ上の各ノードにラベルを割り当てる場合に、グラフ上に伝播させるメッセージ量を計算するメッセージ計算部１２と、ラベルに対応するメッセージ量の変化量を計算し、メッセージ量の変化量が所定値以下となった場合には該ラベルに関するメッセージ量の計算が収束したと判断して該ラベルに関する以降のメッセージ量の計算を省略してラベル空間を削減する収束値計算部１３と、削減したラベル空間上で全ノードのエネルギー量が最小となるラベルを計算し、該計算したラベルをノードに有効なラベルとして決定する有効ラベル計算部１４とを有する。【選択図】図１
2018014040.tif 000002
【特許請求の範囲】
【請求項１】
確率伝播法に基づく収束計算を行ってグラフ上の各ノードにラベルを割り当てるラベリング装置であって、
前記グラフ上のノード間に伝播させるメッセージ量を計算するメッセージ計算部と、
前記ラベルに対応する前記メッセージ量の変化量を計算し、前記メッセージ量の変化量が所定値以下となった場合には、該ラベルに関するメッセージ量の計算が収束したと判断して該ラベルに関する以降のメッセージ量の計算を省略してラベル空間を削減する収束計算部と、
前記収束計算部が削減したラベル空間上で、前記確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルを計算し、該計算したラベルを前記ノードに有効なラベルとして決定する有効ラベル計算部と、
を有することを特徴とするラベリング装置。
【請求項２】
前記収束計算部は、前回計算した前記ラベルに対応するメッセージ量から、今回計算した前記ラベルに対応するメッセージ量への変化量を計算することを特徴とする請求項１に記載のラベリング装置。
【請求項３】
確率伝播法に基づく収束計算を行ってグラフ上の各ノードにラベルを割り当てるラベリング装置が行うラベリング方法であって、
前記グラフ上に伝播させるメッセージ量を計算する工程と、
前記ラベルに対応する前記メッセージ量の変化量を計算し、前記メッセージ量の変化量が所定値以下となった場合には、該ラベルに関するメッセージ量の計算が収束したと判断して該ラベルに関する以降のメッセージ量の計算を省略してラベル空間を削減する工程と、
削減したラベル空間上で、前記確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルを計算し、該計算したラベルを前記ノードに有効なラベルとして決定する工程と、
を含んだことを特徴とするラベリング方法。
【請求項４】
確率伝播法に基づく収束計算を行ってグラフ上の各ノードにラベルを割り当てるコンピュータに実行させるためのラベリングプログラムであって、
前記グラフ上に伝播させるメッセージ量を計算するステップと、
前記ラベルに対応する前記メッセージ量の変化量を計算し、前記メッセージ量の変化量が所定値以下となった場合には、該ラベルに関するメッセージ量の計算が収束したと判断して該ラベルに関する以降のメッセージ量の計算を省略してラベル空間を削減するステップと、
削減したラベル空間上で、前記確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルを計算し、該計算したラベルを前記ノードに有効なラベルとして決定するステップと、
を前記コンピュータに実行させるためのラベリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ラベリング装置、ラベリング方法およびラベリングプログラムに関する。
【背景技術】
【０００２】
自然画像全体の背後に隠れている統計的性質をモデル化する手段として、マルコフ確率場（Markov  Random  Field；ＭＲＦ）（例えば、非特許文献１参照）によるモデリングがある。ＭＲＦでは、画像全体を、画素をノード、近傍画素間の統計的性質をエッジとするグラフとして捉えることによって、様々なタスクをグラフにおけるラベリング問題として表現する。
【０００３】
このラベリング問題は、エネルギー最小化問題として定式化され、確率伝播法、平均場近似などの最適化アルゴリズムによって解くことができる。応用先の例としては、オプティカルフロー推定（移動方向推定）処理、ステレオ視におけるステレオマッチ（深度推定）処理、画像領域分割処理、画像復元処理などがあり、ラベリング問題に帰着できる広範な問題に適用可能である。これらのタスクにおいて、ＭＲＦでは、画素間の依存関係をモデルに組み込むことによって、従来の画素を独立して扱う処理手法と比較して、精度が高い結果が得られる。
【０００４】
ここで、確率伝播法の最適化アルゴリズムを用いた場合、繰り返し法による収束計算が必要となるため、最適化に係る計算時間が非常に大きいことが欠点の一つとして挙げられる。この確率伝播法では、グラフ上を、メッセージと呼ばれる量を伝播させることによって最適化を行う（例えば、非特許文献２参照）。このメッセージの計算には、Ｃを最大クリークサイズ、Ｋをラベル数とすると、Ｏ（ＫＣ）の計算時間が必要となり、全てのノードについて計算が収束するまでには、Ｎをノード数、Ｔを収束までの反復回数とすると、Ｏ（ＮＫＣＴ）の計算量を要することが知られている。
【０００５】
この計算量を削減する方法として、Yangらはエネルギー量に基づく階層的な探索空間削減手法を提案した（例えば、非特許文献３参照）。このYangらによる方法では、エネルギー量に基づきノードごとに保持するラベルを固定数（top-k）（kは閾値）に限定することによって計算の高速化を実現する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Li,  Stan  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.
【非特許文献３】Qingxiong  Yang,  Liang  Wang,  and  Narendra  Ahuja,  "A  Constant-Space  Belief  Propagation  Algorithm  for  Stereo  Matching"，  Computer  vision  and  pattern  recognition  (CVPR),  2010  IEEE  Conference  on.IEEE,  2010.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、この閾値kの取り方は、高速化率と精度とに大きく影響するため、別途ユーザが調整する必要が生じる。ここで、全体の計算量はラベル数に比例するためラベル数の削減は高速化に寄与する一方で、候補ラベルの過度な絞り込みは精度低下に繋がる。このため、固定数の調整が重要となり、この固定数の調整をユーザが行う必要が生じるという問題があった。
【０００８】
本発明は、上記に鑑みてなされたものであって、確率伝播法に基づく収束計算を行ってグラフ上の各ノードにラベルを割り当てるラベリングにおいて、計算の高速化と、精度との双方を担保しながら、従来必要であったユーザによるパラメータ調整処理を削除できるラベリング装置、ラベリング方法およびラベリングプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するために、本発明に係るラベリング装置は、確率伝播法に基づく収束計算を行ってグラフ上の各ノードにラベルを割り当てるラベリング装置であって、グラフ上のノード間に伝播させるメッセージ量を計算するメッセージ計算部と、ラベルに対応するメッセージ量の変化量を計算し、メッセージ量の変化量が所定値以下となった場合には、該ラベルに関するメッセージ量の計算が収束したと判断して該ラベルに関する以降のメッセージ量の計算を省略してラベル空間を削減する収束計算部と、収束計算部が削減したラベル空間上で、確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルを計算し、該計算したラベルをノードに有効なラベルとして決定する有効ラベル計算部と、を有することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、確率伝播法に基づく収束計算を行ってグラフ上の各ノードにラベルを割り当てるラベリングにおいて、計算の高速化と、精度との双方を担保しながら、従来必要であったユーザによるパラメータ調整処理を削除できる。
【図面の簡単な説明】
【００１１】
【図１】図１は、本実施の形態に係るラベリング装置の構成の一例を示すブロック図である。
【図２】図２は、図１に示すラベリング装置が行うラベリング処理の処理手順を示すフローチャートである。
【図３】図３は、図１に示すラベリング装置が使用するアルゴリズムを示す図である。
【図４】図４は、プログラムが実行されることにより、ラベリング装置が実現されるコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して、本発明の一実施の形態を詳細に説明する。なお、この実施の形態により本発明が限定されるものではない。また、図面の記載において、同一部分には同一の符号を付して示している。
【００１３】
［主な記号の定義］
実施の形態で用いる主な記号を下表に示す。以下、実施の形態の数理的背景、実施の形態の各説明において、同一の記号を用いる。
【００１４】
【表１】
2018014040.tif 000003
【００１５】
［数理的背景］
まず、以降の説明において必要となる数理的背景を説明する。まず、ＭＲＦでは、画像全体を、画素をノード、近傍画素間の統計的性質をエッジとするグラフとして捉えることによって、様々なタスクをグラフにおけるラベリング問題として表現する。そして、確率伝播法に基づく収束計算を行ってグラフ上の各ノードにラベル割り当てを行う場合、ラベリング対象であるグラフｇに紐付けられる確率変数のベクトルを、Ｘ＝（Ｘ１，Ｘ２，・・・，ＸＮ）とする。そして、Ｘがある値ｘ＝（ｘ１，ｘ２，・・・，ｘＮ）Ｔをとった場合の結合確率分布をＰ（ｘ）とする。この場合、Ｐ（ｘ）を、以下の（１）式で表す。
【００１６】
【数１】
2018014040.tif 000004
【００１７】
すなわち、ＭＲＦにおける結合確率分布Ｐ（ｘ）は、クリークＣ上のノードが取るラベルの値ｘｃによって定まる関数（チルダ）Ψｃ（ｘｃ）によって記される。例えば、Ｃ＝２のＭＲＦにおいて、（１）式は、以下の（２）式と書ける。
【００１８】
【数２】
2018014040.tif 000005
【００１９】
Ψｉ，Ψｉｊの分布としては、一般に指数分布族が選択される。ここで、Ｄｉ（ｘｉ）＝−ｌｎΨｉ，Ｖｉｊ（ｘｉ，ｘｊ）＝−ｌｎΨｉj（ｘｉ，ｘｊ）とおくことで、（２）式は、以下の（３）式及び（４）式のように、エネルギー関数Ｅ（ｘ）を用いて再定義できる。
【００２０】
【数３】
2018014040.tif 000006
【００２１】
【数４】
2018014040.tif 000007
【００２２】
なお、Ｄｉ（ｘｉ），Ｖｉj（ｘｉ，ｘｊ）を、それぞれ、データ項、平滑化項（相互作用項）と呼ぶ。このときＰ（ｘ）を最大化するラベルの組み合わせｘ＊は、（４）式のエネルギー最小化問題を解くことによって間接的に求められる。
【００２３】
ここで、最適化アルゴリズムの一つである確率伝播法では、グラフ上をメッセージと呼ばれる量を伝播させることにより、推論を行う。Ｃ＝２の構造を持つＭＲＦにおいて、ノードｐからノードｑへ送られるメッセージｍｐｑは、以下の（５）式で示され、周辺ノードから再帰的に計算される。
【００２４】
【数５】
2018014040.tif 000008
【００２５】
次に、各ノードにおいて、Ｔ回のメッセージ伝播後、それぞれのノードについて、以下の（６）式を満たすラベルの組み合わせｘ＊を選択する。
【００２６】
【数６】
2018014040.tif 000009
【００２７】
（６）式を満たすラベルの組み合わせｘ＊を選択することによって、全体としてエネルギーが最小となるラベルの組み合わせが推定される。
【００２８】
閉路があるＭＲＦ上での確率伝播法では、（５）式で示すメッセージ伝播を全てのノードに対して繰り返し適用することによって、最適となるラベルの組み合わせｘ＊を決定する。この場合、エネルギー関数の減少が収束したところで、iterationを打ち切るが、このエネルギーの収束特性は、ノードごとに異なる。
【００２９】
［本実施の形態の数理的背景］
さらに、本実施の形態に関する数理的背景について説明する。本実施の形態では、各ノードｐにおいて、ｍｐｑを（５）式から計算する場合に、ノードｓ∈Ｎ（ｐ）について、以下の（７）式に示す収束判定をノードごとに行う。
【００３０】
【数７】
2018014040.tif 000010
【００３１】
具体的には、本実施の形態では、ノードｓ∈Ｎ（ｐ）について、（７）式に示す収束判定をノードごとに行うことにより、ｍｓｐｔ−１（ｘｐ）≠ｍｓｐｔ（ｘｐ）を満たすラベルに対応するメッセージｍｐｑ（ｘｐ）のみを、更新すべきメッセージ集合に加え、activeなラベルに対応するメッセージであるとして更新する。
【００３２】
一方、ｍｓｐｔ−１（ｘｐ）＝ｍｓｐｔ（ｘｐ）を満たしたラベルについては、該ラベルに対応するメッセージの計算が収束したとして、該ラベルに対応付けられる、以降のメッセージ量の計算を省略する。したがって、本実施の形態では、iterationごとに固定数（top-k）のラベルを各ノードで保持させる従来の方法と比較して、ノードごとに適応的に保持するラベル空間を削除するため、メッセージ計算の高速化が可能になる。
【００３３】
なお、ｍｓｐｔ−１（ｘｐ）＝ｍｓｐｔ（ｘｐ）を満たすラベルについては、該ラベルに紐付くメッセージの計算が収束したと判断する例を説明したが、もちろん、これは一例である。本実施の形態では、ｍｓｐｔ−１（ｘｐ）とｍｓｐｔ（ｘｐ）との変化量が、所定値以内であれば、該ラベルに紐付くメッセージの計算が収束したと判断すればよい。この所定値は、予め設定しておけばよい。
【００３４】
［ラベリング装置の構成］
上記の実施の形態の数理的背景を踏まえ、本実施の形態に係るラベリング装置などについて説明する。なお、以下の実施の形態は、一例を示すに過ぎない。図１は、本実施の形態に係るラベリング装置１０の要部構成の一例を示すブロック図である。図１に示すラベリング装置１０は、確率伝播法に基づく収束計算を行ってグラフ上の各ノードにラベル割り当てを行う。図１に示すように、ラベリング装置１０は、繰り返し計算部１１、メッセージ計算部１２、収束値計算部１３及び有効ラベル計算部１４を有する。
【００３５】
繰り返し計算部１１は、メッセージ計算部１２、収束値計算部１３及び有効ラベル計算部１４による繰り返し計算を制御する。具体的には、繰り返し計算部１１は、繰り返し計算回数であるiteration「t」が「0」から「T」まで繰り返し計算が実行されるように、他の機能部を制御する。
【００３６】
メッセージ計算部１２は、繰り返し計算回数であるiteration=（t-1）のグラフデータを入力とし、iteration=（t）におけるメッセージを出力する。言い換えると、メッセージ計算部１２は、グラフ上に伝播させるメッセージ量を計算する。メッセージ量については、（５）式により定義される。
【００３７】
収束値計算部１３は、iteration=(t-1),tのメッセージを入力とし、ラベルごとの収束値を出力する。この収束値計算部１３は、ラベルごとの収束値として、ラベルに対応するメッセージ量の変化量を計算する。具体的には、収束値計算部１３は、前回計算したラベルに対応するメッセージ量から、今回計算したラベルに対応するメッセージ量への変化量を計算する。
【００３８】
そして、収束値計算部１３は、メッセージ量の変化量が所定値以下となった場合には、該ラベルに関するメッセージ量の計算が収束したと判断して該ラベルに関する以降のメッセージ量の計算を省略してラベル空間を削減する。一方、収束値計算部１３は、メッセージ量の変化量が所定値を超えた場合には、この該ラベルに関するメッセージ量を、以降のメッセージ計算に含まれるように、更新すべきメッセージ集合に加える。
【００３９】
具体的には、収束値計算部１３は、前述の（７）式を用いることによって、収束判定をノードごとに行うことにより、ｍｓｐｔ−１（ｘｐ）＝ｍｓｐｔ（ｘｐ）であるラベルについては、以降のメッセージ量の計算を省略する。これに対し、収束値計算部１３は、ｍｓｐｔ−１（ｘｐ）≠ｍｓｐｔ（ｘｐ）を満たすラベルに対応するメッセージｍｐｑ（ｘｐ）のみを更新すべきメッセージ集合に加えて更新する。
【００４０】
有効ラベル計算部１４は、ラベルごとの収束値を入力とし、（６）式を解くことによって、ノードごとに有効なラベルを出力する。すわなち、収束計算部１３が削減したラベル空間上で、確率伝播法に基づくエネルギー最小化問題を解いて全ノードのエネルギー量が最小となるラベルを、該計算したラベルをノードに有効なラベルとして決定する。
【００４１】
［ラベリング処理］
次に、ラベリング装置１０が実行するラベリング処理について説明する。図２は、ラベリング装置１０が行うラベリング処理の処理手順を示すフローチャートである。
【００４２】
まず、ラベリング装置１０では、ラベリング対象となるグラフｇの入力を受け付ける（ステップＳ１）。この入力情報は、このグラフｇにおけるノード集合とエッジ集合とを含む。そして、繰り返し計算部１１は、繰り返し計算回数（iteration  t）を初期化して０とし（ステップＳ２）、これに伴い、メッセージ集合Ｍｔも初期化され、Ｍ０とされる（ステップＳ３）。
【００４３】
そして、メッセージ計算部１２は、iteration  tにおける有効なメッセージ集合に含まれるメッセージｍｐｑを、（５）式を用いて計算し（ステップＳ４）、収束値計算部１３に出力する。収束値計算部１３は、iteration  t≧１であるか否かを判断する（ステップＳ５）。収束値計算部１３は、iteration  t＜１であると判断した場合（ステップＳ５：Ｎｏ）、ステップＳ８に進み、メッセージ計算部１２が計算したメッセージ量を、更新すべきメッセージ集合に追加する。
【００４４】
一方、収束値計算部１３は、iteration  t≧１であると判断した場合（ステップＳ５：Ｙｅｓ）、ラベルに対応するメッセージ量の変化量を計算する（ステップＳ６）。そして、収束値計算部１３は、計算したメッセージ量の変化量が所定の閾値以下であるか否かを判断する（ステップＳ７）。例えば、収束値計算部１３は、ステップＳ７において、ｍｓｐｔ−１（ｘｐ）≠ｍｓｐｔ（ｘｐ）（（７）式参照）であるか否かを判断し、収束ラベルの検出を行う。
【００４５】
収束値計算部１３は、メッセージ量の変化量が所定の閾値以下でないと判断した場合（ステップＳ７：Ｎｏ）、このactiveなラベルｘｐに対応するメッセージｍｐｑ（ｘｐ）については、更新すべきメッセージ集合に追加する（ステップＳ８）。例えば、収束値計算部１３は、ステップＳ７において、ｍｓｐｔ−１（ｘｐ）≠ｍｓｐｔ（ｘｐ）（（７）式参照）である場合には、このメッセージｍｐｑ（ｘｐ）については、更新すべきメッセージ集合に追加する。そして、収束値計算部１３は、activeなラベルに対するメッセージのみを、以降の計算対象として更新する（ステップＳ９）。
【００４６】
一方、収束値計算部１３は、メッセージ量の変化量が所定の閾値以下であると判断した場合（ステップＳ７：Ｙｅｓ）、このラベルｘｐに対応するメッセージの計算が収束したと判断する（ステップＳ１０）。そして、収束値計算部１３は、該ラベルｘｐに対応付けられる、以降のメッセージ量の計算を省略してラベル空間を削除する（ステップＳ１１）。例えば、収束値計算部１３は、ステップＳ７において、ｍｓｐｔ−１（ｘｐ）≠ｍｓｐｔ（ｘｐ）（（７）式参照）でない場合には、このメッセージｍｐｑ（ｘｐ）については、該ラベルｘｐに対応付けられる、以降のメッセージ量の計算を省略する。
【００４７】
そして、繰り返し計算部１１は、次のメッセージ量の計算対象があるか否かを判断する（ステップＳ１２）。繰り返し計算部１１は、次のメッセージ量の計算対象があると判断した場合（ステップＳ１２：Ｙｅｓ）、ステップＳ４に戻り、ステップＳ４以降の処理をメッセージ計算部１２、収束値計算部１３及び有効ラベル計算部１４に実行させる。
【００４８】
一方、繰り返し計算部１１は、次のメッセージがないと判断した場合（ステップＳ１２：Ｎｏ）、全てのメッセージ集合について計算したかを判断する（ステップＳ１３）。そして、繰り返し計算部１１は、全てのメッセージ集合について計算していないと判断した場合（ステップＳ１３：Ｎｏ）、ステップＳ４に戻り、ステップＳ４以降の処理をメッセージ計算部１２、収束値計算部１３及び有効ラベル計算部１４に実行させる。
【００４９】
繰り返し計算部１１は、全てのメッセージ集合について計算したと判断した場合（ステップＳ１３：Ｙｅｓ）、iteration  t=Tであるか否かを判断する（ステップＳ１４）。繰り返し計算部１１は、t=Tでないと判断した場合（ステップＳ１４：Ｎｏ）、iteration  tに１を加算して（ステップＳ１５）、ステップＳ４に戻り、ステップＳ４以降の処理をメッセージ計算部１２、収束値計算部１３及び有効ラベル計算部１４に実行させる。
【００５０】
これに対し、t=Tであると繰り返し計算部１１が判断した場合（ステップＳ１４：Ｙｅｓ）、有効ラベル計算部１４は、収束計算部１３が削減したラベル空間上で、全ノードのエネルギー量が最小となるラベルを計算し、該計算したラベルをノードに有効なラベルとして決定する有効ラベル計算処理を行い（ステップＳ１６）、処理結果を出力する。
【００５１】
［アルゴリズム］
次に、ラベリング装置１０が使用するアルゴリズムについて説明する。図３は、ラベリング装置１０が使用するアルゴリズムを示す図である。図３に示すアルゴリズムは、図２のラベリング処理のフローチャートが示す処理に対応する。
【００５２】
まず、アルゴリズムは、グラフｇ＝（ν，ε）を入力（input）とし、グラフｇにおける最適なラベル集合Ｌを出力（output）とする。そして、グラフｇにおけるノード集合νに含まれる各ノードｐに対して、データ項Ｄｐを計算する（図３の１行目）。そして、メッセージ集合をＭ０に初期化する（図３の２行目）。図３の２行目は、図２に示すステップＳ３に該当する。
【００５３】
続いて、iteration=tにおける有効なメッセージ集合に含まれるｍｐｑを演算し(図３の４行目)、iteration=t≧１である場合には（図３の５行目）、（７）式より収束ラベルの検出を行う(図３の６，７行目)。図３の４行目は、図２に示すステップＳ４に該当し、図３の５行目は、図２のステップＳ５：Ｙｅｓに相当し、図３の６，７行目は、図３のステップＳ６及びステップＳ７：Ｎｏに相当する。ｍｓｐｔ−１（ｘｐ）≠ｍｓｐｔ（ｘｐ）である場合には、このactiveなラベルｘｐに対応するメッセージｍｐｑ（ｘｐ）については、更新すべきメッセージ集合に追加する（図３の７〜９行目）。図３の７〜９行目は、図２のステップＳ８に該当する。
【００５４】
そして、activeなラベルに対するメッセージのみを、以降の計算対象として更新する（図３の１２行目）。図３の１２行目は、図２のステップＳ９に該当する。全てのメッセージ集合について、以上を繰り返す（図３の４〜１３行目）。そして、iteration=tからＴまで繰り返した後（図３の３〜１４行目）、全てのノードについてエネルギーが最小となるラベルｘを（６）式を用いて割り当てる（図３の１５〜１７行目）。図３の１５〜１７行目は、図２のステップＳ１６に該当する。
【００５５】
［実施の形態の効果］
本実施の形態では、確率伝播法に基づく収束計算を行ってグラフ上の各ノードにラベル割り当てを行う場合に、グラフ上に伝播させるメッセージ量を計算する。そして、本実施の形態では、ラベルに対応するメッセージ量の変化量を計算し、メッセージ量の変化量が所定値以下となった場合には、該ラベルに関するメッセージ量の計算が収束したと判断して該ラベルに関する以降のメッセージ量の計算を省略してラベル空間を削減する。続いて、本実施の形態では、削減したラベル空間上で、全ノードのエネルギー量が最小となるラベルを計算し、該計算したラベルをノードに有効なラベルとして決定する。
【００５６】
したがって、本実施の形態によれば、メッセージ計算対象として追加する必要がないラベルに対応するメッセージを、収束計算に基づいて検出し、以降のメッセージ計算から省略する。言い換えると、本実施の形態では、収束計算に基づいて、ノードごとに有効なラベル数を適応的に変化させることによって、精度を担保しながら、高速化を可能とする。
【００５７】
そして、本実施の形態によれば、収束計算に基づいて、ノードごとに有効なラベル数を自動的に変化させるため、従来必要であったユーザによるパラメータ（top-k）調整処理は不要である。
【００５８】
［実施の形態のシステム構成について］
図１に示したラベリング装置１０の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、ラベリング装置１０の機能の分散および統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散または統合して構成することができる。
【００５９】
また、ラベリング装置１０においておこなわれる各処理は、全部または任意の一部が、ＣＰＵ（Central  Processing  Unit）およびＣＰＵにより解析実行されるプログラムにて実現されてもよい。また、ラベリング装置１０においておこなわれる各処理は、ワイヤードロジックによるハードウェアとして実現されてもよい。
【００６０】
また、実施の形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的に行うこともできる。もしくは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上述および図示の処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて適宜変更することができる。
【００６１】
［プログラム］
図４は、プログラムが実行されることにより、ラベリング装置１０が実現されるコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。
【００６２】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１及びＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。
【００６３】
ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、ラベリング装置１０の各処理を規定するプログラムは、コンピュータ１０００により実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、ラベリング装置１０における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤ（Solid  State  Drive）により代替されてもよい。
【００６４】
また、上述した実施の形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して実行する。
【００６５】
なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３及びプログラムデータ１０９４は、ネットワーク（ＬＡＮ、ＷＡＮ等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３及びプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【００６６】
以上、本発明者によってなされた発明を適用した実施の形態について説明したが、本実施の形態による本発明の開示の一部をなす記述及び図面により本発明は限定されることはない。すなわち、本実施の形態に基づいて当業者等によりなされる他の実施の形態、実施例及び運用技術等は全て本発明の範疇に含まれる。
【符号の説明】
【００６７】
１０  ラベリング装置
１１  繰り返し計算部
１２  メッセージ計算部
１３  収束値計算部
１４  有効ラベル計算部
【図１】
2018014040.tif 000011
【図２】
2018014040.tif 000012
【図３】
2018014040.tif 000013
【図４】
2018014040.tif 000014