(57)【特許請求の範囲】
【請求項１】
画像に含まれる特定の対象の輪郭を、初期形状を有し所定の変形の傾向にしたがって変形を繰り返す動的曲線が該変形を繰り返して収束することにより抽出する動的輪郭抽出方法において、
前記動的曲線を形成する複数の節点の各節点ごとに前記変形の傾向の要素となる該節点の移動の方向および移動量を表すベクトルとして、該節点と該節点の両隣の節点とを結ぶ直線により構成される内角が大きくなる傾向に対応する平滑化ベクトルと、前記動的曲線を形成する節点間の距離が均等になる傾向に対応する均等化ベクトルと、前記動的曲線が収縮する傾向に対応する圧力ベクトルと、前記動的曲線を形成する各節点が画像の濃度勾配がより高い位置へと移動する傾向に対応する濃度勾配ベクトルとを含む複数のベクトルを定義し、
前記複数のベクトルのそれぞれに対して所望の変形の傾向に対応する重みづけをすることにより前記所定の変形の傾向を決定し、
前記重みづけがされた複数のベクトルに釣り合いが生じた状態を収束状態と定義し、
該決定された変形の傾向にしたがって前記動的曲線を変形せしめ、
前記各節点が前記収束状態に達した時点をもって、前記輪郭を抽出したこととする動的輪郭抽出方法。
【請求項２】
画像に含まれる特定の対象の輪郭を、初期形状を有し所定の変形の傾向にしたがって変形を繰り返す動的曲線が該変形を繰り返して収束することにより抽出する動的輪郭抽出方法において、
前記動的曲線を形成する複数の節点の各節点ごとに前記変形の傾向の要素となる該節点の移動の方向および移動量を表すベクトルとして、該節点と該節点の両隣の節点とを結ぶ直線により構成される内角が大きくなる傾向に対応する平滑化ベクトルと、前記動的曲線を形成する節点間の距離が均等になる傾向に対応する均等化ベクトルと、前記動的曲線が膨張する傾向に対応する圧力ベクトルと、前記動的曲線を形成する各節点が画像の濃度勾配がより高い位置へと移動する傾向に対応する濃度勾配ベクトルとを含む複数のベクトルを定義し、
前記複数のベクトルのそれぞれに対して所望の変形の傾向に対応する重みづけをすることにより前記所定の変形の傾向を決定し、
前記重みづけがされた複数のベクトルに釣り合いが生じた状態を収束状態と定義し、
該決定された変形の傾向にしたがって前記動的曲線を変形せしめ、
前記各節点が前記収束状態に達した時点をもって、前記輪郭を抽出したこととする動的輪郭抽出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、動的輪郭抽出方法、すなわち画像中の特定の対象の輪郭を所定の変形の傾向にしたがって変形を繰り返す曲線により抽出する方法に関する。
【０００２】
【従来の技術】
画像に含まれる特定の対象の輪郭を抽出する方法の１つとして、動的輪郭抽出方法が知られている。動的輪郭抽出方法は、抽出する輪郭のモデルとして、所定の変形の傾向にしたがって変形を繰り返す曲線（以下、これを「動的曲線」という）を仮定して、その輪郭のモデルが対象の輪郭に近づくように、すなわち動的曲線が変形を繰り返して最終的にその対象の輪郭に収束するように変形の傾向を定めることにより、対象の輪郭を抽出するものである。
【０００３】
この動的輪郭抽出方法としてよく知られているSNAKESモデル（M.Kass, A.Witkin, D.Terzopoulos; "SNAKES: ACTIVE CONTOUR MODELS" International Journal of Computer Vision, Vol.1, No.4, pp.321-331, 1988）は、動的曲線のエネルギーを定義することにより、その曲線の状態を定量的に評価して変形の傾向を定めようとするものである。このエネルギーは、動的曲線が対象の輪郭に一致した場合に最小となるように定義され、これにより、動的曲線の持つエネルギーが最小となる安定状態を見つけることによって対象の輪郭を抽出することが可能となる。この際、輪郭抽出処理の速度および正確さは、変形の傾向の定め方に依存する。
【０００４】
このSNAKESモデルの問題点としては、計算量が膨大なため高速処理が期待できないこと、また変形の傾向の調整が困難であることが指摘されており、従来より、これらの問題を解決した数々の改良、例えば、動的計画法（Amani A.A., Weymouth T.E, Jain R.C "Using Dynamic Programming for Solving Variational Problems in Vision" IEEE Trans., PAMI-12, pp.855-867, 1990）、グリーディアルゴリズム（D.J.Wiliams, M.Shah "A Fast Algorithm for Active Contour and Curvature Estimation", CVGIP: Image Understanding, Vol.55, No1, Jan. pp14-26, 1992）、多重スケールを用いる方法（藤村, 横矢, 山本 "多重スケールを用いた非剛体物体の動的輪郭追跡", コンピュータビジョン, 78-4 pp25-32, 1992）、外部から圧力を加える方法（坂口他, "圧力エネルギーを持つSNAKES", 1990信学春期全大, D-523）、膨張モデルへの改良（L.D.Cohen: "On Active Contour Models and Balloons", CVGIP: Image Understanding Vol.53, No.2, March.pp211-218, 1991）などが提案されている。
【０００５】
【発明が解決しようとする課題】
しかしながら、上記提案された数々の方法は、あくまでもSNAKESモデルの改良にすぎず、変形の傾向の決定をエネルギーの最小値問題として処理することには変わりはない。そのため、多少の効果は得られるものの、十分な解決には至っておらず、例えば処理速度の面で最も効果的といわれている上記グリーディアルゴリズムをもってしても、処理時間は、数百msecから数秒、場合によっては分のオーダーとなってしまう。これは、例えば動画像において対象を追跡するために輪郭抽出を行う場合、あるいは画像中の複数の対象に対して複数の動的曲線を用いて並列に輪郭抽出を行う場合などを考えると、実用レベルに達しているとは言い難い。
【０００６】
本発明は、上記問題に鑑みて、変形の傾向をSNAKESモデルとは全く異なる方法によって決定することにより、計算機による高速処理が可能で、かつその変形の傾向の決定に関する自由度の高い動的輪郭抽出方法を提供することを目的とする。
【０００７】
【課題を解決するための手段】
本発明は、画像に含まれる特定の対象の輪郭を、初期形状を有し所定の変形の傾向にしたがって変形を繰り返す動的曲線が該変形を繰り返して収束することにより抽出する動的輪郭抽出方法において、前記動的曲線を形成する複数の節点の各節点ごとに前記変形の傾向の要素となる該節点の移動の方向および移動量を表すベクトルを定義し、該ベクトルに所望の変形の傾向に対応する重みづけをすることにより前記所定の変形の傾向を決定し、該重みづけされたベクトルにより決定された変形の傾向にしたがって該各節点を移動させて前記動的曲線を変形せしめることにより前記変形を行うことを特徴とするものである。前記ベクトルは、前記変形の各種傾向ごとに複数定義し、該複数のベクトルのそれぞれに対して前記重みづけをして前記所定の変形の傾向を決定してもよい。
【０００８】
具体的には、前記複数のベクトルには、前記動的曲線が滑らかになる傾向に対応する平滑化ベクトルと、前記動的曲線を形成する節点配列が均等になる傾向に対応する均等化ベクトルと、前記動的曲線が収縮する傾向に対応する圧力ベクトルと、前記動的曲線を形成する各節点が画像の濃度勾配がより高い位置へと移動する傾向に対応する濃度勾配ベクトルが含まれていることが望ましい。但し、前記動的曲線が収縮する傾向に対応する圧力ベクトルは、動的曲線が膨張する傾向に対応する圧力ベクトルであってもよい。このようにベクトルを定義すると、動的曲線が対象の輪郭近傍に到達した場合に前記複数のベクトルにつり合いが生じ、動的曲線の移動量が小さくなるか、または振動状態になる。このような状態を収束状態とし、この収束状態をもって対象の輪郭を抽出したこととする。
【０００９】
ここで、上記「動的曲線を形成する複数の節点」とは、動的曲線上の任意の点を意味するものである。すなわち、動的曲線は理論上は連続的な曲線であるが、動的輪郭抽出を計算機を用いて実施する場合、この動的曲線は、離散的な点の集合として扱わざるを得ない。このため、本明細書においては、動的曲線をこの離散的な点を結ぶことにより得られる曲線とみなし、この各点について、動的曲線を形成する複数の節点という表現を用いることとする。
【００１０】
また、上記「変形の傾向」とは、例えば動的曲線が収縮する傾向とか、滑らかに丸みをおびた形状になる傾向などを意味する。したがって、上記「変形の傾向の要素となる該節点の移動の方向および移動量を表す」とは、ある節点が、もしその方向にその移動量分だけ移動したとしたら、それにより動的閉曲線全体の変形の傾向が変わってしまうような方向および移動量を表すという意味である。例えば、ある節点を両隣の節点の中間点に移動したとすれば、その変形の傾向は節点が均等配置になるような傾向となる。この場合、その中間点と、節点の元の位置との相対関係に基づいて、上記「変形の傾向の要素となる該節点の移動の方向および移動量を表すベクトル」が定義される。
【００１１】
したがって、上記「ベクトルに所望の変形の傾向に対応する重みづけをする」とは、例えば、ベクトルの大きさに１以下の係数をかけることとした場合、重みづけが１の時に、均等配置になる傾向が最も強くなり、重みづけが１より小さくなれば、その大きさに応じてその傾向も弱まることとなる。
【００１２】
【発明の効果】
本発明の動的輪郭抽出方法によれば、輪郭抽出処理の速度および正確さを決定する動的曲線の変形の傾向は、ベクトルとして視覚的に表現されるため、動的曲線を形成する各節点の移動方向を一意に決定することができ、抽出処理に要する時間を飛躍的に短縮することができる。
【００１３】
また、本発明の動的輪郭抽出方法によれば、上記ベクトルを変形の各種傾向ごとに複数定義することにより、それぞれの変形の傾向を独立して決定することができるため、変形の傾向を所望どおりに決定することができる。
【００１４】
また、本発明の動的輪郭抽出方法によれば、動的曲線が滑らかになる傾向に対応する平滑化ベクトルと、動的曲線を形成する節点配列が均等になる傾向に対応する均等化ベクトルと、動的曲線が収縮する傾向に対応する圧力ベクトルと、動的曲線を形成する各節点が画像の濃度勾配がより高い位置へと移動する傾向に対応する濃度勾配ベクトルに、それぞれ重みづけをして変形の傾向を決定することにより、動的曲線をきめ細かに調整しながら輪郭に収束せしめることができる。
【００１５】
また、一般に対象の内部は、対象の外部に比べて不必要な情報が少ないため、上記動的曲線が収縮する傾向に対応する圧力ベクトルの代わりに、動的曲線が膨張する傾向に対応する圧力ベクトルを用いて変形の傾向を決定するようにすれば、より正確な輪郭抽出が期待できる。
【００１６】
【従来技術の詳細な説明】
以下、本発明の動的輪郭抽出方法について詳細に説明する前に、本発明と従来技術との相違点をより明確にするために、上記SNAKESモデルについて説明する。
【００１７】
SNAKESモデルは、動的曲線のエネルギーを定義することによりその曲線の状態を定量的に評価するものである。このエネルギーは、動的曲線が対象の輪郭に一致した場合に最も小さくなるように定義されるものであり、これにより、動的曲線の持つエネルギーが最小となる安定状態を見つけることによって対象の輪郭を抽出することが可能となる。このエネルギーは、動的曲線の状態に対応して定義される複数のエネルギーの総和として定義される。動的曲線の状態に対応して定義されるエネルギーとは、例えば、動的曲線自体の性質に基づいて定義されるエネルギーや、動的曲線が外部から受ける制約に基づいて定義されるエネルギーなどをいう。
【００１８】
動的曲線の持つエネルギーEsnakeは、一般に、動的曲線上の点を動的曲線上の所定の点からの曲線に沿った距離に対応する媒介変数sを用いて
v(s)＝(x(s),y(s))
のように表記するものとして、次のような式で記述される。
【００１９】
【数１】
0003850076.tif 000002
【００２０】
内部エネルギーEintは、動的曲線自体の性質を評価するものである。従来、この性質は「滑らかさ」として評価されており、内部エネルギーはスプラインエネルギーとも呼ばれている。内部エネルギーは、動的曲線が滑らかであるほど小さい値となるように規定されるものであるため、この内部エネルギーが小さくなるように変形を行えば、動的曲線はより滑らかになる。内部エネルギーは、次のような式で記述される。
【００２１】
0003850076.tif 000003
画像エネルギーEimageは動的曲線が画像から受ける影響を評価するものであり、従来から「濃度勾配」が利用されている。これは、輪郭付近は他の部分に比べて濃度勾配が急であることに着目したものである。画像エネルギーは、濃度勾配が急なところほど小さくなるように規定されており、これにより、動的曲線は変形とともに輪郭に引き寄せられることとなる。画像エネルギーは、次のような式で記述される。
【００２２】
0003850076.tif 000004
外部エネルギーＥextは、人の手により意図的に与えられる制約を評価するものであり、一般には各画像に特化したポテンシャル場などが用いられている。外部エネルギーは、上記２つのエネルギーと同様、エネルギーが小さくなるように動的曲線を変形すれば輪郭に近づくように規定されるものであるが、設計事項として任意に規定し得るものであり、汎用性を欠くため、本発明の説明においては、外部エネルギーは無視（Eext＝0と仮定）するものとする。
【００２３】
以上、SNAKESモデルの概要を説明したが、このSNAKESモデルは、上記従来技術の問題点においても述べたように、実際に実現しようとすると２つの問題点がある。以下、その問題点および従来の解決策について説明する。
【００２４】
１つ目の問題点は、計算量が膨大であるということである。SNAKESモデルによる輪郭抽出を計算機によって実現する場合、上記連続した動的曲線はその動的曲線を形成する離散的な節点の集合として扱われる。したがって、エネルギーが小さくなるように動的曲線を変形する処理とは、各節点にそれぞれ着目し、エネルギー計算に基づいて節点の移動方向を決定し、その方向に節点を移動する処理に他ならない。
【００２５】
この際、各節点は、その節点におけるエネルギーEsnake(v(s))がより小さくなる方向へと移動する。この移動すべき方向は、その節点の近傍にある複数の点（x'i,y'i）についてその節点をその点に移動した場合のエネルギーEsnake(x'i,y'i)をそれぞれ求め、その中から求められたエネルギーが最小となるi=kを求めて移動先（x'k,y'k)を探すことにより決定される。計算機により節点vi(＝(xi,yi))のエネルギーを求める際には、そのとなりの節点をvi+h(＝(xi+h,yi+h))として、上記式の各項を以下のような有限差分で近似することが多い。
【００２６】
xs(s)＝(xi+h−xi)／h          …  (4)
ys(s)＝(yi+h−yi)／h          …  (5)
xss(s)＝(xi+h−2xi＋xi-h)／h2 …  (6)
yss(s)＝(yi+h−2yi＋yi-h)／h2 …  (7)
|vs|2＝xs2＋ys2               …  (8)
|vss|2＝xss2＋yss2            …  (9)
grad2I(x,y)＝Max|I(xi+j,yi+j)−I(xi,yi)|2  (j=-1,0,+1)  …  (10)
しかし、このような近似により計算処理を簡略化するとしても、１つの節点の移動方向を決定するために、その節点が動き得る全ての方向にある近傍点について上記エネルギーを求める計算を行って、さらにそのような計算を動的曲線上の全ての節点について行わなければならない。抽出の正確さを考えれば節点数を少なくしたり、動き得る方向を限定することは好ましくなく、SNAKESモデルによる動的輪郭抽出方法において高速な処理が期待できないことは明らかである。
【００２７】
この問題の解決策として提案されている、上記動的計画法、あるいはグリーディアルゴリズムなどは、節点が動き得る全ての方向にある近傍点について計算を行うかわりに、計算を行う点を所定のアルゴリズムに基づいてある程度限定することによって、計算効率の向上を図るものである。しかしながら、上記のように、これらの改良による効果は、実用上望まれている処理速度には及んでいない。
【００２８】
SNAKESモデルのもう１つの問題点は、動的曲線の変形の傾向の調整が難しいことである。SNAKESモデルのエネルギーの定義は、上記のように動的曲線が変形の繰り返しにより対象の輪郭に収束するように定義されるものであるが、この定義式には重みづけパラメータが含まれており、必ずしも一意に定義されるものではない。一般に抽出の速さや正確さは、抽出しようとする対象の輪郭によっても変わるものであり、ある対象の輪郭に対して適切な抽出が行われたとしても、同じ定義式で別の対象の輪郭に対しても適切な抽出が行われるとは限らない。例えば、円形の対象を抽出するためには、変形の傾向として滑らかさを最重視し、動的曲線がより滑らかになるように変形を繰り返すことにより適切な抽出を行うことができるが、四角形の抽出において同様の変形の傾向による変形を行っても四角形の角の部分が適切に抽出できないことが予想される。すなわち、動的曲線の変形の傾向は抽出する対象の輪郭によって異なることが望まれており、そのための調整は上記定義式の重みづけパラメータを変更することにより行われている。しかしながら、この重みづけパラメータは、調整したい変形の傾向とは必ずしも一致しておらず、所望の変形の傾向となるように調整を行うことは非常に難しかった。
【００２９】
ここで、この調整の困難さの問題をより明らかにするために、内部エネルギーの定義式の各項の意味について説明する。内部エネルギーの定義式(2)の１次微分項|vs(s)|2は、式(4)、(5)および(8)により、節点間の距離の２乗として定義されていることがわかる。したがって、この１次微分項は、その節点が右隣または左隣（定義による）の節点に近いほど小さい値となる。すなわち、この１次微分項が小さくなるように節点を移動するということは、動的閉曲線が回転しながら収縮することを意味し、この１次微分項の重みづけパラメータwsp1大きくすることにより、この回転しながら収縮する変形の傾向を強くすることができる。
【００３０】
定義式(2)の２次微分項|vss(s)|2は、式(6)、(7)および(9)により、節点間の距離および位置関係として定義されていることがわかる。したがって、この２次微分項は、その節点と両隣の節点とを結んだ線が直線に近いほど、またその節点と両隣の節点が均等に配置されているほど小さい値となる。すなわち、この２次微分項が小さくなるように節点を移動するということは、動的閉曲線が滑らかになりながら収縮することを意味し、この２次微分項の重みづけパラメータwsp2を大きくすることにより、この傾向を強くすることができる。
【００３１】
なお、上記のように、SNAKESモデルの内部エネルギーの各項は、動的曲線が収縮する意味を持つ。このため、動的曲線は抽出する対象を取り囲むようなものであることが前提であり、変形の傾向は、収縮しながらの収束となる。
【００３２】
動的曲線を対象に適切に収束させるためには、上記１次および２次微分項を適当に調整する、すなわちこれらの項の重みづけパラメータであるwsp1およびwsp2の値を調整する必要がある。ところが、これらの項は、上記のように複数の意味を持っており、ある１つの傾向のみを強くしたいと思っても、他の傾向も同時に強まってしまうという不都合が生じる。例えば、細かい凹凸でも抽出できるように滑らかさの傾向を抑えようとすれば、２次微分項に対して１次微分項の影響を強くしなければならないが、この場合、節点がいくつかの場所に局所的に集まってしまうという問題が生ずる。逆に、節点の局所化を防止するために２次微分項の影響を強くすると、動的曲線は丸みをおびたものとなってしまい、複雑な形状のものは抽出できなくなる。
【００３３】
このような、調整の難しさは、内部エネルギーと画像エネルギーの関係においても問題となる。すなわち、画像エネルギーの重みづけを大きくすれば、より正確に対象の輪郭を抽出することができるが、同時にノイズなどの影響を受けやすくなり、その上、内部エネルギーによる収縮機能の働きが弱まる分、収縮しにくくなるという問題が生じる。さらに、内部エネルギーが動的曲線が収縮するほど小さくなるものであるのに対し、画像エネルギーは収縮の程度とは無関係であるため、重みづけパラメータを一定の値に設定して抽出処理を行っても、動的曲線の変形が進行するにつれて、内部エネルギーと画像エネルギーのバランスは大きく変化する。これを、常に適度なバランスを保つように調整することは難しく、特に変形の進行にあわせて同時にバランス調整も行うことは非常に困難である。
【００３４】
この問題については、例えば、上記外部から圧力を加える方法などが提案されている。この方法は、SNAKESモデルのエネルギーの１つとして新たに、動的曲線の状態にかかわらず常に収縮する傾向に対応する圧力エネルギーを定義し、収縮の傾向を調整しやすくしようとするものである。これにより、例えば内部エネルギーを滑らかさの傾向に着目して調整した結果、収縮の傾向が弱まってしまい、変形が途中でとまってしまうといったことはなくなり、常に一定の収縮の傾向で変形が続けられる。しかしながら、この方法は、このようなケース、すなわち収縮の傾向の調整に限られた効果であり、全ての面において調整を容易にするものではない。同様に他の方法も、断片的には効果が得られるが、上記問題の根本的な解決には至っていない。
【００３５】
【発明の実施の形態】
以上、SNAKESモデルの問題点について説明したが、次に、本発明の動的輪郭抽出方法について、具体的実施の形態に基づいて詳細に説明する。以下に説明する実施の形態は、動的曲線を形成する各節点に対して４つのベクトルを定義し、これらのベクトルの合成によりその節点の移動方向を決定するものであるが（以下、ベクトルモデルという）、本発明の効果を明らかにするために、これらのベクトルとして従来のSNAKESモデルの各種エネルギーに対応する４種類のベクトルを定義するものとする。但し、これらのベクトルは、変形の傾向を調整することが可能であり、その調整された傾向にしたがって変形を繰り返した動的曲線が輪郭に収束するようなものであれば、どのような種類のベクトルでもよく、本実施の形態における定義はほんの一例にすぎない。
【００３６】
本実施の形態における４種類のベクトルとは、動的曲線が滑らかになる傾向に対応する平滑化ベクトル、動的曲線を形成する節点配列が均等になる傾向に対応する均等化ベクトル、動的曲線が膨張する傾向に対応する圧力ベクトル、および動的曲線を形成する各節点が画像の濃度勾配がより高い位置へと移動する傾向に対応する濃度勾配ベクトルである、これらのベクトルは動的曲線を形成する各節点においてそれぞれ定義され、その節点の移動方向は、これらのベクトルをそれぞれ重みづけして合成することにより決定される。
【００３７】
このようにベクトルを定義すると、動的曲線が対象の輪郭近傍に到達した際に、画像勾配ベクトルの効果によって前記４つのベクトルに釣り合いが起こり、動的曲線は、移動量が小さくなったり、もしくは振動状態になる。本実施の形態では、このような状態になった時点を収束と定義し、この状態をもって対象の輪郭を抽出することとする。
【００３８】
図１は本実施の形態におけるこれらのベクトルの定義を示したものであり、対象の輪郭１に対しその輪郭１の内側に初期形状を有する動的曲線２を輪郭モデルとして仮定した場合の、動的曲線２を形成する節点の１つである節点viにおける均等化ベクトルSP1、平滑化ベクトルSP2および圧力ベクトルPRの定義が示されている。濃度勾配ベクトルINは、画像の濃度勾配に依存して定義されるものであるため、図示しないものとする。この際、本実施の形態と同種のベクトルに対して異なる定義をすることは、当然可能であり、以下に説明する定義は各ベクトルの定義を限定するものではない。なお、図１においては、節点viの両隣の節点を節点vi-1、節点vi+1とし、これら両隣の節点の中点をＭとし、これら両隣の節点を結ぶ直線とその直線に対し節点viから垂直におろした線との交点をＭ’とし、節点viから同直線に対して平行に引いた線と前記中点Ｍから同直線に対して垂直に引いた線との交点をＮとし、また前記３つの節点vi-1、vi、およびvi+1により形成される三角形の各内角をそれぞれα、β、γとして表している。
【００３９】
本実施の形態において、均等化ベクトルSP1、平滑化ベクトルSP2、圧力ベクトルPRおよび濃度勾配ベクトルINは、それぞれ以下の式
0003850076.tif 000005
により定義される。ここで、単位ベクトルnsp1の方向はviからNに向かう方向、単位ベクトルnsp2の方向はviからM'に向かう方向、単位ベクトルnprの方向はvi-1とvi+1を結ぶ線に対して垂直かつ動的曲線２を膨張させる外向き方向（但し、圧力ベクトルを動的曲線を収縮させるものとして定義した場合には垂直内向き方向）であり、図１に示される均等化ベクトルSP1、平滑化ベクトルSP2、圧力ベクトルPRの矢印の向きにそれぞれ対応する。但し、単位ベクトルnsp1は、viとNが一致するような場合に０となり、単位ベクトルnsp2は、viとM'が一致するような場合に０となる。ngradについては節点viとその近傍画素との濃度差分が最大の方向とする。濃度差分最大の方向は、節点の移動方向の決定の際に求めてもよいが、動的曲線の状態とは無関係に定まるものであるため、処理の効率から考えれば、予め画像の各画素点においてその方向を求めておくことが望ましい。
【００４０】
上記式からわかるように、vi-N間距離とvi+1-vi-1間距離との比が大きいほど、すなわち均等化ベクトルSP1は動的曲線の状態が均等でないほど、ベクトルの大きさが大きくなり、均等化しようとする傾向が強くなる。また平滑化ベクトルSP2は内角βが小さいほど、つまり角張っているほど、ベクトルの大きさが大きくなり、平滑化しようとする傾向が強くなる。これら２つのベクトルが動的曲線の状態に応じて大きさが変わるものであるのに対し、圧力ベクトルおよび濃度勾配ベクトルは、動的曲線の状態に関わらず一定の大きさを有する。これにより、均等化ベクトルおよび平滑化ベクトルの大きさが０となる場合でも、動的曲線は一定の変形の傾向を保つことができる。
【００４１】
以上の処理を計算量という観点からみると、本発明の動的輪郭抽出方法において必要とされる計算は、各節点の位置から、上記４つのベクトルの方向および大きさを求める計算と、ベクトル合成のための計算のみであることがわかる。これは、従来のSNAKESモデルおよびそれを改良したモデルにおいて行われていた計算と比べると、非常に簡単な計算であり、また計算量も非常に少ないことは明らかである。実際に、汎用ワークステーションを用いて、同じ対象について、本発明の動的輪郭抽出方法と、従来の方法の中で最も高速であると言われているグリーディアルゴリズムを用いた方法による輪郭抽出を行ったところ、対象や動的曲線の初期形状により効果は多少異なるものの、最高で1/10程度まで計算時間が短縮されることがわかった。動的輪郭抽出処理はその処理速度が遅いために、従来、高速処理が必要とされる動画中の対象の輪郭抽出などには処理速度上のブレイクスルーが必要であるとされていたが、本発明は、このような動的輪郭抽出処理を実用レベルに到達せしめるものであり、これにより動的輪郭抽出方法の適用範囲を大幅に拡大するものである。
【００４２】
次に、上記処理の変形の傾向の調整のしやすさについて説明する。本実施の形態では、各ベクトルがそれぞれ所望の傾向に対応しており、その各ベクトルごとに重みづけパラメータを独立して決定することができるため、変形の傾向の細かい調整が可能である。例えば、動的曲線を角度90度の角に対して収束させる場合について考える。図１の節点viが、βが９０度より大きければ膨張する方向に移動し、小さければ収縮する方向に移動するような傾向であればよいことは、図から容易に理解される。これをベクトルに基づいて分析すると、βが９０度となったときに圧力ベクトルと平滑化ベクトルの大きさが等しくなって平衡状態となればよいことがわかる。したがって、例えば圧力ベクトルの重みづけパラメータwprが１の場合、上記(12)式および(13)式により、
|wsp2×(1-β/π)|＝1
が求められる条件であり、これによりwsp2＝2とすれば、動的曲線の変形の傾向は、上記所望のとおりの傾向となる。この例のように、本発明では、エネルギー値ではなくベクトルとして必要な条件を考えることができるため、所望通りの傾向とするための重みづけパラメータを、試行錯誤ではなく視覚的に求めることができる。
【００４３】
以上、本発明の動的輪郭抽出方法について説明してきたが、最後に従来のSNAKESモデルと、本発明のベクトルモデルでそれぞれ輪郭抽出を行った様子を図面を参照して具体的に示す。
【００４４】
図２は従来のSNAKESモデル（エネルギーモデル）、図３は本発明のベクトルモデルによる輪郭抽出の様子を示したものである。これによれば、円形および四角形については、抽出のレベルとしてはほぼ同等であるが、節点のばらつきかたをみるとベクトルモデルが優れていることがわかる。また多角形の鋭角の部分においては、明らかな差が見られる。なお、処理時間については、図中の多角形の場合で、ベクトルモデルによる処理時間が、エネルギーモデルによる処理時間の約1/10となっている。
【００４５】
さらに、輪郭が途切れている形状の抽出について同様に比較したものが図４（エネルギーモデル）と図５（ベクトルモデル）である。これらの図によれば、ベクトルモデルでは、どのような重みづけパラメータを設定した場合においても、輪郭が途切れている部分で動的曲線は収束しており、また、その部分はある程度補間されている。これに対し従来モデルでは、発散してしまったり、パラメータによってはほとんど変形しない場合もあることがわかる。発散してしまった場合、図４では節点は画像の端点に収束しているが、画像サイズが大きい場合はこのような端点がないため、さらに発散してしまうこととなる。また、輪郭に収束している部分だけを比べても、ベクトルモデルでは節点は均等に配置されているが、従来モデルでは大きくばらついていることがわかる。
【００４６】
このように、処理速度および調整のしやすさのみならず、抽出の精度の面においても本発明のベクトルモデルは優れている。このように本発明は、動的輪郭抽出方法を広く実用レベルに到達せしめるものであり、実用上の効果は極めて大きい。
【図面の簡単な説明】
【図１】本発明の動的輪郭抽出方法の概要を示す図
【図２】エネルギーモデルの輪郭抽出の効果を示す図
【図３】ベクトルモデルの輪郭抽出の効果を図２と比較して示す図
【図４】輪郭が途切れた形状に対するエネルギーモデルの効果を示す図
【図５】ベクトルモデルの輪郭抽出の効果を図４と比較して示す図
【符号の説明】
１    対象の輪郭
２    動的曲線
ｖ    動的曲線を形成する節点
SP1   均等化ベクトル
SP2   平滑化ベクトル
PR    圧力ベクトル
【図１】
0003850076.tif 000006
【図２】
0003850076.tif 000007
【図３】
0003850076.tif 000008
【図４】
0003850076.tif 000009
【図５】
0003850076.tif 000010