JPH0362269A - 線画像近似方法および装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は紙面に描かれた図形を走査して入力された画像
を認識する図面認識方法およびその装置に関し、特に線
図形を含む画像の線構造を数値的に近似する方法および
その装置に関する。

（従来の技術） 図面画像を認識する処理の第１段階として、図面画像中
の線図形を構成する直線や曲線の線構造を抽出すること
が一般に行われる。入力線画像の線構造を線分と円弧近
似する従来の代表的な方式としては、同一出願人の提案
になる方式が特願昭６３−８７１２０号に開示されてい
る。この方式は、図形を走査して得られた線画像から各
画素における方向の値を求め、線上に於て線形な平均方
向変化率を有する線形方向区間を求め、方向変化率が所
定の閾値以上の線形方向区間を円弧または円に、閾値未
満の線形方向区間を線分に近似する方式である。

（発明が解決しようとする課題） しかしながら、上述の従来方式は、以下に述べるような
問題点がある。第３図（ａ）と（ｂ）を用いて説明する
。第３図（ａ＞は２つの線図形を含む入力画像であり、
第３図（ｂ）はこの線画像の各画素における方向を短線
骨で模式的に表した図である。

線画像から求めた各画素での方向には多少の誤差を含む
ので、第３図（ａ）のように直交する２線分の角点にお
いて第３図（ｂ）の区間Ｌ１のように滑らかに方向が変
化してしまう場合がある。

この区間Ｌ１は、微小な円弧に対応した第３図（ｂ）の
区間Ｌ２とほぼ同じ平均変化率を有するので、上記の従
来の線分円弧近似方式に用いられていた所定の閾値以上
の平均方向変化率を持つ区間を円弧近似する方式では、
区間Ｌ１と区間Ｌ２のいずれも円弧で近似されてしまう
、もしくはいずれもが線分で近似されてしまう。

即ち、従来の線分円弧近似方式では線形方向区間の平均
方向変化率によってのみ線分であるか円弧であるかが判
定されるので、方向の抽出結果に含まれる誤差に影響さ
れ易いという問題点があった。

本発明の目的は、上記の問題点を解決し、方向の抽出結
果の誤差に影響されに＜＜、微小な円弧や線分の角点を
正しく近似できる線画像近似方法および装置を提供する
ことにある。

（課題を解決するための手段） 前述の課題を解決するため本発明による線画像近似方法
は、線図形を走査して得られた線画像の中心線点を表す
中心線画像と、線画像の各画素における線の方向を表す
方向画像から入力線画像を線分と円弧で近似する線図形
近似方法において、中心線画像上で任意の特徴点から他
の特徴点に至る点列の位置座標を近似点列として抽出す
る近似点列抽出処理と、前記近似点列における方向画像
の方向の値を用いて、線形な平均方向変化を有する複数
の線形方向区間に近似点列を分割し、各線形方向区間の
平均方向変化率と線形性誤差を算出する線形方向区間抽
出処理と、前記線形方向区間の近似点列の線分近似によ
る位置誤差、該近似点列の円弧近似による位置誤差、線
形方向区間の方向の線形性誤差、および近似点列長に対
する線形方向区間長の割合に基づいて前記線形方向区間
が線分であるか円弧であるかを判定して近似を行う線分
円弧判定処理とを含むことを特徴とする線画像近似方法
である。

また、本発明による線画像近似装置は、紙面上に記録さ
れた線図形を走査して得られる線画像から求められる線
の中心線点および前記線画像の各位置における線の局所
的方向をそれぞれ記憶する中心線メモリおよび方向画像
メモリを少なくとも備える線画像近似装置において、前
記中心線メモリから読出される任意の特徴点から他の特
徴点に至る中心線点の位？ＩｆＪｕ標を近似点列として
出力する近似点列抽出手段と、該近似点列に対応した位
置における方向値を前記画像メモリから読出す方向系列
読出し手段と、前記方向系列上での方向値の変化を線形
近似して線形な平均方向変化を有する複数の線形方向区
間に近似点列を分割すると共に各線形方向区間の平均方
向変化率と線形性誤差を算出する線形方向区間抽出手段
と、前記線形方向区間ごとに近似点列の線分近似による
位置誤差、該近似点列の円弧近似による位置誤差、線形
方向区間の方向の線形性誤差、および近似点列長に対す
る線形方向区間長の、割合に基づいて該線形方向区間が
線分であるか円弧であるかを判定する線分円弧判定手段
とを備えて戒る線画像近似装置である。

（実施例） 次に本発明における実施例について図面を参照して説明
する。

第１図は本発明における一実施例の処理手順を示す。

