JPH07104954B2 - 円弧抽出装置 - Google Patents

Description

【発明の詳細な説明】 〔概要〕 この発明は、図形を細線化・折線近似して生成した折線
中から円弧候補を抽出する円弧抽出装置において、細線
化・折線近似された図形の折線のうち円弧に該当する部
分を抽出する際に、１つの円弧として抽出されても実際
は複数の円弧部分を含んでしまう問題や、あるいは実際
は１つの円弧に係わらず複数の円弧に分割されて抽出さ
れてしまう問題を解決するため、１つの円弧候補を構成
する各折線ベクトルの仮半径および仮中心点に基づいて
円弧候補を分割処理すると共に、複数の円弧候補に対す
る夫々の仮半径、仮中心点および端点間の距離に基づい
て円弧候補の結合処理を行うことにより、原図形パター
ンにより厳密で有効な望ましい円弧候補の抽出を行うよ
うにしている。

〔産業上の利用分野〕 本発明は、細線化・折線近似された折線から抽出された
円弧候補に対して更に有効な円弧候補を生成するために
円弧の分割処理および／あるいは結合処理を行うよう構
成した円弧抽出装置に関するものである。

〔従来の技術と発明が解決しようとする問題点〕

一般に図形読取装置などにおいて、図形を認識させる場
合、細線化などによって得られた図形を構成する線分を
折線近似し、この線分を特徴づけることにより図形認識
を行うようになる。そのためには、図形を構成している
全ての線分に対して特徴点を求め、予め設定した所定値
と比較することによって認識を行う必要がある。

この際、図形を構成している線分の種類が直線か円弧か
円かが予め分かっていれば、認識時に必要な特徴点を減
らしたり、あるいは認識の処理対象を限定したりして処
理速度を向上させることが可能となる。

この種の円弧抽出方式として、図形データを既知の方法
で細線化・折線近似して折線データを生成し、この折線
データから円弧部分を構成する折線列を円弧候補として
抽出することが考えられる。しかし、この方式によって
円として抽出された場合でも、本当の円の場合や楕円の
場合が考えられる。また、異なった半径の複数の円弧が
分割し得ず、１つの円弧として抽出されている場合もあ
る。逆に、本当は、１つの円や円弧であるはずの円弧候
補がいくつかの円弧に分割されている場合もある。この
ように、本来の抽出したい円弧候補と異なって非所望の
円弧候補が抽出されてしまうという問題点があった。こ
のため、抽出されている円・円弧候補をもう１度、更に
厳しい条件で分割したり、更に緩い条件で結合したりし
て原図形パターンにより一致した所望の円弧候補を抽出
することが望まれている。

〔問題点を解決するための手段〕

本発明は、前記問題点を解決するために、折線から抽出
された円弧に対応する円弧候補の折線の仮半径および仮
中心点に基づいて円弧候補を複数に分割する円弧分割処
理部１と、折線から抽出された円弧に対応する複数の円
弧候補について夫々算出した仮半径および仮中心点と、
端点情報とに基づいて１つの円弧あるいは円に結合する
円弧結合処理部２とを設け、円弧候補に対して必要に応
じて分割および／あるいは結合を行って円弧部分を抽出
するようにしている。

第１図は本発明の原理構成図を示す。図中円弧分割処理
部１は、折線から抽出された円弧に対応する円弧候補の
折線の仮半径および仮中心点に基づいて円弧候補を分割
するものである。

円弧結合処理部２は、折線から抽出された円弧に対応す
る複数の円弧候補について夫々算出した仮半径および仮
中心点と、端点情報とに基づいて１つの円弧あるいは円
に結合するものである。

折線列の円弧データは、細線化・折線近似された折線か
ら円弧候補として粗く抽出された折線列のデータであ
る。

〔作用〕

次に、動作を説明する。

第１図において、細線化・折線近似されて生成された折
線のうち、円弧候補として抽出された折線列の円弧デー
タを円弧分割処理部１に入力すると、この円弧分割処理
部１は、円弧候補を構成する折線ベクトルに対して求め
た仮半径、仮中心点に基づいて、円弧候補を複数の円弧
候補に分割処理を行う。また、円弧候補として抽出され
た折線列の円弧データを円弧結合処理部２に入力する
と、この円弧結合処理部２は、複数の円弧候補を構成す
る折線列に対して求めた仮半径、仮中心点と、端点とに
基づいて、複数の円弧候補を１つの円弧候補に結合処理
を行う。これら分割処理と結合処理とは、相互に独立に
行うことが可能である。

