JPS5846476A - 黒領域頂点検出回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 この発明は、図形や記号等が記載された図面の認識装置
に曲し、特にスキャナなどで図面を走査して得た２値パ
ターン中から図形や記号を分離認識するための黒領域頂
点検出回路に関する。

図形や記号を＃［算機に入力する方法としては、コンピ
ュータグラフィックスを応用した会話型グラフィックス
システムなどにおいてタブレット。

ディジタイザなどの座標入力装置を利用して図形の外形
などを点列で入力していく方式が一般的である・この方
法は、会話型に作業を進める事ができるため、容易に入
力図形の作成・編集ができる。

自由に考えながら図形を入力することができるなどの利
点がある反面、地図１回路図表どの複雑な図面の入力、
大量の図面の入力には効率上適してｂない。

とのた″め、このような用途に対しては、最近のスキャ
ナ技術９画鐵処理技術、認識処理技術の進歩に伴なって
図面をスキャナ等で走査して得た多値パターンや２値パ
ターンから所望の図形や記号を認識する方法の研究開発
が進められ実用化されはじめてｂる。

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

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

このような制限を設けることは図面を作成する立場から
見ると融通性がなく、従って実用的には限定された利用
法しかできなりとｂう問題があるため、これに対処する
ために制限なく自由ｉｃ書；６ｂれた図形や記号の分離
が試みられて匹る・制限なく自由ＶＣ書かれた図面の２
値）くターンから適当な図形に対応する黒領域を分離す
るために２値パターン上を走査し黒領域を検出すること
が必要となるか、従来はｌラインずつラスタ走査を行う
ことにより黒領域頂点を判定していたため、的えば、水
平線分の如くラスク方向に長い線分については２値パタ
ーンでの凹凸がその１ま黒領域頂点として判定され、従
っていくつもの頂点が検出される。全画面を１ナインず
つ順次ラスク走食しなければならないため走査時Ｉ川が
かかる、などの欠点があった。

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

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

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

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

この発明の黒領域検出回路は、また、連続するＮライン
の状態により次ＶＣ矩査するＮラインを決めるように＠
成されるため不要なライン走査を避けることかで１ａ１
従って処理の高速化が実現される− 以下本発明を図面を参照して詳細に説明する。

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

第２図は黒領域頂点を検出するための一般的表方法を示
す図である０図において黒丸−ｅ−ｔｌドツトの黒点を
示している。簡単のため説明に盛装なものは記したが、
それ以外の黒点、白点は図面上への記載を省略して＾る
。黒領依頂点の検出は図にお込で点線で示す如く２値パ
タ一ン全体をラスク走査することによりすべでの頂点を
得る方法が一般的である。ｉ番目のライン（以下Ｌ（＋
）と略記する）上での頂点の検出にはｂ　Ｌ（ｉ−１）
とＬ（ｉ）の２つのラインを射熱する。まずＬ（＋−１
）をラスク走奔し、白→黒への変化点および黒→白への
変化点をナベて記憶しておく・第２図の例の場合。

Ｌ（ｉ−１）Ｋついては、ａ点とｂ点の）ｉｎ　Ｋは黒
点は存在してｂない・同様にしてＬ（ｉ）を走査したど
き、ａ点で白→黒の変化があシ、ｂ点で黒→白の変化が
あることがわかる・次にＬ（ｉ−１）の走査においてａ
点とｂ点の間で黒点が存在したか否かを調べる。この回
ではＬ（ｉ−１）上ではａ点とｂ点の間に黒点が存在し
ないので、従ってＬ（ｉ）の点ａと点５０間の黒点は頂
点として判定されるーしかし、　Ｌ（ｉ−１）の点ａと
点すの間に１つでも黒点が存在すれば、Ｌ（ｉ）の点ａ
と点すの黒点はＬ（ｉ−１）から連続する黒領域の１部
であることを意味し、頂点とはならなり。

次に１本発明にかかる黒領域頂点の検出方法について説
明する。

第３図は、−同として連続する３ライン中に現われるタ
イプパターンを示す図である。以下の説明におりては連
続する３ライン（すなわちＮ＝３）を例にして説明して
囚〈、連続する３ラインを各ラインの黒、白の組合わせ
で第３図に示す８造りのタイプパターン（’ｌ’Ｑ〜Ｔ
７）が存在する。ＴＱは黒点が存在しないことを示すパ
ターン、　ＴＩ、Ｔ３は黒領域の存在の可能性を示すパ
ターン、Ｔ４゜′ｖ６は黒領域の下端点の存在の可能性
を示すパターンである・Ｔ７は黒領域が該３フインに渡
って縦方向に連結するパターンを示している。タイプパ
ターン１゛０〜Ｔ７は連続する３ラインＬ（ｉ−１）。

Ｌ（ｉ）、Ｌ（ｉ＋１）の左からの位置ｊでの値をそれ
ぞれＶ（ゑ−”ｅｊ）ｓｖ（ｔｓＪＬｖ（ｔ＋ｘ、ｊ）
とすると、（式ｌ）で定義される。