処理開始に伴って、まず、線画像の中心線を求める中心
線抽出処理を行い（ステップ１０１〉、線画像の線の中
心を通る連結した画素から成る中心線画像を求める。中
心線抽出処理の手順は、細線化を行う公知の手法を用い
て実現される０例えば文献「画像認識の基礎［１］Ｊ（
森俊二・坂倉栂子共著、１９８６年）に示された細線化
の手順を用いることができる。また、線の両側の輪郭線
の中点を順に追跡する公知の手順でもよい。

次に、方向画像生成処理を行い、線画像の各画素におけ
る線の方向を求める（ステップ１０２）。

各画素における方向を求める第１の手順としては、同一
出願人により提案され、特願昭６２−２８５０４３号に
開示されている。予めＴ個の方向に対する信頼性を局所
マツチングにより求め、これを合成して各画素の方向と
その信頼性を求める手順を用いることができる。

以下では簡単のため、位置（ｘ、ｙ）における線画像の
値を、 Ｆ　（ｘ、ｙ）　、１≦Ｘ≦Ｍ、１≦ｙ≦Ｎで表す、尚
、Ｘおよびｙは線画像上での位置座標であり、右方向を
Ｘ軸、下方向をＹ軸とする０ＭおよびＮはそれぞれ線画
像の横および縦の大きさである。

パラメータＷを予期される線幅を基に定められる視野を
表す数、パラメータＴを予め設定された信頼性を求める
べき相異なる方向の数とするとき、まず、位置（ｘ、ｙ
）を中心とした縦横の幅がＷの範囲にある画像、即ち、
ＷｘＷの局所線素面像ｆ　（ｔ、５）（１≦ｔ、ｓ≦Ｗ
）に対して、局所線素画１ｆ内に所定の方向線素が中心
に存在する信頼性Ｖ　ｒ　　（ｘ　、　ｙ）　　（１＝
　１〜Ｔ　）を求める。

ここで、局所線素画像ｆ内に設定された方向線素が存在
する信頼性を求める方法としては、パターン認識技術で
用いられるマツチング手法、例えば予め設定された方向
線素のパターンの固有値展開による類似度法などの公知
の方法で実現される。

例えばＴ＝４、即ち、縦、横、右下がりの斜め、右上が
りの斜めの４つの方向線素に対する辞書を作成しておき
、局所線素画像ｆに対して各辞書との類似度を求めれば
よい。

次に、Ｔ個の方向に対する信頼性を以下の式に従って合
成する。これにより、位置（ｘ、ｙ）における線の方向
θ（ｘ、ｙ）が求められる。

Ｓｚ　（ｘ、ｙ）　＝Σ　Ｖ＋　　（ｘ、ｙ）＊Ｃ０３
（２＊＾ｒｃ＋＋）（１）Ｓｙ　　（ｘ、ｙ）　　＝Σ
　Ｖ＋　　（Ｘ、Ｖ）”５ＩＮ（２１Ａｒ１Ｊ＋　　）
　　（２）θ（Ｘ、／）　　＝ＴＡＨ−”（Ｓ、　　（
ｘ、Ｖ）／　Ｓ、　（ｘ、ｙ））／２　　（３）ここで
Ａｒｇ、は第０番目の方向線素の角度であり、例えば上
記Ｔ＝４の方向線素を選択した場合（こ　は　、　　Ａ
　　ｒ　　ｇ　　Ｉ　　＝　　Ｏ、Ａ　　ｒ　　ｇ　　
２　　　＝　　ｙｒ　　／　　２　　。

Ａｒｇ３＝ｉ／４．Ａｒｇａ　＝３ｇ／４である。

各画素における方向を求める第２の方法として、局所線
画像ｆ　（ｘ、ｙ）（１≦Ｘ＋Ｖ≦Ｗ）の慣性主軸を求
める方法を用いてもよい、即ち、以下の式で定まる方向
θを画素（ｘ、ｙ）の方向とする方法でもよい。

【眞　＝２；　　Σ　ｔ　ｘｒ（ｘ、ｙ）］／Ｅゆ　　
　　　　　　　　（５）次に、近似点列抽出処理を行い
、以下の手順［１］ないし［４］により近似すべき中心
線点の座標の系列から成る近似点列Ｓを求める（ステッ
プ１０３）、ここで、特徴点を分岐点または端点とし、
中心線点の１点ｐの８近傍に他の中心線点が１点ある点
Ｐを端点、また、中心線点の１点ｐの８近傍に他の中心
線点が３点以上存在する点ｐを分岐点とする。

［１］近似されていない中心線点が連結している任意の
特徴点を選択し、これを近似点列Ｓの始点ｐｏとする。

［２］ｐｏに連結する中心線点のうち、近似されていな
い中心線点の一つをｐＩとし、ｐＩを近似点列Ｓに加え
る。１＝１とする。

［３］　ｐＩが特徴点ならば終了する。

［４］ｐ＋に連結する中心線点のうち、近似点列Ｓに含
まれていない点をｐ　ｒ＋１　とし、これを近似点列Ｓ
に加える。１をｉ＋１に置き換え、［３］へ。

