JPH044479A

JPH044479A - 直線抽出方法

Info

Publication number: JPH044479A
Application number: JP10692290A
Authority: JP
Inventors: Hiroyuki Kanehara; 弘幸金原
Original assignee: Ricoh Co Ltd
Current assignee: Ricoh Co Ltd
Priority date: 1990-04-23
Filing date: 1990-04-23
Publication date: 1992-01-08

Abstract

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

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、図面認識システム等において入力された２値
画像より直線を抽出する方法に関する。

〔従来の技術〕

この種の直線抽出に関しては、特開平１−２６９１８５
号公報に述べられている直線成分抽出方式が知られてい
る。この方法は、第６図に示すように、注目ベクトルｖ
１と、これにつながるベクトルｖ２を結ぶ直線ＰＩＰ２
と、両ベクトルの交点との距離ｔ□が閾値Ｔ以下である
ならばベクトルＶ１．　Ｖ２を統合して直線Ｐ工Ｐ２に
置き換え、ベクトルｖ２につながるベクトル■３がある
ならば、同様に直線Ｐ□Ｐ３とベクトルｖ１．■２の交
点との距離ｔ２と閾値Ｔとを比較し、もしｔ２≦Ｔのと
きにはバク１〜ルＶ、、Ｖ２にベクトルＶ３を統合して
直線ＰｉＰ３に置き換えるという統合過程を繰り返すこ
とによって、直線を抽出する方法である。

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

しかし、線分の交差点すなわち複数のベクトルの合流点
または分岐点で、ベクトルの誤統合により抽出間違いが
起きやすく、また半径の大きな円弧等を誤って直線とし
て抽出しやすいため、機械図面のような複雑な図面を処
理する用途には問題があった。

本発明の目的は、そのような誤抽出を削減できる実用的
な直線抽出方法を提供することにある。

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

特許請求の範囲の請求項（１）記載の発明は、２値画像
上の線分を折線近似したベクトルに関し、注目ベクトル
の隣接ベクトルを探索し、注目ベクトルとの間でなす角
度及び線幅がそれぞれ閾値以下の隣接ベクトルを注目ベ
クトルと同じ直線の候補ベクトルと判定し、注目ベクト
ルとの間でなす角度及び線幅がそれぞれ閾値以下の隣接
ベクトルが複数ある場合は、角度及び線幅が最小の−っ
の隣接ベクトルを候補ベクｊ・ルと判定し、候補ベクト
ルと判定した隣接ベクトルをを改めて注目ベクトルとし
て同様の隣接ベクトルの探索と候補ベクトルの判定の処
理を繰り返すことにより、直線を構成する一つづきの候
補ベクトル群を抽出することを特徴とする特許請求の範囲の請求項（２）記載の発明は、２値画像
の黒画素を追跡して輪郭ベクトルを抽出し、ペアをなす
輪郭ベクトルより芯線ベクトルを抽出し、芯線ベクトル
に関し前記の如き直線抽出処理を行い、候補ベクトルと
して抽出した芯線ベクトルに対応した輪郭ベクトルを参
照することにより直線の線幅を求めることを特徴とする
。

〔作　用〕

注目ベクトルの隣接ベクトルが直線の候補ベクトルか否
かの判定条件として、両ベクトル間でなす角度と線幅（
第４図参照）を用いるため、径の大きな円弧等を直線と
して抽出する間違いを減らすことが可能である。また、
判定条件を満たす隣接ベクトルが複数存在する場合、そ
の中で角度及び線幅が最小の一つの隣接ベクトルを注目
ベクトルと同じ直線の候補ベクトルとして選ぶため、複
数のベクトルの合流点または分岐点での候補ベクトルの
選択間違いを減らし、他の線分と交差した直線の抽出精
度を上げることが可能である。

また、請求項（２）記載の発明によれば、抽出した線分
の正確な線幅（太さ）を簡単に求めることができる。

さらに、処理内容が比較的単純であるうえに、候補ベク
トルの判定閾値を変更することにより、清書された図面
から手書きの図面まで容易に対応可能であり、また輪郭
ベクトル抽出及び芯線ベクトル抽出は、機械図面等の認
識処理の場合に前処理としてもともと必要となる処理で
ある。

このように本発明の直線抽出方法は、機械図面等の認識
システムにおける直線抽出方法として最適かつ実用的で
ある。

