JP5564643B2

JP5564643B2 - 情報処理方法および情報処理装置

Info

Publication number: JP5564643B2
Application number: JP2009140998A
Authority: JP
Inventors: 博石川
Original assignee: Individual
Current assignee: Individual
Priority date: 2009-06-12
Filing date: 2009-06-12
Publication date: 2014-07-30
Anticipated expiration: 2029-06-12
Also published as: JP2010287091A; WO2010143561A1

Description

本発明は、各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理方法および情報処理装置に関する。

領域分割やステレオ，画像復元などの画像分野の問題をマルコフ確率場（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の用語では（ｋ−１）階のエネルギーと呼ぶが、上述した手法によって最小化可能なエネルギーの回数は最大でも２階に限られ、また実際にはほとんど１階のものしか使われていない。例えば、画像処理の分野では、各画素のみに依存する項と隣接する２つの画素のみに依存する項との和により表わされた１階のエネルギーが殆どである。近年、画像処理では自然画像の特徴をより高い精度で捉えるために高次の統計の重要性が指摘されており、高階のエネルギーを効率的に最小化する手法の構築が望まれる。

本発明の情報処理方法および情報処理装置は、各変数が２値の４次以上の多項式により表わされる高階エネルギーからなるデータを少ない計算コストで最小化することを主目的とする。

本発明の情報処理方法および情報処理装置は、上述の主目的を達成するために以下の手段を採った。

本発明の情報処理方法は、
各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理方法であって、
前記高階エネルギーのデータ表現を記憶手段に格納し、
前記高階エネルギーに対称式を用いて次数に応じた数の２値の外部変数を付加することに対応するように該格納したデータ表現を演算手段により変更することにより前記高階エネルギーを同値な１階のエネルギーに変換し、
該変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより
前記高階エネルギーが最小となる前記各変数を設定する
ことを特徴とする。

この本発明の情報処理方法では、各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換し、変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより高階エネルギーが最小となる各変数を設定する。これにより、少ない計算コストで高階エネルギーを最小化することができる。ここで、「同値」とは、変換後の１階のエネルギーを最小化する変数の設定が変換前の高階のエネルギーをも最小化することを意味する。また、「次数に応じた数の２値の外部変数」は、具体的には、各項について、次数をｄとすると（ｄ−１）／２を超えない最大の整数である。さらに、「所定のエネルギー最小化法」としては、グラフカット法，信念伝播法，ツリー重み再配分メッセージ伝達法などが含まれる。

こうした本発明の情報処理方法において、次数をｄとし係数をａとし前記変数をｘ₁，…，ｘ_dとし値０か値１のいずれかをとる前記外部変数をｗとし１次の基本対称式をＳ₁とし２次の基本対称式をＳ₂とすると、前記高階エネルギーの多項式の各項毎に、係数ａが正の項に対しては該項の次数ｄが偶数のときには式（１）を用いて前記１階エネルギーの多項式に変換し、該項の次数ｄが奇数のときには式（２）を用いて前記１階エネルギーの多項式に変換するものとすることもできる。これは、任意の２次の対称式を１次および２次の基本対称式によって表わすことができることに基づく。

この態様の本発明の情報処理方法において、前記高階エネルギー多項式の各項毎に係数ａが負の項に対しては式（３）を用いて前記１階エネルギーの多項式に変換するものとすることもできる。

また、画像データを処理する本発明の情報処理方法において、前記画像データを構成する各画素のうち所定の条件に合致する画素に第１の値のラベルを割り当てると共に該所定の条件に合致しない画素に第２の値のラベルを割り当てる２値のラベルを前記変数として前記各画素だけに依存する１次の項と４点以上の画素の組に依存する４次以上の項とを含む多項式の高階エネルギーを設定し、該設定した高階エネルギーが最小となるよう前記変数を設定することにより前記２値のラベルを割り当てるものとすることもできる。こうすれば、所定の条件を用いた画像データの処理をより少ない計算コストで行なうことができる。ここで、「所定の条件」には、画像の領域を分割するための条件や画像に含まれるノイズを除去するための条件などが含まれる。

画像データを処理する態様の本発明の情報処理方法において、前記所定の条件に合致する確率が高いほどエネルギーが小さくなるよう各項の係数を定めることにより前記多項式の高階エネルギーを設定するものとすることもできる。この態様の本発明の情報処理方法において、前記所定の条件に合致する確率をＰとしたときにエネルギーが−ｌｏｇＰとなるよう前記各項の係数を定めるものとすることもできる。こうすれば、所定の条件により適合する高階のエネルギーを設定することができる。