これにより、近似点列Ｓの一つが５＝（ｐｏ＋ｐｒ　、
ｐ堂・・・・・・ｐ、）として求められる。

次に、線形方向区間抽出処理を行う（ステップ１０４）
、近似点列Ｓ上での方向画像の値の系列りをＤ＝（θ０
．θ１．θｔ・・・・・・θ、）とするとき、方向系列
りから方向の変化が線形である線形方向区間、即ち方向
に変化がない区間または方向の変化が一次式で表される
区間り、（１≦ｍ≦Ｋ）を求める。更に線形方向区間り
、の始点のｌの値Ｓ、および終点のｉの値ｅ１、始点と
終点に対応する中心線点の位置座標である２つの端点座
標Ｅ、、＝　（Ｘｓ＋＋　ｙｓｔ）とＥｍ＊＝　（Ｘ　
ｓｔｌ　’ｌ　１１２→、および線形方向区間り、内の
穴内変化の平均値である平均方向変化率ＭＴ、を求める
。

平均方向変化率は単位長さ当りの方向の変化量であり、
単位はラジアン／ドツト（ｒａｄｉａｎ／ｄａｔ）とす
る、ドツトは単位長さの単位である。ここで方向の変化
を線形近似する手順には、平面上に分布する点列を直線
近似する方法を応用して実現する０例えば文献「セグメ
ンテーション・オブ・プレイン・カーブスＪ　　（”５
ｅａＩｌｅｎｔｉｏｎ　ｏｆ　Ｐｌａｎｅ　Ｃｕｒ−ｖ
ｅｓ”、Ｔ、Ｐａｖｌｉｄｉｓ　ａｎｄ　Ｓ、Ｌ、Ｈｏ
ｒｏｗｉｔｚ、ＩＥＥＥ　Ｔｒａｎｓ。

Ｖｏｌ、Ｃ−２３，Ｎｏ、８．ｐｐ、８６Ｇ−８７０［
１９７４））　ニ示された手順を用いることができる。

即ち、１およびθを２つの直交軸とする平面（１，θ）
上でのθ１の点列の配置を複数の線分で近似することに
よって、線形方向区間の範囲と平均方向変化率が求めら
れる。尚、これにより得られる線形方向区間り。

（１≦ｍ≦Ｋ）の近似直線Ｌ１の式を θ、＝　Ｍ　Ｔ　−Ｘ　ｉ＋β、　　　　　　　　（１
１）とする、また、線形方向区間り、の方向の線形性誤
差Ａ　４　ｒ　ｒ を以下の式で求める。

ＩｘｌはＸの絶対値 次に、線分円弧判定処理を行い（ステップ１０５）、Ｋ
個の線形方向区間り、の各々が線分であるか円弧である
かを判定し、線分近似または円弧近似結果を出力する。

まず、線形区間Ｄ１の２つの端点座標Ｅ１およびＥ、２
を通り、半径Ｒ１がＲ，＝１／ｌ　ＭＴ−の円の中心点
Ｏ１を求める。これを満たす円の中心点として２つの候
補点０１および０１１２が求められるが、ベクトルＯ＠
ＩＢ　＠１の偏角ベクトル０１Ｅ１の偏角の変化量の符
号が、平均方向変化率ＭＴ、の符号と一致する中心点０
１を選ぶことによって正しい中心点０．が求まる。即ち
、Ａｒ９（ｖ）をベクトルＶのＸ軸の正の向きがら右回
りを正とする方向で計測した偏角、Ｓｉｇｎ　（ｘ　）
を値Ｘの符号とするとき、 Ｓｉｇｎ　（（Ａｒｃ＋（０，ｔ　Ｅ　、ｚ）−Ａｔｃ
＋（０、ｔ　Ｅ　ｓｉｌ　））＝Ｓｉｇｎ（ＨＴ　ｍ）
　　　　　　　　　　　　　（１３）なる中心点Ｏｓ＋
が求めるべき中心点０．となる。

この中心点Ｏ１の座標を（０□、０□）とする。

次に、線形方向区間り、に対応する近似点列の位置座標
より、以下の式に従って、近似点列の線分近似誤差し、
１、および円弧近似誤差Ｃ＊　ｒ　ｒを求める。但し、
近似点列ｐ、の座標を（ｐ　＋−，ｐ　ｔｙ）とする。

＋（ｐ、、−ｐｏ、）　　（ｐ、、−ｐ、、）　　ｌ　
　）　　０−’（１４） ただし＾＝（（Ｐ、、−ＰＧ、）　２　　＋（Ｐ、、−
ＰＧ、）　”　）　０・Ｓ−Ｑ、、）　　２−１．２　
　））０・５（１５） この線分近似誤差り、１１および円弧近似誤差Ｃ６１，
を用いて、以下の条件に依って第１の線分円弧判定を行
う、ただし、Ｂは予め定められた定数である。

