JPH03154177A - 線図形の曲線近似方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） この発明は、線図形の少なくとも一部を曲線で近似する
方法に関する。

（従来の技術） 機械や電気回路の設計図のような図面をコンビニー夕で
処理できるようにするために、図面を読み込んでその図
形データを作成する図面自動入力装置が利用されている
。図面自動入力装置は、図面をスキャナで読み込むこと
によって、図面上に描かれている線図形の図形データを
作成し、さらに、様々な処理を行うことにより、コンピ
ュータで取扱い易い形式の図形データを作成している。

図面自動入力装置で行われる処理には、例えば線図形の
中心線のみを抽出する細線化処理（または芯線化処理）
、中心線で表わされた線図形の乱れを修正する形状修正
処理、および線図形の曲線部分を円弧やスプライン関数
などで近似する曲線近似処理などがある。

（発明が解決しようとする課題） しかし、上述の形状修正処理を曲線近似処理の前に行う
と、曲線として近似すべき部分が線図形の乱れであると
誤って認識され、誤った修正が行われてしまう場合があ
る。第７Ａ図と第７Ｂ図は、形状修正処理によって線図
形が誤って修正されてしまう場合を示す説明図である。

第７Ａ図の（ａ）は、線・図形から抽出された中心線が
、点Ｑｌｌ’＝　Ｑ１４を結ぶ線分で近似されている状
態を示しており、この線に形状修正処理と曲線近似処理
が順次行われる。点Ｑ１□とＱ１３との間は、本来第７
Ａ図の（ｂ）に示すように円弧で近似するのが望ましい
。しかし、形状修正処理を曲線近似処理の前に行うと、
第７Ａ図（ａ）の点Ｑ１□〜Ｑ１３の間の数個の点の集
合が、図形の歪みとして誤って認識されてしまい、第７
Ａ図（ｃ）に示されるように、２つの点Ｑ　　とＱ　　
とに置換えられて１２ａ　　　１３ａ しまう場合がある。この結果、点Ｑ　　とＱ１２ａ　　
　１３ａ との間は線分で近似され、曲線部分が無いものとされて
しまうという不都合が生じる。

第７Ｂ図の（ａ）は、円弧状の線図形から抽出された中
心線が、点Ｑ２１とＱ２□の間の数個の点を結ぶ線分で
近似されている状態を示している。また、点Ｑ２３から
円弧状に並んだ数個の点の方向に伸びる線分が描かれて
いるが、この線分は本来不要なものである。従って、形
状修正処理では点Ｑ２３が取除かれ、その後の曲線近似
処理によって、第７Ｂ図の（ｂ）に示すように、線図形
が曲線で近似されることが望ましい。しかし、形状修正
処理の結果、第７Ｂ図の（ｃ）に示すように、点Ｑ２３
とその周囲の数個の点が点Ｑ２４とＱ２５とで置換えら
れてしまうことがある。この結果、点Ｑ２□とＱ２４の
間、および点Ｑ２５とＱ２□の間は円弧で近似されるが
、点Ｑ２４とＱ２５の間は直線で近似されてしまうとい
う不都合が生じる。

一方、上述とは逆に曲線近似処理を形状修正処理の前に
行うとすると、直線で近似された部分を表わすデータと
、曲線で近似された部分を表わすデータの形式が異なる
ために、その後の形状修正処理などにおけるデータの取
扱いが繁雑になるという問題がある。

（発明の目的） この発明は、従来技術における上述の課題を解決するた
めになされたものであり、形状修正処理と曲線近似処理
との双方を容易にかつ適切に行うことのできる線図形の
曲線近似方法を提供することを目的とする。

（課題を解決するための手段） 上述の課題を解決するため、この発明では、連続した複
数の線分で表わされた線図形の少なくとも一部を曲線で
近似する線図形の曲線近似方法において、（ａ）　　前
記複数の線分のうち、所定の曲線判定条件を満足するも
のを曲線候補線分として特定し、（ｂ）　　前記複数の
線分のうち、前記曲線候補線分を除く線分について、前
記線図形の形状の乱れを修正する形状修正処理を施した
後、（ｃ）前記曲線候補線分を所定の曲線で近似する。