以上のように、細線化・折線近似されて生成された折線
のうち、粗く円弧として抽出された折線の円弧候補に対
して更に厳密な円弧分割処理および／あるいは円弧結合
処理を施すことにより、原図形パターンにより一致した
所望の円弧候補を抽出することが可能となる。

〔実施例〕

次に、第１図ないし第７図を用いて本発明の１実施例の
構成および動作を詳細に説明する。

第２図を用いて本発明の動作の概略をまず説明する。図
中ないしは第１図円弧分割処理部１によって実行さ
れる処理を示し、図中ないしは円弧結合処理部２に
よって実行される処理を示す。

第２図図中は、円弧候補を抽出する状態を示す。これ
は、例えば第８図ないし第12図を用いて後述するよう
に、図形を細線化・折線近似して折線を生成し、この生
成した折線からの円弧を構成する折線列を抽出したもの
である。この抽出した円弧候補は、第11図円弧候補ベク
トルテーブルに登録する。

図中は、仮半径・仮中心点を求める状態を示す。これ
は、第３図を用いて詳述するように、円弧候補を構成す
る折線列に対して仮半径および仮中心点を算出すること
を意味している。

図中は、円と楕円の分割を行う状態を示す。これは、
閉ループとなる円弧候補（円あるいは楕円）に対して図
中で求めた仮半径および仮中心点に基づいて分割処理
例えば楕円を円部分と直線部分とに分割することを意味
している。

図中は、円弧の分割を行う状態を示す。これは、図中
で求めた円弧候補を構成する各折線ベクトルの仮半径
および仮中心点に基づいて、１つの円弧を２つの円弧に
分割することを意味している。

図中は、図中および図中で分割された円弧候補を
円弧候補ベクトルテーブルに登録する状態を示す（第11
図を用いて後述する）。

図中は、仮半径、仮中心点のずれと、端点間の距離と
による結合を行う状態を示す。これは、複数の円弧候補
に対して夫々求めた仮半径および仮中心点と、これら両
者の端点の距離差とに基づいて、１つの円弧候補に結合
することを意味している。

図中は、円弧候補を円弧候補ベクトルテーブルに登録
する状態を示す。

以上によって、粗く抽出された円弧候補に対して更に厳
密な条件のもとで分割処理および結合処理を施して、原
図形パターンにより一致する所望の円弧候補を抽出する
ことが可能となる。

以下本実施例の構成および動作を順次詳細に説明する。

第３図は円弧分割部１の動作説明フローチャートを示
す。

第３図において、図中は、抽出された円弧候補情報を
格納した第11図円弧候補テーブルおよび円弧候補ベクト
ルテーブルから所望のデータを読み出す状態を示す。こ
の際、円弧候補テーブル中のループフラグ欄にフラグが
立ててある場合（閉ループであって円あるいは楕円であ
る場合）、円候補として図中以下の処理を実行する。
一方、ループフラグが立ててない場合（円弧である場
合）、図中以下の処理を実行する。

図中は、ないしの処理から構成されている。

図中のは、候補中の座標（Ｘ、Ｙ）の重心を求め、
これを仮中心点とする状態を示す。これは、第11図円弧
候補ベクトルテーブルに格納されている円弧候補である
折線V_i（ｉは０ないしｎのうち円弧候補として抽出され
たもの）の例えば各始点P_iの座標（X_pi,Y_pi）を第９図
ベクトルテーブルから夫々読み出し、この読み出した全
てのＸ座標およびＹ座標について夫々の総和を求め、こ
の総和を求めた折線の総数ｎで割算して重心の座標
（X_G,Y_G）を算出し、これを仮中心点APの座標とするこ
とを意味している。

図中のは、仮中心点と各点との距離の平均値を仮半
径とする状態を示す。これは、図中ので算出した仮
中心点APの座標（X_G、Y_G）と、各折線V_iの始点P_iの座標
（X_pi、Y_pi）との距離差の平均値ARを下式を用いて算出
し、これを仮半径ARとすることを意味している。