（１）もし１．　Ｂ　＊　Ｃｅｒｒ　＜　Ｌ　ｅｒｒを
満たすならば線形方向区間り、を円ｉまたは円であると
判定し、円弧近似を行う、即ち、中心点Ｏ１と２つの端
点Ｅ１およびＥａｔをそれぞれ結ぶ方向θ、Ｉおよびθ
、２を円弧の開始角および終了角として求め、中心点０
１、半径Ｒ、、開始角θ１、終了角θ、２を円弧近似結
果として出力する。

（２）もし、＋　Ｂ　”　Ｌ　ｅｒｒ　＜　Ｃｅｒｒを
満たすならば線形方向区間り、を線分であると判定し、
線分近似を行う、即ち、２つの端点座標Ｅ　ａｔおよび
Ｅａｔを線分近似結果として出力する。

これにより、条件（１）または（２）を満たすときは線
分円弧判定が行われ、近似結果が求められる。

条件（１）および（２）のいずれも満たさないときは、
以下の条件によって第２の線分円弧判定を行う。

（３）　Ｒ−１−／　Ｐ　−＜Ｒ−＜Ｆｔ−−−＊　Ｐ
−且つＤＴ、、、／Ｐ、＜ＤＴ、を満たすならば線形方
向区間り、を円弧または円であると判定し、円弧近似を
行う、即ち、中心点Ｏ１と２つの端点Ｅ１およびＥｓｓ
をそれぞれ結ぶ方向θ、Ｉおよび０．１を円弧の開始角
および終了角として求め、中心点０１、半径Ｒ、、開始
角θ、Ｉ、終了角θｎを円弧近似結果として出力する。

ここで、Ｒｍ　ｌ　ｍ、Ｒｗａｘ　、ＤＴｍｔｓは予め
定められた定数であり、方向変化量ＤＴ、および信頼性
Ｐ。

は以下の式で定まる値である。

口Ｔ、　＝ＨＴ　、　Ｉｎ　、　　　　　　　　　　（
１６）Ｐ、＝（φ、　（Ａ、、、　）−φ２　（ｎｓ　
＋　ｎ））　’°５（１７） ここでφ１　（ｘ）はＸに関して単調減少な関数であり
、例えば、 φｌ　（ｘ）＝１／　（ｘ＋１　）”’　　（１８）を
選ぶことができる。また、φｘ　　（ｘ、ｙ）はＸに関
して単調増加、ｙに関して単調減少な関数であ、す、例
えば、 φｔ（ｘ、ｙ）＝（ｘ／ｙ）”’　　（１９）を選ぶこ
とができる。

（４）それ以外ならば、線形方向区間り、を線分である
と判定し、線分近似を行う、即ち、２つの端点座標Ｅ１
およびＥａｔを線分近似・結果として出力する。

以上により、一つの近似点列Ｓについて線分円弧近似が
行われる。中心線画像にまだ近似されていない中心線点
が存在する場合は近似点列抽出処理から以降を繰り返し
て他の近似点列に対して同様の処理を行う、存在しない
場合は全ての処理を終了する。これにより全線画像が線
分円弧近似される。

尚、第１図および上記の説明においては中心線抽出処理
の次に方向画像生成処理を行っているが、上記の説明か
ら明らかなようにこの２つの処理は独立に行えるので、
順序を逆に行ってもよいし、同時に行ってもよい。

第２図は本発明における線画像近似装置の機能ブロック
図である。

画像入力装置１は、図形を走査して線画像を入力し記憶
する。中心線抽出装置２は画像入力装置１内の線画像か
ら線の中心点を求める中心線メモリ３は、該中心線点お
よび近似済みの点を記憶する。方向画像生成装置４は、
画像入力装置１内の線画像から各画素における局所的な
方向を求めて方向画像を生成する。方向画像メモリ５は
、該方向画像を記憶する。近似点列抽出装置６は該中心
線メモリ３から中心線点を読出して近似すべき中心線点
の系列を求める。方向系列読出し装置７は、該近似点列
に対応した位置における方向値の系列からなる方向系列
を方向画像メモリ５から読出す。

線形方向区間抽出装置８は、方向系列上での方向値の変
化を線形近似して線形な平均方向変化率を有する線形方
向区間に近似点列を分割すると共に各線形方向区間の平
均方向変化率と線形性誤差を算出する。形状数値化９は
、線形方向区間ごとに円弧または円の半径と中心点座標
を算出する。線分円弧判定装置１０は、線形方向区間の
近似点列の線分近似による位置座標、該近似点列の円弧
近似による位置座標、線形方向区間の方向の線形性誤差
、および近似点列置に対する線形方向区間長の割合に基
づいて該線形方向区間が線分であるか円弧であるかを判
定して近似を行う、制御装置１１は、画像入力装置工な
いし線分円弧判定装置１０を起動し一連の処理の実行を
制御する。以下より具体的に動作を説明する。

