JPH07129772A - 円弧の始終点認識方法および装置 - Google Patents

Abstract

(57)【要約】 【目的】線図形から円弧部分の始終点を検出する方法で
あって、計算量が少なくかつノイズの影響を受けにくい
方法を提供する。 【構成】線図形に折れ線近似処理を施し（ステップ２
３）、円弧の端点を認識する（ステップ２５）。円弧端
点の認識は、円弧と直線との接続点において、折れ線
近似による線分が直線側で長く円弧側で短くなり、直
線側での線分と円弧側での線分とのなす角が２直角では
ないがかなり大きい、の２条件が成立することを利用し
て行なう。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、２値画像に対する特徴
抽出に関し、特に、与えられた線図形から円弧部分を抽
出するためにこの円弧部分の始点と終点とを認識する、
円弧の始終点認識方法および装置に関する。

【０００２】

【従来の技術】手書き入力によって入力された線図形や
イメージスキャナで読み込まれた線図形に対して特徴抽
出を施し、その線図形がどのような図形要素（直線、線
分、円弧など）から構成されているかを認識することが
行なわれている。この場合、入力される線図形は、１個
の図形要素のみからなることは少なく、線分や円弧が連
結されたものであることが多い。

【０００３】ここで、線図形から円弧部分の端点（始点
と終点）を抽出する従来の方法について、図５を用いて
説明する。ここでは、図５(a)に示すような線図形９１
が入力されたものとする。

【０００４】まず、必要に応じて細線化処理を行なった
のち、図５(b)に示すように、この線図形９１を比較的
細かなベクトルに分割してベクトル化を行なう。得られ
たベクトル列がｖ(１),ｖ(２),...,ｖ(ｎ)で表わされ
る。そして、隣接するベクトル相互がなす角ａ(１),ａ
(２),...,ａ(ｎ−１)を求める。角ａ(i)は、ベクトルｖ
(ｉ)とベクトルｖ(ｉ＋１)のなす角である。そして、こ
の角の値の変化率ｇ(１),ｇ(２),...,ｇ(ｎ−２)を求め
る。変化率ｇ(ｉ)は、ｇ(ｉ)＝ｇ(ｉ＋１)−ｇ(ｉ)で表
わされる。

【０００５】そして、変化率が０であるベクトルをグル
ープ化する。図５(b)に示した例では、グループＡ〜Ｃ
の３グループが生成している。そして、隣接するベクト
ル間の角ａ(ｉ)がほぼ０°となっているグループを直線
グループとし、その他のグループを円弧グループする。
変化率ｇ(ｉ)が変化する点であって、この点のどちらか
一方側が直線グループであり他方側が円弧グループであ
るならば、この点を円弧の端点すなわち始点か終点のど
ちらかとして認識する。以上の処理により、円弧の始終
点が抽出されたことになる。

【０００６】

【発明が解決しようとする課題】上述した従来の円弧の
始終点認識方法では、入力された線図形を細かいベクト
ルに分割するので、多大な計算機パワーと計算時間とを
必要とし、かつ入力される線図形中に含まれる手ブレな
どのノイズの影響を受けやすく前処理を必要とするなど
の問題点がある。

【０００７】本発明の目的は、計算量が少なくかつノイ
ズの影響を受けにくい、円弧の始終点認識方法および装
置を提供することにある。

【０００８】

【課題を解決するための手段】本発明の円弧の始終点認
識方法は、線図形を入力する入力工程と、入力された線
図形に対して折れ線近似処理を施し、連結した複数の線
分に前記線図形を分割する折れ線近似工程と、前記線図
形に対応する複数の線分中から１つの線分を選択して該
選択された線分を注目線分とするとき、以下の２条件
およびの両方、条件；前記注目線分に隣接する２線
分のうちの一方の線分の長さが前記注目線分の長さおよ
び前記２線分のうちの他方の線分の長さのそれぞれに比
べて所定の比率以上で大きく、条件；前記一方の線分
と前記注目線分がなす角が２直角ではないが２直角に近
い、および以下の２条件およびの少なくとも一方、
条件；前記注目線分の長さと前記他方の線分の長さが
ほぼ等しく、条件；前記一方の線分と前記注目線分が
なす角が、前記注目線分と前記他方の線分がなす角とほ
ぼ等しい、の各条件について当該条件が成立するかを調
べ、調べられた条件の中で不成立のものがない場合に、
前記一方の線分と前記注目線分の接続点を円弧部分の端
点として認識する円弧端点認識工程とを有し、前記線図
形に対応する各線分について前記円弧端点認識工程を順
次適用する。

