JPH01120680A - 近似図形発生装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野Ｊ 本発明は近似図形発生装置、％に１図面の自動読取等で
図形の輪郭を円弧区間と直線区間に分離し、分離された
各区間に対し、直線または円弧の近似図形を発生させる
近似図形発生装置に関する。

〔従来の技術〕

従来の近似図形発生装置には、特開昭５９−１２１５６
４号公報に示されているように図形入力装置がある。従
来の近似図形発生装置は画像入力装置と記憶装置と点列
データ作成装置と、特徴量算出装置と、特徴量解析装置
と、図形データ作成装置とを含んで構成される。次に従
来の近似図形発生装置について図面を参照して詳細に説
明する。Ｍ６図に示す近似図形発生装置は画像を入力す
る画像入力袋ｆ１３０と入力された画像を記憶する記憶
装置１３１と入力された画像の線の中心となるような点
を抽出し、点列データを作成する点列データ作成装置３
２と作成された点列データを記憶する記憶装置３３と点
列データから直線性を表゛わす特徴蓋を算出する特徴量
算出装置３４と、−連の特徴蓋から直線や円弧や角を判
定し、点列を分離する特徴量解析装置３５と解析結果、
直線や円弧などをコード化し図形データを作成する図形
データ作成装置３６を含んでいる。ここで、画像入力装
置３０は画像を入力し、入力された画像は記憶装置３１
に記憶される。記憶された画像は処理のために記憶装置
３１から読み出され、点列データ作成装置３２に入れら
れる。点列データ作成装置３２では、細線化処理及び細
線化された図形のチェーンコード化を行なう。ここで細
線化処理及びチェ−ンコード化については種々の文献に
よシ、その動作は明らかで１本発明の範躊ではないので
説明は省略する。チェーンコード化された点列データは
記憶装置３３に記憶される。

次に記憶装置３３から点列データが読み出され、特徴量
算出装置３４で特徴蓋ｊ（以後、特徴蓋と呼ぶ）の算出
が行なわれる。

第７図において特徴蓋はチェーンコード化されたある画
素に着目した時（以後、着目画素と呼ぶ）。

その着目画素４０の前後に点（ｋ＝１〜ｎ）離れたとこ
ろにある画素ｋｌ、に２の間を結んだ線分４２と着目画
素４０との距離４１で表わされる。

第８図は特徴蓋の一例を示す図である。直線部分を構成
する点列の特徴蓋は小さい値をとり、角付近の点列の特
徴蓋は山形の形状をとシ、円弧部分を構成する点列の特
徴蓋はある一定の値に近い一値をとることから区間５０
，５２ｉｊ直線を表わす区間（以後直線区間と呼ぶ）０
区間５１は角を表わす区間（以後角区間と呼ぶ）、区間
５３は円弧を表わす区間（以後円弧区間と呼ぶ）と判断
できる。

轡微量解析装置３５では、直線区間、角区間。

円弧区間が前記したような特性を持つことからある基準
値１１で特徴蓋を分割し、１１以下の特徴蓋を持つ一連
の点列を直線区間とする。

欠に１直線区間以外の区間の各点列の特徴蓋の分散を求
め、分散の大きい区間を角区間、小さい区間を円弧区間
とする。さらに角区間に対しては角の頂点に対応する点
（以後角点と呼ぶ）を求め隣接している区間を角点まで
延長する。この様にして点列は最終的な直線区間５４．
５５と円弧区間５６に分離される。

特徴量解析装置３５により求められた分離データは記憶
装置３３に記ｔｉされ、記憶された分離データは図形デ
ータ作成装置３６に入れられる。

図形データ作成装置３６では直線区間なら直線の始点、
終点９円弧なら始点、終点、中心位置などの情報を作成
し、作成された図形データは記憶装置３３に記憶される
。

〔発明が解決しようとする問題点〕

上述した従来の近似図形発生装置は、点列データを作成
する際細線化処理を行なうため図形周囲の情報が失なわ
れてしまい入力図形が面積を持つ面図形で図形周囲の情
報が必要とされる場合には使用できず、また特徴蓋の解
析を、第１段階では点列データを直線区間と、円弧区間
または角区間の２りに分類し、第２段階で直線区間以外
の区間の各点列の特徴蓋の分散を調べ、分散が大きい区
間を角区間、小さい区間を円弧区間と判定し、第３段階
で角区間に関しては角点を求め隣接する区間を角点まで
延長して最終的な直線区間と円弧区間に分離しておシ最
終的な直線区間と円弧区間を求めるために第１段階から
第３段階までの処理を行なわなければならず、これらの
処理を行なった後に図形データの作成を行なっているの
で処理が複雑であシ、また従来例で引用した入力図形の
例のように直線区間と円弧区間が滑らかに変化する場合
は直線区間と円弧区間の分離を行なえるが直線区間から
円弧区間へと急激に変化する場合、直線区間と円弧区間
の分離が困難であるという欠点があった。

