JP4586103B2 - 画像抽出方法及び装置 - Google Patents

Description

本発明は、画像抽出方法及び装置に関し、より具体的には、画像中から特定カテゴリーの対象を抽出する画像抽出方法及び装置並びに記憶媒体に関する。

特開平８−７１０７号公報 特開平８−１６７７９号公報 特開平７−３３４６７５号公報 特公平７−３４２１９号公報 特開平３−２４０８８４号公報 特開平７−２２５８４７号公報 特開平６−２５１１４９号公報 特開平７−１０７２６６号公報 特開平８−７０７５号公報 特開平８−７７３３６号公報 特公平６−４２０６８号公報 特公平８−２０７２５号公報 特許２６４２３６８号公報 特開平９−５０５３２号公報 特開平６−１６８３３１号公報 特開平５−２４２１６０号公報

M.Kass, A.Witkin, D.Terzopoulos, Snakes, "Active Contour Models,International Journal of Computer Vision, pp.321-331, 1988 A.De Bimbo and P.Pa1a, "Visua1 Image Retrieval by Elastic Matching of User Sketches", IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 19,pp. 121-132, 1997 L.H.Steib and J.S.Duncan, "Boundary Finding with Parametrically Deformable Mode1s", IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 14, pp. 1061-1075, 1992 F. S. Cohen, Z. Huang, Z. Yang, "Invariant Matching and Identification of Curves Using B-Splines curve Representation", IEEE Trans. on Image Processing, vo1. 4, pp. 1-10, 1995 G. C. H. Chuang and C. C. J. Kuo, "Wave1et Descriptor of Planar Curves:Theory and App1ications", IEEE Trans. on Image Processing, vol. 5, pp. 56-70, 1996

従来、画像から特定の被写体又は対象を切り出す処理として、種々の方式が知られている。第１の方式は、ユーザが指定した物体又は背景上の点の画素値を含む所定範囲の色成分値（又は濃淡値）を有する領域を選択しながら、背景の除去又は抽出被写体の領域指定を繰り返す方法（特開平８−７１０７号公報、特開平８−１６７７９号公報、特開平７−３３４６７５号公報及び特公平７−３４２１９号公報等）、及び、抽出対象の輪郭線を含む大まかな粗輪郭線領域又は局所領域を指定し、その指定領域内で細線化又はクラスタリングなどの処理により対象の境界輪郭線を求めて切り出す方法（特開平３−２４０８８４号公報、特開平７−２２５８４７号公報、特開平６−２５１１４９号公報、特開平７−１０７２６６号公報、特開平８−７０７５号公報、特開平８−７７３３６号公報、特公平６−４２０６８号公報及び特公平８−２０７２５号公報など）がある。

第２の方式として、切り出し対象の画像部分を大まかに囲むように閉曲線（又は多角形の境界線）を設定し、色成分の情報のみを用いて対象物の形状にほぼ近い切り出しマスク画像を生成する方法（特許２６４２３６８号公報など）がある。

第３の方式として、画像から対象物体を検出し、その輪郭を抽出する構成（特開平９−５０５３２号公報など）において、多重解像度を利用した粗密探索により入力濃淡画像をモザイク化した画像辞書データを参照しながら対象物体の位置とサイズを求め、それらに基づいて初期輪郭を設定する動的輪郭法（Ｍ．Ｋａｓｓ， Ａ．Ｗｉｔｋｉｎ， Ｄ．Ｔｅｒｚｏｐｏｕｌｏｓ， Ｓｎａｋｅｓ， "Ａｃｔｉｖｅ Ｃｏｎｔｏｕｒ Ｍｏｄｅｌｓ，Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ， ｐｐ．３２１−３３１， １９８８）を用いて輪郭を抽出する方法がある。

その他、画像中の特定の物体の有無の判定、又は特定の物体が存在する画像をデータベースから検索して抽出することに利用可能な技術として、予め用意したテンプレートを画像上でスキャンし、各位置でのマッチング度を算出し、そのマッチング度が所定の閾値以上となる位置を探索する方法（特開平６−１６８３３１号公報）、画像データベース作成時に画像中の構成要素の領域と構成要素名を入力しておき、所定の特徴を有する画像を高速に検索する方法（特開平５−２４２１６０号公報）、ユーザにより与えられた例（スケッチ及び画像等）との類似度を求め、その類似度が高い画像を検索する方法（文献１：Ａ．Ｄｅ Ｂｉｍｂｏ ａｎｄ Ｐ．Ｐａ１ａ， "Ｖｉｓｕａ１ Ｉｍａｇｅ Ｒｅｔｒｉｅｖａｌ ｂｙ Ｅｌａｓｔｉｃ Ｍａｔｃｈｉｎｇ ｏｆ Ｕｓｅｒ Ｓｋｅｔｃｈｅｓ"， ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ｖｏｌ． １９，ｐｐ． １２１−１３２， １９９７など）、及び、形状モデルを用いて境界線を検出する方法（文献２：Ｌ．Ｈ．Ｓｔｅｉｂ ａｎｄ Ｊ．Ｓ．Ｄｕｎｃａｎ， "Ｂｏｕｎｄａｒｙ Ｆｉｎｄｉｎｇ ｗｉｔｈ Ｐａｒａｍｅｔｒｉｃａｌｌｙ Ｄｅｆｏｒｍａｂｌｅ Ｍｏｄｅ１ｓ"， ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ｖｏｌ． １４， ｐｐ． １０６１−１０７５， １９９２）などがある。

