米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> ソニー株式会社

発明の名称 領域分割処理装置および方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平9−6961
公開日 平成9年(1997)1月10日
出願番号 特願平7−149298
出願日 平成7年(1995)6月16日
代理人 【弁理士】
【氏名又は名称】稲本 義雄
発明者 新橋 龍男
要約 目的
領域の形状を、正確にリアルタイムで取得できるようにする。

構成
初期円中心点C13-1を中心とする初期円C14を設定し、この初期円C14の円周上に複数の初期節点C16を設定する。この初期節点C16を初期円C14の半径に沿った方向に直線的に移動(膨張)させ、移動後の新節点C18により構成される閉領域曲線の形状を特徴点C11の形状に近似させる。
特許請求の範囲
【請求項1】 入力信号から特徴点を検出する検出手段と、前記特徴点以外の各点の前記特徴点までの距離により一義的に規定されるポテンシャルを計算する計算手段と、前記点の前記ポテンシャルに対応して処理開始点を決定する決定手段と、前記処理開始点を基準にして複数の節点を発生させる発生手段と、前記節点を、前記接点と前記処理開始点とを結ぶ直線の延長線上で移動させる移動手段と、移動後の前記節点で囲繞される閉領域を抽出する抽出手段とを備えることを特徴とする領域分割処理装置。
【請求項2】 前記計算手段は、前記特徴点以外の点の、最も近い前記特徴点までの距離に対応して前記ポテンシャルを計算することを特徴とする請求項1に記載の領域分割処理装置。
【請求項3】 前記決定手段は、前記ポテンシャルの分布の極大点を検索し、前記極大点としての前記点のうち、前記特徴点までの距離の値の大きい順番に順序付けし、順序付けに対応して前記極大点を前記処理開始点として選択するとともに、確定した領域に含まれる前記極大点を前記処理開始点として選択しないようにすることを特徴とする請求項1に記載の領域分割処理装置。
【請求項4】 前記発生手段は、前記処理開始点を中心点とし、前記中心点の前記ポテンシャルから決まる値を半径とする円の円周を、前記半径により規定される値で複数に分割した点を前記節点とすることを特徴とする請求項1に記載の領域分割処理装置。
【請求項5】 前記移動手段は、前記発生手段によって発生された前記節点を、前記円の外側に向かって半径方向に、前記節点のポテンシャルの値により規定される長さだけ移動させることを特徴とする請求項1に記載の領域分割処理装置。
【請求項6】 前記抽出手段は、同一の前記処理開始点を基準にして発生され、移動された前記節点の間を曲線で接続して閉曲線を生成し、入力信号から前記閉曲線の位置および形状に従って信号を抜き出すことを特徴とする請求項1に記載の領域分割処理装置。
【請求項7】 入力信号から特徴点を検出し、前記特徴点以外の各点の前記特徴点までの距離により一義的に規定されるポテンシャルを計算し、前記点の前記ポテンシャルに対応して処理開始点を決定し、前記処理開始点を基準にして複数の節点を発生させ、前記節点を、前記接点と前記処理開始点とを結ぶ直線の延長線上で移動させ、移動後の前記節点で囲繞される閉領域を抽出することを特徴とする領域分割処理方法。
【請求項8】 入力信号から特徴点を検出し、複数の節点を生成し、前記節点を結んだ閉曲線を設定し、前記節点を前記特徴点に近づくように移動させ、前記閉曲線で囲まれた領域を決定する領域分割処理装置において、前記閉曲線上の点であって、前記節点とは異なる点としての中間点を選択する選択手段と、前記中間点と前記特徴点の位置から決まる値をしきい値処理し、その結果に対応して、前記中間点を前記節点として追加する処理手段とを備えることを特徴とする領域分割処理装置。
【請求項9】 前記選択手段は、前記閉曲線上の隣接する前記節点間の中点を前記中間点として選択することを特徴とする請求項8に記載の領域分割処理装置。
【請求項10】 前記選択手段は、前記閉曲線上の隣接する前記節点間の各点におけるポテンシャルを計算し、前記ポテンシャルが最大である点を前記中間点として選択することを特徴とする請求項8に記載の領域分割処理装置。
【請求項11】 入力信号から特徴点を検出し、複数の節点を生成し、前記節点を結んだ閉曲線を設定し、前記節点を前記特徴点に近づくように移動させ、前記閉曲線で囲まれた領域を決定する領域分割処理方法において、前記閉曲線上の点であって、前記節点とは異なる点としての中間点を選択し、前記中間点と前記特徴点の位置から決まる値をしきい値処理し、その結果に対応して、前記中間点を前記節点として追加することを特徴とする領域分割処理方法。
【請求項12】 入力信号から特徴点を検出し、複数の節点を生成し、前記節点を結んだ閉曲線を設定し、前記節点を前記特徴点に近づくように移動させ、前記閉曲線で囲まれた領域を決定する領域分割処理装置において、移動処理された後の前記節点で形成される前記閉曲線で囲まれた領域の中心点を計算する計算手段と、前記節点の前記中心点との距離の変化から、変化点を検出する検出手段と、前記検出手段の検出結果に対応して、前記変化点を補間する補間手段とを備えることを特徴とする領域分割処理装置。
【請求項13】 前記検出手段は、第1の前記節点の前記中心点からの距離と、前記第1の節点に隣接する第2の前記節点の前記中心点からの距離との差に対して、増大方向と減少方向のしきいち処理行って、前記距離が前記しきい値以上に増大する前記節点を、前記変化点のうちの増大点として検出し、前記距離が前記しきい値以上に減少する前記節点を、前記変化点のうちの減少点として検出することを特徴とする請求項12に記載の領域分割処理装置。
【請求項14】 前記補間手段は、前記増大点と減少点およびその間の節点を削除することを特徴とする請求項13に記載の領域分割処理装置。
【請求項15】 前記補間手段は、前記増大点の直前の前記節点と、前記減少点の直後の前記節点とを結ぶ曲線と、前記増大点と前記中心点とを結ぶ直線とが交差する位置に、前記増大点を移動させるとともに、前記増大点の直前の前記節点と、前記減少点の直後の前記節点とを結ぶ曲線と、前記減少点と前記中心点とを結ぶ直線とが交差する位置に、前記減少点を移動させることを特徴とする請求項13に記載の領域分割処理装置。
【請求項16】 前記計算手段は、前記特徴点以外の各点の前記特徴点までの距離により一義的に規定されるポテンシャルの分布の極大点を検索し、前記極大点としての前記点のうち、前記特徴点までの距離の値の大きい順番に順序付けし、順序付けに対応して前記極大点を前記中心点として選択するとともに、確定した領域に含まれる前記極大点を前記中心点として選択しないようにすることを特徴とする請求項12に記載の領域分割処理装置。
【請求項17】 前記検出手段は、前記中心点からの距離が最も小さい前記節点を始点として、前記始点から順次しきい値処理を行うことを特徴とする請求項13に記載の領域分割処理装置。
【請求項18】 入力信号から特徴点を検出し、複数の節点を生成し、前記節点を結んだ閉曲線を設定し、前記節点を前記特徴点に近づくように移動させ、前記閉曲線で囲まれた領域を決定する領域分割処理方法において、移動処理された後の前記節点で形成される前記閉曲線で囲まれた領域の中心点を計算し、前記節点の前記中心点との距離の変化から、変化点を検出し、その検出結果に対応して、前記変化点を補間することを特徴とする領域分割処理方法。
【請求項19】 入力信号から特徴点を検出し、複数の節点を生成し、前記節点を結んだ閉曲線を設定し、前記節点を前記特徴点に近づくように移動させ、前記閉曲線で囲まれた領域を決定する領域分割処理装置において、前記入力信号から、前記特徴点以外の点により構成される領域であって、前記閉曲線で囲まれていない非閉曲線領域を検出し、前記非閉曲線領域を、前記閉曲線で囲まれた領域とする処理の条件を判断する判断手段と、前記判断手段の判断の結果に対応して、前記非閉曲線領域を前記閉曲線で囲まれた領域とする処理を実行する処理手段とを備えることを特徴とする領域分割処理装置。
【請求項20】 前記判断手段は、前記閉曲線で囲まれた領域とする処理の回数が、予め設定された所定の回数に達した否かを判断することを特徴とする請求項19に記載の領域分割処理装置。
【請求項21】 前記判断手段は、前記閉曲線で囲まれた領域の面積を計算し、その面積をしきい値処理して、前記非閉曲線領域を前記閉曲線で囲まれた領域とする処理を実行するか否かを判断することを特徴とする請求項19に記載の領域分割処理装置。
【請求項22】 前記処理手段は、前記判断手段の判断結果に対応して、前記非閉曲線領域の信号の入力を受けることを特徴とする請求項19に記載の領域分割処理装置。
【請求項23】 入力信号から特徴点を検出し、複数の節点を生成し、前記節点を結んだ閉曲線を設定し、前記節点を前記特徴点に近づくように移動させ、前記閉曲線で囲まれた領域を決定する領域分割処理方法において、前記入力信号から、前記特徴点以外の点により構成される領域であって、前記閉曲線で囲まれていない非閉曲線領域を検出し、前記非閉曲線領域を、前記閉曲線で囲まれた領域として処理する条件を判断し、その判断の結果に対応して、前記非閉曲線領域を前記閉曲線で囲まれた領域として処理することを特徴とする領域分割処理方法。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、信号をその特徴に従って複数の領域に分割する領域分割処理装置および方法に関し、例えば、物体識別装置や製品仕分装置等のように、信号の解析や認識を行うための信号処理装置において、入力信号から対象を抽出する場合に用いて好適な領域分割処理装置および方法に関する。
【0002】また本発明は、例えば、データ伝送装置やデータレコーダ等のように、信号の伝送や記録再生を行うために原信号の情報量を効率的に圧縮する符号化装置において、領域の特徴に応じた処理を行う場合に適用される。
【0003】
【従来の技術】信号の領域分割処理方法には、例えば、点ごとに特徴量を計算して、その特徴量の類似度から隣接点が同一領域に属しているか否かを識別して統合し、順次各点を集合化して領域を形成するスプリットアンドマージ方式や、信号の特徴点を検出し、そこからの距離を微分したポテンシャルベクトル場を計算して、そのポテンシャルエネルギの和が最小になるような形状を計算し、その形状の内側を領域とするスネーク方式などがある。
【0004】スプリットアンドマージ方式は、点ごとの計算を用いているので装置化は比較的容易であるが、点の統合が進むにつれて局所的な性質が反映されなくなり、得られる領域形状が不正確になるという欠点がある。そこで処理は複雑ではあるが、値の分布を大局的に扱えるので、物体輪郭によく適合させることができるスネーク方式が用いられることが多い。
【0005】図13にスネーク方式を領域形状化に用いた信号処理装置の例を示す。図13に示す信号処理装置においては、入力信号A11は特徴点検出回路101に入力され、そこでエッジなどの特徴点が検出され、そこから特徴点信号A12が出力される。特徴点信号A12はポテンシャル計算回路102に入力され、そこで入力信号の各点のポテンシャルベクトルが計算され、ポテンシャル信号A13が出力される。このポテンシャルの計算方法を以下に示す。
【0006】すなわち、各点のエッジ(特徴点)からの距離をd(x,y)としたときの2次元ポテンシャル場P(x,y)は、単位ベクトルi,jを用いて次のように表される。
【0007】
【数1】