各点と仮中心点との距離R_iは R_i＝{(X_pi-X_G)²+(Y_pi-Y_G)²}^1/2 ・・・（１） 仮半径ARは 図中のは、仮半径AR、各点の距離R_iとの差を算出
し、この差に基づいて円と円弧との判断に利用する状態
を示す。例えば両者の差が、ｋ以上となる点がｊ個以上
あった場合、その円候補は、円でないと判断し、この円
弧候補を分割の対象とする。両者が上記の条件を満たさ
ない場合、円候補としてそのまま残す。具体的に言え
ば、第４図（イ）に示すように楕円であれば、Ｙ軸付近
の点では当該各点P_iと仮中心点APとの間の距離R_iと、仮
半径ARとの差が−方向に大きくなり（平均値よりも小さ
くなり）、他方Ｘ軸付近の点では両者の差が＋方向に大
きくなり、ここでｋ＝10、およびｊ＝５と設定し、条件
に当てはまる点が５個以上となった場合、この円弧候補
は分割処理を行う必要があるので、この場合は、図中
以下の円弧分割処理を実行する。また、第４図（ロ）に
示すような円であれば、仮半径ARと、各点P_iと仮中心点
APとの距離R_iとの差にバラツキがないので、このまま円
として分割処理は行う必要がない。

図中は、仮半径ARおよび仮中心点APをこの円弧候補の
半径および中心点として抽出する状態を示す。

図中は、図中で抽出した半径および中心点を第11図
円弧候補テーブルに登録すると共に、この抽出した円弧
候補を構成する折線V_iを円弧候補ベクトルテーブルに登
録する状態を示す。

図中は、円弧候補の仮半径および仮中心点を求め、仮
半径の大きくくい違うところで円弧を分割する状態を示
す。これは、開ループの場合（円弧候補の場合）に対す
る分割処理を行うものである。以下説明する。第１に、
円弧候補を構成する折線V_iの仮半径R_iを第５図（イ）に
示すように定義し、下式を用いて算出する。

R_i＝L/θ₁ ・・・（３） ここで、Ｌは第５図（イ）に示すように折線V_iの長さを
表し、θ₁はこの折線V_i（折線ベクトル）の延長線と、
これに接続されている隣接する折線V_i+1との間の角度を
表す。AP_iは仮中心点を表す。この仮半径R_iを全ての折
線V_iについて算出する。第２に、第１で算出した接線V_i
の仮半径R_iについて順次隣接するものに対して比較し、
その差がｐ以上の値を持つ時にその円弧候補の折線V_iと
折線V_i+1との間で分割する。例えば第５図（ロ）に示す
ように円弧候補を構成する折線の一部として折線V₁と折
線V₂とがあり、ｐ＝15と設定する。この時、折線V₁の仮
半径R₁と折線V₂の仮半径R₂との長さの差が15以上違った
場合、この円弧候補の折線V₁と折線V₂との間を２つの円
弧候補にするための分割点とし、この分割点で円弧候補
を分割して図中で分割処理を実行する。

図中のは、円弧候補の始点と終点とを結だ線分の垂
直２等分線と、各折線ベクトルの垂線２等分線との交点
を求め、この交点の中から最適値を求め、これを中心点
とする状態を示す。これは、図中で分割した新しい円
弧候補となる折線V_i群に対して、その中心点を求めるこ
とを意味している。

図中のは、各点と中心点より、半径を求める状態を
示す。これは、図中ので求めた中心点と、各折線V_i
の始点との間の距離差を夫々求め、例えばこの平均値を
半径として算出することを意味している。そして、図中
で、図中で分割して新たに生成した円弧候補に属す
る折線V_i、および図中で算出した中心点の座標、半径
などのデータは、円弧候補毎に、第11図円弧候補テーブ
ルおよび円弧候補ベクトルテーブルを作成してこれに夫
々登録する。

以上の手順によって、円あるいは円弧を構成する円弧候
補が複数の円弧候補に分割される。

次に、第６図を用いて結合処理を説明する。

第６図において、図中は、円弧候補テーブルに登録さ
れている円弧候補のみを対象とする状態を示す。これ
は、第11図円弧候補テーブルおよび円弧候補ベクトルテ
ーブルに登録されている円弧候補のみを検索して以下の
結合処理を実行することを意味している。