Ｔ（ｉ、ｊ）＝ｖ（ｉ−Ｌｊ）×４＋ｖ（ｉ−ＤＸ２＋
ｖ（ｉ＋ＩＷ）（式１） 但し、Ｖの値は黒点の時！、白点の時０（式ｌ）が第３
図に示す８通りのタイプパターンＴＯ〜Ｔ７と対応して
−ることは明らかである。

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

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

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

ＴＯ・〔１゛１・Ｔ２・（Ｔ３　）　）・Ｔｏ　　　　
　（式２）（式２）におりで〔〕はタタイプくターンＴ
Ｉ、Ｔ２゜Ｔ３が任意の順序・長さで連続してよいこと
を意味し、！た（　）はＴ３が必須であることを意味す
る。従って’Ｉ’ｌ、Ｔ２は存在してもしなくてもより
・以下編４図を用いて説明する。

第４図（ａ）　においてＬ（２）〜Ｌ（４）　ＣＤ走査
ラインの場合タイプパターン系列はＴＯ・’ｒ□、’ｒ
□・＋１゛０・Ｔ１・・１゛３・Ｔ３・Ｔ３・ＴＯ・Ｔ
Ｏとムリ、（式２）の条件がＴＯ・１“１−Ｔ３・Ｔ３
・Ｔ３・ＴＯの部分で満たされておハ従ってＬ（３）の
ｊ・・６〜８の間に黒領域頂点が存在することが検出さ
れる・第４図（ｂ）においでＬ（２）〜Ｌ（４）の走置
ラインの場合タイプパターン系列は’Ｉ’Ｑ、ＴＱ−’
ｌ’３・Ｔ３・Ｔｌ−Ｔｌ・Ｔ３・Ｔ３・Ｔ１・Ｔ１・
ＴＯとなシ、（式２）％式％ Ｔ１・ＴＯの部分で満たされておシ、従って１．（３）
のｊ＝３〜８０間に黒領域頂点が存在することが４寅出
される。第・１図（１））からも明らかなように仁の場
合第２図で説明した従来の方法ではｊ＝３〜４ｊｊ＝ｑ
〜８の２箇所に黒領域頂点が見つかるとｂう不都合があ
ったが、ここで述べた方法によりこの欠点が改善された
ことがわかる。

次に本方法による走査における走査の高速化につｂて説
明する。第３図のタイプパターンで説明した如く、ＴＯ
は黒領域がなりことを示し、’ｉ’７は縄領域が連続す
ることを示す・このことは言込かえれば、ＴＯのタイプ
パターンが１ラインスキツプした走査ラインで現われる
タイプパターンはＴＩ、Ｔ２．Ｔ２Ｃ，かあシえなりこ
とおよびＴＩのタイプパターンが１ラインスキツプした
走査ラインで現われるタイプパターンはＴ４Ｃかありえ
ないことを示してｈる・この特徴を次に走査する走査ラ
インの決定する規則として利用し、走査の高速化を計る
ことができる。すなわち、現走査ラインのタイプパター
ン系列がすべてＴＯである場合、またはＴＯ以外のタイ
プパターンを含むグループが必ずＴＩを含む場合は次の
走査ラインをスキップすることができる。すなわち現在
Ｌ（ｉ−１）。

Ｌ（ｓ）ｅＬ（ｔ＋ｔ）を走査していたとすると本来な
（１１） らばＬ（ｉ）　ａ　Ｌ（ｓ　＋　１　）　ａ　”　（ｉ
　＋　２　）を走査し々ければならなりが、この走査を
スキップしてＬ（ｉ＋１）Ｌ（ｉ＋２）　、Ｌ（ｉ＋３
）の走査に進むことができる・第５図は本発明である黒
領域頂点検出回路を図面自ｔｔｈ読取装置に利用した場
合のブロック図である０図において、参照番号ｌは情報
処理装置、２はドラムスキャナ、３は前処理回路、４は
２値パターン記憶回路、５は本発明である黒領域頂点検
出回路、６は図形分離回路、７は図形認識回路である。

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

図形分離回路６は、順次送られる黒領域頂点情報を元に
、例えば予かじめ情報処理装置ｌによシ与えられている
寸法以内の黒領域の魯を分離するように構成されておシ
、第１図における学校や山頂等の記号を地図中から分離
する。現在の黒領域頂点情報に対して分離が正常に行わ
れた場合は図形分離情報を信号線６００を通して図形認
識回路７ｔ■ に送る。一方分離できなかった場合には信号線１００を
通して黒領域検出回路５Ｖｃ黒領域頂点検出動作の続行
を指示する０図形認識回路７は、図形分離情報を受ける
と信号線７００を通して２値パターン記憶回路４の対応
する２値パターンを参照しながら、しｕえばパターンマ
ツチング等の方法によシ該図形の認識を行す、認識結果
を信号線１００を通して情報処理装置ＩＶｃ渡すととも
に、黒領域頂点検出回路５に黒領域頂点検出動作の続行
を指示する。