また、画像データを処理する態様の本発明の情報処理方法において、現在の画像に対して変化を与えた提案画像を生成し前記現在の画像の画素を該生成した提案画像の対応する画素に置き換えるときには前記第１の値のラベルを割り当てると共に前記現在の画像の画素を前記生成した提案画像の対応する画素に置き換えないときには前記第２のラベルを割り当てることにより新たな画像を生成する処理を繰り返すことにより画像を復元するものとすることもできる。この態様の本発明の情報処理方法において、前記提案画像は、再急降下法を用いて生成するものとすることもできるし、前記現在の画像に対して所定のぼかしフィルタを適用することにより生成するものとすることもできる。

本発明の情報処理装置は、
各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理装置であって、
前記高階エネルギーのデータ表現を格納する記憶手段と、
前記高階エネルギーに対称式を用いて次数に応じた数の２値の外部変数を付加することに対応するように該格納したデータ表現を変更する演算手段と、
前記高階エネルギーを該データ表現の変更により同値な１階のエネルギーに変換するエネルギー変換手段と、
該変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより前記高階エネルギーが最小となる前記各変数を設定するエネルギー最小化手段と、
を備えることを要旨とする。

この本発明の情報処理装置では、各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを対称式を用いて次数に応じた数の２値の外部変数を付加することにより同値な１階のエネルギーに変換し、変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより高階エネルギーが最小となる各変数を設定する。これにより、少ない計算コストで高階エネルギーを最小化することができる。

本発明の一実施例としての情報処理装置の構成の概略を示す構成図である。画素に割り当てるラベルのパターンの一例を示す説明図である。コンピュータ２０により実行される高階エネルギー設定処理の一例を示すフローチャートである。画素のデータ値ＤとエネルギーＥ（Ｄ）との関係を示す説明図である。コンピュータ２０により実行されるエネルギー変換処理の一例を示すフローチャートである。

次に、本発明の実施の形態を実施例を用いて説明する。

図１は、本発明の一実施例としての情報処理装置の構成の概略を示す構成図である。実施例の情報処理装置は、ＣＰＵやＲＯＭ，ＲＡＭ，入出力処理回路，ハードディスク，キーボード４０，マウス５０などを備える汎用のコンピュータ２０であり、デジタルカメラやＣＴ（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」は画素ｕに対して割り当てるラベルとしての２値変数であり、「ａ₁」，「ａ₂」は実数係数である。実数係数ａ₁は、Ｘ_u＝０即ち画素ｕが骨であるとしたときのエネルギー値Ｅ₀（Ｄ）であり、画素ｕのデータ値Ｄが骨である可能性を示す確率をＰ₀（Ｄ）としたときにａ₁即ちＥ₀（Ｄ）が−ｌｏｇＰ₀（Ｄ）となるよう設定し、同様に、実数係数ａ₂は、画素ｕのデータ値Ｄが骨でない可能性を示す確率をＰ₁（Ｄ）としたときにａ₂即ちＥ₁（Ｄ）が−ｌｏｇＰ₁（Ｄ）となるよう設定する。即ち、画素ｕが骨である可能性が高いほどＸ_u＝０としたときのエネルギーが小さくなるよう、また画素ｕが骨でない可能性が高いほどＸ_u＝１としたときのエネルギーが小さくなるよう実数係数ａ₁，ａ₂を設定するのである。勿論、画素ｕが骨である可能性が高ければＸ_u＝０としたときのエネルギーが小さくなり、画素ｕが骨でない可能性が高ければＸ_u＝１としたときのエネルギーが小さくなればよいから、上述した手法に限定されるものではなく、例えば、データ値Ｄ（あるいは確率Ｐ）とエネルギーＥとの関係を予め求めてマップとしてＲＯＭに記憶しておき、データ値Ｄが与えられたときにマップから対応するエネルギーＥを導出し、導出したエネルギーＥに基づいて設定するものとしてもよい。データ値ＤとエネルギーＥとの関係の一例を図４に示す。