図中は、図中で第11図テーブルから検索して読み出
した任意の円弧候補と、中心点座標（Ｘ、Ｙ）および半
径Ｒの夫々の値が、所定の最小値（X_MIN、Y_MIN、R_MIN）よ
りも大きくかつ所定の最大値（X_MAX、Y_MAX、R_MAX）よりも
小さくなる任意の円候補を見つける状態を示す。

図中は、この任意の２つの円弧候補の端点の距離をみ
る状態を示す。これは、２つの円弧候補の端点の座標
を、第11図円弧候補ベクトルテーブルに登録されている
先頭および末尾の折線V_iに対応する始点座標および末尾
座標を第９図ベクトルテーブルから読み出し、両者の端
点の最短距離を求めることを意味している。両者の端点
の距離が、所定値Ｌよりも小さい場合には、図中で結
合処理を実行する。両者の端点の距離が、所定値Ｌより
も大きい場合には、図中で２つの円弧候補をつなが
ず、次の候補を探すために図中以下を繰り返し実行す
る。

図中は、１つの円弧にまとめる状態を示す。これは、
図中およびで２つの円弧候補に対して全ての条件が
満足されたので、これら２つの円弧候補に含まれる全て
の折線V_iに対して、中心点、半径および端点を再計算す
ることを意味している。例えば第７図に示すようなＰお
よびＱを用いて示す２つの円弧候補を考え、折線V_iの内
角θ₁のみを利用して粗く円弧候補を抽出した処理で
は、点Ａで円弧Ｐと円弧Ｑとに分割されてしまう。この
時、円弧Ｐの中心点PPと円弧Ｑの中心点QQの距離が所定
値ｓ以下であって、かつ円弧Ｐの半径PRと円弧Ｑの半径
QRの長さの差が所定値ｔ以下であれば、円弧Ｐおよび円
弧Ｑの端点どうしが点Ａで接しているので、１つの円弧
として結合しても良いと判定する。

図中は、図中で２つの円弧を１つの円弧にまとめた
各種情報を、第11図円弧候補テーブルおよび円弧候補ベ
クトルテーブルに登録する状態を示す。

図中は、新しく抽出された円弧候補も含め、結合処理
の対象となる円弧があるか否かを判別する状態を示す。
YESの場合には、図中以下を繰り返し実行する。NOの
場合には、終了する。

以上のように、任意の２つの円弧候補に対して更に厳密
な条件を適用して条件を満足するものに対しては、２つ
の円弧候補を１つの円弧候補にまとめて新たに中心点の
座標、半径などを算出し、第11図テーブルに登録するこ
とにより、有効な円弧候補を抽出することが可能とな
る。

次に、第８図ないし第12図を用いて、図形パターンを細
線化・折線近似した折線列に対して、粗い条件を適用し
て円弧候補を抽出する手順を説明する。

第８図は円弧候補を抽出する概念説明図を示す。図中細
線化・折線近似処理部３は、入力された図形パターンに
対して細線化を行い、更にこの細線化された線図形に対
して折線近似を行って折線データを生成するものであ
る。

分類処理部４は、折線の長さに基づいて、折線を直線候
補折線、円弧候補折線、および歪候補折線に分類するも
のである。

円弧抽出処理部５は、分類処理部４によって分類された
円弧候補折線中から円弧を構成する円弧候補折線を抽出
するものである。

円弧算出処理部６は、円弧抽出処理部５によって抽出さ
れた円弧を構成する円弧候補折線群を結ぶ円弧の半径お
よび中心点座標を算出するものである。

円弧分割処理部１は、既述したように、１つの円弧候補
を複数の円弧候補に分割処理するものである。

円弧結合処理部２は、既述したように、複数の円弧候補
を１つの円弧候補に結合するものである。