〔実施例〕

第１図は一実施例に係る図面認識システムのブロック図
である。１は機械図面等の２値画像データを記憶するた
めの画像メモリであって、その２値画像データは外部の
スキャナ等から入出力インタフェース部２を介して入力
する。３は処理を実行するＣＰＵ、４はＣＰＵ３により
実行される処理のプログラムを記憶するプログラムメモ
リであり、ここに記憶されるプログラムとしては輪郭ベ
クトル抽出、芯線化、直線抽出、その他の図面認識のた
めの処理のプログラムが含まれる。５は処理の中間デー
タや結果データを記憶するためのデータメモリである。

第２図はＣＰ’Ｕ　３による直線抽出処理の全体的な流
れを示すフローチャートである。

なお、処理■■は、実際的な直線抽出のための処理■〜
０の前処理であるが、図面認識処理全体の前処理でもあ
る。すなわち、処理■■は本発明による直線抽出のため
だけに必要となるものではない。

処理■■ 画像メモリ１に入力された２値画像の黒画素を追跡する
ことによって、線分の輪郭を折線近似する輪郭ベクトル
を抽出し、そのデータをデータメモリ５に記憶する。こ
の輪郭ベクトルのデータより、ペアをなす輪郭ベクトル
の中心線を芯線ベクトルとして抽出し、そのデータを輪
郭ベクトルと対応させてデータメモリ５に記憶する。こ
の芯線ベクトルは線分を折線近似したベクトルである。

なお、このような輪郭ベク１−ル抽出（■）及び芯線化
（■）は、例えば論文「大沢ほか；″多次元データ構造
を用いた図面処理″、電子通信学会論文誌、Ｖｏｌ、Ｊ
　６８−Ｄ、　Ｎｏ、４．１９８２年４月。

ｐｐ、８４５−５８２Ｊ及び論文「大沢ほか；″輪郭線
をベースにした芯線化方式の改良″、情情報処理学会第
３目０１」に述べられている方法によればよい。

処理■ データメモリ５の芯線ベクトルデータを参照し、処理済
みフラグが設定されていない芯線ベクトルを探す。見つ
けた一つの芯線ベクトルを注目ベクトルＣＶＥＣとし、
処理■に進む。注目ベクトルが見つからない場合、処理
を終了する。

処理■ 芯線ベクトルデータを参照し、処理済みフラグが設定さ
れていない芯線ベクトルより、注目ベクトルＣＶＥＣの
前方の隣接ベクトルＮＶＥＣを探す。

第３図に注目ベクトルと隣接ベクトルの例を示す。（Ａ
）は隣接点が屈曲点の場合、（Ｂ）は隣接点が線分の分
岐点または合流点の場合である。

なお、（Ｂ）の破線は輪郭ベクトルより抽出した芯線ベ
クトルの交流点または分岐点での切れを接続するだめの
コネクトベクトルであり、前記論文　　　　′″輸郭線
をベースにした芯線化方式の改良″における”ｇｌｕｅ
ベクトル″に対応する。

処理■ 各隣接ベクトルＮＶＥＣと注目ベクトルＣＶＥＣとの間
の角度及び線間（第４図参照）を求め、角度及び線間が
それぞれ閾値以下であれば、その隣接ベクトルを注目ベ
クトルと同じ直線の候補ベクトルＬＶＥＣと判定し処理
■に進む。

複数の芯線ベクトルが合流または分岐する交差点では、
注目ベクトルに対する隣接ベクトルが複数存在し、その
複数本の角度及び線幅が閾値以下となる場合がある。こ
の場合、その複数本の隣接ベクトルの中で、注目ベクト
ルとの角度及び線幅が最小の１本の隣接ベクトルを候補
ベクトルＬＶＥＣと判定する。

隣接ベクトルのいずれも上記条件からはずれている場合
、注目ベクトルの前方に候補ベクトルがないものとして
処理■へ進む。

処理■ 直線の候補ベクトルＬＶＥＣをデータメモリ５内の直線
候補配列に登録（代入）した後、この候補ベクトルＬＶ
ＥＣを新たに注目ベクトルＣＶＥＣに選び処理■へ戻る
。ただし、隣接ベクトルの探索方向は注目ベクトルＣＶ
ＥＣの前方に固定である。