【０００９】本発明の円弧の始終点認識装置は、線図形
を入力する入力手段と、入力された線図形に対して折れ
線近似処理を施し、連結した複数の線分に前記線図形を
分割する折れ線近似手段と、前記複数の線分を格納する
格納手段と、前記格納手段から１つずつ線分を読み出し
て注目線分とし、以下の２条件およびの両方、条件
；前記注目線分に隣接する２線分のうちの一方の線分
の長さが前記注目線分の長さおよび前記２線分のうちの
他方の線分の長さのそれぞれに比べて所定の比率以上で
大きく、条件；前記一方の線分と前記注目線分がなす
角が２直角ではないが２直角に近い、および以下の２条
件およびの少なくとも一方、条件；前記注目線分
の長さと前記他方の線分の長さがほぼ等しく、条件；
前記一方の線分と前記注目線分がなす角が、前記注目線
分と前記他方の線分がなす角とほぼ等しい、の各条件に
ついて当該条件が成立するかを調べ、調べられた条件の
中で不成立のものがない場合に、前記一方の線分と前記
注目線分の接続点を円弧部分の端点として認識する円弧
端点認識手段と、を有する。

【００１０】

【作用】線図形に対して折れ線近似処理を施した場合、
この線図形は、いくつかの頂点とこれら頂点を結ぶ線分
とからなる折れ線で近似される。この場合、頂点間の距
離は、もとの線図形において曲率が小さいところでは長
く、曲率が大きいところでは短くなる。また一般の線図
形では、円弧部分はその前後に直線（線分）部分が連結
されていることが多い。

【００１１】そこで直線部分と円弧部分との接続点に着
目すると、条件；折れ線近似による線分が直線側で長
く円弧側で短くなり、条件；直線側での線分と円弧側
での線分とのなす角が２直角ではないがかなり大きい、
の２条件が成立している。したがって、この２条件が成
立する点が直線部分と円弧部分の接続点の候補となる。
条件は、Ｖ字型に折れ曲がっているような点を検出す
るのを防ぐための条件でもある。実際には、円弧以外の
曲線が直線と接続している場合も、これら条件,が
成立する可能性がある。そのため、条件；円弧側での
各線分の長さがほぼ等しい、条件；連続する３線分間
で隣接する２線分のなす角がほぼ等しい、の２条件の少
なくとも一方の成立を確かめる必要があり、条件,
の成立がどちらかでも否定された場合には円弧部分の端
点ではないとする必要がある。

【００１２】したがって、条件,の両方と、条件,
の少なくとも一方について、これら条件の成立を調
べ、調べた結果において不成立のものがない場合に、そ
こが直線と円弧との接続点、すなわち円弧部分の端点
（始点あるいは終点）であると結論づけることができ
る。

【００１３】複数の線分への折れ線近似処理による分割
の刻みは、従来法における細かいベクトルへの分割の刻
みに比べ、かなり粗くなるので、その分、計算量を削減
でき、計算に要する時間も短くなる。また、刻みが粗い
分だけ、ノイズの影響を受けにくくなり、ノイズによる
誤認識の影響が後段側に及ばなくなる。

【００１４】実際に計算を行なう際、線分よりもベクト
ルとしてデータを扱う方が計算が容易になることがある
が、このような場合には、折れ線近似工程において、複
数の線分の代りに、それぞれ線図形の一方の端点側から
他方の端点側に向かう複数のベクトルが得られるように
し、円弧端点認識工程ではこのベクトルに対して条件判
定が行なわれるようにすればよい。この場合、当業者に
は容易に理解できることであるが、（向きの定義されな
い）線分相互の角の定義と、（向きを有する）ベクトル
相互の角の定義とは異なるから、円弧端点認識工程ある
いは円弧端点認識手段での条件判断では、角の定義が異
なることを考慮する必要がある。

