JPS58214970A - 特徴点検出回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 この発明は図形や記号等が記載された図面の詔識装置に
関し、特にスキャナ外とで図面を中査して得た２値パタ
ーン中から図形や記号の特徴を検出するだめの特徴点検
出回路に関する。

図形や記号を計算機に入力する方法としては、コンピュ
ータグラフィックスを応用し気会話型グラフィックスシ
ステムなどにおいてタブレット、ディジタイザなどの座
標入力装置を利用して図形の外形などを点列で入力して
いく方丈が一般的である。この方法は会話型に作業を進
める串ができるため、容易に入力図形の作成・編集がで
きる。

自由に考えながら図形を入力することができるなどの利
点がある反面、地図、回路図などの複雑な図面の入力、
大量の図面の入力には効率１適していない。仁のため、
このような用途に対しては、最近のスキャナ技術、画像
処理技術、認識処理技術の進歩に伴って図面をスキャナ
等で走査して得た多値パターンや２値パターンから所望
の図形や記号を認識する方法の研究開発が進められ実用
化されはじめてＩρる。

一般に利用される図面においては、例えば地図や回路図
などのように、図形、記号、文字などの如く物理的な寸
法のみならず認識方法が異なるものが混在しており、以
下の認識処理を効率よく行うためにも認識処理の前にこ
れらの異質のものを分離しておく必要がある。

従来、このように図形や記号が混在する場合には、例え
ば、図形の右側に記号を書くといつたように図形と記号
の相対関係を規定したり、図形は自由に書けるが記号は
決められた位置にしホ書けないなどの制限をつけること
により図形と記号の分離を容易に行えるように図面作成
の仕様に分いて配慮されていた。

このような制限を設けることは図面を作成する立場から
見ると融ｊ１看性がなく、従って実用的には限定されブ
こ利用法しかでき々いという間頌点があるため、これに
対処するだめに制限なく自由に書された図形や記号の分
離が試みられている。

制限々〈自由に書かれた図面の２値パターンから適当な
図形に対応する黒領域を分離するだめに２／４パターン
上を走査し黒領域を検出するととが必要とかるが、従来
は１ラインずつラスタ走査を行うとと（ｆ、より黒＠域
頂点を判定１２．ていただめ、例えば水平線分の知〈ラ
スタ方向に艮１ρ線分については２値パ々−ンでの凹凸
が、そのまま黒領域頂点として判定され、従っていくつ
もの頂点が検出される。全画面を１ラインずつ順次ラス
タ走査しなければならないため、走査時間力かかるなど
の欠点があった。

この発明は前記事情を考慮してなされたものでこの発明
の目的は、図面を走査して得た２値パターンから黒領域
頂点を検出する際、１つの水Ｙ線分についていくつもの
頂点が検出されるという不都合を除去する特徴点検回路
を提供することにある。

この発明の他の目的は、前記２値パターンの走査をより
高速に行う特徴点検出回路を提供することにある。

本発明によれば、図面などを走査して得た２値パターン
務ら図形や記号を分離するために２値／’？ターン中で
の該図形や記号に対応する黒領域の上側頂点や下側頂点
を検出する回路において、前記２値パタ一ン全体に渡っ
て連続するＮライン単位で後記ライン取出情報を元に該
２値パターンを走査し、取出す走査回路と前記取出され
たＮラインの２値パターンを一時記憶するＮ個のライン
メモリと、前記Ｎ個のラインメモリのラスタ方向の各点
におけるＮ個の値をもって構成されるタイプパターンを
順次発生するタイプ発生回路と前記タイプ発生回路で発
生されるライン中でのタイプパターンの発生系列を調べ
ることにょシ、該Ｎライン内に前記黒領域の上側頂点が
存在するか否かを判定し、存在すれば上側頂点検出１ｇ
号を発生する上側頂点検出回路と同様にして前記タイプ
パターン系列を調べることにより、該Ｎライン内に前記
黒領域の下側頂点が存在するか否かを判定し存在すれば
下側頂点検出信号を発生する下側頂点検出回路と前記タ
イプパターン系列を調べることにより次にとのＮライン
を前記ライシン、そりに取出し記憶せしめるかを判定し
ライン取出情報を発生する走査ライン決定回路とを具備
することにより、２値パターン中に存在する水平線分に
対しても、凹凸の有無に彰響されず、不要な黒領域頂点
の検出を避けることができる特徴点検出回路が得られる
。