処理■ 注目ベクトルＣＶＥＣの前方に直線の候補ベクトルがな
いと判断されたので、注目ベクトルＣｖＥＣの後方の隣
接ベクトルＮＶＥＣを探す。つまり逆方向について処理
■と同様の処理を行う。

処理■ 処理■と同様に隣接ベクトルから候補ベクトルＬＶＥＣ
を探す。見つからないときは処理［相］に進み、見つか
ったときは処理■に進む。

処理■ 候補ベクトルＬＶＥＣを直線候補配列に代入し、この候
補ベクトルＬＶＥＣを新たに注目ベクトルＣＶＥＣとし
て処理■に戻る。ただし、候補ベクトルを検索する方向
は後方に固定である。

処理［相］ ■から■の処理により求められて直線候補配列に登録さ
れた候補ベクトル全体について、線幅の閾値を用いて確
認を行い。すなわち、第５図に矢印で示した一つづきの
候補ベクトル中の、処理■で注目ベクトルＮＶＥＣに選
ばれたバク１〜ルの上下の線幅閾値内に存在し、かつ他
の直線の一部となっていない候補バク１〜ル（太い矢線
で示した候補ベクトル）だけを選ぶ。そして、ここで選
んだ候補ベクトル群の一方の端から他の一方の端までの
長さが文字サイズより大きい場合、この候補ベクトル群
を直線のベクトルと確定する。すなわち第５図の例では
、Ｐ□を始点、Ｐ２を終点とした直線が抽出される。

また、確定したベクトルに対応した輪郭ベクトルを参照
し、直線の正確な線幅（太さ）を求める。

処理０直線と確定された芯線ベクトル及び対応した輪郭ベクト
ルに処理済みフラグを設定し、処理■に戻る。

〔発明の効果〕

以上の説明から明らかなように、本発明の直線抽出方法
は、比較的簡単な処理によって、機械図面などでしばし
ば現れる他の線分と交差した直線も確実に抽出可能であ
り、曲率の小さな円弧等の曲線の誤抽出を減らすことが
可能であり、また直線の太さを正確に抽出可能であり、
さらに直線の候補ベクトルの判定閾値を変更するだけで
清書された図面から手書きの図面まで対処可能である等
、機械図面認識システム等の直線抽出方法として最適か
つ実用的である。

【図面の簡単な説明】第１図は本発明の一実施例に係る図面認識システムのブ
ロック図、第２図は直線抽出処理の全体の流れを示すフ
ローチャー１・、第３図は注目ベクトルと隣接ベクトル
の説明図、第４図は注目ベクトルと隣接ベクトルとの間
の角度及び線幅の説明図、第５図は線幅閾値による直線
候補ベクトルの確定方法の説明図、第６図は従来方法の
説明図である。１・・・画像メモリ、　３・・・ＣＰＵ、４・・・プロ
グラムメモリ、　　５・・・データメモリ、ＣＶＥＣ・
・・注目ベクトル、ＮＶＥＣ・・・隣接ベクトル。

Claims

【特許請求の範囲】

（１）２値画像上の線分を折線近似したベクトルに関し
、注目ベクトルの隣接ベクトルを探索し、注目ベクトル
との間でなす角度及び線幅がそれぞれ閾値以下の隣接ベ
クトルを注目ベクトルと同じ直線の候補ベクトルと判定
し、注目ベクトルとの間でなす角度及び線幅がそれぞれ
閾値以下の隣接ベクトルが複数ある場合は、角度及び線
幅が最小の一つの隣接ベクトルを候補ベクトルと判定し
、候補ベクトルと判定した隣接ベクトルを改めて注目ベ
クトルとして同様の隣接ベクトルの探索と候補ベクトル
の判定の処理を繰り返すことにより、直線を構成する一
つづきの候補ベクトルを群を抽出することを特徴とする
直線抽出方法。
（２）２値画像の黒画素を追跡して輪郭ベクトルを抽出
し、ペアをなす輪郭ベクトルより芯線ベクトルを抽出し
、芯線ベクトルに関し請求項（１）記載の直線抽出処理
を行い、候補ベクトルとして抽出した芯線ベクトルに対
応した輪郭ベクトルを参照することにより直線の線幅を
求めることを特徴とする直線抽出方法。