（作用） 形状修正処理を曲線候補線分を除く線分について行うの
で、曲線として近似されるべき曲線候補線分が形状修正
処理によって誤って修正されることがない。

（実施例） Ａ、装置の概略構成 第１図は、この発明の一実施例を適用する図面自動入力
装置を示すブロック図である。この図面自動人力装置は
、制御部１．第１前処理部２．ベクトル化部３．第２前
処理部４．認識処理部５゜メモリ６、および２つのイン
ターフェース７．８を備えており、これらの各部はデー
タバス２０を介して互いに接続されている。また、イン
ターフェース７．８にはそれぞれディスク９とスキャナ
１０とが接続されている。

なお、ベクトル化部３は曲線候補抽出部３１を含んでお
り、また、第２前処理部４は形状修正部４１と曲線近似
部４２と含んでいる。

Ｂ、実施例の処理手順 第２図は、実施例の処理手順を示すフローチャートであ
る。また、第３図は、この手順による線図形の処理の経
過を示す概念図である。

ステップＳ１では、線図形を含む原画（図面）を準備す
る。第３図の（ａ）に、線図形Ａを例示している。

ステップＳ２では、この原画をスキャナ１０で読み、得
られた画像データをメモリ６に保存する。

この画像データは、例えば線図形の白黒画像を画素ごと
の２値データで表現したものである。

ステップＳ３では、この画像データに基づいて第１前処
理部２がノイズ除去等を目的とした第１の前処理を実施
する。

ステップＳ４では、第１の前処理を受けた画像データに
基づいて、ベクトル化部３が線図形Ａの中心線を表わす
ベクトルデータを求める。第３図（ｂ）にベクトルデー
タによって表わされた中心線ＣＬを示す。中心線ＣＬは
１、点ｐ　　−ｐ１２を順■ 次結ぶベクトル列で表わされる。第４Ａ図は、１つのベ
クトルＶを表わすベクトルデータの構造を示す図である
。開始点Ｐ１と終了点Ｐ。との間を結ぶベクトルＶのベ
クトルデータＤ　は、データの種類（ベクトルデータか
曲線データか等）を表わす種別データｄ　、開始点Ｐ１
の座標値（ｘ　ｉ。

ｙ　）および終了点Ｐ　の座標値（ｘ、ｙ）１　　　　
　　　　　ｅ　　　　　　　ｅ　　　ｅを示すデータを
含んでいる。なお、ベクトルデータＤ　の構造としては
、開始点Ｐ、とベクトルＶＶ　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　１の
方向とベクトルＶの長さとを示すデータを含んだもので
もよい。第４Ｂ図は、複数のベクトルｖ　−ｖ３が連結
しているときのベクトルデータ■ ＤＶの構造を示す図である。図に示すように、連結した
ベクトルを表わすベクトルデータＤＶは、各ベクトルｖ
　−ｖ３のベクトルデータＤ　〜１　　　　　　　　　
　　　　　　　　　　　　　　　ｖｌＤｖ３が連結の順
に従って配列された構造を有している。

線図形Ａの中心線ＣＬを求めるのは、線図形Ａの形状を
少量のデータで表現でき、データ処理に便利だからであ
る。中心線ＣＬのベクトルデータを求めるには、例えば
、まず前記の２値画像データに基づいて線図形Ａの輪郭
線（黒領域と白領域との境界線）を、多数のベクトルを
連結した閉ベクトルで表現する。その後、この閉ベクト
ルに基づいて、いわゆる芯線化を行うことによって、中
心線ＣＬのベクトルデータを求めることができる。

また、他の例として、前記２値画像データに基づいて線
図形Ａを細線化することにより、１画素の幅の中心線Ｃ
Ｌを求め、この中心線ＣＬを表現するベクトルデータを
求めることもできる。