この発明の特徴点検出回路は、凹凸を有する水平線分に
対しても不要な頂点の検出を避けることができるため、
例えば図形分離処理などの以下の処理において不要な処
理を避けることができ、従って処理の高速化が実現され
る。

この発明の特徴点検出回路は、また、連続するＮライン
の状態により次に走査するＮラインを決めるように構成
されるため、不要なライン走査を避けることができ、従
って処理の高速化が実現される。

以下本発明を図面を参照して詳細に説明する。

第１図は地図の１部分の２値パターンの例を示す図であ
り、図中には等高線や学校、山頂等大小の図形が混在し
ている。

第２図は黒領域の特徴点のうちの上側頂点を検出するだ
めの一般的な方法を示す図である。

図において、黒丸・は１ドツトの黒点を示している。簡
単のため説明に必要なものは記したが、それ以外の黒点
、白点は図面上への記載を省略している。黒領域の上側
頂点の検出は図において点線で示す如く２値パタ一ン全
体をラスタ走査することにより、すべての頂点を得る方
法が一般的である。ｉ番目のライン（以下Ｌ（ｉ）と略
記する）上での頂点の検出には、Ｌ（ｉ−１）とＬ（ｉ
Ｊの２つのラインを参照する。まず、Ｌ（ｉ−１）をラ
スタ走査し白→黒への変化点を、すべて記憶しておく。

第２図の例の場合、Ｌ（ｉ−１）Ｋついては、ａ点とｂ
点の間に杜黒点は存在していない。同様にしてＬ（ｉ）
を走査したとき、ａ点で白→黒の変化があす、ｂ点で黒
→白の変化があることがわふる。

次にＬ（ｉ−１）の走査においてａ点とｂ点の間で黒点
が存在したか否かを調べる。この例ではＬ（ｉ−１）上
ではａ点とｂ点の間に黒点が存在しないので、従って、
Ｌ山の点３と点すの間の黒点は頂点とげ判定される。し
かし、Ｌ　（＋　ｔ）、の点ａと点すの間に１つでも黒
点が存在すれば、Ｌ山の点ａと点すの黒点はＬ（ｉ−１
）ｈら連続する黒領域の１部であることを意味し、上側
頂点とけならない。

次に、本発明にかかる黒領域の特徴点すなわち上側頂点
と下側頂点の検出方法について説明する。

第３図は、−例として連続する３ライン中に現われるタ
イプパターンを示す図である。以下の説明においては連
続する３ライン（すなわちＮ−３）を例にして説明して
いく。連続する３ライン内においては各ラインの黒、白
の組合わせで第３図に示す８通りのタイプパターン（Ｔ
ｏ〜Ｔ？）が存在する。Ｔｏは黒点が存在しないことを
示すパターンＴｌ、Ｔ３は黒領域の上側頂点存在の可能
性を示すパターン、Ｔ４．Ｔ６は黒領域の下側頂点の存
在の可能性を示すパターンである。Ｔ７は黒領域が該３
ラインに渡って縦方向に連結するパターンを示している
。タイプパターンＴＯ〜Ｔ７は連続する３ラインＬ（ｉ
−ｉ）、　Ｌ（ｉ）、　Ｌ（１−１−１）の左ムらの位
置ｊでの値を、それぞれｖ（ｉ−１，ｊ　）、　ｖ（Ｌ
　ｊ）ｔｖ（ｉ＋１．ｊ）とすると、（式１）で定義さ
れる。