曲線をパラメトリックにモデル化する一手法として、スプライン曲線を用いる方法（Ｆ． Ｓ． Ｃｏｈｅｎ， Ｚ． Ｈｕａｎｇ， Ｚ． Ｙａｎｇ， ”Ｉｎｖａｒｉａｎｔ Ｍａｔｃｈｉｎｇ ａｎｄ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｏｆ Ｃｕｒｖｅｓ Ｕｓｉｎｇ Ｂ−Ｓｐｌｉｎｅｓ ｃｕｒｖｅ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ”， ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ， ｖｏ１． ４， ｐｐ． １−１０， １９９５）、フーリエ記述子を用いる手法（文献２）、及びウェーブレット記述子を用いる方法（Ｇ． Ｃ． Ｈ． Ｃｈｕａｎｇ ａｎｄ Ｃ． Ｃ． Ｊ． Ｋｕｏ， ”Ｗａｖｅ１ｅｔ Ｄｅｓｃｒｉｐｔｏｒ ｏｆ Ｐｌａｎａｒ Ｃｕｒｖｅｓ：Ｔｈｅｏｒｙ ａｎｄ Ａｐｐ１ｉｃａｔｉｏｎｓ”， ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ， ｖｏｌ． ５， ｐｐ． ５６−７０， １９９６）などがある。

しかしながら、上述の第１の方式による画像抽出法は、ユーザの比較的詳細な指示による操作を必要とするので、特定の形状を有する対象物を画像から探索して抽出（切り出し）する処理を自動化できない。

切り出し対象の画像部分を大まかに囲む閉曲線等を指定する方法（特許２６４２３６８号公報）に代表される第２の方式では、閉曲線内に含まれる同じ色成分を有する領域の面積の割合を用いるので、閉曲線内の背景中に被写体と同色となる領域がある場合、及び閉曲線領域が切り出し対象領域と比べて２倍以上の面積を有する場合などでは、背景部分が抽出されるなどの誤抽出を生じ易いという問題があり、汎用性に欠ける。

第３の方法を示す特開平９−５０５３２号公報に記載される輪郭検出装置では、いわゆる動的輪郭法を用いるので、入力画像の背景部分（抽出対象以外の部分）が複雑なテクスチャパターンを有する場合などでその影響を受けて、抽出すべき輪郭線の複雑さを反映することが困難な場合が多い。すなわち、本来の輪郭線形状から外れた不自然な凹凸形状が抽出されるという問題があった。

文献２に記載される輪郭抽出法では、輪郭モデルのパラメータ及び輪郭モデルの誤差をガウシアン分布と仮定する確率モデルを前提とするので、実際にそれらの分布が非ガウシアンとなる場合には、正しい輪郭を効率よく抽出することが困難であり、輪郭モデルと抽出対象の形状の差異に関する許容度が低い。

本発明は、このような問題点を解決する画像抽出方法及び装置を提示することを目的とする。

本発明はまた、より高速に所望の画像を精度良く抽出できる画像抽出方法及び装置を提示することを目的とする。

本発明に係る画像抽出方法は、第１のマッチング手段が入力画像と局所的な図形要素を含むテンプレートとの所定の特徴量の値に関する所定の評価関数値を求める第１のマッチング処理を行う第１のマッチングステップと、局所変換手段が前記テンプレート上の所定の代表点の近傍領域について局所的な幾何学的変換を行う局所変換ステップと、変換パラメータ算出手段が前記局所変換ステップの変換パラメータを前記第１のマッチング処理結果、および、所定の変形モードまたは確率分布の少なくとも一方、に基づいて求める変換パラメータ算出ステップと、第２のマッチング手段が前記局所変換ステップにより得られるテンプレートと前記入力画像との第２のマッチング処理を行う第２のマッチングステップと、画像領域抽出手段が前記第２のマッチング処理の結果に基づき前記輪郭線を含む画像領域を抽出する画像領域抽出ステップとを具備することを特徴とする。

本発明に係る画像抽出装置は、入力画像と局所的な図形要素を含むテンプレートとの所定の特徴量の値に関する所定の評価関数値を求める第１のマッチング処理を行う第１のマッチング手段と、前記テンプレート上の所定の代表点の近傍領域について局所的な幾何学的変換を行う局所変換手段と、前記局所変換手段の変換パラメータを前記第１のマッチング処理結果、および、所定の変形モードまたは確率分布の少なくとも一方、に基づいて求める変換パラメータ算出手段と、前記局所変換手段により得られるテンプレートと前記入力画像との第２のマッチング処理を行う第２のマッチング手段と、前記第２のマッチング処理の結果に基づき前記輪郭線を含む画像領域を抽出する画像領域抽出手段とを具備することを特徴とする。

本発明によれば、テンプレートデータの走査及びその形状に関する適合度評価、並びに拘束条件を与えた変形（移動範囲、形状拘束条件及び局所幾何学的変換など）を実行することにより、形状に関する予め与えられた情報に適合する対象物を画像から自動的に探索することができる。また、適合する範囲において変形の許容度が高く、ノイズに強い輪郭抽出及び画像抽出が可能になる。

テンプレートの変形に際して、変形（代表点の移動）に関する拘束条件の全体的なセットが与えられ、又は幾何学的位相を保存するような局所幾何学的変換の推定を行うので、大域的な形状情報が常に保持され、局所的なノイズ等の影響を受けにくい。従って、背景が複雑なパターンを有していても、不自然な輪郭の抽出が効果的に防止される。

本発明の一実施例の概略構成ブロック図である。 画像処理装置１６の概略構成ブロック図である。 テンプレートデータの一例と移動範囲を示す模式図である。 テンプレートデータの例を示す表である。 本実施例の動作フローチャートである。 画像表示装置１４の表示画面例である。 太線上でのエッジ割合の説明例の模式図である。 更新テンプレート生成処理過程におけるテンプレート図形の変形の様子を示す模式図である。 Ｐ５がＰ５’に移動したことに伴う、代表点Ｐ６，Ｐ７の移動の様子を示す模式図である。 更新テンプレート生成処理（図５のＳ７）を変更した実施例の変更部分の動作フローチャートである。 人体のテンプレートモデルの例である。 幾何学的（アフィン）変換パラメータの推定手順を示すフローチャートである。 不定部分を有するテンプレートモデルの輪郭推定手順を説明する模式図である。 第３実施例におけるテンプレート更新処理のフローチャートである。 図１４の説明例である。

