JP5464739B2 - 画像領域分割装置、画像領域分割方法および画像領域分割プログラム - Google Patents

Description

本発明は、1枚の画像を類似した特徴（特に似た色）を持つ複数の領域に分割し、画像に含まれる個々のオブジェクトを分離するための、画像領域分割装置、画像領域分割方法および画像領域分割プログラムに関するものである。

画像を解析し、内容を詳細に把握するためには、画像に含まれる個々のオブジェクトを分離し、それぞれを抽出する領域分割処理が必須となる。各オブジェクトが特徴的な色を有する性質を利用して、1枚の画像を類似した色を持つ複数の領域に分割することで、画像に含まれるオブジェクトを分離する既存の領域分割方法がある。

下記の非特許文献１に示された技術では、図１１（ａ）に示す原画像から抽出したい前景オブジェクト（この場合は花）が含まれる大まかな領域を、ユーザがマウスのドラッグ操作で同図（ｂ）に示す通り矩形で指定することにより、原画像を同図（ｅ）に示す前景オブジェクトと同図（ｆ）に示す背景との2つの領域に分離する。

この際、同図（ｃ）に示すユーザによって指定された矩形領域の内側には前景オブジェクトと背景の一部とが混在する領域と考えることができ、逆に同図（ｄ）に示す矩形の外側の領域には背景だけが含まれると考えられる。

したがって、ユーザによって指定された矩形の外側の領域に含まれる画素の色の分布をGaussian Mixture Model（GMM：混合正規分布モデル）でモデル化する。生成されたモデルを背景色の分布として用いて、矩形領域の内側の混在領域に含まれる個々の画素についてその色から背景らしさを示す尤度を算出する。背景色として高い尤度を示した画素を混在領域から取り除くことによって、原画像から前景オブジェクトを抽出する。