【００１５】ここで、折れ線近似処理の概要について、
図４を用いて簡単に説明する。

【００１６】折れ線近似処理では、点列で表わされた線
図形を対象とし、入力点列には、細線化された端点と通
過点のみが存在するものとする。入力点列の一方の端点
を始点とし、他方の端点を終点とする。入力パラメータ
として、errmax,conemaxの２つの正定数を定義する。

【００１７】また、次の点を探す操作とは、入力点列を
出発点より走査して行き、errmax離れた点を探す操作の
ことである。ただし、一度、走査した点は走査しない、
すなわち、後戻りしないものとする。次の点を探す操作
を行なう点を出発点とし、次の点を探す操作により得ら
れた点を（折れ線近似処理での）注目点とし、出発点と
注目点との間の点（次の点を探す操作によって過去に探
された点）を過去の点とする。さらに、出発点と注目点
を結ぶ線分を垂直２等分線とし底辺の長さがconemaxの
２倍である２等辺三角形（この三角形の頂点は出発点で
ある）を定義するとき、この２等辺三角形の内部の領域
をcone領域とする。複数のcone領域の共通領域を共通co
ne領域とする。

【００１８】このように定義を行ない、さらにまた、
（折れ線近似による）頂点とは、折れ線近似の結果出力
される点のこととし、仮の頂点とは、頂点として仮に記
憶する点のこととする。始点と終点は頂点である。

【００１９】まず、始点を出発点とし（ステップ４
１）、出発点を注目点とする（ステップ４２）。そし
て、注目点の次の点を探し、その点を注目点とする。ま
た、その注目点を仮の頂点とする（ステップ４３）。さ
らに、注目点の次の点を探し、その点を注目点とする
（ステップ４４）。

【００２０】ここで、注目点が過去の点と比べ、出発点
より遠くにあるかどうかを調べる（ステップ４５）。注
目点が遠くにない場合にはステップ４９に進み、遠くに
ある場合には、その注目点が過去の点についての共通co
ne領域に存在するかどうかを調べる（ステップ４６）。
共通cone領域にない場合にはステップ４８に進み、共通
cone領域にある場合には、その注目点を仮の頂点とし
（ステップ４７）、ステップ４８に進む。

【００２１】ステップ４８では、共通cone領域が全く存
在しなくなったかどうかが調べられる。共通cone領域が
存在する場合には、ステップ４４に進んで次の注目点を
探索し、共通cone領域が全く存在しない場合には、ステ
ップ４９に進む。

【００２２】ステップ４９では、仮の頂点を頂点とし、
その頂点を新たな出発点とし、ステップ４２に戻る。

【００２３】以上の動作を始点から終点まで繰り返すこ
とにより、線図形の折れ線近似が行なわれる。

【００２４】

【実施例】次に、本発明の実施例について図面を参照し
て説明する。図１は、本発明の一実施例の円弧の始終点
認識装置の構成を示すブロック図である。

【００２５】この円弧の始終点認識装置は、線図形が入
力するタブレットやイメージスキャナなどの入力部１、
入力された線図形に対して細線化処理を行なう細線化部
２、細線化処理の施された線図形に対して折れ線近似処
理を施す折れ線近似処理部３、折れ線近似処理の結果と
して得られた複数のベクトルを格納する格納部４、格納
部４からベクトルを取り出し、上述の４条件〜がい
ずれも成立するかどうかを調べていずれも成立する場合
に円弧の端点として認識する円弧端点認識部５とによっ
て構成されている。

【００２６】次に本実施例の動作について、図２(a)を
用いて説明する。

【００２７】まず、入力部１によって線画像が入力され
（ステップ２１）、細線化部２において、この線画像に
対して細線化処理が施される（ステップ２２）。ここで
は、細線化処理後の線図形が図３(a)で表わされたとす
る。

【００２８】次に、細線化処理後の線図形１１に対し
て、折れ線近似処理が施す（ステップ２３）。ここで
は、図３(b)に示されるように、線図形１１の一端側か
ら他端側に向かう複数のベクトルに、入力された線図形
１１が分割されたする。このように生成されたベクトル
は、格納部４に格納される。そして線図形の一端に最も
近い折れ線近似の頂点（ベクトルの接続点）を注目点と
する（ステップ２４）。