以下、図面を参照して、本発明の実施例を詳細に説明する。

図１は、本発明の一実施例の概略構成ブロック図を示す。１０は画像入力装置、１２は画像データ及びテンプレートモデルデータを記憶する画像記憶装置、１４は画像表示装置、１６は画像処理装置、１８はマウスなどのポインティング・デバイスからなる指示選択装置である。画像入力装置１０は、イメージ・スキャナ、ディジタル・カメラなどの撮像装置、又は、画像データベースに接続する画像データ転送装置からなる。

本実施例では、画像入力装置１０から、背景から分離抽出されるべき対象を含む画像データが入力し、画像記憶装置１２に記憶される。画像記憶装置１２に記憶される画像データは、画像表示装置１４の画面上の所定位置に所定の形式で表示される。

画像処理装置１６の概略構成を図２に示す。２０は入力画像の特徴量を抽出する特徴量抽出装置、２２は、テンプレートモデル選択装置、２４は、複数解像度のテンプレートデータを生成するテンプレートデータ生成装置、２６は、テンプレートの走査及び入力画像の特徴量との第１のマッチング評価を実行するテンプレート走査装置、２８は、テンプレート上の各代表点の移動範囲・条件を更新及び設定する移動範囲・条件更新設定装置、３０は更新テンプレート生成装置、３２は変形後の形状適合度の評価を画像特徴量との第２のマッチング処理により変形後の形状適合度を評価する形状適合度評価装置、３４は、更新テンプレートの代表点間を滑らかにつなぐスプライン補間曲線によりその図形要素の境界線を生成する境界線生成装置、３６は更新テンプレートの境界線を画像表示装置１４の画面上で入力画像に重畳して表示する境界線表示装置、３８は更新テンプレートの境界線内部の領域を示すマスクデータを生成するマスクデータ生成装置である。図示していないが、更に、更新テンプレートの境界線及び／又はマスクデータを記憶する記憶装置を具備する。

先ず、本実施例で用いるテンプレートモデル及びパラメトリックな曲線表現方法を説明する。

テンプレートデータは、抽出カテゴリー（人物、自動車、魚及び飛行機など）を代表する抽象化された図形要素又は代表的な画像（図形）パターンを主たる構成要素とし、典型的にはそれらを構成する輪郭線データ若しくはその輪郭線を含む背景が無地の濃淡画像又はカラー画像等により与えられる。この輪郭線データは、該当するカテゴリーの外形を表わすものに限らず、そのカテゴリーを構成する主要な形状データ（例えば、人物の顔を構成する目、鼻及び口など）を含んでよいことはいうまでもない。

各カテゴリーに属する図形要素の輪郭線は、代表点間を通る曲線又は線分で構成され、予めスプライン曲線、フーリエ記述子及びウェーブレット記述子などにより、パラメトリックに表現されているものとする。

例えば、輪郭線モデルの全体はＪ個のスプライン曲線から構成され、ｊ番目のスプライン曲線

r_j(t) = [ x_j(y), y_j(t)]
は、ｎ_ｊ＋１個の制御点を有するｍ_ｊ次のＢスプラインであるとすると、

ここに、ｊ＝０，１，・・・，Ｊである。また、Ｑ_N，m＋1（ｔ）は、

のように表わされる。Ｃ_Ｎ＝［Ｃ_ｘ，Ｎ，Ｃ_ｙ，Ｎ］は、Ｎ番目の制御点位置を示すベクトルである。

フーリエ記述子を用いる場合には、

と表現される。但し、

である。ｔは、弧長ｓと全周長Ｓを用いて、ｔ＝２πｓ／Ｓのように表わされる。フーリエ記述子を用いて曲線の一部を表現する場合には、その両端点で

x(t) = x(2π−t)

y(t) = y(2π一t)
とし、従って、ｂ_ｋ＝ｄ_ｋ＝０とすればよい。

ウェーブレット記述子を用いる場合は、

ここで、

である。

ウェーブレット関数はそれぞれ周期性を有し、以下のように定義される。すなわち、

ここに、ｋ，ｍ，ｎは、０又は正の整数であり、関数φ，ψは、双直交３次スプライン関数等が用いられる。

テンプレートを構成する輪郭線は、抽出対象の形状を表わす輪郭線を一つの閉曲線として表わすのではなく、抽出対象のカテゴリーを表わす形状の部分的輪郭線からなる構成（例えば、本出願と同じ出願人による特開平７−３２００８６号公報に記載されたモデル）を用いてもよい。

代表点の粗密分布及びこれら曲線のパラメータ（例えば、Ｂスプライン関数の次数及び制御点の数など）は、抽出すべき対象の形状に関する複雑さ及び滑らかさなどを表現し、反映するものである。図３（ａ）は、テンプレートを構成する図形要素の一例を示す。テンプレートデータ生成装置２４が、画像データから輪郭線抽出などによりこの図形要素を生成してもよい。

図３（ｂ）及び図４（ａ），（ｂ）に例示するように、テンプレートデータには、代表点位置とスプライン曲線などのパラメータに関するデータ（曲線の次数及び種別）の他に、各代表点の移動範囲データ又は後述の形状拘束条件が与えられる。

移動範囲を各代表点で明示的に表わすのではなく、単に代表点近傍での形状の凹又は凸が保持されること、若しくは、曲率が保持されること及び新たなループが生成しないことなどの局所形状条件を与えて、それらを移動条件データとして各代表点ごとに与えてもよい。この場合、そのようにして定められる局所形状条件が破られないことと、移動後の更新テンプレートの形状に関する後述する適合度が基準値を満たさないことといいう２つの条件の下で代表点の移動範囲を徐々に拡大して探索し、適合度が基準値以上となった位置で代表点の移動を停止する。

形状拘束条件としては、例えば、図４（ａ）の４行目に記載されるように、