ステップＳ５では、ベクトル化部３内の曲線候補抽出部
３１が、曲線近似をすべき部分のベクトル列を抽出する
。曲線候補の抽出は、例えば次のような判定基準に基づ
いて行われる： まず、連続したベクトル列Ｖ、（ｉ−１，２゜・・・、
ｎ）の隣り合うベクトルＶ　−、Ｖ　ｊ＋１（ｊ−１，
２，・・・、’ｎ−１）が次の２つの条件を満たすかど
うかを順次調べる。

ＩＶ、　　　　ＩＶｊ＋１ −　　ｃｏｓ／Ｖ、Ｖ、　　　＞θ１−（２）Ｊ　　　
　ｊ＋１ 式（１）は、２つのベクトルｖ、、ｖｊ＋１の長さの比
が一定範囲内（ｒ　〜ｒ２）にある場合にの■ み、この２つのベクトルｖ、、ｖｊ＋１を曲線候補とす
ることを示している。従って、２つのベクトルＶ、、Ｖ
ｊ＋１のうちの一方が長いとき（これは直線部であると
考えられる。）には、曲線候補とならない。

一方、式（２）は２つのベクトルｖ、、ｖｊ＋１のなす
角度Ｚｖ、ｖ　　　の余弦が一定値θ１より大Ｊ　　　
　ｊ＋１ きい場合にのみ、２つのベクトルＶ、Ｖ、　　をｊ　　
　Ｊ＋１ 曲線候補とすることを示している。すなわち、２つのベ
クトルのなす角度Ｚｖ　ｖ　　が一定の角ｊ　　ｊ＋１ 度未満になっている場合にのみ曲線候補として抽出され
、角度Ｚｖ　Ｖ　　が大きなときには曲線Ｊ　　ｊ＋１ 候補とされない。

さらに、上記の（１）、（２）式を両方とも満足するベ
クトル列ｖ１の個数Ｎが所定の数ｍ１以上であることを
第３の条件とする。

ｍｌ　　　≦　Ｎ　　　　　　　　　　　　・・・（３
）これは、曲線候補のベクトル列Ｖｔの個数Ｎがｍｌよ
り小さい場合は真の曲線部でなく、線図形の歪みの部分
である可能性が高いからである。

（１，）〜（３）式で用いられる定数は半経験的に定め
られるが、例えばｒｌ−０，９，「２−１．■。

θ、　−０，９０８３１（角度２５°に相当）、ｍｌ−
３などが適当である。

第３図（ｃ）は、このようにして曲線候補として抽出さ
れたベクトル列の部分を破線で示した図である。第３図
（ｂ）と比較すればわかるように、点Ｐ２〜Ｐ９の間を
順次連結するベクトル列が曲線候補として抽出されてい
る。なお、曲線候補とされたベクトルについては、ベク
トルデータＤ　内の種別データｄ、（第４Ａ図参照）を
、曲線候補のベクトルであることを示す値に変更する。

このように種別データｄｋを変更して曲線候補のベクト
ルデータを他のベクトルデータと区別するようにすれば
、ベクトルデータの構造を変えることなく曲線候補を特
定できるという利点がある。さらに、曲線候補とそれ以
外のベクトルデータの構造がすべて同じなので、ベクト
ル化部３やその後の処理を行う第２前処理部４などの構
成を簡単にできるという利点もある。

ステップＳ６では、曲線候補が抽出されたベクトルデー
タに基づいて、第２前処理部４内の形状修正部４１によ
り、図形の形状修正処理が行われる。図形の形状修正処
理としては次に示す「整形処理」や「かすれ補正処理」
などがある。

整形処理とは、線図形の交差点や角の部分に歪みがある
場合に、これを自動的に修正する処理を言う。第５Ａ図
と第５Ｂ図は、整形処理によって線図形の歪みが除去さ
れる場合を示す概念図である。第５Ａ図の例では、線図
形Ｆ１において接近する３つの点ｐｐ、ｐ　　が、修正
後の線図ａｌ°ｂｌ　　　ｃｌ 形Ｆ　では１つの分岐点Ｐｄ１に置換えられている。