続いて、画像データの上下あるいは左右に隣接する２画素に依存する項を次式（１５）により設定する（ステップＳ１１０）。ここで、式（１５）中の「Ｘ_u」，「Ｘ_v」は隣接する画素ｕ，ｖに対してそれぞれ割り当てるラベルとしての２値変数であり、「ｂ₁〜ｂ₄」は、実数係数である。実数係数ｂ₁は、Ｘ_u＝１，Ｘ_v＝１即ち画素ｕ，ｖが共に骨でないとしたときのエネルギー値Ｅ₁₁（Ｄ_u，Ｄ_v）であり、画素ｕ，ｖのデータ値Ｄ_u，Ｄ_vが画素ｕ，ｖが共に骨でない可能性を示す確率をＰ₁₁（Ｄ_u，Ｄ_v）としたときにｂ₁即ちＥ₁₁（Ｄ_u，Ｄ_v）が−ｌｏｇＰ₁₁（Ｄ_u，Ｄ_v）となるよう設定するものとした。実数係数ｂ₂は、Ｘ_u＝０，Ｘ_v＝１即ち画素ｕが骨であり画素ｖが骨でないとしたときのエネルギー値Ｅ₀₁（Ｄ_u，Ｄ_v）であり、画素ｕ，ｖのデータ値Ｄ_u，Ｄ_vが画素ｕが骨であり画素ｖが骨でない可能性を示す確率をＰ₀₁（Ｄ_u，Ｄ_v）としたときにｂ₂即ちＥ₀₁（Ｄ_u，Ｄ_v）が−ｌｏｇＰ₀₁（Ｄ_u，Ｄ_v）となるよう設定するものとした。実数係数ｂ₃は、Ｘ_u＝１，Ｘ_v＝０即ち画素ｕが骨でなく画素ｖが骨であるとしたときのエネルギー値Ｅ₁₀（Ｄ_u，Ｄ_v）であり、画素ｕ，ｖのデータ値Ｄ_u，Ｄ_vが画素ｕが骨でなく画素ｖが骨である可能性を示す確率をＰ₁₀（Ｄ_u，Ｄ_v）としたときにｂ₃即ちＥ₁₀（Ｄ_u，Ｄ_v）が−ｌｏｇＰ₁₀（Ｄ_u，Ｄ_v）となるよう設定するものとした。実数係数ｂ₄は、Ｘ_u＝０，Ｘ_v＝０即ち画素ｕ，ｖが共に骨であるとしたときのエネルギー値Ｅ₀₀（Ｄ_u，Ｄ_v）であり、画素ｕ，ｖのデータ値Ｄ_u，Ｄ_vが共に骨である可能性を示す確率をＰ₀₀（Ｄ_u，Ｄ_v）としたときにｂ₄即ちＥ₀₀（Ｄ_u，Ｄ_v）が−ｌｏｇＰ₀₀（Ｄ_u，Ｄ_v）となるよう設定するものとした。なお、この場合も、例えば、データ値Ｄ_u，Ｄ_v（あるいは確率）とエネルギーＥとの関係を予め求めてマップとしてＲＯＭに記憶しておき、データ値Ｄ_u，Ｄ_vが与えられたときにマップから対応するエネルギーＥを導出し、導出したエネルギーＥに基づいて設定するものとしてもよい。

そして、画像データの上下左右に隣接する画素４点に依存する項を次式（１６）により設定する（ステップＳ１２０）。ここで、式（１６）中の「Ｘ_u」，「Ｘ_v」，「Ｘ_s」，「Ｘ_t」は隣接する画素ｕ，ｖ，ｓ，ｔに対してそれぞれ割り当てる２値変数であり、「ｃ₁〜ｃ₁₆」は、実数係数である。上述したステップＳ１１０と同様に、実数係数ｃ₁〜ｃ₁₆は、Ｘ_u，Ｘ_v，Ｘ_s，Ｘ_tに値０か値１を与えたパターン毎に決定される各画素が骨であるかないかという組み合わせに対応するエネルギーであり、画素ｕ，ｖ，ｓ，ｔの各データ値Ｄ_u，Ｄ_v，Ｄ_s，Ｄ_tがその組み合わせである可能性を示す確率が高いほどエネルギーが小さくなるよう定められる。

こうして各項を設定すると、各項の和をとると共にこれらを展開することにより４次の多項式を設定して（ステップＳ１３０）。本ルーチンを終了する。これにより、３階のエネルギーが設定される。実施例では、このエネルギーを最小化する各画素に対応した２値変数を見つけることにより画像データのうち骨の部分とそれ以外の部分とに分割する。