第８図において、図形パターンを細線化・折線近似処理
部３に入力すると、既知の技術に基づいて、図形パター
ンが細線化され、更にこの細線化された線図形に対して
例えば屈曲点が現れるまで線図形中の点列を線分で結ぶ
などの折線近似処理が行われ、折線データが出力され
る。この折線データが入力された分類処理部４は、この
入力された折線の長さによって、折線を直線候補折線、
円弧候補折線、および歪候補折線に分類し、この分類し
た分類データを出力する。円弧抽出処理部５は、この分
類データ中の円弧候補折線について追跡を行い、ある円
弧候補折線に対して所定の角度範囲以内に接続されてい
る他の隣接する円弧候補折線を順次抽出して１つにまと
める。この１つにまとめられた円弧候補折線群の通知を
受けた円弧算出処理部６は、これら円弧候補折線群に対
する円弧の半径および中心点座標を円弧データとして算
出し、第11図テーブルに登録する。

以上によって、図形パターンを細線化、折線近似を行っ
た折線の円弧候補折線を追跡し、ある円弧候補折線に隣
接する他の円弧候補折線が所定の角度範囲内に接続され
ている一連のものを１つにまとめ、このまとめた円弧候
補折線群に対する円弧の半径および中心点座標を求めて
折線中から円弧部分を粗く抽出して第11図テーブルに登
録することができる。以下円弧部分を粗く抽出する動作
について説明する。

第９図はベクトルテーブルを示す。これは、第８図細線
化・折線近似処理部１によって生成された折線データを
格納するものである。図中（ａ）を用いて示す始点側の
Ｘ座標、Ｙ座標、および端点情報には、夫々該当する折
線V_iの始点側の座標および分岐などの端点情報を格納す
る。図中（ｂ）を用いて示す終点側のＸ座標、Ｙ座標、
および端点情報には、夫々該当する折線V_iの終点側の座
標および分岐などの端点情報を格納する。図中（ｃ）を
用いて示す属性には、直線候補折線、円弧候補折線、お
よび歪候補折線に対応する情報を格納する。

第10図フローチャートを用いて第８図の動作を説明す
る。

第10図において、処理は、すべての折線データを生成
する状態を示す。これは、細線化・折線近似処理部３が
全ての折線V_i（ｉ＝１ないしｎ）に対して折線データを
生成して第９図ベクトルテーブルに格納することを意味
している。

処理は、長さによる分類を行う状態を示す。これは、
分類処理部４が、第９図ベクトルテーブルから読み出し
たすべての折線データの長さＬに対して、所定値L_MAXお
よびL_MINと比較し、L_MAXよりも長い場合は当該折線V_iを
直線候補折線と分類して第９図ベクトルテーブル中の属
性欄に“1"を格納し、L_MINよりも短い場合は当該折線V_i
を歪候補折線と分類して属性欄に“3"を格納し、いずれ
でもない場合は当該折線V_iを円弧候補折線と分類して属
性欄に“2"を格納することを意味している。尚、折線デ
ータの長さＬは、第９図ベクトルテーブルの始点側座標
と終点側座標とに基づいて算出すればよい。

処理は、円弧候補を抽出する状態を示す。これは、以
下処理ないしによって実行される。

処理は、分岐点をはさまない円弧候補ベクトル２本を
円弧候補として抽出する状態を示す。これは、第９図ベ
クトルテーブル中の属性が円弧候補折線を意味する“2"
が格納されている隣接する２つの折線V_iを検索し、その
座標などを読み出すことを意味している。

処理は、２本の折線V_iのベクトルの内角θを利用して
円弧候補ベクトルを追跡する状態を示す。この時、歪候
補ベクトルに接していたら、そこで追跡を終了する。こ
れは、第12図（イ）に示すように、図中で読み出した
隣接する２本の折線V_i例えば折線V₁およびV₂のベクトル
の内角θが、所定範囲内例えば90°よりも大きくかつ18
0°よりも小さい範囲に存在するか否かを判別し、存在
する場合には、これを円弧候補として抽出することを意
味している（これは、処理で第11図円弧候補ベクトル
テーブルに登録例えばV₁、V₂・・・として登録する）。
以下同様に、次の円弧候補ベクトルについて順次抽出す
る。また、追跡途中で、分岐点にぶつかった場合には、
第12図（ロ）に示すように、すべての折線V_iに対して内
角θを調べ、最適な折線V_iを選び、追跡を続ける。更
に、この円弧候補ベクトルを追跡する途中で、歪候補ベ
クトルが現れた場合には、この歪候補折線をを飛び越し
て上記処理を継続する。この場合には、歪候補折線をは
さんだ２つの分岐点をまとめて１つの分岐点と考え、上
記普通の分岐点と同様に処理する。例えば第12図（ハ）
に示すように、折線V₁から追跡が行われた場合、折線
V₂、折線V₃、折線V₄について折線V₁との内角θを見て、
条件に合う折線V₂の方向に進むようにする。この方向に
対して一連の追跡を終了したら、次に、反対方向につい
ても同様に追跡を行う。