〔問題点を解決するための手段ｊ 本発明の近似図形発生装置は画像を入力するための画像
入力装置と入力された画像を二値化するための二値化装
置と、二値比された画像の輪郭を点列のつながりとして
取シ出す輪郭点列データ作成装置と作成された輪郭点列
データを記憶するための記憶装置と記憶された輪郭点列
データを直線区間１円弧区間に分離するために用いる特
徴量を算出する特徴量算出装置と算出された特徴量から
直線区間と円弧区間を分離するための分離点抽出装置と
抽出された分離点から分離点と分離点の間の区間に対し
、直ＩＩＩＪ！または円弧の近似図形を発生させる線分
近似装置と、隣接する線分を取シ出し同一線分であると
判定したら分離点を取シ除き１つの線分とする隣接線分
調査装置とを含んで構成される。

〔実施例〕

次に、本発明の実施例について、図面を参照して詳細に
説明する。

第１図は本発明の一実施例を示すプロ、り図である。

第２図（ａ）は入力図形の第一の例で図形の輪郭線は直
線あるいは円弧によって＃ＩＩ成される。第２図（ｂ）
はｇ２図（ａ）で示される入力図形の輪郭点列を表わし
ている。

第３図は第２図（ｂ）に示す輪郭点列の特徴量ｌの変化
を表わす図である。

第４図（ａ）は入力図形の第２の例を示す図、第４図（
ｂ）は第４図（ａ）　Ｋ示す入力図形の隣接線分調査後
の分離点を表わす図である。

第５図１８）は隣接線分調査装置の動作の説明図、第５
図［ｂ）は第５図（ａ）Ｋ示す線分の隣接線分調査後の
分離点を表わす図である。なお、本実施例では、本発明
の理解を容易にするために入力図形の第１の例と第２の
例を用いて詳細に説明する。

第１図に示す近似図形発生装置は、画像を入力するため
の画像入力装置１と、入力された画像を二値化するため
の二値化装置２と、二値化された画像の輪郭を点列のつ
ながりとして取り出しチェーンコード化する輪郭点列デ
ータ作成装置３と、作成された輪郭データを記憶するた
めの、記憶装置４と、輪郭点列データを直線区間１円弧
区間に分離するために用いる特徴量を算出する特徴量算
出装置５と、算出された特徴量から直線区間と円弧区間
を分離するための分離点を抽出する分離点抽出装置６と
、抽出された分離点から分離点と分離点の間の区間に対
し直線または円弧の近似図形を発生させる線分近似装置
７と、隣接する線分を取シ出し同一線分であると判定し
たら分離点を取シ除き、１つの線分とする隣接線分調査
装置８とを含んで構成される。

画像入力装置１は画像を入力し入力された画像は二値化
装置２に入れられる。二値化装置２では入力された画像
の二値化を行ない、二値化された画像は輪郭点列データ
作成装置３に入れられる。

輪郭点列データ作成装置３では二値化された入力図形の
エツジトレース処理及びチエインコード化を行なう。エ
ツジトレース処理は図形の輪郭をトレースする処理のこ
とでトレースした情報からチェーンコード化が行なわれ
る。

第２図（ａ）は入力図形の一例で図形の輪郭線は直線あ
るいは円弧によシ構成される。第２図（ｂ）は第２図ｔ
ａ）で示される入力図形にエツジトレース処理を行なっ
た後の輪郭点列を表わしている。

チエインコード化された輪郭点列データは記憶装置４に
記憶される。次に記ｔぽ装置４から輪郭点列データが読
み出され、特徴量算出装置５で特徴量の算出が行なわれ
る。

第７図において特徴Ｊｋはチェーンコード化されたある
画素に着目した時（以後着目画素と呼ぶ）、その着目画
素４０の前後に点（ｋ＝ｘ〜ｎ）Ｍれたところにある画
ｇｋｌ、に２の間を結んだ線分４２と着目画素４０との
距離４１で表わされる。

第３図は第２図ｔｂ）に示す輪郭点列の特徴量を表わし
ている。ここで区間１４．１５．１７は直線区間１区間
１６は、円弧区間を表わしている。特徴ａＸＸ張装置で
算出された特徴量のデータは分離点抽出装置６に入れら
れる。

第２図において直線区間と直線区間を分離する分離点１
６．１１は第３図における分離点１０ｂ。