【００２９】次に、円弧端点認識部５は、格納部４を参
照し、上述の４条件〜の成立の有無を確認し、設定
された注目点が円弧端点であるかどうかの識別を行なう
（ステップ２５）。そして、折れ線近似の全ての頂点に
ついて上記ステップ２５が行なわれたどうかを判定し
（ステップ２６）、注目点として設定されたことがない
頂点がある場合にはその頂点を新たな注目点として（ス
テップ２７）、ステップ２５に進み、全ての頂点につい
てステップ２５が実行されている場合には処理を終了す
る。

【００３０】ここで、円弧端点認識部４の動作につい
て、図２(b)を用いて説明する。

【００３１】線図形上で連続する３つベクトルをベクト
ルａ〜ｃとし、ベクトルａの終点（すなわちベクトルｂ
の始点）が注目点であるようにする。まず、「ベクトル
ａがベクトルｂおよびベクトルｃよりかなり長い」とい
う条件が成立するかのチェックを行ない（ステップ３
１）、成立する場合にはステップ３２に進み、不成立の
場合にはステップ３６に進んでこの注目点が円弧の端点
ではないとする。具体的には、

【００３２】

【数１】 の成立をチェックする。ここでｒは０＜ｒ＜１の定数で
あるが、例えば、０.５に設定する。

【００３３】ステップ３２では、「ベクトルｂとベクト
ルｃの長さがほぼ同じである」という条件が成立するか
どうかがチェックされる。成立しない場合には、上述と
同様にステップ３６に進んでこの注目点が端点ではない
とし、成立する場合には、ステップ３３に進む。具体的
には、ｓを定数として、

【００３４】

【数２】 の成立をチェックする。ｓは例えば２程度に設定する。

【００３５】ステップ３３では、「ベクトルａとｂのな
す角が０°ではないが０°に近い」という条件の成立の
有無が確認される。この条件は、線分のなす角が２直角
ではないが２直角に近いという条件と、等価である。条
件が成立しない場合には、上述と同様にステップ３６に
進んでこの注目点が端点ではないとし、成立する場合に
は、ステップ３４に進む。具体的には、ベクトルａとｂ
のなす角をθとし、ｔを定数として、

【００３６】

【数３】θ＜ｔ の成立をチェックする。ｔは例えば６０°程度に設定す
る。

【００３７】ステップ３４では、「ベクトルａとベクト
ルｂのなす角がベクトルｂとベクトルｃのなす角とほぼ
同じ」という条件が成立するかどうかのチェックがなさ
れる。条件が成立しない場合には、上述と同様にステッ
プ３６に進んでこの注目点が端点ではないとし、成立す
る場合には、ステップ３５に進み、この注目点が円弧の
端点であると最終的に結論付ける。具体的には、ベクト
ルａとｂのなす角をθとし、ベクトルｂとｃのなす角を
φとし、ｕを定数として、

【００３８】

【数４】 の成立をチェックする。例えばｕは２程度に設定する。
以上のようにして、注目点ごとにその注目点が円弧の端
点であるかどうかの識別が行なわれる。ここで使用され
るパラメータｒ,ｓ,ｔ,ｕは、入力される線図形の品位
や種類に応じて、適宜に設定することができる。

【００３９】なお、ここで示したベクトルによる例で
は、注目点に関して前方方向と後方方向とに対する操作
が対称的ではないので、同じ注目点に関し、ベクトルａ
をベクトル−ｂ'、ベクトルｂをベクトル−ａ'とし、さ
らにベクトルａより１つ始点側にあるベクトルをベクト
ルｄとするとき、ベクトルｄをベクトル−ｃ'として、
これらベクトルａ',ｂ',ｃ'について同様の処理（逆転
処理）を行なう必要がある。逆転処理を行なわないと、
円弧の端点についての検出漏れを生じる。線分で考えた
場合には、方向が考慮されていないので、逆転処理を行
なう必要はない。

【００４０】