【0008】初期点検出回路103はポテンシャル信号A13からポテンシャルの極大点を検出し、当該極大点におけるポテンシャルの大きい順に極大点の座標を初期点としてマークし、初期点ポテンシャル信号A14を出力する。この初期点ポテンシャル信号A14はスネーク計算回路104に入力され、そこで図14を参照して後述するスネークアルゴリズムによって、ポテンシャルの分布に応じた形状の閉曲線が生成され、閉曲線形状信号A15が出力される。領域処理回路105は入力信号A11と閉曲線形状信号A15から、閉曲線に囲まれた信号を抜き出し、適当な方法で信号処理を行い、結果を領域処理信号A16として出力する。特徴点信号A12と領域処理信号A16は、多重化回路106によって多重化され、出力信号A17として出力される。
【0009】次に、スネークアルゴリズムの計算方法を数式によって以下に示す。
【0010】点列{ei}={(xi,yi)}に対してエネルギEを次のように定義する。
【0011】
【数2】

【0012】ここでeext(i)は、スネークのポテンシャル場における位置エネルギであり、eint(i)は、スネークの形状による張力エネルギである。これらはエッジ(特徴点)からの距離をd(x,y)としたときのポテンシャル場P(x,y)と、スネークの各節点間を結ぶベクトル{vi}を用いて、それぞれ以下のように表される。
【0013】
【数3】