とする。（ｘ_ｊ，ｙ_ｊ）は、ｊ番目の代表点位置を示す。数８は、代表点（ｘ_ｊ，ｙ_ｊ）の近傍の形状に関する凹凸及び曲率の保持されるべき範囲の概算値を示す。

サイズに関する拘束条件として、例えば、

とする。これと形状拘束条件により、（ｘ_ｊ−１，ｙ_ｊ−１），（ｘ_ｊ，ｙ_ｊ）が定まれば、（ｘ_ｊ＋１，ｙ_ｊ＋１）は、数８及び数９を満たす範囲の平均値として求めることが出来る。数９でｄ_ｊは、点（ｘ_ｊ，ｙｊ）と（ｘ_ｊ＋１，ｙ_ｊ＋１）とを結ぶ線分長の基準値、μはその許容する変化幅の基準値をそれぞれ示す。

図３には、ｊ−１，ｊ，ｊ＋１番目の各代表点とそれらを連結するパラメトリックに表現された曲線及び各移動範囲が、図示されている。移動範囲データは、テンプレートを構成する代表点の移動に伴う元のテンプレート形状からの変形許容度を与えるものとして予め与えられている。各移動範囲は、抽出対象の各部分の非剛性度（弾性度及び関節の有無など）及びアプリオリな形状に関する知識によって一般的に異なり、また、テンプレートの変形更新過程においても適宜に変化しうる。

例えば、人物の頭部は、通常、２次曲線（楕円形状）関数で近似される凸形状であるが、この頭部を構成する代表点の移動範囲は、移動により新たな凹部が発生しないことを条件に定められる。頭部を構成する外形の曲線を輪郭線に沿った弧長の関数として表わした時、凹部の発生は、２階微分値（又はこれに相当する近似値）が正となることにより検出される。

従って、ある代表点の移動範囲の大きさ及び形状は、その点に隣接する代表点を固定したときに、代表点間を結ぶ曲線が移動後の代表点の近傍において２階微分値（又はその近似値）が正とならない範囲となるように決定される。この範囲は、厳密には、当該代表点を除く他の代表点の移動とともに相対的に変化するが、変形量が大きくなく且つ形状の類似性が保たれる範囲として、予め各代表点ごとに固定（代表点ごとにその範囲の大きさ及び形状が異なっても良い）して、設定されている。

本実施例における画像抽出手順を説明する。図５は、その動作フローチャートを示す。撮影手段などの画像入力装置１０から画像データ入力される、画像記憶装置１２に格納され、図６に例示するように画像表示装置１４の画面上に表示される（Ｓ１）。図６で、４０は画像表示装置１４の画面、４２は入力画像、４４はテンプレートモデル画像データ、４６は目標位置確認インディケータ、４８は抽出指示ボタン、５０はテンプレートスクロールボタンである。

特徴量抽出装置２０は、入力画像の特徴量分布（エッジ強度分布又は各点での局所空間周波数に関する情報など）を求め、所定の閾値で２値化する（Ｓ２）。

テンプレート選択装置２２は、テンプレートモデル画像データ４４を画像表示装置１４の表示画面４０上に表示する。ユーザが、抽出カテゴリーのテンプレートデータを選択すると、選択されたテンプレートデータの情報（例えば、図４に例示されるデータ）が読み込まれる（Ｓ３）。テンプレートモデル画像データ４４に表示される一覧からスクロールボタン５０によりテンプレートモデル画像データ４４の表示内容をスクロールして所望のものを表示させ、指示選択装置１８により選択することにより、希望する１つのテンプレートモデル画像データを選択できる。抽出カテゴリーは、例えば、マイクなどの音声入力装置及び音声認識装置により口頭で抽出カテゴリーの名称を指示入力してもよい。ユーザにより所望のテンプレートデータが選択されると、テンプレートデータ生成装置２２は、選択されたテンプレートデータから互いに大きさが異なる複数（通常は１０未満）のテンプレートセットを自動生成する（Ｓ４）。

テンプレート走査装置２６は、各テンプレートをそれぞれ画像上でその大きさに応じた所定のサンプリングピッチ（例えば、テンプレート図形の横幅の１０分の１など）でラスタースキャンし（Ｓ５）、各場所で第１の形状適合度を求める（Ｓ６）。具体的には、形状の適合度を表わすパラメータとして、テンプレート上の図形要素の輪郭線上又はその輪郭線を所定幅（典型的には、５画素程度）に太線化して得られる太線上で、エッジである点の割合及びエッジ点でのエッジ強度勾配の向きの揃い具合（又はそれらの距離）を表わす勾配ベクトルの内積（の絶対値）の総和（又はエッジ点であって上記内積値が基準値以上の点の割合）を求める。

太線上でのエッジ割合とは、図７に例示するように、太線の中心線上のサンプリング点とそのサンプリング点を含む微小領域（太線領域セル）においてエッジが存在する場合にそのサンプリング点をエッジ点としてカウントする要領で総サンプリング点数に対するエッジ点数の割合である。第１の形状適合度は、画像中の抽出対象とテンプレートとの全体的な形状類似度を表わす。

適合度パラメータとしては、本出願と同じ出願人による特開平９−１８５７１９号公報に示されるように、テンプレートモデルの輪郭線近傍の画像データ（色成分の情輝度分布など）に関する誤差の逆数等を適合度の尺度として用いてもよい。

複数の大きさの異なるテンプレートの走査及び適合度評価の過程において、あるテンプレートの適合度パラメータが所定の基準値以上となったとき、そのテンプレートの走査を停止し、ユーザに対しては目標対象確認インディケータ４６（図６）が表示される。この段階で、対象の位置と大きさに関する情報が抽出されたことになる。ユーザが抽出ボタン４８を押して抽出実行処理の開始を指示すると、次の更新テンプレート生成処理（Ｓ７）が実行される。