制御装置１１はまず画像入力装置１を起動して、画像を
入力し数値化した線画像として記憶させる。

線画像を以下では簡単のため、位置座標（ｘ、ｙ）にお
ける線画像の値を、 Ｆ（ｘ、ｙ）、１≦Ｘ≦Ｍ、１≦ｙ≦Ｎで表す、尚、Ｘ
およびｙは線画像上での位置座標であり、右・方向をＸ
軸、下方向をＹ軸とする０ＭおよびＮはそれぞれ線画像
の横および縦の大きさである０画像入力装置１は、光学
的スキャナもしくは撮像管を用いた撮像装置とそれから
得られる信号を数値に変換する変換器、およびその数値
を記憶するＲＡＭやディスク型ファイル装置などの書換
え可能な記憶装置によって容易に構成される。

画像入力装置１内に線画像が記憶されると、制御装置１
１は中心線抽出装置２を起動し、入力線画像の線の中心
を通る連結した中心線点を求める。

中心線抽出装置２は、細線化を行う公知の手法を用いて
実現される０例えば文献「画像認識の基礎［１］Ｊ　　
（森俊二・坂倉栂子共著、１９８６年）に示された細線
化の手順をマイクロコンピュータに代表される電子計算
機のプログラムで実現し、これを画像入力装置１内に記
憶された入力画像に対して実行することにより容易に実
現できる。

中心線抽出装置２は求めた中心線点を中心線メモリ３に
格納する。中心線メモリ３は中心線点である画素と中心
線点でない画素を区別でき、また、後述する近似済みの
点と近似済みでない点を区別できる形式で記憶する装置
であり、ＲＡＭやディスク型ファイル装置などの書換え
可能な記憶装置によって容易に構成される９例えば中心
線メモリ３は中心線点である画素を１、中心線点でない
画素を０で表した中心線画像と、近似済みの点を１、未
近似の点をＯで表した近似済み画像の２枚の２値画像を
記憶する形態で実現される。また、例えば、中心線点で
あるが近似されていない点を０、中心線点でなく近似さ
れていない点を１、中心線点であり近似済みの点を３で
表すように組合せを多値で表した形式で記憶する形態で
もよい、尚、中心線抽出装置２が電子計算機のプログラ
ムと記憶装置によって構成される場合には、中心線メモ
リ３を同一の電子計算機のメモリ内に設けることもでき
る。

次に、制御装置１１は方向画像生成装置４を起動する。

方向画像生成装置４は、線画像Ｆ（ｘ、ｙ）の各点（ｘ
、ｙ）について、点（ｘ、ｙ）を中心とした所定の局所
範囲にある局所線画ｔａｆ（ｔ。

ｓ）、例えば局所範囲を横縦の幅がＷの矩形とする場合
には、 ｆ（ｔ、５）＝Ｆ（ｘ＋ｔ−１−Ｗ／２．ｙ＋５−１−
Ｗ／２）、１≦ｔ、ｓ≦ｎを線画像入力装置１から読出
し、局所線画像ｆ　（ｔ、ｓ）の方向θ（ｘ、ｙ）を求
める。線画像Ｆの全ての点についてこれを行い、方向画
像θ（ｘ、ｙ）（１≦Ｘ≦Ｍ、１≦ｙ≦Ｎ）を生成する
。尚、方向画像生成装置４を実現するには、第１の発明
の式（１）ないし式（３〉に示した方法または（４）な
いし式（１０）に示した方法をマイクロコンピュータに
代表される電子計算機上のプログラムによって実現し、
画像入力装置１に記憶された線画像に対して処理するこ
とによって容易に実現されうる。方向画像メモリＷｔ４
は求めた方向画像θ（ｘ、ｙ）を方向画像メモリ５に格
納する。

方向画像メモリ５は、ＲＡＭやディスク型ファイル装置
などの書換え可能な記憶装置によって容易に構成されて
もよいし、方向画像生成装置４が電子計算機のプログラ
ムと記憶装置によって構成される場合には方向画像メモ
リ５を同一の電子計算機の記憶装置内に設けてもよい。

次に制御装置１１は、近似区間抽出装置６を起動し、近
似区間抽出装置６は以下の動作を行い、近似すべき中心
線点の座標の系列から戒る近似点列Ｓを求める。尚、上
記の中心線メモリ３には中心線点である画素を１、中心
線点でない画素をＯで表した中心線画像ｇ　（ｘ、ｙ）
と、近似済みの点を１、未近似の点をＯで表した近似済
み画像ｈ　（ｘ、ｙ）の２枚の２値画像を記憶する形態
で実現されており、処理の開始に伴って近似済み画＠ｈ
　（ｘ、ｙ）は全てＯに初期化されている場合について
説明する。

［１１ａ＝１．ｂ＝１として、［３］の動作を行う。

