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