図８は、更新テンプレート生成処理過程におけるテンプレート図形の変形の様子を示す。図８（ａ）では、テンプレート図形の初期形状と入力画像の対象物形状とのマッチングの程度（補間曲線上のエッジ割合など）が、小さい部分の代表点Ｐ１，Ｐ２，・・・，Ｐ７のように表示されている。これら以外の代表点は、比較的マッチングが良好な点であり、図３（ｂ）に示すような各移動範囲内で最適な移動先が検出される。

更新テンププレート生成処理（Ｓ７）では、テンプレート図形要素変形装置３０が、テンプレート図形を構成するある図形要素（曲線セグメント）の代表点を移動範囲内で（又は数８及び数９などの移動条件に従って）移動し（Ｓ７ａ）、テンプレート図形要素変形装置３０が移動後の代表点間を結ぶ新たな曲線セグメントを生成し（Ｓ７ｂ）、形状適合度評価装置３２が各部分で第２の形状適合度を評価することにより（Ｓ７ｃ）、第２の形状適合度が所定の基準値以上又は最大となるように代表点が移動され、最終的に、境界線生成装置３４が、代表点間を結ぶ曲線（又は線分）を生成する。これらの処理を実行する過程で、移動条件の緩和等（Ｓ７ｄ）が必要に応じて行われ、最終的に、移動条件を満足するようにテンプレート全体が変形される（Ｓ７ｅ）。

境界線表示装置３６が、画像表示装置１４の画面上にその境界線を入力画像に重畳して表示する。更新テンプレートデータはその境界線データ又はその領域を示す２値のマスクデータとして生成される。

移動と適合度評価は、各代表点を同時に移動しながら実行するのではなく、エッジ割合の高いセグメントの端点をなす代表点に隣接するエッジ割合の低いセグメントを中継する代表点の移動を優先して行うと効率的である。図８（ｂ）は、そのようにして移動した後の代表点間を結ぶ曲線を表わす更新テンプレートの形状を示す。図８（ｂ）で、図８（ａ）のＰｉは、図８（ｂ）では、Ｐｉ’に移動している。例えば、図８（ａ）において、エッジ割合の高いセグメントの端点である代表点Ｑに隣接する代表点Ｐ５について、点Ｑを中心とする所定の半径（例えば、ＱからＰ５までの弧長）の円弧上でＰ５の移動先を初めに探索する。

代表点位置の移動先探索では、上述した移動範囲を所定の確率分布（特に、移動範囲の外で値が０となるようなもの）により表わし、その分布により与えられる代表点位置を確率的に生成し、その代表点を含む曲線セグメントの形状適合度をその都度評価することにより、値が所定基準値以上（又は量大）となる位置を推定してもよい。

代表点の移動先は、第２の形状適合度の評価結果に基づいて決定される。第２の形状適合度は各代表点について定義され、その代表点に隣接する代表点（通常、２つ）との間を結ぶ曲線（又は線分）上のエッジ割合とその曲線（又は線分）上の特徴量勾配（エッジ強度分布の勾配など）の許容範囲内での一致度（許容範囲内で一致している点の割合）の線形和で表わされる。

移動範囲・条件更新設定装置２８は、この第２の形状適合度の値に応じて当該代表点の移動範囲を拡大し、又は移動条件を緩和して（Ｓ７ｄ）、未だ探索されていない領域から最適な代表点位置、即ち第２の形状適合度が最大となる代表点位置を探索して移動してもよい。即ち、第２の形状適合度に基づいて上述したテンプレートの図形要素を変形することにより、抽出カテゴリーに属するテンプレートの輪郭線形状データと多少異なる輪郭線を有する対象であっても、非適合部分についての代表点移動範囲の拡大又は移動条件の緩和がなされる結果、全体の輪郭抽出が可能となる。

図８に示す例では、Ｐ５がＰ５’に移動したことに伴い、残りの連続して存在する代表点の移動範囲は、Ｐ５’の位置に基づいて更新される。その様子を図９に示す。具体的には、例えば、Ｐ５’，Ｐ６’，Ｐ７’を通る曲線の形状が凸であることと、その曲線の長さと同程度のサイズを維持することの少なくとも一方を拘束条件に移動範囲を設定し、探索を実行する。何れの条件又は両方の条件を用いるかは、抽出対象の非剛性度及び関節の有無などにより異なるが、予めテンプレートデータに定義されているものとする。

図９では、Ｐ６とＰ６’及びＰ７とＰ７’の探索範囲の大きさは同程度であり、各探索範囲の配置は、形状が凸であることの拘束条件（例えば、数８及び数９に示す条件）を当てはめて設定されている。新たに設定される移動範囲は、図９（ｂ）に示すように、元の移動範囲と全く重なり合わないような離れた所になる場合もある。

移動範囲を明示的に設定せずに移動の拘束条件のみを与えて代表点を移動する場合には、Ｐ５’，Ｐ６’，Ｐ７’を通る曲線の接線方向の変化率が正であること（数８及び数９参照）等を条件として課せばよい。

移動後の代表点間を結ぶ曲線は、元のテンプレートを構成する曲線と同種の曲線を用いるのが望ましい。但し、パラメータの次数等は、抽出対象の形状に最も適合するように変更可能とする。例えば、Ｂスプライン曲線を用いる場合、次数及び制御点の数等は変更しても構わない。

更新後のテンプレートを構成する曲線パラメータの決定法の一例を説明する。或る曲線セグメントｖ（ｓ）＝（ｘ（ｓ），ｙ（ｓ））^Ｔがｎ階のＢスプライン関数を用いてモデル化されているとする。代表点移動後のパラメータの最適値は、例えば、以下のように推定される。即ち、

ここで、Ｔは転置行列を示し、Ｂ（ｓ）はＢスプライン行列、ｔは曲線セグメントの長さ、ＱはＢスプラインパラメータをそれぞれ示す。