次に、エネルギー変換処理について説明する。図５は、エネルギー変換処理の一例を示すフローチャートである。このエネルギー変換処理では、まず、３次以上の変換対象の項を設定し（ステップＳ２００）、設定した変換対象の項の係数ａは正か否か（ステップＳ２１０）、次数ｄは奇数か否か（ステップＳ２２０）、をそれぞれ判定する。変換対象の項の係数ａが正でない即ち負のときには前述した式（１３）を用いて２次の多項式すなわち１階のエネルギーに変換し（ステップＳ２３０）、変換対象の項の係数ａが正であり且つ次数ｄが偶数のときには前述した式（９）を用いて１階のエネルギーに変換し（ステップＳ２４０）、変換対象の項の係数ａが正であり且つ次数ｄが奇数のときには前述した式（１０）を用いて１階のエネルギーに変換し（ステップＳ２５０）。そして、次数ｄが３以上の未変換の項があるときにはステップＳ２００に戻って新たに変換対象の項に設定してステップＳ２１０〜２５０の処理を繰り返し、次数ｄが３以上の未変換の項がなくなったときにこれで本処理を終了する。

こうして１階のエネルギー多項式に変換すると、既存のグラフカット法などのアルゴリズムを用いて各画素に対応した２値変数を設定し、変数Ｘ_uが値０すなわち骨である画素ｕに対して色を付すと共に変数Ｘ_uが値１すなわち骨でない画素ｕに対しては透明処理を施してディスプレイ３０に表示出力することにより、入力した画像のうち骨の部分だけを表示する。なお、グラフカット法などの適用によっても変数がわからないエラーが生じる可能性もあるが、予め定めた割り当てを行なったり、エラーが生じた変数だけで再びエネルギーを生成してエネルギー最小化アルゴリズムを適用したりすることにより対応することができる。

以上説明した実施例の情報処理装置によれば、画像データの各画素に２値のラベルを割り当てることにより領域分割する場合、ラベルに対応する２値変数を用いて４次以上の多項式である高階エネルギーを設定し、次数ｄが３以上の項毎に（ｄ−１）／２を超えない最大の整数の数だけ２値の外部変数を付加することにより１次および２次の基本対称式を用いて高階エネルギーを次数が２以下の１階のエネルギーに変換するから、１階のエネルギーの最小化が可能なグラフカット法などのエネルギー最小化アルゴリズムを適用することにより、少ない計算コストで適切に画像データの領域分割を行なうことができる。

実施例の情報処理装置では、隣接する画素４点に依存する４次（３階）のエネルギー多項式を設定するものとしたが、周辺の画素５点以上に依存する５次（４階）以上のエネルギー、例えば、３次元空間内に配置された画素（ボクセル）について立体格子状に隣接する画素８点に依存する８次（７階）のエネルギーを設定するものとしてもよい。

実施例の情報処理装置では、画像データの領域を分割する画像分割問題に本発明を適用して説明したが、これに限定されるものではなく、例えば、画像復元やステレオ，動画像解析などに本発明を適用することができるし、画像分野以外のデータ処理に適用することもできる。ここで、画像復元に本発明を適用する場合、例えば、現在の画像から若干の変化を与えた提案画像を生成し、現在の画像と生成した提案画像とを融合して新たな画像を生成する処理を繰り返し行なう融合移動アルゴリズムを用いることができる。ここで、「融合」とは、現在の画像における画素のデータ値と提案画像における対応する画素のデータ値とのうちエネルギーが小さくなる方のデータ値を新たな画像の対応する画素に設定することにより新たな画像を生成するものである。したがって、現在の画像のデータ値を維持するときにその画素に値０を割り当て提案画像のデータ値に置き換えるときに値１を割り当てるラベル割付問題として考えることができるから、エネルギー最小化法を用いて解くことができる。ここで、エネルギー（多項式）の実数係数としては、画像データを構成する画素の組のうちノイズが含まれる可能性が低いパターンほどエネルギーが小さくなるように設定することができる。また、提案画像としては、現在の画像を平滑化フィルタ（Gaussian kernel）を用いてぼかしたものを設定したり、エネルギーを各変数で偏微分して変数の数と同じ次元の勾配ベクトルを生成すると共に生成したベクトルの方向に現在の画像のデータ値から値をずらす再急降下法を用いて生成したりすることができる。勿論、これらの手法に限られず、例えば乱数画像を設定するなど如何なる手法も採用し得る。