修正後の線図形Ｆ　は、点Ｐｄ工て２つの直線が直交す
る図形となっている。

第５Ｂ図の例では、線図形Ｆ３の２つの分岐点Ｐａ２”
　ｂ２が、修正後の線図形Ｆ３では１つの分岐点Ｐａ２
にまとめられている。修正後の線図形Ｆ　は、分岐点Ｐ
ａ２から線が放射状に伸びた形状となっている。なお、
線図形Ｆ３において点Ｐ。２が直線Ｐ　　Ｐ　上にあっ
たため、点Ｐｃ２も省略ａ２’　　　　ｄ２ されている。

形状修正処理としては、上記のような分岐点（又は交差
点）の歪みの修正処理のほかに、屈曲点（直線が折れ曲
がっている部分）の歪みの修正処理や、ヒゲ歪（第７Ｂ
図のように突出している部分）の修正処理などがある。

形状修正処理の詳細については、例えば特公昭６３−３
１８２２号公報や特開昭６３−１０３３８４号公報に開
示されている。

かすれ補正処理は、原画としての図面に薄い部分やかす
れている部分があるために、その部分の図形がスキャナ
による読み取りやベクトル化の処理の結果として切れて
しまう場合に、これを自動的に補正する処理である。第
５Ｃ図はかすれ補正処理によって線図形のかすれが補充
される場合を示す概念図である。この例では、線図形Ｆ
５において本来１つの分岐点にあるべき３つの点Ｐａ３
’Ｐ　、Ｐ　が互いに離れた位置にあり、かつ切りｂｌ
　　　ｃ８ 離されている。かすれ補正処理を行うと、３つの点ｐｐ
、ｐ　　が処理後の線図形Ｆ６においａ３’　　　　ｂ
３　　　　　ｃ３ て１つの分岐点Ｐａ３に置換えられている。なお、かす
れ補正処理の詳細については、例えば特公昭６３−１３
１７８号公報（ここでは「っなぎ処理」と呼ばれている
。）などに開示されている。

なお、ステップＳ６では形状修正処理のほかに、要素分
類処理や特徴点抽出処理を行ってもよい。

二二で、要素分類処理とは、ベクトルデータで表わされ
る図形を、文字要素や図形要素などに分類する処理をい
う。また、特徴点抽出処理とはベクトルデータで表わさ
れる図形の点の中から、端点（連続した一本の線の開始
点または終了点）、屈曲点、交点などの特徴点を抽出す
る処理をいう。

ステップＳ６における形状修正処理では、曲線候補とし
て抽出されていたベクトル列が処理の対象から除外され
る。第３図（ｄ）に、形状修正処理を受けた後の中心線
ＣＬ　　を示す。第３図（ｃ）の点Ｐ　　Ｐ　は、形状
修正処理の結果として１つｌＯｏ　　　ｔｉ の屈曲点Ｐ　　に置換えられている。また、点０ａ Ｐ２とＰ９との間のベクトル列は曲線候補としてそのま
ま保存されているので、破線で描かれている。

ステップＳ７では、第２前処理部４内の曲線近似部４２
が、曲線候補となっているベクトル列部分の曲線近似処
理を行う。第３図（ｅ）は、点Ｐ２とＰ９との間のベク
トル列が円弧で近似された状態を示す図である。曲線が
円弧で近似された場合、その曲線データは例えば・第６
Ａ図のようなデータ構造となる。この曲線データＤ。は
、円弧であることを示す種別データｄ、と、円弧の中心
Ｐ。の座標値（ｘ、ｙｏ）、半径Ｒ１円弧の開始点Ｐ　
の座標値（Ｘ　　、ｙｌ）ならびに終了点Ｐ。

１　　　　　　　　　　　　　１ の座標値（ｘ、ｙ）を示すデータで構成されｅ　　　　
　　ｅ ている。