曲線セグメントに対応する抽出対象の輪郭線をｖ’（ｓ）＝（ｘ’（ｓ），ｙ’（ｓ））^Ｔとし、各点での特徴量（エッジ強度値など）をＥ_ｖ’（ｓ）とおき、Ｅ_ｖ’（ｓ）がＥ_ｖ（ｓ）に対して正規分布をなすとすると、その確率分布密度関数は、

となる。ここで、（σ_ｘ）^２，（σ_ｙ）^２は、Ｅ_ｖ’（ｓ）＝（Ｅ_{ｘ’（ｓ）}，Ｅ_{ｙ’（ｓ）}）に対する分散を示す。

本実施例では説明を簡単化して理解を容易にするため、Ｅ_ｖ（ｓ）は２値（０又は１）とし、テンプレート図形の輪郭モデルデータは、Ｅ_ｖ（ｓ）＝１となる点の集合として与えられるものとする。このとき、最ゆう推定値は、

で与えられる。Ｑの階数等は、以下に示す情報量基準ＡＩＣ（Ｑ）が最小となるｎなどのようにして求められる。具体的には、

である。Ｎｕｍｂｅｒ（Ｑ）は、Ｑの要素数である。

移動範囲の拡大は、典型的には、元の移動範囲の形状を単純に所定の倍率で拡大する。しかし、テンプレート図形要素の当該代表点を含む曲線の接線方向を大きくとるような非等方的な拡大でもよい。このとき、前述した移動条件を満たす範囲で探索することはいうまでもない。

移動に関する拘束条件の緩和によっても第２の形状適合度が所定の基準値（例えば０．３）未満である代表点の数がその全体の一定数以下（例えば、過半数）ならば、当該テンプレートの変形を停止し、大きさ等の異なる他のテンプレートに切り替えて上述した処理を実行しても良い。

当該代表点の近傍にある代表点間を結ぶテンプレートの曲線セグメント上でエッジ割合が極めて高い場合（例えば、０．９以上）、当該代表点の上述したような移動先の探索を行わなくてもよい。

図８（ｃ）に示すように、代表点間を結ぶ曲線（又は線分）上において、先に抽出された特徴量の非エッジ点がある場合、その非エッジ点を付加代表点として追加し（そのような非エッジ点が連続している場合にはその連続した非エッジ線分上の中点を新たな代表点とする）、その代表点について同様に移動範囲を設定して（又は移動条件を満たすように移動探索を行って）拘束条件を満たす位置へ移動させ、その代表点に隣接する代表点との間を結ぶ曲線を生成してもよい。この代表点の付加は、自動的に行うことができるが、ユーザの指示により実行しても良い。適切な代表点位置が検出されない場合には、同様にして、移動範囲の拡大又は移動条件の緩和を実行する。

最後に、更新後のテンプレート輪郭線を表示し（Ｓ８）、輪郭線データからマスクデータを生成し（Ｓ９）、必要に応じて輪郭線又はマスクデータを記憶装置に記録して（Ｓ１０）、処理を終了する。

以上の各処理は、コンピュータで実行可能な所定のプログラム形式により形成されていても良いし、各部の処理を所定のゲートアレイ（ＦＰＧＡ及びＡＳｌＣ等）などのハードウェア、又は所定のコンピュータプログラムと図１に示す一部の要素を実現する部分的ハードウェアモジュールとが混在する形式でも実現できることは明らかである。ハードウェアモジュールが含まれる場合、必ずしも各構成要素が図１に示す構成と同一でなくてもよく、その機能が実質的に同一であるもの、又は、一つの要素が図１の複数の要素の機能を備えるものなどは、本発明の技術的範囲に含まれることはいうまでもない。この点は、以下の実施例において同様である。

更新テンプレート生成処理（図５のＳ７）を変更した実施例を説明する。この変更実施例（第２実施例）では、テンプレートの走査と適合度評価を実行して、抽出対象の位置と適切なテンプレートモデルを選択した後、本実施例に特有の更新テンプレート生成処理を実行する。その具体的処理手順のフローチャートを図１０に示す。

先ず、更新前のテンプレートデータから形状適合度の低いセグメントを含む代表点を自動抽出し（Ｓ１１）、テンプレートデータをその代表点を含むように局所領域に分割する（Ｓ１２）。予めまとまった形状要素ごとに領域分割されたテンプレートを使う場合には、この領域分割処理は、不要である。

代表点を含む局所領域で、以下に説明するような幾何学的変換パラメータの推定と変換を実行する（Ｓ１３）。本実施例では、所定の代表点の近傍領域について局所的な幾何学的変形（局所アフィン変換、局所双線形変換及び局所透視変換など）によりテンプレートを更新するが、ここでは、そのためのテンプレートの局所幾何学的変換パラメータを、曲線パラメータに関する確率過程のベイズの推定手法に基づき入力画像中の対象に最も適合するようなパラメータとして求める。

更に、必要に応じて輪郭モデル形状を微調整するために、上述の実施例と同様に、変換後の代表点間を結ぶ曲線セグメントを生成し（Ｓ１４）、第２の形状適合度を評価し（Ｓ１５）、テンプレート形状を変形し、更新する（Ｓ１６）。

この実施例で局所的な幾何学的変形と適合度評価を行う意義は、代表点間の相対的な位置関係（即ち、幾何学的位相及び凹又は凸形状など）を概ね保持しながら、局所的な領域において複数の代表点の位置を一括して所与の変形モードと合致するように変換することにより、抽出対象に適合する輪郭モデルの探索を効率化することにある。

アフィン変換、透視変換及び双線形変換はそれぞれ、下記式で与えられる。すなわち、

ｘ’＝ｘｗ’、ｙ’＝ｙｗ’、［ｕｖ］は変換前の座標、［ｘｙ］は変換後の座標、｛ａ_ｉｊ｝｛ａ_ｉ｝｛ｂ_ｉ｝及びｗは変換パラメータである。

