情報処理方法および情報処理装置
【課題】各変数が２値の４次以上の多項式により表わすことが可能な高階エネルギーからなるデータを少ない計算コストで最小化する。
【解決手段】画像データの各画素に２値のラベルを割り当てることにより領域分割する場合、ラベルに対応する２値変数で４次以上の多項式で表わされる高階エネルギーを次数ｄが３以上の項毎に（ｄ−１）／２を超えない最大の整数の数だけ２値の外部変数を付加することにより１次および２次の基本対称式を用いて次数が２以下の１階のエネルギーに変換する（Ｓ２１０〜２５０）。これにより、１階のエネルギーの最小化が可能なグラフカット法などの既存のエネルギー最小化アルゴリズムを適用することができ、少ない計算コストで適切に画像データの領域分割を行なうことができる。
【解決手段】画像データの各画素に２値のラベルを割り当てることにより領域分割する場合、ラベルに対応する２値変数で４次以上の多項式で表わされる高階エネルギーを次数ｄが３以上の項毎に（ｄ−１）／２を超えない最大の整数の数だけ２値の外部変数を付加することにより１次および２次の基本対称式を用いて次数が２以下の１階のエネルギーに変換する（Ｓ２１０〜２５０）。これにより、１階のエネルギーの最小化が可能なグラフカット法などの既存のエネルギー最小化アルゴリズムを適用することができ、少ない計算コストで適切に画像データの領域分割を行なうことができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理方法および情報処理装置に関する。
【背景技術】
【０００２】
領域分割やステレオ，画像復元などの画像分野の問題をマルコフ確率場（Markov Random Field: MRF）などの確率モデルの最大事後確率推定問題として定式化してエネルギー最小化問題として効率的に解く方法としては、グラフカット（例えば、非特許文献１参照）や信念伝播法（例えば、非特許文献２参照）、ツリー重み再配分メッセージ伝達法（例えば、非特許文献３参照）などが提案されている。これらの手法では、エネルギーを比較的効率良く最小化することができるが、使用できるエネルギーの形は限られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】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 Mesage Passing for Energy Minimization." IEEE Transactions on Pattern Analysis and Machine Intelligence 28(10):1568-1583,2006.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
エネルギーが最高ｋ個の点に依存する関数の和により表わせるとき、MRFの用語では（ｋ−１）階のエネルギーと呼ぶが、上述した手法によって最小化可能なエネルギーの回数は最大でも２階に限られ、また実際にはほとんど１階のものしか使われていない。例えば、画像処理の分野では、各画素のみに依存する項と隣接する２つの画素のみに依存する項との和により表わされた１階のエネルギーが殆どである。近年、画像処理では自然画像の特徴をより高い精度で捉えるために高次の統計の重要性が指摘されており、高階のエネルギーを効率的に最小化する手法の構築が望まれる。
【０００５】
本発明の情報処理方法および情報処理装置は、各変数が２値の４次以上の多項式により表わされる高階エネルギーからなるデータを少ない計算コストで最小化することを主目的とする。
【課題を解決するための手段】
【０００６】
本発明の情報処理方法および情報処理装置は、上述の主目的を達成するために以下の手段を採った。
【０００７】
本発明の情報処理方法は、
各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理方法であって、
前記高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換し、
該変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより前記高階エネルギーが最小となる前記各変数を設定する
ことを特徴とする。
【０００８】
この本発明の情報処理方法では、各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換し、変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより高階エネルギーが最小となる各変数を設定する。これにより、少ない計算コストで高階エネルギーを最小化することができる。ここで、「同値」とは、変換後の１階のエネルギーを最小化する変数の設定が変換前の高階のエネルギーをも最小化することを意味する。また、「次数に応じた数の２値の外部変数」は、具体的には、各項について、次数をｄとすると（ｄ−１）／２を超えない最大の整数である。さらに、「所定のエネルギー最小化法」としては、グラフカット法，信念伝播法，ツリー重み再配分メッセージ伝達法などが含まれる。
【０００９】
こうした本発明の情報処理方法において、次数をｄとし係数をａとし前記変数をｘ1，…，ｘdとし値０か値１のいずれかをとる前記外部変数をｗとし１次の基本対称式をＳ1とし２次の基本対称式をＳ2とすると、前記高階エネルギーの多項式の各項毎に、係数ａが正の項に対しては該項の次数ｄが偶数のときには式（１）を用いて前記１階エネルギーの多項式に変換し、該項の次数ｄが奇数のときには式（２）を用いて前記１階エネルギーの多項式に変換するものとすることもできる。これは、任意の２次の対称式を１次および２次の基本対称式によって表わすことができることに基づく。
【００１０】
【数１】
【００１１】
この態様の本発明の情報処理方法において、前記高階エネルギー多項式の各項毎に係数ａが負の項に対しては式（３）を用いて前記１階エネルギーの多項式に変換するものとすることもできる。
【００１２】
【数２】
【００１３】
また、画像データを処理する本発明の情報処理方法において、前記画像データを構成する各画素のうち所定の条件に合致する画素に第１の値のラベルを割り当てると共に該所定の条件に合致しない画素に第２の値のラベルを割り当てる２値のラベルを前記変数として前記各画素だけに依存する１次の項と４点以上の画素の組に依存する４次以上の項とを含む多項式の高階エネルギーを設定し、該設定した高階エネルギーが最小となるよう前記変数を設定することにより前記２値のラベルを割り当てるものとすることもできる。こうすれば、所定の条件を用いた画像データの処理をより少ない計算コストで行なうことができる。ここで、「所定の条件」には、画像の領域を分割するための条件や画像に含まれるノイズを除去するための条件などが含まれる。
【００１４】
画像データを処理する態様の本発明の情報処理方法において、前記所定の条件に合致する確率が高いほどエネルギーが小さくなるよう各項の係数を定めることにより前記多項式の高階エネルギーを設定するものとすることもできる。この態様の本発明の情報処理方法において、前記所定の条件に合致する確率をＰとしたときにエネルギーが−ｌｏｇＰとなるよう前記各項の係数を定めるものとすることもできる。こうすれば、所定の条件により適合する高階のエネルギーを設定することができる。
【００１５】
また、画像データを処理する態様の本発明の情報処理方法において、現在の画像に対して変化を与えた提案画像を生成し前記現在の画像の画素を該生成した提案画像の対応する画素に置き換えるときには前記第１の値のラベルを割り当てると共に前記現在の画像の画素を前記生成した提案画像の対応する画素に置き換えないときには前記第２のラベルを割り当てることにより新たな画像を生成する処理を繰り返すことにより画像を復元するものとすることもできる。この態様の本発明の情報処理方法において、前記提案画像は、再急降下法を用いて生成するものとすることもできるし、前記現在の画像に対して所定のぼかしフィルタを適用することにより生成するものとすることもできる。
【００１６】
本発明の情報処理装置は、
各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理装置であって、
前記高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換するエネルギー変換手段と、
該変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより前記高階エネルギーが最小となる前記各変数を設定するエネルギー最小化手段と、
を備えることを要旨とする。
【００１７】
この本発明の情報処理装置では、各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換し、変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより高階エネルギーが最小となる各変数を設定する。これにより、少ない計算コストで高階エネルギーを最小化することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施例としての情報処理装置の構成の概略を示す構成図である。
【図２】画素に割り当てるラベルのパターンの一例を示す説明図である。
【図３】コンピュータ２０により実行される高階エネルギー設定処理の一例を示すフローチャートである。
【図４】画素のデータ値ＤとエネルギーＥ（Ｄ）との関係を示す説明図である。
【図５】コンピュータ２０により実行されるエネルギー変換処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１９】
次に、本発明の実施の形態を実施例を用いて説明する。
【実施例】
【００２０】
図１は、本発明の一実施例としての情報処理装置の構成の概略を示す構成図である。実施例の情報処理装置は、ＣＰＵやＲＯＭ，ＲＡＭ，入出力処理回路，ハードディスク，キーボード４０，マウス５０などを備える汎用のコンピュータ２０であり、デジタルカメラやＣＴ（Computed Tomography），ＭＲＩ（Magnetic Resonance Imaging），ＰＥＴ（Positron Emission Tomography）などの撮像装置や画像データを記憶する記憶装置に入力処理回路を介して接続されると共にディスプレイ３０やプリンタなどの出力機器に出力処理回路を介して接続されている。実施例では、コンピュータ２０は、画像処理用プログラムがインストールされており、これにより画像処理装置として機能する。
【００２１】
ＣＴやＭＲＩ，ＰＥＴなどから得られるデータは３次元の格子点に数値（データ値）を与えるものである。データ値は例えばＣＴなら空間内の各格子点がどれだけＸ線を吸収するかを表わす。２次元の断面画像なら各点の値に応じて色を変えれば全体を見ることができるが、３次元のデータは一望するのは困難である。したがって、例えば、ＣＴ画像のうち骨だけを見たいなら骨の部分だけを残し他の部分は透明にして３次元グラフィックス表示することになる。このためには、元画像を骨の部分とそれ以外の部分とに分割する必要がある（画像分割問題）。これは、値０が骨の部分で値１がそれ以外を表わすというように各格子点に値０か値１かのいずれかのラベルを与えるラベル割付問題として考えることができる。この場合、ある閾値を定めてデータ値が閾値よりも大きい点は値０を割り当て閾値以下の点は値１を割り当てものとすると、ノイズなどにより表面形状が荒いものとなる。このため、一般には隣接する格子点間ではあまり激しく値０と値１とが入れ替わらないように、即ち境界がなめらかになるような傾向をもたせる。このための手法の一つがエネルギー最小化による方法である。以下、実施例では、人のＣＴ画像に対して骨に該当する画素に値０のラベルを割り当てそれ以外の部分の画素に値１のラベルを割り当てることにより領域を分割する画像分割問題をエネルギー最小化法により解く場合を例として説明する。
【００２２】
コンピュータ２０は、その機能ブロックとしては、画像データの領域分割をエネルギー最小化法を用いて処理するための多項式（高階エネルギー）を設定する高階エネルギー設定部２２と、設定した高階エネルギーを２値の外部変数を付加して１階のエネルギーに変換するためのエネルギー変換部２４と、変換後の１階のエネルギーが最小となるよう各画素毎に値０か値１のラベルを割り当てて画像の領域分割を行なうエネルギー最小化部２６とを備え、これらは、ＣＰＵやＲＯＭ，ＲＡＭ，ハードディスクなどのハードウェアと画像処理用プログラムとが一体となって機能する。
【００２３】
高階エネルギー設定部２２は、各画素に対して割り当てる値０か値１のラベルを２値変数として上述した領域分割問題を解くための高次の多項式を設定する処理部であり、実施例では、画像データの各画素１点だけに基づいてエネルギーを設定する１次の項と、隣接する画素２点のパターン（図２（ａ）参照）に基づいてエネルギーを設定する２次の項と、隣接する２×２の画素４点のパターン（図２（ｂ）参照）に基づいてエネルギーを設定する４次の項との和により設定するものとした。
【００２４】
エネルギー変換部２４は、２値変数からなる３次以上（２階以上）のエネルギー多項式を２次（１階）のエネルギーに変換する処理部として構成されており、この変換は多項式の各項について基本対称式を用いて次数をｄとしたときに（ｄ−１）／２を超えない最大の整数に相当する数の２値の外部変数を付加することにより行なう。
【００２５】
ここで、２値変数をｘ，ｙ，ｚとする次数が３の項を２次の多項式に変換する場合、引用文献１によると、次式（４）に基づいて係数ａが負のときには両辺に係数ａを乗じた次式（５）により、係数ａが正のときにはｘ，ｙ，ｚをそれぞれ１−ｘ，１−ｙ，１−ｚに置き換えて計算した次式（６）により「ｍａｘ」を「ｍｉｎ」に代えることができる。ここで、式（４）〜（６）中の「ｗ」はＢ＝｛０，１｝の値しかとらない即ち値０か値１しかとらない外部変数である。この式（５）および式（６）は、最小化問題に３次の項ａｘｙｚが現われた場合、左辺を右辺に代えても最小値とこれをとるための変数ｘ，ｙ，ｚは変わらないことを意味する。即ち、変換後の関数で最小値を与える変数ｘ，ｙ，ｚは元の関数でも最小値を与える。しかし、式（７）に示すように、２値変数をｘ，ｙ，ｚ，ｔとする４次の項を考えると、上記の手法では、係数ａが正で且つ偶数次の項についてはｘ，ｙ，ｚ，ｔをそれぞれ１−ｘ，１−ｙ，１−ｚ，１−ｔに置き換えても「ｍａｘ」を「ｍｉｎ」に変えることができないため、使用することはできない。また、５以上の奇数次を考えても、展開後の式には４次などの偶数次の項が現われるから、同様に使用することはできない。
引用文献１：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)2:939-946.
【００２６】
【数３】
【００２７】
これに対して、実施例では、係数ａが正のときには、（ｄ−１）／２を超えない最大の整数に相当する数の２値の外部変数を付加することにより、式（８）に示す１次の基本対称式Ｓ１と２次の基本対称式Ｓ２とを用いて次数ｄが偶数の場合には次式（９）を、次数ｄが奇数の場合には次式（１０）を変換式として定めている。例えば、２値変数をｘ，ｙ，ｚ，ｔとする次数が４の項については、１つの２値の外部変数ｗを加えて次式（１１）により変換することができ、２値変数をｘ，ｙ，ｚ，ｔ，ｕとする次数が５の項については、２つの２値の外部変数ｖ，ｗを加えて次式（１２）により変換することができる。これらの式は、任意の２次の対称式を１次と２次の基本対称式によって表わすことができることを利用したものである。これにより、係数ａが正であっても、任意階のエネルギー多項式を１階のエネルギー多項式に変換することができる。なお、係数ａが負のときには、前述した式（４）や式（７）を一般化した次式（１３）を変換式として定めるものとした。
【００２８】
【数４】
【００２９】
エネルギー最小化部２６は、値０か値１の２値変数をもつ２次の多項式として表わされる１階のエネルギーが最小となる変数を見つける処理部として構成されており、処理アルゴリズムとしては、例えば、グラフカット法や信念伝播法，ツリー重み再配分メッセージ伝達法などを用いることができる。
【００３０】
次に、こうして構成された実施例の情報処理装置の動作、特に、高階エネルギー設定部２２の動作とエネルギー変換部２４の動作について説明する。まず、高階エネルギー設定部２２の動作について説明する。図３は、コンピュータ２０により実行される高階エネルギー設定処理の一例を示すフローチャートである。
【００３１】
高階エネルギー設定処理では、まず、画像データの各画素の１点のみに依存する項を次式（１４）により設定する（ステップＳ１００）。ここで、式（１４）中の「Ｘu」は画素ｕに対して割り当てるラベルとしての２値変数であり、「ａ1」，「ａ2」は実数係数である。実数係数ａ1は、Ｘu＝０即ち画素ｕが骨であるとしたときのエネルギー値Ｅ0（Ｄ）であり、画素ｕのデータ値Ｄが骨である可能性を示す確率をＰ0（Ｄ）としたときにａ1即ちＥ0（Ｄ）が−ｌｏｇＰ0（Ｄ）となるよう設定し、同様に、実数係数ａ2は、画素ｕのデータ値Ｄが骨でない可能性を示す確率をＰ1（Ｄ）としたときにａ2即ちＥ1（Ｄ）が−ｌｏｇＰ1（Ｄ）となるよう設定する。即ち、画素ｕが骨である可能性が高いほどＸu＝０としたときのエネルギーが小さくなるよう、また画素ｕが骨でない可能性が高いほどＸu＝１としたときのエネルギーが小さくなるよう実数係数ａ1，ａ2を設定するのである。勿論、画素ｕが骨である可能性が高ければＸu＝０としたときのエネルギーが小さくなり、画素ｕが骨でない可能性が高ければＸu＝１としたときのエネルギーが小さくなればよいから、上述した手法に限定されるものではなく、例えば、データ値Ｄ（あるいは確率Ｐ）とエネルギーＥとの関係を予め求めてマップとしてＲＯＭに記憶しておき、データ値Ｄが与えられたときにマップから対応するエネルギーＥを導出し、導出したエネルギーＥに基づいて設定するものとしてもよい。データ値ＤとエネルギーＥとの関係の一例を図４に示す。
【００３２】
【数５】
【００３３】
続いて、画像データの上下あるいは左右に隣接する２画素に依存する項を次式（１５）により設定する（ステップＳ１１０）。ここで、式（１５）中の「Ｘ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が与えられたときにマップから対応するエネルギーＥを導出し、導出したエネルギーＥに基づいて設定するものとしてもよい。
【００３４】
【数６】
【００３５】
そして、画像データの上下左右に隣接する画素４点に依存する項を次式（１６）により設定する（ステップＳ１２０）。ここで、式（１６）中の「Ｘu」，「Ｘv」，「Ｘs」，「Ｘt」は隣接する画素ｕ，ｖ，ｓ，ｔに対してそれぞれ割り当てる２値変数であり、「ｃ1〜ｃ16」は、実数係数である。上述したステップＳ１１０と同様に、実数係数ｃ1〜ｃ16は、Ｘu，Ｘv，Ｘs，Ｘtに値０か値１を与えたパターン毎に決定される各画素が骨であるかないかという組み合わせに対応するエネルギーであり、画素ｕ，ｖ，ｓ，ｔの各データ値Ｄu，Ｄv，Ｄs，Ｄtがその組み合わせである可能性を示す確率が高いほどエネルギーが小さくなるよう定められる。
【００３６】
【数７】
【００３７】
こうして各項を設定すると、各項の和をとると共にこれらを展開することにより４次の多項式を設定して（ステップＳ１３０）。本ルーチンを終了する。これにより、３階のエネルギーが設定される。実施例では、このエネルギーを最小化する各画素に対応した２値変数を見つけることにより画像データのうち骨の部分とそれ以外の部分とに分割する。
【００３８】
次に、エネルギー変換処理について説明する。図５は、エネルギー変換処理の一例を示すフローチャートである。このエネルギー変換処理では、まず、３次以上の変換対象の項を設定し（ステップＳ２００）、設定した変換対象の項の係数ａは正か否か（ステップＳ２１０）、次数ｄは奇数か否か（ステップＳ２２０）、をそれぞれ判定する。変換対象の項の係数ａが正でない即ち負のときには前述した式（１３）を用いて２次の多項式すなわち１階のエネルギーに変換し（ステップＳ２３０）、変換対象の項の係数ａが正であり且つ次数ｄが偶数のときには前述した式（９）を用いて１階のエネルギーに変換し（ステップＳ２４０）、変換対象の項の係数ａが正であり且つ次数ｄが奇数のときには前述した式（１０）を用いて１階のエネルギーに変換し（ステップＳ２５０）。そして、次数ｄが３以上の未変換の項があるときにはステップＳ２００に戻って新たに変換対象の項に設定してステップＳ２１０〜２５０の処理を繰り返し、次数ｄが３以上の未変換の項がなくなったときにこれで本処理を終了する。
【００３９】
こうして１階のエネルギー多項式に変換すると、既存のグラフカット法などのアルゴリズムを用いて各画素に対応した２値変数を設定し、変数Ｘuが値０すなわち骨である画素ｕに対して色を付すと共に変数Ｘuが値１すなわち骨でない画素ｕに対しては透明処理を施してディスプレイ３０に表示出力することにより、入力した画像のうち骨の部分だけを表示する。なお、グラフカット法などの適用によっても変数がわからないエラーが生じる可能性もあるが、予め定めた割り当てを行なったり、エラーが生じた変数だけで再びエネルギーを生成してエネルギー最小化アルゴリズムを適用したりすることにより対応することができる。
【００４０】
以上説明した実施例の情報処理装置によれば、画像データの各画素に２値のラベルを割り当てることにより領域分割する場合、ラベルに対応する２値変数を用いて４次以上の多項式である高階エネルギーを設定し、次数ｄが３以上の項毎に（ｄ−１）／２を超えない最大の整数の数だけ２値の外部変数を付加することにより１次および２次の基本対称式を用いて高階エネルギーを次数が２以下の１階のエネルギーに変換するから、１階のエネルギーの最小化が可能なグラフカット法などのエネルギー最小化アルゴリズムを適用することにより、少ない計算コストで適切に画像データの領域分割を行なうことができる。
【００４１】
実施例の情報処理装置では、隣接する画素４点に依存する４次（３階）のエネルギー多項式を設定するものとしたが、周辺の画素５点以上に依存する５次（４階）以上のエネルギー、例えば、３次元空間内に配置された画素（ボクセル）について立体格子状に隣接する画素８点に依存する８次（７階）のエネルギーを設定するものとしてもよい。
【００４２】
実施例の情報処理装置では、画像データの領域を分割する画像分割問題に本発明を適用して説明したが、これに限定されるものではなく、例えば、画像復元やステレオ，動画像解析などに本発明を適用することができるし、画像分野以外のデータ処理に適用することもできる。ここで、画像復元に本発明を適用する場合、例えば、現在の画像から若干の変化を与えた提案画像を生成し、現在の画像と生成した提案画像とを融合して新たな画像を生成する処理を繰り返し行なう融合移動アルゴリズムを用いることができる。ここで、「融合」とは、現在の画像における画素のデータ値と提案画像における対応する画素のデータ値とのうちエネルギーが小さくなる方のデータ値を新たな画像の対応する画素に設定することにより新たな画像を生成するものである。したがって、現在の画像のデータ値を維持するときにその画素に値０を割り当て提案画像のデータ値に置き換えるときに値１を割り当てるラベル割付問題として考えることができるから、エネルギー最小化法を用いて解くことができる。ここで、エネルギー（多項式）の実数係数としては、画像データを構成する画素の組のうちノイズが含まれる可能性が低いパターンほどエネルギーが小さくなるように設定することができる。また、提案画像としては、現在の画像を平滑化フィルタ（Gaussian kernel）を用いてぼかしたものを設定したり、エネルギーを各変数で偏微分して変数の数と同じ次元の勾配ベクトルを生成すると共に生成したベクトルの方向に現在の画像のデータ値から値をずらす再急降下法を用いて生成したりすることができる。勿論、これらの手法に限られず、例えば乱数画像を設定するなど如何なる手法も採用し得る。
【００４３】
以上、本発明の実施の形態について実施例を用いて説明したが、本発明はこうした実施例に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において、種々なる形態で実施し得ることは勿論である。
【産業上の利用可能性】
【００４４】
本発明は、情報処理装置や画像処理装置の製造産業などに利用可能である。
【符号の説明】
【００４５】
２０ コンピュータ、２２ 高階エネルギー設定部、２４ エネルギー変換部、２６ エネルギー最小化部、３０ ディスプレイ、４０ キーボード、５０ マウス。
【技術分野】
【０００１】
本発明は、各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理方法および情報処理装置に関する。
【背景技術】
【０００２】
領域分割やステレオ，画像復元などの画像分野の問題をマルコフ確率場（Markov Random Field: MRF）などの確率モデルの最大事後確率推定問題として定式化してエネルギー最小化問題として効率的に解く方法としては、グラフカット（例えば、非特許文献１参照）や信念伝播法（例えば、非特許文献２参照）、ツリー重み再配分メッセージ伝達法（例えば、非特許文献３参照）などが提案されている。これらの手法では、エネルギーを比較的効率良く最小化することができるが、使用できるエネルギーの形は限られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】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 Mesage Passing for Energy Minimization." IEEE Transactions on Pattern Analysis and Machine Intelligence 28(10):1568-1583,2006.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
エネルギーが最高ｋ個の点に依存する関数の和により表わせるとき、MRFの用語では（ｋ−１）階のエネルギーと呼ぶが、上述した手法によって最小化可能なエネルギーの回数は最大でも２階に限られ、また実際にはほとんど１階のものしか使われていない。例えば、画像処理の分野では、各画素のみに依存する項と隣接する２つの画素のみに依存する項との和により表わされた１階のエネルギーが殆どである。近年、画像処理では自然画像の特徴をより高い精度で捉えるために高次の統計の重要性が指摘されており、高階のエネルギーを効率的に最小化する手法の構築が望まれる。
【０００５】
本発明の情報処理方法および情報処理装置は、各変数が２値の４次以上の多項式により表わされる高階エネルギーからなるデータを少ない計算コストで最小化することを主目的とする。
【課題を解決するための手段】
【０００６】
本発明の情報処理方法および情報処理装置は、上述の主目的を達成するために以下の手段を採った。
【０００７】
本発明の情報処理方法は、
各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理方法であって、
前記高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換し、
該変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより前記高階エネルギーが最小となる前記各変数を設定する
ことを特徴とする。
【０００８】
この本発明の情報処理方法では、各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換し、変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより高階エネルギーが最小となる各変数を設定する。これにより、少ない計算コストで高階エネルギーを最小化することができる。ここで、「同値」とは、変換後の１階のエネルギーを最小化する変数の設定が変換前の高階のエネルギーをも最小化することを意味する。また、「次数に応じた数の２値の外部変数」は、具体的には、各項について、次数をｄとすると（ｄ−１）／２を超えない最大の整数である。さらに、「所定のエネルギー最小化法」としては、グラフカット法，信念伝播法，ツリー重み再配分メッセージ伝達法などが含まれる。
【０００９】
こうした本発明の情報処理方法において、次数をｄとし係数をａとし前記変数をｘ1，…，ｘdとし値０か値１のいずれかをとる前記外部変数をｗとし１次の基本対称式をＳ1とし２次の基本対称式をＳ2とすると、前記高階エネルギーの多項式の各項毎に、係数ａが正の項に対しては該項の次数ｄが偶数のときには式（１）を用いて前記１階エネルギーの多項式に変換し、該項の次数ｄが奇数のときには式（２）を用いて前記１階エネルギーの多項式に変換するものとすることもできる。これは、任意の２次の対称式を１次および２次の基本対称式によって表わすことができることに基づく。
【００１０】
【数１】
【００１１】
この態様の本発明の情報処理方法において、前記高階エネルギー多項式の各項毎に係数ａが負の項に対しては式（３）を用いて前記１階エネルギーの多項式に変換するものとすることもできる。
【００１２】
【数２】
【００１３】
また、画像データを処理する本発明の情報処理方法において、前記画像データを構成する各画素のうち所定の条件に合致する画素に第１の値のラベルを割り当てると共に該所定の条件に合致しない画素に第２の値のラベルを割り当てる２値のラベルを前記変数として前記各画素だけに依存する１次の項と４点以上の画素の組に依存する４次以上の項とを含む多項式の高階エネルギーを設定し、該設定した高階エネルギーが最小となるよう前記変数を設定することにより前記２値のラベルを割り当てるものとすることもできる。こうすれば、所定の条件を用いた画像データの処理をより少ない計算コストで行なうことができる。ここで、「所定の条件」には、画像の領域を分割するための条件や画像に含まれるノイズを除去するための条件などが含まれる。
【００１４】
画像データを処理する態様の本発明の情報処理方法において、前記所定の条件に合致する確率が高いほどエネルギーが小さくなるよう各項の係数を定めることにより前記多項式の高階エネルギーを設定するものとすることもできる。この態様の本発明の情報処理方法において、前記所定の条件に合致する確率をＰとしたときにエネルギーが−ｌｏｇＰとなるよう前記各項の係数を定めるものとすることもできる。こうすれば、所定の条件により適合する高階のエネルギーを設定することができる。
【００１５】
また、画像データを処理する態様の本発明の情報処理方法において、現在の画像に対して変化を与えた提案画像を生成し前記現在の画像の画素を該生成した提案画像の対応する画素に置き換えるときには前記第１の値のラベルを割り当てると共に前記現在の画像の画素を前記生成した提案画像の対応する画素に置き換えないときには前記第２のラベルを割り当てることにより新たな画像を生成する処理を繰り返すことにより画像を復元するものとすることもできる。この態様の本発明の情報処理方法において、前記提案画像は、再急降下法を用いて生成するものとすることもできるし、前記現在の画像に対して所定のぼかしフィルタを適用することにより生成するものとすることもできる。
【００１６】
本発明の情報処理装置は、
各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理装置であって、
前記高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換するエネルギー変換手段と、
該変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより前記高階エネルギーが最小となる前記各変数を設定するエネルギー最小化手段と、
を備えることを要旨とする。
【００１７】
この本発明の情報処理装置では、各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換し、変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより高階エネルギーが最小となる各変数を設定する。これにより、少ない計算コストで高階エネルギーを最小化することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施例としての情報処理装置の構成の概略を示す構成図である。
【図２】画素に割り当てるラベルのパターンの一例を示す説明図である。
【図３】コンピュータ２０により実行される高階エネルギー設定処理の一例を示すフローチャートである。
【図４】画素のデータ値ＤとエネルギーＥ（Ｄ）との関係を示す説明図である。
【図５】コンピュータ２０により実行されるエネルギー変換処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１９】
次に、本発明の実施の形態を実施例を用いて説明する。
【実施例】
【００２０】
図１は、本発明の一実施例としての情報処理装置の構成の概略を示す構成図である。実施例の情報処理装置は、ＣＰＵやＲＯＭ，ＲＡＭ，入出力処理回路，ハードディスク，キーボード４０，マウス５０などを備える汎用のコンピュータ２０であり、デジタルカメラやＣＴ（Computed Tomography），ＭＲＩ（Magnetic Resonance Imaging），ＰＥＴ（Positron Emission Tomography）などの撮像装置や画像データを記憶する記憶装置に入力処理回路を介して接続されると共にディスプレイ３０やプリンタなどの出力機器に出力処理回路を介して接続されている。実施例では、コンピュータ２０は、画像処理用プログラムがインストールされており、これにより画像処理装置として機能する。
【００２１】
ＣＴやＭＲＩ，ＰＥＴなどから得られるデータは３次元の格子点に数値（データ値）を与えるものである。データ値は例えばＣＴなら空間内の各格子点がどれだけＸ線を吸収するかを表わす。２次元の断面画像なら各点の値に応じて色を変えれば全体を見ることができるが、３次元のデータは一望するのは困難である。したがって、例えば、ＣＴ画像のうち骨だけを見たいなら骨の部分だけを残し他の部分は透明にして３次元グラフィックス表示することになる。このためには、元画像を骨の部分とそれ以外の部分とに分割する必要がある（画像分割問題）。これは、値０が骨の部分で値１がそれ以外を表わすというように各格子点に値０か値１かのいずれかのラベルを与えるラベル割付問題として考えることができる。この場合、ある閾値を定めてデータ値が閾値よりも大きい点は値０を割り当て閾値以下の点は値１を割り当てものとすると、ノイズなどにより表面形状が荒いものとなる。このため、一般には隣接する格子点間ではあまり激しく値０と値１とが入れ替わらないように、即ち境界がなめらかになるような傾向をもたせる。このための手法の一つがエネルギー最小化による方法である。以下、実施例では、人のＣＴ画像に対して骨に該当する画素に値０のラベルを割り当てそれ以外の部分の画素に値１のラベルを割り当てることにより領域を分割する画像分割問題をエネルギー最小化法により解く場合を例として説明する。
【００２２】
コンピュータ２０は、その機能ブロックとしては、画像データの領域分割をエネルギー最小化法を用いて処理するための多項式（高階エネルギー）を設定する高階エネルギー設定部２２と、設定した高階エネルギーを２値の外部変数を付加して１階のエネルギーに変換するためのエネルギー変換部２４と、変換後の１階のエネルギーが最小となるよう各画素毎に値０か値１のラベルを割り当てて画像の領域分割を行なうエネルギー最小化部２６とを備え、これらは、ＣＰＵやＲＯＭ，ＲＡＭ，ハードディスクなどのハードウェアと画像処理用プログラムとが一体となって機能する。
【００２３】
高階エネルギー設定部２２は、各画素に対して割り当てる値０か値１のラベルを２値変数として上述した領域分割問題を解くための高次の多項式を設定する処理部であり、実施例では、画像データの各画素１点だけに基づいてエネルギーを設定する１次の項と、隣接する画素２点のパターン（図２（ａ）参照）に基づいてエネルギーを設定する２次の項と、隣接する２×２の画素４点のパターン（図２（ｂ）参照）に基づいてエネルギーを設定する４次の項との和により設定するものとした。
【００２４】
エネルギー変換部２４は、２値変数からなる３次以上（２階以上）のエネルギー多項式を２次（１階）のエネルギーに変換する処理部として構成されており、この変換は多項式の各項について基本対称式を用いて次数をｄとしたときに（ｄ−１）／２を超えない最大の整数に相当する数の２値の外部変数を付加することにより行なう。
【００２５】
ここで、２値変数をｘ，ｙ，ｚとする次数が３の項を２次の多項式に変換する場合、引用文献１によると、次式（４）に基づいて係数ａが負のときには両辺に係数ａを乗じた次式（５）により、係数ａが正のときにはｘ，ｙ，ｚをそれぞれ１−ｘ，１−ｙ，１−ｚに置き換えて計算した次式（６）により「ｍａｘ」を「ｍｉｎ」に代えることができる。ここで、式（４）〜（６）中の「ｗ」はＢ＝｛０，１｝の値しかとらない即ち値０か値１しかとらない外部変数である。この式（５）および式（６）は、最小化問題に３次の項ａｘｙｚが現われた場合、左辺を右辺に代えても最小値とこれをとるための変数ｘ，ｙ，ｚは変わらないことを意味する。即ち、変換後の関数で最小値を与える変数ｘ，ｙ，ｚは元の関数でも最小値を与える。しかし、式（７）に示すように、２値変数をｘ，ｙ，ｚ，ｔとする４次の項を考えると、上記の手法では、係数ａが正で且つ偶数次の項についてはｘ，ｙ，ｚ，ｔをそれぞれ１−ｘ，１−ｙ，１−ｚ，１−ｔに置き換えても「ｍａｘ」を「ｍｉｎ」に変えることができないため、使用することはできない。また、５以上の奇数次を考えても、展開後の式には４次などの偶数次の項が現われるから、同様に使用することはできない。
引用文献１：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)2:939-946.
【００２６】
【数３】
【００２７】
これに対して、実施例では、係数ａが正のときには、（ｄ−１）／２を超えない最大の整数に相当する数の２値の外部変数を付加することにより、式（８）に示す１次の基本対称式Ｓ１と２次の基本対称式Ｓ２とを用いて次数ｄが偶数の場合には次式（９）を、次数ｄが奇数の場合には次式（１０）を変換式として定めている。例えば、２値変数をｘ，ｙ，ｚ，ｔとする次数が４の項については、１つの２値の外部変数ｗを加えて次式（１１）により変換することができ、２値変数をｘ，ｙ，ｚ，ｔ，ｕとする次数が５の項については、２つの２値の外部変数ｖ，ｗを加えて次式（１２）により変換することができる。これらの式は、任意の２次の対称式を１次と２次の基本対称式によって表わすことができることを利用したものである。これにより、係数ａが正であっても、任意階のエネルギー多項式を１階のエネルギー多項式に変換することができる。なお、係数ａが負のときには、前述した式（４）や式（７）を一般化した次式（１３）を変換式として定めるものとした。
【００２８】
【数４】
【００２９】
エネルギー最小化部２６は、値０か値１の２値変数をもつ２次の多項式として表わされる１階のエネルギーが最小となる変数を見つける処理部として構成されており、処理アルゴリズムとしては、例えば、グラフカット法や信念伝播法，ツリー重み再配分メッセージ伝達法などを用いることができる。
【００３０】
次に、こうして構成された実施例の情報処理装置の動作、特に、高階エネルギー設定部２２の動作とエネルギー変換部２４の動作について説明する。まず、高階エネルギー設定部２２の動作について説明する。図３は、コンピュータ２０により実行される高階エネルギー設定処理の一例を示すフローチャートである。
【００３１】
高階エネルギー設定処理では、まず、画像データの各画素の１点のみに依存する項を次式（１４）により設定する（ステップＳ１００）。ここで、式（１４）中の「Ｘu」は画素ｕに対して割り当てるラベルとしての２値変数であり、「ａ1」，「ａ2」は実数係数である。実数係数ａ1は、Ｘu＝０即ち画素ｕが骨であるとしたときのエネルギー値Ｅ0（Ｄ）であり、画素ｕのデータ値Ｄが骨である可能性を示す確率をＰ0（Ｄ）としたときにａ1即ちＥ0（Ｄ）が−ｌｏｇＰ0（Ｄ）となるよう設定し、同様に、実数係数ａ2は、画素ｕのデータ値Ｄが骨でない可能性を示す確率をＰ1（Ｄ）としたときにａ2即ちＥ1（Ｄ）が−ｌｏｇＰ1（Ｄ）となるよう設定する。即ち、画素ｕが骨である可能性が高いほどＸu＝０としたときのエネルギーが小さくなるよう、また画素ｕが骨でない可能性が高いほどＸu＝１としたときのエネルギーが小さくなるよう実数係数ａ1，ａ2を設定するのである。勿論、画素ｕが骨である可能性が高ければＸu＝０としたときのエネルギーが小さくなり、画素ｕが骨でない可能性が高ければＸu＝１としたときのエネルギーが小さくなればよいから、上述した手法に限定されるものではなく、例えば、データ値Ｄ（あるいは確率Ｐ）とエネルギーＥとの関係を予め求めてマップとしてＲＯＭに記憶しておき、データ値Ｄが与えられたときにマップから対応するエネルギーＥを導出し、導出したエネルギーＥに基づいて設定するものとしてもよい。データ値ＤとエネルギーＥとの関係の一例を図４に示す。
【００３２】
【数５】
【００３３】
続いて、画像データの上下あるいは左右に隣接する２画素に依存する項を次式（１５）により設定する（ステップＳ１１０）。ここで、式（１５）中の「Ｘ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が与えられたときにマップから対応するエネルギーＥを導出し、導出したエネルギーＥに基づいて設定するものとしてもよい。
【００３４】
【数６】
【００３５】
そして、画像データの上下左右に隣接する画素４点に依存する項を次式（１６）により設定する（ステップＳ１２０）。ここで、式（１６）中の「Ｘu」，「Ｘv」，「Ｘs」，「Ｘt」は隣接する画素ｕ，ｖ，ｓ，ｔに対してそれぞれ割り当てる２値変数であり、「ｃ1〜ｃ16」は、実数係数である。上述したステップＳ１１０と同様に、実数係数ｃ1〜ｃ16は、Ｘu，Ｘv，Ｘs，Ｘtに値０か値１を与えたパターン毎に決定される各画素が骨であるかないかという組み合わせに対応するエネルギーであり、画素ｕ，ｖ，ｓ，ｔの各データ値Ｄu，Ｄv，Ｄs，Ｄtがその組み合わせである可能性を示す確率が高いほどエネルギーが小さくなるよう定められる。
【００３６】
【数７】
【００３７】
こうして各項を設定すると、各項の和をとると共にこれらを展開することにより４次の多項式を設定して（ステップＳ１３０）。本ルーチンを終了する。これにより、３階のエネルギーが設定される。実施例では、このエネルギーを最小化する各画素に対応した２値変数を見つけることにより画像データのうち骨の部分とそれ以外の部分とに分割する。
【００３８】
次に、エネルギー変換処理について説明する。図５は、エネルギー変換処理の一例を示すフローチャートである。このエネルギー変換処理では、まず、３次以上の変換対象の項を設定し（ステップＳ２００）、設定した変換対象の項の係数ａは正か否か（ステップＳ２１０）、次数ｄは奇数か否か（ステップＳ２２０）、をそれぞれ判定する。変換対象の項の係数ａが正でない即ち負のときには前述した式（１３）を用いて２次の多項式すなわち１階のエネルギーに変換し（ステップＳ２３０）、変換対象の項の係数ａが正であり且つ次数ｄが偶数のときには前述した式（９）を用いて１階のエネルギーに変換し（ステップＳ２４０）、変換対象の項の係数ａが正であり且つ次数ｄが奇数のときには前述した式（１０）を用いて１階のエネルギーに変換し（ステップＳ２５０）。そして、次数ｄが３以上の未変換の項があるときにはステップＳ２００に戻って新たに変換対象の項に設定してステップＳ２１０〜２５０の処理を繰り返し、次数ｄが３以上の未変換の項がなくなったときにこれで本処理を終了する。
【００３９】
こうして１階のエネルギー多項式に変換すると、既存のグラフカット法などのアルゴリズムを用いて各画素に対応した２値変数を設定し、変数Ｘuが値０すなわち骨である画素ｕに対して色を付すと共に変数Ｘuが値１すなわち骨でない画素ｕに対しては透明処理を施してディスプレイ３０に表示出力することにより、入力した画像のうち骨の部分だけを表示する。なお、グラフカット法などの適用によっても変数がわからないエラーが生じる可能性もあるが、予め定めた割り当てを行なったり、エラーが生じた変数だけで再びエネルギーを生成してエネルギー最小化アルゴリズムを適用したりすることにより対応することができる。
【００４０】
以上説明した実施例の情報処理装置によれば、画像データの各画素に２値のラベルを割り当てることにより領域分割する場合、ラベルに対応する２値変数を用いて４次以上の多項式である高階エネルギーを設定し、次数ｄが３以上の項毎に（ｄ−１）／２を超えない最大の整数の数だけ２値の外部変数を付加することにより１次および２次の基本対称式を用いて高階エネルギーを次数が２以下の１階のエネルギーに変換するから、１階のエネルギーの最小化が可能なグラフカット法などのエネルギー最小化アルゴリズムを適用することにより、少ない計算コストで適切に画像データの領域分割を行なうことができる。
【００４１】
実施例の情報処理装置では、隣接する画素４点に依存する４次（３階）のエネルギー多項式を設定するものとしたが、周辺の画素５点以上に依存する５次（４階）以上のエネルギー、例えば、３次元空間内に配置された画素（ボクセル）について立体格子状に隣接する画素８点に依存する８次（７階）のエネルギーを設定するものとしてもよい。
【００４２】
実施例の情報処理装置では、画像データの領域を分割する画像分割問題に本発明を適用して説明したが、これに限定されるものではなく、例えば、画像復元やステレオ，動画像解析などに本発明を適用することができるし、画像分野以外のデータ処理に適用することもできる。ここで、画像復元に本発明を適用する場合、例えば、現在の画像から若干の変化を与えた提案画像を生成し、現在の画像と生成した提案画像とを融合して新たな画像を生成する処理を繰り返し行なう融合移動アルゴリズムを用いることができる。ここで、「融合」とは、現在の画像における画素のデータ値と提案画像における対応する画素のデータ値とのうちエネルギーが小さくなる方のデータ値を新たな画像の対応する画素に設定することにより新たな画像を生成するものである。したがって、現在の画像のデータ値を維持するときにその画素に値０を割り当て提案画像のデータ値に置き換えるときに値１を割り当てるラベル割付問題として考えることができるから、エネルギー最小化法を用いて解くことができる。ここで、エネルギー（多項式）の実数係数としては、画像データを構成する画素の組のうちノイズが含まれる可能性が低いパターンほどエネルギーが小さくなるように設定することができる。また、提案画像としては、現在の画像を平滑化フィルタ（Gaussian kernel）を用いてぼかしたものを設定したり、エネルギーを各変数で偏微分して変数の数と同じ次元の勾配ベクトルを生成すると共に生成したベクトルの方向に現在の画像のデータ値から値をずらす再急降下法を用いて生成したりすることができる。勿論、これらの手法に限られず、例えば乱数画像を設定するなど如何なる手法も採用し得る。
【００４３】
以上、本発明の実施の形態について実施例を用いて説明したが、本発明はこうした実施例に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において、種々なる形態で実施し得ることは勿論である。
【産業上の利用可能性】
【００４４】
本発明は、情報処理装置や画像処理装置の製造産業などに利用可能である。
【符号の説明】
【００４５】
２０ コンピュータ、２２ 高階エネルギー設定部、２４ エネルギー変換部、２６ エネルギー最小化部、３０ ディスプレイ、４０ キーボード、５０ マウス。
【特許請求の範囲】
【請求項１】
各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理方法であって、
前記高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換し、
該変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより前記高階エネルギーが最小となる前記各変数を設定する
ことを特徴とする情報処理方法。
【請求項２】
請求項１記載の情報処理方法であって、
次数をｄとし係数をａとし前記変数をｘ1，…，ｘdとし値０か値１のいずれかをとる前記外部変数をｗとし１次の基本対称式をＳ1とし２次の基本対称式をＳ2とすると、前記高階エネルギーの多項式の各項毎に、係数ａが正の項に対しては該項の次数ｄが偶数のときには式（１）を用いて前記１階エネルギーの多項式に変換し、該項の次数ｄが奇数のときには式（２）を用いて前記１階エネルギーの多項式に変換する
ことを特徴とする情報処理方法。
【数１】
【請求項３】
請求項２記載の情報処理方法であって、
前記高階エネルギー多項式の各項毎に係数ａが負の項に対しては式（３）を用いて前記１階エネルギーの多項式に変換する
ことを特徴とする情報処理方法。
【数２】
【請求項４】
前記所定のエネルギー最小化法は、グラフカット法，信念伝播法，ツリー重み再配分メッセージ伝達法のいずれかである請求項１ないし３いずれか１項に記載の情報処理方法。
【請求項５】
画像データを処理する請求項１ないし４いずれか１項に記載の情報処理方法であって、
前記画像データを構成する各画素のうち所定の条件に合致する画素に第１の値のラベルを割り当てると共に該所定の条件に合致しない画素に第２の値のラベルを割り当てる２値のラベルを前記変数として前記各画素だけに依存する１次の項と４点以上の画素の組に依存する４次以上の項とを含む多項式の高階エネルギーを設定し、該設定した高階エネルギーが最小となるよう前記変数を設定することにより前記２値のラベルを割り当てる
ことを特徴とする情報処理方法。
【請求項６】
前記所定の条件に合致する確率が高いほどエネルギーが小さくなるよう各項の係数を定めることにより前記多項式の高階エネルギーを設定することを特徴とする請求項５記載の情報処理方法。
【請求項７】
前記所定の条件に合致する確率をＰとしたときにエネルギーが−ｌｏｇＰとなるよう前記各項の係数を定めることを特徴とする請求項６記載の情報処理方法。
【請求項８】
請求項５ないし７いずれか１項に記載の情報処理方法であって、
現在の画像に対して変化を与えた提案画像を生成し前記現在の画像の画素を該生成した提案画像の対応する画素に置き換えるときには前記第１の値のラベルを割り当てると共に前記現在の画像の画素を前記生成した提案画像の対応する画素に置き換えないときには前記第２のラベルを割り当てることにより新たな画像を生成する処理を繰り返すことにより画像を復元する
ことを特徴とする情報処理方法。
【請求項９】
前記提案画像は、再急降下法を用いて生成することを特徴とする請求項８記載の情報処理方法。
【請求項１０】
前記提案画像は、前記現在の画像に対して所定のぼかしフィルタを適用することにより生成することを特徴とする請求項８記載の情報処理方法。
【請求項１１】
各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理装置であって、
前記高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換するエネルギー変換手段と、
該変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより前記高階エネルギーが最小となる前記各変数を設定するエネルギー最小化手段と、
を備える情報処理装置。
【請求項１】
各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理方法であって、
前記高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換し、
該変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより前記高階エネルギーが最小となる前記各変数を設定する
ことを特徴とする情報処理方法。
【請求項２】
請求項１記載の情報処理方法であって、
次数をｄとし係数をａとし前記変数をｘ1，…，ｘdとし値０か値１のいずれかをとる前記外部変数をｗとし１次の基本対称式をＳ1とし２次の基本対称式をＳ2とすると、前記高階エネルギーの多項式の各項毎に、係数ａが正の項に対しては該項の次数ｄが偶数のときには式（１）を用いて前記１階エネルギーの多項式に変換し、該項の次数ｄが奇数のときには式（２）を用いて前記１階エネルギーの多項式に変換する
ことを特徴とする情報処理方法。
【数１】
【請求項３】
請求項２記載の情報処理方法であって、
前記高階エネルギー多項式の各項毎に係数ａが負の項に対しては式（３）を用いて前記１階エネルギーの多項式に変換する
ことを特徴とする情報処理方法。
【数２】
【請求項４】
前記所定のエネルギー最小化法は、グラフカット法，信念伝播法，ツリー重み再配分メッセージ伝達法のいずれかである請求項１ないし３いずれか１項に記載の情報処理方法。
【請求項５】
画像データを処理する請求項１ないし４いずれか１項に記載の情報処理方法であって、
前記画像データを構成する各画素のうち所定の条件に合致する画素に第１の値のラベルを割り当てると共に該所定の条件に合致しない画素に第２の値のラベルを割り当てる２値のラベルを前記変数として前記各画素だけに依存する１次の項と４点以上の画素の組に依存する４次以上の項とを含む多項式の高階エネルギーを設定し、該設定した高階エネルギーが最小となるよう前記変数を設定することにより前記２値のラベルを割り当てる
ことを特徴とする情報処理方法。
【請求項６】
前記所定の条件に合致する確率が高いほどエネルギーが小さくなるよう各項の係数を定めることにより前記多項式の高階エネルギーを設定することを特徴とする請求項５記載の情報処理方法。
【請求項７】
前記所定の条件に合致する確率をＰとしたときにエネルギーが−ｌｏｇＰとなるよう前記各項の係数を定めることを特徴とする請求項６記載の情報処理方法。
【請求項８】
請求項５ないし７いずれか１項に記載の情報処理方法であって、
現在の画像に対して変化を与えた提案画像を生成し前記現在の画像の画素を該生成した提案画像の対応する画素に置き換えるときには前記第１の値のラベルを割り当てると共に前記現在の画像の画素を前記生成した提案画像の対応する画素に置き換えないときには前記第２のラベルを割り当てることにより新たな画像を生成する処理を繰り返すことにより画像を復元する
ことを特徴とする情報処理方法。
【請求項９】
前記提案画像は、再急降下法を用いて生成することを特徴とする請求項８記載の情報処理方法。
【請求項１０】
前記提案画像は、前記現在の画像に対して所定のぼかしフィルタを適用することにより生成することを特徴とする請求項８記載の情報処理方法。
【請求項１１】
各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理装置であって、
前記高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換するエネルギー変換手段と、
該変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより前記高階エネルギーが最小となる前記各変数を設定するエネルギー最小化手段と、
を備える情報処理装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１０−２８７０９１（Ｐ２０１０−２８７０９１Ａ）
【公開日】平成２２年１２月２４日（２０１０．１２．２４）
【国際特許分類】
【出願番号】特願２００９−１４０９９８（Ｐ２００９−１４０９９８）
【出願日】平成２１年６月１２日（２００９．６．１２）
【出願人】（５０６２１８６６４）公立大学法人名古屋市立大学 (48)
【Ｆターム（参考）】
【公開日】平成２２年１２月２４日（２０１０．１２．２４）
【国際特許分類】
【出願日】平成２１年６月１２日（２００９．６．１２）
【出願人】（５０６２１８６６４）公立大学法人名古屋市立大学 (48)
【Ｆターム（参考）】
[ Back to top ]