(57)【特許請求の範囲】
【請求項１】
画像を輝度差及び色の分散を基準とする分割条件を満たす場合に再帰的に分割することにより得られる複数のセルそれぞれに対して、該複数のセルそれぞれが属するクラスを示す状態値の初期値を示す初期状態値を設定する設定工程と、
前記設定工程により前記複数のセルに設定された初期状態値を更新する状態更新工程であって、任意の確率密度関数を用いて前記複数のセルそれぞれに対して各クラスに属する確率を計算し、該計算した確率が最大となるクラスを前記複数のセルそれぞれの状態値とすることにより前記初期状態値を更新する状態更新工程と、
前記状態更新工程により更新された前記複数のセルそれぞれの状態値を参照し、該状態値が一致しているか否かに基づいて前記複数のセルを併合し、前記画像の領域分割を行う併合工程とを有し、
前記状態更新工程は、与えられたすべてのセルではなく、それぞれ異なる前記初期状態値が設定されたセルの境界により特定される領域の境界線に接するセルの初期状態値を更新し、該更新を、該更新により状態値が変化したセルの数のセル全体に対する割合が一定の割合になるまで繰り返し行うことを特徴とする画像処理方法。
【請求項２】
画像を輝度差及び色の分散を基準とする分割条件を満たす場合に再帰的に分割することにより得られる複数のセルそれぞれに対して、該複数のセルそれぞれが属するクラスを示す状態値の初期値を示す初期状態値を設定する設定手段と、
前記設定手段により前記複数のセルに設定された初期状態値を更新する状態更新手段であって、任意の確率密度関数を用いて前記複数のセルそれぞれに対して各クラスに属する確率を計算し、該計算した確率が最大となるクラスを前記複数のセルそれぞれの状態値とすることにより前記初期状態値を更新する状態更新手段と、
前記状態更新手段により更新された前記複数のセルそれぞれの状態値を参照し、該状態値が一致しているか否かに基づいて前記複数のセルを併合し、前記画像の領域分割を行う併合手段とを有し、
前記状態更新手段は、与えられたすべてのセルではなく、それぞれ異なる前記初期状態値が設定されたセルの境界により特定される領域の境界線に接するセルの初期状態値を更新し、該更新を、該更新により状態値が変化したセルの数のセル全体に対する割合が一定の割合になるまで繰り返し行うことを特徴とする画像処理装置。
【請求項３】
コンピュータを請求項２項に記載の画像処理装置として機能させるためのプログラムを記録したコンピュータ可読な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像処理方法、画像処理装置及び記憶媒体に関する。
【０００２】
【従来の技術】
画像処理および画像認識では、静止画像からのオブジェクトの抽出や判定が基本的かつ重要な問題となる。オブジェクト抽出は、静止画像内オブジェクトによる類似画像検索を始め、顔認識、MPEG4におけるデータ記述、ヒューマン・インターフェースなど幅広い分野に利用される。領域分割は、オブジェクト抽出の前処理として必要不可欠な機能である。
【０００３】
静止画像の領域分割処理とは、ある一定の基準に従って静止画像を分割する処理である。静止画像の領域分割の実現方式は、2つに大別できる。一つは、静止画像上の領域の不連続性に着目する方式である。もう一つは、静止画像上の領域の連続性に着目する方式である。
【０００４】
前者の例としては、エッジ検出法が挙げられる。エッジ検出法とは、画像のエッジを検出し、エッジによって画像を切り分ける方法の事を指す。エッジ検出処理は、計算コストが低いという利点がある。しかし、エッジ検出法には、エッジが閉領域を構成する保証が無いという欠点がある。この問題点に関する対策として、エッジの補間処理を行い分割を試みる方式が、提案されている。
【０００５】
後者の例としては、リージョン・グローイングが挙げられる。リージョン・グローイングとは、種となる小領域の特徴を調べ、その小領域の周囲の画素のうち、小領域の特徴に近い特徴を持つ画素を取り込んで行く事で領域を拡張することにより、領域を形成する方式である。領域の連続性に着目する方式は、必ず閉領域を得ることが出来るという特徴があるため、比較的広く用いられている。
【０００６】
また、領域分割を行う際に問題となるのは、ノイズの影響である。例えば、エッジ検出法を用いる場合、ノイズの影響によりエッジが正常に検出できなくなる場合が考えられる。また、リージョン・グローイングによる分割処理に関しても、局所解に陥る可能性がある。
【０００７】
このようなノイズの影響を低減するために、ノイズに強いマルコフ確率場(MRF; Markov Randam Field)が、領域分割処理にしばしば利用されている。MRFは、ノイズに対する処理をモデルとして含むため、ノイズが付加された画像の復元にも応用されている。
【０００８】
【発明が解決しようとする課題】
しかしながら、MRFを用いた領域分割法は、膨大な記憶領域と計算量を必要とするという問題点がある。これは、各画素が各領域に属する確率の計算を各画素に対して行い、全ての画素の状態値を決めるという状態値の更新処理を、状態値が更新する画素の数がすくなくなり画素の状態が安定するまで繰り返し行う必要がある。
【０００９】
本発明は、上記問題を解決するための画像処理方法、画像処理装置及び記憶媒体を提供することを目的とする。
【００１０】
更に本発明は、任意の確率密度関数を用いた更新処理を伴う領域分割処理において、更新処理で処理するデータ量を減らすことにより記憶領域、計算量を軽減し、領域分割処理を高速に行うことを目的とする。
【００１１】
【課題を解決するための手段】
上記目的を達成するために本発明は、画像を輝度差及び色の分散を基準とする分割条件を満たす場合に再帰的に分割することにより得られる複数のセルそれぞれに対して、該複数のセルそれぞれが属するクラスを示す状態値の初期値を示す初期状態値を設定する設定工程と、前記設定工程により前記複数のセルに設定された初期状態値を更新する状態更新工程であって、任意の確率密度関数を用いて前記複数のセルそれぞれに対して各クラスに属する確率を計算し、該計算した確率が最大となるクラスを前記複数のセルそれぞれの状態値とすることにより前記初期状態値を更新する状態更新工程と、前記状態更新工程により更新された前記複数のセルそれぞれの状態値を参照し、該状態値が一致しているか否かに基づいて前記複数のセルを併合し、前記画像の領域分割を行う併合工程とを有し、前記状態更新工程は、与えられたすべてのセルではなく、それぞれ異なる前記初期状態値が設定されたセルの境界により特定される領域の境界線に接するセルの初期状態値を更新し、該更新を、該更新により状態値が変化したセルの数のセル全体に対する割合が一定の割合になるまで繰り返し行うことを特徴とする。
【００１２】
【発明の実施の形態】
（第1の実施形態）
本実施形態について図面を参照して説明する。
【００１３】
図1は、第1の実施形態の構成を示すフローチャートである。ステップS101は、前処理である。図7は、セルの生成方法を図示したものである。
【００１４】
ステップS101は前処理であって、ユーザから与えられた条件に従って4分木を作成することにより、画素の集合を生成する。ここで、簡略化のために本実施形態では4分木を用いたが、作成される木は、任意の数の枝を持って良い。このように生成された画素の集合を、セルとして扱う。最後に、セルの初期状態値の設定を行う。
【００１５】
ステップS102は、状態値の更新処理である。クラスは、近い特徴量を持つセルの集合である。
【００１６】
ステップS102では、セルがクラスに属する確率の計算を行い、セルの状態値を更新する。
【００１７】
ステップS103で、更新処理によって状態値が変化したセルの数のチェックを行い、収束の判定を行う。セルの状態値が収束したと判定されたら、ステップS104に進む。収束していないと判定された場合は、ステップS102へ戻る。
【００１８】
ステップS104では、セルの状態値と空間の連続性を考慮して、各領域にユニークな領域番号を付与する。
【００１９】
S105では、領域併合処理を行う。領域併合処理には、隣接する領域の平均色の近さに基づいて併合する方式や、領域の境界における色の変化量に基づいて併合する方式がある。
【００２０】
図2は、図1中の前処理S101の構成を示すフローチャートである。
【００２１】
ステップS101は、デジタル画像を入力とし、画素または画素の集合をセルに対応させ、セルとクラスの初期状態を設定する。
【００２２】
セルは、セルが属するクラス番号を状態値として持つ。状態値の初期値は、どのようにして決めてもかまわないが、ここではその一例として、ユーザが指定した数を上限とする自然数の乱数で定めることとする。
【００２３】
4分木の生成は、入力画像に対し分割条件を定め、分割条件を満たす部分画像を再帰的に分割する事により行う。例えば本実施形態では、分割条件として、次の2つの基準を用いるとする。
1. 部分画像内の輝度差
2. 部分画像内の色の分散（色ベクトルの分散共分散行列の行列式の値）
【００２４】
ステップS201で分割条件に関する閾値dを求める。例えば本実施形態では、閾値dは、ユーザによって与えられる重みTdivと原画像に含まれる全ての画素の輝度差の最大値Fallを用いて次式で表す。
【００２５】
【外１】
0004095208.tif 000002
【００２６】
ステップS202で、部分画像について分割パラメータを計算する。部分画像の初期状態は、静止画像全体である。例えば本実施形態では、分割条件を、『分割パラメータ＞閾値d』とする。
【００２７】
ステップS203で、分割条件を満たす部分画像が存在するかどうかを判定する。分割条件を満たす部分画像が存在する場合、ステップS204へ進む。分割条件を満たす部分画像が存在しない場合は、処理を終了する。
【００２８】
本実施形態では、ある基準に関する閾値によって分割条件を定めたが、他の条件による分割条件を定めても良い。
【００２９】
ステップS204では、条件Dを満たす部分画像をx方向に2等分、y方向に2等分することにより4等分する。x方向の部分画像の大きさが1ピクセルである場合は、x方向の分割は行わない。また、y方向の部分画像の大きさが1ピクセルである場合は、y方向の分割は行わない。
【００３０】
状態更新処理S102は、処理を行うセルのリストを作る前段と、リストに登録されているセルの状態更新を行う後段の2つの処理から成る。
【００３１】
ステップS102の処理の流れを、図3に示したフローチャートにしたがって説明する。
【００３２】
前段：本実施形態では、領域の境界線に接するセルのみを処理することで更新処理をより高速に実行することが出来る。図8は、ステップS102で処理されるセルと処理されないセルに関して図示したものである。前段では、処理されるセルのリストを作成する。この前段は、ステップS301において、
1. 高速化を伴う状態更新処理を一度も行っていない場合
2. 高速化を伴う状態更新処理を一度以上行い、すでに境界に接するセルのリストが存在する場合で2つの流れに分かれる。
【００３３】
1つ目の場合、ステップS302とステップS303において、全てのセルについて、領域の境界線に接しているかどうかを調べ、領域の境界線に接しているセルのみを処理リストに登録し、後段へ進む。
【００３４】
2つ目の場合、ステップS304で、すでに存在する処理リストに登録されているセルの状態値が更新されたかどうかを調べる。次に、ステップS305で、状態が更新されたセルをリストから削除する。
【００３５】
最後に、ステップS306で、削除されたセルとその近傍のセルに関して、領域の境界線に接しているかどうかを調べ、領域の境界線に接しているセルのみをリストに登録して、後段へ進む。例えば本実施形態では、前記近傍は、注目しているセルに隣接するセルの集合とする。図5は、注目しているセルの近傍を図示したものである。
【００３６】
後段：後段では、MRFを用いて静止画像の領域分割を実現する方式の一つとして、Heat Bath法による領域分割を行う。
【００３７】
Heat Bath法とは、次のような手順により処理を行う方法である。
1. 全てのセルに対して：
(a) セルが、各クラスに属する確率をそれぞれ求める。
(b) 求めた確率に応じて、セルが属するクラスを決定する。例えば、本実施形態では、確率が最大となるクラスを選択する。
2.クラスのパラメータを更新する。例えば本実施形態では、パラメータは、クラスに属するセルの平均色、色の分散値と、分散共分散行列の逆行列である。
3. セルの状態が安定しない場合は、1へ戻る。例えば本実施形態では、クラスが変わったセルを調べ、クラスが変わったセル数のセル全体に対する割合が、一定の割合より多い場合は、セルの状態が安定しないと判断する。
【００３８】
ここで、セルの初期状態は、乱数で決めて良い。また、クラスの数は任意で良い。ステップS307、ステップS308で、
処理リストに登録されたセルの各クラスに属する確率P(xc|yc)を計算し、確率が最大となるクラスの値を、そのセルの状態値とする。状態を決定するために参照される画素の集まりであるクリークは、例えば本実施形態では、注目しているセルと、そのセルに隣接する全てのセルの集合とする。図6は、本実施形態におけるクリークを図示したものである。
【００３９】
cがクリーク、xが状態Xの要素、yが画素の色ベクトルを表すとすると、確率P(xc|yc)は、次式で表す。
【００４０】
【外２】
0004095208.tif 000003
とする。本実施形態において、画素の色ベクトルyijの色空間は、例えばRGB空間L*a*b*空間のような任意の空間を用いて良い。式(8)におけるエッジは、例えばSobelフィルタを用いたエッジ検出のような任意のエッジ検出方法を用いて定めて良い。
【００４１】
ここで、式(2)の意味について、簡単に説明する。式(2)は、式(3)と式(5)、式(4)と式(6)、およびPyc-1により構成されている。このうち、式(5)は、セルの平均色とクラスの平均色の色空間上での距離を表す。ただし、この距離は、クラスの色の分散値により正規化されている(マハラノビス距離)。
【００４２】
式(6)は、領域の連続性をMRFにより計算する部分である。式(6)中のλ、Hは、それぞれ式(7)、式(8)に示されるものである。
【００４３】
また、βは、色空間上でのマハラノビス距離に対する領域の連続性の重みを決定するパラメータである。式(7)は、周囲のセルの状態値とターゲットのセルの状態値が一致する割合が高いほど、式(2)全体の値が高くなるように設定された式である。
【００４４】
また、式(8)によって、クリークの制限を行うライン過程を導入することで、単純に領域の連続性を考慮するのではなくエッジを考慮に入れている。式(3)、式(4)は、それぞれ式(5)、式(6)を正規化する分配関数であり、式(2)を確率として計算するために用いている。Pycは、画素の出現確率であるので、常に1となる。
【００４５】
ライン過程について、図11を用いて説明する。ライン過程は、クリークに含まれるセルのうち、ある条件を満たすセルをMRFの計算から除外する処理である。例えば本実施形態では、ある条件を満たすセルとは、
ターゲットのセルとの間をエッジで区切られたセルを指す。図11においてセルRの状態を決める時に、セルRのクリークに含まれるセルであるセルA、B、C、Dの状態値が、それぞれ1、2、3、3であるとする。また、セルRとセルC、セルRとセルDの間には、エッジが検出されているとする。ここで、式(6)のβの値が非常に大きく、色の近さより領域の連続性が優先される状態になった場合、ライン過程を導入しなければ、セルRの状態値は、エッジによって区切られているにも関わらず3になってしまう。それに対し、エッジで区切られたセルCとセルDを、ライン過程により式(6)のMRFの計算から除外することによって、セルRに対して適切な状態値を設定することが可能になる。
【００４６】
例えば、セルRの色がセルBの色よりセルAの色に近い場合、図11のようにセルRの状態値は1となる。
【００４７】
次に、ステップS309において、状態更新前後のセルの状態値を比較し、何パーセントのセルの状態値が変化したかを収束度として求める。
【００４８】
前記更新処理ステップS102は、図3のステップS103によって、収束度が予め定めた値を越えるまで繰り返し実行される。
【００４９】
図4は、領域番号設定処理S104の構成を示すフローチャートである。ステップS104は、ステップS102によってクラス分けされたセルに対し、空間的連続性を考慮して領域に分ける処理を行う。
【００５０】
ステップS104では、あるセルの領域番号を決定する時に、周囲のセルの状態値を参照する。周囲のセルの状態値が注目しているセルの状態値と一致している場合とそうでない場合で、処理が異なる。
【００５１】
状態値が一致しない場合： 周囲のセルと状態値が一致していない場合は、ステップS403で新しい領域番号を用意し、セルの領域番号とする。
【００５２】
状態値が一致する場合： 注目しているセルと同じ状態値を持つ周囲のセルの領域番号が全て一致している場合、注目しているセルの領域番号も一致させる(図9)。一致していない場合、領域番号を一致させる(図10)。注目しているセルの領域番号は、一致させた後の領域番号を設定する。
【００５３】
本実施形態では、領域に属するセルがリスト構造で格納されているため、領域番号設定における領域番号の一致や、領域併合における併合処理は、リストの繋ぎ直しを行うだけで済むようになっている。
【００５４】
以上説明したように、第1の実施形態によれば、全ての画素について更新処理を行うことなく、画素の集合をセルと対応させ、領域の境界に接するセルのみを処理することによって高速にデジタル画像の領域分割処理を行うことが可能となる。
【００５５】
（第2の実施形態）
第1の実施形態において、MRFを用いたデジタル画像の領域分割を高速に処理する方法を説明した。第2の実施形態では、動画像のフレーム間差分などによって算出された動きベクトルにより、動画像のフレームを構成する画像の領域分割を高速に処理する方式について説明する。なお、第2の実施形態における全ての処理の流れは、第1の実施形態と同様であるので、ここでは説明を省略する。
【００５６】
本実施形態では、動きベクトルのみを用いて領域分割する方法について述べるが、動画像の動きベクトルによる領域分割の場合、フレームを構成する画像を用いる事により、画像の色情報を用いても良い。
【００５７】
動きベクトルのみを用いた領域分割においては、第1の実施形態に見られるような色特有の特徴を用いた処理を行う事はできない。したがって、前処理S101において、動きベクトルの分散共分散行列の行列式の値を基準として、閾値dを設定することにより分割条件を定めることによってn分木を生成し、セルと対応づける。
【００５８】
更新処理S102では、同様の処理によりセルの状態値を更新する。本実施形態では、式(2)、式(4)、式(5)におけるyは、動きベクトルに対応する。式(8)におけるエッジは、動きベクトルの変化量を算出する事により検出可能である。
【００５９】
領域番号設定処理S104は、第1の実施形態と同様である。
【００６０】
以上説明したように、第2の実施形態によれば、動画像のフレーム間差分などにより算出された動きベクトルを用いて、MRFによる動画像のフレームの領域分割を高速に行う事が可能になる。
【００６１】
（第3の実施形態）
第1の実施形態において、MRFを用いた確率密度関数を用いてセルの状態値の更新処理を行ったが、MRFの他に、任意の確率密度関数を用いてセルの状態値の更新処理を行ってもよい。
【００６２】
（他の実施形態）
また前述した実施形態の機能を実現する様に各種のデバイスを動作させる様に該各種デバイスと接続された装置あるいはシステム内のコンピュータに、前記実施形態機能（例えば、図2,3,4のフローチャートにより実現される機能）を実現するためのソフトウエアのプログラムコードを供給し、そのシステムあるいは装置のコンピュータ（CPUあるいはMPU）を格納されたプログラムに従って前記各種デバイスを動作させることによって実施したものも本発明の範疇に含まれる。
【００６３】
またこの場合、前記ソフトウエアのプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコード自体、及びそのプログラムコードをコンピュータに供給するための手段、例えばかかるプログラムコードを格納した記憶媒体を提供する。
【００６４】
かかるプログラムコードを格納する記憶媒体としては例えばフロッピーディスク、ハードディスク、光ディスク、光磁気ディスク、CD-ROM,、磁気テープ、不揮発性のメモリカード、ROM等を用いることが出来る。
【００６５】
またコンピュータが供給されたプログラムコードを実行することにより、前述の実施形態の機能が実現されるだけではなく、そのプログラムコードがコンピュータにおいて稼働しているOS(オペレーティングシステム)、あるいは他のアプリケーションソフト等と共同して前述の実施形態の機能が実現される場合にもかかるプログラムコードは本実施形態に含まれることは言うまでもない。
【００６６】
更に供給されたプログラムコードが、コンピュータの機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに格納された後そのプログラムコードの指示に基づいてその機能拡張ボードや機能格納ユニットに備わるCPU等が実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も本実施形態に含まれることは言うまでもない。
【００６７】
また、複数の機器（例えば、ホストコンピュータ、インタフェイス機器、リーダ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置など）に適用してもよい。
【００６８】
【発明の効果】
以上説明したように請求項１によれば、所定の評価関数を用いた更新処理を伴う領域分割処理において、更新処理で処理するセルの数を減らすことにより領域分割処理を高速に行うことができる。
【図面の簡単な説明】
【図１】本実施形態における処理の流れを示すフローチャートである。
【図２】本実施形態における前処理S101の処理の流れを示すフローチャートである。
【図３】本実施形態における状態更新処理S102の処理の流れを示すフローチャートである。
【図４】本実施形態における領域番号設定処理S104の処理の流れを示すフローチャートである。
【図５】本実施形態におけるセルの近傍系を示す図である。
【図６】本実施形態におけるクリークを示す図である。
【図７】本実施形態におけるセルの生成方式を示す図である。
【図８】本実施形態の更新処理において処理されるセルを示す図である。
【図９】本実施形態のあるセルの領域番号を設定する時、近傍のセルのうち同じ状態値を持つセルの領域番号が一致している場合の処理の一例を示す図である。
【図１０】本実施形態のあるセルの領域番号を設定する時、近傍のセルのうち同じ状態値を持つセルの領域番号が一致していない場合の処理の一例を示す図である。
【図１１】本実施形態のあるセルの状態値を設定する時、ライン過程を導入した場合の処理を示す図である。
【図１】
0004095208.tif 000004
【図２】
0004095208.tif 000005
【図３】
0004095208.tif 000006
【図４】
0004095208.tif 000007
【図５】
0004095208.tif 000008
【図６】
0004095208.tif 000009
【図７】
0004095208.tif 000010
【図８】
0004095208.tif 000011
【図９】
0004095208.tif 000012
【図１０】
0004095208.tif 000013
【図１１】
0004095208.tif 000014