以上、本発明の実施の形態について実施例を用いて説明したが、本発明はこうした実施例に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において、種々なる形態で実施し得ることは勿論である。

本発明は、情報処理装置や画像処理装置の製造産業などに利用可能である。

２０コンピュータ、２２高階エネルギー設定部、２４エネルギー変換部、２６エネルギー最小化部、３０ディスプレイ、４０キーボード、５０マウス。

Claims

各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理方法であって、
前記高階エネルギーのデータ表現を記憶手段に格納し、
前記高階エネルギーに対称式を用いて次数に応じた数の２値の外部変数を付加することに対応するように該格納したデータ表現を演算手段により変更することにより前記高階エネルギーを同値な１階のエネルギーに変換し、
該変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより前記高階エネルギーが最小となる前記各変数を設定する
ことを特徴とする情報処理方法。
請求項１記載の情報処理方法であって、
次数をｄとし係数をａとし前記変数をｘ₁，…，ｘ_dとし値０か値１のいずれかをとる前記外部変数をｗとし１次の基本対称式をＳ₁とし２次の基本対称式をＳ₂とすると、前記高階エネルギーの多項式の各項毎に、係数ａが正の項に対しては該項の次数ｄが偶数のときには式（１）を用いて前記１階エネルギーの多項式に変換し、該項の次数ｄが奇数のときには式（２）を用いて前記１階エネルギーの多項式に変換する
ことを特徴とする情報処理方法。
請求項２記載の情報処理方法であって、
前記高階エネルギー多項式の各項毎に係数ａが負の項に対しては式（３）を用いて前記１階エネルギーの多項式に変換する
ことを特徴とする情報処理方法。
前記所定のエネルギー最小化法は、グラフカット法，信念伝播法，ツリー重み再配分メッセージ伝達法のいずれかである請求項１ないし３いずれか１項に記載の情報処理方法。
画像データを処理する請求項１ないし４いずれか１項に記載の情報処理方法であって、
前記画像データを構成する各画素のうち所定の条件に合致する画素に第１の値のラベルを割り当てると共に該所定の条件に合致しない画素に第２の値のラベルを割り当てる２値のラベルを前記変数として前記各画素だけに依存する１次の項と４点以上の画素の組に依存する４次以上の項とを含む多項式の高階エネルギーを設定し、該設定した高階エネルギーが最小となるよう前記変数を設定することにより前記２値のラベルを割り当てる
ことを特徴とする情報処理方法。
前記所定の条件に合致する確率が高いほどエネルギーが小さくなるよう各項の係数を定めることにより前記多項式の高階エネルギーを設定することを特徴とする請求項５記載の情報処理方法。
前記所定の条件に合致する確率をＰとしたときにエネルギーが−ｌｏｇＰとなるよう前記各項の係数を定めることを特徴とする請求項６記載の情報処理方法。
請求項５ないし７いずれか１項に記載の情報処理方法であって、
現在の画像に対して変化を与えた提案画像を生成し前記現在の画像の画素を該生成した提案画像の対応する画素に置き換えるときには前記第１の値のラベルを割り当てると共に前記現在の画像の画素を前記生成した提案画像の対応する画素に置き換えないときには前記第２のラベルを割り当てることにより新たな画像を生成する処理を繰り返すことにより画像を復元する
ことを特徴とする情報処理方法。
前記提案画像は、再急降下法を用いて生成することを特徴とする請求項８記載の情報処理方法。
前記提案画像は、前記現在の画像に対して所定のぼかしフィルタを適用することにより生成することを特徴とする請求項８記載の情報処理方法。
各変数が２値の４次以上の多項式によって表わすことが可能な高階エネルギーを処理する情報処理装置であって、
前記高階エネルギーのデータ表現を格納する記憶手段と、
前記高階エネルギーに対称式を用いて次数に応じた数の２値の外部変数を付加することに対応するように該格納したデータ表現を変更する演算手段と、
前記高階エネルギーを該データ表現の変更により同値な１階のエネルギーに変換するエネルギー変換手段と、
該変換した１階のエネルギーに対して所定のエネルギー最小化法を適用することにより前記高階エネルギーが最小となる前記各変数を設定するエネルギー最小化手段と、
を備える情報処理装置。