第６Ｂ図は、曲線近似の結果、ベクトルｖ１とＶ２との
間が曲線Ｃ１で近似された場合の図形データのデータ構
造を示す概念図である。図に示すように、図形データＤ
ＦはベクトルＶｌのベクトルデータＤ　と曲線Ｃｔの曲
線データＤｅｌとベクｌ トルＶ　のベクトルデータＤｖ２とが順番に配列された
構造を有している。

なお、曲線の近似は円弧に限らず、所定の多項式やスプ
ライン関数などを用いて行ってもよい。

曲線近似によって得られた図形データは、ステップＳ８
で認識処理部５に伝送され、所定の認識処理を受ける。

ここで認識処理とは、いわゆる図形認識１文字認識、シ
ンボル認識などを言う。認識処理の結果、図形データは
コンピュータで取扱い情報に整理され、変換される。こ
の図形データは−Ｈメモリ６に収納される。

ステップＳ９では、こうして最終的に得られた図形デー
タがメモリ６から読出され、スキャナ１０の出力部に与
えられて図面の複製が作成される。

なお、スキャナ１０で図面を複製するかわりに、外部の
コンピュータなどに図形データを出力して所望の処理を
行うようにしてもよい。

Ｃ０変形例 本発明は上記実施例に限定されるものではなく、例えば
次のような変形も可能である。

■　線図形はベクトル列で表わされるものとしたが、ベ
クトル列に限らず、連続した複数の線分で表わされてい
ればよい。

■　形状修正処理としては、整形処理やかすれ補正処理
以外のものであってもよく、線図形の形状の乱れを修正
する処理であればよい。

■　上記実施例では曲線候補の抽出を、所定の判定条件
に従って自動的に行うようにしていた。

しかし、オペレータが任意に曲線候補を抽出するように
してもよい。この場合には、例えば複数の線分で表わさ
れた線図形（第３図（ｂ）参照）をＣＲＴなどの表示手
段に表示して、曲線候補となるべき一連の線°分（また
はその両端の端点など）をオペレータがマウスなどを用
いて指定するようにすればよい。

（発明の効果） 以上説明したように、この発明によれば、形状修正処理
を曲線候補線分を除く線分について行うので、曲線とし
て近似されるべき曲線候補線分が形状修正処理によって
誤って修正されることがなく、形状修正処理と曲線近似
処理との双方を容易にかつ適切に行うことができるとい
う効果がある。

【図面の簡単な説明】

第１図は、この発明の一実施例を適用する図面自動入力
装置の構成を示すブロック図、第２図は、実施例の処理
手順を示すフローチャート、 第３図は、実施例における線図形の処理の経過を示す概
念図、 第４Ａ図および第４Ｂ図は、ベクトルデータの構造を示
す概念図、 第５Ａ図ないし第５Ｃ図は、形状修正処理の例を示す説
明図、 第６Ａ図は、曲線データの構造を示す概念図、第６Ｂ図
は、曲線データとベクトルデータとを含む図形データの
構造を示す概念図、 第７Ａ図および第７Ｂ図は、従来における形状修正処理
と曲線近似処理の例を示す説明図である。 Ａ・・・線図形、　　　ＣＬ・・・中心線、ｖ、　　ｖ
　　〜ｖ３・・・ベクトル、ＤＶ　”　ｖｌ”””ｖ３
・・・ベクトルデータ、Ｃ１Ｃ・・・曲線、　Ｄ、Ｄ。 、・・・曲線データ、ｌ　　　　　　　ｃ ＤＦ・・・図形データ

Claims (1)

【特許請求の範囲】
1. （１）連続した複数の線分で表わされた線図形の少なく
   とも一部を曲線で近似する線図形の曲線近似方法であっ
   て、 （ａ）前記複数の線分のうち、所定の曲線判定条件を満
   足するものを曲線候補線分として特定し、（ｂ）前記複
   数の線分のうち、前記曲線候補線分を除く線分について
   、前記線図形の形状の乱れを修正する形状修正処理を施
   した後、 （ｃ）前記曲線候補線分を所定の曲線で近似することを
   特徴とする線図形の曲線近似方法。