(57)【要約】【課題】外部変数を付加することなしに、エネルギーを効率よく低階劣モジュラエネルギーに変換して最小化する。【解決手段】  エネルギー変換部２４は、エネルギーのデータ表現の中から２次以上の項を１つ選び、２次以上の項に含まれる各変数が取りうる値の組み合わせのうち、エネルギーＥの最小化配置の一部でない可能性が高い変数の値の組み合わせを、２次以上の項の係数と、変数の値が１になる個数の偶奇とに基づいて選択する。そして、２次以上の項の係数と、変数の値の組み合わせとから、変換前のエネルギーを、最小化を難しくする項を減らしたエネルギーに変換する。これにより、外部変数を付加することなしに、エネルギーを効率よく最小化のより容易なエネルギーに変換でき、これを最小化できる。【選択図】図１
2015190593.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータによって実行される、多項式によって表わすことが可能なエネルギーを処理する情報処理方法であって、
記憶手段に格納されている、前記エネルギーのデータ表現の中から２次以上の項を１つ選択し、
前記データ表現の中で、前記２次以上の項に含まれる各変数が取りうる値の組み合わせのうち、前記エネルギーの最小化配置の一部でない可能性が高い変数の値の組み合わせを、前記２次以上の項の係数と、前記変数の値が１になる個数の偶奇とに基づいて選択し、
前記２次以上の項の係数と、前記変数の値の組み合わせとから、前記エネルギーを、前記２次以上の項を縮減したエネルギーに変換し、
該変換したエネルギーに対して所定のエネルギー最小化法を適用することにより、前記エネルギーが最小となる各変数を設定することを特徴とする情報処理方法。
【請求項２】
前記２次以上の項をαｘ１…ｘｄとすると、
実数ｑを選択し、
前記変数の値の組み合わせを、ｘ１＝ｕ１，…，ｘｄ＝ｕｄとしたときに、前記エネルギーを表す多項式に次の数１を加えて、
【数１】
2015190593.tif 000032
前記エネルギーを、前記２次以上の項を縮減したエネルギーに変換することを特徴とする請求項１記載の情報処理方法。
【請求項３】
前記データ表現の中で、変数ｘ１，…，ｘｄの少なくとも一つを含む項の和を第１の関数とし、
前記変数ｘ１，…，ｘｄの値の組み合わせについての第１の条件を、前記２次以上の項の係数αが０よりも小さければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と同じであること、また前記２次以上の項の係数αが０よりも大きければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と逆になることとし、
前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄについての第２の条件を、別な前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｖ１，…，ｘｄ＝ｖｄであって、組み合わせｘ１＝ｖ１，…，ｘｄ＝ｖｄを満たす配置での前記第１の関数の最大値を、組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄを満たす配置での前記第１の関数の最小値から減じた差であるギャップが正であるものが存在することとしたときに、
前記第２の条件を満たす前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄであって、前記第１の条件を満たすか、前記２次以上の項の係数αの絶対値｜α｜より大きい前記ギャップを持つものが存在するか否かを判定し、
もし存在すれば、前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄを、前記変数の値の組み合わせとして選択し、前記実数ｑとして、該組み合わせが前記第１の条件を満たすならば｜α｜を選択し、満たさないならば−｜α｜を選択することを特徴とする請求項２記載の情報処理方法。
【請求項４】
前記データ表現の中で、ｘ１，…，ｘｄ以外の変数を含まない項の和を第２の関数としたときに、
前記２次以上の項の係数αが０よりも小さければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と同じになるような、また前記２次以上の項の係数αが０よりも大きければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と逆になるような組み合わせの中から、
前記変数ｘ１，…，ｘｄの値の組み合わせで、前記第２の関数の値が最大になるものを、前記変数の値の組み合わせとして選択し、前記実数ｑとして前記２次以上の項の係数αの絶対値｜α｜を選択することを特徴とする請求項２記載の情報処理方法。
【請求項５】
前記変数の値の組み合わせをランダムに選択することを特徴とする請求項２記載の情報処理方法。
【請求項６】
多項式によって表わすことが可能なエネルギーを処理する情報処理装置であって、
前記エネルギーのデータ表現を格納する記憶手段と、
前記データ表現の中から２次以上の項を１つ選択し、前記データ表現の中で、前記２次以上の項に含まれる各変数が取りうる値の組み合わせのうち、前記エネルギーの最小化配置の一部でない可能性が高い変数の値の組み合わせを、前記２次以上の項の係数と、前記変数の値が１になる個数の偶奇とに基づいて選択し、前記２次以上の項の係数と、前記変数の値の組み合わせとから、前記エネルギーを、前記２次以上の項を縮減したエネルギーに変換するエネルギー変換手段と、
該変換したエネルギーに対して所定のエネルギー最小化法を適用することにより、前記エネルギーが最小となる各変数を設定するエネルギー最小化手段と、
を備えたことを特徴とする情報処理装置。
【請求項７】
前記２次以上の項をαｘ１…ｘｄとすると、
実数ｑを選択し、
前記変数の値の組み合わせを、ｘ１＝ｕ１，…，ｘｄ＝ｕｄとしたときに、前記エネルギーを表す多項式に次の数２を加えて、
【数２】
2015190593.tif 000033
前記エネルギーを、前記２次以上の項を縮減したエネルギーに変換するように、前記エネルギー変換手段を構成したことを特徴とする請求項６記載の情報処理装置。
【請求項８】
前記データ表現の中で、変数ｘ１，…，ｘｄの少なくとも一つを含む項の和を第１の関数とし、
前記変数ｘ１，…，ｘｄの値の組み合わせについての第１の条件を、前記２次以上の項の係数αが０よりも小さければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と同じであること、また前記２次以上の項の係数αが０よりも大きければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と逆になることとし、
前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄについての第２の条件を、別な前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｖ１，…，ｘｄ＝ｖｄであって、組み合わせｘ１＝ｖ１，…，ｘｄ＝ｖｄを満たす配置での前記第１の関数の最大値を、組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄを満たす配置での前記第１の関数の最小値から減じた差であるギャップが正であるものが存在することとしたときに、
前記第２の条件を満たす前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄであって、前記第１の条件を満たすか、前記２次以上の項の係数αの絶対値｜α｜より大きい前記ギャップを持つものが存在するか否かを判定し、
もし存在すれば、前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄを、前記変数の値の組み合わせとして選択し、前記実数ｑとして、該組み合わせが前記第１の条件を満たすならば｜α｜を選択し、満たさないならば−｜α｜を選択するように、前記エネルギー変換手段を構成したことを特徴とする請求項７記載の情報処理装置。
【請求項９】
前記データ表現の中で、ｘ１，…，ｘｄ以外の変数を含まない項の和を第２の関数としたときに、
前記２次以上の項の係数αが０よりも小さければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と同じになるような、また前記２次以上の項の係数αが０よりも大きければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と逆になるような組み合わせの中から、
前記変数ｘ１，…，ｘｄの値の組み合わせで、前記第２の関数の値が最大になるものを、前記変数の値の組み合わせとして選択し、前記実数ｑとして前記２次以上の項の係数αの絶対値｜α｜を選択するように、前記エネルギー変換手段を構成したことを特徴とする請求項７記載の情報処理装置。
【請求項１０】
前記変数の値の組み合わせをランダムに選択するように、前記エネルギー変換手段を構成したことを特徴とする請求項７記載の情報処理装置。
【請求項１１】
請求項１から５のいずれか１項に記載の情報処理方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多項式によって表わすことが可能なエネルギーを、新たな変数を導入することなく、高階な項や非劣モジュラな項を縮減することにより、より最小化しやすく変換するための情報処理方法および情報処理装置に関する。
【背景技術】
【０００２】
劣モジュラな１階２値マルコフ確率場のエネルギーは、グラフカットにより大域最小化できることから、広く応用されているが、近年、１階でなく高階のマルコフ確率場や、劣モジュラでないマルコフ確率場のように、最小化が難しいマルコフ確率場がますます重要視されるようになってきている。高階マルコフ確率場の重要性は昔から理解されており、その活用方法について最初の試みはあったものの、様々なタイプの高階マルコフ確率場エネルギーの最小化法の研究やその応用は、近年急速な発展を遂げてきた。特に高階エネルギーの最小化は、コンピュータビジョンや画像処理で最近注目されている。また、かつて最小化が望めなかった非劣モジュラなマルコフ確率場の研究も近年、その最小解についての情報を得たり、近似的に最小化したりするなどの発展を遂げている。【０００３】
例えば画像処理の分野では、画像の領域分割（セグメンテーション）などのために、画像をドット単位の格子構造とするマルコフ確率場の最大事後確率推定問題のエネルギー最小化問題として解く手法が知られており、具体的には、劣モジュラな１階２値エネルギーを大域最小化できるグラフカット（例えば、非特許文献１を参照）をはじめ、信念伝播法（例えば、非特許文献２を参照）や、ツリー重み再配分メッセージ伝達法（例えば、非特許文献３を参照）などが提案されている。これらの手法では、エネルギーを比較的効率良く最小化することができるが、使用できるエネルギーの形は限られている。【０００４】
また、劣モジュラな１階マルコフ確率場に変換可能で、グラフカットで効率的に最小化できる特別な形を持った高階マルコフ確率場も存在するが、データから学習されるField of Expertsなどの洗練された事前確率分布モデルを利用するためには、一般の高階マルコフ確率場や、それを１階に変換後生じる非劣モジュラなマルコフ確率場のエネルギーを最小化する必要がある。【０００５】
一般の高階マルコフ確率場を近似的に最小化することが可能な方法の一つに、グラフカット法の拡張がある。単項、あるいは二項のポテンシャルを持つ１階マルコフ確率場では、２値ラベルを持つ劣モジュラエネルギー関数をグラフカットによって最小化できる。またＱＰＢＯアルゴリズム（Quadratic Pseudo-Boolean Optimization algorithm、非特許文献４、５を参照）により、非劣モジュラエネルギー関数最小化問題を部分的に解くことができる。多値ラベルを持つエネルギー関数は、“移動アルゴリズム”（move-making algorithm）によって近似的に最小化され、当該アルゴリズムは、２値ラベルの問題を設定し、グラフカット法で問題を解くことによって、解を逐次的に更新していく。α拡張アルゴリズムやその一般化である融合移動アルゴリズムは、この範疇に入る。【０００６】
これらの方法を高階エネルギーまで拡張するために、２値ラベルを持つ高階ポテンシャルを低階に縮減する方法がこれまで提案されてきた（例えば、非特許文献６、特許文献１、特許文献２を参照）。そのアイデアは、エネルギーの階数を縮減するために新たな変数を導入することである。以下で項とは、エネルギーを展開された多項式として表した場合の単項式を指す。エネルギーの階数と、それを多項式で表したときの次数は、１階が２次、２階が３次というように１だけずれて対応している。高階および高次とはどちらも２階以上、つまり３次以上を指す。また、１階、すなわち２次の項は、その係数が負であるとき劣モジュラ、正であるとき非劣モジュラな項という。１階エネルギーは１階の項がすべて劣モジュラなとき、劣モジュラなエネルギーという。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１０−２８７０９１号公報
【特許文献２】特開２０１２−２７７５５号公報
【非特許文献】
【０００８】
【非特許文献１】Y.Boykov,O.Veksler,R.Zabih. "Fast Apporoximate Energy Minimization via Graph Cuts." IEEE Transactions on Pattern Analysis and Machine Intelligence 23:1222-1239:2001.
【非特許文献２】P.Felzenszwalb and D.Huttenlocher."Efficient Belief Propagation for Early Vision." International Journal of Computer Vision 70:41-54,2006.
【非特許文献３】V.Kolmogorov. "Convergent Tree-Reweighted Message Passing for Energy Minimization." IEEE Transactions on Pattern Analysis and Machine Intelligence 28(10):1568-1583,2006.
【非特許文献４】Endre Boros, Peter L. Hammer, Richard Sun, Gabriel Tavares, A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO), Discrete Optimization, Volume 5, Issue 2, May 2008, Pages 501-529.
【非特許文献５】E. Boros, P. L. Hammer, G. Tavares. "Preprocessing of unconstrained quadratic binary optimization", Rutcor Research Report RRR 10-2006, Rutcor Research Report April, 2006, 2
【非特許文献６】D.Freedman and P.Drineas."Energy minimization via graph cuts: Settling what is possible." Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR2005) II:939-946,2005.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従来技術における高階エネルギーの縮減方法では、高階の項を１階の項に縮減するために新たな変数を導入する必要がある。変数が多くなるということは、最小化が難しくなることを意味するので、新しい変数を導入するのは都合が悪い。実際、従来技術においては、一般の高階ポテンシャルを縮減させるために必要な変数の数は、階数が上がるにつれて指数関数的に多くなるので、当該変数の数が律速因子となってしまい、記憶容量および計算処理量において高コストが要求される問題を引き起こす。また、１階であっても、非劣モジュラな項を含むエネルギーについては、ＱＰＢＯアルゴリズム等で、最小解について一定の情報を得ることはできるが、必ず最小解が得られるわけではない。【００１０】
そこで本発明は上記問題点に鑑み、エネルギーの高階項や非劣モジュラ項のような、エネルギー最小化を難しくしている項を、最小解を変えないまま、また新たな変数を導入することなく、縮減することが可能な情報処理方法、情報処理装置およびそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明では、新たな変数を導入することなしに、与えられたエネルギーの最小解を変えないまま、高階項や１階非劣モジュラ項を縮減するための方法、装置、およびそのプログラムを提案する。各項について縮減できるための条件を探しだし、その性質を利用するためのアルゴリズムを有する方法、装置やプログラムを提示する。また、当該条件をチェックすることなしに、それらの項を縮減させるような近似も提案する。【００１２】
すなわち本発明は、コンピュータによって実行される、多項式によって表わすことが可能なエネルギーを処理する情報処理方法であって、
記憶手段に格納されている、前記エネルギーのデータ表現の中から２次以上の項を１つ選択し、
前記データ表現の中で、前記２次以上の項に含まれる各変数が取りうる値の組み合わせのうち、前記エネルギーの最小化配置の一部でない可能性が高い変数の値の組み合わせを、前記２次以上の項の係数と、前記変数の値が１になる個数の偶奇とに基づいて選択し、
前記２次以上の項の係数と、前記変数の値の組み合わせとから、前記エネルギーを、前記２次以上の項を縮減したエネルギーに変換し、
該変換したエネルギーに対して所定のエネルギー最小化法を適用することにより、前記エネルギーが最小となる各変数を設定することを特徴とする。【００１３】
こうした本発明の情報処理方法では、前記２次以上の項をαｘ１…ｘｄとすると、
実数ｑを選択し、
前記変数の値の組み合わせを、ｘ１＝ｕ１，…，ｘｄ＝ｕｄとしたときに、前記エネルギーを表す多項式に次の数１を加えて、
前記エネルギーを、前記２次以上の項を縮減したエネルギーに変換する。【００１４】
【数１】
2015190593.tif 000003
【００１５】
特に、本発明の情報処理方法では、前記データ表現の中で、変数ｘ１，…，ｘｄの少なくとも一つを含む項の和を第１の関数とし、
前記変数ｘ１，…，ｘｄの値の組み合わせについての第１の条件を、前記２次以上の項の係数αが０よりも小さければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と同じであること、また前記２次以上の項の係数αが０よりも大きければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と逆になることとし、
前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄについての第２の条件を、別な前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｖ１，…，ｘｄ＝ｖｄであって、組み合わせｘ１＝ｖ１，…，ｘｄ＝ｖｄを満たす配置での前記第１の関数の最大値を、組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄを満たす配置での前記第１の関数の最小値から減じた差であるギャップが正であるものが存在することとしたときに、
前記第２の条件を満たす前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄであって、前記第１の条件を満たすか、前記２次以上の項の係数αの絶対値｜α｜より大きい前記ギャップを持つものが存在するか否かを判定し、
もし存在すれば、前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄを、前記変数の値の組み合わせとして選択し、前記実数ｑとして、該組み合わせが前記第１の条件を満たすならば｜α｜を選択し、満たさないならば−｜α｜を選択する。【００１６】
代わりに、本発明の情報処理方法では、前記データ表現の中で、ｘ１，…，ｘｄ以外の変数を含まない項の和を第２の関数としたときに、
前記２次以上の項の係数αが０よりも小さければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と同じになるような、また前記２次以上の項の係数αが０よりも大きければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と逆になるような組み合わせの中から、
前記変数ｘ１，…，ｘｄの値の組み合わせで、前記第２の関数の値が最大になるものを、前記変数の値の組み合わせとして選択し、前記実数ｑとして前記２次以上の項の係数αの絶対値｜α｜を選択してもよい。【００１７】
代わりに、本発明の情報処理方法では、前記変数の値の組み合わせをランダムに選択してもよい。【００１８】
また本発明は、多項式によって表わすことが可能なエネルギーを処理する情報処理装置であって、
前記エネルギーのデータ表現を格納する記憶手段と、
前記データ表現の中から２次以上の項を１つ選択し、前記データ表現の中で、前記２次以上の項に含まれる各変数が取りうる値の組み合わせのうち、前記エネルギーの最小化配置の一部でない可能性が高い変数の値の組み合わせを、前記２次以上の項の係数と、前記変数の値が１になる個数の偶奇とに基づいて選択し、前記２次以上の項の係数と、前記変数の値の組み合わせとから、前記エネルギーを、前記２次以上の項を縮減したエネルギーに変換するエネルギー変換手段と、
該変換したエネルギーに対して所定のエネルギー最小化法を適用することにより、前記エネルギーが最小となる各変数を設定するエネルギー最小化手段と、を備えている。【００１９】
すなわち本発明は、前記２次以上の項をαｘ１…ｘｄとすると、
実数ｑを選択し、
前記変数の値の組み合わせを、ｘ１＝ｕ１，…，ｘｄ＝ｕｄとしたときに、前記エネルギーを表す多項式に次の数２を加えて、
前記エネルギーを、前記２次以上の項を縮減したエネルギーに変換するように、前記エネルギー変換手段を構成している。【００２０】
【数２】
2015190593.tif 000004
【００２１】
特に、本発明の情報処理装置では、前記データ表現の中で、変数ｘ１，…，ｘｄの少なくとも一つを含む項の和を第１の関数とし、
前記変数ｘ１，…，ｘｄの値の組み合わせについての第１の条件を、前記２次以上の項の係数αが０よりも小さければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と同じであること、また前記２次以上の項の係数αが０よりも大きければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と逆になることとし、
前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄについての第２の条件を、別な前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｖ１，…，ｘｄ＝ｖｄであって、組み合わせｘ１＝ｖ１，…，ｘｄ＝ｖｄを満たす配置での前記第１の関数の最大値を、組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄを満たす配置での前記第１の関数の最小値から減じた差であるギャップが正であるものが存在することとしたときに、
前記第２の条件を満たす前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄであって、前記第１の条件を満たすか、前記２次以上の項の係数αの絶対値｜α｜より大きい前記ギャップを持つものが存在するか否かを判定し、
もし存在すれば、前記変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄを、前記変数の値の組み合わせとして選択し、前記実数ｑとして、該組み合わせが前記第１の条件を満たすならば｜α｜を選択し、満たさないならば−｜α｜を選択するように、前記エネルギー変換手段を構成している。【００２２】
代わりに、本発明の情報処理装置では、前記データ表現の中で、ｘ１，…，ｘｄ以外の変数を含まない項の和を第２の関数としたときに、
前記２次以上の項の係数αが０よりも小さければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と同じになるような、また前記２次以上の項の係数αが０よりも大きければ、前記変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と逆になるような組み合わせの中から、
前記変数ｘ１，…，ｘｄの値の組み合わせで、前記第２の関数の値が最大になるものを、前記変数の値の組み合わせとして選択し、前記実数ｑとして前記２次以上の項の係数αの絶対値｜α｜を選択するように、前記エネルギー変換手段を構成してもよい。【００２３】
代わりに、本発明の情報処理装置では、前記変数の値の組み合わせをランダムに選択するように、前記エネルギー変換手段を構成してもよい。【００２４】
さらに、上記記載の情報処理方法をコンピュータに実行させるためのプログラムとして、本発明を提供してもよい。
【発明の効果】
【００２５】
上述した本発明の情報処理方法、情報処理装置およびそのプログラムでは、次のような効果が発揮される。【００２６】
処理対象が高階エネルギーであれば、外部の変数を付加せずに、２次以下の項のみからなる、或いは３次以上の項がより少ない、同値なエネルギーに変換できる。その変換後のエネルギーをさらに、あるいは処理対象が最初から１階のエネルギーだった場合に、外部の変数を付加せずに、劣モジュラな１階の項のみからなる、或いは非劣モジュラな１階の項がより少ない、同値なエネルギーに変換できる。【００２７】
外部の変数を付加しないので、従来手法に比べて使用メモリが少なく、より高速に処理できる利点がある。【００２８】
必ずしもすべての３次以上の項や非劣モジュラな項をなくすことができない場合でも、本発明の方法や装置を適用した後に従来手法を用いることで、従来手法のみを使った場合よりも使用メモリが少なく、より高速に処理できる利点がある。【００２９】
よって本発明では、エネルギーの高階項や非劣モジュラ項のような、エネルギー最小化を難しくしている項を、新たな変数を導入することなく削減することが可能となり、従来手法に比べて低い記憶容量および計算処理量コストで、高階エネルギーの最小化を実現することができる。
【図面の簡単な説明】
【００３０】
【図１】本発明の一実施例としての情報処理装置の構成の概略を示す構成図である。
【図２】画素に割り当てるラベルのパターンの一例を示す説明図である。
【図３】コンピュータ２０により実行される高階エネルギー設定処理の一例を示すフローチャートである。
【図４】画素のデータ値ＤとエネルギーＥ（Ｄ）との関係を示す説明図である。
【図５】本発明の実施例１において、コンピュータ２０により実行されるエネルギー変換処理の一例を示すフローチャートである。
【図６】同上、除外可能な局所配置を探し出すための詳細なアルゴリズムのフローチャートである。
【図７】本発明の実施例２において、コンピュータ２０により実行されるエネルギー変換処理の一例を示すフローチャートである。
【図８】本発明の実施例３において、コンピュータ２０により実行されるエネルギー変換処理の一例を示すフローチャートである。
【図９】実験結果として、第１〜第５の方法におけるエネルギー縮減後の一階エネルギーの変数の平均数を示すグラフである。
【図１０】同上、（Ａ）は反復数に対するエネルギーのプロット、（Ｂ）は時間に対するエネルギーのプロット、（Ｃ）はラベルされた画素数の割合のプロットを示すグラフである。
【発明を実施するための形態】
【００３１】
以下、添付図面を参照しながら、本発明における情報処理装置の好ましい実施形態について、適宜実施例を用いて説明する。
【００３２】
図１は、本発明の各実施例に共通する情報処理装置の構成の概略を示す構成図である。各実施例における情報処理装置は、図示しないがＣＰＵやＲＯＭ，ＲＡＭ，入出力処理回路（入出力インターフェース）、ハードディスク等で構成されており、キーボード４０、マウス５０などが接続された汎用のコンピュータ２０である。このコンピュータは、デジタルカメラやＣＴ（Computed Tomography）、ＭＲＩ（Magnetic Resonance Imaging）、ＰＥＴ（Positron Emission Tomography）などの撮像装置や、画像データを記憶する記憶装置に入力処理回路を介して接続されると共に、ディスプレイ３０やプリンタなどの出力機器に出力処理回路を介して接続されている。実施例では、制御手段たるコンピュータ２０には画像処理用プログラムがインストールされており、これにより画像処理装置として機能する。
【００３３】
例えば、ＣＴやＭＲＩ、ＰＥＴなどから得られるデータは、３次元の格子点に数値（データ値）を与えるものである。データ値は例えばＣＴなら空間内の各格子点がどれだけＸ線を吸収するかを表わす。２次元の断面画像なら各点の値に応じて色を変えれば全体を見ることができるが、３次元のデータは一望するのは困難である。したがって、例えば、ＣＴ画像のうち骨だけを見たいなら骨の部分だけを残し、他の部分は透明にして、３次元グラフィックスを表示することになる。このためには、元画像を骨の部分とそれ以外の部分とに分割する必要がある（画像分割問題）。これは、値０が骨の部分で値１がそれ以外を表わすというように、各格子点に値０か値１かのいずれかのラベルを与えるラベル割付問題として考えることができる。この場合、ある閾値を定めてデータ値が閾値よりも大きい点は値０を割り当て閾値以下の点は値１を割り当てものとすると、ノイズなどにより、ディスプレイ３０に表示される画像の形状が荒いものとなる。このため、一般には隣接する格子点間ではあまり激しく値０と値１とが入れ替わらないように、即ち境界がなめらかになるような傾向をもたせる。このための手法の一つがエネルギー最小化による方法である。以下、実施例では、人のＣＴ画像に対して骨に該当する画素に値０のラベルを割り当てそれ以外の部分の画素に値１のラベルを割り当てることにより領域を分割するような画像分割問題を、エネルギー最小化法により解く場合を例として説明する。
【００３４】
コンピュータ２０は、その機能ブロックとしては、画像データの領域分割をエネルギー最小化法を用いて処理するための多項式（高階エネルギー）を設定する高階エネルギー設定部２２と、外部変数を付加することなく、設定した高階エネルギーを、より低い階数のエネルギーに変換するためのエネルギー変換部２４と、変換後のエネルギーが最小となるように、各画素にそれぞれ値０か値１のラベルを割り当てて、画像の領域分割を行なうエネルギー最小化部２６とを備え、これらは、ＣＰＵやＲＯＭ、ＲＡＭ、ハードディスクなどのハードウェアと画像処理用プログラムとが協働することで機能が実現される。
【００３５】
高階エネルギー設定部２２は、各画素に対して割り当てる値０か値１のラベルを２値変数として上述した領域分割問題を解くための高次の多項式を設定する第１演算手段となる処理部であり、実施例では、画像データの各画素１点だけに基づいてエネルギーを設定する１次の項と、隣接する画素２点のパターン（図２（Ａ）参照）に基づいてエネルギーを設定する２次の項と、隣接する２×２の画素４点のパターン（図２（Ｂ）参照）に基づいてエネルギーを設定する４次の項との和により設定する。このような高階エネルギーのデータ表現は、コンピュータ２０の記憶手段であるハードディスクなどに格納記憶される。
【００３６】
エネルギー変換部２４は、コンピュータ２０の記憶手段に格納したデータ表現を読み出して、２値変数からなる３次以上（２階以上）のエネルギー多項式を、２次（１階）以下の項のみからなる、或いは３次以上の項がより少ない、同値なエネルギー多項式に変換する第２演算手段となる処理部として構成される。このエネルギー変換部２４の処理手順については、後程詳しく説明する。
【００３７】
エネルギー最小化部２６は、エネルギー変換部２４で得られた値０か値１の２値変数をもつ２次の多項式として表わされる変換後のエネルギーが、最小となる変数を見つける第３演算手段となる処理部として構成されており、ここでの処理アルゴリズムとしては、例えば、グラフカット法や信念伝播法，ツリー重み再配分メッセージ伝達法などを用いることができる。
【００３８】
次に、こうして構成された実施例の情報処理装置の動作、特に、高階エネルギー設定部２２の動作とエネルギー変換部２４の動作について説明する。まず、高階エネルギー設定部２２の動作について説明する。図３は、コンピュータ２０の第１演算手段により実行される高階エネルギー設定処理の一例を示すフローチャートである。
【００３９】
高階エネルギー設定処理では、まず、画像データの各画素の１点のみに依存する項を次の数３により設定する（ステップＳ１００）。ここで、数３中の「Ｘu」は画素ｕに対して割り当てるラベルとしての２値変数であり、「ａ１」，「ａ2」は実数係数である。実数係数ａ1は、Ｘu＝０即ち画素ｕが骨であるとしたときのエネルギー値Ｅ0（Ｄ）であり、画素ｕのデータ値Ｄが骨である可能性を示す確率をＰ0（Ｄ）としたときに、ａ1即ちＥ0（Ｄ）が−ｌｏｇＰ0（Ｄ）となるよう設定し、同様に、実数係数ａ2は、画素ｕのデータ値Ｄが骨でない可能性を示す確率をＰ1（Ｄ）としたときに、ａ2即ちＥ1（Ｄ）が−ｌｏｇＰ1（Ｄ）となるよう設定する。即ち、画素ｕが骨である可能性が高いほどＸu＝０としたときのエネルギーが小さくなるように、また画素ｕが骨でない可能性が高いほどＸu＝１としたときのエネルギーが小さくなるように、実数係数ａ1，ａ2を設定するのである。勿論、画素ｕが骨である可能性が高ければＸu＝０としたときのエネルギーが小さくなり、画素ｕが骨でない可能性が高ければＸu＝１としたときのエネルギーが小さくなればよいから、上述した手法に限定されるものではなく、例えば、データ値Ｄ（あるいは確率Ｐ）とエネルギーＥとの関係を予め求めてマップとしてＲＯＭに記憶しておき、データ値Ｄが与えられたときにマップから対応するエネルギーＥを導出し、導出したエネルギーＥに基づいて設定するものとしてもよい。データ値ＤとエネルギーＥとの関係の一例を、図４に示す。
【００４０】
【数３】
2015190593.tif 000005
【００４１】
続いて、画像データの上下あるいは左右に隣接する２画素に依存する項を、次の数４により設定する（ステップＳ１１０）。ここで、数４中の「Ｘu」，「Ｘv」は、隣接する画素ｕ，ｖに対してそれぞれ割り当てるラベルとしての２値変数であり、「ｂ1〜ｂ4」は、実数係数である。実数係数ｂ1は、Ｘu＝１，Ｘv＝１即ち画素ｕ，ｖが共に骨でないとしたときのエネルギー値Ｅ11（Ｄu，Ｄv）であり、画素ｕ，ｖのデータ値Ｄu，Ｄvが画素ｕ，ｖが共に骨でない可能性を示す確率をＰ11（Ｄu，Ｄv）としたときに、ｂ1即ちＥ11（Ｄu，Ｄv）が−ｌｏｇＰ11（Ｄu，Ｄv）となるように設定するものとした。実数係数ｂ2は、Ｘu＝０，Ｘv＝１即ち画素ｕが骨であり画素ｖが骨でないとしたときのエネルギー値Ｅ01（Ｄu，Ｄv）であり、画素ｕ，ｖのデータ値Ｄu，Ｄvが画素ｕが骨であり画素ｖが骨でない可能性を示す確率をＰ01（Ｄu，Ｄv）としたときに、ｂ2即ちＥ01（Ｄu，Ｄv）が−ｌｏｇＰ01（Ｄu，Ｄv）となるよう設定するものとした。実数係数ｂ3は、Ｘu＝１，Ｘv＝０即ち画素ｕが骨でなく画素ｖが骨であるとしたときのエネルギー値Ｅ10（Ｄu，Ｄv）であり、画素ｕ，ｖのデータ値Ｄu，Ｄvが画素ｕが骨でなく画素ｖが骨である可能性を示す確率をＰ10（Ｄu，Ｄv）としたときに、ｂ3即ちＥ10（Ｄu，Ｄv）が−ｌｏｇＰ10（Ｄu，Ｄv）となるよう設定するものとした。実数係数ｂ4は、Ｘu＝０，Ｘv＝０即ち画素ｕ，ｖが共に骨であるとしたときのエネルギー値Ｅ00（Ｄu，Ｄv）であり、画素ｕ，ｖのデータ値Ｄu，Ｄvが共に骨である可能性を示す確率をＰ00（Ｄu，Ｄv）としたときに、ｂ4即ちＥ00（Ｄu，Ｄv）が−ｌｏｇＰ00（Ｄu，Ｄv）となるよう設定するものとした。なお、この場合も、例えば、データ値Ｄu，Ｄv（あるいは確率）とエネルギーＥとの関係を予め求めてマップとしてＲＯＭに記憶しておき、データ値Ｄu，Ｄvが与えられたときにマップから対応するエネルギーＥを導出し、導出したエネルギーＥに基づいて設定するものとしてもよい。
【００４２】
【数４】
2015190593.tif 000006
【００４３】
そして、画像データの上下左右に隣接する画素４点に依存する項を次の数５により設定する（ステップＳ１２０）。ここで、数５中の「Ｘu」，「Ｘv」，「Ｘs」，「Ｘt」は、隣接する画素ｕ，ｖ，ｓ，ｔに対してそれぞれ割り当てる２値変数であり、「ｃ1〜ｃ16」は、実数係数である。上述したステップＳ１１０と同様に、実数係数ｃ1〜ｃ16は、Ｘu，Ｘv，Ｘs，Ｘtに値０か値１を与えたパターン毎に決定される各画素が、骨であるかないかという組み合わせに対応するエネルギーであり、画素ｕ，ｖ，ｓ，ｔの各データ値Ｄu，Ｄv，Ｄs，Ｄtがその組み合わせである可能性を示す確率が高いほど、エネルギーが小さくなるよう定められる。
【００４４】
【数５】
2015190593.tif 000007
【００４５】
こうして各項を設定すると、各項の和をとると共にこれらを展開することにより４次の多項式を設定して（ステップＳ１３０）、本ルーチンを終了する。これにより、３階のエネルギーが設定される。実施例では、このエネルギーを最小化する各画素に対応した２値変数を見つけることにより、画像データのうち骨の部分とそれ以外の部分とに分割する。
【００４６】
次に、エネルギー変換処理について説明する。本発明の情報処理方法および情報処理装置によれば、高階マルコフ確率場エネルギーのように、多項式によって表わすことが可能なエネルギーを、以下に説明する処理方法で、新たな変数を導入することなく、高階な項や非劣モジュラな項を縮減することにより、より最小化しやすく変換することができる。当該エネルギーの具体的な処理方法を提示する前に、本実施例におけるエネルギー変換アルゴリズムの導入の前提となる理論形式について、以下の数式を参照しながら説明する。
【００４７】
０か１の２値をとるいくつかの変数の実数値関数は擬ブール関数（Pseudo-Boolean Function：ＰＢＦ）と呼ばれ、常に多項式によって表すことができる。ここでは、３変数の擬ブール関数Φ（ｘ，ｙ，ｚ）を２次の多項式に変換する場合を考える。Φ（ｘ，ｙ，ｚ）が、以下の数６のような値ａ〜ｈを得たと仮定する。
【００４８】
【数６】
2015190593.tif 000008
【００４９】
変数がｘ，ｙ，ｚの３つなので、このような形をもつ一般の擬ブール関数は３次であり、当該関数は２階である。当該擬ブール関数は、多項式の形で以下の数７のように書き表せる。
【００５０】
【数７】
2015190593.tif 000009
【００５１】
これを展開すれば、最高次数の項ｘｙｚの係数は以下の数８の通りとなる。
【００５２】
【数８】
2015190593.tif 000010
【００５３】
ｘｙｚは、上記数７の展開における唯一の３次項であるから、ｓが０であるならば、当該多項式は２次式となる。数７の式を用い、ａをａ’＝ａ＋ｓで置き換えることによって、新たな擬ブール関数Φ’（ｘ，ｙ，ｚ）を導入する。関数Φ’（ｘ，ｙ，ｚ）におけるｘｙｚの係数は、次の数９のように表せる。
【００５４】
【数９】
2015190593.tif 000011
【００５５】
したがって、新たな変数を導入することなく、３次多項式の擬ブール関数Φ（ｘ，ｙ，ｚ）が、２次式の擬ブール関数Φ’（ｘ，ｙ，ｚ）に変換された。ただし、変換前の関数と変換後の関数は異なるので、こうした変換が最小化問題の結果に影響しないように注意する必要がある。
【００５６】
関数Φ（ｘ，ｙ，ｚ）が、より大きいエネルギー関数の一部であったと仮定する。この場合の変数ｘ，ｙ，ｚは、問題となっているより多くの変数のうちの、一部の変数を構成する。
【００５７】
このとき、少なくとも全エネルギーの最小解の一部が、ｘ＝０，ｙ＝０，ｚ＝０でなければ、ａにｓを加え、最小解ではない変数配置であるｘ＝０，ｙ＝０，ｚ＝０においてエネルギーの値をｓだけ変化させても、値を上昇させる分には、また下降させるにしても新たに最小解の一部になるほど下降しなければ、最小値は変更を受けない。勿論、エネルギーを変化させる変数配置はｘ＝０，ｙ＝０，ｚ＝０である必要はなく、全エネルギーの最小解すべての一部とならない限り、どの値のときでもよい。
【００５８】
このように、可能なｘ、ｙ、ｚへの値の割り当て方のうち１つを選んで、そのときのΦの値を変化させることで、最高次の係数を０にすることができる。但し、このような処理によって、値の変化によって最小解が変化してしまう可能性もある。これを踏まえ、次に値の変化によって全エネルギーの最小解が変化しないための一般の条件を示していく。
【００５９】
・除外可能な局所配置（Excludable Local Configuration：ＥＬＣ）
要素が０と１である集合をＢ＝｛０，１｝とする。画素などに代表される「位置」の抽象化をサイトと呼び、その（有限）集合をＶとする。以下では、各サイトｉ∈Ｖに０か１の２値をとる変数ｘｉがあると考える。これら変数全てへの値の割り当てを配置とよぶ。つまり、配置はＶからＢへの写像と考えられる。配置全体の集合をＢＶで表す。例えば、配置ｘ∈ＢＶは各サイトｉ∈Ｖにラベルｘｉ∈Ｂを与えるなどと書く。Ｖの部分集合をクリークと呼ぶ。これが上記におけるｘ、ｙ、ｚのような、変数の一部を取り出したものにあたる。クリークＣに対して、ＣからＢへの写像をＣ上の局所配置と呼び、これが上記におけるｘ、ｙ、ｚへの値の割り当てにあたる。クリークＣ上の局所配置全体の集合をＢＣとする。例えば、Ｃ上の局所配置ｕ∈ＢＣは各サイトｉ∈Ｃにラベルｕｉ∈Ｂを与えるなどと書く。エネルギーとは、配置ｘ∈ＢＶに対して実数値Ｅ（ｘ）を与える擬ブール関数Ｅである。エネルギー関数Ｅ（ｘ）は常に、変数ｘｉ（ｉ∈Ｖ）についての多項式によって一意に表わすことができる。そのような多項式は、一般に次の数１０のように書ける。
【００６０】
【数１０】
2015190593.tif 000012
【００６１】
数１０において、記号「∈」の左側にあるＣはクリークであり、記号「∈」の右側にあるＣの装飾文字は、クリークの集合であって、サイトの集合Ｖの部分集合から構成される集合である。さらに、αＣはクリークＣ毎に決まる（クリークＣでインデックス付けられた）実係数である。ｘＣは次の数１１のように、ｉ∈Ｃを持つ変数ｘｉの積を表しており、単項式である。
【００６２】
【数１１】
2015190593.tif 000013
【００６３】
つまり、数１０は係数のかかった単項式の和、すなわち展開された多項式である。Ｃの装飾文字は、この多項式に現れる単項式を規定している。クリークＣは部分集合であるから、同じｉが２つ以上Ｃに属することはないが、変数ｘｉは０か１という値しかとらないため、（ｘｉ）２＝ｘｉからわかるように同一変数のべき乗は１乗と同じであるため、全ての可能な単項式を数１１の形で書くことができる。したがって、２値変数ｘｉ（ｉ∈Ｖ）についての任意の多項式は数１０の形に表現できる。クリークの要素数の最大がｋ＋１であるとき、つまり多項式の次数がｋ＋１であるとき、エネルギーはｋ階であるという。クリークＣの要素数を｜Ｃ｜で表す。
【００６４】
任意のクリークＣ⊂Ｖに対して、エネルギーを次の数１２のように２つの部分に分ける。
【００６５】
【数１２】
2015190593.tif 000014
【００６６】
但し、数１２の右辺の各部分は、それぞれ以下のように定義される。
【００６７】
【数１３】
2015190593.tif 000015
【００６８】
【数１４】
2015190593.tif 000016
【００６９】
数１４に示すエネルギーＥＣ−（ｘ）（以後、本文中では、文字の上に付された記号を、その文字の次に並べて記載する。）は、ｉ∈Ｃとなるような変数ｘｉを一切含まないことに注意されたい。任意の配置ｘ∈ＢＶおよびクリークＣ⊂Ｖに対して、ｘのＣへの制限と呼ばれる局所配置ｘ｜Ｃ∈ＢＣを以下の数１５のように定義する。
【００７０】
【数１５】
2015190593.tif 000017
【００７１】
つまりｘ｜Ｃは、各ｉ∈Ｃに対してｘｉを与える局所配置である。配置ｘ∈ＢＶおよびクリークＣ上の局所配置ｖ∈ＢＣについて、ｖがｘのＣへの制限（ｘ｜Ｃ＝ｖ）であるとき、ｖはｘの一部であるともいう。
【００７２】
・定義１
クリークＣ⊂Ｖと局所配置ｕ∈ＢＣについて、局所配置ｖ∈ＢＣがあってＧが以下の数１６で定義されるとき、ｕはギャップＧを持つという。正のギャップを持つときｕはＣ上の除外可能な局所配置（Excludable Local Configuration：ＥＬＣ）と呼ばれる。またこのとき正のＧを与えるｖを随伴局所配置と呼ぶ。
【００７３】
【数１６】
2015190593.tif 000018
【００７４】
多項式ＥＣ（ｘ）にはＣの外側のインデックスを持つ変数に依存する単項式が含まれるため、ｘ｜Ｃを固定してもＥＣ（ｘ）は値を変えることが可能である。しかし、除外可能な局所配置ｕ∈ＢＣと、その随伴局所配置ｖ∈ＢＣは、ｘ｜Ｃをそれぞれに固定したときのＥＣ（ｘ）の値の範囲が互いに重複せず、その間にはギャップＧだけの間隔がある。つまり、ｘ｜Ｃ＝ｕとなるとき、ＥＣ（ｘ）は、ｘ｜Ｃ＝ｖとなるときよりも常に少なくとも正の数Ｇだけ大きな値をとる。一方、Ｅ（ｘ）のＥＣ（ｘ）以外の部分、すなわちＥＣ−（ｘ）は、ｘ｜Ｃの値に依存しないから、エネルギー全体の最小解、すなわち最小化配置は、Ｃ上でｕの値は取らない。なぜなら、ｖを取った方が必ず少なくともＧだけ値が小さくなるからである。より形式的には、以下の定理が存在する。
【００７５】
・定理１
ｕ∈ＢＣが除外可能な局所配置であれば、次の数１７が成立する。
【００７６】
【数１７】
2015190593.tif 000019
【００７７】
すなわち、エネルギーＥ（ｘ）の最小化配置は、Ｃ上の局所配置ｕをとらない。ゆえに、除外可能な局所配置が最小化配置の一部となることはないので、除外可能な局所配置におけるエネルギー値を上昇させても、最小化問題が変更を受けることなく、エネルギー階数の縮減などの処理を行なうことができる（後に詳しく説明する）。また、以下の証明からわかるように、数１７の右辺から左辺を引いた差はギャップＧ以上なので、除外可能な局所配置におけるエネルギー値を上昇させる代わりにギャップＧより小さな値だけ下降させても、同様に最小化問題は変更を受けない。
【００７８】
・定理１の証明
任意の配置ｘ∈ＢＶおよび局所配置ｖ∈ＢＣに対して、ｘをｖで「上書き」して得られた配置ｘ（ｖ）∈ＢＶを、以下の数１８のように定義する。
【００７９】
【数１８】
2015190593.tif 000020
【００８０】
数１４に示すエネルギーＥＣ−（ｘ）は、ｉ∈Ｃとなるような変数ｘｉを一切含まないので、任意のｘ∈ＢＶおよびｖ∈ＢＣに対して以下の数１９が得られる。
【００８１】
【数１９】
2015190593.tif 000021
【００８２】
また、任意のｖ∈ＢＣに対して以下の数２０が得られる。
【００８３】
【数２０】
2015190593.tif 000022
【００８４】
上の数２０が成立する理由は、上式右辺のＥＣ−のいかなる最小化配置も、上式左辺の最小化配置を作るためにｖで上書き可能であることである。ここで、ｘ〜∈ＢＶをＥＣ−の最小化配置であるとすると、任意のｖ∈ＢＣに対して次の数２１の式が成立する。
【００８５】
【数２１】
2015190593.tif 000023
【００８６】
最後に、ｕはＣ上の除外可能な局所配置であるので、数１６のＧが正であるようなｖ∈ＢＣが存在する。これらをすべてまとめると、次の数２２を得、定理１が証明される。
【００８７】
【数２２】
2015190593.tif 000024
【００８８】
除外可能な局所配置の条件（数１６のＧ＞０）は、比較的、局所的に調べられる点が重要である。つまり、多項式ＥＣ（ｘ）に含まれる変数は多くの場合局在している。ただし、一般には、ＥＣ（ｘ）＝Ｅ（ｘ）となる可能性もある。また、除外可能な局所配置が存在しない可能性もある。つまり、固定されたｘ｜ＣにおけるＥＣ（ｘ）の取り得る値に一般の制限はなく、ｘ｜Ｃを固定する局所配置の組をどのように選んだとしても、対応するＥＣ（ｘ）の値の範囲が重複してしまう可能性もある。
【００８９】
Ｃ上の除外可能な局所配置（ＥＬＣ）ｕ∈ＢＣを発見できれば、ｘ｜Ｃ＝ｕの場合にのみエネルギーの値Ｅ（ｘ）を一定範囲で変化させることができる。定理１によれば、エネルギーの最小化配置は、Ｃ上ではｕを取らないが、それはｘ｜Ｃ＝ｕの場合のエネルギー値を上昇させてもそのままである。また、ｘ｜Ｃ＝ｕの場合のエネルギー値を、ｕのギャップＧより小さい値だけ低下させても、最小化問題に影響を及ぼさない。つまり、ｘ｜Ｃ＝ｕの場合のエネルギー値の変化をΔとして、Δ＞−Ｇであれば、最小化問題に影響を及ぼさない。このとき、ｘｃの係数はΔと同じ絶対値だけ変化するが、係数の変化の符号は、ｕのパリティと次数｜Ｃ｜の偶奇に依存する。
【００９０】
・定義２
ｕｉ＝１であるｉ∈Ｃが偶数（奇数）個であるとき、局所配置ｕ∈ＢＣは偶（奇）のパリティを持つと呼ぶ。
【００９１】
すると、ｕと｜Ｃ｜の偶奇が一致すれば、ｘ｜Ｃ＝ｕの場合のエネルギー値を上昇させたとき、単項式ｘＣの係数も同じだけ上昇する。逆にｕと｜Ｃ｜の偶奇が逆のときは、エネルギー値を上昇させたとき、単項式ｘＣの係数は同じだけ下降する。従って、単項式αＣｘＣを削除したいとすると、αＣ＜０のときは、｜Ｃ｜と偶奇が一致する除外可能な局所配置ｕを見つけることができれば、ｘ｜Ｃ＝ｕの場合のエネルギー値を−αＣだけ上昇させることによって、係数を０にし、削除することができる。逆にαＣ＞０のときは、｜Ｃ｜と偶奇が逆の除外可能な局所配置ｕを見つけることができれば、ｘ｜Ｃ＝ｕの場合のエネルギー値をαＣだけ上昇させることによって、最小化問題に影響を及ぼさずに削除することができる。どちらの場合も、ｘ｜Ｃ＝ｕの場合のエネルギー値を｜αＣ｜だけ上昇させることになる。また、これらαＣの正負それぞれの場合に、望む条件と逆のパリティの除外可能な局所配置ｕしか見つけることができない場合でも、｜αＣ｜＜Ｇであれば、ｘ｜Ｃ＝ｕの場合のエネルギー値を｜αＣ｜だけ下降させることによって、最小化問題に影響を及ぼさずに単項式αＣｘＣを削除できる。
【００９２】
次に、エネルギー変換部２４により行なわれるエネルギーの具体的な処理方法を提示する。ここでは各実施例に共通して、エネルギー変換部２４が次の手順で、エネルギーの変換を行なう。
【００９３】
段階１：変換前のエネルギーＥを表わす多項式の中から、ｄ次の項（ｄ＞２）を１つ選び、これを項αｘ１…ｘｄとする。これは上記では数１０の多項式から単項式αＣｘＣを選び、αＣ＝α、ｘＣ＝ｘ１…ｘｄであることに相当する。ここで、３次以上の項は、高階項であることから、除去することが望ましい。また２次の項は、その係数が正であるときは、非劣モジュラな項であるので、除去することが望ましい。ここでは、次数の高い項から選択していき、後述する実施例１では２次の項まで、実施例２および実施例３では３次の項までを選択するものとする。ただし、実施例１における２次の項については、係数が正である非劣モジュラな項のみを選択するものとする。
【００９４】
段階２：それぞれの変数ｘ１，…，ｘｄが取りうる値の組み合わせ（すなわちＣ上の局所配置）のうち、エネルギーＥの最小化配置の一部でない（最小化配置において、変数ｘ１，…，ｘｄがその値の組み合わせを取らない）可能性が高い組み合わせを１つ選ぶ。
・このとき、上記のように、α＜０ならば、変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と同じになるように、またα＞０ならば、変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と逆になるように、組み合わせを選ぶことできれば、その組み合わせのときのエネルギー値を上昇することでこの項を縮減できるので、より望ましい。
・選んだ値の組み合わせを、ｘ１＝ｕ１，…，ｘｄ＝ｕｄとする。
【００９５】
ただし、「変数ｘ１，…，ｘｄが取りうる値の組み合わせ」とは、変数がとりうる局所配置を意味し、変数の値の組み合わせと局所配置は同義の用語として用いることとする
【００９６】
段階３：変換前のエネルギーＥを表わす多項式に、次の数２３を加えて変換後のエネルギーＥ’とする。ただしｑは実数で、その設定は実施例毎に説明する。
【００９７】
【数２３】
2015190593.tif 000025
【００９８】
ここで、ｕ１，…，ｕｄは０か１の数であり、数２３は、ｘ１，…，ｘｄを変数とするｄ次の多項式である。例えばｄ＝３として、選んだ値の組み合わせが、ｘ１＝０，ｘ２＝１，ｘ３＝１であれば、数２３においてｕ１＝０、ｕ２＝１、ｕ３＝１となり、数２３の多項式はｑ（１−ｘ１）ｘ２ｘ３、すなわちｑｘ２ｘ３−ｑｘ１ｘ２ｘ３となる。この多項式は、選んだ値の組み合わせｘ１＝０，ｘ２＝１，ｘ３＝１のときだけ値がｑになり、それ以外の値の組み合わせのときには値が０になる。
【００９９】
すると、変換後のエネルギーＥ’の値は、次のようになる。
・ｘ１＝ｕ１，…，ｘｄ＝ｕｄであるとき：エネルギーＥの値にｑを加えた値。
・ｘ１＝ｕ１，…，ｘｄ＝ｕｄでないとき：エネルギーＥと同じ値。
・このため、ｑ＞０のとき、エネルギーＥの最小化配置において、ｘ１＝ｕ1，…，ｘｄ＝ｕｄでなければ、エネルギーＥ’の最小値や最小化配置は、エネルギーＥの最小値や最小化配置と等しい。ｑ＜０のときも、ｑの絶対値が一定範囲内に入っていれば、同様である（実施例１で説明する）。
【０１００】
また、エネルギーＥ’を表わす多項式は、エネルギーＥを表わす多項式と比べて、
・αｘ１…ｘｄの項がなくなり、ｄ次の項が１つ減っている。
・ｄ次以上の他の項には変化がない。
【０１０１】
したがって、上記段階１〜３の手順を繰り返すことで、変換後のエネルギーＥ’は、最小化する配置を変えないまま、外部変数を加えることなく高階項や非劣モジュラ項などの最小化を難しくする項を減らして行くことが可能になる。
【０１０２】
前記段階２において、「それぞれの変数ｘ１，…，ｘｄが取りうる値の組み合わせのうち、エネルギーＥの最小化配置の一部でない可能性が高い組み合わせを１つ選ぶ」方法として、例えば以下の３つが考えられる。第１の方法は保証付方法であり、第２の方法は近似的方法であり、第３の方法はランダム法である。以下、これら３通りの方法について、各実施例で順番に説明していく。なお、これらは例示であって、３つに限られるわけではない。
【実施例１】
【０１０３】
第１の保証付方法について詳しく説明する。ここでは前記段階２で、エネルギー変換部２４が次の手順を行なう。【０１０４】
段階２Ａ：エネルギーＥを２つの部分、すなわちｘ１，…，ｘｄの変数を１つでも含む項の和となるエネルギーＥ１と、ｘ１，…，ｘｄの変数を１つも含まない項の和となるエネルギーＥ２に分ける。すると、Ｅ＝Ｅ１＋Ｅ２である。【０１０５】
段階２Ｂ：変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄについて、次の条件を考える。
・変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｖ１，…，ｘｄ＝ｖｄであって、ｘ１＝ｖ１，…，ｘｄ＝ｖｄを満たす配置におけるエネルギーＥ１の値の最大値が、ｘ１＝ｕ１，…，ｘｄ＝ｕｄを満たす配置におけるエネルギーＥ１の最小値よりも小さいものが存在する。【０１０６】
段階２Ｃ：段階２Ｂの条件を満たす変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄは、除外可能な局所配置（ＥＬＣ）と呼ばれ、付随するｘ１＝ｖ１，…，ｘｄ＝ｖｄは随伴局所配置と呼ばれる。また、ｘ１＝ｖ１，…，ｘｄ＝ｖｄを満たす配置におけるエネルギーＥ１の値の最大値を、ｘ１＝ｕ１，…，ｘｄ＝ｕｄを満たす配置におけるエネルギーＥ１の最小値から減算した値をギャップと呼ぶ。除外可能な局所配置はエネルギーＥを最小化する配置の一部ではあり得ないことが証明できる（定理１）。【０１０７】
したがって、段階２Ｂの条件を満たすような変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄについて、その存在をエネルギー変換部２４が発見できれば、その組み合わせの時のみエネルギーＥを上昇させるか、ギャップ以内の範囲で下降させるエネルギー変換を行っても、エネルギー最小化の問題は変更を受けない。このような変数ｘ１，…，ｘｄの値の組み合わせは、エネルギーＥ１に含まれる変数ｘ１，…，ｘｄ，…について、例えばその値の組み合わせを総当たりすることにより、段階２Ｂの条件を満たす変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄが存在すれば発見できる。多くの場合、エネルギーＥ１に含まれる変数は、ｘ１，…，ｘｄにいくつかの変数が加わった程度であり、これが可能となる。このとき、α＜０ならば、変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と同じになること、α＞０ならば、変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と逆になることを、パリティ条件と呼ぶことにすると、パリティ条件を満たすような組み合わせのうちから、段階２Ｂの条件を満たす組み合わせを選ぶことが、エネルギーの上昇により項αｘ１…ｘｄが正しくキャンセルされるために必要である。そのような組み合わせが見つかれば、その組み合わせの時のみエネルギーＥを｜α｜だけ上昇させることで、αｘ１…ｘｄが正しくキャンセルされる。そのようにパリティ条件と段階２Ｂの条件を満たす組み合わせのうちから選ぶことができなくても、段階２Ｂの条件を満たし、ギャップが｜α｜より大きいような値の組み合わせが見つけられれば、それでも十分である。その場合は、その組み合わせの時のみエネルギーＥを上昇させるのではなく、｜α｜だけ下降させることで、αｘ１…ｘｄが正しくキャンセルされる。この場合、エネルギーはその組み合わせの時のみ下がっているが、下がり方はギャップより少ないので、エネルギーＥを最小化する配置の一部にならない。【０１０８】
この方法の利点は、上記の条件を満たす変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄが存在すれば、それは確実に最小化配置の一部ではなく、従って上記のようなエネルギー上昇あるいは下降が、最小化問題に影響を与えないと確実にいえることである。【０１０９】
なお、この方法を用いる場合には、上記の条件を満たす変数ｘ１，…，ｘｄの値の組み合わせが存在しない場合がありうる点や、存在しても見つけるのに比較的時間がかかる可能性が考えられる点に留意が必要である。但し、エネルギー変換部２４が例えば並列処理を行なうことで、時間がかかるのをある程度解消することができる。また、Ｅ１に含まれる変数の数の上限や、除外可能な局所配置の探索に使うステップ数あるいは時間の上限を決めておき、項毎にそれを超える場合には探索をとりやめることにより、時間を節約することも考えられる。【０１１０】
図５は、本実施例におけるエネルギー変換処理の一例を示すフローチャートである。ここでは、高階単項式αｘ１…ｘｄを除去するために、エネルギー変換部２４が次の手順を行なう。【０１１１】
・段階１：エネルギーＥを表わす多項式の中から、項αｘ１…ｘｄを変換対象に設定する段階
・段階２−１：αの値とｄの偶奇とに応じて、除外可能な局所配置を探す段階
・段階２−２：除外可能な局所配置を用いて多項式関数Ψ（ｘ）を設定する段階
・段階３：多項式関数Ψ（ｘ）をエネルギーに加算し、エネルギーを変換する段階
以下、上述各段階を詳しく説明する。【０１１２】
・段階１：
単項式αｘ１…ｘｄを１つ選ぶ（ステップＳ２００）。ここでは、繰り返すうち、次数の高い項から選択していき、２次の項までを選択するものとする。ただし、２次の項については、係数が正である項のみを選択する。こうすることで、高階項及び非劣モジュラな１階項をできるだけ縮減する。【０１１３】
・段階２−１：
単項式αｘ１…ｘｄが決まれば、それが取り除かれるようにエネルギー変換を行なうためには除外可能な局所配置（ＥＬＣ）を探す必要がある。定理１によれば、除外可能な局所配置が最小化配置の一部となることはない。したがって、除外可能な局所配置においてエネルギーを上昇あるいはギャップより小さい値だけ下降させ、エネルギー変換を行っても、最小化問題は変更を受けない。ただしエネルギーを上昇させるか下降させるかは、単項式αｘ１…ｘｄが次に説明する段階（段階２−２）で正しく相殺するように、除外可能な局所配置のパリティによって適切に決めねばならない。ここで、ある局所配置（つまり変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄ）において、ｕｉ＝１となるようなｉの数が偶（奇）であるとき、当該配置は偶（奇）のパリティを持つと呼び、以下のような手順で除外可能な局所配置を探す。除外可能な局所配置をみつけるためのより詳細なアルゴリズムは、後に説明する。【０１１４】
先ずステップＳ２１０で、係数αの正負を判定する。ここでα＜０の場合、次のステップＳ２２０の手順で、次数ｄが奇数なら、奇のパリティを持つか、｜α｜より大きいギャップＧを持つような除外可能な局所配置ｘ１＝ｕ１，…，ｘｄ＝ｕｄを探し（ステップＳ２４０）、ｄが偶数なら、偶のパリティを持つか、｜α｜より大きいギャップＧを持つような除外可能な局所配置ｘ１＝ｕ１，…，ｘｄ＝ｕｄを探す（ステップＳ２５０）。またステップＳ２１０の手順で、α＞０の場合には、次のステップＳ２３０の手順で、次数ｄが偶数なら、奇のパリティを持つか、偶のパリティを持ちギャップＧが｜α｜より大きいような除外可能な局所配置ｘ１＝ｕ１，…，ｘｄ＝ｕｄを探し（ステップＳ２４０）、ｄが奇数なら、偶のパリティを持つか、奇のパリティを持ちギャップＧが｜α｜より大きいような除外可能な局所配置ｘ１＝ｕ１，…，ｘｄ＝ｕｄを探す（ステップＳ２５０）。【０１１５】
・段階２−２：
前述のステップＳ２４０またはステップＳ２５０で、除外可能な局所配置ｘ１＝ｕ１，…，ｘｄ＝ｕｄが見つかれば、ｘ１＝ｕ１，…，ｘｄ＝ｕｄのときに限ってエネルギーに実数値ｑだけ加える。ただしｑは、ステップＳ２４０で奇のパリティを持つ局所配置を見つけたかステップＳ２５０で偶のパリティを持つ局所配置を見つけたのであればｑ＝｜α｜とし、そうでなければｑ＝−｜α｜とする。上述の定理によれば、除外可能な局所配置がエネルギー最小化配置の一部となることはない。よって、変換前のエネルギー関数に以下に定められる多項式関数を加算することで、変換前のエネルギー関数に存在していた単項式αｘ１…ｘｄを相殺するようなエネルギー変換をすることが可能である。これを相殺するように定められる当該多項式関数Ψ（ｘ）は、上で設定した実数ｑおよび除外可能な局所配置ｘ１＝ｕ１，…，ｘｄ＝ｕｄを用いて次の数２４のように設定される（ステップＳ２６０）。【０１１６】
【数２４】
2015190593.tif 000026
【０１１７】
・段階３：
ステップＳ２６０で設定した多項式関数Ψ（ｘ）を、変換前のエネルギー関数Ｅ（ｘ）に加えることでエネルギー変換を行なう。変換後のエネルギー関数Ｅ’（ｘ）は、次の数２５を用いて取得される（ステップＳ２７０）。【０１１８】
【数２５】
2015190593.tif 000027
【０１１９】
結果として、変換後のエネルギー関数Ｅ’（ｘ）は、次の数２６のような値を持つ。【０１２０】
【数２６】
2015190593.tif 000028
【０１２１】
ｘ１＝ｕ１，…，ｘｄ＝ｕｄは除外可能な局所配置であるので、もとのエネルギーＥ（ｘ）のいかなる最小化配置もｘ１＝ｕ１，…，ｘｄ＝ｕｄをその一部としてとらない。したがって、ｑ＞０であれば、変換前のエネルギー関数Ｅ（ｘ）と変換後のエネルギー関数Ｅ’（ｘ）は、どちらも同じ最小化配置を持つ。またｑ＜０になるのは、ギャップが｜α｜より大きいときであり、このときｑ＝―｜α｜であるから、ｘ１＝ｕ１，…，ｘｄ＝ｕｄのときのエネルギーＥ’（ｘ）の値は下がるが、それでもまだｘ１＝ｕ１，…，ｘｄ＝ｕｄは除外可能な局所配置であり、従って変換前のエネルギー関数Ｅ（ｘ）と変換後のエネルギー関数Ｅ’（ｘ）は、どちらも同じ最小化配置を持つ。【０１２２】
ステップＳ２７０で加えられた多項式関数Ψ（ｘ）は、最高次の単項式−αｘ１…ｘｄを有するが、ｄ以上の次数を持つ他の単項式を含まない。したがって変換前のエネルギーＥ（ｘ）にあった単項式αｘ１…ｘｄは、新しいエネルギーＥ’（ｘ）では取り除かれ、エネルギーのｄ次の項が１つ減る。【０１２３】
こうして、ステップＳ２１０〜ステップＳ２５０で条件を満たす除外可能な局所配置が見つからず、ステップＳ２８０でエネルギー変換が成功しなかった場合には、ステップＳ２９０において、単項式αｘ１…ｘｄを縮減するために、公知のアルゴリズムを併用することも可能である。そして、エネルギー変換が成功したか否かに拘らず、ステップＳ３００では他に縮減する項があるか否かを判定し、縮減する項が存在しなくなるまで、上述のステップＳ２００〜ステップＳ２９０の手順を繰り返す。ここではループ内で項毎に公知のアルゴリズムを併用したが、ループ内ではエネルギー変換が成功しなかった項はそのまま残しておき、あとでまとめて残った高階項に公知のアルゴリズムを適用してもよい。【０１２４】
次に、前述のステップＳ２１０〜ステップＳ２５０に対応して、「エネルギーＥ１に含まれる変数ｘ１，…，ｘｄ，…について、例えばその値の組み合わせを総当たりすることにより、段階２Ｂの条件を満たす変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄが存在すれば発見できる」とした除外可能な局所配置を見つけ出すための詳細なアルゴリズムについて、図６を参照しながら説明する。【０１２５】
除外可能な局所配置が存在していれば、エネルギーＥ１に含まれる変数ｘ１，…，ｘｄ，…について、その値の組み合わせを総当たりすることにより、当該除外可能な局所配置をみつけることができる。ここでは、変数ｘ１，…，ｘｄに０か１を代入する可能な２ｄとおりの順列のカウンタをｉとし、エネルギー上昇になるパリティの値の組み合わせの最小値の最大値をＭｍ、エネルギー下降になるパリティの値の組み合わせの最小値の最大値をＭ’ｍとし、最大値の最小値をｍＭとする。また、エネルギー変換部２４への入力は多項式Ｅ１と、変数の組（ｘ１，…，ｘｄ）である。Ｅ１はｘ１，…，ｘｄのうち少なくとも１つを含む単項式からなる。ただし、Ｅ１にはそれ以外の変数も含まれる。【０１２６】
順番にｘ１，…，ｘｄへ割り当てる０か１の組み合わせを１つ選び、その上でそれ以外の変数を変化させたときのＥ１の最大値をＭとし、最小値をｍとする。すべての組み合わせを試行していく中で、当該組み合わせに対応する様々な最小値ｍの中での最大値をパリティ毎にＭｍとＭ’ｍとし、一方、当該組み合わせに対応する様々な最大値Ｍの中での最小値をｍＭとする。ＭｍとＭ’ｍおよびｍＭはＥ１に含まれる変数の組み合わせを試行しながら随時更新していく。【０１２７】
先ず図６のステップＳ４００で、初期値としてカウンタｉを０にセットする。また、最小値の最大値ＭｍとＭ’ｍは想定されるエネルギーに比べて十分小さな値を代入し（Ｍｍ←−∞）、最大値の最小値ｍＭは十分大きなエネルギーを代入する（ｍｍ←∞）。また、エネルギー上昇になる局所配置のパリティを表す整数Ｐを、α＜０のときは次数ｄに、α＞０のときはｄ＋１に設定する。【０１２８】
次にステップＳ４１０で、変数の組（ｘ１，…，ｘｄ）にカウンタｉの２進展開を代入し、そのときエネルギーＥ１からできる多項式をＥｉ１とする。また、ｘ１，…，ｘｄのうち１が代入されたものの数をｐとする。そしてエネルギーＥ１において、当該クリークの外側であって、多項式Ｅｉ１の残った変数に、０か１を代入するすべての可能な順列について、多項式Ｅｉ１の値を求め、その最大値をＭ、最小値をｍとする（ステップＳ４２０）。このときｍＭ＞Ｍならば、最大値の最小値ｍＭにＭを代入し（ｍｍ←Ｍ）、その値ｍＭをＭとして更新する（ステップＳ４３０）。【０１２９】
こうして、最大値の最小値ｍＭが更新された結果、次のステップＳ４４０で、ｍＭ＜Ｍｍの条件が満たされれば、実数ｑとして｜α｜を設定し、Ｍｍに対応する局所配置（ｕ１，…，ｕｄ）を返し、処理を終える（ステップＳ４５０）。一方、前記ステップＳ４４０で、ｍＭ＜Ｍｍの条件が満たされなかった場合には、次のステップＳ４４５で、ｍＭ＜Ｍ’ｍ−｜α｜の条件が満たされれば、実数ｑとして−｜α｜を設定し、Ｍ’ｍに対応する局所配置（ｕ’１，…，ｕ’ｄ）を返し、処理を終える（ステップＳ４６７）。一方、前記ステップＳ４４５で、ｍＭ＜Ｍ’ｍ−｜α｜の条件が満たされなかった場合には、次のステップＳ４６０で、「ｐとＰの偶奇が同じ」であるか否かを判定し、そうである場合には、ステップＳ４７０で、Ｍｍ＜ｍならばＭｍにｍを代入し（Ｍｍ←ｍ）、エネルギー上昇になるパリティの除外可能な局所配置の候補として、（ｕ１，…，ｕｄ）に（ｘ１，…，ｘｄ）を代入する（（ｕ１，…，ｕｄ）←（ｘ１，…，ｘｄ））。【０１３０】
この結果、次のステップＳ４８０で、ｍＭ＜Ｍｍとなれば、実数ｑとして｜α｜を設定し、Ｍｍに対応する局所配置（ｕ１，…，ｕｄ）を返し、処理を終える（ステップＳ４５０）。一方、前記ステップＳ４８０で、ｍＭ＜Ｍｍとならない場合には、ステップＳ４９０に移行して、順列のカウンタｉを１つ増やし（ｉ←ｉ＋１）、ステップＳ５００において、カウンタｉの値がｉ＜２ｄとなるまで、ステップＳ４１０〜ステップＳ４９０の手順を繰り返す。一方、前述のステップＳ４４５で、ｍＭ＜Ｍ’ｍ−｜α｜の条件が満たされなかった場合であって、さらに次のステップＳ４６０で、「ｐとＰの偶奇が同じ」ではない場合に、ステップＳ４６５で、Ｍ’ｍ＜ｍならばＭ’ｍにｍを代入し（Ｍ’ｍ←ｍ）、エネルギー下降になるパリティの除外可能な局所配置の候補として、（ｕ’１，…，ｕ’ｄ）に（ｘ１，…，ｘｄ）を代入する（（ｕ’１，…，ｕ’ｄ）←（ｘ１，…，ｘｄ））。この結果、次のステップＳ４６６で、ｍＭ＜Ｍ’ｍ−｜α｜となれば、実数ｑとして−｜α｜を設定し、Ｍ’ｍに対応する局所配置（ｕ’１，…，ｕ’ｄ）を返し、処理を終える（ステップＳ４６７）。一方、ステップＳ４６６で、ｍＭ＜Ｍ’ｍ−｜α｜とならなければ、ステップＳ４９０で順列のカウンタｉを一つ増やし、ステップＳ５００において、カウンタｉの値がｉ＜２ｄとなるまで、ステップＳ４１０〜ステップＳ４９０の手順を繰り返す。こうしてステップＳ５００で、ｉ＜２ｄとなるまで可能な順列のカウンタｉをすべて総当たりし、結果条件を満たす配置が得られなかった場合には、ステップＳ５１０で一連の処理を終える。【０１３１】
以上が、本実施例におけるエネルギー変換のアルゴリズムの流れである。変換が終われば、次のエネルギー最小化部２６が、グラフカットなどの効率的なアルゴリズムを利用して、エネルギーを最小化する。【０１３２】
また、変換後の多項式について、正の係数を持つ２次の項をすべて除去できれば、当該関数は劣モジュラ関数と呼ばれ、このとき最小化問題を厳密に解くことが可能である。関数が劣モジュラでなくとも、ＱＰＢＯアルゴリズムとして一般的に呼ばれているルーフ双対性に関する技術（前述の非特許文献４，非特許文献５等参照）によって、最小化配置に関する情報を得ることができる。【０１３３】
このように、変換前のエネルギーに対して、上記実施例のアルゴリズムをうまく利用し、高次の項および非劣モジュラな２次の項を縮減した後、そのエネルギーを最小化するための様々な公知テクニックと併用することが可能である。
【実施例２】
【０１３４】
次に、本発明の第２の実施例として、近似的方法について詳しく説明する。【０１３５】
実施例１で説明した保証付方法では、前述のように除外可能な局所配置が存在しない可能性も一般には存在する。また、除外可能な局所配置が存在していたとしても、それを見つけ出すのに時間がかかる場合もある。固定された局所配置に関しては、Ｅ１（ｘ）のなかで、０に固定された変数を含む単項式を消去することが可能であり、また１に固定された変数も変数ではなくなるので、多項式はかなり小さくすることが可能となる。その後、上記のように、多項式の最小値、最大値を総当たり的な方法で探さなければならないが、アルゴリズムのこの部分に関しては並列処理が可能である。それでも時間がかかり過ぎる場合には、実施例１のアルゴリズムを以下の実施例２のように変更することも可能である。本実施例においては除外可能な局所配置を探す必要はない。αの正負とｄの偶奇とに応じて、パリティを選択し、選択されたパリティを持つ局所配置のなかでポテンシャルが最大となるもの（局所最大解）を探せば、それで十分である。本実施例では除外可能な局所配置の条件をチェックしないので、エネルギーを変換（上昇）させるために選ぶ変数の配置が必ず１つ選べ、またエネルギー変換の速度はより高速である。【０１３６】
本実施例では、前述した段階２で、エネルギー関数Ｅの項のうち、ｘ１，…，ｘｄ以外の変数を含まない項を足し合わせた関数Ｅ３について、当該関数Ｅ３が最大になるような局所配置（変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄ）を選ぶ。当該配置は、α＜０ならば、ｘ１，…，ｘｄのうち値が１になるものの個数の偶奇が次数ｄの偶奇と同じである配置から選び、反対にα＞０ならば、ｘ１，…，ｘｄのうち値が１になるものの個数の偶奇が次数ｄの偶奇と逆である配置から選ぶようにする。【０１３７】
本実施例の利点は、エネルギーを変換（上昇）させるために選ぶ変数ｘ１，…，ｘｄの値の組み合わせすなわち局所配置が必ず１つ選べることと、当該組み合わせを見つけるのに比較的時間がかからないことである。なお本実施例では、見つけた値の組み合わせが、エネルギーＥを最小化する配置の一部である可能性もあるが、その確率は実験的には非常に低いものとなる。本実施例でエネルギー変換部２４が行なうアルゴリズムは、以下の通りである。【０１３８】
・段階１’：エネルギーＥを表わす多項式の中から、高階項αｘ１…ｘｄを変換対象に設定する段階
・段階２’−１：αの正負とｄの偶奇とに応じて、局所最大解を探す段階
・段階２’−２：局所最大解を用いて多項式関数Ψ（ｘ）を設定する段階
・段階３：多項式関数Ψ（ｘ）をエネルギーに付加し、エネルギーを変換する段階
以下、図７のフローチャートを参照して、上述各段階を詳しく説明する。【０１３９】
・段階１’：
全エネルギーＥの中から、項αｘ１…ｘｄを変換対象に設定する（ステップＳ２０１）。ここでは、繰り返すうち、次数の高い項から選択していき、３次の項までを選択するものとする。なお、本実施例の近似手法は、後に述べるように階数が高いほど正しく項を削減できる。逆に２次の項についてはあまり高い近似が望めないので、本実施例では高階項、すなわち３次以上の項のみを処理するものとする。もちろん、高階項を処理した後で、実施例１に示した方法で、非劣モジュラな２次の項を削減することは可能である。次に、ｘ１，…，ｘｄ以外の変数を含まない単項式の和をとり、以下の数２７の多項式Ｅ３（ｘ）を定める（Ｃは変数ｘ１，…，ｘｄにあたるクリーク）。【０１４０】
【数２７】
2015190593.tif 000029
【０１４１】
数２７で示しているように、本実施例におけるエネルギー多項式Ｅ３を構成する変数は、ｘ１，…，ｘｄのみであることに注意されたい。つまり、Ｅ３はｘ１，…，ｘｄの関数である。【０１４２】
・段階２’−１：
先ずステップＳ２１０で、係数αの正負を判定する。ここでα＜０の場合、ｄが奇数なら奇のパリティを持つ局所最大解を探し（ステップＳ２４１）、ｄが偶数なら偶のパリティを持つ局所最大解を探す（ステップＳ２５１）。またα＞０の場合には、ｄが偶数なら奇のパリティを持つ局所最大解を探し（ステップＳ２４１）、ｄが奇数なら偶のパリティを持つ局所最大解を探す（ステップＳ２５１）。ここで局所最大解とは、数２７によって定められるポテンシャルを最大にするような変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄを指し、本実施例では除外可能な局所配置を探す必要はない。ここでは係数αの正負とｄの偶奇とに応じて、解のパリティを選択し、選択されたパリティを持つ局所配置のなかで、ポテンシャルが最大となる局所配置（局所最大解）を探せばそれで十分である。【０１４３】
・段階２’−２：
段階２’−１で定めた局所最大解ｘ１＝ｕ１，…，ｘｄ＝ｕｄから、以下の数２８に定める多項式関数を設定する（ステップＳ２６０）。これは、上記の数２３でｑ＝｜α｜としたものである。【０１４４】
【数２８】
2015190593.tif 000030
【０１４５】
・段階３：
最後に、段階２’−２で定めた多項式関数Ψ（ｘ）を、変換前のエネルギー関数Ｅ（ｘ）に加えることでエネルギー変換を行なう。変換後のエネルギー関数Ｅ’（ｘ）は、実施例１で示した数２５を用いて取得される（ステップＳ２７０）。本実施例では、局所最大解が必ず見つかるので、実施例１におけるステップＳ２８０〜ステップＳ２９０の各手順は必要ない。【０１４６】
当該エネルギー変換によって、高階項が１つ減る。局所最大解ｘ１＝ｕ１，…，ｘｄ＝ｕｄは、変数ｘ１，…，ｘｄの値の全組み合わせのうち半分における最大解であるので、ｘ１＝ｕ１，…，ｘｄ＝ｕｄが全エネルギーの最小値の一部となる可能性は低い。後に述べる実験結果によって、最小化のスピードは、実施例１と比較して速くなることが示される。【０１４７】
以上が、本実施例におけるエネルギー変換のアルゴリズムの流れである。本実施例の利点は、エネルギーを変換（上昇）させるために選ぶ変数の配置が必ず１つ選べることと、当該配置をみつけるのに比較的時間がかからないことである。
【実施例３】
【０１４８】
次に、本発明の第３の実施例として、ランダム法について詳しく説明する。【０１４９】
上述した実施例１と実施例２の主な違いは、エネルギー最小値をとらないと思われる局所配置の選び方にある。エネルギー変換を行うために探し出す局所配置は、実施例２のように、エネルギー変換を近似的に行う場合には、除外可能な局所配置である必要はない。本実施例は、実施例１あるいは実施例２において、除外可能な局所配置もしくは局所最大解の条件はチェックせずに、当該局所配置をランダムに選び、選ばれた局所配置におけるエネルギーを上昇させることでエネルギー変換を行なう。本実施例では除外可能な局所配置の条件をチェックしないので、エネルギーを変換（上昇）させるために選ぶ変数の配置が必ず１つ選べ、またエネルギー変換の速度は高速である。【０１５０】
本実施例では、前述した段階２で、エネルギー関数Ｅの項の組み合わせをランダムに選ぶ。この方法の利点は、前述したように、変数ｘ１，…，ｘｄの値の組み合わせを必ず一つ選択できると共に、エネルギー変換を高速に行なえることにあるが、見つけた値の組み合わせが、エネルギーＥを最小化する配置の一部である可能性がある。しかし、その確率は低い。【０１５１】
図８は、本実施例でエネルギー変換部２４が行なうアルゴリズムを、フローチャートで示している。実施例２で示した図７のフローチャートとの相違点は、ステップＳ２４２で奇のパリティの局所配置をランダムに選び、ステップＳ２５２で偶のパリティの局所配置をランダムに選ぶことである。それ以外の手順は実施例２と共通するため、説明は省略する。【０１５２】
こうして、各実施例で説明した方法の何れか一つを用いて、エネルギー変換部２４が２階以上のエネルギー多項式を１階のエネルギー多項式に変換すると、後段のエネルギー最小化部２６は、既存のグラフカット法などのアルゴリズムを用いて、各画素に対応した２値変数を設定し、変数Ｘｕが値０すなわち骨である画素ｕに対して色を付すと共に、変数Ｘｕが値１すなわち骨でない画素ｕに対しては透明処理を施して、ディスプレイ３０に表示出力することにより、入力した画像のうち骨の部分だけをディスプレイ３０で表示する。なお、使用する既存のエネルギー最小化アルゴリズムによっては、変数がわからないエラーが生じる可能性もあるが、予め定めた割り当てを行なったり、エラーが生じた変数だけで再びエネルギーを生成してエネルギー最小化アルゴリズムを適用したりすることにより対応することができる。【０１５３】
なお、上述の各実施例では、エネルギー多項式の各項のうち、次数ｄが最も高い項から順に変換対象に設定して、エネルギー変換処理を行なう手順を説明したが、必ずしも次数ｄが最も高い項から順に設定する必要はなく、次数ｄの低いものから設定したり、ランダムに次数ｄが３以上の項を設定したりしても構わない。ただし、ｄ次の項を変換すると、ｄ次より低次の項は影響を受けるので、低次の項を先に消すと、消した筈の項が、より高次の項を変換した影響でふたたび現れる可能性があるので、次数の高い項から変換するか、そのような影響を考慮した順番にする必要がある。また、上述の各実施例では、変換対象の項を順に選んで逐次的に処理しているが、変換対象の項に対応するクリークが干渉しないように気を付ければ、これらは並列に処理できる。ここで複数のクリークが干渉しないことは、実施例１においては、各クリークに対応するＥ１が共通の変数を含まなければ保障され、実施例２および実施例３においては、異なるクリークが共通のサイトを含まないことを意味する。【０１５４】
次に、本発明の効果を説明するために、以下に本発明における実験の詳細と結果を述べる。実験では、比較例として以下の参考文献１及び参考文献２に示すクリーク縮減のアルゴリズム（以下ＨＯＣＲと記載することがある）と、参考文献３に示すグラフカットアルゴリズムを用いた例を用いる。なお、画像ノイズ除去の性能比較に関するベンチマークとして、参考文献４のＦｏＥ（Field of Expert）モデルを用いることとする。【０１５５】
参考文献１：H. Ishikawa "Higher-Order Clique Reduction in Binary Graph Cut", CVPR2009: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Miami Beach, Florida. June 20-25, 2009.【０１５６】
参考文献２：H. Ishikawa "Transformation of General Binary MRF Minimization to the First Order Case", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 6, pp. 1234-1249, June 2011.【０１５７】
参考文献３：A. Fix, A. Gruber, E. Boros, and R. Zabih “A Graph Cut Algorithm for Higher-order Markov Random Fields” In ICCV2011, pp.1020-1027, 2011.【０１５８】
参考文献４：S. Roth and M. J. Black. “Fields of Experts” International Journal of Computer Vision (IJCV), 82(2):205-229, April 2009.【０１５９】
初めに、参考文献４に記載のＦｏＥモデルについて説明する。参考文献４に示すＦｏＥモデルでは、数２９のように、画像の事前確率分布を、幾つかのスチューデントのＴ分布の積として表す。【０１６０】
【数２９】
2015190593.tif 000031
【０１６１】
上記数２９で、Ｃは画像中の全ての２×２画素パッチの集合にわたり、Ｊｉは２×２画素のフィルターである。モデルのパラメータはＪｉとαｉで、自然画像のデータベースから学習される。【０１６２】
ＦｏＥモデルの具体的なエネルギーや、ベンチマークとして用いられた融合移動アルゴリズムの定式化の詳細は、本実験では参考文献２に記載された内容に基づいている。ここで比較されるアルゴリズムは、すべて基本的に同じような構造を持ち、すべて同じ３階の複数ラベルエネルギーを最小化する。これらはすべて反復的なアルゴリズムであり、提案画像が各々反復計算で生成され、当該提案画素は高階マルコフ確率エネルギーを最小化することによって、その時点での配置と融合する。各々の反復計算で最小化されるエネルギーは、２値の３階エネルギーである。当該３階エネルギーは、様々な階数縮減方法を用いて、エネルギー変換される。実験によって、以下の第１〜第５の方法を比較した。【０１６３】
１）実施例１の保証付方法とＨＯＣＲ法との併用法（第１の方法）
実施例１の保証付方法により求めたＥＬＣをまず用い、正しいパリティを持つＥＬＣを持たない高次項はＨＯＣＲ法（参考文献１及び参考文献２を参照）により縮減する。
２）実施例１の保証付方法と参考文献３の方法との併用法（第２の方法）
実施例１の保証付方法により求めたＥＬＣをまず用い、それでも縮減されなかった項を参考文献３の方法で縮減する。
３）実施例２の近似的方法（第３の方法）
実施例２の近似的方法であって、高次項のすべてを縮減する。
４）ＨＯＣＲ法（第４の方法）
参考文献１及び参考文献２に記載された方法で縮減する。これは従来技術を用いた比較例である。
５）グラフカットによる方法（第５の方法）
参考文献３による方法で、これは従来技術を用いた比較例である。【０１６４】
縮減されたエネルギーはＱＰＢＯアルゴリズムによって最小化されるが、当該アルゴリズムは各変数をラベルする場合としない場合がある。ラベルされている変数の比率は、エネルギー階数低減の品質を評価する上で重要な基準となる。【０１６５】
・実験結果
図９は、上記第１〜第５の方法について、エネルギー階数縮減後の１階エネルギーの変数の平均数を各々比較したものである。図中、「ELC＋HOCR」は第１の方法、「ELC＋Fix et. al」は第２の方法、「Approx.ELC」は第３の方法、「HOCR」は第４の方法、「Fix et. al」は第５の方法である。本発明に関係する第１〜第３の方法は、他の方法と比較して相当少ない変数を生成していることが確認できる。本発明のアルゴリズムでは、変数の数が従来のアルゴリズムの約五分の一となっている。これにより、より効果的なエネルギー最小化ができるようになる。【０１６６】
図１０の（Ａ）は、反復数「iterations」に対するエネルギー「energy」のプロットを示し、（Ｂ）は時間「Time」に対するエネルギー「energy」のプロットを示し、（Ｃ）は反復数「iterations」に対するラベルされた画素数の割合「％ pixels labeled」のプロットを示している。また、（Ａ）〜（Ｃ）に共通して、第１の方法である「ELC＋HOCR」と、第３の方法である「Approx.ELC」と、第４の方法である「HOCR」と、第５の方法である「Fix et. al」におけるデータ点を、線で結んでいる。【０１６７】
図１０を総合的にみて、本発明の近似的方法は、従来技術である第５の方法よりも優れていることが見て取れる。当該近似的な方法は、反復数のまだ少ない段階で、既に９８％のラベル付けがなされるが、従来技術である第５の方法では、７５％しかラベルされていない。結果として、当該近似的方法は各々の反復計算でより多くの高階エネルギーを縮減する。また、第５の方法と比べて各々の反復計算がより短くなり、時間に対するエネルギーのプロットでは、実施例２で示した近似的方法と従来技術である第５の方法との差がより大きく示される。【０１６８】
・近似の評価
別な実験として、実施例２で説明した近似的方法による質の評価を実験的に行なった。各３次項あるいは４次項に対して、近似的方法によるアルゴリズムは、当該項に含まれる変数のみを含むエネルギーの中のすべての単項式より構成される多項式Ｅ３（数２７を参照）をとり、その多項式Ｅ３を最大化するような局所最大解を探す。除外可能な局所配置ではなく、局所最大解を用いてエネルギーを上昇させ、その局所最大解が配置の一部となる場合にのみ、エネルギーを一定量上昇させる。概ね３次項の８８％、４次項の９７％に対して、局所最大解が実際に除外可能な局所配置となっていることが分かった。これは近似方法によるアルゴリズムであっても、これらの項が正しく縮減されていることを意味している。【０１６９】
さらに、局所最大解が除外可能な局所配置でなくとも、Ｅ３の値の上昇によって最小化問題が影響を受けずに、局所最大解が最小化配置の一部にならないこともある。このような場合を確認するため、局所最大解が除外可能な局所配置とはなっていないような各項に対して、局所最大解が最小化配置の一部となるかどうか確認した。本実験では、もとのエネルギー変換には第５の方法を利用し、変換されたエネルギーの最小化にはＱＰＢＯ（ルーフ双対）アルゴリズムを利用した。ＱＰＢＯの性質から、変数がラベル付けされれば、それらは最小化配置の一部であることが保障される。局所最大解が除外可能な局所配置ではない項のうち、６５％の３次項が、また９７％の４次項の変数がすべてラベル付けされた。これらのうちごく一部（３次項の0.02％、４次項の0.003％）だけが、実際に最小化配置の一部となっていた。【０１７０】
この結果にも見られるが、一般的に、３次項よりも４次項の方が実施例２によってより正確に縮減されやすいと予想される。これは、３次項に比べて４次項の方が、局所配置の選択肢がより多くなっており、選んだ最大解が最小化配置の一部である可能性がより低いためである。したがって、高い次数を持つ項に対して、当該近似アルゴリズムはより一層うまく働く。【０１７１】
画素毎の比較を行なったところ、全画素の約83.3％が、近似的方法によるアルゴリズムと第５の方法のアルゴリズムの両方によってラベル付けされた。これらのわずか0.00012％の画素に対してのみ、異なるラベル付けがなされた。つまり、判定可能な画素のうち、99.99988％の画素は実施例２によって正しくラベル付けされた。【０１７２】
以上説明した本発明の情報処理装置は、各実施例に共通して、多項式によって表わすことが可能なエネルギーＥを処理するために、そのエネルギーＥのデータ表現を格納するコンピュータ２０の記憶手段と、当該データ表現の中から２次以上の項を１つ選択し、そのデータ表現の中で、２次以上の項に含まれる各変数ｘ１，…，ｘｄが取りうる値の組み合わせのうち、エネルギーＥの最小化配置の一部でない可能性が高い変数ｘ１，…，ｘｄの値の組み合わせを、２次以上の項の係数αと、変数ｘ１，…，ｘｄの値が１になる個数の偶奇とに基づいて選択し、２次以上の項の係数αと、変数ｘ１，…，ｘｄの値の組み合わせとから、変換前のエネルギーＥを、高階の項や非劣モジュラな項などの、最小化を難しくする項を減らしたエネルギーＥ’に変換するエネルギー変換手段としてのエネルギー変換部２４と、変換したエネルギーＥ’に対して所定のエネルギー最小化法を適用することにより、エネルギーＥが最小となる各変数を設定するエネルギー最小化手段としてのエネルギー最小化部２６と、を備えている。【０１７３】
この場合、エネルギーＥをデータ表現する多項式の中から、２次以上の項を選択し、その項の係数αと、変数ｘ１，…，ｘｄの値が１になる個数の偶奇とに基いて、エネルギーＥの最小化配置の一部でない可能性が高い変数ｘ１，…，ｘｄの値の組み合わせを選択すれば、これらの２次以上の項の係数αと、変数の値ｘ１，…，ｘｄの組み合わせとだけで、外部の変数を付加せずに、２次以下の劣モジュラな項のみからなる、或いは３次以上または非劣モジュラな項がより少ない、同値なエネルギーに変換することが可能になる。【０１７４】
そのため、処理対象が高階エネルギーであれば、外部の変数を付加せずに、２次以下の劣モジュラな項のみからなる、或いは３次以上または非劣モジュラな項がより少ない、同値なエネルギーに変換できる。その変換後のエネルギーをさらに、あるいは処理対象が最初から１階のエネルギーだった場合に、外部の変数を付加せずに、劣モジュラな１階の項のみからなる、或いは非劣モジュラな１階の項がより少ない、同値なエネルギーに変換できる。このように、外部の変数を付加しないので、従来手法に比べてコンピュータ２０の使用メモリが少なく、より高速に処理できる。【０１７５】
また、変換後のエネルギーに対して、１階のエネルギーの最小化が可能なグラフカット法などのエネルギー最小化アルゴリズムを適用することにより、少ない計算コストで適切に画像データの領域分割を行なうことが可能になり、必ずしもすべての３次以上または非劣モジュラな項をなくすことができない場合でも、本発明の装置を適用した後に従来手法を用いることで、従来手法のみを使った場合よりも使用メモリが少なく、より高速に処理できる利点がある。【０１７６】
したがって、エネルギーの高階項や非劣モジュラ項のような、エネルギー最小化を難しくしている項を、新たな変数を導入することなく削減することが可能となり、従来手法に比べて低い記憶容量および計算処理量コストで、高階エネルギーの最小化を実現することができる。【０１７７】
また、本発明のエネルギー変換部２４は、各実施例に共通して、前記２次以上の項をαｘ１…ｘｄとすると、実数ｑを選択し、前記変数ｘ１，…，ｘｄの値の組み合わせを、ｘ１＝ｕ１，…，ｘｄ＝ｕｄとしたときに、エネルギーＥを表す多項式に数２３を加えて、最小化を難しくする項を減らしたエネルギーＥ’に変換するように構成している。【０１７８】
この場合、エネルギー変換部２４で変換した後のエネルギーＥ’は、各変数ｘ１，…，ｘｄの値がｘ１＝ｕ１，…，ｘｄ＝ｕｄであるとき、変換前のエネルギーＥの値にｑを加えた値となり、各変数ｘ１，…，ｘｄの値がｘ１＝ｕ１，…，ｘｄ＝ｕｄでないとき、高階エネルギーＥの値と同じ値になる。そのため、ｑ＞０のときは、高階エネルギーＥの最小化配置において、各変数ｘ１，…，ｘｄの値がｘ１＝ｕ１，…，ｘｄ＝ｕｄでなければ、変換した後のエネルギーＥ’の最小値や最小化配置を、高階エネルギーＥの最小値や最小化配置と等しくすることが可能になる。【０１７９】
また、本発明のエネルギー変換部２４は、特に実施例１において、変数ｘ１，…，ｘｄの値の組み合わせについての第１の条件を、２次以上の項の係数αが０よりも小さければ、変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と同じであること、また２次以上の項の係数αが０よりも大きければ、変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と逆になることとし、変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄについての第２の条件を、前記変数ｘ１，…，ｘｄの値の別な組み合わせｘ１＝ｖ１，…，ｘｄ＝ｖｄであって、組み合わせｘ１＝ｖ１，…，ｘｄ＝ｖｄを満たす配置での第１の関数の最大値を、組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄを満たす配置での第１の関数の最小値から減算した差であるギャップが正であるものが存在することとしたときに、データ表現の中で、エネルギーＥ１に含まれる変数ｘ１，…，ｘｄ，…について、値の組み合わせを総当たりで行ない、第２の条件を満たす変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄであって、第１の条件を満たすか、２次以上の項の係数αの絶対値｜α｜より大きいギャップを持つものが存在するか否かを判定し、もし存在すれば、変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄを、前記変数の値の組み合わせとして選択し、実数ｑとして、該組み合わせが第１の条件を満たすならば｜α｜を選択し、満たさないならば−｜α｜を選択するように構成している。【０１８０】
この場合、エネルギーＥ１に含まれる変数ｘ１，…，ｘｄ，…について、値の組み合わせを総当たりで行ない、変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄであって、第１の条件を満たすか、第１の条件を満たさずギャップが２次以上の項の係数αの絶対値｜α｜より大きいものが存在すれば、その組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄが確実に高階エネルギーを最小化する配置の一部でないことを保証できる。したがって、そのような変数ｘ１，…，ｘｄの値の組み合わせｘ１＝ｕ１，…，ｘｄ＝ｕｄを選択した上で、エネルギー変換を行なえば、最小化する配置を確実に変えないまま、外部の変数を付加せずに、２次以下の劣モジュラな項のみからなる、或いは３次以上または非劣モジュラな項がより少ない、同値なエネルギーに変換することが可能になる。【０１８１】
また、本発明のエネルギー変換部２４は、特に実施例２において、コンピュータ２０の記憶手段に格納するデータ表現の中で、ｘ１，…，ｘｄ以外の変数を含まない項の和を第２の関数となるエネルギーＥ３としたときに、２次以上の項の係数αが０よりも小さければ、変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と同じになるような、また前記２次以上の項の係数αが０よりも大きければ、変数ｘ１，…，ｘｄのうち、値が１になるものの個数の偶奇が次数ｄの偶奇と逆になるような組み合わせの中から、変数ｘ１，…，ｘｄの値の組み合わせで、エネルギーＥ３の値が最大になるものを、上記変数の値の組み合わせとして選択するように構成している。【０１８２】
この場合、変数ｘ１，…，ｘｄの値の組み合わせで、エネルギーＥ３の値が最大になるものを、変数ｘ１，…，ｘｄの値の組み合わせとして必ず一つ選択できると共に、その一つの組み合わせを見つけるのに比較的時間がかからず、高速な演算処理が可能となる。【０１８３】
また、本発明のエネルギー変換部２４は、特に実施例３において、変数ｘ１，…，ｘｄの値の組み合わせをランダムに選択するように構成している。【０１８４】
この場合、高階エネルギーＥの最小化配置の一部でない可能性が高い変数ｘ１，…，ｘｄの値の組み合わせを必ず一つ選択できると共に、その一つの組み合わせを見つけるのに時間がかからず、極めて高速な演算処理が可能となる。【０１８５】
そして、上述した作用効果は、コンピュータ２０の記憶手段に格納した高階エネルギーＥのデータ表現を、上記のエネルギー変換部２４やエネルギー最小化部２６により処理する情報処理方法や、その情報処理方法をコンピュータ２０に実行させるプログラムにおいても同様に実現する。【０１８６】
上記実施例の情報処理方法や情報処理装置では、隣接する画素４点に依存する４次（３階）のエネルギー多項式を設定するものとしたが、周辺の画素５点以上に依存する５次（４階）以上のエネルギー、例えば、３次元空間内に配置された画素（ボクセル）について立体格子状に隣接する画素８点に依存する８次（７階）のエネルギーを設定するものとしてもよい。【０１８７】
実施例の情報処理方法や情報処理装置では、画像データの領域を分割する画像分割問題に本発明を適用して説明したが、これに限定されるものではなく、例えば、画像復元やステレオ，動画像解析などに本発明を適用することができるし、画像分野以外のデータ処理に適用することもできる。ここで、画像復元に本発明を適用する場合、例えば、現在の画像から若干の変化を与えた提案画像を生成し、現在の画像と生成した提案画像とを融合して新たな画像を生成する処理を繰り返し行なう融合移動アルゴリズムを用いることができる。ここで、「融合」とは、現在の画像における画素のデータ値と提案画像における対応する画素のデータ値とのうちエネルギーが小さくなる方のデータ値を新たな画像の対応する画素に設定することにより新たな画像を生成するものである。したがって、現在の画像のデータ値を維持するときにその画素に値０を割り当て提案画像のデータ値に置き換えるときに値１を割り当てるラベル割付問題として考えることができるから、エネルギー最小化法を用いて解くことができる。ここで、エネルギー（多項式）の実数係数としては、画像データを構成する画素の組のうちノイズが含まれる可能性が低いパターンほどエネルギーが小さくなるように設定することができる。また、提案画像としては、現在の画像を平滑化フィルタ（Gaussian kernel）を用いてぼかしたものを設定したり、エネルギーを各変数で偏微分して変数の数と同じ次元の勾配ベクトルを生成すると共に生成したベクトルの方向に現在の画像のデータ値から値をずらす再急降下法を用いて生成したりすることができる。勿論、これらの手法に限られず、例えば乱数画像を設定するなど如何なる手法も採用し得る。【０１８８】
実施例の情報処理方法や情報処理装置では、エネルギー変換における条件を示したが、その条件より厳しい条件を満たすことを要求する手法も採用しうる。例えば、実施例１において、α＜０の場合、次数ｄが奇数なら、奇のパリティを持つか、｜α｜より大きいギャップを持つような除外可能な局所配置を探し、ｄが偶数なら、偶のパリティを持つか、｜α｜より大きいギャップを持つような除外可能な局所配置を探すものとした。これは、エネルギー値を上昇させる場合だけでなく、ギャップ以内の下降も許すためにこのように条件を定めたが、簡単のため、エネルギー値を上昇させる場合だけを探すことにして、α＜０の場合、次数ｄが奇数なら、奇のパリティを持つ除外可能な局所配置を探し、ｄが偶数なら、偶のパリティを持つ除外可能な局所配置を探すこととすることもできる。【０１８９】
また実施例１において、２次の項を処理する場合には、非劣モジュラな項のみを処理することとしたが、すべての２次の項を処理して２次の項の数自体を減らすことにすることも可能である。また、非劣モジュラな項を処理するにあたり、その項の係数を０にして項自体を削除するように処理することにしたが、係数を負の数にして、項を劣モジュラにすることも可能である。【０１９０】
以上、本発明の実施の形態について実施例を用いて説明したが、本発明はこうした実施例に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において、種々なる形態で実施し得ることは勿論である。
【産業上の利用可能性】
【０１９１】
本発明は、上述した情報処理方法や情報処理装置の製造産業などに利用可能である。
【符号の説明】
【０１９２】
２０  コンピュータ
２４  エネルギー変換部
２６  エネルギー最小化部
【図１】
2015190593.tif 000034
【図２】
2015190593.tif 000035
【図３】
2015190593.tif 000036
【図４】
2015190593.tif 000037
【図５】
2015190593.tif 000038
【図６】
2015190593.tif 000039
【図７】
2015190593.tif 000040
【図８】
2015190593.tif 000041
【図９】
2015190593.tif 000042
【図１０】
2015190593.tif 000043
【国際調査報告】
2015190593.tif 000044
2015190593.tif 000045