［２］ａ＜Ｍならばａをａ＋１に置き換える。

方ａ＝Ｍならばａを１に、ｂをｂ＋１に置き換える。こ
こでａ＝Ｍ、ｂ＝Ｎになったら制御装置１１に終了信号
を送る。そうでないならば［３］の動作を行う。

［３］中心線メモリ３からｇ（ａ、ｂ’）を読出し、ｇ
　（ａ、ｂ）＝１ならば［４］の動作を行う、そうでな
ければ［２］の動作を行う。

〔４］中心線メモリ３からｇ　（ａ−１，ｂ−１）。

ｇ（ａ、ｂ−１）、ｇ（ａ＋１．ｂ−１）。

ｇ　（ａ−１＋　ｂ）＋　ｇ　（ａ＋１．ｂ）。

ｇ　（ａ　　１．ｂ＋１）＋　ｇ　（ａ、ｂ十ｔ）。

ｇ　（ａ＋１．ｂ＋１）の８つの値を読出し、これらの
値のうち１つ又は３つが１ならば次に［５］の動作を行
う、そうでなければ［２］の動作を行う。

［５］　（ｃ、　ｄ）を（ａ−１，ｂｌ）（ａ　、ｂ　
　１　）　＋　　（ａ　＋　１　＊　ｂ　　１　）　＊
（ａ−１，ｂ）、（ａ＋１．ｂ） （ａ−１，ｂ＋１）、（ａ、ｂ＋１）。

（ａ＋１．ｂ＋１）のいずれかとするとき、中心線メモ
リ３からｈ　（ｃ、ｄ）を読出してｈ　（ｃ、ｄ）＝０
であるような（ｃ、ｄ）を求める。このような（ｃ、ｄ
）が存在しないならば［２］の動作を行う、存在するな
らば（ａ、ｂ）を方向系列読出し装置７と線形方向区間
抽出装置８へ出力すると共に、（ａ、ｂ）を（ｐｘ、ｐ
ｙ）に記憶して［６］の動作を行う。

［６］　　（ｃ、ｄ）を方向系列読出し装置７と線形方
向区間抽出装置８へ出力する０次に中心線メモリ３から
ｇ　（ｃ−１，ｄ　　１）　。

ｇ　（ｃ、ｄ−１）、ｇ　（ｃ＋１．ｄ−１）。

ｇ　（ｃ−１，ｄ）、ｇ　（ｃ＋１．ｄ）ｇ　（Ｃ−１
，ｄ＋１）、ｇ　（Ｃ，ｄ＋１）。

ｇ　（ｃ＋１．ｄ＋１）の８つの値を読出し、これらの
値のうち１つ又は３つが１ならば終了するそうでなけれ
ばｈ　（ｃ、ｄ）を１に書き換え、［７］の動作を行う
。

［７］　（ｅ、　ｆ）を（ｃ　　１．ｄ　　１）　＋　
（ｃ。

ｄ　　１　）　、（ｃ　＋１　＋　ｄ　　１　）　、（
ｃ　　１　。

ｄ）、（ｃ＋１．ｄ）、（ｃ−ｉ、ｄ＋１）（Ｃ，ｄ＋
１）、（ｃ＋１．ｄ＋１）のいずれかとするとき、中心
線メモリ３からｇ（ｅ、ｆ）をみ出してｇ（ｅ、ｆ）＝
１且つ（ｅ、ｆ）≠（ｐｘ、ｐｙ）であるような（ｅ、
ｆ）求める。（ｃ、ｄ）を新たな（ｐｘ、ｐｙ）に置き
換え、（ｅ、ｆ）を新たな（ｃ、ｄ）に置き換えて［６
］の動作を行う。

以上により、一つの特徴点間の近似点列が抽出され、方
向系列読出し装置７と線形方向区間抽出装置８へ出力さ
れる。

近似区間抽出装置６が近似点列を出力すると、方向系列
読出し装置７は近似点列の各々に対応した位置にある方
向画像の値を方向画像メモリ５から順次読出し、方向系
列として線形方向区間抽出装置８へ出力する。即ち、近
似区間抽出装置６が出力した近似区間Ｓが、 ５＝（（ｘ＋　、ｙ＋　）、（Ｘ２　、Ｙ２　）、−−
−−−−（ｘｍ　、ｙ、　））であるとき、方向系列読
出し装置７は、方向系列りとして、 ０＝（θ（Ｘ＋　＋Ｖ＋　）、θ（Ｘ２１Ｖ２　）ｓ”
θ（ｘ、　＋ｙｍ　））＝（θ１，１≦ｉ≦ｎ） を方向画像メモリ５から読出して線形方向区間抽出装置
８へ出力する。