１１ｂに相当しており、分離点１０ｂ、ｌｌｂで特徴量
は山形の形伏をとる。また第２図において直線区間と円
弧区間を発酵する分離点１２．１３は第３図における分
離点１２ｂ、１３ｂＫ相当しておシ分離点１２・：ｂＪ
゛１３ｂで特徴量は円弧区間における特徴量の値と直線
区間における特徴量の値との間の値をとる。

分離点抽出装置６では、これらの分離点を抽出するため
に分離基準値７２．　ｉ１３を導入する。

分離基準値１２は直線区間と直線区間を分離するために
用い、円弧区間での特徴量よシも大きい値を設定する。

分離基準値１２以上の特徴量が連続する区間で特徴量が
最大値をとる点を直線区間と直線区間を分離する分離点
として抽出する。この時点列の始点と終点は隣接点とし
て考えることは当然である。

分離基準値１３は直線区間と円弧区間を分離するために
用い、直線区間での、特徴量と円弧区間での特徴量との
間の値を設定する。次に％微量と分離基準値１３との交
点を求め直線区間と円弧区間を分離する分離点として抽
出する。ただし、直線区間と直線区間を分離する分離点
が抽出されたらその前後にある特徴量と分離基準値１３
との交点は分離点として抽出しない。以上のような方法
で％徴童と分離基準値ｉＪ２゜１３によシ、分離点が抽
出される。

分離点抽出装置６で抽出された分離点の情報は線分近似
装置７に入れられる。線分近似装置７は抽出された分離
点から隣シ合う分離点を両端とする各区間に対し、直線
または円弧の近似図形を発生させる。

区間両端の分離点が分離基準値１３と特徴量との交点と
して求められた分離点である場合その区間は円弧区間で
あると判定し、円を表わす式で近似する。それ以外の区
間は直線区間であると判定し、直線を表わす式で近似す
る。

以下同様に第２の入力図形の例を用いて本発明の詳細な
説明する。

第４図ｔａ）は第２の入力図形の例で輪郭点列のｍ−を
表わしている。第４図（ｂ）は第４図（ａ）に示す輪郭
点列の特徴量！を表わしている。分離基準値１２．１３
を用いて分離点を求めると分離点２１ｂ。

２２ｂ、２３ｂが抽出され、区間２４．２５゜２６は直
線区間として直線の式に近似され、区間２７は円弧区間
として円の式に近似される。分離点２１において図形輪
郭は直線から円弧へと変化するがその変化が滑らかでは
ないため特徴量は山形の形伏をとなる。また画素２２で
は図形輪郭の形伏から特徴ｔｌが０になる。したがって
分離基準値１２，１３／Ｃよシ分Ｍ点を抽出すると第４
図［ｂ）　Ｋ示すよ５１Ｃ輪郭の形伏から判断すると、
本来は分離点でない分離点２３ｂが抽出され、本来円弧
区間の一部である線分２６が直線区間とされ直線に近似
される。

線分近似装置７で近似された線分の情報は隣接線分調査
装置８に入れられる。以下線分近似調量の機能の概略を
説明し、その後動作について詳細に説明する。

線分近似調査装置では線分近似された線分のうち隣接す
る２つの線分を順番に取シ出し、２つの線分のうち点列
を構成する画素数（以下、構成画素数という）の多い刀
の線分の近似式と、他方の線分の構成画素との近似度（
近似度については後述する）を求め、°その値が基準値
未満であれば２つの線分間の分離点を取シ除き、構成画
素数が多い刀の線分の近似式を新しい線分の近似式とし
て用いる。

以下第５図を使って線分近似調量の動作を説明する。

第５図（ａ）Ｋ図形の輪郭を構成する点列の一部と抽出
された分離点８１．８２．８３と分離点Ｂｌ。

Ｂ２を両端とする点列を近似した近似式ｍ１と、分離点
８２．Ｂ３を両端とする点列を近似した近似式ｍ２を示
す。

今、隣接線分調査装置でこの２つの線分を取り出したと
する。近似線分ｍｌの構成画素数は近似線分ｍ２の構成
画素数よりも多いので近似−分ｍ１と分離点Ｂ２，８３
間の点列との距離ｄ１の平均値（以下近似度と呼ぶ）を
求める。近似度が基準値以下であれば分離点１：１２．
ｔ３３間の点列によシ構成される線分は近似線分ｍｌＫ
よって近似することができると判定し、２つの線分の間
にある分離点Ｂ２を取り除く。また、分離点Ｂｌ、Ｂ３
を両ｍ、ｂする新しい線分の近似式には近似式ｍｌを用
いる。

ただし近似度が基準値以上ならば例もしない。

第５図ｆｂ）は第５図１ａ）に示す２つの近似線分とそ
れらの構成画素によシ計算された近似度が基準値以下で
めった時に２つの線分を分離点Ｂｌ、Ｂ３を両端とする
１つの線分にして、その区間を近似式ｍ１で近似した結
果を表わしている。以上説明した内容から第４図Ｆａ）
に示す入力画像の点列の分離点２３は隣接線分装置によ
り取シ除かれ、第５図ｆｂ）に示すように分離点２０．
２１のみが正しい分離点として残る。

