(57)【特許請求の範囲】
【請求項１】
経路探査を利用して画像中から対象物の輪郭を抽出する輪郭抽出装置において、
上記対象物の輪郭が存在すると考えられる輪郭候補領域において当該輪郭に沿つた複数の点を中継点として抽出し、当該中継点に対して当該輪郭に沿つた順序付けを行う中継点抽出手段と、
局所的な経路毎に設定された通過コストの総和を表す評価関数が最小となるよう、上記順序が連続する上記中継点間の最短経路を決定することにより上記中継点同士を結ぶ経路を探査し、当該経路を順次連結することにより上記輪郭を表す線図形を生成する中継点連結手段と、
上記線図形によつて表される形状を近似する曲線を生成する曲線生成手段と
を具え、
上記中継点抽出手段は、上記輪郭候補領域において検出した複数のエツジ点のうち、エツジ強度が所定のしきい値よりも大きい上記エツジ点を上記中継点として抽出する強エツジ点抽出手段を具える
ことを特徴とする輪郭抽出装置。
【請求項２】
上記中継点抽出手段は、
上記画像からエツジ強度を算出して出力するエツジ強度算出手段と、
上記画像からエツジ点を検出し、当該エツジ点の位置を指定するエツジ点２値画像を生成して出力するエツジ検出手段と
を具え、
上記強エツジ点抽出手段は、上記エツジ強度算出手段及び上記エツジ検出手段の出力に基づいて、上記エツジ点のうち上記エツジ強度が所定のしきい値より大きい上記エツジ点を上記中継点として抽出する
ことを特徴とする請求項１に記載の輪郭抽出装置。
【請求項３】
上記中継点抽出手段は、
上記対象物の輪郭をおおまかに示す推定輪郭曲線に沿つて連続した折れ線又は曲線でなる輪郭候補領域情報を用いて、上記画像からグラデイエントベクトルを算出して出力するグラデイエントベクトル算出手段と、
上記輪郭候補領域における上記画像からエツジ点を検出し、当該エツジ点の位置を指定するエツジ点２値画像を生成して出力するエツジ検出手段と、
を具え、
上記強エツジ点抽出手段は、上記グラデイエントベクトル算出手段及び上記エツジ検出手段の出力に基づいて、上記折れ線の各線分、上記曲線を分割して得られる各セグメントを近似する各線分、又は上記曲線を分割して得られる各セグメントの近傍毎に、上記エツジ点のうち上記エツジ強度が最大となる上記エツジ点を上記中継点として抽出する
ことを特徴とする請求項１に記載の輪郭抽出装置。
【請求項４】
上記経路探査手段は、
上記画像からグラデイエントベクトルを算出するグラデイエントベクトル算出手段と、
上記グラデイエントベクトルに基づいて、経路探査中の８近傍において、上記順序が連続する中継点間に存在し互いに隣接する２画素の位置座標におけるグラデイエントベクトルを算出し、上記２画素の位置座標における上記グラデイエントベクトルと上記２画素の位置座標との関数で表される評価項をもつ局所評価関数を用いて、上記順序が連続する中継点間の経路を決定する
ことを特徴とする請求項１に記載の輪郭抽出装置。
【請求項５】
上記経路探査手段は、
上記順序が連続する上記中継点間に存在し互いに隣接する２画素間の局所評価値を算出するための局所評価関数を有し、当該局所評価関数を用いて上記順序が連続する上記中継点間の経路を決定する
ことを特徴とする請求項１に記載の輪郭抽出装置。
【請求項６】
上記曲線生成手段は、
上記線図形によつて表される形状を複数のセグメントに分割する分割点を算出して出力する分割点算出手段と、
上記線図形及び上記各分割点に基づいて、上記各セグメントを連結するための連結条件を上記各分割点毎に算出して出力する連結条件算出手段と、
上記線図形、上記各分割点及び上記各連結条件に基づいて、上記各分割点における上記連結条件を満たすように上記各セグメントを曲線近似する曲線近似手段と
を具えることを特徴とする請求項１に記載の輪郭抽出装置。
【請求項７】
オペレータにより指定された輪郭の大まかな形状を基に、対象物の輪郭を推定輪郭として推定する輪郭推定手段
を具え、上記中継点抽出手段は、上記輪郭推定手段により推定された上記推定輪郭に基づき上記輪郭候補領域を算出し上記中継点を抽出する
ことを特徴とする請求項１に記載の輪郭抽出装置。
【請求項８】
上記曲線生成手段の出力に基づいて、現画像中における対象物の輪郭を推定輪郭として推定する輪郭推定手段
を具え、上記中継点抽出手段は、上記輪郭推定手段により推定された上記推定輪郭に基づき上記現画像中における上記輪郭候補領域を算出して上記中継点を抽出し、
上記中継点連結手段は、上記中継点同士を結ぶ経路を探査し順次連結することにより、上記現画像中における上記対象物の輪郭を上記線図形として生成する
ことを特徴とする請求項１に記載の輪郭抽出装置。
【請求項９】
経路探査を利用して画像中から対象物の輪郭を抽出する輪郭抽出方法において、
上記対象物の輪郭が存在すると考えられる輪郭候補領域において当該輪郭に沿つた複数の点を中継点として抽出し、当該中継点に対して当該輪郭に沿つた順序付けを行う中継点抽出ステツプと、
上記中継点同士を結ぶ経路を探査し順次連結することにより、上記輪郭を表す線図形を生成する中継点連結ステツプと、
上記線図形によつて表される形状を近似する曲線を生成する曲線生成ステツプと
を具え、
上記中継点抽出ステツプは、上記輪郭候補領域において検出した複数のエツジ点のうち、エツジ強度が所定のしきい値よりも大きい上記エツジ点を上記中継点として抽出する強エツジ点抽出ステツプを具え、
上記中継点連結ステツプは、局所的な経路毎に設定された通過コストの総和を表す評価関数を有し、上記評価関数が最小となるように、上記順序が連続する上記中継点間の最短経路を決定する経路探査ステツプを具える
ことを特徴とする輪郭抽出方法。
【発明の詳細な説明】
【０００１】
【目次】
以下の順序で本発明を説明する。
発明の属する技術分野
従来の技術
発明が解決しようとする課題
課題を解決するための手段
発明の実施の形態
（１）全体構成（図１）
（２）実施例（図２〜図１８）
（２−１）輪郭曲線生成部の基本構成（図２）
（２−１−１）輪郭座標リスト生成部の構成（図３及び図４）
（２−１−１−１）中継点抽出部の構成（図５〜図７）
（２−１−１−２）中継点連結部の構成（図８〜図１３）
（２−１−２）曲線生成部の構成（図１４及び図１５）
（２−２）実施例の動作及び効果（図１６）
（３）他の実施例（図１７及び図１８）
発明の効果
【０００２】
【発明の属する技術分野】
本発明は輪郭抽出装置及び輪郭抽出方法に関し、特にテレビジヨンや映画等の映像制作における特殊効果処理において、画像中から対象物の輪郭を抽出する輪郭抽出装置及び輪郭抽出方法に適用して好適なものである。
【０００３】
【従来の技術】
従来、この種の特殊効果処理においては、画像から任意の部分画像を抽出する際の精度が重要となる。この抽出作業においては、エツジ検出、領域検出及び既知物体との対応付け等の処理が必要であり、特に画像中の背景や対象物が複雑である場合には、対象物の輪郭を構成するエツジを精度良く検出して追跡する必要がある。
【０００４】
ここで画像中から対象物の輪郭を抽出する第１の輪郭抽出方法として、文献「画像合成のための対象物抽出法」（井上誠喜、電子情報通信学会論文誌、vol.J74-D-II、No.10 、pp1411-1418 、1991）や「領域抽出方法」（特開平3-17680 号）がある。この第１の輪郭抽出方法は、太線で対象物の輪郭をなぞることによつて対象物のおおよその輪郭を情報として与え、この太線領域内に対してエツジ強度（画素値の変化の度合い）の大きい画素を残した輪郭線図形２値画像を得るものである。
【０００５】
また画像中から対象物の輪郭を抽出する第２の輪郭抽出方法として、文献「Intelligent Scissors for Image Composition」（Eric N.Mortensen and William A.Barrett、Computer Graphics Proceedings 、Annual Conference Series、1995、ACM SIGGRAPH、pp.191-198）に記載されている方法がある。
【０００６】
この第２の輪郭抽出方法は、インタラクテイブに輪郭の任意の２点を指定すると、その２点間の輪郭線図形２値画像を算出するものであり、この操作を繰り返すことよつて対象物の輪郭を得る。与えられた２点間の輪郭は、エツジの強度とエツジの方向を用いた経路評価関数を設定することにより、最短路探査問題を解くことによつて算出する。文献「離散最適化法とアルゴリズム」（茨木俊秀、岩波書店、1993年）によれば、最短路探査問題を高速に解くアルゴリズムが提案されており、この輪郭抽出方法においてもこれを利用している。
【０００７】
さらに画像中から対象物の輪郭を抽出する第３の輪郭抽出方法として、「SNAKES: Active Contour models 」（Kass M. 、Witikin A.、Terzopoulos D.、Proc.1st ICCV 、pp259-268 、1987）がある。この「snakes」と呼ばれる動的輪郭モデルは、画像中の輪郭に収束するように移動するコントロールポイントを、拘束条件によつて鎖状に連結したものである。この動的輪郭モデルの応用例としては、「領域分割に基づく複雑物体の自動切り出し」（栄藤稔、白井良明、NICOGRAPH ’92論文集、pp. 8-17、1992）、「領域抽出装置」（特開平5-61977 ）、「弾性輪郭モデルとエネルギー最小化原理による輪郭追跡手法」（上田修功、間瀬健二、末永康仁、信学誌、vol.J-75-D-II 、No．1 、pp.111-120、1992）、「動物体の輪郭追跡方法」（特開平5-12443 号）がある。
【０００８】
この「snakes」と呼ばれる動的輪郭モデルを用いる輪郭抽出方法は、第１に、動的輪郭モデルは、複数のコントロールポイントをスプライン曲線などを用いて連結したもので、線図形２値画像でない常に滑らかな輪郭を得ることができるという特徴、第２に、動的輪郭モデルの収束はコントロールポイントを少しずつ動かしながら、モデルのもつ評価関数の更新を反復処理するという局所探査と呼ばれる方法によつて解を求めるという特徴をもつている。
【０００９】
【発明が解決しようとする課題】
ところで画像中の対象物の輪郭を抽出する方法において、抽出された輪郭が最終的に曲線で得られると、輪郭における様々な特徴量の算出が容易になることや、サブピクセル精度の形状をもつことによりアンチアイリアス等が可能になり画像合成処理等に有利になるなど、後続の画像処理が容易になる。従つて対象物の輪郭形状は曲線で得られることが望ましい。
ところが上述の第１及び第２の輪郭抽出方法は、対象物の輪郭を線図形２値画像として算出し、輪郭形状を最終的に曲線で得ないため、抽出した輪郭を最終的に曲線で得た場合に得られる上述の利点を得ることができない問題があつた。
【００１０】
また第２の輪郭抽出方法は、第１の輪郭抽出方法と比較して、問題を解くためのソート処理などの処理時間の増大を抑えることができるが、輪郭上の種々の点をオペレータが与える必要があるため、輪郭抽出作業が煩雑になる問題があつた。また第２の輪郭抽出方法は、最短経路探査問題を解くために用いる経路評価関数に画像の２次微分を用いており、この画像の２次微分の項は評価関数中最も重要な項であるが、画像の２次微分はノイズに弱く、輪郭曲線を精度良く抽出し得ない問題があつた。
【００１１】
一方、動的輪郭モデルを用いる第３及び第４の輪郭抽出方法は、輪郭をスプライン曲線として得ることができる。しかしながら、動的輪郭モデルの原理上、コントロールポイントの数は予め定められており、スプライン曲線の形状の自由度は、コントロールポイントの数によつて制限されるため、輪郭全体の形状の次数よりスプライン曲線の次数が小さくならないようにコントロールポイントの数を設定しなければならない。ところが輪郭の形状の次数を輪郭抽出を行うことなく画像から直接調べることは困難であり、輪郭の形状の次数に一致した輪郭曲線を得ることができなかつた。
【００１２】
また第３及び第４の輪郭抽出方法の場合、エツジ強度勾配を指標とした評価関数により動的輪郭モデルを駆動するため、エツジ強度の勾配のノイズや、求めたい輪郭と判別しにくい他物体の輪郭に起因するエツジ強度の勾配などに影響され易く、輪郭曲線を精度良く抽出することができなかつた。
さらに第３及び第４の輪郭抽出方法は、局所探査を基本としたアルゴリズムであるため、動的輪郭モデルの初期位置によつては最適解を得ることができないおそれがあつた。
【００１３】
本発明は以上の点を考慮してなされたもので、画像中から対象物の輪郭の形状の次数に一致した輪郭曲線を得ることのできる輪郭抽出装置及び輪郭抽出方法を提案しようとするものである。
【００１４】
【課題を解決するための手段】
かかる課題を解決するため本発明においては、対象物の輪郭が存在すると考えられる輪郭候補領域において検出した複数のエツジ点のうち、エツジ強度が所定のしきい値よりも大きいエツジ点を中継点として抽出し、当該中継点に対して当該輪郭に沿つた順序付けを行い、局所的な経路毎に設定された通過コストの総和を表す評価関数が最小となるよう、順序が連続する中継点間の最短経路を決定して各中継点を結ぶ経路を探査し、当該経路を順次連結することにより輪郭を表す線図形を生成して、当該線図形によつて表される形状を近似する曲線を生成するようにした。
経路探査を用いることにより中継点間を結ぶ経路をそれぞれ高精度に探査でき、また探索した経路を順次連結した線図形が曲線に近似されるので、輪郭形状を最終的に曲線で得ることができる。
【００１５】
【発明の実施の形態】
以下、図面について本発明の一実施例を詳述する。
【００１６】
（１）全体構成
図１において、１は全体として本発明を適用したキー信号生成装置を示し、連続した複数の画像中に存在する対象物のソフトキーを生成する。
キー信号生成装置１は、輪郭抽出部２及びキー算出部３により構成されており、輪郭抽出部２において算出した対象物の輪郭曲線と、対象物の輪郭のグラデイエントベクトルとに基づいて、キー算出部３において対象物のソフトキーを生成する。
【００１７】
キー信号生成装置１は、入力手段として例えばマウス４を用いてオペレータによつて入力された、輪郭のおおまかな形状を示す線分情報、折れ線情報、曲線情報、又は太い筆でなぞつたようなマスク画像情報Ｓ１を、輪郭抽出部２の推定輪郭算出部５で受ける。推定輪郭算出部５は、線分情報、折れ線情報、曲線情報又はマスク画像情報Ｓ１に基づいて対象物の輪郭の推定形状（以下、これを推定輪郭と呼ぶ）に応じた推定輪郭情報Ｓ２を得、当該推定輪郭情報Ｓ２を輪郭候補領域決定部６に送出する。
【００１８】
輪郭候補領域決定部６は、推定輪郭情報Ｓ２に基づいて、輪郭が存在すると考えられる領域（以下、これを輪郭候補領域と呼ぶ）を算出し、当該輪郭候補領域に応じた輪郭候補領域情報Ｉi を輪郭曲線生成部７に送出する。
輪郭曲線生成部７は、輪郭候補領域情報Ｉi に基づいて輪郭候補領域におけるグラデイエントベクトルを算出して当該グラデイエントベクトルを規格化すると共に、輪郭の中心を通過する画素のリスト（以下、これを輪郭座標リストと呼ぶ）Ｐを生成した後、当該輪郭座標リストＰによつて表される形状を近似する曲線を生成し、当該曲線に応じた輪郭曲線情報Ｃ及び規格化されたグラデイエントベクトルＧＳをキー算出部３に送出する。
【００１９】
ここでこのキー信号生成装置１においては、折れ線情報、曲線情報又はマスク画像情報Ｓ１より推定輪郭情報Ｓ２を得る方法とは別に、１つ前のフレームである画像ｉ−１の輪郭曲線情報Ｓ４を用い、動きベクトル推定処理によつて画像ｉ−１の輪郭が現画像ｉにおいてどこに移動したかを推定することより、現画像ｉにおける推定輪郭情報Ｓ２を得ることができるようになされている。
【００２０】
すなわち動きベクトル推定部８は、１フレーム前の画像ｉ−１について、輪郭候補領域決定部６及び輪郭曲線生成部７を介して得られる輪郭曲線情報Ｃを用いて、当該輪郭曲線情報Ｃに応じた輪郭曲線が現画像ｉにおいてどこに移動したかを推定し、この結果を推定輪郭情報Ｓ２として輪郭候補領域決定部６に送出する。この場合、輪郭候補領域決定部６及び輪郭曲線生成部７での処理は、上述と同様の方法で行われる。
従つて推定輪郭情報Ｓ２を得る方法として動きベクトル推定部８が選択された場合、輪郭曲線生成部７は、輪郭曲線情報Ｃを遅延回路９を介して動きベクトル推定部８にフイードバツクするようになされている。
【００２１】
キー算出部３は、グラデイエントベクトルＧＳ及び輪郭曲線情報Ｃを両端曲線算出部１０で受ける。両端曲線算出部１０は、グラデイエントベクトルＧＳ及び輪郭曲線情報Ｃに基づいて、輪郭の両端を表す２本の曲線（以下、これを両端曲線と呼ぶ）間の幅を算出し、当該両端曲線間の幅に応じた両端曲線情報Ｓ３をソフトキー生成部１１に送出する。ソフトキー生成部１１は、両端曲線情報Ｓ３に基づいて、２本の両端曲線間に高さが「０」から「１」まで滑らかに変化する曲面を生成し、この曲面の高さをソフトキーの値として画像に書き込む処理を行つてソフトキーを算出し出力する。
【００２２】
かくしてこのキー信号生成装置１は、画像中に存在する対象物のソフトキーを生成することができるようになされている。
【００２３】
（２）実施例
（２−１）輪郭曲線生成部の基本構成
本発明の実施例による輪郭曲線生成部７の構成を図２に示す。輪郭曲線生成部７は、輪郭候補領域決定部６から供給される輪郭候補領域情報Ｉi を輪郭座標リスト生成部２０で受ける。
【００２４】
輪郭座標リスト生成部２０は、輪郭座標情報生成手段として、輪郭候補領域情報Ｉi に基づいて、対象物の輪郭を複数の離散的な座標データでなる輪郭座標リストＰとして生成し、当該輪郭座標リストＰを曲線生成部２１に送出する。曲線生成部２１は、輪郭座標リストＰによつて表される形状を近似する曲線Ｃを生成し、当該曲線Ｃを輪郭曲線情報Ｃとしてキー算出部３に送出する。
以下、この実施例における輪郭座標リスト生成部２０及び曲線生成部２１の具体的な構成を順に説明する。
【００２５】
（２−１−１）輪郭座標リスト生成部の構成
輪郭座標リスト生成部２０の具体的な構成を図３に示し、輪郭座標リスト生成部２０における輪郭座標リスト生成処理について図４に示すフローチヤートを用いて説明する。
輪郭座標リスト生成部２０は、ステツプＳＰ１より輪郭座標リスト生成処理を開始し、ステツプＳＰ２において、輪郭候補領域情報Ｉi （ｘ、ｙ）を中継点抽出部２２及び中継点連結部２３において受ける。
【００２６】
次いでステツプＳＰ３において、輪郭座標リスト生成部２０は、中継点抽出手段としての中継点抽出部２２において、輪郭候補領域情報Ｉi 中から対象物の輪郭を検出した後、当該検出した輪郭から複数の点を中継点ｑi として輪郭に沿つて抽出し、これら中継点ｑi でなる中継点座標リストＱを中継点連結部２３に送出する。この実施例の場合、中継点抽出部２２は、後述するように、エツジの強度が近傍に比して明らかに大きい点を中継点ｑi として抽出する。
【００２７】
続いてステツプＳＰ４において、輪郭座標リスト生成部２０は、中継点連結手段としての中継点連結部２３において、輪郭候補領域情報Ｉi 及び中継点座標リストＱに基づいて、各中継点ｑi を順次連結して８近傍線図形を作成し、ステツプＳＰ５において、当該８近傍線図形を表す輪郭座標リストＰを曲線生成部２１に送出し、ステツプＳＰ６において輪郭座標リスト生成処理を終了する。
【００２８】
（２−１−１−１）中継点抽出部の構成
中継点抽出部２２の具体的な構成を図５に示し、中継点抽出部２２における中継点抽出処理について図６に示すフローチヤートを用いて説明する。
中継点抽出部２２は、ステツプＳＰ１より中継点抽出処理を開始し、ステツプＳＰ２において、輪郭候補領域情報Ｉi をエツジ強度算出部２２Ａ及びエツジ検出部２２Ｂで受ける。
【００２９】
次いでステツプＳＰ３において、中継点抽出部２２は、エツジ強度算出手段としてのエツジ強度算出部２２Ａにおいて、輪郭候補領域情報Ｉi に基づいて輪郭候補領域におけるエツジ強度を算出して当該エツジ強度に応じたエツジ強度画像Ｇ（ｘ、ｙ）を生成し、当該エツジ強度画像Ｇを強エツジ点抽出部２２Ｃに送出する。ここでエツジ強度算出部２２Ａは、例えば「画像解析ハンドブツク」（高木幹雄、下田陽久、東京大学出版界、1991）に記載されている方法によつてエツジ強度を算出する。
【００３０】
続いてステツプＳＰ４において、中継点抽出部２２は、エツジ検出手段としてのエツジ検出部２２Ｂにおいて、輪郭候補領域情報Ｉi よりエツジ点を検出して当該エツジ点の位置を指定するエツジ点２値画像Ｅ（ｘ、ｙ）を生成し、当該エツジ点２値画像Ｅを強エツジ点抽出部２２Ｃに送出する。ここでエツジ点２値画像とは、エツジ位置に相当する画素の値が「１」で表され、それ以外の画素の値が「０」で表される画像である。エツジ検出部２２Ｂは、例えば上述の「画像解析ハンドブツク」に記載されている方法によつてエツジ点を検出する。
【００３１】
次いでステツプＳＰ５において、中継点抽出部２２は、強エツジ点抽出手段としての強エツジ点抽出部２２Ｃにおいて、エツジ強度画像Ｇ及びエツジ点２値画像Ｅに基づいて、エツジ点のうち、エツジ強度が予め定められたしきい値Ｔより大きいエツジ点に相当する位置の画素を中継点ｑi として抽出し、当該抽出した中継点ｑi を輪郭に沿つて順序付けすることにより、中継点座標リストＱを生成する。中継点抽出部２２は、ステツプＳＰ６において、中継点座標リストＱを中継点連結部２３に送出し、ステツプＳＰ７において中継点抽出処理を終了する。
【００３２】
ここで強エツジ点抽出部２２Ｃにおける中継点ｑi の順序付け処理について図７を用いて説明する。
中継点ｑi が輪郭に沿つてそれほど大きくない間隔で得られている場合、中継点ｑi をたどる経路（折れ線）がループを作らないようにしながら（物体輪郭はループにならない）、近傍の中継点ｑi をたどる順序付けをすることにより輪郭に沿つた順序付けを行うことができる。すなわち中継点ｑi をたどる経路のうち最短で１周する経路を選択すればループが生じない。
【００３３】
ここで図７（Ａ）に示すように、ループのある経路では必ず経路のどこかで交差が発生し、このような経路が最短の経路でないことは、図７（Ｂ）に示すような交差を修正した経路が図７（Ａ）に示すような経路より明らかに短いことから証明できる。すなわち図７（Ａ）における線分［ｑi 、ｑi+1 ］と線分［ｑj 、ｑj+1 ］の長さの和と、図７（Ｂ）における線分［ｑi 、ｑi+1 ］と線分［ｑj 、ｑj+1 ］の長さの和には、三角形の一辺と他の２辺の和の関係が成立し、交差がある経路には必ずこれよりも短い経路が存在することが分かるので、最短経路はループをもたない。
【００３４】
従つて強エツジ点抽出部２２Ｃにおける中継点ｑi の順序付け処理は、全ての中継点ｑi をたどる最短の経路を求める問題に置き換えることができる。この問題は、「離散最適化法とアルゴリズム」（茨木俊秀、岩波書店、1993）によれば、巡回セールスマン問題の１種であり、この問題を解くことによつて全ての中継点ｑi をたどる最短の経路を求めることができる。
【００３５】
（２−１−１−２）中継点連結部の構成
中継点連結部２３の具体的な構成を図８に示す。中継点連結部２３は、中継点連結手段として、輪郭候補領域決定部６から供給される輪郭候補領域情報Ｉｉをグラデイエントベクトル算出部２４で受ける。グラデイエントベクトル算出部２４は、後述するように、輪郭候補領域情報ＩｉからグラデイエントベクトルＧを生成した後、当該グラデイエントベクトルＧを規格化することにより、入力画像における色差の大小に依存しない規格化されたグラデイエントベクトルＧＳを生成し、当該グラデイエントベクトルＧＳをエツジ検出部２５、経路探査部２６及びキー算出部３に送出する。
【００３６】
ここでこの実施例における輪郭候補領域決定部６及びグラデイエントベクトル算出部２４の構成を図９に示す。この実施例の場合、入力手段４から、検出したい輪郭のおおまかな位置及び方向を指定する情報として、輪郭に沿つて連続した曲線情報Ｓ１が入力されるものとする。
【００３７】
輪郭候補領域決定部６は、推定輪郭算出部５から供給される曲線でなる推定輪郭情報Ｓ２を特徴点抽出回路６Ａ及び曲線分割回路６Ｂで受ける。特徴点抽出回路６Ａは、推定輪郭情報Ｓ２に応じた曲線より特徴点を抽出し、当該特徴点に応じた特徴点情報ＣＲを曲線分割回路６Ｂに送出する。ここで特徴点とは、曲線上で特異な点を示す点であり、例えば曲線の形状が屈曲する屈曲点や曲線の軌跡上で画像の色が変化する色変化点などである。
【００３８】
曲線分割回路６Ｂは、推定輪郭情報Ｓ２に応じた曲線を、各特徴点を頂点とするエツジに沿つて連続した折れ線Ｌに近似し、当該折れ線Ｌを領域分割回路６Ｃに送出する。領域分割回路６Ｃは、曲線分割回路６Ｂから供給される折れ線Ｌに基づいて、折れ線Ｌの各線分ｌj の近傍画素を指定するマスク画像Ｉmjを各線分ｌj 毎に生成し、それぞれ対応する線分ｌj とマスク画像Ｉmjとの対を輪郭の方向及び位置の情報としてグラデイエントベクトル算出部２４に送出する。
【００３９】
グラデイエントベクトル算出部２４は、グラデイエントベクトル算出手段として、輪郭候補領域情報Ｉi として供給される線分ｌj とマスク画像Ｉmjとの対を、当該対の数だけ設けられたエツジ強度規格化回路２４Ａで受けると共に、各マスク画像Ｉmjを画像合成部２４Ｂで受ける。各エツジ強度規格回路２４Ａは、線分ｌj とマスク画像Ｉmjに基づいてグラデイエントベクトルＧj を生成した後、当該グラデイエントベクトルＧj 、線分ｌj 及びマスク画像Ｉmjに基づいて、色差の大きさを「１」にするような規格化処理を行うことにより、規格化したグラデイエントベクトルＧsjを生成し、当該規格化された各グラデイエントベクトルＧsjを画像合成部２４Ｂに送出する。
画像合成部２４Ｂは、対応するグラデイエントベクトルＧsjとマスク画像Ｉmjとの対を用いて、規格化されたグラデイエントベクトルＧＳを生成し、当該グラデイエントベクトルＧＳをエツジ検出部２５、経路探査部２６及びキー算出部３に送出する。
【００４０】
ここでエツジ強度画像規格化回路２４Ａにおける規格化処理の具体的な内容について説明する。
エツジ強度規格化回路２４Ａは、エツジの位置及びエツジの方向についての情報として与えられるマスク画像及び線分の対に基づいて、エツジを垂直に横切る横断直線を算出し、当該横断直線上でエツジ強度が最大となるエツジ強度最大点を算出した後、横断直線上のエツジ強度最大点を始点とする一方の側の半直線上において、エツジ強度がエツジ強度最大点におけるエツジ強度より小さく、かつ所定のしきい値以下となる点Ｐ０を検出すると共に、横断直線上のエツジ強度最大点を始点とする上述の半直線とは正反対の半直線上において、エツジ強度がエツジ強度最大点におけるエツジ強度より小さく、かつ所定のしきい値以下となる点Ｐ１を検出し、点Ｐ０及び点Ｐ１間を結ぶ直線を積分経路ＰＩとする。
【００４１】
続いてエツジ強度規格化回路２４Ａは、積分経路ＰＩ上の端点Ｐ０から端点Ｐ１までの任意の複数の点におけるエツジ強度値を求め、これら各点におけるエツジ強度値の総和を規格化係数Ｓとして算出した後、当該規格化係数ＳでグラデイエントベクトルＧj を除算することにより、規格化されたグラデイエントベクトルＧＳj を生成する。
【００４２】
次にこの実施例におけるエツジ検出部２５の構成を図１０に示す。エツジ検出部２５は、エツジ検出手段として、グラデイエントベクトル算出部２４から規格化係数Ｓ及び積分経路ＰＩをしきい値算出回路２５Ａで受けると共に、規格化されたグラデイエントベクトルＧＳをエツジ点検出回路２５Ｂで受ける。
しきい値算出回路２５Ａは、規格化係数Ｓを積分経路ＰＩの長さ（すなわち点Ｐ０及び点Ｐ１間の距離）で除算することにより得られる値をしきい値Ｈとしてエツジ点検出回路２５Ｂに送出する。
【００４３】
エツジ点検出回路２５Ｂは、しきい値Ｈを用いて、規格化されたグラデイエントベクトルＧＳに対してしきい値処理を行うことにより、エツジ強度がピークとなるエツジ点を検出し、エツジ強度のピークを表すエツジ点２値画像ＥＰを経路探査部２６に送出する。
かくして経路探査部２６には、規格化されたグラデイエントベクトルＧＳ及びエツジ点２値画像ＥＰが入力される。
【００４４】
経路探査部２６における経路探査処理について図１１に示すフローチヤートを用いて説明する。
経路探査部２６は、経路探査手段として、ステツプＳＰ１より経路探査処理を開始し、ステツプＳＰ２、ステツプＳＰ３及びステツプＳＰ４において、それぞれ中継点座標リストＱ、グラデイエントベクトルＧＳ及びエツジ点２値画像ＥＰを受ける。次いで経路探査部２６は、ステツプＳＰ５において、出力する輪郭座標リストＰを初期化し、第１の座標にｑ0 を入力する。
【００４５】
続いて経路探査部２６は、ステツプＳＰ６において、後述するように、グラデイエントベクトルＧＳ及びエツジ点２値画像ＥＰを用いた局所評価関数ｄを用いて、中継点ｑi 及び中継点ｑi+1 間の最短経路Ｐｔを算出した後、最短経路Ｐｔと終点ｑi+1 を、輪郭座標リストＰに入力し、このようにして輪郭座標リストＰが完成すると、ステツプＳＰ７において輪郭座標リストＰを曲線生成部２１に送出し、ステツプＳＰ８において経路探査処理を終了する。最短経路Ｐｔは８近傍線図形を表す座標リストである。
【００４６】
ここで経路探査部２６のステツプＳＰ６における処理について説明する。最短経路探査は種々の方法で求めることができるが、あらゆる局所的な経路の通過コストは一意に決まり、経路全体のコストがこれら局所的な通過コストの総和となるような経路評価関数、すなわち一意に決まる通過コストの大きさを表す経路評価関数を設定することにより、例えば上述した「離散最適化法とアルゴリズム」や「Intelligent Scissors for Image Composition」のような高速なアルゴリズムを用いることができる。この「Intelligent Scissors for Image Composition」における最短経路探査アルゴリズムを図１２及び図１３に示す。
【００４７】
しかしながら局所的な通過コストを決定する局所評価関数は、適用する具体的な問題に合わせて設定する必要がある。ここでは本発明の目的に適した局所評価関数について説明する。
【００４８】
（Ａ）進行方向の評価関数
グラデイエントは、色の勾配が上昇する方向に向くので、場所によつて輪郭の色差が変化する場合では、輪郭上でグラデイエントの向きが不連続に変化するところが生ずる。しかしこの実施例においては中継点連結部２３は、検出したい輪郭の大まかな位置と方向、すなわちエツジの位置とエツジの方向とを用いて、検出したい輪郭上でグラデイエントベクトルの向きが常に滑らかに変化するようにグラデイエントを算出している。これにより輪郭に沿つて常に時計回り又は反時計回りに沿つて進むような経路のコストを、輪郭の途中で後戻りするような経路よりも低く評価する局所評価関数を作成することができる。
【００４９】
このような局所評価関数は、経路探査中の８近傍において、隣接する中継点間に存在する隣接する２画素の位置座標ｐ、ｑを入力とし、座標ｐ、ｑにおけるグラデイエントの方向を示すベクトルＧ（ｐ）、Ｇ（ｑ）と座標ｐ、ｑとの関数ｇを、次式（１）
【数１】
0004114966.tif 000002
で表されるように構成する。ここでＨは、グラデイエントベクトルＧ（ｑ）の方向より＋π／２ずれた方向を示す単位ベクトルであり、acos（（ｑ−ｐ）／｜ｑ−ｐ｜・Ｈ）は、輪郭の進む方向と、ｐからｑへ進む局所経路の方向のなす角度を表す。
【００５０】
ここで上述のようにグラデイエントベクトルＧ（ｑ）の方向は連続なので、輪郭に沿つて一方向に進む経路ほどコストが低く、逆に輪郭に沿つていても途中で逆方向に方向が変化する経路はコストが悪くなる。
従つて経路探査部２６は、局所関数ｇを用いることにより、常に輪郭に沿つて一方向に進むような経路探査を行うことができる。
【００５１】
（Ｂ）エツジピーク通過の評価関数
経路が輪郭の中央をなるべく通過するようにする評価関数は本発明に有効である。同様の機能をもつ評価関数が上述の「Intelligent Scissors for Image Composition」においては画像のラプラシアンを用いて実現されている。ラプラシアンはエツジの中心を検出する能力は高いが、ノイズに敏感であるので、平滑化フイルタと組み合わせて使用される。しかしながらどんなサイズの平滑化フイルタを用いるかは、得たい輪郭に合わせてその都度決定しなければならない。
【００５２】
この実施例における中継点連結部２３は、検出したい輪郭の大まかな位置と方向、すなわちエツジの位置とエツジの方向とを用いて、エツジ強度がピークとなるエツジ点を検出するエツジ点検出処理を行つており、これによりエツジ強度を用いたエツジ点検出でもエツジ中心の検出能力を向上させることができるので、評価関数の信頼性を向上させることができる。またラプラシアンのように平滑化フイルタを用いる必要がないので、その分中継点連結部２３の構成を簡略化することができる。
【００５３】
このような局所評価関数は、経路探査中の８近傍において、隣接する中継点間に存在する隣接する２画素の位置座標ｐ、ｑを入力とし、エツジ点２値画像ＥＰにおける座標ｐ、ｑでの画素値Ｅ（ｐ）、Ｅ（ｑ）と、座標ｐ、ｑとの関数ｅを、次式（２）
【数２】
0004114966.tif 000003
で表されるように構成する。ここでＥ＝０又は１である。すなわちこの局所評価関数ｅは、エツジ強度がピークとなる位置を通過する画素を評価する関数である。従つて経路探査部２３は、局所関数ｅを用いることにより、エツジ強度がピークとなる位置を評価する経路探査を行うことができる。
【００５４】
（Ｃ）評価関数の組み合わせと８近傍距離の補正
この実施例では上述の評価関数ｇ及び評価関数ｅ（すなわちグラデイエントベクトルＧＳ及びエツジ２値画像ＥＰ）を以下のように組み合わせて用いる。
評価関数ｄは、評価関数ｇと評価関数ｅとを評価項とし、その係数付き線形和に、隣接する中継点間に存在する隣接する２画素の座標ｐ、ｑ間の距離（｜ｑ−ｐ｜）を乗ずることによつて、各評価項がそれぞれ８近傍距離による評価補正を受ける次式（３）
【数３】
0004114966.tif 000004
となるｄで表されるように構成する。ここで係数ｃ１とｃ２は予め適当に定められた係数である。
【００５５】
またこの局所関数ｄを一般的に表したものを次式（４）
【数４】
0004114966.tif 000005
で表す。この場合、ｆi はｉ番目の評価項を表し、ｃi は番目の係数を表す。
従つて経路探査部２３は、複数の評価項がそれぞれ８近傍距離による評価補正を受けることができる。
【００５６】
かくして輪郭座標リスト生成部２０は、連続値をもつ画像を２値化して対象物の輪郭を中継点でなる輪郭座標リストＰとして生成することにより輪郭の形状の次数を調べやすいようにし、各中継点を順次連結して輪郭形状を一本の経路として抽出することにより他の輪郭などの不要な情報を削除し得るようになされている。
【００５７】
（２−１−２）曲線生成部の構成
曲線生成部２１の構成を図１４に示す。曲線生成部２１は、曲線生成手段として、輪郭座標リスト生成部２０から供給される輪郭座標リストＰを、それぞれ入力座標分割回路２１Ａ、連結条件算出回路２１Ｂ及び曲線近似回路２１Ｃで受ける。入力座標分割回路２１Ａは、輪郭座標リストＰによつて表される形状を分割する分割点の座標のリスト（以下、これを分割点座標リストと呼ぶ）Ｆを生成し、これを連結条件算出回路２１Ｂ及び曲線近似回路２１Ｃに送出する。
【００５８】
すなわち入力座標分割回路２１Ａは、輪郭座標リストＰの離散的な並びから、求める形状の次数を局所的に推定する。この場合、輪郭座標リストＰは分割された各セグメントにおける形状の次数が大きくならないように分割する。例えば各分割点を曲率の大きさに基づいて決定することより、座標データ数に依存せずに各セグメントにおける次数を決定することができので、各セグメントにおける次数が大きくなることを防止することができる。
【００５９】
連結条件算出回路２１Ｂは、輪郭座標リストＰ及び分割点座標リストＦに基づいて、各分割点における連結条件、すなわちＧ１連続性を満たす連結条件を算出し、連結条件リストＲＶとして曲線近似回路２１Ｃに送出する。すなわち連結条件算出回路２１Ｂは、各分割点の連結位置を一致させるための連結位置の座標ｒi と、連結位置ｒi における速度方向を一致させるための速度ベクトルｖi との対（すなわち接線）を連結条件リストＲＶとして算出する。この場合、連結位置の座標と分割点の座標とは必ずしも一致しない。
【００６０】
曲線近似回路２１Ｃは、隣接する分割点で区切られる各セグメントを、両端点における連結条件を満たすように最小２乗法を用いて曲線近似することにより、隣接する分割点間における近似曲線ｃi を算出し、近似曲線ｃi でなる近似曲線群Ｃを輪郭曲線情報Ｃとしてキー算出部３に送出する。
【００６１】
曲線生成部２１における曲線生成処理について図１５に示すフローチヤートを用いて説明する。
曲線生成部２１は、ステツプＳＰ１より曲線生成処理を開始し、ステツプＳＰ２において、輪郭座標リスト生成部２０から輪郭座標リストＰを受け、ステツプＳＰ３において、輪郭座標リストＰを基に分割点座標リストＦを作成する。
【００６２】
続いて曲線生成部２１は、ステツプＳＰ４において、各分割点近傍における形状に近似した近似曲線を算出し、当該近似曲線における分割点近傍での接線ｒi 、ｖi を各セグメントを曲線近似するための連結条件ＲＶとして算出する。次いで曲線生成部２１は、ステツプＳＰ５において、隣接する分割点で区切られる各セグメントを、両端点における連結条件を満たすように最小２乗法を用いて曲線近似することにより近似曲線ｃi を算出し、ステツプＳＰ６において、近似曲線ｃi でなる近似曲線群を輪郭曲線情報Ｃとして出力し、ステツプＳＰ７において曲線生成処理を終了する。
【００６３】
（２−２）実施例の動作及び効果
以上の構成において、輪郭曲線生成部７は、図１６に示すステツプＳＰ１より輪郭曲線生成処理を開始し、ステツプＳＰ２において、輪郭候補領域決定部６から輪郭候補領域情報Ｉi を受けた後、ステツプＳＰ３において、輪郭候補領域情報Ｉi からエツジ強度が最大となるエツジ点を中継点として算出し、当該各中継点を順次連結することにより、対象物の輪郭として８近傍線図形を表す輪郭座標リストＰを生成する。
【００６４】
次いで輪郭曲線生成部７は、ステツプＳＰ４において、輪郭座標リストＰで表される形状を複数のセグメントに分割した後、各セグメントを連結する連結条件を算出して当該連結条件を満たすように各セグメントを曲線近似することにより近似曲線を生成し、ステツプＳＰ５において、当該近似曲線群を輪郭曲線情報Ｃとしてキー算出部３に送出し、ステツプＳＰ６において輪郭曲線生成処理を終了する。
【００６５】
従つてこの輪郭曲線生成部７は、連続値でなる画像から対象物の輪郭を、複数の離散的な座標データでなる輪郭座標リストＰとして生成しているので、対象物の輪郭の形状の次数を容易に調べることができる。
またこの輪郭曲線生成部７は、対象物の輪郭を一本の経路として抽出しているので、抽出したい輪郭以外の他の輪郭などの不要な情報を削除することができ、これにより対象物の輪郭を精度良く抽出することができる。
【００６６】
またこの輪郭曲線生成部７は、画像から対象物の輪郭を曲線として抽出する問題を、曲線近似で解きやすい問題にすることができるので、対象物の輪郭を曲線として容易に抽出することができる。
【００６７】
以上の構成によれば、輪郭候補領域情報Ｉi からエツジ強度が最大となるエツジ点を中継点として算出し、当該各中継点を順次連結することにより、対象物の輪郭として８近傍線図形を表す輪郭座標リストＰを生成した後、輪郭座標リストＰで表される形状を複数のセグメントに分割すると共に、各セグメントを連結する連結条件を算出し、当該連結条件を満たすように各セグメントを曲線近似して近似曲線を生成したことにより、対象物の輪郭の形状の次数を容易に調べることができると共に、抽出したい輪郭以外の他の輪郭などの不要な情報を削除することができる。
かくして画像中から対象物の輪郭の形状の次数に一致した輪郭曲線を精度良く抽出することのできる輪郭抽出部７及び輪郭抽出方法を実現することができる。
【００６８】
また上述の構成によれば、対象物の輪郭の特徴点を基準に輪郭座標リストＰによつて表される形状を分割して各セグメントの次数を決定すると共に、各近似曲線における分割点近傍での接線を連結条件として算出し、当該連結条件を維持するように各近似曲線を曲線近似したので、輪郭座標リストＰによつて表される形状の次数と一致し、かつ滑らかに連続する輪郭曲線を生成することができる。
【００６９】
さらに上述の構成によれば、輪郭上から複数の中継点ｑi を抽出し、各中継点ｑi を経路探査処理によつて連結することにより８近傍線図形を生成したので、曲線生成部２１における曲線近似処理の近似精度を向上させることができる。また輪郭上から複数の中継点ｑi を抽出したので、高速な経路探査処理を行うことができる。
【００７０】
さらに上述の構成によれば、隣接する中継点間の経路を、輪郭の各小部分における最短経路探査問題に帰着させることができるので、輪郭８近傍線図形２画像を生成することができ、これにより輪郭を一本の経路として抽出することができる。従つて対象物の輪郭を精度良く抽出することができる。
【００７１】
さらに上述の構成によれば、画像のグラデイエントと、エツジ強度の極値位置情報とを用いた局所評価関数を用いて経路探査処理を行うようにしたので、ノイズの影響を回避することができる。また隣接する２画素間の局所評価値を算出するための局所評価関数を用いたので、高速な最短経路探査アルゴリズムを適用することができる。
【００７２】
さらに上述の構成によれば、グラデイエントベクトルＧＳ及びエツジ点２値画像ＥＰに基づいて、エツジ点のうちエツジ強度が最大となるエツジ点を中継点ｑi として抽出したので、輪郭の探査処理を行う際にオペレータが探査に必要な点を与える必要がなく、その分輪郭抽出作業を簡略化することができ、また輪郭上の点を確実に抽出することができる。
【００７３】
さらに上述の構成によれば、局所評価関数ｄを用いているので、エツジ強度の勾配や、他の物体の輪郭に起因するエツジ強度の勾配の影響を回避することができるので、画像中から対象物の輪郭を輪郭曲線として精度良く抽出することができる。
【００７４】
さらに上述の構成によれば、色差の大小に依存しない規格化されたグラデイエントベクトルＧＳを用いてエツジ点を検出したので、輪郭全周に亘つて均等に中継点を検出することができ、これにより対象物の輪郭を精度良く抽出することができる。
【００７５】
（３）他の実施例
なお上述の実施例においては、中継点抽出手段として中継点抽出部２２を用いた場合について述べたが、本発明はこれに限らず、図５及び図８との対応部分に同一符号を付した図１７に示すような中継点抽出部３０を中継点抽出手段として用いてもよい。
【００７６】
中継点抽出部３０における中継点抽出処理について図１８に示すフローチヤートを用いて説明する。
中継点抽出部３０は、ステツプＳＰ１より中継点抽出処理を開始し、ステツプＳＰ２において、対応する線分ｌj 及びマスク画像Ｉmjの各対でなる輪郭候補領域情報Ｉi をグラデイエントベクトル算出部２４及びエツジ検出部２２Ｂで受ける。
【００７７】
次いでステツプＳＰ３において、中継点抽出部３０は、グラデイエントベクトル算出部２４において、規格化されたグラデイエントベクトルＧＳを算出した後、ステツプＳＰ４において、エツジ点２値画像Ｅをエツジ検出部２２Ｂにおいて生成し、グラデイエントベクトルＧＳ及びエツジ点２値画像Ｅを強エツジ点抽出部２２Ｃに送出する。この場合、グラデイエントベクトル算出部２４は、算出したグラデイエントベクトルＧを規格化せずに、当該グラデイエントベクトルＧを強エツジ点抽出部２２Ｃに送出するようにしてもよい。
【００７８】
続いてステツプＳＰ５において、中継点抽出部３０は、強エツジ点抽出部２２Ｃにおいて、グラデイエントベクトルＧＳ及びエツジ点２値画像Ｅに基づいて、中継点座標リストＱを生成した後、ステツプＳＰ６において、当該中継点座標リストＱを中継点連結部２３に送出し、ステツプＳＰ７において中継点抽出処理を終了する。ここで強エツジ点抽出部２２Ｃは、グラデイエントベクトルＧＳ及びエツジ点２値画像Ｅに基づいて、エツジ点のうちエツジ強度が最大となるエツジ点を中継点として算出し、当該中継点でなる中継点座標リストＱを生成するようにしてもよい。
【００７９】
この場合、入力画像における色差の大小に依存せずにエツジ強度を均一に検出することができるので、中継点を対象物の輪郭全周に亘つてほぼ均等に抽出することができ、これにより最終的に得られる輪郭曲線の精度を一段と向上させることができる。またこの場合、入力手段４から対象物の輪郭の大まかな形状を指定する曲線情報を入力したので、輪郭上の中継点の信頼性を向上させることができる。
【００８０】
また上述の実施例においては、中継点連結手段として中継点連結部２３を用いた場合について述べたが、本発明はこれに限らず、図５及び図８との対応部分に同一符号を付して示す図１９に示すような中継点連結部４０を用いてもよい。
この中継点連結部４０は、折れ線又は曲線でなる輪郭候補領域情報Ｉi をグラデイエントベクトル算出部４１及びエツジ検出部２２Ｂで受ける。
グラデイエントベクトル算出部４１は、一般に知られているグラデイエントベクトル算出方法を用いて、輪郭候補領域情報Ｉi に応じた輪郭候補領域におけるグラデイエントベクトルＧを算出し、当該グラデイエントベクトルＧを経路探査部２６に送出する。
【００８１】
さらに上述の実施例においては、中継点連結手段として中継点連結部２３を用いた場合について述べたが、本発明はこれに限らず、経路探査処理を行わずに上述の「画像合成のための対象物抽出方法」及び「領域抽出方法」に記載されている細線化処理を用いて中継点を連結するようにしてもよい。
【００８２】
さらに上述の実施例においては、経路評価方法として局所評価関数ｇ及び局所評価関数ｄを組み合わせた局所評価関数ｄを用いた場合について述べたが、本発明はこれに限らず、要は一意に決まる通過コストの大きさを表す評価関数であれば、経路評価方法としてこの他種々の評価関数を用いてもよい。この場合、この評価関数が最小となるように、隣接する中間点間の経路を決定する。また経路評価方法として画像のラプラシアンを用いてもよく、探査方法として「Intelligent Scissors for Image Composition」や「離散最適化法とアルゴリズム」を用いてよい。
【００８３】
さらに上述の実施例においては、局所評価関数ｇとして（１）式で構成される局所評価関数ｇを用いた場合について述べたが、本発明はこれに限らず、次式（５）
【数５】
0004114966.tif 000006
に示すように、要は経路探査中の８近傍において、隣接する中継点間に存在する隣接する２画素の位置座標におけるグラデイエントベクトルＧ（ｐ）、Ｇ（ｑ）と、２画素の位置座標ｐ、ｑとの関数で表される評価項をもつ局所評価関数ｇを経路探査部２６にもたせるようにしてもよい。これによりエツジの進む方向を考慮した経路探査を行うことができる。
【００８４】
さらに上述の実施例においては、局所評価関数ｅとして（２）式で構成される局所評価関数ｅを用いた場合について述べたが、本発明はこれに限らず、次式（６）
【数６】
0004114966.tif 000007
に示すように、要は、経路探査中の８近傍において、隣接する中継点間に存在する隣接する２画素の位置座標における画素値（エツジ点２値画像ＥＰにおける画素値）Ｅ（ｐ）、Ｅ（ｑ）と、２画素の位置座標ｐ、ｑとの関数で表される評価項をもつ局所評価関数ｅを経路探査部２６にもたせるようにしてもよい。これによりエツジのピーク位置を考慮した経路探査を実現することができる。
【００８５】
さらに上述の実施例においては、局所評価関数ｇ及び局所評価関数ｄを組み合わせた局所評価関数ｄを用いた場合について述べたが、本発明はこれに限らず、局所評価関数ｇ又は局所評価関数ｅを用いるようにしてもよく、要は状況に応じて局所評価関数を用いればよい。
【００８６】
さらに上述の実施例においては、オペレータが入力手段４を用いて線分、折れ線又は曲線を入力した場合について述べたが、本発明はこれに限らず、上述したように、現画像ｉと、既に輪郭曲線情報Ｃとして輪郭曲線が得られている１フレーム前の画像ｉ−１と、当該画像ｉ−１の輪郭曲線情報Ｃとに基づいて現画像ｉの推定輪郭情報Ｓ２を得るようにしてもよい（図１）。これにより、作業効率を格段的に向上させることができる。
【００８７】
さらに上述の実施例においては、推定輪郭情報Ｓ２に応じた曲線を各特徴点を頂点とする折れ線に近似し、折れ線の各線分ｌi をエツジ強度規格回路２４Ａに送出したた場合について述べたが、本発明はこれに限らず、推定輪郭情報Ｓ２に応じた曲線を各特徴点で分割し、各特徴点で分割した曲線でなるセグメントをエツジ強度規格化回路２４Ａに送出するようにしてもよい。
【００８８】
【発明の効果】
上述のように本発明によれば、対象物の輪郭が含まれる輪郭候補領域情報Ｉｉからエツジ強度を基に中継点ｑｉを抽出し、各中継点ｑｉを結ぶ経路を探査し順次連結することにより複数の離散的な座標データでなる線図形として生成し、線図形によつて表される形状を近似する曲線を生成することにより、輪郭の形状の次数を容易に調べることができると共に、輪郭形状を最終的に曲線で得ることができる。
かくして対象物の輪郭の形状に一致した輪郭曲線を得ることのできる輪郭抽出装置及び輪郭抽出方法を実現することができる。
【図面の簡単な説明】
【図１】本発明を適用したキー信号生成装置の全体構成を示すブロツク図である。
【図２】輪郭曲線生成部の構成を示すブロツク図である。
【図３】輪郭座標リスト生成部の構成を示すブロツク図である。
【図４】輪郭座標リスト生成処理の処理手順の説明に供するフローチヤートである。
【図５】中継点抽出部の構成を示すブロツク図である。
【図６】中継点抽出処理の処理手順の説明に供するフローチヤートである。
【図７】中継点の順序付け処理の説明に供する略線図である。
【図８】中継点連結部の構成を示すブロツク図である。
【図９】グラデイエントベクトル算出部及び輪郭候補領域決定部の構成を示すブロツク図である。
【図１０】エツジ検出部の構成を示すブロツク図である。
【図１１】経路探査処理の処理手順の説明に供するフローチヤートである。
【図１２】最短経路探査アルゴリズムを示す図表である。
【図１３】最短経路探査アルゴリズムを示す図表である。
【図１４】曲線生成部の構成を示すブロツク図である。
【図１５】曲線生成処理の処理手順の説明に供するフローチヤートである。
【図１６】輪郭曲線生成処理の処理手順の説明に供するフローチヤートである。
【図１７】他の実施例による中継点抽出部の構成を示すブロツク図である。
【図１８】他の実施例による中継点抽出部における中継点抽出処理の処理手順の説明に供するフローチヤートである。
【図１９】他の実施例による中継点連結部の構成を示すブロツク図である。
【符号の説明】
１……キー信号生成装置、２……輪郭抽出部、３……キー算出部、４……入力手段、５……推定輪郭算出部、６……輪郭候補領域決定部、６Ａ……特徴点抽出回路、６Ｂ……曲線分割回路、６Ｃ……領域分割回路、７……輪郭曲線生成部、８……動きベクトル推定部、９……遅延回路、１０……両端曲線算出部、１１……ソフトキー生成部、２０……輪郭座標リスト生成部、２１……曲線生成部、２１Ａ……入力座標分割回路、２１Ｂ……連結条件算出回路、２１Ｃ……曲線近似回路、２２、３０……中継点抽出部、２２Ａ……エツジ強度算出部、２２Ｂ、２５……エツジ検出部、２２Ｃ……強エツジ点抽出部、２３、４０……中継点連結部、２４、４１……グラデイエントベクトル算出部、２４Ａ……エツジ強度規格化回路、２４Ｂ……画像合成部、２５Ａ……しきい値算出回路、２５Ｂ……エツジ点検出回路。２６……経路探査部。
【図１】
0004114966.tif 000008
【図２】
0004114966.tif 000009
【図３】
0004114966.tif 000010
【図４】
0004114966.tif 000011
【図５】
0004114966.tif 000012
【図８】
0004114966.tif 000013
【図６】
0004114966.tif 000014
【図７】
0004114966.tif 000015
【図９】
0004114966.tif 000016
【図１０】
0004114966.tif 000017
【図１４】
0004114966.tif 000018
【図１１】
0004114966.tif 000019
【図１２】
0004114966.tif 000020
【図１３】
0004114966.tif 000021
【図１５】
0004114966.tif 000022
【図１６】
0004114966.tif 000023
【図１７】
0004114966.tif 000024
【図１９】
0004114966.tif 000025
【図１８】
0004114966.tif 000026