(57)【特許請求の範囲】
【請求項１】
画像中からキー信号を生成するキー信号生成装置において、
上記対象物の輪郭についての輪郭領域を決定する輪郭領域決定手段と、
上記輪郭領域におけるグラデイエントベクトルを算出するグラデイエントベクトル算出手段と、
上記輪郭領域におけるグラデイエントベクトルに基づき、上記輪郭領域のエツジに沿つて上記エツジの内側及び外側における境界位置をそれぞれ複数抽出し、当該各境界位置を表す境界座標情報を上記エツジの内側及び外側毎に生成して出力する境界座標抽出手段と、
上記境界座標抽出手段の出力に基づき、上記各境界座標情報によつて表される各形状を近似する２本の境界曲線を上記対象物の輪郭として生成する境界曲線生成手段と、
上記境界曲線生成手段の出力に基づいて、上記２本の境界曲線間に形成する曲面の形状を決定する曲面制御情報を算出して出力する曲面制御情報算出手段と、
上記曲面制御情報算出手段の出力に基づいて、上記各境界曲線によつて挟まれた領域上に曲面を生成し、当該曲面をキー情報として出力する曲線生成手段とを具え、
上記曲面制御情報算出手段は、
上記境界曲線のうち一方の上記境界曲線をｚ＝１の平面上に位置させると共に、上記境界曲線のうち他方の上記境界曲線をｚ＝０の平面上に位置させ、当該境界曲線を相対する縁とする曲線を生成するような上記曲面制御情報を算出する
ことを特徴とするキー信号生成装置。
【請求項２】
上記境界座標抽出手段は、
上記グラデイエントベクトル算出手段の出力に基づいて、上記エツジを横切る経路を経路情報として算出して出力する経路算出手段と、
上記グラデイエントベクトル算出手段及び上記経路算出手段の出力に基づいて、上記エツジを横切る方向におけるエツジ強度最大値と、当該エツジ強度最大値の位置とを検出して出力するエツジ強度ピーク検出手段と、
上記グラデイエントベクトル算出手段、上記経路算出手段及び上記エツジ強度ピーク検出手段の出力に基づいて、上記エツジを横切る方向におけるエツジ強度断面積を算出するエツジ強度断面積算出手段と、
上記エツジ強度ピーク検出手段及び上記エツジ強度断面積算出手段に基づいて、上記エツジ強度最大値に等しい高さ及び上記エツジ強度最大値の位置に等しい中心位置を底辺に有し、かつ上記エツジ強度断面関と等しい面積を有する矩形を算出し、上記矩形における底辺の両端点の座標を上記エツジの内側及び外側における境界位置として算出して出力する矩形算出手段と
を具えることを特徴とする請求項１に記載のキー信号生成装置。
【請求項３】
上記エツジ強度断面積算出手段は、
上記グラデイエントベクトル算出手段、上記経路算出手段及び上記エツジ強度ピーク算出手段の出力に基づいて、上記エツジを横切る経路上において、上記エツジの一端から上記エツジ強度最大値の位置を通過して上記エツジの他端までの区間を積分区間として算出して出力する積分区間算出手段と、
上記グラデイエントベクトル算出手段及び上記積分経路算出手段の出力に基づいて、上記積分区間におけるエツジ強度値を積分した値を上記エツジ強度断面積として算出して出力する積分手段と
を具えることを特徴とする請求項２に記載のキー信号生成装置。
【請求項４】
上記経路算出手段は、
上記エツジ強度画像に基づいて、エツジ強度を指標として上記エツジ強度画像を細線化処理することにより上記対象物の輪郭の位置を算出して出力する細線化手段と、
上記細線化手段の出力に基づいて、上記対象物の位置を座標情報に変換して出力する座標情報変換手段と、
上記座標情報から所定の間隔で計算点を抽出して出力する計算点抽出手段と、
上記座標情報変換手段及び上記計算点抽出手段の出力に基づいて、上記各計算点における法線方向を算出する方向算出手段と
を具え、上記経路算出手段は、対応する上記計算点及び上記法線方向を上記経路情報として出力するようにした
ことを特徴とする請求項２に記載のキー信号生成装置。
【請求項５】
上記境界曲線生成手段は、
それぞれ上記エツジの内側及び外側における境界位置を表す上記各境界座標情報によつて表される各形状をそれぞれ複数のセグメントに分割する分割点を算出する分割点算出手段と、
上記各境界座標情報によつて表される上記各形状について、上記各境界座標情報及び上記各分割点に基づき、上記各セグメントを連結するための連結条件を上記各分割点毎に算出する連結条件算出手段と、
上記各境界座標情報によつて表される上記各形状について、上記各境界座標情報、上記各分割点及び上記各連結条件に基づき、上記各分割点における上記連結条件を満たすように上記各セグメントを曲線近似することにより上記２本の境界曲線を生成する曲線近似手段と
を具えることを特徴とする請求項１に記載のキー信号生成装置。
【請求項６】
上記輪郭領域決定手段は、
上記対象物の輪郭についてのおおまかな形状を示す折れ線情報又は曲線情報を入力する入力手段
を具え、
上記経路算出手段は、
上記入力手段より入力された上記折れ線情報又は曲線情報に応じた折れ線又は曲線上における任意の複数の位置を計算点として抽出する計算点抽出手段と、
上記折れ線又は曲線及び上記各計算点に基づいて、上記各計算点における法線方向を算出する方向算出手段と
を具え、上記経路算出手段は、対応する上記計算点及び上記法線方向を上記経路情報として出力するようにした
ことを特徴とする請求項２に記載のキー信号生成装置。
【請求項７】
任意の実数座標における上記画像の値を算出する画像補間手段を具え、
上記エツジ強度ピーク検出手段による上記エツジを横切る方向における上記エツジ強度最大値の検出、又は上記エツジ強度断面積算出手段による上記エツジを横切る方向における上記エツジ強度断面積の算出が行われる
ことを特徴とする請求項２に記載のキー信号生成装置。
【請求項８】
画像中からキー信号を生成するキー信号生成方法において、
上記対象物の輪郭についての輪郭領域を決定する輪郭領域決定ステツプと、
上記輪郭領域におけるグラデイエントベクトルを算出するグラデイエントベクトル算出ステツプと、
上記輪郭領域におけるグラデイエントベクトルに基づき、上記輪郭領域にエツジに沿つて上記エツジの内側及び外側における境界位置をそれぞれ複数抽出し、当該各境界位置を表す境界座標情報を上記エツジの内側及び外側毎に生成して出力する境界座標抽出ステツプと、
上記境界座標抽出手段の出力に基づき、上記各境界座標情報によつて表される各形状を近似する２本の境界曲線を上記対象物の輪郭として生成する境界曲線生成ステツプと、
上記境界曲線生成ステツプの出力に基づいて、上記２本の境界曲線間に形成する曲面の形状を決定する曲面制御情報を算出して出力する曲面制御情報算出ステツプと、
上記曲面制御情報算出ステツプの出力に基づいて、上記各境界曲線によつて挟まれた領域上に曲面を生成し、当該曲面をキー情報として出力する曲面生成ステツプと
を具えることを特徴とするキー信号生成方法。
【発明の詳細な説明】
【０００１】
【目次】
以下の順序で本発明を説明する。
発明の属する技術分野
従来の技術
発明が解決しようとする課題
課題を解決するための手段
発明の実施の形態
（１）全体構成（図１）
（２−１）境界抽出部の構成（図２〜図１６）
（２−１−１）境界座標抽出部の構成（図８及び図９）
（２−１−１−１）経路算出部の構成（図１０及び図１１）
（２−１−１−２）エツジ強度ピーク検出部及びエツジ強度断面積算出部の構成（図１２〜図１４）
（２−１−２）境界曲線生成部の構成（図１５及び図１６）
（２−２）ソフトキー生成部の構成（図１７及び図１８）
（２−３）実施例の動作及び効果
（３）他の実施例（図１９〜図２１）
発明の効果
【０００２】
【発明の属する技術分野】
本発明は輪郭抽出装置、輪郭抽出方法、キー信号生成装置及びキー信号生成方法に関し、例えばテレビジヨンや映画等の映像制作における特殊効果処理において、画像中から注目する物体の画像を抽出し、当該抽出した物体画像を他の画像に合成する際に適用して好適なものである。
【０００３】
【従来の技術】
従来、この種の特殊効果処理においては、抽出した部分画像を他の画像に合成する際にはソフトキーを用いるようになされており、画像から任意の部分画像を抽出する際の精度が重要となる。この抽出作業においては、エツジ検出、領域検出及び既知物体との対応付け等の処理が必要であり、特に画像中の背景や対象物が複雑である場合には、対象物の輪郭を構成するエツジを精度良く検出して追跡する必要がある。
【０００４】
ここでエツジ検出とは、濃淡画像内で画素値が急激に変化している部分を検出する処理（色変化を検出する処理）である。通常、このような画素値の急激な変化は、対象物体の輪郭で発生するため、エツジ検出の結果に基づいて画像から対象物体の輪郭を抽出することができる。この輪郭抽出は、物体の認識、物体の追尾及び画像合成等において使用される基本的かつ重要な技術である。従つてエツジ検出は、画像から対象物体に関する情報を得るための最も基本的な技術であると言える。
【０００５】
このように画像中から対象物の輪郭を抽出する輪郭抽出方法として、「画像合成のための対象物抽出法」（井上誠善、電子情報通信学会論文誌、vol.J74-D-IINo.10 、pp.1411-1418、1991）、「領域抽出方法」（特開平3-17680 号）、「領域分割に基づく複雑物体の自動切り出し」（栄藤稔、白井良明、 NICOGRAPH′92論文集、pp.8-17 、1992）、「領域抽出装置」（特開平5-61977 号）、「弾性輪郭モデルとエキルギー最小化原理による輪郭追跡手法」（上田修功、間瀬健二、末永康仁、信学誌、Vol.J-75-D-II 、No.1、pp.111-120、1992）、「動物体の輪郭追跡方法」（特開平5-12443 号）、「Intelligent Scissors for Image Composition」（Eric N. Mortensen and William A. Barrett、Computer Graphics Proceedings 、Annual Coference Series 、1995、ACM SIGGRAPH  、pp.191-198）などが知られている。
これらの輪郭抽出方法においては、対象物の輪郭のほぼ中心を通過するように輪郭を１本の曲線又は線図形画像として抽出する。
【０００６】
画像合成処理においては、注目する対象物の領域を切り抜くために、まず対象物の輪郭を抽出する処理を行うことが多い。上述した輪郭抽出方法は、画像合成処理に適用するためのものである。
一般に、画像合成処理においては、画像を合成した結果の合成画像Ｉは、前景画像Ｆと背景画像Ｂより次式
【数１】
0003812763.tif 000002
を用いて算出される。ここでαは、各画素において色の混合比を決定するキー情報である。
【０００７】
一般に画像における物体の輪郭は、撮像系のフイルタ効果及び物体の運動に起因するぼけのために、ある有限の太さをもつた領域である。この輪郭領域は、本来の物体の色と背景の色とが混合した色をもつている。キー情報の変化と輪郭の色の変化が一致していない場合には、輪郭領域において変色した画素を合成することになるので、合成画像の品質が著しく低下する。このような問題を解決するための方法として、輪郭領域においてキーを緩やかに変化させ、輪郭の色の変化に近づけるようにする方法がある。ここでαが「０」（又は「１」）から「１」（又は「０」）に急激に変化するキーをハードキーと呼び、上述の方法で緩やかに変化するキーをソフトキーと呼ぶ。
【０００８】
すなわち画像のうち注目する対象物を前景（前景画像）とし、それ以外の部分を背景（背景画像）とした場合、画像における前景領域を「１」とすると共に、背景領域を「０」とした２値のキー情報をハードキーと呼ぶ。これに対して、画像にはエイリアスやモーシヨンブラー（動きぼけ）が生ずるが、これらを考慮して、「０」から「１」の範囲の連続した実数値をもつキー情報をソフトキーと呼ぶ。従つてハードキーは、急峻な境目を有する信号（キー信号が「０」（又は「１」）から「１」（又は「０」）に変わる境目の傾斜が急峻な信号）であり、ソフトキーは、滑らかな境目を有する信号（キー信号が「０」（又は「１」）から「１」（又は「０」）に変わる境目の傾斜が滑らかな信号）となる。
【０００９】
この輪郭領域にソフトキーを生成する方法として、「画像合成装置」（特開昭60-232787 号）がある。この「画像合成装置」においては、ハードキーを得た後、このハードキーを用いて輪郭領域を平滑化することにより、輪郭領域をぼかして、見た目上滑らかにするものである。また「画像合成におけるアンチエイリアシング方法」（特開平4-340671号）に記載されている方法は、ハードキー２値画像における輪郭領域の画素パターンを観察し、適当な中間値のαに置き換えることによりソフトキーを得るものである。
【００１０】
しかしながらこれら２つのソフトキー生成方法によつて生成されたソフトキーは、グレー領域（「０」から「１」までの間の値をとる領域）における値が一様なものであるため、例えば前景が動いている場合に生ずるモーシヨンブラーに対処することが困難であつた。
このような問題を解決するためのソフトキー生成方法として、「映像信号合成装置」（特開平5-143493号）、「動画像のための対象物の抽出とはめ込み法」（井上誠善、小山広毅、テレビジヨン学会誌、Vol.47、No.7、pp.999-1005 、1993）及び「ソフトキー生成装置」（特開平5-236347号）がある。
【００１１】
「映像信号合成装置」に記載されている方法は、フレーム間の画素値の変化を検出することにより、この画素値の変化に基づいて物体が移動したか否かを判断し、画素値の変化の大きさに基づいてソトフキーを生成するものである。また「動画像のための対象物の抽出とはめ込み法」及び「ソフトキー生成装置」に記載されている方法は、予め得たハードキーを、物体内部に向かつてα値を削つていくことによりソフトキーを生成するものである。このとき、物体の重心の運動方向と輪郭の各場所におけるエツジ強度を検出し、物体運動によるぶれの影響をαの削り量に反映させている。
【００１２】
【発明が解決しようとする課題】
ところで上述のように、画像における物体の輪郭は、撮像系のフイルタ効果及び物体の運動に起因するぼけのために、ある有限の太さをもつた領域であり、本来の物体の色と背景の色が混合した色をもつている。
ところが上述したソフトキー生成方法は、上述した輪郭抽出方法を用いてハードキーを生成し、このハードキーの輪郭部におけるα値の変化を適当に緩やかにする操作を行うことによりソフトキーを生成しているため、ハードキーを作成した時点において物体色と背景色とが混合した輪郭領域の太さについての情報が失われ、ソフトキーのα値が緩やかに変化する領域と画像の輪郭領域とが一致せず、ソフトキーを精度良く生成することができなかつた。
【００１３】
このような問題を解決する１つの方法として、画像勾配情報を用いることによりソフトキーを精度良く生成することができる。この画像勾配情報を用いたソフトキー生成方法として上述の「ソフトキー生成装置」がある。ところがこの「ソフトキー生成装置」の場合、物体運動によるキーのぶれを確実に回避することができず、また画像勾配を分離して処理したり、予め得たハードキーの内側だけにソフトキー領域を作成するなど、本来の画像勾配とソフトキーの物理的関係とが異なる経験則的な手法を用いているために、ソフトキーを精度良く生成するには実用上未だ不十分であつた。
【００１４】
また上述した「映像信号合成装置」に記載されている方法は、フレーム間の画像勾配を検出することによりキーのぶれ量を推測しているが、通常の画像フレームレートは24フレーム／秒、25フレーム／秒又は30フレーム／秒程度であるため、画像上を高速に運動する物体のぶれ量を正確に測定することは困難であり、このためソフトキーを精度良く生成することができなかなつた。
【００１５】
本発明は以上の点を考慮してなされたもので、対象物の輪郭を表す２本の境界曲線を抽出することにより、キー情報を精度良く生成することのできる輪郭抽出装置、輪郭抽出方法、キー信号生成装置及びキー信号生成方法を提案しようとするものである。
【００１６】
【課題を解決するための手段】
かかる課題を解決するため本発明においては、画像中からキー信号を生成するキー信号生成装置において、対象物の輪郭についての輪郭領域を決定する輪郭領域決定手段と、輪郭領域におけるグラデイエントベクトルを算出するグラデイエントベクトル算出手段と、輪郭領域におけるグラデイエントベクトルに基づき、輪郭領域のエツジに沿つてエツジの内側及び外側における境界位置をそれぞれ複数抽出し、当該各境界位置を表す境界座標情報をエツジの内側及び外側毎に生成して出力する境界座標抽出手段と、境界座標抽出手段の出力に基づき、各境界座標情報によつて表される各形状を近似する２本の境界曲線を対象物の輪郭として生成する境界曲線生成手段と、境界曲線生成手段の出力に基づいて、２本の境界曲線間に形成する曲面の形状を決定する曲面制御情報を算出して出力する曲面制御情報算出手段と、曲面制御情報算出手段の出力に基づいて、各境界曲線によつて挟まれた領域上に曲面を生成し、当該曲面をキー情報として出力する曲線生成手段とを具え、曲面制御情報算出手段は、境界曲線のうち一方の境界曲線をｚ＝１の平面上に位置させると共に、境界曲線のうち他方の境界曲線をｚ＝０の平面上に位置させ、当該境界曲線を相対する縁とする曲線を生成するような曲面制御情報を算出する。
【００１７】
本発明によれば、輪郭領域を囲む２本の境界曲線間に当該境界曲線間を縁とするような曲面が生成されるので、対象物の色が混合する輪郭領域とソフトキー情報の位置とを一致させたキー情報を生成することができる。
【００１８】
【発明の実施の形態】
以下、図面について本発明の一実施例を詳述する。
【００１９】
（１）全体構成
図１において、１は全体として本発明を適用したキー信号生成装置を示し、連続した複数の画像中に存在する対象物の輪郭領域にソフトキーを生成する。
キー信号生成装置１は、輪郭抽出部２及びソフトキー生成部３により構成されている。
【００２０】
キー信号生成装置１は、マウスやタブレツト等の２次元ポインテイングデバイスを入力手段としてオペレータによつて入力された、輪郭のおおまかな形状を示す線分情報、折れ線情報、曲線情報、又は太い筆でなぞつたようなマスク画像情報Ｓ１を、輪郭抽出部２の推定輪郭算出部５で受ける。推定輪郭算出部５は、輪郭領域決定手段として線分情報、折れ線情報、曲線情報又はマスク画像情報Ｓ１に基づいて対象物の輪郭の推定形状（以下、これを推定輪郭と呼ぶ）に応じた推定輪郭情報Ｓ２を得、当該推定輪郭情報Ｓ２を輪郭候補領域決定部６に送出する。
【００２１】
輪郭候補領域決定部６は、輪郭領域決定手段として、推定輪郭情報Ｓ２に基づいて、輪郭が存在すると考えられる領域（以下、これを輪郭候補領域と呼ぶ）を算出し、当該輪郭候補領域に応じた輪郭候補領域情報Ｓ３をグラデイエントベクトル算出部７に送出する。グラデイエントベクトル算出部７は、グラデイエントベクトル算出手段として、輪郭候補領域情報Ｓ３に基づいて輪郭候補領域におけるグラデイエント強度（エツジ強度）を算出することにより輪郭のグラデイエントベクトルを算出した後、当該グラデイエントベクトルに基づいてエツジ強度画像Ｇを生成し、エツジ強度画像Ｇを輪郭経路探査部８及び境界抽出部９に送出する。
【００２２】
輪郭経路探査部８は、エツジ強度画像Ｇに基づいて、輪郭の中心を通過する画素のリスト（以下、これを輪郭座標リストと呼ぶ）Ｄを生成し、当該輪郭座標リストＤを曲線生成部１０に送出する。曲線生成部１０は、輪郭座標リストＤに基づいて得られる輪郭を曲線近似することにより輪郭曲線を生成し、当該輪郭曲線に応じた輪郭曲線情報Ｃを境界抽出部９に送出する。
【００２３】
ここでこのキー信号生成装置１においては、線分情報、折れ線情報、曲線情報又はマスク画像情報Ｓ１より推定輪郭情報Ｓ２を得る方法とは別に、１つ前のフレームである画像ｉ−１の輪郭曲線情報Ｃを用い、動きベクトル推定処理によつて画像ｉ−１の輪郭曲線が現画像ｉにおいてどこに移動したかを推定することにより、現画像ｉにおける推定輪郭情報Ｓ２を得ることができるようになされている。
【００２４】
すなわち動きベクトル推定部１１は、１つ前の画像ｉ−１について、輪郭候補領域決定部６、グラデイエントベクトル算出部７、輪郭経路探査部８、曲線生成部１０を介して得られる輪郭曲線情報Ｃを用いて、当該輪郭曲線情報Ｃに応じた輪郭曲線が現画像ｉにおいてどこに移動したかを推定し、この結果を推定輪郭情報Ｓ２として輪郭候補領域決定部６に送出する。この場合、輪郭候補領域決定部６から曲線生成部１０までの処理は、上述と同様の方法で行われる。
従つて推定輪郭情報Ｓ２を得る方法として動きベクトル推定部１１が選択された場合、曲線生成部１０は、輪郭曲線情報Ｃを遅延回路１２を介して動きベクトル推定部１１にフイードバツクするようになされている。
【００２５】
境界抽出部９はエツジ強度画像Ｇ及び輪郭曲線情報Ｃに基づいて、対象物の輪郭に相当する領域を囲むような２本の境界曲線Ｃ０及びＣ１を生成し、これら２本の境界曲線Ｃ０及びＣ１をソフトキー生成部３に送出する。ソフトキー生成部３は、これら境界曲線Ｃ０及びＣ１間の幅を算出し、当該境界曲線Ｃ０及びＣ１間の幅に基づいて２本の境界曲線間に高さが「０」から「１」まで滑らかに変化する曲面を生成し、この曲面の高さをソフトキーＫの値として画像に書き込む処理を行つてソフトキーＫを算出し出力する。
【００２６】
この場合、ソフトキー生成部３は、対象物の内部側の境界曲線を境界として対象物の内部側領域におけるキー情報を「１」とし、対象物の外部側領域におけるキー情報を「０」とすることにより、ソフトキーＫを生成する。
ここで、後述するように、生成されたソフトキーＫは画像（ｘ、ｙ）のキー情報をｚ値にもつような曲面で定義されたものである。画像合成処理においては、各画素のキー情報が与えられなければならないが、ここで言う曲面で定義されたキーから曲面のｚ値を画像平面上に曲面を垂直に投影した位置に書き込む処理を行うことによりキー画像を得ることができる。この実施例においては、曲面でキー情報を定義したものを含めてソフトキーと呼ぶ。
【００２７】
かくしてこのキー信号生成装置１は、画像中に存在する対象物の輪郭領域にソフトキーＫを精度良く生成することができるようになされている。
【００２８】
（２−１）境界抽出部の構成
本発明の実施例による境界抽出部９の構成を図２に示し、境界抽出部９における境界抽出処理の処理手順について図３に示すフローチヤートを用いて説明する。
境界抽出部９は、境界抽出手段として、ステツプＳＰ１より境界抽出処理を開始し、ステツプＳＰ２及びステツプＳＰ３において、それぞれエツジ強度画像Ｇ（ｘ、ｙ）及び輪郭曲線情報Ｃを境界座標抽出部２１で受ける。
【００２９】
ステツプＳＰ４において、境界抽出部９は、境界座標抽出部２１において、エツジ強度画像Ｇ及び輪郭曲線情報Ｃに基づき、対象物の輪郭のエツジ強度が対象物の内部側領域において所定のしきい値以下となる点ｐ０0 〜ｐ０m-1 を境界位置として輪郭に沿つて複数抽出し、当該抽出した境界位置ｐ０0 〜ｐ０m-1 の座標を表す境界座標リストＰ０を境界座標情報として生成すると共に、対象物の輪郭のエツジ強度が対象物の外部側領域において所定のしきい値以下となる点ｐ１0 〜ｐ１n-1 を境界位置として輪郭に沿つて複数抽出し、当該抽出した境界位置ｐ１0 〜ｐ１n-1 の座標を表す境界座標リストＰ１を境界座標情報として生成し、これら境界座標リストＰ０及びＰ１を境界曲線生成部２２に送出する。
【００３０】
ステツプＳＰ５において、境界抽出部９は、境界曲線生成部２２において、境界座標リストＰ０及びＰ１に基づき、境界座標リストＰ０によつて表される形状を近似する近似曲線（曲線セグメント）ｃ０0 〜ｃ０k-1 を生成してこれら近似曲線ｃ０0 〜ｃ０k-1 で構成される境界曲線Ｃ０を生成すると共に、境界座標リストＰ１によつて表される形状を近似する近似曲線ｃ１0 〜ｃ１l-1 を生成してこれら近似曲線ｃ１0 〜ｃ１l-1 で構成される境界曲線Ｃ１を生成し、ステツプＳＰ６においてこれら２本の境界曲線Ｃ０及びＣ１をソフトキー生成部３に送出する。
【００３１】
（２−１−１）境界座標抽出部の構成
この実施例の場合、境界抽出部９は、図４（Ａ）に示すように、まずエツジ近傍の適当な位置ｐｏをエツジの方向に沿つて適当な間隔で決めた後、各位置ｐｏにおけるエツジの法線方向を算出し、このエツジの法線方向に平行で長さが「１」のベクトルｐｄを決定する。ここで位置ｐｏは、エツジの近傍にあればどこでもよい。
【００３２】
次に境界抽出部９は、各位置ｐｏと当該位置ｐｏでのベクトルｐｄによつて決まるエツジを横切る経路Ｐ上において、後述する境界位置検出方法によつてエツジの境界位置ｐ０i 及びｐ１i を検出する（図４（Ｂ））。すなわち境界抽出部９は、各経路Ｐ上においてエツジ強度断面の面積を測定すると共に、エツジ強度が最大となるエツジ強度最大位置ｐｃi と当該エツジ強度最大位置ｐｃi でのエツジ強度値ｈi とを求め、エツジ強度最大値ｈi に等しい高さと、エツジ強度最大位置ｐｃi を底辺の中心位置に有し、かつ算出したエツジ強度断面の面積に等しい矩形を算出した後、当該矩形の底辺における両端位置をエツジの境界位置ｐ０i 及びｐ１i として算出する。これによりエツジ強度にノイズがある場合でもエツジの境界位置ｐ０i 及びｐ１i を安定して抽出し得るようになされている。
【００３３】
かくして境界抽出部９は、対象物の内部側領域においてエツジ沿つて得られる内側境界位置ｐ０i の座標を表す境界座標リストＰ０と、対象物の外部側領域においてエツジに沿つて得られる外側境界位置ｐ１i の座標を表す境界座標リストＰ１を得ることができるようになされている。
【００３４】
ここでエツジにおける内側境界位置及び外側境界位置の検出原理について図５（Ａ）〜図５（Ｅ）を用いて説明する。図５（Ａ）は画像中において対象物の輪郭が存在する領域を模式的に表したものであり、左側の領域を色Ｂ、右側の領域を色Ｆとする。また中心に輪郭領域が存在し、輪郭領域の画像勾配を濃淡の勾配で表す。ここで輪郭を横切る方向の経路Ｐにおける色の変化の測定結果を図５（Ｂ）に示し、輪郭領域において色Ｂから色Ｆへの色の変化を観察することができる。
【００３５】
図５（Ｃ）は図５（Ｂ）における勾配、すなわち１次微分を示す。勾配の大きさは輪郭領域の境界位置、すなわち内側境界位置ａと外側境界位置ｂとの間で「０」でない値をもち、勾配の面積をｓとする。図５（Ｄ）は以降の処理を分かりやすくするため面積ｓが「１」になるように規格化したことを表すものである。。ここで勾配の大きさの最大値ｈを求め、この最大値ｈをもつ位置ｐｃの周囲に高さｈで面積「１」の矩形を求めることにより、輪郭領域における境界位置を算出し、この境界位置をそれぞれ内側境界位置ｐ０及び外側境界位置ｐ１とする。
【００３６】
ここで上述した境界位置の検出方法がノイズに対して強いことを図６及び図７を用いて説明する。図６（Ａ）はノイズを含む輪郭領域の画像勾配の大きさの一例を示す。この場合、輪郭領域の左側に陰影などの効果によつて緩やかな勾配が生じているものとする。この勾配は輪郭に起因する成分ではない。図６（Ｂ）及び図６（Ｃ）は画像勾配の大きさが小さくなる位置を直接探査し、その位置を輪郭の境界位置とする処理を用いた例を示す。画像勾配が小さくなる位置を検出するためにしきい値Ｔとして小さいしきい値を用いる。このときしきい値Ｔをわずかにしきい値Ｔ′にずらして設定すると、検出される位置ａ及び位置ｂがそれぞれ位置ａ′及び位置ｂに変化する（右側の位置ｂはほとんど影響を受けないものとする）。この方法で求めた境界位置ｐ０及びｐ１を図６に示す。この方法では、しきい値処理で検出した位置が直接境界位置となるので、設定するしきい値の大きさによつて結果が大きく変化する。
【００３７】
一方、図７（Ａ）〜図７（Ｃ）は、上述した本発明の方法で輪郭領域の境界位置を検出するプロセスを示す。図６（Ａ）と同様にノイズがある画像勾配が算出されたとする（図７（Ａ））。本発明の方法ではまず勾配の面積を計算するために画像勾配の大きさが小さくなる位置を測定する必要がある。この手順（図７（Ｂ））を図６（Ｂ）と同じにすると、上述の場合と同様に、勾配の面積を計算する領域の大きさは設定するしきい値の大きさによつて大きく変化する。しかしながら輪郭における勾配の大きさは十分に大きいため、算出した勾配の面積全体に対するノイズ領域の面積の割合は小さい。
【００３８】
勾配の面積と同じ面積の矩形を算出する過程を図７（Ｃ）に示す。ノイズ領域の面積の影響が小さいので、異なるしきい値から得られる矩形の高さｈとｈ′の違いを小さく抑えることができる。従つて図７（Ｄ）に示すように、その矩形から得られる輪郭領域の境界位置はほとんど変わらないように得ることができる。
【００３９】
ここで実際の画像においては、輪郭に起因する画像勾配成分だけでなく、物体内部のテクスチヤや陰影などに起因する成分が存在するので、上述したノイズの影響は無視できない。従つて上述した本発明の方法によればノイズの影響を実用上十分に回避することができる。
【００４０】
境界座標抽出部２１の構成を図８に示し、境界座標抽出部２１における境界抽出処理の処理手順について図９に示すフローチヤートを用いて説明する。
境界座標抽出部２１は、境界座標抽出手段として、ステツプＳＰ１より境界座標抽出処理を開始し、ステツプＳＰ２において輪郭曲線情報Ｃを経路算出部２３で受けると共に、ステツプＳＰ３において、エツジ強度画像Ｇをそれぞれエツジ強度ピーク検出部２４及びエツジ強度断面積算出部２５で受ける。
【００４１】
続いてステツプＳＰ４において、境界座標抽出部２１は、経路算出部２３において、輪郭曲線情報Ｃに基づき、輪郭曲線Ｃ上の適当な位置ｐｏi と当該位置ｐｏi でのベクトルｐｄi との対をエツジの方向に複数個（｛ｐｏ0 ，ｐｄ0 ｝、……、｛ｐｏm-1 ，ｐｄm-1 ｝）算出し、これら位置ｐｏi 及びベクトルｐｄi の対を経路情報としてエツジ強度ピーク検出部２４及びエツジ強度断面積算出部２５に送出する。
【００４２】
次いでステツプＳＰ５において、境界座標抽出部２１は、エツジ強度ピーク検出部２４において、エツジ強度画像Ｇ及び経路情報（位置ｐｏi 及びベクトルｐｄi の対）に基づき、位置ｐｏi 及びベクトルｐｄi の対で決まる各経路Ｐ上において、エツジ強度最大値ｈi を検出すると共に、当該エツジ強度最大値ｈi の位置（以下、これをエツジ強度最大位置と呼ぶ）ｐｃi を算出し、これらエツジ強度最大値ｈi 及びエツジ強度最大位置ｐｃi をそれぞれエツジ強度断面積算出部２５及び矩形算出部２６に送出する。
【００４３】
続いてステツプＳＰ６において、境界座標抽出部２１は、エツジ強度断面積算出部２５において、エツジ強度画像Ｇ、位置ｐｏi 及びベクトルｐｄi の対、エツジ強度最大値ｈi 及びエツジ強度最大位置ｐｃi に基づき、位置ｐｏi 及びベクトルｐｄi の対で決まる各経路Ｐ上において、エツジ強度を積分した値ｓi を算出し、当該積分値ｓi をエツジ強度の断面積として矩形算出部２６に送出する。
【００４４】
次いでステツプＳＰ７において、境界座標抽出部２１は、矩形算出部２６において、エツジ強度最大値ｈi 、エツジ強度最大位置ｐｃi 及び積分値ｓi に基づき、各経路Ｐ上においてエツジ強度最大位置ｐｃi を基準位置として当該基準位置から各経路Ｐ上の両側に（ｓi ／ｈi ）＊ｃだけ離れた位置を輪郭領域における境界位置、すなわち内側境界位置ｐ０i 及び外側境界位置ｐ１i として算出し（図４（Ｂ））、ステツプＳＰ８において内側境界位置ｐ０i の座標を表す境界座標リストＰ０と、外側境界位置ｐ１i の座標を表す境界座標リストＰ１を境界曲線近似部２２に送出し、ステツプＳＰ９において境界座標抽出処理を終了する。ここでｃは予め与えられた定数値であり、0.5 前後の値が用いられる。
【００４５】
（２−１−１−１）経路算出部の構成
経路算出部２３の構成を図１０に示し、経路算出部２３における経路算出処理について図１１に示すフローチヤートを用いて説明する。
経路算出部２３は、経路算出手段として、ステツプＳＰ１より経路算出処理を開始し、ステツプＳＰ２において、輪郭曲線情報Ｃを計算点抽出回路２３Ａで受ける。
【００４６】
続いてステツプＳＰ３において、経路算出部２３は、計算点抽出手段としての計算点抽出回路２３Ａにおいて、予め定めた適当な間隔ｄｔで輪郭曲線情報Ｃによつて表される曲線Ｃ上における始点から終点までｎ個の位置を計算点ｐｏi （ｐｏo 、ｐｏ1 、……、ｐｏn-1 ）として抽出してこれら計算点ｐｏi でなる計算点座標リストＰｏを生成し、ステツプＳＰ４において、計算点座標リストＰｏをエツジ強度ピーク検出部２４、エツジ強度断面積算出部２５及び方向算出回路２３Ｂに送出する。ここで曲線Ｃは、パラメータｔがｔs からｔe の範囲で定義されているものとする。また「WHILE Ａ｛Ｂ｝」は、「Ａが真である間は、処理Ｂを繰り返す」ということを意味する。
【００４７】
続いてステツプＳＰ５において、経路算出部２３は、方向算出手段としての方向算出回路２３Ｂにおいて、各計算点ｐｏi において、曲線Ｃの接線ベクトルｔｇを算出した後、当該各接線ベクトルｔｇと直角をなす単位ベクトルｐｄi を法線方向として算出してこれら単位ベクトルｐｄi でなる方向ベクトルリストＰｄを生成し、ステツプＳＰ６において、方向ベクトルリストＰｄをエツジ強度ピーク検出部２４及びエツジ強度断面積算出部２５に送出し、ステツプＳＰ７において経路算出処理を終了する。
【００４８】
（２−１−１−２）エツジ強度ピーク検出部及びエツジ強度断面積算出部の構成エツジ強度ピーク検出部２４におけるエツジ強度ピーク検出処理及びエツジ強度断面積算出部２５におけるエツジ強度断面積算出処理について図１２に示すフローチヤートを用いて説明する。
【００４９】
エツジ強度ピーク検出部２４及びエツジ強度断面積算出部２５は、ステツプＳＰ１よりエツジ強度ピーク検出処理及びエツジ強度断面積算出処理を開始し、ステツプＳＰ２において、それぞれエツジ強度画像Ｇ、計算点座標リストＰｏ及び方向ベクトルリストＰｄを受ける。
【００５０】
続いてステツプＳＰ３において、エツジ強度ピーク検出部２４は、エツジ強度ピーク検出手段として計算点座標リストＰｏ及び方向ベクトルリストＰｄのそれぞれ対応する計算点ｐｏi 及び単位ベクトルｐｄi によつて決まる各経路Ｐ上において、エツジ強度画像Ｇに基づきエツジ強度最大値ｈi 及びエツジ強度最大位置ｐｃi を検出してエツジ強度最大値ｈi でなるエツジ強度最大値リストＨ及びエツジ強度最大位置ｐｃi でなるエツジ強度最大位置リストＰｃを生成し、当該エツジ強度最大値リストＨ及びエツジ強度最大位置リストＰｃをエツジ強度断面積算出部２５に送出する。
ここでステツプＳＰ３において、ｋは適当なスカラを表す。
【００５１】
次いでステツプＳＰ４において、エツジ強度断面積算出部２５は、エツジ強度断面積算出手段として計算点座標リストＰｏ及び方向ベクトルリストＰｄのそれぞれ対応する計算点ｐｏi 及び単位ベクトルｐｄi によつて決まる各経路Ｐ上において、エツジの一端からエツジ強度最大位置ｐｃi を通過してエツジの他端までの区間、すなわちエツジ強度最大位置ｐｃi を基準位置として当該基準位置を中心に各経路上の両側にそれぞれ１点ずつ位置ａ及び位置ｂを境界位置として求めて当該位置ａ及び位置ｂを結ぶ線分ａｂを積分区間とし、当該積分区間ａｂにおけるエツジ強度値の総和を計算することによりエツジ強度の断面積ｓi を算出し、断面積ｓi でなる断面積リストＳを生成する。これにより最初に与えられた輪郭を横切る経路があいまいな場合でも、輪郭を正しく横切るようにエツジ強度の断面積を算出し得るようになされている。
【００５２】
ここで位置ａ及び位置ｂを求める処理は、エツジ強度最大位置ｐｃi を基準位置として、エツジ強度が予めエツジ強度最大値ｈi のスカラｋ倍で設定したしきい値より最初に小さくなる位置を、基準位置を中心に経路Ｐに沿つて両方向に順次探査することにより行われる。図１２のステツプＳＰ４において、ｄは経路Ｐ上のエツジ強度をサンプルするために予め定めたスカラである。
【００５３】
次いでステツプＳＰ５において、エツジ強度ピーク検出部２４は、エツジ強度最大位置リストＰｃ及びエツジ強度最大値リストＨを矩形算出部２６に送出し、エツジ強度断面積算出部２５は、断面積リストＳを矩形算出部２６に送出し、ステツプＳＰ６においてエツジ強度ピーク検出処理及びエツジ強度断面積算出処理を終了する。
【００５４】
実際上、図１３に示すように、エツジ強度断面積算出部２５は、積分区間算出回路２５Ａ及び積分回路２５Ｂによつて構成されている。積分区間算出回路２５Ａは、エツジ強度最大位置ｐｃi を基準位置として、エツジ強度がエツジ強度最大値ｈi のスカラｈ倍で設定したしきい値より最初に小さくなる経路上の２点を、基準位置を中心に両方向に経路端点ａ及びｂとして算出し、端点ａ及びｂを結ぶ線分ａｂを積分区間ａｂとして算出し、各経路Ｐ上において算出した積分区間ａｂでなる積分区間リストＡＢを積分回路２５Ｂに送出する。積分回路２５Ｂは、積分区間リストＡＢを基に、各積分区間ａｂおけるエツジ強度値を積分することにより、エツジ強度の断面積ｓi を算出し、断面積ｓi でなる断面積リストＳを生成して矩形算出部２６に送出する。
【００５５】
ここで上述のように、エツジ強度ピーク検出部２４及びエツジ強度断面積算出部２５は、エツジを横切る経路Ｐ上の点におけるエツジ強度値を算出する必要がある。この場合、経路Ｐ上の位置は必ずしも画素格子上にあるとは限らないので、この実施例においては、エツジ強度ピーク検出部２４及びエツジ強度断面積算出部２５は、サブピクセル精度の計算を実現するものとして画像補間手段（図示せず）を有する。この画像補間手段は、画素格子上にない位置におけるエツジ強度値を得るために、画像と実数座標とを入力とし、実数座標上の画像値を出力するようになされている。
【００５６】
画像補間手段における画像補間処理について図１４に示すフローチヤートを用いて説明する。
画像補間手段は、ステツプＳＰ１より画像補間処理を開始し、ステツプＳＰ２及びステツプＳＰ３において、それぞれ画像Ｉi （ｘ、ｙ）及び実数座標（ｘｆ、ｙｆ）を受けた後、ステツプＳＰ４において、補間フイルタの重み関数を定義する。
【００５７】
ここで補間フイルタの重み関数としては、「画像理解のためのデイジタル画像処理（Ｉ）」（鳥脇純一郎、昭晃堂）、「画像解析ハンドブツク」（高木幹雄、下田陽久、東京大学出版会、1991）に記載されている方法を利用する。例えば次式
【数２】
0003812763.tif 000003
で表される関数を用いることができる。ここでｘ＊＊ｙはｘのｙ乗を表す。
【００５８】
次いで画像補間手段は、ステツプＳＰ５において、画像Ｉi と重み関数の畳み込みを計算することにより、関数Ｉｃ（ｘ、ｙ）を作成した後、ステツプＳＰ６において、当該関数Ｉｃを実数座標上の画像値として出力し、ステツプＳＰ７において画像補間処理を終了する。
かくしてエツジ強度ピーク検出部２４及びエツジ強度断面積算出部２５は、それぞれエツジ強度最大値ｈi 及びエツジ強度断面積ｓi を精度良く算出し得るようになされている。
【００５９】
（２−１−２）境界曲線生成部の構成
境界曲線生成部２２の構成を図１５に示す。境界曲線生成部２２は、境界曲線生成手段として、境界座標抽出部２１から供給される境界座標リストＰ０及びＰ１を、それぞれ入力座標分割回路２２Ａ、連結条件算出回路２２Ｂ及び曲線近似回路２２Ｃで受ける。入力座標分割回路２２Ａは、それぞれ境界座標リストＰ０及びＰ１によつて表される各形状をそれぞれ分割する分割点（｛ｅ０0 、ｅ０1 、……、ｅ０m-1 ｝、｛ｅ１0 、ｅ１1 、……、ｅ１m-1 ｝）の座標リスト（以下、これを分割点座標リストと呼ぶ）Ｅ０及びＥ１を生成し、これを連結条件算出回路２２Ｂ及び曲線近似回路２２Ｃに送出する。
【００６０】
すなわち入力座標分割回路２２Ａは、それぞれ境界座標リストＰ０及びＰ１における境界位置ｐ０i 及びｐ１i の離散的な並びから、求める形状の次数を局所的に推定する。この場合、境界座標リストＰ０及びＰ１は分割された各セグメントにおける形状の次数が大きくならないように分割する。例えば各分割点を曲率の大きさに基づいて決定することにより、座標データ数に依存せずに各セグメントにおける次数を決定することができるので、各セグメントにおける次数が大きくなることを防止し得るようになされている。
【００６１】
連結条件算出回路２２Ｂは、境界座標リストＰ０及びＰ１と分割点座標リストＥ０及びＥ１とに基づいて、それぞれ各分割点における連結条件、すなわちＧ１連続性を満たす連結条件を算出し、連結条件リストＲＶ０及びＲＶ１として曲線近似回路２２Ｃに送出する。すなわち連結条件算出回路２２Ｂは、分割点座標リストＰ０における各分割点の連結位置を一致させるための連結位置の座標ｒ０i と、連結位置ｒ０i における速度方向を一致させるための速度ベクトルｖ０i との対（すなわち接線）を連結条件リストＲＶ０として算出すると共に、分割点座標リストＰ１における各分割点の連結位置を一致させるための連結位置の座標ｒ１i と、連結位置ｒ１i における速度方向を一致させるための速度ベクトルｖ１i との対（すなわち接線）を連結条件リストＲＶ１として算出する。この場合、連結位置の座標と分割点の座標とは必ずしも一致しない。
【００６２】
曲線近似回路２２Ｃは、隣接する分割点で区切られる各セグメントを、これら分割点における連結条件を満たすように最小２乗法を用いて曲線近似することにより、隣接する分割点間における近似曲線ｃ０i 及びＣ１i を曲線セグメントｃ０i 及びｃ１i として算出し、当該曲線セグメントｃ０i でなる近似曲線群及び曲線セグメントｃ１i でなる近似曲線群をそれぞれ境界曲線Ｃ０及びＣ１としてソフトキー生成部３に送出する。これによりエツジ強度にノイズが含まれている場合でも、境界曲線Ｃ０及びＣ１を精度良く生成することができるようになされている。
【００６３】
境界曲線生成部２２における境界曲線生成処理について図１６に示すフローチヤートを用いて説明する。ここでは境界座標リストＰ０から境界曲線Ｃ０を生成する場合について説明する。
【００６４】
境界曲線生成部２２は、ステツプＳＰ１より境界曲線生成処理を開始し、ステツプＳＰ２において、境界座標抽出部２１から境界座標リストＰ０を受け、ステツプＳＰ３において、境界座標リストＰ０に基づいて分割点（ｅ０0 、ｅ０1 、……、ｅ０m-1 ）でなる分割点座標リストＥ０を作成する。続いて境界曲線生成部２２は、ステツプＳＰ４において、境界座標リストＰ０及び分割点座標リストＥ０に基づいて、各分割点ｅ０i 近傍における形状に近似した近似曲線を算出し、当該近似曲線における分割点ｅ０i 近傍での連結位置ｒ０i 及び速度ベクトルｖ０i （接線）を、各セグメントを曲線近似するための連結条件ＲＶ０として算出する。
【００６５】
次いで境界曲線生成部２２は、ステツプＳＰ５において、隣接する分割点ｅ０i 及びｅ０i+1 で区切られる各セグメントを、これら分割点ｅ０i 及びｅ０i+1 における連結条件ｒ０i 、ｖ０i ｒ０i+1 及びｖ０i+1 を満たすように最小２乗法を用いて曲線近似することにより得られる近似曲線を曲線セグメントｃ０i として算出し、ステツプＳＰ６において、これら曲線セグメントｃ０0 、ｃ０1 、……、ｃ０n-1 を境界曲線Ｃ０として出力し、ステツプＳＰ７において境界曲線生成処理を終了する。
【００６６】
以上の処理を境界座標リストＰ１に対して行うことにより、境界座標リストＰ１より境界曲線Ｃ１を算出し、境界曲線生成部２２は、各境界曲線Ｃ０及びＣ１をソフトキー生成部３に送出する。
【００６７】
（２−２）ソフトキー生成部の構成
ソフトキー生成部３の構成を図１７に示し、ソフトキー生成部３におけるソフトキー生成処理について図１８に示すフローチヤートを用いて説明する。
ソフトキー生成部３は、ステツプＳＰ１よりソフトキー生成処理を開始し、ステツプＳＰ２において、境界曲線Ｃ０及びＣ１を曲面制御情報算出回路３Ａで受ける。
【００６８】
次いでステツプＳＰ３において、ソフトキー生成部３は、曲面制御情報算出手段としての曲面制御情報算出回路３Ａにおいて、対応する近似曲線ｃ０i 及びｃ１i 毎に曲面を生成するための曲面制御情報ｆ０i 及びｆ１i を算出し、当該曲面制御情報ｆ０i 及びｆ１i を曲面生成回路３Ｂに送出する。ここで曲面制御情報ｆ０及びｆ１は（ｘ、ｙ、ｚ）空間上の曲線である。（ｘ、ｙ）平面は画像に平行であり、ｚ軸は画像に垂直である。ｉ番目の曲面制御情報ｆ０i はｚ＝０の平面上に曲線セグメントｃ０i を描いたものである。また曲面制御情報ｆ１i はｚ＝１の平面上に曲線セグメントｆ１i を描いたものである。
【００６９】
次いでステツプＳＰ４において、ソフトキー生成部３は、曲面生成手段としての曲面生成回路３Ｂにおいて、対応する各曲線セグメントｃ０i 及びｃ１i 毎に、それぞれ対応する曲面制御情報ｆ０i 及びｆ１i を用いて（ｘ、ｙ）空間上の曲面ｒi を生成し、曲面ｒ0 、ｒ1 、……、ｒk-1 でなる曲面群Ｒをソフトキー情報Ｋとして出力する。ここでｉ番目の曲線セグメントにおける曲面ｒi は次式
【数３】
0003812763.tif 000004
のようにパラメータｓで表現できる。
【００７０】
（２−３）実施例の動作及び効果
以上の構成において、このキー信号生成装置１は、エツジ強度画像Ｇに基づいて、輪郭領域のエツジに沿つてエツジの内側及び外側における境界位置をそれぞれ複数抽出し、エツジの内側及び外側毎に各境界位置の座標を表す境界座標リストＰ０及びＰ１を作成し、境界座標リストＰ０によつて表される形状を近似する境界曲線Ｃ０を生成すると共に、境界座標リストＰ１によつて表される形状を近似する境界曲線Ｃ１を生成する。
【００７１】
続いてキー信号生成装置１は、境界曲線Ｃ０及びＣ１に基づいて、対応する曲線セグメントｃ０i 及びｃ１i 毎に曲面を生成するための曲面制御情報ｆ０i 及びｆ１i を算出した後、対応する曲線セグメントｃ０i 及びｃ１i 毎に、それぞれ対応する曲面制御情報ｆ０i 及びｆ１i を用いて曲面ｒi を生成し、これら曲面ｒi でなる曲面群Ｒをソフトキー情報Ｋとして出力する。
【００７２】
従つてこのキー信号生成装置１は、対象物の輪郭を、画像勾配の大きさが「０」でない領域を囲む２本の境界曲線Ｃ０及びＣ１として抽出するので、境界曲線Ｃ０及びＣ１によつて囲まれる領域にα値の勾配を作成することができる。これにより対象物の色が混合する輪郭領域の位置が必要な場合に特に有効な情報を与えることができる。
またこのキー信号生成装置１は、輪郭領域を囲む２本の境界曲線Ｃ０及びＣ１間に、当該各境界曲線Ｃ０及びＣ１を縁とするような曲面を生成したので、対象物の色が混合する輪郭領域とソフトキー情報の位置とを一致させたキー情報を生成することができる。
【００７３】
以上の構成によれば、輪郭曲線Ｃ上の点ｐｏi と当該位置ｐｏi でのベクトルｐｄi との対をエツジの方向に複数個算出し、これら位置ｐｏi 及びベクトルｐｄi で決まる各経路Ｐ上においてエツジ強度最大値ｈi 及びエツジ強度最大位置ｐｃi を算出すると共にエツジ強度を積分した値ｓi を算出し、各経路Ｐ上においてエツジ強度最大位置ｐｃi を基準位置として当該基準位置から各経路Ｐ上の両側に（ｓi ／ｈi ）＊ｃだけ離れた位置を内側境界位置ｐ０i 及び外側境界位置ｐ１i として算出し、内側境界位置ｐ０i の座標を表す境界座標リストＰ０及び外側境界位置ｐ１i の座標を表す境界座標リストＰ１によつてそれぞれ表される各形状をそれぞれ分割する分割点でなる座標リストＥ０及びＥ１を生成すると共に各分割点における連結条件ＲＶ０及びＲＶ１を算出し、隣接する分割点で区切られる各セグメントを、これら分割点における連結条件を満たすように最小２乗法を用いて曲線近似することにより、隣接する分割点間における曲線セグメントｃ０i 及びＣ１i を算出した後、対応する曲線セグメントｃ０i 及びｃ１i 毎に曲面制御情報ｆ０i 及びｆ１i を作成し、対応する曲線セグメントｃ０i 及びｃ１i 毎に、それぞれ対応する曲面制御情報ｆ０i 及びｆ１i を用いて曲面ｒi を生成し、これら曲面ｒi でなる曲面群Ｒをソフトキー情報Ｋとして出力したことにより、対象物の輪郭を、画像勾配の大きさが「０」でない領域を囲む２本の境界曲線Ｃ０及びＣ１として抽出し得るので、境界曲線Ｃ０及びＣ１によつて囲まれる領域にα値の勾配を作成することができると共に、輪郭領域を囲む２本の境界曲線Ｃ０及びＣ１間に当該各境界曲線Ｃ０及びＣ１を縁とするような曲面Ｒを生成したので、対象物の色が混合する輪郭領域とソフトキー情報の位置とを一致させたキー情報を生成することができる。
かくしてキー情報を精度良く生成することのできる輪郭抽出部２、輪郭抽出方法、キー信号生成装置１及びキー信号生成方法を実現することができる。
【００７４】
また上述の構成によれば、グラデイエントベクトルに基づいて輪郭座標リストＤを作成し、当該輪郭座標リストＤによつて表される形状を近似することによつて得た輪郭曲線情報Ｃに基づいて、計算点座標リストＰｏ及び方向ベクトルリストＰｄを算出したので、対象物の輪郭領域とソフトキーの位置とを一段と一致させたキー情報を生成することができる。
【００７５】
さらに上述の構成によれば、エツジを横切る経路Ｐ上における点のエツジ強度を算出する際、画像補間手段を用いてサブピクセル精度で経路Ｐ上における点のエツジ強度を算出したので、エツジ強度最大値ｈi 及びエツジ強度断面積ｓi の精度を格段的に向上させることができる。
【００７６】
さらに上述の構成によれば、エツジを横切る方向においてエツジ強度最大値ｈi 及びエツジ強度断面積ｓi を算出し、エツジ強度最大値ｈi 及びエツジ強度断面積ｓi に基づいて内側境界位置ｐ０i 及び外側境界位置ｐ１i を算出したので、エツジ強度にノイズがある場合でも、対象物の輪郭領域を精度良く抽出することができる。
【００７７】
さらに上述の構成によれば、計算点座標リストＰｏ及び方向ベクトルリストＰｄのそれぞれ対応する計算点ｐｏi 及び単位ベクトルｐｄi によつて決まる各経路Ｐ上において、エツジ強度最大位置ｐｃi を基準位置として当該基準位置から各経路Ｐ上の両側にそれぞれ１点ずつ位置ａと位置ｂとを経路端点として求めて当該端点ａ及び端点ｂを結ぶ線分ａｂを積分区間とし、当該積分区間ａｂにおけるエツジ強度値の総和を計算することによりエツジ強度の断面積ｓi を算出したので、最初に与えられた輪郭を横切る経路があいまいでも実際の輪郭を正しく横切るように断面積を算出することができ、これにより対象物の輪郭領域を精度よく抽出することができる。
【００７８】
さらに上述の構成によれば、境界座標リストＰ０、Ｐ１及び分割点座標リストＥ０、Ｅ１に基づいて、各分割点近傍における形状に近似した近似曲線を算出し、当該近似曲線における分割点近傍での接線ｒ０i 、ｖ０i 及び接線ｒ１i 、ｖ１i を各セグメントを曲線近似するための連結条件ＲＶ０及びＲＶ１として算出し、隣接する分割点で区切られる各セグメントを、これら分割点における連結条件を満たすように最小２乗法を用いて曲線近似してそれぞれ曲線セグメントｃ０i 及びｃ１i を算出したので、エツジ強度にノイズが含まれている場合でも境界曲線Ｃ０及びＣ１を精度良く生成することができる。また境界曲線Ｃ０及びＣ１を滑らかに連結することができるので、ソフトキー生成部３における曲面制御処理を容易に行うことができる。
【００７９】
さらに上述の構成によれば、境界曲線Ｃ０及びＣ１の一方をｚ＝１の平面上に位置させ、他方をｚ＝０の平面上に位置させて境界曲線Ｃ０及びＣ１を縁とする曲面を生成するようにしたので、曲面制御処理を容易に行うことができると共に、ｚ値が「０」から「１」まで変化する曲面を輪郭領域において決定することができる。このｚ値をキー情報αとみなして画像に書き込むことによつてソフトキー画像を得ることができる。
【００８０】
さらに上述の構成によれば、現画像ｉと、既に輪郭曲線情報Ｃとして輪郭曲線Ｃが得られている１フレーム前の画像ｉ−１と、当該画像ｉ−１の輪郭曲線情報Ｃとに基づいて現画像ｉについての推定輪郭情報Ｓ２を得るようにしたので、オペレータが入力手段４を用いて対象物の輪郭のおおまかな形状を表す折れ線情報、曲線情報又は線図形２値画像情報をその都度入力する場合に比して、作業効率を大幅に向上させることができ、特に動画像に対して有効である。
【００８１】
（３）他の実施例
なお上述の実施例においては、経路算出手段として経路算出部２３を用いて、曲線生成部１０から供給される輪郭曲線Ｃに基づいて計算点座標リストＰｏ及び方向ベクトルリストＰｄを算出した場合について述べたが、本発明はこれに限らず、図１０との対応部分に同一符号を付した図１９に示すような経路算出部３０を用いてもよい。この経路算出部３０における経路算出処理について図２０に示すフローチヤートを用いて説明する。
【００８２】
経路算出部３０は、ステツプＳＰ１より経路算出処理を開始し、ステツプＳＰ２において、グラデイエントベクトル算出部７から供給されるエツジ強度画像Ｇを細線化手段としての細線化回路３０Ａで受けた後、ステツプＳＰ３において、エツジ強度を指標としてエツジ強度画像Ｇを細線化回路３０Ａで細線化処理することにより輪郭の位置を表す線図形２値画像Ｂ（ｘ、ｙ）を算出し、当該線図形２値画像Ｂを座標変換手段としての座標リスト変換回路３０Ｂに送出する。ここで細線化処理としては、例えば上述の「画像合成のための対象物抽出法」に記載されている方法を用いることができる。
【００８３】
また細線化回路３０Ａによつてエツジ強度画像Ｇから線図形２値画像Ｂを生成したが、例えばＣＲＴなどの表示手段の表示画面上に対象とする画像を表示し、入力手段４から画像中の対象物の軌跡を入力することにより、線図形２値画像を得るようにしてもよい。従つてこの場合には、入力手段４から入力された対象物の軌跡に応じた線図形２値画像は直接座標リスト変換回路３０Ｂに入力される。
【００８４】
続いてステツプＳＰ４において、経路算出部３０は、座標リスト変換回路３０Ｂにおいて、線図形２値画像Ｂより座標リストＬを算出し、当該座標リストＬを計算点抽出回路２３Ａ及び方向算出回路２３Ｂに送出する。この座標リストＬは、ｍ個のベクトルｌi （ｉ＝０〜ｍ−１）の配列でなる。すなわち座標リストＬは、チエーンコーデイング（Chain Coding）と呼ばれる方法を用いて、線図形２値画像Ｂのある点から線図形を辿る処理を行うことによつて画像からベクトルデータへの変換を行うことにより得ることができる。
【００８５】
次いでステツプＳＰ５において、経路算出部３０は、計算点抽出回路２３Ａにおいて、予め定めた間隔ｄｔで座標リストＬの始点から終点までｎ個の位置を計算点ｐｏとして抽出し、ステツプＳＰ６において当該計算点ｐｏでなる計算点リストＰｏを方向算出回路２３Ｂ、エツジ強度ピーク検出部２４及びエツジ強度断面積算出部２５に送出する。
【００８６】
続いてステツプＳＰ７において、経路算出部３０は、方向算出回路２３Ｂにおいて、各計算点ｐｏi における接線ベクトルｔｇを座標リストＬに基づいて算出し、ステツプＳＰ８において当該接線ベクトルｔｇと直角をなす単位ベクトル（法線方向）ｐｄi を算出し、当該単位ベクトルｐｄi でなる方向ベクトルリストＰｄをエツジ強度ピーク検出部２４及びエツジ強度断面積算出部２５に送出し、ステツプＳＰ９において経路算出処理を終了する。
【００８７】
また上述の実施例においては、境界抽出部として境界抽出部９を用いた場合について述べたが、本発明はこれに限らず、図８、図１０及び図１５との対応部分に同一符号を付した図２１に示すような境界抽出部４０を用いてもよい。
この場合、境界抽出部４０は、境界座標抽出部４１における経路算出部４２の計算点抽出回路４２Ａにおいて作成された分割点座標リストＥを境界曲線生成部４３の連結条件算出部２２Ｂで受けるようになされている。
【００８８】
すなわち計算点抽出部４２Ａは、入力される輪郭曲線情報Ｃに応じた曲線Ｃ上の位置を計算点ｐｏi として所定の間隔で抽出することにより作成した計算点リストＰｏ中の適当なサブセツトを分割座標リストＥとして作成し、これを連結条件算出部２２Ｂに送出する。ここで連結条件算出部２２Ｂには、境界座標リストＰ０及びＰ１が入力されるので、分割座標リストＥがそのサブセツトであることは保証される。
【００８９】
従つてこの境界抽出部４０は、境界抽出部９に比して入力座標分割部２２Ａの分だけ構成が簡易になり、これによりキー信号生成装置１の構成を簡略化することができる。また曲線近似部２２Ｃから出力される境界曲線Ｃ０及びＣ１をそれぞれ構成する曲線セグメントｃ０i 及びｃ１i の数は同数（すなわち図３のステツプＳＰ５においてｋ＝ｌ）となるので、ソフトキー生成部３における処理を容易にすることができる。
【００９０】
さらに上述の実施例においては、曲線生成部１０から供給される輪郭曲線情報Ｃに基づいて計算点座標リストＰｏ及び方向ベクトルリストＰｄを作成した場合について述べたが、本発明はこれに限らず、例えば推定輪郭情報Ｓ２や輪郭候補領域情報Ｓ３を用いてもよい。また対象物の輪郭についてのおおまかな形状を表す折れ線情報又は曲線情報を入力手段４から入力し、この折れ線情報又は曲線情報を用いて計算点座標リストＰｏ及び方向ベクトルリストＰｄを作成するようにしてもよい。これにより、抽出したい対象物の輪郭を指定することができるので、輪郭抽出を精度良く行うことができる。従つてキー信号生成装置１として、輪郭経路探査部８及び曲線生成部９をもたないキー信号生成装置１に本発明を適用し得る。
【００９１】
ここで入力手段４から折れ線情報又は曲線情報をそれぞれ計算点抽出回路２３Ａ及び入力座標分割回路２２Ａに直接入力させるようにしてもよい。この場合、折れ線情報に応じた折れ線の対応する線分、又は曲線情報に応じた曲線の対応するセグメントに基づいて得た境界座標リストＰ０及びＰ１における対応する境界位置ｐ０i 及びｐ１i を１つのセグメントと見なして、これら境界位置ｐ０i 及びｐ１i を分割点とすることにより、境界座標リストＰ０及びＰ１を分割する必要がなくなるので、境界曲線生成部２２の構成を入力座標分割回路２２Ａの分だけ簡略化することができ、これによりキー信号生成装置１の構成を簡略化することができる。
【００９２】
さらに上述の実施例においては、エツジ強度画像Ｇを用いて対象物の輪郭を表す境界曲線Ｃ０及びＣ１を生成した場合について述べたが、本発明はこれに限らず、グラデイエントベクトル算出部７で算出したグラデイエントベクトルに基づいて対象物の輪郭を表す境界曲線Ｃ０及びＣ１を生成してもよい。
【００９３】
【発明の効果】
上述のように本発明によれば、対象物の輪郭についての輪郭領域を決定し、輪郭領域におけるグラデイエントベクトルを算出し、輪郭領域におけるグラデイエントベクトルに基づいて、輪郭領域のエツジに沿つてエツジの内側及び外側における境界位置をそれぞれ複数抽出し、当該各境界曲線を表す境界座標情報をエツジの内側及び外側毎に生成し、各境界座標情報によつて表される各形状を近似する２本の境界曲線を対象物の輪郭として生成することにより、対象物の輪郭を、画像勾配の大きさで「０」でない領域を囲む２本の境界曲線として抽出することができるので、境界曲線によつて囲まれる領域にα値の勾配を作成することができ、さらに、画像中における対象物の輪郭について、当該輪郭における内側及び外側における境界位置を表す２本の境界曲線を生成し、各境界曲線間に形成する曲面の形状を決定する曲面制御情報を算出し、曲面制御情報に基づいて各境界曲線によつて挟まれた領域上に曲面を生成し、当該曲面をキー情報として出力することにより、輪郭領域を囲む２本の境界曲線間に当該境界曲線間を縁とするような曲面を生成することができるので、対象物の色が混合する輪郭領域とソフトキー情報の位置とを一致させたキー情報を生成することができる。
かくしてキー情報を精度良く生成することができるキー信号生成装置及びキー信号生成方法を実現することができる。
【図面の簡単な説明】
【図１】本発明を適用したキー信号生成装置の全体構成を示すブロツク図である。
【図２】境界抽出部の構成を示すブロツク図である。
【図３】境界抽出部における境界抽出処理の処理手順を示すフローチヤートである。
【図４】境界座標抽出部における境界位置抽出処理の説明に供する略線図である。
【図５】境界位置の検出原理の説明に供する略線図及びグラフである。
【図６】エツジ強度のノイズに対する強さの説明に供するグラフ及び略線図である。
【図７】エツジ強度のノイズに対する強さの説明に供するグラフ及び略線図である。
【図８】境界座標抽出部の構成を示すブロツク図である。
【図９】境界座標抽出部における境界座標抽出処理の処理手順を示すフローチヤートである。
【図１０】経路算出部の構成を示すブロツク図である。
【図１１】経路算出部における経路算出処理の処理手順を示すフローチヤートである。
【図１２】エツジ強度ピーク検出処理及びエツジ強度断面積算出処理の処理手順を示すフローチヤートである。
【図１３】エツジ強度断面積算出部の構成を示すブロツク図である。
【図１４】画像補間手段における画像補間処理の処理手順を示すフローチヤートである。
【図１５】境界曲線生成部の構成を示すブロツク図である。
【図１６】境界曲線生成部における境界曲線生成処理の処理手順を示すフローチヤートである。
【図１７】ソフトキー生成部の構成を示すブロツク図である。
【図１８】ソフトキー生成部におけるソフトキー生成処理の処理手順を示すフローチヤートである。
【図１９】他の実施例による経路算出部の構成を示すブロツク図である。
【図２０】他の実施例による経路算出部における経路算出処理の処理手順を示すフローチヤートである。
【図２１】他の実施例による境界抽出部の構成を示すブロツク図である。
【符号の説明】
１……キー信号生成装置、２……輪郭抽出部、３……ソフトキー生成部、３Ａ……曲面制御情報算出回路、３Ｂ……曲面生成回路、４……入力手段、５……推定輪郭算出部、６……輪郭候補領域決定部、７……グラデイエントベクトル算出部、８……輪郭経路探査部、９、４０……境界抽出部、１０……曲線生成部、１１……動きベクトル推定部、１２……遅延回路、２１、４１……境界座標抽出部、２２……境界曲線生成部、２２Ａ……入力座標分割回路、２２Ｂ……連結条件算出回路、２２Ｃ……曲線近似回路、２３、３０、４２……経路算出部、２３Ａ、４２Ａ……計算点抽出回路、２３Ｂ……方向算出回路、２４……エツジ強度ピーク検出部、２５……エツジ強度断面積算出部、２５Ａ……積分区間算出回路、２５Ｂ……積分回路、２６……矩形算出部、２６Ａ……積分区間算出回路、２６Ｂ……積分回路、３０Ａ……細線化回路、３０Ｂ……座標リスト変換回路。
【図１】
0003812763.tif 000005
【図２】
0003812763.tif 000006
【図８】
0003812763.tif 000007
【図３】
0003812763.tif 000008
【図４】
0003812763.tif 000009
【図５】
0003812763.tif 000010
【図６】
0003812763.tif 000011
【図７】
0003812763.tif 000012
【図９】
0003812763.tif 000013
【図１０】
0003812763.tif 000014
【図１３】
0003812763.tif 000015
【図１１】
0003812763.tif 000016
【図１２】
0003812763.tif 000017
【図１４】
0003812763.tif 000018
【図１７】
0003812763.tif 000019
【図１５】
0003812763.tif 000020
【図１６】
0003812763.tif 000021
【図１８】
0003812763.tif 000022
【図１９】
0003812763.tif 000023
【図２０】
0003812763.tif 000024
【図２１】
0003812763.tif 000025