C. Rother, V. Kolmogorv, A. Blake, "GrabCut: Interactive Foreground Extraction Using Iterated Graph Cuts," ACM Trans. Graphics (SIGGRAPH '04), vol.23, no.3, pp.309-314, 2004.

しかしながら、非特許文献１に示された従来技術により画像の領域分割を実現するためには、ユーザがあらかじめ大まかな前景領域を手動で指定する手間（インタラクション）が必要であった。このため、人手を要さず自動的に画像の領域分割を実施できるものではなかった。

また、非特許文献１に示された従来の装置は1枚の画像を前景オブジェクトと背景の2つの領域に分割することを目的としていた。そのため、3つ以上の複数の領域に分割することができなかった。

本発明は上記従来技術の課題を解決するために提案されたものであり、毎回に渡る人手が不要で自動的に画像の領域分割を実現でき、さらに３つ以上の複数の領域に分割し、画像に含まれる個々のオブジェクトの分離を可能とした画像領域分割装置、画像領域分割方法及び画像領域分割プログラムを提供することを目的とする。

上記目的を達成するため、本発明は、入力画像に含まれる各オブジェクトを分離抽出する画像領域分割装置であって、入力画像を色特徴に基づいて複数の小領域に過剰分割する小領域分割部と、該過剰分割された複数の小領域の各々に対して、前記入力画像において該小領域に属する内部領域と該小領域に属さない外部領域とを対応付けて出力する対象領域選択部と、前記外部領域のうち対応する前記内部領域と色特徴が類似する領域を該内部領域と統合して小領域拡張領域として出力する小領域拡張部と、前記小領域拡張領域同士のペアの領域類似度を算出する領域類似度算出部と、前記小領域のペアのうち、対応する小領域拡張領域ペアの前記領域類似度が所定基準を満たす小領域ペア同士を全て同一オブジェクトに属すると判定して統合し、前記所定基準を満たさない小領域ペア同士は異なるオブジェクトに属すると判定することによって前記各オブジェクトを得る小領域統合部とを備える点に第１の特徴がある。

また、前記小領域拡張部が、前記内部領域に含まれる画素の色の分布から色分布モデルを生成する色分布モデル化部と、前記色分布モデルを用いて、前記内部領域に対応する外部領域を該内部領域との色特徴類似性および該外部領域内の局所領域内の色特徴類似性に基づいて二分割するのに必要なエネルギーを求める、該二分割の領域を変数としたエネルギー関数を生成する分割エネルギー算出部と、前記エネルギー関数を用いて前記エネルギーを最小とする分割二領域を求め、該分割二領域のうち前記内部領域と色特徴の類似性があると判定された領域を前記内部領域と統合して前記小領域拡張領域として出力する二領域分割・統合部とを備える点に第２の特徴がある。

また、前記二領域分割・統合部が、前記エネルギー関数を用いて前記エネルギーを最小とする分割二領域を求めるに際して、前記外部領域内に含まれる前記過剰分割された小領域単位で前記エネルギーを最小とする領域を求める点に第３の特徴がある。

また、前記小領域分割部が、入力画像を減色して減色画像に変換する量子化部と、前記減色画像の領域境界尤度を所定サンプリング密度の画素単位で算出する領域境界尤度算出部と、前記領域境界尤度の分布から前記領域境界尤度を算出された各画素が領域境界に属するか領域に属するかを判定し、領域に属する場合は領域番号を付与する領域番号付与部と、前記領域境界に属するか領域に属するかを判定された画素以外の残りの画素に対して、前記領域番号を付与された画素の局所分布に基づいて領域に属すると判定される画素に領域番号を付与し、前記入力画像全体における前記領域番号を付与された画素の連結領域として前記複数の小領域の各々を得る領域拡大部とを備える点に第４の特徴がある。

また、前記小領域分割部が、前記入力画像の画素間の色特徴の類似性を示す類似度行列および該類似度行列の対角行列を算出する画素間類似度行列算出部と、前記類似度行列および前記対角行列を用いて、色特徴の類似度の高い画素同士が同じ小領域に分割されるための評価基準行列を作成する評価基準作成部と、前記評価基準行列の固有ベクトルを固有値昇順に所定数求める固有ベクトル算出部と、前記固有ベクトルおよび前記対角行列を用いて、前記入力画像の各画素が所定数の小領域のいずれに属するかを示す小領域番号行列を算出し、該小領域番号行列を参照して前記複数の小領域の各々を得る小領域算出部とを備える点に第５の特徴がある。

また、前記色分布モデルに混合正規分布モデル（GMM）を用いる点に第６の特徴がある。

また、前記色分布モデルにヒストグラムを用いる点に第７の特徴がある。

また、本発明は、入力画像に含まれる各オブジェクトを分離抽出する画像領域分割方法であって、入力画像を色特徴に基づいて複数の小領域に過剰分割する小領域分割ステップと、該過剰分割された複数の小領域の各々に対して、前記入力画像において該小領域に属する内部領域と該小領域に属さない外部領域とを対応付けて出力する対象領域選択ステップと、前記外部領域のうち対応する前記内部領域と色特徴が類似する領域を該内部領域と統合して小領域拡張領域として出力する小領域拡張ステップと、前記小領域拡張領域同士のペアの領域類似度を算出する領域類似度算出ステップと、前記小領域のペアのうち、対応する小領域拡張領域ペアの前記領域類似度が第一の所定基準を満たす小領域ペア同士を全て同一オブジェクトに属すると判定して統合し、第一の所定基準を満たさない小領域ペア同士は異なるオブジェクトに属すると判定することによって前記各オブジェクトを得る小領域統合ステップとを備える点に第８の特徴がある。

また、本発明は、入力画像に含まれる各オブジェクトを分離抽出する画像領域分割プログラムであって、コンピュータに、入力画像を色特徴に基づいて複数の小領域に過剰分割する小領域分割ステップと、該過剰分割された複数の小領域の各々に対して、前記入力画像において該小領域に属する内部領域と該小領域に属さない外部領域とを対応付けて出力する対象領域選択ステップと、前記外部領域のうち対応する前記内部領域と色特徴が類似する領域を該内部領域と統合して小領域拡張領域として出力する小領域拡張ステップと、前記小領域拡張領域同士のペアの領域類似度を算出する領域類似度算出ステップと、前記小領域のペアのうち、対応する小領域拡張領域ペアの前記領域類似度が第一の所定基準を満たす小領域ペア同士を全て同一オブジェクトに属すると判定して統合し、第一の所定基準を満たさない小領域ペア同士は異なるオブジェクトに属すると判定することによって前記各オブジェクトを得る小領域統合ステップとを実行させる点に第９の特徴がある。

前記第１および第２の特徴によれば、人手不要で自動的に画像の領域分割を実現できるようになる。また、1枚の画像を前景オブジェクトと背景といった2つの領域だけでなく2つ以上の複数の領域にも分割できるようになる。

前記第３の特徴によれば、エネルギー最小領域の算出を外部領域全体よりも狭い各小領域に対して行うので、算出における計算負荷を減らすことができる。

前記第４および第５の特徴によれば、色特徴が類似した小領域に分割されるため、小領域には系統の異なる色が含まれず、後段の小領域拡張部において小領域の色特徴を詳細に反映した領域・形状として小領域拡張領域が得られ、小領域統合部において同一オブジェクトに属するかどうかの判断を高い精度で行うことができる。

前記第６の特徴によれば、色分布のモデル化の精度が高くなり、精度良く画像を領域分割できるようになる。

前記第７の特徴によれば、色分布のモデル化に使用する画素数が少ない場合でも色分布をモデル化できるようになる。

前記第８の特徴によれば、人手不要で自動的に画像の領域分割を実現できるようになる。また、1枚の画像を前景オブジェクトと背景といった2つの領域だけでなく2つ以上の複数の領域にも分割できるようになる。

前記第９の特徴によれば、人手不要で自動的に画像の領域分割を実現できるようになる。また、1枚の画像を前景オブジェクトと背景といった2つの領域だけでなく2つ以上の複数の領域にも分割できるようになる。

本願発明の第１実施形態の画像領域分割装置の構成を示すブロック図である。 本願発明の第２実施形態の画像領域分割装置の構成を示すブロック図である。 第１実施形態の小領域分割部の処理を説明する図である。 図１の量子化部による減色処理を説明する図である。 図１、図２の対象領域選択部、色分布モデル化部、分割エネルギー算出部および二領域分割・統合部による処理を説明する図である。 図１、図２の領域似度算出部と小領域統合部による処理を説明する図である。 各小領域から得られる小領域拡張領域の結果と、その結果に基づく小領域のグループ分けについて説明する図である。 本願発明の領域分割装置により得られる最終的な領域分割結果（各オブジェクト）を説明した図である。 本願発明の画像領域分割装置によるオブジェクト領域抽出処理の流れの概要を示す図である。 第２実施形態の小領域分割部の処理を説明する図である。 従来装置による画像領域分割の実現手順を説明する図である。

以下、図面を参照して本発明の実施形態について詳細に説明するが、本発明は、1枚の画像を類似した特徴（特に似た色）を持つ複数の小領域に過剰分割し、過剰分割された小領域の中から同一オブジェクトに含まれると推定された小領域同士を統合することによって、画像に含まれる個々のオブジェクトを分離することを特徴としている。

図９に本発明の画像領域分割装置に関する領域分割の流れの概要を示す。同図（ａ）の入力画像から色特徴に基づいて小領域分割画像（ｂ）を得る。同図（ｂ）の小領域はオブジェクトへの分割としては過剰分割されている。そこで同一オブジェクトに属すると判定される小領域間の領域統合を行って、最終的に同図（ｃ）の通り、３つのオブジェクトへの領域分割結果を得る。入力画像から過剰分割された小領域を得る方法としては後述のJSEGによる場合[A1]（第１の実施形態）と、Normalized Cutsによる場合[A2]（第２の実施形態）とを説明するが、同等の結果が得られる任意の方法が適用可能である。そして小領域への過剰分割以降の統合処理[B]は共通である。

なお図９（ｄ）では各オブジェクトに異なる色を塗って（異なる濃淡で表現して）、同図（ｃ）における適切にオブジェクトに分けられた領域を分かり易く示した。なおまた同図（a）の入力画像例は後方に柵（主に白灰色）がある牧場で羊（主に白色）が草（主に緑色）を食べている画像であり、後述の図３，５，６，７，８，１０においても共通に例として用いられる。同図の（a）は、カラー画像の原画を白黒画像で表したものであり、白黒の濃淡からわかるように、前記柵、羊、草の色は一様ではなく、これらの部分、部分で色の濃淡や色合いが異なる。

以下に、本発明の第1実施形態の画像領域分割装置および画像領域分割方法について説明する。この第１実施形態は入力画像をJSEGを用いて過剰分割し、続いて統合処理するものである。

[A1]JSEGを用いた過剰分割

まず、前述の小領域への過剰分割に既存の領域分割方法であるJSEGにつき、詳細を述べる。該領域分割の装置構成のブロック図を図１に示す。図１の小領域分割部１では、一例としてJSEGが用いて過剰分割が行われる。この場合、小領域分割部１は図１に示すように量子化部１１、領域境界尤度算出部１２、領域番号付与部１３および領域拡大部１４を含む構成となる。また小領域分割部１（JSEG利用の場合）にて画像が処理されていく例を図３に示す。なお、JSEGは次の文献で提案されている。

Y. Deng, B. S. Manjunath, "Unsupervised Segmentation of Color-Texture Regions in Images and Video", IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI '01), vol. 23, no. 8, pp. 800-810, Agustus 2001.

図１の量子化部１１では、入力された画像を減色する。例えば入力画像がRGB各成分8ビットで示される計24ビットの多値カラー画像の場合、１つの画素は1667万色で表現されるが、量子化部１１によりC色（JSEGではC=10〜20が用いられる）に減色される。

量子化部１１における減色処理は図４に模式的に示すような公知技術のk-meansを用いてなされる。すなわち、入力画像の全画素を、図４に示すように、RGBの3次元空間上にプロットする（図４における各×点が画素である）。なお、図４ではRGB空間のうちRGの２次元空間のみを便宜的に示し、またk-meansは次元数によらず適用可能である。k-meansを用いることで図４に示すように空間をクラスタリングして、各クラスタに属する画素の点を各クラスタのセントロイド（図４における○×点がセントロイドである）が示す色へと減色する。k-meansにおけるクラスタ数kは所定数を任意に設定できるので、k-meansをJSEGにおける量子化部１１として利用する場合は減色される色数Cを設定する。こうして減色後は色数C=kとなる。

k-meansによるクラスタリングは具体的には、以下の（１）〜（４）の手順により行われる
（１）データを指定された任意の数であるk個のクラスタに分割する。
（２）各クラスタについて重心を計算する。
（３）全てのデータについて、重心との距離を最小にするクラスタを求め、各データを最小のクラスタに割り当てる。
（４）前回のクラスタから変化がなければ終了する。変化がある場合は、（２）に戻る

このようにして量子化部１１の処理が行われると、例えば図３（ａ）のような入力画像は図３（ｂ）のような減色画像となる。なお図３（ｂ）の減色画像内において同一色を示す画素が視認できるよう便宜的に画素の値を変換し、図３における入力画像（ａ）から（ｂ）が減色されていることを見やすくした画像が図３（ｂ２）である。

領域境界尤度算出部１２では、以下に示す手順により、量子化部１１を経て減色された入力画像のある着目画素を中心とする局所領域からオブジェクトの境界らしさを示す領域境界尤度Jを算出する。領域境界尤度Jは画素単位で算出され、画像に含まれるオブジェクトの境界で大きな値を取る。（なおJSEGの名称は領域境界尤度Jに由来する。）

減色された入力画像内の着目画素z=(x,y)の位置座標(x,y)について、次式に示すように重心m（数式１）からの分散S_T（数式２）を算出する。なお、数式１，２において着目画素中心の局所領域がZであり、Zに含まれる画素のうち領域境界尤度Jの算出に用いるもの（計算効率・負荷の都合上、局所領域Z内で例えば縦・横方向共に2画素おきでサンプリングする）の個数がN個である。

また数式１，２における着目画素中心の局所領域Zに属する画素を、色数Cに減色された各色別に分類した画素の集合をZ_i(i=1,2,…,C)とする。つまりZ_iの各i(i=1,2,…,C)の和集合が局所領域Zとなり、各Ziも局所領域Zと同様にZの中心である着目画素毎に定まる。画素集合Z_iの重心m_i（数式３）からの分散S_iの総和S_W（数式４）を算出する。なお数式３，４においてN_iを画素集合Z_iに含まれる画素数とする。

次式（数式５）に示す通り、算出された分散S_TとS_Wから局所領域内の中心に位置する着目画素の領域境界尤度Jを算出する。図３（ｂ）の減色画像をこのように領域境界尤度算出部１２で処理して領域境界尤度Jを算出し、領域境界尤度Jを可視化（Jが大きいほど白色に近づくとして可視化）した画像を図３（ｃ）に示す。

領域番号付与部１３では、局所領域（領域境界尤度算出部１２の場合と同様の領域およびサンプリング）における領域境界尤度Jの分布の平均μと分散σ²（および分散σ²の平方根として算出される標準偏差σ）を算出し、次式（数式６）に示す通り、しきい値Tを決定する。ただし、αは調整を要するパラメータであり、予備実験等を行って、有効に作用する値を予め決定する。αの値は例えば0.1程度に設定すると有効に作用する。

設定されたしきい値Tを下回る領域境界尤度Jを持った画素は領域境界ではないと判定して領域番号を付与する。この際、隣接画素（局所領域内の計算に用いた画素での隣接画素）でも領域境界ではないと判定された場合は同一の領域番号を付与する。

図３（ｃ）の領域境界尤度Jを可視化した画像（領域境界尤度Jが算出された画像）を領域番号付与部１３で処理し、しきい値Tを上回る画素（境界領域であると判定された画素）を白で、しきい値Tを下回る画素（境界領域ではないと判定され領域番号を付与された画素）を黒で表示した画像を図３（ｄ）に示した。

領域拡大部１４では、計算効率の都合上、所定サンプリング密度である程度まばらに算出された領域境界尤度Jの結果から得られた、ある程度まばらな境界領域／領域番号判定を残る全画素に渡って補う処理を行う。すなわち、領域番号が付与された画素の領域番号を、その画素に隣接する領域番号がまだ付与されていない画素（局所領域においてサンプリングされなかった画素）でありかつ境界領域の画素には隣接しない画素に対して拡大して付与し、領域番号が付いていない画素（境界領域と判定されたために領域番号が付いてない画素は除く）が無くなるまで拡大処理を繰り返す。また、各局所領域で付与した領域番号を画像全体での領域番号として矛盾がないよう（領域番号が付与された領域が連結なら共通の領域番号とするなど）、それらの付与番号を調整する。こうして最終的に各領域番号の付与された画素の全体を各小領域として、図３（ｅ）の領域分割結果（小領域分割結果）が得られる。

なお領域分割結果として過剰分割して得られる小領域を統合してオブジェクトを得るためさらに後述の対象領域選択部２以降で処理するにあたっては、小領域の各画素は入力画像を参照して量子化部１１で減色される前の画素値に戻すものとする。この処理は領域拡大部１４において行っても、対象領域選択部２において行ってもよい。なお、後述の[A2]Normalized Cutsによる小領域分割では減色されないため、減色前の元の画素値に戻す処理は必要ない。

以上、JSEGで小領域分割部１を実施して入力画像から小領域分割結果を得るまでを説明した。

[B]小領域の統合処理

次に、小領域分割結果（および入力画像）に対して、対象領域選択処理、小領域拡張処理、領域類似度算出処理および小領域統合処理を行って領域分割結果を得るまでの段階を説明する。本段階のうち、図１（または後述の図２でも同様）の対象領域選択部２、小領域拡張部３０（色分布モデル化部３、分割エネルギー算出部４および二領域分割・統合部５を含む）によって画像が処理されていく例を図５に示す。また本段階のうち、図１（または図２）の形状類似度算出部６、小領域統合部７によって画像が処理されていく例を図６に示す。

対象領域選択部２では、小領域分割結果から小領域を選択し、選択された各小領域ごとに該小領域を識別するための処理番号を付与して出力すると同時に、入力画像から選択された小領域の内部領域と外部領域をそれぞれ抽出する。なお小領域の内部領域とは小領域自身であり、外部領域と区別するための用語である。外部領域とは入力画像全体の領域から内部領域を除いた領域である。小領域の内部に（小領域に属さない）穴の領域がある場合、穴は内部領域ではない。小領域が連結でない場合、その各部分が内部領域である。

図５に示す例では、同図（ａ）に示す小領域分割結果の画像の中から左寄りの緑色の草の領域が選択された場合、選択された小領域の内部領域は同図（ｂ）、選択された小領域の外部領域は同図（ｃ）のように出力される。同図（ｂ）、（ｃ）では該当しない領域は黒色で塗りつぶして表示した。

なお各小領域が前述のJSEGの場合のように小領域分割部１にて途中で減色されるなどしている場合（かつ分割結果を得てから小領域分割部１内で減色前の画素値に戻されていない場合）は、対象領域選択部２において元の入力画像を参照して画素値を元に戻してもよい。

小領域拡張部３０は、以下に述べる色分布モデル化部３、分割エネルギー算出部４および二領域分割・統合部５を含む。ここでは内部領域の色特徴を抽出し、外部領域のうち内部領域と色特徴が類似していると判定される領域（色特徴類似領域）を選出し、色特徴類似領域と対応する内部領域（＝小領域）とを統合して小領域拡張領域を得る。図５に示す例では、同図（ｂ）、（ｃ）から（ｄ）を出力するのが小領域拡張部３０である。

色分布モデル化部３では、選択された小領域内部に含まれる画素の色の分布をモデル化する。例えば図５の場合、同図（ｂ）が選択された小領域の内部領域であるため、これに含まれる画素の色分布をモデル化する。この場合、主に草の緑色の分布がモデル化されることになる。この際、色分布のモデル化には、例えば混合正規分布モデル（GMM）もしくはヒストグラムを用いることができる。

画素の信号値をFとした場合、混合数Mの混合正規分布モデル（GMM）の密度関数g[F]は、平均μ_m、共分散行列Σ_mで決定されるM個の正規分布N_m(μ_m、Σ_m)の重み付き線形和として定義される（数式７）。ただし、Fは画素の信号値、λ_mは各正規分布に割り当てられる重みを示す。

色の分布を混合正規分布モデル（GMM）によりモデル化する場合は、選択された小領域内に含まれる画素の信号値Fを用いて、公知の技術であるEMアルゴリズム（期待値最大化法）により、各正規分布N_m(μ_m、Σ_m)に割り当てられる重みλ_mと同時に平均μ_mおよび共分散行列Σ_mを決定する。

色の分布をヒストグラムによりモデル化する場合は、画素の取りうる信号値Fの適切な区間を各階級として、選択された小領域内に含まれる画素の信号値Fの相対頻度を測定することによりヒストグラムθ[F]を算出する。ヒストグラムの値θ[F]は信号値Fの各区間の相対頻度であり規格化されているので、次式（数式８）に示すとおり、全信号値Fの区間に渡ってその和を取ると1となる。

分割エネルギー算出部４では、外部領域を内部領域と色特徴が類似すると判定される領域と類似しないと判定される領域とに分割するのに必要なエネルギー（エネルギーが小さいほど色特徴に基づく分割が妥当な分割であると判定される）を算出するエネルギー関数を生成する。このため、まず色分布モデル化部３にて生成された色分布モデルを用いて、入力画像内で選択された小領域以外の領域に含まれる個々の画素pが、どの程度選択された小領域内の画素の色分布と類似しているかを、画素pの信号値F(p)から尤度L[F(p)]として算出する。

色の分布を混合正規分布モデル（GMM）の密度関数g[F]によりモデル化する場合は、尤度L[F(p)]= g[F(p)]とする。また、色の分布をヒストグラムθ[F]によりモデル化する場合は、尤度L[F(p)]=θ[F(p)]とする。

尤度L[F(p)]すなわち内部領域との各画素の色特徴の類似性の指標に加えて、隣接する画素間の色特徴の類似性から入力画像内で選択された小領域以外の領域で指定された画像を二領域に分割する際に必要となるエネルギーを求め、分割の仕方を変数としたエネルギー関数Eを次式（数式９）に従い生成する。

なお、数式９においてe[l(p),l(q)]は次（数式１０）のとおりである。

ただし、qは画素pの近傍にある画素とし、l(p)は選択された小領域以外の領域に含まれる画素pが選択された小領域内の画素の色特徴に類似していると判定した場合1を、そうでない場合0とする（すなわち分割の仕方を定めるとl(ｐ)の値が全ての画素pにつき定まり、エネルギー関数Eの値が定まる）。ηおよびκは調整を要する正の定数、dist(p,q)は画素p、q間の距離である。

二領域分割・統合部５では、まず二領域分割処理として選択された小領域以外の領域に含まれる画素pが選択された小領域内の画素の色特徴に類似していると判定した場合はl(p)=1とし、そうでない場合l(p)=0として、生成されたエネルギー関数Eからエネルギーを最小とする分割二領域を決定する。分割二領域の各々は連結である場合も連結でない場合も、穴がある場合もない場合もありえる。次に統合処理として、分割二領域のうちl(p)=1で内部領域（小領域）の色特徴に類似していると判定された領域を対応する（色特徴の類似性の判定元となる）内部領域と統合して、小領域拡張領域として出力する。

エネルギー最小化による二領域分割とこれにより得られる色特徴類似領域の内部領域への統合の結果、小領域拡張領域として例えば図５（ｄ）に示すような画像が得られる。なお図５（ｄ）では外部領域内において類似していると判定されなかった領域（小領域拡張領域以外の領域）は黒塗りで示している。

なお、数式９の第1項は色特徴に関連する項であり、選択された小領域内部で画素pの信号値F(p)が使われているほど値が小さくなるため、この場合画素pが選択された小領域内の画素の色特徴に類似していると判定するのがエネルギー最小化で好まれることとなる。

また、数式９の第2項は色特徴および（色特徴に基づく）分割の仕方に関連する項であり、画素p、q間の信号値が近い画素であれば大きなエネルギーが発生するためl(p)およびl(q)が異なる(すなわちp,qは色特徴が異なり分割二領域の異なる領域に属する)という判定は下され難いが、画素値の差が大きい境界部分では大きなエネルギーが発生しないため、l(p)およびl(q)が異なるという判定が好まれる。

また二領域分割・統合部５は、上記のように生成されたエネルギー関数Eからエネルギーを最小とする分割二領域を決定するにあたって、外部領域全体を変数として一度に決定するのではなく、外部領域に含まれるその他の（該当する内部領域以外の）小領域（小領域分割部１で分割された小領域）ごとにそれぞれエネルギー最小の領域を決定してもよい。またこの場合、各小領域から得られるエネルギー最小の領域が小領域の所定の割合（例えば含まれる画素数の半分）を超えるか否かによって、各小領域の全体を小領域拡張領域に加えるもしくは加えないような処理を行ってもよい。

領域類似度算出部６では、小領域拡張領域同士のペア間の領域類似度（形状・位置など含む）を算出し、類似度を比較した対応する（各々の小領域拡張領域が小領域拡張部３０によって拡張される前の）小領域の処理番号のペアと共に出力する。ここで小領域拡張領域間の領域類似度S(R₁, R₂)は次式（数式１１）から算出する。

数式１１において分子R₁∩R₂は小領域拡張領域R₁およびR₂の両方に属する画素の個数を、分母R₁∪R₂は小領域拡張領域領域R₁またはR₂のいずれかに属する画素の個数を示す。また、0≦S(R₁, R₂)≦1であり、領域R₁およびR₂が完全に一致していればS(R₁, R₂)=1を、全く一致する画素がなければS(R₁, R₂)=0を示す。領域類似度は大きいほど領域（形状・位置などを含む）間が類似していることを示す。

小領域統合部７では、算出された類似度が指定されたしきい値T_sより大きい値であった場合、小領域分割結果内の小領域の中で比較対象となった小領域の番号から該当する小領域同士を統合し、また該当する小領域同士は同一のオブジェクトに属するものとして共通のオブジェクトのＩＤを与える。また類似度が指定されたしきい値T_s以下であった場合、該当する小領域同士は統合せず、異なるオブジェクトに属するものとして異なるＩＤを与える。

例えばしきい値を所定の値としてT_s=0.90に設定した場合、図６の例では、二領域分割・統合５において小領域ペア（ｂ）、（ｃ）からそれぞれ得られる小領域拡張領域ペア（ｄ）Ｒ１、（ｅ）Ｒ_２に対して、領域類似度算出部６が算出する領域類似度S(R₁, R₂)=0.92はしきい値を上回る。よって小領域統合部７は小領域拡張領域ペアR₁およびR₂は類似していると判定して、その拡張元となった同図（ｂ）および（ｄ）の選択小領域を同一オブジェクトに属するとして統合した領域同図（ｆ）を得る。

なお、本発明の画像領域分割装置における上述のような統合処理は、画像に含まれるオブジェクトはそれぞれ特徴的な色の分布を有しており、また同一のオブジェクト内であれば部分的に見て色分布が大きく変わることがない、という特性に基づいて行われるものである。したがって、ある一定の色分布を選択された２つの小領域のそれぞれの色分布に基づいて出力された小領域拡張領域同士に重複する領域が多い場合（位置・形状などの一致度が大きい場合を含む）は、選択された小領域が同じ色分布を持っており、選択された２つの小領域（選択された１つの小領域ペア）は同一のオブジェクトの一部である可能性が高いと考えて統合する。

また小領域統合部７は小領域の統合処理（統合しない処理を含む）を入力画像全体の小領域ペアの全てに渡って繰り返した結果として、入力画像全体におけるオブジェクトの分離抽出結果を得る。すなわち小領域の組み合わせの全てに対して対応する小領域拡張領域ペアの領域類似度を求め、各小領域をそのグループ内同士の任意ペアの対応する領域類似度が所定のしきい値を超え、そのグループ外同士の任意ペアの対応する領域類似度が所定のしきい値以下であるようなグループに分ける。同一グループ内に属する小領域は同一のオブジェクトに属するとしてオブジェクトのＩＤを与えられ、同一ＩＤの小領域を全て統合した領域として該ＩＤに対応するオブジェクトが得られる。なお属する小領域が１個のみのグループができた場合は、その小領域は他の小領域を統合することなくそのままでオブジェクトとなる。

このようにして小領域統合部７が入力画像の小領域ペア全てにつき領域類似度を求め、小領域を各オブジェクトに対応するグループに分けていく例を図７に示す。また図７のグループ分けから各グループに属する小領域を統合して各オブジェクトを得る例を図８に示す。

図７に示す通り、入力画像を小領域分割部１によって小領域分割した結果、１７個の小領域Ｒ１〜Ｒ１７が生成され、番号を与えて識別されている。各小領域に対して、対象領域選択部２および小領域拡張部３０の処理によって対応する小領域拡張領域Ｄ１〜Ｄ１７が得られる。小領域拡張領域の全ペアの領域類似度を求め、所定しきい値を上回るかもしくはそれ以下である判定を行った結果、小領域拡張領域の３グループ[（D14,D15,D16,D17）、（D5,D6,D7,D8,D9,D10,D11,D12,D13）、（D1,D2,D3,D4）]が得られる。この３グループは各グループ内の小領域拡張領域ペアは全て領域類似度が所定値を上回り、各グループ外のペアでは全て所定値以下となるようなグループ分けとなっている。よってこの３グループから対応する元の小領域の３グループ[グループ１（R１４,R１５,R１６,R１７）、グループ２（R５,R６R７,R８R９,R１０,R１１,R１２,R１３）、グループ３（R１,R２,R３,R４）]を得る。各グループは各オブジェクトの一部であるとみなされる。

よってグループ１に属する小領域を全て統合することによって図８（ｂ）オブジェクト１：羊が、グループ２から（ｃ）オブジェクト２：草が、またグループ３から（ｄ）オブジェクト３：柵、が得られ、結果として入力画像から同図（ａ）に示す小領域過剰分割結果を介してなされるオブジェクト分離抽出が完了する。

次に、本発明の第２の実施形態の画像領域分割装置および画像領域分割方法について説明する。この第２の実施形態は、入力画像をNormalized Cutsを用いて過剰分割する点で、第１の実施形態と異なるが、統合処理は共通である。よって以下ではNormalized Cutsを用いた過剰分割処理についてのみ説明し、小領域の統合処理の説明は省略する。

[A2]Normalized Cutsを用いた過剰分割

Normalized Cutsを利用して、本発明の画像領域分割装置における小領域分割部１を実現する場合について詳細を述べる。該画像領域分割装置の構成を図２に、本構成で小領域に分割する処理の流れを図１０に示す。なお、Normalized Cutsは次の文献で提案されているように既知である。

Jianbo Shi and Jitendra Malik, "Normalized Cuts and Image Segmentation," IEEE Transactions on PAMI, Vol. 22, No. 8, pp.888-905, Aug. 2000.

画素間類似度行列算出部１０１では、画像内の任意の2画素の組み合わせ全てに対し、画素間の色特徴の類似性を示した類似度行列Ｗを算出する。縦N_R画素、横N_C画素、全N_RN_C画素の入力画像内の画素をラスタースキャン順に数え上げて、第i番目の画素の信号値をF(i)、位置座標をX(i)、第j番目の画素の信号値をF(j)、位置座標をX(j)とする。ただし、i,j=1,2,…, N_RN_Cである。N_RN_C行、N_RN_C列の類似度行列Wの第i行第j列の要素w_ijは次の通り算出される（数式１２）。

数式１２においてrは距離しきい値で調整を要するパラメータである。σ_I ²およびσ_x ²はそれぞれ入力画像内の画素の信号値Fの分散および位置座標Xの分散から求める。r以上の距離が離れた画素間は類似性を0とすることを意味する。

算出された類似度行列Wから、画素間類似度行列算出部１０１は同じくN_RN_C行、N_RN_C列の対角行列Dを次式の通り算出する（数式１３）。ただし、対角行列Dの第i行第j列の要素d_ijとする。

評価基準作成部１０２では、算出された類似度行列Wおよびその対角行列Dから色特徴の類似度の高い画素同士が同じ小領域に分割されるための評価基準行列Aを次式の通り作成する（数式１４）。評価基準行列AもまたN_RN_C行、N_RN_C列の行列となる。

固有ベクトル算出部１０３では、評価基準行列Aの固有ベクトルv_pを固有値の小さいものから昇順にP個算出する（p=1,2,...,P）。固有ベクトルv_pはN_RN_C行、1列の行列となる。

小領域算出部１０４では、算出されたP個の固有ベクトルv_pを固有値の小さいものから順次列方向に並べた固有ベクトル行列V=[v₁,v₂,…,v_P]と、類似度行列Wの対角行列Dから次式に示す行列Bを算出する。

行列BはN_RN_C行、P列の行列となる。行列B内の要素を行方向に抽出し、N_RN_C個の行ベクトルu_r (r=1,2,…,N_RN_C)を生成する。すなわち行ベクトルu_r(r=1,2,…,N_RN_C)は行列Ｂの第ｒ行に一致する1行P列の行列であり、行ベクトル（行列）u_rの１行ｊ列（ｊ＝1,2,..,P）成分は行列Bのｒ行ｊ列成分に等しい。

N_RN_C個の行ベクトルu_rの集合が分布するP次元空間を前述のk-meansによりQ個にクラスタリングする。ただし、Qは分割させたい小領域の数を設定する。クラスタリングの結果、N_RN_C個の行ベクトルu_rのそれぞれに1からQまでの小領域番号が付与される。付与された小領域番号を要素とするN_RN_C行、1列の行列を小領域番号行列hとして算出する。小領域番号行列hの要素は、入力画像のラスタースキャン順に対応して順番で、Q個に分割された小領域の番号が記述される。すなわち小領域行列hのi行1列の要素（iは1,2,…,N_RN_Cのいずれか）がQi(Qiは1,…,Qのいずれか)であれば、入力画像におけるラスタースキャン順に数え上げた順番がiの画素は小領域番号Qiの小領域に属している。こうして小領域行列hの各要素を参照することで入力画像のN_RN_C画素が各々どの小領域に属するか決まり、小領域分割結果を得る。

なお、本発明の画像領域分割装置（第１の実施形態および第２の実施形態を含む）は入力画像を入力する入力部と、処理中の画像データを記憶する主記憶部と、プログラムを格納する記録部と、プログラムを実行する中央演算部と、処理結果を表示する表示部とを備えるパーソナルコンピュータ（PC）に対して図１、図２の各種処理を行うプログラムをインストールすることで構築してもよい。

本発明により画像関連の新しいサービスを提供できるようになる。すなわち、本発明の画像領域分割装置により、画像に含まれる個々のオブジェクトを分離できるようになる。そのため抽出された個々のオブジェクトを別々に切り替えて表示することができるようになる。また画像符号化・伝送サービスにも役立つ。すなわち重要なオブジェクトを優先して高画質で符号化することにより、限定された符号レート下での符号化において画像の主観画質を改善するのに役立つ。さらに画像認識サービスにも役立つ。すなわち個々のオブジェクトを抽出することによって、オブジェクトが混在した画像を全体的に解析するよりも、画像内容をより詳細に解析および理解することができるようになる。

１…小領域分割部、２…対象領域選択部、３０…小領域拡張部、６…領域類似度算出部、７…小領域統合部、３…色分布モデル化部、４…分割エネルギー算出部、５…二領域分割・統合部、１１…量子化部、１２…領域境界尤度算出部、１３…領域番号付与部、１４…領域拡大部、１０１…画素間類似度行列算出部、１０２…評価基準作成部、１０３…固有ベクトル算出部、１０４…小領域算出部

Claims (8)

1. 入力画像に含まれる各オブジェクトを分離抽出する画像領域分割装置であって、
   入力画像を色特徴に基づいて複数の小領域に過剰分割する小領域分割部と、
   該過剰分割された複数の小領域の各々に対して、前記入力画像において該小領域に属する内部領域と該小領域に属さない外部領域とを対応付けて出力する対象領域選択部と、
   前記外部領域のうち対応する前記内部領域と色特徴が類似する領域を該内部領域と統合して小領域拡張領域として出力する小領域拡張部と、
   位置及び形状に基づいて前記小領域拡張領域同士のペアの領域類似度を算出する領域類似度算出部と、
   前記小領域のペアのうち、対応する小領域拡張領域ペアの前記領域類似度が所定基準を満たす小領域ペア同士を全て同一オブジェクトに属すると判定して統合し、前記所定基準を満たさない小領域ペア同士は異なるオブジェクトに属すると判定することによって前記各オブジェクトを得る小領域統合部とを備え、
   前記小領域拡張部が、
   前記内部領域に含まれる画素の色の分布から色分布モデルを生成する色分布モデル化部と、
   前記色分布モデルを用いて、前記内部領域に対応する外部領域を該内部領域との色特徴類似性および該外部領域内の局所領域内の色特徴類似性に基づいて二分割するのに必要なエネルギーを求める、該二分割の領域を変数としたエネルギー関数を生成する分割エネルギー算出部と、
   前記エネルギー関数を用いて前記エネルギーを最小とする分割二領域を求め、該分割二領域のうち前記内部領域と色特徴の類似性があると判定された領域を前記内部領域と統合して前記小領域拡張領域として出力する二領域分割・統合部とを備えることを特徴とする画像領域分割装置。
2. 前記二領域分割・統合部が、
   前記エネルギー関数を用いて前記エネルギーを最小とする分割二領域を求めるに際して、前記外部領域内に含まれる前記過剰分割された小領域単位で前記エネルギーを最小とする領域を求めることを特徴とする請求項１に記載の画像領域分割装置。
3. 前記小領域分割部が、
   入力画像を減色して減色画像に変換する量子化部と、
   前記減色画像の領域境界尤度を所定サンプリング密度の画素単位で算出する領域境界尤度算出部と、
   前記領域境界尤度の分布から前記領域境界尤度を算出された各画素が領域境界に属するか領域に属するかを判定し、領域に属する場合は領域番号を付与する領域番号付与部と、
   前記領域境界に属するか領域に属するかを判定された画素以外の残りの画素に対して、前記領域番号を付与された画素の局所分布に基づいて領域に属すると判定される画素に領域番号を付与し、前記入力画像全体における前記領域番号を付与された画素の連結領域として前記複数の小領域の各々を得る領域拡大部とを備えることを特徴とする請求項１または２に記載の画像領域分割装置。
4. 前記小領域分割部が、
   前記入力画像の画素間の色特徴の類似性を示す類似度行列および該類似度行列の対角行列を算出する画素間類似度行列算出部と、
   前記類似度行列および前記対角行列を用いて、色特徴の類似度の高い画素同士が同じ小領域に分割されるための評価基準行列を作成する評価基準作成部と、
   前記評価基準行列の固有ベクトルを固有値昇順に所定数求める固有ベクトル算出部と、
   前記固有ベクトルおよび前記対角行列を用いて、前記入力画像の各画素が所定数の小領域のいずれに属するかを示す小領域番号行列を算出し、該小領域番号行列を参照して前記複数の小領域の各々を得る小領域算出部とを備えることを特徴とする請求項１または２に記載の画像領域分割装置。
5. 前記色分布モデルに混合正規分布モデル（GMM）を用いることを特徴とする請求項１ないし４のいずれかに記載の画像領域分割装置。
6. 前記色分布モデルにヒストグラムを用いることを特徴とする請求項１ないし４のいずれかに記載の画像領域分割装置。
7. 入力画像に含まれる各オブジェクトを分離抽出する画像領域分割方法であって、
   入力画像を色特徴に基づいて複数の小領域に過剰分割する小領域分割ステップと、
   該過剰分割された複数の小領域の各々に対して、前記入力画像において該小領域に属する内部領域と該小領域に属さない外部領域とを対応付けて出力する対象領域選択ステップと、
   前記外部領域のうち対応する前記内部領域と色特徴が類似する領域を該内部領域と統合して小領域拡張領域として出力する小領域拡張ステップと、
   位置及び形状に基づいて前記小領域拡張領域同士のペアの領域類似度を算出する領域類似度算出ステップと、
   前記小領域のペアのうち、対応する小領域拡張領域ペアの前記領域類似度が第一の所定基準を満たす小領域ペア同士を全て同一オブジェクトに属すると判定して統合し、第一の所定基準を満たさない小領域ペア同士は異なるオブジェクトに属すると判定することによって前記各オブジェクトを得る小領域統合ステップとを備え、
   前記小領域拡張ステップは、
   前記内部領域に含まれる画素の色の分布から色分布モデルを生成する色分布モデル化ステップと、
   前記色分布モデルを用いて、前記内部領域に対応する外部領域を該内部領域との色特徴類似性および該外部領域内の局所領域内の色特徴類似性に基づいて二分割するのに必要なエネルギーを求める、該二分割の領域を変数としたエネルギー関数を生成する分割エネルギー算出ステップと、
   前記エネルギー関数を用いて前記エネルギーを最小とする分割二領域を求め、該分割二領域のうち前記内部領域と色特徴の類似性があると判定された領域を前記内部領域と統合して前記小領域拡張領域として出力する二領域分割・統合ステップとを備えることを特徴とする画像領域分割方法。
8. 入力画像に含まれる各オブジェクトを分離抽出する画像領域分割プログラムであって、コンピュータに、
   入力画像を色特徴に基づいて複数の小領域に過剰分割する小領域分割ステップと、
   該過剰分割された複数の小領域の各々に対して、前記入力画像において該小領域に属する内部領域と該小領域に属さない外部領域とを対応付けて出力する対象領域選択ステップと、
   前記外部領域のうち対応する前記内部領域と色特徴が類似する領域を該内部領域と統合して小領域拡張領域として出力する小領域拡張ステップと、
   位置及び形状に基づいて前記小領域拡張領域同士のペアの領域類似度を算出する領域類似度算出ステップと、
   前記小領域のペアのうち、対応する小領域拡張領域ペアの前記領域類似度が第一の所定基準を満たす小領域ペア同士を全て同一オブジェクトに属すると判定して統合し、第一の所定基準を満たさない小領域ペア同士は異なるオブジェクトに属すると判定することによって前記各オブジェクトを得る小領域統合ステップとを実行させ、
   前記小領域拡張ステップでは、コンピュータに、
   前記内部領域に含まれる画素の色の分布から色分布モデルを生成する色分布モデル化ステップと、
   前記色分布モデルを用いて、前記内部領域に対応する外部領域を該内部領域との色特徴類似性および該外部領域内の局所領域内の色特徴類似性に基づいて二分割するのに必要なエネルギーを求める、該二分割の領域を変数としたエネルギー関数を生成する分割エネルギー算出ステップと、
   前記エネルギー関数を用いて前記エネルギーを最小とする分割二領域を求め、該分割二領域のうち前記内部領域と色特徴の類似性があると判定された領域を前記内部領域と統合して前記小領域拡張領域として出力する二領域分割・統合ステップとを実行させるプログラム。