Ｔ（ｉ、ｊ）−ｖ（ｉ−１，ｊ）Ｘ４＋ｖ（Ｌｊ）Ｘ２
−）ｖ（ｉ＋１．ｊ）　　　Ｃ式１）但し、Ｖの値は黒
点の時１．白点の時０（式１）が第３図に示す８通りの
タイプパターンＴｏＪｒ７と対応しているととは明らか
である。

第４図（飢（ｂ）は（式ｌ）を用いて発生されるタイプ
パターン系ガムら黒領域の上側頂点を検出する方法およ
び次の走査ラインを決定する方法を説明するための図で
ある。第４図（ａｌは黒領域の上側頂点が１箇所しか存
在しない場合の例、第４図（ｂ）は黒領域の上側頂点が
２箇所存在する場合の例である。

第３図の説明で述べた如く黒領域の上側頂点の存在の可
能性を示すタイプパターンはＴ１とＴ３であるが、連続
する３ラインを単位として走査すとを考慮すれば、黒領
域の上側頂点の存在の判定はＴ３の有無が必須になると
考えてよい。

以上のととふら黒領域の上側頂点であるだめのタイプパ
ターン系列はＣ式２）のように定義できる。

ＴＯ・（ＴＩ−Ｔ２・（Ｔ３）’）・Ｔｏ　　　　　（
式２）（式２）において〔〕はタタイプパターン系列１
．７［２゜Ｔ３が任意の順序・長さで連続してよいこと
を意味し、また（　）はＴ３が必須であることを意味虹
る。

従ってＴＩ、’Ｉ’２は存在してもしなくてもよい。

以下第４図を用いて説明する。

第４図＜ａＪにおいてＩ、（２）〜Ｌ（４）の走査ライ
ンの場合タイプパターン系列は、１゛Ｏ・′【０・Ｔｏ
−Ｔｏ・Ｔｔ・Ｔ３・Ｔ３・Ｔ３・ＴＯ・ＴＯとなり、
（式２）の条件がＴｏ・１゛１・Ｔ３・′ｒ３・Ｔ３・
Ｔｏの部分で満たされており、従ってＬ（３ＪのＪ−６
〜８の間に黒領域の上側頂点が存在することが検出され
る。

第４図（ｂｌにおいてＬ（２）−Ｌ（４）の走査ライン
の場合タイプパターン系列は’ｒｏ−’ｒｏ・Ｔ３・Ｔ
３パｒｌ・Ｔｌ・Ｔ３−Ｔ３・Ｔｌ−Ｔｌ・Ｔｏとなり
、（式２）の条件がＴＯ・Ｔ３・Ｔ３・Ｔ１・Ｔ１・Ｔ
３・Ｔ３・Ｔ１・Ｔ１・Ｔｏの部分で満たされており、
従ってＬ（３）のｊの場合第２図で説明した従来の方法
ではＪ−３〜４、　　ｊ−７〜８の２箇所に黒領域の上
側頂点が見つかるという不都合があったが、とこで述べ
た方法に↓す、この欠点が改善されたことがわかる。

次に本方法による”走査における走査の高速化について
説明する。第３図のタイプパターンで説明した如く、Ｌ
（ｊ）に黒領域の上側頂点が存在する必要十分条件はｃ
式ｌ）が満たされるととである。

このことは言い換えれば、１つ前の走査すなわちＬロー
２）、ＬローＩＬ玖ｉ〕のタイプパターン系列において
（弐３）が満たされることが必要条件となることは明ら
力）である。

Ｔｏ・（（ＴＩ））−’Ｉ’０　　　　　　　（弐３）
この特徴を次に走査する走査ラインの決定する規則とし
て利用し、走査の高速化をａ［ることができる。すなわ
ち、現走査ラインのタイプパターン系列において１式３
）の系列が存在しない場合は次の走査ラインをスキップ
することができる。

すなわち、現在Ｌ　（１−１）、　Ｌ（ｉ）、　Ｌ（ｉ
＋１）を走査していたとすると、本来ならば、Ｌ（ｉ）
ｅ　Ｌ（ｉ＋１）＊Ｌ（ｉ＋２）を走査しなければなら
ないが、この走査をスキップしてＬ（ｉ＋１）、Ｌ（ｉ
＋２）、Ｌ（ｉ＋３）の走査に進むことができる。