第６図は１本発明である黒領域頂点検出回路５の主要部
のブロック図である０図におして、参照番号５０は走査
回路、５１はラインメモリ、５２はタイプ発生回路、５
３は判定回路、５４は頂点検出回路、５５は走査ライン
決定回路である・走査回路５０は、信号線４００を通し
て前処理回路３より検出開始信号を受けると頂点検出動
作を開始する。すなわち、走査回路５ｏは２値パターン
記憶回路４に記憶されてｂる２値パタ一ン全体に渡って
講述の走査ライン決定回路５５が発生０４） し信号線４０１を通して送ってくるライン取出情報を元
に、信号線７００全通して前記２値パターン記憶回路４
から連続する３ラインを読出しラインメモリ５１に記憶
させる。また伏述の頂点検出回路５４が発生する検出信
号および黒領域頂点情報を信号線４０１ｉ通して受はる
と、信号線５００を通して前記黒領域頂点情報を図形分
離回路６に送る。

ラインメモリ５１は３個のラインメモリで構成されてお
り、その内容は信号線・１０２全通してタイプ発生回路
５２に送られている。／１′タイプ晃生発生″：４５２
は、前記ラインメモリ５１の内容を元にラインの左から
順に走査しながら（式１）で定義した方法で第３図で説
明したタイプパターン系列を発生するように構成されて
：ひり、発生されたタイプパターン系列は順次信号線４
０３を通して判定回路５３内の頂点検出回路５４と走査
ライン決定回路５５に、送られる・ 判定回路５３は、頂点検出回路５４゛と走査ライン決定
回路５５から構成されてお郵、前記タイプα５）・ パターン系列を元に頂点検出および次に走査するライン
の決定を行う。

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

走査ライン決定回路５５は、第４図で説明した方法によ
シ現在のタイプパターン系列から次に走査すべきライン
群を決定するよう構成されておシ次に走査すべきジイン
取出情報を信号線４０１を通して走査回路５０に送シ、
次の走査ラインに対する走査を開始させる・ 以上図面を用いて説明した如く１本発明によシ図血等を
スキャナで走査して得た２値パターン中に存在する黒領
域の各頂点を検出する際に１従来の方法では水平線分に
対してその凹凸Ｖこ１６じて不要な部分が頂点として検
出されＣいたという欠点が、本発明により改善され、加
えて紺青時間も短（紛 縮されることがわかる。

【図面の簡単な説明】

第１図は大きざの異なる図形が混在する図面の２値パタ
ーンの例を示す図、第２図は従来の方法による黒領域頂
点検出の方法を説明する図、第３図は本発明にかかる黒
領域頂点検出の際に利用されるタイプパターンを示す図
、第４図は本発明である黒領域頂点検出の方法を説明す
るための図、第５図は氷見ゆｊである黒領域頂点検出回
路を自動読取装置に利用した実施例のブロック図を示す
起、第６図は本発明である黒領域頂点検出回路を具体的
に示す主侠ブロック図である。 図において、１・・・情報処理装置、２・・・ドラムス
キャナ、３・・・前処理回路、４・・・２値パターン記
憶回路、５・・・黒領域頂点検出回路、６・・・図形分
離回路、７・−・図形認識回路、５０−・・走査回路、
５１・・・ラインメモリ、５２・・・タイプ発生回路、
５３−・・判定回路、５４・・・頂点検出回路、５５・
・・走査ライン決定回路、を示す― 一１η 第１図 第　２　図 ！−，う　ち ジ　丁Ｉ　　Ｔ） 第 （α） ３図 ■３　丁４　７ｓ　　Ｔａ　　７７ ４図 ｊ＋　　ｚ３４５ｓ７ｓ９１ｏｔ＋ （ｂ） 第５図 第６図 （ｎ ５ｊ　　′−一一−−−’

Claims (1)

【特許請求の範囲】
1. 図面などを走査して得た２値パターンから１図形に対応
   する黒領域を分離し認識する回路において、与えられた
   ライン取出情報に従って前記２値パタ一ン全体に渡って
   連結するＮライン単位で該２値パターンから前記連続す
   る１〜ライン分の２値パターンを取出す走査回路と、前
   記取出されたＮラインの２値パターンを一時記憶するＮ
   個のラインメモリと、前記Ｎ個のラインメモリのラスク
   方向の各点におけるＮ個の値をもって構成されるタイプ
   パターンをライン中の各点ＶＣ対して順次発生するタイ
   プ発生回路と、前記タイプ発生回路で発生されるライン
   中でのタイプパターンの発生系列を調べ、該ヘライン内
   に前記黒領域頂点が存在するか否かを判定し存在すれば
   頂点検出信号を発生し、かつ前記タイプパターン発生系
   列から次にどのＮラインを前記ラインメモリに取出し記
   憶せしめるかを決定しライン取出情報を発生し前記走査
   回路へ与える判定回路とを具備してなる黒領域頂点検出
   回路。