【0014】スネークアルゴリズムにおいては、この(2)式のエネルギEを最小にするような{(xi,yi)}の組を求める。
【0015】以上の図13のスネーク計算回路104におけるスネークアルゴリズムをフローチャートで表すと図14に示すようになる。
【0016】図14における入力の初期点ポテンシャル信号は、図13における初期点ポテンシャル信号A14に相当する。初期点検査ステップ111では、入力された初期点ポテンシャル信号A14にマークされた初期点を大きい順にチェックし、初期点が存在する場合、現在最も大きなポテンシャルを持った初期点をスネーク設定ステップ112へ渡す。初期点が存在しない場合は全てのスネークの構成が終了したものとして、構成された全てのスネーク節点リストを出力する。このスネーク節点リストは図13における閉曲線形状信号A15に相当する。
【0017】スネーク設定ステップ112では、当該初期点をスネーク生成の中心点とし、スネーク節点初期化ステップ113では、スネーク中心点から適当な間隔で初期節点を配置する。ポテンシャル計算ステップ114では、初期節点で示される全ての節点におけるポテンシャルエネルギを求めて、その和を計算する。連立方程式計算ステップ115では、このポテンシャルエネルギの和から、 (2)式のエネルギEを最小にするような {( xi, yi )} の組を求める連立方程式を解いて、節点移動量を計算する。節点移動処理ステップ116では、この各節点に対して節点移動量だけ座標を移動させた新節点を生成する。
【0018】スネーク収束判断ステップ117では、この新節点と元の節点を比較して、移動量があるしきい値より大きいときはスネークはまだ収束していないものとみなして、新節点を元の節点と置き換えてポテンシャル計算ステップ114に戻り、再びポテンシャルから節点の移動量を計算する。また移動量があるしきい値以下ならばスネークは収束したものとみなして、この初期点を中心としたスネークの処理を終了し、近似節点を領域内点検査ステップ118へ出力する。
【0019】最後に領域内点検査ステップ118では、近似節点が張る領域内に存在する初期点を消去してスネーク中心の候補から外し、確定節点として、初期点検査ステップ111の判断に戻る。
【0020】
【発明が解決しようとする課題】信号の特徴点を検出して、その特徴点に囲まれた領域を単一領域として抜き出す領域分割処理方法において、上述したような、ポテンシャルエネルギ最小化によるスネークアルゴリズムを用いると、ポテンシャル場の計算と、エネルギ最小点を求める連立方程式の計算量が莫大で計算コストがかかり過ぎるうえ、さらに収束するまでに多くの回数の反復処理を必要とするため、リアルタイム処理が困難になるという課題がある。また(1)式のエネルギEは、例えば特徴点までの距離により一義的に決定されるものではないので、ポテンシャルの極小解に陥ってしまうことがあり、正確な領域の形状が取れない場合が起こりうるという課題がある。
【0021】本発明は、このような状況に鑑みてなされたもので、リアルタイム処理を可能にするとともに、正確な領域の形状を取得できるようにするものである。
【0022】
【課題を解決するための手段】請求項1に記載の領域分割処理装置は、入力信号から特徴点を検出する検出手段と、特徴点以外の各点の特徴点までの距離により一義的に規定されるポテンシャルを計算する計算手段と、点のポテンシャルに対応して処理開始点を決定する決定手段と、処理開始点を基準にして複数の節点を発生させる発生手段と、節点を、接点と処理開始点とを結ぶ直線の延長線上で移動させる移動手段と、移動後の節点で囲繞される閉領域を抽出する抽出手段とを備えることを特徴とする。
【0023】請求項7に記載の領域分割処理方法は、入力信号から特徴点を検出し、特徴点以外の各点の特徴点までの距離により一義的に規定されるポテンシャルを計算し、点のポテンシャルに対応して処理開始点を決定し、処理開始点を基準にして複数の節点を発生させ、節点を、接点と処理開始点とを結ぶ直線の延長線上で移動させ、移動後の節点で囲繞される閉領域を抽出することを特徴とする。
【0024】請求項8に記載の領域分割処理装置は、閉曲線上の点であって、節点とは異なる点としての中間点を選択する選択手段と、中間点と特徴点の位置から決まる値をしきい値処理し、その結果に対応して、中間点を節点として追加する処理手段とを備えることを特徴とする。
【0025】請求項11に記載の領域分割処理方法は、閉曲線上の点であって、節点とは異なる点としての中間点を選択し、中間点と特徴点の位置から決まる値をしきい値処理し、その結果に対応して、中間点を節点として追加することを特徴とする。
【0026】請求項12に記載の領域分割処理装置は、移動処理された後の節点で形成される閉曲線で囲まれた領域の中心点を計算する計算手段と、節点の中心点との距離の変化から、変化点を検出する検出手段と、検出手段の検出結果に対応して、変化点を補間する補間手段とを備えることを特徴とする。
【0027】請求項18に記載の領域分割処理方法は、移動処理された後の節点で形成される閉曲線で囲まれた領域の中心点を計算し、節点の中心点との距離の変化から、変化点を検出し、その検出結果に対応して、変化点を補間することを特徴とする。
【0028】請求項19に記載の領域分割処理装置は、入力信号から、特徴点以外の点により構成される領域であって、閉曲線で囲まれていない非閉曲線領域を検出し、非閉曲線領域を、閉曲線で囲まれた領域とする処理の条件を判断する判断手段と、判断手段の判断の結果に対応して、非閉曲線領域を閉曲線で囲まれた領域とする処理を実行する処理手段とを備えることを特徴とする。
【0029】請求項23に記載の領域分割処理方法は、入力信号から、特徴点以外の点により構成される領域であって、閉曲線で囲まれていない非閉曲線領域を検出し、非閉曲線領域を、閉曲線で囲まれた領域として処理する条件を判断し、その判断の結果に対応して、非閉曲線領域を閉曲線で囲まれた領域として処理することを特徴とする。
【0030】
【作用】請求項1に記載の領域分割処理装置おいては、検出手段が、入力信号から特徴点を検出し、計算手段が、特徴点以外の各点の特徴点までの距離により一義的に規定されるポテンシャルを計算し、決定手段が、点のポテンシャルに対応して処理開始点を決定し、発生手段が、処理開始点を基準にして複数の節点を発生させ、移動手段が、節点を、接点と処理開始点とを結ぶ直線の延長線上で移動させ、抽出手段が、移動後の節点で囲繞される閉領域を抽出する。
【0031】請求項7に記載の領域分割処理方法おいては、入力信号から特徴点を検出し、特徴点以外の各点の特徴点までの距離により一義的に規定されるポテンシャルを計算し、点のポテンシャルに対応して処理開始点を決定し、処理開始点を基準にして複数の節点を発生させ、節点を、接点と処理開始点とを結ぶ直線の延長線上で移動させ、移動後の節点で囲繞される閉領域を抽出する。
【0032】請求項8に記載の領域分割処理装置おいては、選択手段が、閉曲線上の点であって、節点とは異なる点としての中間点を選択し、処理手段が、中間点と特徴点の位置から決まる値をしきい値処理し、その結果に対応して、中間点を節点として追加する。
【0033】請求項11に記載の領域分割処理方法おいては、閉曲線上の点であって、節点とは異なる点としての中間点を選択し、中間点と特徴点の位置から決まる値をしきい値処理し、その結果に対応して、中間点を節点として追加する。
【0034】請求項12に記載の領域分割処理装置おいては、計算手段が、移動処理された後の節点で形成される閉曲線で囲まれた領域の中心点を計算し、検出手段が、節点の中心点との距離の変化から、変化点を検出し、補間手段が、検出手段の検出結果に対応して、変化点を補間する。
【0035】請求項18に記載の領域分割処理方法おいては、移動処理された後の節点で形成される閉曲線で囲まれた領域の中心点を計算し、節点の中心点との距離の変化から、変化点を検出し、その検出結果に対応して、変化点を補間する。
【0036】請求項19に記載の領域分割処理装置おいては、判断手段が、入力信号から、特徴点以外の点により構成される領域であって、閉曲線で囲まれていない非閉曲線領域を検出し、非閉曲線領域を、閉曲線で囲まれた領域とする処理の条件を判断し、処理手段が、判断手段の判断の結果に対応して、非閉曲線領域を閉曲線で囲まれた領域とする処理を実行する。
【0037】請求項23に記載の領域分割処理方法おいては、入力信号から、特徴点以外の点により構成される領域であって、閉曲線で囲まれていない非閉曲線領域を検出し、非閉曲線領域を、閉曲線で囲まれた領域として処理する条件を判断し、その判断の結果に対応して、非閉曲線領域を閉曲線で囲まれた領域として処理する。
【0038】
【実施例】以下に本発明の実施例を説明するが、特許請求の範囲に記載の発明の各手段と以下の実施例との対応関係を明らかにするために、各手段の後の括弧内に、対応する実施例(但し一例)を付加して本発明の特徴を記述すると、次のようになる。但し勿論この記載は、各手段を記載したものに限定することを意味するものではない。
【0039】請求項1に記載の領域分割処理装置は、入力信号から特徴点を検出する検出手段(例えば図1の特徴点検出回路11)と、特徴点以外の各点の特徴点までの距離により一義的に規定されるポテンシャルを計算する計算手段(例えば図1の特徴点距離計算回路12)と、点のポテンシャルに対応して処理開始点を決定する決定手段(例えば図1の初期点検出回路13)と、処理開始点を基準にして複数の節点を発生させる発生手段(例えば図3の膨張節点初期化ステップ23)と、節点を、接点と処理開始点とを結ぶ直線の延長線上で移動させる移動手段(例えば図1の円膨張計算回路14)と、移動後の節点で囲繞される閉領域を抽出する抽出手段(例えば図1の領域処理回路16)とを備えることを特徴とする。
【0040】請求項8に記載の領域分割処理装置は、閉曲線上の点であって、節点とは異なる点としての中間点を選択する選択手段(例えば図6の中点検出ステップ42)と、中間点と特徴点の位置から決まる値をしきい値処理し、その結果に対応して、中間点を節点として追加する処理手段(例えば図6の節点追加処理ステップ46)とを備えることを特徴とする。
【0041】請求項12に記載の領域分割処理装置は、移動処理された後の節点で形成される閉曲線で囲まれた領域の中心点を計算する計算手段(例えば図10の距離計算ステップ52)と、節点の中心点との距離の変化から、変化点を検出する検出手段(例えば図10のはみ出し点検査ステップ54、戻り点検査ステップ56)と、検出手段の検出結果に対応して、変化点を補間する補間手段(例えば図10の修正ステップ58)とを備えることを特徴とする。
【0042】請求項19に記載の領域分割処理装置は、入力信号から、特徴点以外の点により構成される領域であって、閉曲線で囲まれていない非閉曲線領域を、閉曲線で囲まれた領域とする処理の条件を判断する判断手段(例えば図1の再領域化選択回路15)と、判断手段の判断の結果に対応して、非閉曲線領域を閉曲線で囲まれた領域とする処理を実行する処理手段(例えば図1の特徴点距離計算回路12)とを備えることを特徴とする。
【0043】以下、本発明の実施例について述べる。図1は本発明における信号処理装置の構成例を表している。
【0044】図1に示す信号処理装置において、入力信号B11は特徴点検出回路11に入力され、そこでエッジなどの特徴点が検出され、特徴点信号B12が出力される。特徴点距離計算回路12は、特徴点信号B12と、後に説明する再領域化特徴点信号B16のいずれか一方から、各点からの最も近い特徴点までの距離を特徴点距離として計算し、特徴点距離信号B13を出力する。この特徴点距離は、各点から最も低い特徴点までの距離をユークリッド距離で表したものである。一般的にはここでは各点でのポテンシャルを計算することになるが、本発明におけるポテンシャル値は各点から最も近い特徴点までの距離と等価なので、以後適宜、このポテンシャルを距離ということとする。
【0045】初期点検出回路13は特徴点距離信号B13から信号値の極大点を検出し、当該極大点における特徴点距離の大きい順に極大点の座標を初期点としてマークし、初期点距離信号B14を出力する。初期点距離信号B14は円膨張計算回路14に入力され、そこで円膨張アルゴリズムによって特徴点に最も近い形状の閉曲線が生成され、閉曲線形状信号B15が出力される。この円膨張アルゴリズムについては図3を参照して後に説明する。
【0046】再領域化選択回路15は、閉曲線形状信号B15が画面を埋め尽くしている(閉曲線で領域化されている)かどうかを調べて、埋め尽くしていなければ残りの部分を再領域化するために、すでに領域化されている点をマスクに置き換えた再領域化特徴点信号B16を生成し、特徴点距離計算回路12に入力させる。再領域化選択回路15は、画面が閉曲線形状信号B15で埋め尽くされていれば領域化処理を終了して、領域化信号B17を生成して出力する。
【0047】領域処理回路16は、入力信号B11と領域化信号B17から、閉曲線に囲まれた信号を抜き出し、適当な方法で信号処理を行い、結果を領域処理信号B18として出力する。特徴点信号B12と領域処理信号B18は、多重化回路17によって多重化されて、出力信号B19として出力される。
【0048】次に、その動作について説明する。特徴点検出回路11は、入力信号B11から特徴点を検出し、特徴点信号B12を特徴点距離計算回路12に出力する。この特徴点とは、例えば図2にC11で示すように、エッジを表す点とされる。特徴点距離計算回路12は、この特徴点信号B12を用いて、各点において、そこからの最も近い特徴点までの距離(特徴点距離)を計算する。これにより、図2に示すように、特徴点C11までの距離(ポテンシャル)により構成されるマップが構成されることになり、特徴点距離計算回路12は、この距離によるポテンシャルマップを表す特徴点距離信号B13を初期点検出回路13に出力する。
【0049】初期点検出回路13は、特徴点距離信号B13の極大点を検出する。この極大点は、図2に示すように、特徴点C11から等距離の位置を表す等距離線C12で囲まれた極大点C13(C13-1乃至C13-5)として表される。
【0050】そして、初期点検出回路13は、この極大点C13における特徴点距離の大きい順にこれを初期点としてマークし(図2の実施例では、C13-1,C13-2,C13-3,C13-4,C13-5の順番に順序づけ)、初期点距離信号B14として、円膨張計算回路14に出力する。円膨張計算回路14は、この初期点距離信号B14を円膨張アルゴリズムに従って処理する。
【0051】次に、図3のフローチャートを参照して、円膨張アルゴリズムについて説明する。
【0052】なお一般的には従来例で説明したように、各点でのポテンシャルを計算することが必要であるが、本実施例においては、ポテンシャル値は各点から最も近い特徴点までの距離と等価とされる。この特徴点距離は各点における最も近い特徴点までの距離をユークリッド距離で表したものである。もちろん従来例の説明で用いたようなポテンシャルを採用することも可能である。
【0053】図3における入力としての初期点距離信号は図1における初期点距離信号B14に相当する。初期点検査ステップ21では、入力された初期点距離信号B14にマークされた初期点を大きい順にチェックし、初期点が存在すれば、現在最も大きな距離を持った初期点(図4の場合、C13-1)を初期円設定ステップ22へ渡す。
【0054】初期円設定ステップ22では、その初期点(特徴点距離の最も大きな極大点)を円膨張処理の初期円中心点とし、その初期円中心の特徴点距離を半径rとする初期円を設定する。例えば図4に示すように、中央の極大点を初期円中心点C13-1とし、そこから半径rの位置に、初期円C14を設定する。
【0055】膨張節点初期化ステップ23では、初期円中心点から適当な間隔で初期節点を配置する。図4の実施例では、半径rの初期円C14を、θ = π/2r の角度で分割した間隔を初期節点間隔C15とし、初期節点間隔の初期円C14上の点を初期節点C16としている。
【0056】距離計算ステップ24では、初期節点C16の節点距離(初期円中心点からの距離(いまの場合、r))を求める。移動検査ステップ25では、各節点の座標をその点での節点距離(r)の分だけ初期円C14の半径方向へ膨張させたとき(初期円中心点C13と初期節点C16とを結ぶ直線の延長線上で、中心点C13から離れるように移動させたとき)、特徴点C11にぶつからないか(当接しないか)を調べる。ぶつかってしまうような場合はこの節点はこれ以上移動させないこととして距離計算ステップ24に戻り、次の節点について処理を続ける。ぶつからないようであれば節点移動量(r)を出力する。節点移動処理ステップ26ではその節点に対して、節点移動量(r)だけ座標を移動させた新節点を生成する。
【0057】近似調整処理ステップ27では、新節点に対し、その新節点の周囲で特徴点の配置にうまくフィットできるように近似調整が行われて、近似新節点が生成される。この近似調整アルゴリズムについては図6を参照して後に説明する。
【0058】収束判断ステップ28では、この近似新節点と元の節点を比較して、移動量があるしきい値以上ならばまだ収束していないとみなして、元の節点を近似新節点で置き換えて、距離計算ステップ24に戻り、再び節点距離から近似新節点の移動量を計算する。また移動量があるしきい値以下ならば収束したとみなして、この初期点を中心とした円膨張処理を終了する。
【0059】以上のようにして、例えば図4に示すように、初期円中心点C13-1から初期円C14上の所定の初期節点C16までの距離rを節点距離として、その初期節点C16をその節点距離rだけ、初期円中心点C13とその初期節点C16とを結ぶ直線の延長線上に移動できるか否かが判定される。節点距離rだけ初期節点C16を移動させたとしても、新たな位置が特徴点C11に当接しない場合においては、新たな位置まで、その初期節点C16が移動(膨張)される。このような動作が、移動量が所定のしきい値以下となるまで繰り返し実行される。このようにして、図4に示すように、元の初期節点C16が、節点移動量C17だけ移動されて新節点C18となる。
【0060】以上のような処理が、初期円中心点C13-1を中心とする初期円C14上の各初期節点C16に対して行われる。その結果、図5に示すように、初期円C14が膨張されて、新節点C18により閉領域曲線C19が生成される。
【0061】このようにして、収束判断ステップ28から近似節点が整合性検査ステップ29に出力される。整合性検査ステップ29では、特徴点の不整合による近似節点の異常を修正して、修正近似節点を出力する。この整合性検査アルゴリズムについては図10を参照して後に説明する。
【0062】最後に、領域内点検査ステップ30では、修正近似節点C18で形成される閉領域曲線C19内に存在する初期中心点C13-1を消去して、初期円中心点としての候補から外し、閉領域曲線C19上の新節点C18を確定節点とする。そして、初期点検査ステップ21の判断に戻る。
【0063】初期点検査ステップ21においては、次に大きい極大点が初期円中心点として選択され、初期円設定ステップ22以降の処理が上述した場合と同様に行われる。そして、初期点検査ステップ21において、他に初期点が存在しないと判定された場合、それまでの処理により得られた閉領域曲線C19に関する信号を閉曲線形状信号B15として出力する(閉領域曲線C19上の新節点C18のリストを膨張節点リストとして出力する)。
【0064】次に前述した図3の近似調整ステップ27の近似調整アルゴリズムについて、図6のフローチャートを参照して説明する。
【0065】図6における入力信号は前述の新節点C18に相当する。節点ループ制御ステップ41では、入力された節点が、その閉領域曲線C19の最後の節点であるか否かを判定し、最後の節点でなければ次段の中点検出ステップ42の処理に進む。
【0066】すなわち、それまでの処理により、図7(A)に示すように、初期円中心点C13を中心とする初期円C14上に設定された初期節点C16を、初期円中心点C13とその初期節点C16を結ぶ直線上に移動し、図7(B)に示すような、新節点(移動後の節点)C18からなる閉領域曲線(近似曲線)C19を生成する。そして、この閉領域曲線C19上の新節点C18が最後の節点でなければ、中点検出ステップ42の処理に進む。
【0067】中点検出ステップ42では、図7(C)に示すように、所定の節点Aiと、隣接する節点Ai+1との間の中点Mの座標を計算し、特徴点間距離計算ステップ43では、初期円中心点C13から中点Mを通って延びる直線が特徴点C11にぶつかる点Nの座標を計算して、中点Mと点Nの間の距離LMNを計算する。さらに、距離計算ステップ44で、中点Mの節点距離(初期円中心点C13から中点Mまでの距離)dMを求める。近似度検査ステップ45では、距離LMNと距離dMを比較して、距離LMNが距離dMより大きい場合、精度の良い近似を得るために、節点追加処理ステップ46によって点Nを新しい節点として追加させる。
【0068】距離LMNが、距離dMと等しいか、それより小さい場合においては、節点追加処理ステップ46の処理はスキップされる。
【0069】以上のようにして、閉領域曲線C19の全ての新節点C18に対する処理が完了したと、節点ループ制御ステップ41で判定されるまで、同様の処理が繰り返し実行される。
【0070】図7の実施例においては、同図(C)に示すように、点Aiと、それに隣接する点Ai+1の中点Mが求められている。そして、初期円中心点C13と中点Mを結ぶ直線C21が特徴点C11と当接する点がNとされる。初期円中心点C13から中点Mまでの距離dMと、点Mと点Nの距離LMNが比較され、距離LMNが距離dMより大きい場合には、図7(D)に示すように、点Nが閉領域曲線C19の新節点C18として追加される。換言すれば、閉領域曲線C19が図7(B)に示す状態から、同図(D)に示す状態に変更される。
【0071】このようにして、各節点を単に膨張させるだけでは、特徴点C11に充分近似させることができなかった節点間に新しい節点を設け、近似の調整を行う。これにより、特徴点C11により近似した閉領域曲線(近似曲線)C19を得ることができる。節点間に近似のずれを合わせるために追加された節点を含んだ信号が、近似調整節点信号として出力される。
【0072】なお、閉領域曲線C19上の点であって、隣接する2つの節点C16間の各点における特徴点C11までの距離(ポテンシャル)を計算し、その距離が最大となる点を、中点Mの代わりに選択し、同様の処理を行うようにしてもよい。
【0073】ところで、検出された特徴点の配置によっては、上述した処理で近似した各節点が、本来の領域を囲んでいる特徴点とは異なる領域に対する特徴点に収束してしまい、得られた領域の形状が大きくゆがんでしまう場合がある。例えば図8に示すように、領域を囲むエッジ(特徴点C11)に切れ目ができていて、近似節点C33,C34が外側の別なエッジ(特徴点C11A)に収束してしまう場合がある。
【0074】このようにはみ出してしまった節点C33,C34を、本来存在するであろうエッジの内側に配置するために、図8に示すように、はみ出した節点C33,C34、並びにその間に他の節点があればその節点を削除し、その前後の節点C32とC35の間を線分(直線)C31で接続し直すことができる。あるいはまた図9に示すように、はみ出さなかった節点C32とC35の間に曲線C41を引き、その曲線C41と、中心点C13と節点C33を結ぶ直線が交差する位置に、節点C33を引き戻し、同様に、曲線C41と、中心点C13と節点C34を結ぶ直線が交差する位置に、節点C34を引き戻すことができる。
【0075】図3の整合性検査ステップ29における処理は、この図8または図9に示すような処理を実行するものである。図10のフローチャートは、この場合の処理例を表している。
【0076】節点ループ制御ステップ51では、所定の閉領域曲線C19上の最後の節点であるか否かを判定し、最後の節点でなければ次段の距離計算ステップ52の処理に進む。距離計算ステップ52では、中心点C13を決定し、各節点Aiと中心点C13との間の距離Riを計算する。差分計算ステップ53では、中心点C13からの距離が最も小さい節点(図8と図9において、Aiとして表されている節点)とし、この始点から順次、各節点Aiの距離Riと、その前の節点Ai-1との距離Ri-1の差分diを計算する。
【0077】はみ出し点検査ステップ54では、差分diを調べて、差分diがしきい値Thより大きく、かつ、はみ出し点フラグがセットされていなければ、はみ出し点セットステップ55で、はみ出し点フラグをセットし、この節点番号をはみ出し点としてストアしておく。さらに戻り点検査ステップ56では、差分diを調べて、差分diが負のしきい値Thより小さく、かつ、はみ出し点フラグがセットされていれば、戻り点セットステップ57で、戻り点フラグをセットし、この節点番号を戻り点としてストアしておく。
【0078】以上の処理を全ての閉領域曲線C19上の各節点間において行って、はみ出し点と戻り点のペアを全て検出した後、修正ステップ58で、はみ出し点フラグと戻り点フラグを参照して、それぞれのはみ出し点と戻り点のペアの間で、図8または図9に示すような補間処理により節点の修正を行う。
【0079】以上のようにして、例えば図11(A)に示すように、各節点Aiの中心点C13からの距離Riが求められると、図11(B)に示すように、節点Aiの距離Riと直前の節点Ai-1の距離Ri-1との差分diが求められる。そして、この差分diがしきい値Thと比較される。
【0080】そして、差分diがしきい値Thより大きいとき、その節点Aiは、図8と図9における節点C33のようなはみ出し点として、その節点番号を記憶する。
【0081】同様に、差分diが負のしきい値-Thより小さいと判定された場合、図8と図9に示す節点C34のように、戻り点として、その節点番号が記憶される。
【0082】そして、このように、はみ出し点と戻り点のペアが記憶されると、例えば図11(C)示すように、はみ出し点と戻り点が削除され、はみ出し点の直前の節点と戻り点の直後の節点との間を補完する処理が実行される。すなわち、図8に示すように、はみ出し点としての節点C33の直前の節点C32と、戻り点としての節点C34の直後の節点C35を、線分C31で結ぶようにし、節点C33とC34は削除される。
【0083】あるいはまた、図12(A)に示すように、中心点C13と各節点Aiの距離Riが得られたとき、節点Aiの距離Riと、その直前の節点Ai-1の距離Ri-1との差分diが、図12(B)に示すように求められる。そして、この差分diが正のしきい値Thおよび負のしきい値-Thと比較され、図9に示すように、飛び出し点としての節点C33と、戻り点としての節点C34が求められる。
【0084】そして、図12(C)に示すように、はみ出し点の直前の節点と戻り点の直後の節点との間に曲線が描かれ、その曲線上の節点が補間される。
【0085】すなわち、図9に示すように、はみ出し点としての節点C33の直前の節点C32と、戻り点C34の直後の節点C35の間に曲線C41がひかれ、その曲線C41と中心点C13と節点C33を結ぶ直線との交点上に節点C33が移動され、また曲線C41と、中心点C13と節点C34を結ぶ直線との交点上に節点C34が移動される。
【0086】なお、この曲線C41としては、円弧、スプライン曲線などの他、直線を用いることができる。
【0087】このようにして、節点が本来の領域を囲んでいる特徴点とは異なる領域の特徴点に収束してしまい、得られた領域の形状が大きく歪んでしまうようなことが防止される。
【0088】なお、図10の距離計算ステップ52において、移動後の節点により形成される閉領域曲線C19の中心点を計算により求めるようにしてもよい。この時、図3の円膨張のフローチャートに示した場合の処理と同様に、特徴点までの距離の極大点を、距離の大きさの順番で順序付け、その順番で極大点を中心点として選択し、確定した領域に含まれる極大点は中心点として選択しないようにすることができる。
【0089】以上のようにして、図1の円膨張計算回路14における処理が行われ、閉領域曲線(近似曲線)C19に対応する閉曲線形状信号B15が出力される。再領域化選択回路15は、例えば図2に示すような画面上の信号が、全て閉曲線形状信号B15で埋め尽くされているか否かを判定し、まだ閉曲線形状信号B15が生成されていない領域(非閉曲線領域)が存在する場合には、すでに領域化されている点をマスクした再領域化特徴点信号B16を生成し、これを特徴点距離計算回路12に出力する。特徴点距離計算回路12以降の各回路は、上述した場合と同様にして、領域化処理を実行する。
【0090】これにより、例えば図2に示す極大点C13-1乃至C13-5を含む特徴点C11で囲まれる領域を閉領域曲線C19で近似する処理が、順次実行される。
【0091】そして、特徴点C11で囲まれる全ての領域の領域化処理が完了したとき、再領域化選択回路15は、円膨張計算回路14より供給される閉曲線形状信号B15を領域化信号B17として、領域処理回路16に出力する。
【0092】領域処理回路16は、入力信号B11と領域化信号B17から閉曲線に囲まれた領域の信号を抜き出し、適当な方法で信号処理を行う。例えば、領域毎にデータを圧縮したり、画像データであれば、その画像の認識を行ったりする。処理結果は領域処理信号B18として、多重化回路17に出力される。多重化回路17は、領域処理回路16より入力された領域処理信号B18を、特徴点検出回路11より入力された特徴点信号B12とともに多重化し、出力信号B19として出力する。
【0093】なお、上記実施例においては、初期形状として円を設定しているが、この他、例えば、任意の閉多角形や閉曲線を設定してもよい。また、ポテンシャルや距離に応じて異なる初期形状を設定するようにしてもよい。
【0094】さらに上記実施例においては、ポテンシャルとしてユークリッド距離を用いているが、この他、例えば、チェス盤距離(長い方の目の数が距離となる)や市街地距離(垂直方向と水平方向の目の辺の和が距離となる)など、任意の距離計算法を用いてもよく、さらにそれらの1次微分をとったポテンシャルでもよい。要するに、距離により一義的に規定されるポテンシャル(単調増加または単調減少するポテンシャル)であればよい。
【0095】上記実施例においてはまた、再領域化処理の判断を、閉曲線領域の有無で行うようにしたが、この他、例えば、一度も行わない、常に所定回数行う、非閉曲線領域の面積があるしきい値を越えるようなら行う、などのような基準(条件)で判断するようにしてもよい。
【0096】以上のように、節点の移動を直線に沿った移動に限定することと、節点の逐次修正を行うことで、以下のような効果が得られる。
1. 従来のポテンシャルエネルギ最小化の収束アルゴリズムと比較して、ポテンシャルが距離で一義的に与えられるので、極小解に陥ることがなく、少ない計算量で処理でき、収束するまでの反復回数も減少させることができる。
2. 従来のスネークアルゴリズムと比較して、ポテンシャルとずれたところに新規節点を増設することができるので、領域形状を精度よく近似できる。
【0097】
【発明の効果】以上の如く、請求項1に記載の領域分割処理装置および請求項7に記載の領域分割処理方法によれば、特徴点までの距離により一義的に規定されるポテンシャルに対応して処理開始点を決定し、節点を、節点と処理化始点とを結ぶ直線の延長線上で移動させるようにしたので、リアルタイムで領域を抽出することが可能となる。また、極小解に陥ることがないので、正確な領域の形状を近似することが可能となる。
【0098】請求項8に記載の領域分割処理装置および請求項11に記載の領域分割処理方法によれば、閉曲線上の点であって、節点とは異なる点としての中間点を選択し、中間点を節点として追加するようにしたので、より精度よく、領域形状を近似することが可能となる。
【0099】請求項12に記載の領域分割処理装置および請求項18に記載の領域分割処理方法によれば、移動処理された後の節点で形成される閉曲線で囲まれる領域の中心点と節点の距離の変化から変化点を検出し、その検出結果に対応して変化点を補間するようにしたので、異なる特徴点に形状が収束してしまうようなことが防止される。
【0100】請求項19に記載の領域分割処理装置および請求項23に記載の領域分割処理方法によれば、非閉曲線領域を閉曲線で囲まれた領域として処理する条件を判断し、その判断の結果に対応して、非閉曲線領域を閉曲線で囲む領域として処理するようにしたので、迅速かつ確実に特徴点に近似した領域を決定することが可能となる。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013