以上、魚頭１或の上側頂点を中心に説明したが、下側頂
点についても同様に下側頂点が存在する必要十分条件（
式４）と、次の走査をスキップすることができない条件
（式５）が成立つことは明らかである。

ＴＯ・（Ｔ２・Ｔ４・（Ｔ６））・Ｔｏ　　　　　（式
４）ＴＯ・（（Ｔ４）：ｌＴ’ｏ　　　　　　　　　　
（式５）第５図は本発明である特徴点検出回路を図面目
動読取装置に利用し７だ場合のブロック図である。

図において、参照番号１は情報処理装置、２はドラムス
キャナ、３は前処理回路、４は２値パターン記憶回路、
５は本発明である特徴点検出回路６は図形分離回路、７
は図形認識回路である。

ドラムスキャナ２は、情報処理装置ｆ１より信号線１０
（）を通して制御され、ドラムに張りつけられている読
取対象図面を走査し、その濃度値すなわち多値データを
信号線２００を通して前処理回路３に送る。前処理回路
３は情報処理装置１より信号線１００を通して制御され
、ドラムスキャナより送られる前記多値データを予かし
め情報処理装置ｌにより与えられている閾値で２値化し
、更にノイズ処理等を施した後、信号線３００を通して
２値パターン記憶回路４に記憶させしめ、１図面の記憶
が終了すると信号線４００を通して検出開始信号を特徴
点検出回路５に送る。２値パターン記憶回路３は、前処
理回路３から送られる２値パターンを記憶するとともに
、その内容を４８号線７００を通して特徴点検出回路５
１図形分離回路６９図形詔鵬回路７から読出すことがで
きるように構成されている。特徴点検出回路５は、前処
理回路３より検出開始を受けると信号線７００をａして
３ライン単位で２値パタ一ン全体を走査しなから該２値
パターン中に存在するすべての黒領域の特徴点を順次検
出する。１つの頂点が検出される毎に黒領域の特徴点情
報を信号線５００全通して図形分離回路６に送り記憶さ
せる。

図形分離回路６は、記則しである１゛に散点情報を元に
、例えば特徴点の位置関係等を用いて予かしめ情報処理
装置ＩＫより与えられでいる寸法以内の黒領域のみを分
離するように構成されており、第１図にむける学校や山
頂等の記号を地図中から分離する。分離が正′塁に行わ
れた場合は図形分離情報を信号線６００を通して図形認
識回路７に送る。

図形認識回路７は、図形分離情報を受けると信号ｍニア
ｏｏを通して２値パタ一ン記儒回路４の対応する２値パ
ターンを参照しながら、例えばパターンマツチング等の
方法により該図形の認識を行い認識結果を信号線１００
を通して情報処理装置１に渡す。

第６図は、本発明である特徴点検出回路５の主要部のブ
ｏツク図である。図において、参照番号５０は走査回路
、５１はラインメモリ、５２はタイプ発生回路、５３は
上側頂点検出回路、５４は下側頂点検出回路、５５は走
査ライン決定回路である。

走査回路５０１よ、信号ｖＡ４ｏｏを通して前処理回路
３より検出開始信号を受けると頂点検出動作を開始する
。すなわち、走査回路５０ｕ２値パタ一ン記憶回路４に
記憶されている２値パタ一ン全体に渡って後述の走査ラ
イン決定回路５５が発生し信号線４０１を通して送って
くるライン取出情報を元に１′ｕ号！７ｏｏを通し７て
前記２値パターン記憶回路４から連続する３ラインを読
出しラインメモリ５１に記憶させる。まだ彼述の上側頂
点検出回路５３、下側頂点検出回路５４が発生する検出
信号および特徴点情報を信号線４０１全通し°Ｃ受ける
と、信号線５００を通して前記黒領域頂点情報を図形分
離回路６に送る。

ラインメモリ５１は３個のラインメモリで構成されてお
り、その内容は信号線４０２を通してタイプ発生回路５
２に送られている。