【発明の効果】以上説明したように本発明は、入力され
た線図形に折れ線近似処理を施し、円弧部分と直線部分
の接続点において、折れ線近似による線分が直線側で
長く円弧側で短くなり、直線側での線分と円弧側での
線分とのなす角が２直角ではないがかなり大きい、の２
条件が成立することに着目することにより、細かいベク
トルを生成する必要がなくなって演算量、演算時間とも
削減され、かつノイズの影響を受けにくくなるという効
果がある。

【図面の簡単な説明】

【図１】本発明の一実施例の円弧の始終点認識装置の構
成を示すブロック図である。

【図２】(a)は図１の装置の動作を示すフローチャート
であり、(b)は円弧端点認識部の動作を示すフローチャ
ートである。

【図３】(a),(b)は、図１の装置における円弧の始終点
認識方法を説明する図である。

【図４】折れ線近似処理を説明するフローチャートであ
る。

【図５】(a),(b)は従来の円弧の始終点認識方法を説明
する図である。

【符号の説明】

１ 入力部 ２ 細線化部 ３ 折れ線近似部 ４ 格納部 ５ 円弧端点認識部 ２１〜２７，３１〜３６ ステップ

Claims (3)

【特許請求の範囲】
1. 【請求項１】 与えられた線図形から円弧部分の始点お
   よび終点を探索する始終点認識方法であって、 線図形を入力する入力工程と、 入力された線図形に対して折れ線近似処理を施し、連結
   した複数の線分に前記線図形を分割する折れ線近似工程
   と、 前記線図形に対応する複数の線分中から１つの線分を選
   択して該選択された線分を注目線分とするとき、以下の
   ２条件およびの両方、 条件；前記注目線分に隣接する２線分のうちの一方の
   線分の長さが前記注目線分の長さおよび前記２線分のう
   ちの他方の線分の長さのそれぞれに比べて所定の比率以
   上で大きく、 条件；前記一方の線分と前記注目線分がなす角が２直
   角ではないが２直角に近い、および以下の２条件およ
   びの少なくとも一方、 条件；前記注目線分の長さと前記他方の線分の長さが
   ほぼ等しく、 条件；前記一方の線分と前記注目線分がなす角が、前
   記注目線分と前記他方の線分がなす角とほぼ等しい、の
   各条件について当該条件が成立するかを調べ、調べられ
   た条件の中で不成立のものがない場合に、前記一方の線
   分と前記注目線分の接続点を円弧部分の端点として認識
   する円弧端点認識工程とを有し、 前記線図形に対応する各線分について前記円弧端点認識
   工程を順次適用することを特徴とする円弧の始終点認識
   方法。
2. 【請求項２】 折れ線近似工程で得られる複数の線分
   が、それぞれ、線図形の一方の端点側から他方の端点側
   に向かうベクトルとして表わされ、円弧端点認識工程で
   は前記ベクトルに対して条件判定が行なわれる請求項１
   に記載の円弧の始終点認識方法。
3. 【請求項３】 与えられた線図形から円弧部分の始点お
   よび終点を探索する始終点認識装置であって、 線図形を入力する入力手段と、 入力された線図形に対して折れ線近似処理を施し、連結
   した複数の線分に前記線図形を分割する折れ線近似手段
   と、 前記複数の線分を格納する格納手段と、 前記格納手段から１つずつ線分を読み出して注目線分と
   し、以下の２条件およびの両方、 条件；前記注目線分に隣接する２線分のうちの一方の
   線分の長さが前記注目線分の長さおよび前記２線分のう
   ちの他方の線分の長さのそれぞれに比べて所定の比率以
   上で大きく、 条件；前記一方の線分と前記注目線分がなす角が２直
   角ではないが２直角に近い、および以下の２条件およ
   びの少なくとも一方、 条件；前記注目線分の長さと前記他方の線分の長さが
   ほぼ等しく、 条件；前記一方の線分と前記注目線分がなす角が、前
   記注目線分と前記他方の線分がなす角とほぼ等しい、の
   各条件について当該条件が成立するかを調べ、調べられ
   た条件の中で不成立のものがない場合に、前記一方の線
   分と前記注目線分の接続点を円弧部分の端点として認識
   する円弧端点認識手段と、を有することを特徴とする円
   弧の始終点認識装置。