近傍領域としては、複数の代表点を含む所定サイズの矩形領域とするか、又は、予めテンプレートを所定のブロックごとに分割しておき、変形を各ブロックごとに行なうようにしてもよい。例えば、人体を表わすテンプレートでは、頭部、胴部、胸部及び脚部などのように、意味のある形状ごとにブロック分割したものを近傍領域としてもよい。図１１は、人体の各部を予め分割しておき、元のデータ図１１（ａ）に対して各部に所定の幾何学的変換を行なった結果図１１（ｂ），（ｃ），（ｄ）を例示する。実際に用いる輪郭線データは、図１１の各図形の最外郭輪郭線であることはいうまでもない。

近傍領域内の各点（又は代表点）位置を上述の幾何学変換により移動することにより、テンプレートが変形される。アフィン変換を例に、最適な変換パラメータを求める手順を説明する。変換パラメータセット｛ａ_ｉｊ｝の事前確率をＰ（ａ）、画像データの事前確率をＰ（ｂ）、変換パラメータが与えられたときに、その変換によって得られるテンプレート図形要素が入力画像の特徴量と一致する事後確率をＰ（ｂ｜ａ）、画像の特徴量ｂが与えられたときに、それに対応するテンプレートの変換パラメータセットが｛ａ_ｉｊ｝である事後確率をＰ（ａ｜ｂ）、求めるべき変換パラメータを｛ａ_ｏｐｔ｝とする。｛ａ_ｏｐｔ｝は、ベイズの法則に従い、最大事後確率ｍａｘ［Ｐ（ａ｜ｂ）］を与えるパラメータとして下記式により与えられる。即ち、

上式の最右辺の対数をとり、またＰ（ｂ）が定数であることを考慮すると、結局、

となる。

次に、図１２を参照して、幾何学的（アフィン）変換パラメータの推定手順を具体的に説明する。幾何学的変換パラメータの事前確率分布Ｐ（ａ）及び変換によって得られるテンプレート図形要素が入力画像の特徴量と一致する事後確率Ｐ（ｂ｜ａ）を下記式に示すようにして求め（Ｓ２１）、それらを数１８の右辺に代入して最大事後確率評価関数を求める（Ｓ２２）。求めた関数の値が最大となるようなパラメータ｛ａ_ｏｐｔ｝を、連続勾配山登り法などによる最適化法により求める（Ｓ２３）。

テンプレートデータが線図形からなるものとし、ある代表点を含むテンプレートの図形要素を構成する局所線分（曲線要素）上の点の集合Ｎにおいて２値のテンプレートデータｔ（ｕ，ｖ）にアフィン変換｛ａ｝を行った結果の誤差がガウシアン分布となると仮定する。この仮定の下では、事後確率Ｐ（ｂ｜ａ）は下記式で与えられる。即ち、

ここで、σは分散、ａ（ｕ，ｖ）はアフィン変換により点（ｕ，ｖ）が移される座標、ｂは入力画像の２値のエッジマップ（エッジ強度分布を所定の閾値で２値化したもの）をそれぞれ示す。テンプレートデータが濃淡画像の場合、Ｎは当該代表点を含む局所領域又は予め分割された当該代表点を含む領域上の点の集合となり、ｂはエッジ強度分布を示す。

事前確率分布Ｐ（ａ）は、水平又は垂直方向への変倍、回転又はシフトを与える変形モードで高い値をとるものとし、

ここで、ｍ_ｉｊ，σ_ｉｊはそれぞれａ_ｉｊの平均及び分散を示し、

である。ｍｏｄｅ＝｛回転_１、回転_２、・・・、倍率_１、倍率_２、・・・、シフト_１、・・・、その他｝のように表わされ、各変形モードごとに、ｍ_ｉｊ及びσ_ｉｊのパラメータ値が与えられる。‘その他’のモードは、特定の名称が与えられない任意の変換モードである。

最適な変換パラメータは、数１９、数２０、数２１及び数２２を数１８に代入し、Ｖ_ｍｏｄｅ及び｛ａ_ｉｊ｝について連続勾配山登り法（ｃｏｎｔｉｎｕｏｕｓ ｇｒａｄｉｅｎｔ ａｓｃｅｎｔ）又はＰｏｗｅｌ法などを用いることにより求められる。以上は、最適な変換パラメータを求める手法の一例であり、他の最適化手法（ＥＭアルゴリズム、動的計画法及び遺伝的アルゴリズムなど）を用いてもよいことはいうまでもない。

上述した方法で求めた変換パラメータにより変換されたテンプレートデータを初期値として、更に第１の実施例に示した第２の形状適合度評価に基づく代表点の移動と代表点間を結ぶ曲線の生成処理を行ってもよい。

上述した方法により抽出対象の輪郭線（閉曲線）が求まったら、その閉曲線データを画像表示装置１４の画面上に表示し、必要があれば、閉曲線内部の領域データとしてマスクデータを生成し、その何れかを所定の記憶手段に記録する。

不定部分を一部に有する図形要素からなる可変形状テンプレートを用いてもよい。不定部分とは変形の自由度が大きい部分であり、変形に伴い新たなループ形状が発生しないこと、及び、不定部分に対応する形状が凹か凸かが予め分かっていることを拘束条件として、それ以外の特定の拘束条件が課されない部分をいう。

抽出対象として、例えば人物の胸部及び脚部のように関節を有する部分は、変形の自由度が他の部分に比べて大きいことが予め分かっているから、これらの部分を不定部分として予めテンプレートデータ上で定義しておく。

第１実施例と同様に、テンプレートの走査と適合度評価を実行し、抽出対象の位置と適切なテンプレートモデルを選択する。次に、テンプレートを構成する図形要素の変形と形状適合度評価によるテンプレート更新を実行する。その際に、先ず、不定部分を除いた部分で第１実施例又は第２実施例に示した方法によりテンプレートを変形し、その後、不定部分の輪郭線を推定する。