また第２図（ｂ）に示す７Ｘｌの入力図形の分離点は正
しく抽出されているので隣接線分装置装置により分な点
は灰化しない。

し発明の効果〕 本発明の近似図形発生装置は輪郭点列ｆ−タ作成装置と
、分離点抽出装置と隣接線分装置装置とを設けることに
より図形外周の情報が電装である面図形の輪郭の特徴を
解析できるとともに分離基準点１１，１２を設けて分に
よ点を抽出するので、角区間と円弧区間の区別をするた
めに区間の各点列の特徴音の分散を求めることや、隣接
する区間を角点まで蝙長する必要がなく、直線区間と円
弧区間の分離が簡単にでき、また直線区間から円弧区間
へ急激に変化する部分で余分に検出される分離点を取り
除くことによシ、正しい分離点を求めることがでさると
いう効果がある。

【図面の簡単な説明】

第１図は本発明の一夾施例を示すブロック図、第２図ｆ
ａ）は入力図形の第１の例を表わす図、第２図（ｂ）は
第２図（ａ）に示す入力図形の輪郭点列を表わす図、第
３図は第２図ｔｂｌの輪郭点列の特徴音と分離点検出の
説明図、第４図（ａ）は入力図形の第２の例の輪郭点列
の一部を表わす図、巣４図（ｂｌは第４図（ａ）に示す
点列の特徴音と分離点検出の説明図、第４図１ｃ）は第
４図１２）に示す一分の隣接線分調食後の分離点の説明
図、第５図（ａ）は隣接線分装置装置の動作の説明図、
第５図ｉｂ）は第５図（ａ）に示す線分の隣接線分調食
後の分ｉ点の説明図、第６図は従来の一例を示すプロッ
クーー第７１．第８図は第６図における特徴音を説明す
るグラフである。 ■・・・・・・画像入力装置、２・・・・・・二値化装
置、３・・・・・・輪郭点列データ作成装置、４・・・
・・・記憶装置、５・・・・・・荷徴澁鼻出装置、６・
・・・・・分離点検出装置、７・・・・・・線分近似装
置、８・・・・・・隣接線分ｙ４食装置、１０〜↓３・
・・・・・分離点、１０′〜１３′・・・・・・分離点
、１４．１５．１７・・・・・・直線区間、１６・・・
・・・円弧区間、２０．２１．２３・・・・・・分離点
、２０’　、２１’。 ２３′・・・・・・分離点、２２．２２’・・・・・・
籍徴璽が０になる画素、２４〜２６・・・・・・直線区
間、２７・・・・・・円弧区間、３０・・・・・・画像
入力装置、３１．３３・・・・・・記憶装置、３２・・
・・・・点列データ作成装置、３４・・・・・・特９に
算出装置、３５・・・・・・特徴量解析装置、３６・・
・・・・図形データ作成装置、４０・・・・・・層目画
素、４１・・・・・・特徴社、４２・・・・・・線分、
５０．５２・・・・・・直煉区間、５１・・・・・・角
区間、５３・・・・・・円弧区間、５４．５５・・・・
・・最終的直線区間、５６・・・・・・Ｒ終曲円弧区間
。 伏ＦＦ人弁理士内厚　　音 ／θ〜１３・・ヌ端ＩＬ薇。 （ａ）（幻 第２　図 ／４．１５．／７−４７群２閘 ）乙−−ＩＦＩ５ρ−区閂 １ｂＱ〜１３トー冷り櫨。 ノ２．ノ３−−−今虜咋糾青匡 第３　図 （αン （呑） 第４７ も ｊ （α） 櫓Ｓ　ゾ 第　７　則

Claims (1)

【特許請求の範囲】
1. 画像を入力するための画像入力装置と、入力された画像
   を二値化するための二値化装置と、二値化された画像の
   輪郭を点列のつながりとして取り出す輪郭点列データ作
   成装置と、作成された輪郭点列データを記憶するための
   記憶装置と、記憶された輪郭点列データを直線区間、円
   弧区間に分離するために用いる特徴量を算出する特徴量
   算出装置と、算出された特徴量から直線区間と円弧区間
   を分離するための分離点を抽出する分離点抽出装置と、
   抽出された分離点から分離点と分離点の間の区間に対し
   直線または円弧の近似図形を発生させる線分近似装置と
   、隣接する線分を取り出し同一線分であると判定したら
   分離点を取り除き１つの線分とする隣接線分調査装置と
   を含むことを特徴とする近似図形発生装置。