タイプ発生回路５２は、前記ラインメモリ５１の内容を
元にラインの左から順に走査しながら（式１）で定義し
た方法で第３図で説明したタイプパターン系列を発生す
るように構成されており、発生されたタイプパターン系
列は順次信号線４０３を通しで上側頂点検出回路５：つ
、下側頂点検出回路５４および走査ライン決定回ＩＪｇ
５５に送られる。

上側頂点検出回路５３．下側頂点検出回路５４は第４図
で説明した方法で、タイプパターン系列を元に特徴点の
存在の有無の判定を打つように構成されており、頂点が
存在する場合は検出情報と特−故点の位置や巾たとを含
む特徴点情報どを信号線４０１を通して走査回路５０に
送る。

走査ライン決定回路５５は、第４図で説明した如く、（
式３）および（式５）の系列の存在を調べることにより
現在のタイプパターン系列から次に走査すべきライン群
を決定する。Ｌつ構成されており、欣に走査すべきライ
ン取出情報を信号線４０１を通して走査回路５０に送り
、次の走査ラインに対する走査を開始させる。

以上図面を用いて説明した如く、本発明により図面等を
スキャナで走査して得た２値パターン中に存在する黒領
域の特徴点を検出する際に、従来の方法では水平純分に
対してその凹凸に応じて不要な部分が頂点とし、て検出
されていプ（−という欠点が、本発明により致着され、
加えて走査時間も短縮されることがわかる〇

【図面の簡単な説明】 第１図に１大きさの異々る図形が混在する図面の２値パ
ターンの例を示す図、第２図は従来の方法による黒領域
の上側頂点検出の方法を説明する図ある黒領域の特徴点
のうちの上側頂点検出の方法を説明するだめの図、第５
図は本発明である特徴点検出回路を自動読取装置に利用
した実施例のブ胃ッ図を示す図、第６図は本発明である
特徴点検出回路を具体的に示す主要ブロック図で冴）る
。 図において、１・・・・・・・・・情報処理装置、２・
・・・・・・・・ドラムスキャナ、３・・・・・・・前
処理回路、４・・・・・・・・・２　（ａ　ハターン記
憶回路、５・・・・・・・・・特徴点検出回路、６・・
・・・・・・・図形分離回路、７・・・・・・・・・図
形認識回路、５０・・・・・・・・・走査回路、５１・
・・・・・・・・ラインメモ’へ５２−タイプ発生回路
、５３・・・・・・・・・上側頂点検出回路、５４・・
・・・・・・・下側頂点検出回路、５５・・・・・・・
・・走査ライン決定回路、を）１図 ｏｏｏｏｏｏ■■Ｏ 第３図 未４図 （α）（ｂ）

Claims (1)

【特許請求の範囲】
1. 図面などを走査して得た２値パターン−！Ｊ）ら図形に
   対応する黒領域の特徴点を検出する回路において、Ｌ７
   ．えられ；そライン取出情報に従って前記２　（ｉｔ’
   ｉパターン全体ＩＣ渡って連続するＮ（Ｎは２以上の整
   数）ライン晰位で該２値パターンから前記連続するＮラ
   イン分の２値パターンを取出す走査回路と、前記取出さ
   れたＮラインの２値パターンを一時記憶するＮ個のライ
   ンメモリと、前記Ｎ個のラインメモリのラスク方向の各
   点におけるＮ個の値をもって構成されるタイプパターン
   をライン中の各点に対して順次発生するタイプパターン
   発生回路と前記タイプパターン系列を調べ該Ｎライン内
   に前記黒領域の上側頂点が存在するか否かを判定する上
   側黒頂点検出回路と同様に１−で前記タイプパターン系
   列を調べｆｉＮライン内に前記黒領域の下側頂点が存在
   するか否りを判定する下側黒頂点検出回路と前記タイプ
   パターン系列を調べて、次にとのＮラインを取出すかを
   前記走査回路に指示する走査ライン決定回路とを具備し
   てなる情？徴点検出回路。