不定部分の輪郭線を推定する方法として２つの方法を説明する。第１の方法では、不定部分の一方の端点を始点とし、他方を終点とする輪郭追跡を不定部分ごとに実行する。その結果得られる不定部分の輪郭線を近似する曲線を生成してもよい。図１３（ａ），（ｂ）は、第１の方法による不定部分の輪郭形状抽出過程の一例を示す。

第２の方法では、図１３（ｃ）に示すように、不定部分の両端点を結ぶ線分を直径とするプローブ円をその不定部分の形状が凸なら外側に、凹なら内側方向に移動させながら、各場所でその円の半径と位置を微少量ずつ変化させて、抽出対象の輪郭がその円と２箇所（ｐ_ｊ，ｑ_ｊ）で接するような円の位置と半径を求める。これにより、順次、輪郭線の座標を確定していく。この方法は、分岐のない形状の輪郭線を抽出するのに適している。この方法で概略の形状を抽出してから、抽出された部分を初輪郭モデルとして用い、第１実施例又は第２実施例で説明した手法で細部の形状を抽出してもよい。

図１４は、第３実施例におけるテンプレート更新処理のフローチャートを示す。図１４に示す処理は、図５のＳ７に相当する。

先ず、端点を有する曲線セグメントペアを選択し（Ｓ３１）、不定部分以外のテンプレート図形要素の形状を先の実施例で説明した方法により更新する（Ｓ３２）。次に、更新後の隣接する図形要素の相対する端点から始点及び終点を設定し（Ｓ３３）、上述した方法、即ち始点及び終点間を結ぶ輪郭追跡（第１の方法）、又はプローブ円による輪郭位置確定（第２の方法）を実行する（Ｓ３４）。以上の処理を全ての端点がなくなるまで繰り返し（Ｓ３５）、テンプレートの図形要素により１つの閉曲線が形成されたら（Ｓ３５）、更新後のテンプレートデータとして出力する（Ｓ３６）。

このような構成では、特定部分について形状の不確定性（自由度）が高いことが予め分かっている抽出対象の輪郭を安定して抽出することが出来る。すなわち、与えられたテンプレートの形状とは大きく異なる部分を有する対象が画像中に存在しても、その異なる部分の輪郭について残りの確定した部分形状のギャップを補完するような最も確からしい曲線（例えば、端点での形状連続性又は画像特徴量の連続性の条件を満たすものとして輪郭追跡により求まる曲線）として求めることができる。

第４の実施例として、テンプレート更新処理（図５のＳ７）に相当する処理として、代表点間を通るテンプレートを構成する図形要素の曲線（又は線分）に沿った（又はその曲線を中心線とする）所定幅の太線を図１５に示すように生成し、太線の両側の特徴量（色成分値及び局所空間周波数代表値など）に基づき太線内部の境界位置を推定するようにしてもよい。この場合、テンプレート更新処理の前には、先の実施例と同様の処理が施される。

具体的には、図１５に示すように太線化した領域の輪郭線１又は輪郭線２の少なくとも一方の上に、領域成長のための核を設定する。領域成長処理では、その核での画像特徴量の差が所定の閾値より小さい核の近傍領域を核に併合し、その結果得られる輪郭線１からの成長結果と輪郭線２からの成長結果を統合する。又は、いずれかの輪郭線からの成長結果に基づいて１つの境界線を推定する。

境界位置は例えば、太線の方向に略直交するライン上での特徴量の最大エッジ強度位置として、又は、太線の両側の所定サンプリング点からの特徴量（例えば、色成分）の類似度に基づく領域成長による境界位置などとして決定される。

本実施例では、最終的に抽出される輪郭線は必ずしもパラメトリックな曲線で表現されなくても良い。

１０：画像入力装置
１２：画像記憶装置
１４：画像表示装置
１６：画像処理装置
１８：指示選択装置
２０：特徴量抽出装置
２２：テンプレートモデル選択装置
２４：テンプレートデータ生成装置
２６：テンプレート走査装置
２８：移動範囲・条件更新設定装置
３０：更新テンプレート生成装置
３２：形状適合度評価装置
３４：境界線生成装置
３６：境界線表示装置
３８：マスクデータ生成装置
４０：画像表示装置１４の画面
４２：入力画像
４４：テンプレートモデル画像データ
４６：目標位置確認インディケータ
４８：抽出指示ボタン
５０：テンプレートスクロールボタン

Claims (2)

1. 第１のマッチング手段が入力画像と局所的な図形要素を含むテンプレートとの所定の特徴量の値に関する所定の評価関数値を求める第１のマッチング処理を行う第１のマッチングステップと、
   局所変換手段が前記テンプレート上の所定の代表点の近傍領域について局所的な幾何学的変換を行う局所変換ステップと、
   変換パラメータ算出手段が前記局所変換ステップの変換パラメータを前記第１のマッチング処理結果、および、所定の変形モードまたは確率分布の少なくとも一方、に基づいて求める変換パラメータ算出ステップと、
   第２のマッチング手段が前記局所変換ステップにより得られるテンプレートと前記入力画像との第２のマッチング処理を行う第２のマッチングステップと、
   画像領域抽出手段が前記第２のマッチング処理の結果に基づき前記輪郭線を含む画像領域を抽出する画像領域抽出ステップ
   とを具備することを特徴とする画像抽出方法。
2. 入力画像と局所的な図形要素を含むテンプレートとの所定の特徴量の値に関する所定の評価関数値を求める第１のマッチング処理を行う第１のマッチング手段と、
   前記テンプレート上の所定の代表点の近傍領域について局所的な幾何学的変換を行う局所変換手段と、
   前記局所変換手段の変換パラメータを前記第１のマッチング処理結果、および、所定の変形モードまたは確率分布の少なくとも一方、に基づいて求める変換パラメータ算出手段と、
   前記局所変換手段により得られるテンプレートと前記入力画像との第２のマッチング処理を行う第２のマッチング手段と、
   前記第２のマッチング処理の結果に基づき前記輪郭線を含む画像領域を抽出する画像領域抽出手段
   とを具備することを特徴とする画像抽出装置。

Images