処理は、直線候補ベクトルに接したら、そこで追跡を
終了する状態を示す。これは、図中の処理中に、第９
図ベクトルテーブルの属性欄から直線候補折線を意味す
る“1"が読み出された場合、ここで追跡を終了すること
を意味している。

処理は、閉ループとして抽出された時には、フラグを
立てる状態を示す。これは、第11図円弧候補テーブル中
のループフラグの欄にフラグを立てておくことを意味し
ている。

処理は、円弧候補ベクトル列をテーブルに格納すると
共に、歪候補ベクトル情報や内角情報も保存する状態を
示す。これは、処理ないしによって追跡した結果を
第11図テーブルに登録することを意味している。第11図
円弧候補テーブル中には、処理ないしによって追跡
して条件を満足したベクトルの数、条件を満足した折線
V_iを登録する弧候補ベクトルテーブルをポイントするベ
クトル別ポインタ、条件を満足した一連の円弧候補折線
の始点および終点の座標（Ｘ、Ｙ）、閉ループを表すル
ープフラグ、それから追跡によって得られた一連の折線
に対して算出された円弧の半径およびこの円弧の中心点
座標（Ｘ、Ｙ）が格納される。

以上のように、第９図ベクトルテーブルに折線データを
格納し、この折線データに基づいて、円弧候補折線、歪
候補折線、および直線候補折線に分類し、この分類した
円弧候補折線のうち隣接するものについて内角θに基づ
いて円弧候補となるものを抽出し、この抽出した円弧候
補を第11図テーブルに登録する。

〔発明の効果〕

以上説明したように、本発明によれば、１つの円弧候補
を構成する各折線ベクトルの仮半径および仮中心点に基
づいて円弧候補を分割処理すると共に、複数の円弧候補
に対する夫々の仮半径、仮中心点および端点間の距離に
基づいて円弧候補の結合処理を行う構成を採用している
ため、粗く抽出された折線の円弧候補に対して更に厳密
な条件を適用して原図形パターンにより忠実な円弧部分
を抽出することができる。また、円弧分割処理および円
弧結合処理をそれぞれ独立に別個に取り扱うため、原図
形の種類や図形の処理の用途などに適応させた最適な円
弧部分を抽出することができる。

【図面の簡単な説明】

第１図は本発明の原理構成図、第２図は本発明の動作説
明フローチャート、第３図は円弧分割処理部の動作説明
フローチャート、第４図および第５図は円弧分割処理の
動作説明図、第６図は円弧結合処理部の動作説明フロー
チャート、第７図は円弧結合処理の動作説明図、第８図
は円弧抽出処理の原理構成図、第９図はベクトルテーブ
ル、第10図は円弧抽出処理の動作説明フローチャート、
第11図はテーブル例、第12図は円弧抽出処理の動作説明
図を示す。 図中、１は円弧分割処理部、２は円弧結合処理部を表
す。

Claims (1)

【特許請求の範囲】
1. 【請求項１】図形を細線化・折線近似して生成した複数
   の折線から所定の条件に基づいて抽出された折線列を円
   弧候補として登録するテーブルと、 上記テーブルに登録された円弧候補の折線の仮半径Riを
   順次求めて比較し、その差が所定値以上となった点で、
   円弧候補を分割する円弧分割処理部（１）と、 上記テーブルに登録された円弧候補の中の任意の２つの
   円弧候補について夫々算出した仮半径の差および仮中心
   点の差が夫々所定値よりも小さく、かつ両者の端点の距
   離が所定値以下の場合に、１つの円弧あるいは円に結合
   する円弧結合処理部（２）とを備え、 円弧候補に対して上記分割または結合を行って円弧部分
   を抽出するようにしたことを特徴とする円弧抽出装置。