次に制御装置１１は線形方向区間抽出装置８を起動し、
近似区間Ｓにおける方向系列りから、方向値の変化が線
形である線形区間、即ち、方向に変化がない区間または
方向の変化が一次式で表される区間り、（１≦ｍ≦Ｋ〉
を求める。更に線形方向区間Ｄヨの始点ｌの値ｓａおよ
び終点の１の値ｅ、、、始点と終点に対応する中心線点
の位置座標である２つの端点座標Ｅ　ａ＋＝　（ｘ　ｍ
ｌ　、　ｙ　＋ｍｔ　）とＥ　ａ２＝（Ｘ　ｍ２＋　３
’　１１２）　、線形方向区間り、内内方向変化の平均
値である平均方向変化率ＭＴ、、式（１２）で定まる線
形性誤差Ａ、２．を求める。平均方向変化率は単位長さ
当りの方向の変化量であり、単位はラジアン／ドツト　
（ｒａｄｉａｎ／ｄｏｔ）　トする。また、ドツトは単
位長さの単位である。

線形方向区間抽出装置８において方向変化を線形近似す
るには、第１図に示す実施例に於て線形方向区間抽出処
理で説明した手順をマイクロコンピュータに代表される
電子計算機のプログラムで実現し、これを電子計算機内
のメモリまたは外部記憶装置に読込まれた近似区間の中
心線点の位置座標列と方向列に対して・実行することに
より容易に実現できる。

線形方向区間抽出装置８は、Ｋ個の線形方向区間り、の
各々について、求めた平均方向変化率ＭＴ、　、２つの
端点座標Ｅ　ｓｌｌ　Ｅｍ２を形状数値化装置９へ出力
し、更に、線形方向区間り、に対応した部分近似点列の
座標Ｓ、と平均方向変化率ＭＴ、、線形性誤差Ａ、１１
．２つの端点Ｍ　ＩＩ　Ｅ　１゜Ｅａｔおよび線形方向
区間抽出装置８に入力された近似点列の点数ｎを線分円
弧判定装置１０に出力する。

形状数値化装置９は線形方向区間抽出装置８から入力さ
れる２つの端点座標Ｅ１およびＥｌと平均方向変化ＭＴ
、から円または円弧の半径と中心点の位置を求める。

まず、半径Ｒ，をＲ１がＲ，＝１／ＩＭＴ。

に従って求め、次に２つの端点座標Ｅ１およびＥｆｆｉ
２を通り、半径Ｒ１の円の中心点Ｏ１を求める。

これを満たす円の中心点として２つの候補点Ｏ，Ｉおよ
び０．２が求められるが、ベクトルＯｅｒ　ｌ　Ｅ　ｗ
ｒ　１の偏角とベクトルＯｓ＋Ｅ＋ａ＊の偏角の変化量
の符号が、平均方向変化率ＭＴ、の符号と一致する中心
点Ｏｍｌを選ぶことによって正しい中心点Ｏ１が求まる
。即ち、Ａｒｇ（Ｖ）をベクトルマのＸ軸の正の向きか
ら右回りを正とする方向で計測した偏角、Ｓｉｇｎ（ｘ
）を値Ｘの符号とするとき、式（１３）を満たす中心点
０１が求めるべき中心点Ｏ１となる。

形状数値化装置９は求めた半径Ｒ１と中心点０、の座標
（０，、、Ｏ，、）を線分円弧判定装置１０に出力する
。尚、形状数値化装置９はマイクロコンピュータに代表
される電子計算機のプログラムで実現し、線形方向区間
抽出装置８から入力される値に対して上記の処理を実行
することにより容易に実現できる。

線分円弧判定装置１０は、線形方向区間抽出装置８から
入力される部分近似点列の座標Ｓ、と平均方向変化率Ｍ
Ｔ、　、線形性誤差Ａ　ｅｒｒ　％　２つの端点座標Ｅ
　＠１１　Ｅｓ２近似点列の点数ｎ、および形状数値化
装置から入力される半径Ｒ１と中心点座標Ｏ１から各線
形方向区間り、が線分であるか円弧であるかを判定する
。

まず、部分近似点列Ｓ、の位置座標と半径Ｒ。

より、式（１４）および式（１５）に従って近似点列の
線分近似誤差Ｌ　１１　ｒ　ｒおよび円弧近似誤差Ｃｅ
　ｒ　ｒを求める。

次にこの線分近似誤差Ｌ　＠　ｒ　Ｆおよび円弧近似誤
差Ｃｅｒｒを用いて、第１図に示す実施例で説明した条
件（１）および〈２）に従って第１の線分円弧判定を行
う。

これにより円弧であると判定された場合には、中心点Ｏ
ａと２つの端点Ｅ　ｍｌ　＋　Ｅ　ｓ＋２をそれぞれ結
ぶ方向θ１およびθ、２を円弧の開始角および終了角と
して求め、中心点０１、半径Ｒ１、開始角θ１、終了角
θ０を円弧近似結果として出力する。

一方、線分であると判定された場合には２つの端点座標
Ｅ　ｗａ　ｌおよびＢａｔを線分近似結果として出力す
る。

第１の線分円弧判定でいづれにも判定できなかったとき
は、線形性誤差Ａ１１１、平均方向変化率ＭＴ、、近似
点列の点数ｎおよび部分近似点列の点数ｎ、を用いて、
第１図の実施例で説明した条件（３）および（４）に従
って第２の線分円弧判定を行う、これにより円弧である
と判定された場合には中心点Ｏｍと２つの端点Ｅ　ａ　
ｌおよびＥｆｆｉ２をそれぞれ結ぶ方向θ、Ｉおよびθ
、２を円弧の開始角および終了角として求め、中心点０
１、半径Ｒ１、開始角θ、Ｉ、終了θｎを円弧近似結果
として出力する。一方、線分であると判定された場合に
は２つの端点座標Ｅ１およびＥ、を線分近似結果として
出力する。

制御装置１１は、線形方向区間抽出装置８が抽出したに
個の線形方向区間について近似結果が線分円弧判定装置
１０から出力されると、再び近似区間抽出装置６を起動
して、他の近似区間を抽出する。このとき、近似区間抽
出装置６から終了信号が制御装置１１に送られると、１
１は全ての処理を終了する。これにより画像入力装置１
に記憶された全線画像が線分円弧近似される。

（発明の効果〉 線画像上の平均方向変化率のみを用いて線分であるか円
弧であるかを判定する従来の方法では求めた方向の誤差
に影響され易い問題点があったのに対し、本発明におい
ては各近似区間の判定は平均方向変化率だけでなく、近
似結果と実際の中心線点との位置誤差も含めて判定して
いるため、微小な円弧や線分の角点などの方向が急激に
変化する点においても正しく判定することができる。

また、入力された線画像の方向を線形近似することによ
って中心線を分割しているため、線分の部分と円弧の部
分を精度良く分離するという効果は損なわれない、従っ
て本発明は線分や円弧および円を含む線画像を、分岐点
や角点などの特徴点においても、あるいは曲率の大きな
円弧部分においても正しく近似することができる。

【図面の簡単な説明】

第１図は本発明の一実施例による線画像近似方法の手順
を表す図、第２図は本発明の他の実施例による線画像近
似装置の機能を表すブロック図、第３図は従来の手法に
よる動作を示す図である。 １・・・画像入力装置、２・・・中心線抽出装置、３・
・・中心線メモリ、４・・・方向画像生成装置、５・・
・方向画像メモ・す、６・・・近似点列抽出装置、７・
・・方向系列読出し装置、８・・・線形方向区間抽出装
置、９・・・形状数値化装置、１０・・・線分円弧判定
装置、１１・・・制御装置。

Claims (2)

【特許請求の範囲】
1. （１）線図形を走査して得られた線画像の中心線点を表
   す中心線画像と、線画像の各画素における線の方向を表
   す方向画像から入力線画像を線分と円弧で近似する線図
   形近似方法に於いて、 中心線画像上で任意の特徴点から他の特徴点に至る点列
   の位置座標を近似点列として抽出する近似点列抽出処理
   と、 前記近似点列における方向画像の方向の値を用いて、線
   形な平均方向変化を有する複数の線形方向区間に近似点
   列を分割し、各線形方向区間の平均方向変化率と線形性
   誤差を算出する線形方向区間抽出処理と、 前記線形方向区間の近似点列の線分近似による位置誤差
   、該近似点列の円弧近似による位置誤差、線形方向区間
   の方向の線形性誤差、および近似点列長に対する線形方
   向区間長の割合に基づいて前記線形方向区間が線分であ
   るか円弧であるかを判定して近似を行う線分円弧判定処
   理とを含むことを特徴とする線画像近似方法。
2. （２）紙面上に記録された線図形を走査して得られる線
   画像から求められる線の中心線点および前記線画像の各
   位置における線の局所的方向をそれぞれ記憶する中心線
   メモリおよび方向画像メモリを少なくとも備える線画像
   近似装置において、前記中心線メモリから読出される任
   意の特徴点から他の特徴点に至る中心線点の位置座標を
   近似点列として出力する近似点列抽出手段と、該近似点
   列に対応した位置における方向値を前記画像メモリから
   読出す方向系列読出し手段と、前記方向系列上での方向
   値の変化を線形近似して線形な平均方向変化を有する複
   数の線形方向区間に近似点列を分割すると共に各線形方
   向区間の平均方向変化率と線形性誤差を算出する線形方
   向区間抽出手段と、前記線形方向区間ごとに近似点列の
   線分近似による位置誤差、該近似点列の円弧近似による
   位置誤差、線形方向区間の方向の線形性誤差、および近
   似点列長に対する線形方向区間長の割合に基づいて該線
   形方向区間が線分であるか円弧であるかを判定する線分
   円弧判定手段とを備えて成る線画像近似装置。