JPS6316787B2

JPS6316787B2 -

Info

Publication number: JPS6316787B2
Application number: JP56101846A
Authority: JP
Inventors: Takeshi Masui; Shigemi Osada; Toshio Matsura
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1981-06-30
Filing date: 1981-06-30
Publication date: 1988-04-11
Also published as: JPS583081A

Description

【発明の詳細な説明】本発明は図形情報抽出処理方式に関し、特にク
ロス点を含まないループ・パターンの図形情報を
抽出できるようにした図形情報抽出処理方式に関
する。

本願出願人は、先に特願昭55−156635号（特開
昭57−81686号公報参照。）（パターン図形自動読
取り装置）として、例えばプリント配線パターン
図形を自動的に読取る装置を提案した。この装置
は、第１図に示す如く、１種類または複数種類の
ランド記号１を抽出し、その上で１つのランド記
号と他のランド記号との間に存在する線状のパタ
ーン２を抽出するようにしている。

しかし、例えばプリント板パターン図が複数層
にわたる場合においては、第２図図示の如く、線
状のパターン２の１端または両端にランド記号１
が記述されていない図面が存在する。これは他の
図面においてランド記号が記述されているために
同じランド記号を繰返して記述する煩雑さをさけ
るためであると考えてよい。

上記特願昭55−156635号開示のものは、図面上
のノイズによる影響をさけるために、上記線状の
パターン２の両端にランド記号１が存在すること
を前提として上記線状のパターン２を抽出するよ
うにしている。このために第２図図示の如く、ラ
ンド記号１を持たない線状のパターンについての
処理は上記特願昭55−156635号開示の技術をその
まま適用することが困難である。

そのため、本願出願人は第２図の如くランド記
号１のない線状のパターン２を抽出するために特
願昭56−59196号（図形情報抽出処理システム）
として、ｎ×ｍメツシユの観測枠を使用して、こ
の観測枠の少なくとも上・下・左・右の４つの辺
と右上・左上・左下・右下の４つの隅とのいずれ
の位置をこの線状のパターン２が交差するかを検
出して端点を求め、これを擬似ランドとして抽出
し、パターンの処理を行なつている。

通常、第３図に示す如く、格子軸を基準にして
描かれた線図形には、ランド記号１、線状のパタ
ーン２、ループ・パターン３、クロス点を有する
ループ・パターン４等、種々な図形が描かれてい
る。これらの線図形を自動的に読取り図形処理を
行なう場合には、このような画像データより各パ
ターンを抽出し、第４図に示す如き座標テーブル
状の記述コードとして保持することになる。例え
ばランド記号についてはそのXY座標を記憶し、
２点間を結ぶ線分についてはその出発点と終点の
XY座標を記憶し、折線分についてはその出発点
と終点の途中の屈折点の座標も含んだ座標テーブ
ルとなる。

ところで線分を近似する場合、その線分の状態
により処理方式が異なる。そして第３図に示すよ
うに、格子軸に沿つて描かれたパターンは種々の
ものがあり、また種々の状態で接続されている
が、これを大別すると第５図イ〜ニに示される４
種類に区分けされる。

すなわち第５図イの如く、パターンの両端に必
らず端点記号（シンボル）が存在する場合、ロの
如くパターンの両端に端点記号（シンボル）が無
い場合（この場合は定義されたシンボル記号が存
存せず、ただ線分のパターンだけが描かれている
ものを意味する。）、ハの如くパターンがクロス点
をもつ場合（この場合はただクロス点が１つのパ
ターンにあればよい。パターンはループであつて
もなくともよい。）、ニの如くパターンがクロス点
をもたないループ系である場合等に区分けされ
る。

そして第５図イの如きパターンの自動読取り図
形処理方式については上記特願昭55−156635号と
して出願し、同ロの如きパターンに対しては上記
特願昭56−59196号として出願し、また同ハの如
きパターンに対してはこれまた上記特願昭55−
156635号に出願した技術により処理可能である。
それ故、第５図イ，ロ，ハ等により構成される図
形に対しては、第６図に示すフローにより処理す
ることができる。

パターンの抽出すなわち図面上に格子軸を基準にして描かれ
た線図形のパターンのビデオ情報をとり、各パ
ターンを格子単位に分割して、格子単位で近似
させる。

特徴点の抽出線分パターンをベクトルで表示するときに出
発点、終点となるべき特徴点、すなわち端点記
号、端点、クロス点等を抽出する。

パターンの記述格子単位で近似されたパターンの情報とパタ
ーンの特徴点を合成してパターンをベクトルと
して求める。

しかしながら第５図ニの如きクロス点をもたな
いループ系のパターンが他のパターンと混在する
場合に対してはこれを自動読取り図形処理する方
式が未だ得られなかつたため、第３図に示す如
く、クロス点をもたないループ系のパターンを含
む図形処理を自動読取化することができなかつ
た。それ故、自動読取処理できるパターンが限定
されるため、図形処理上問題点となつていた。

したがつて本発明はこのような問題を改善し
て、他のパターンとともにクロス点を含まないル
ープパターンが存在する図形を自動読取処理する
ことができるようにした図形情報抽出処理方式を
提供するものである。そしてこのため本発明にお
ける図形情報抽出処理方式では、実質上格子線に
沿う形で描かれたパターンを抽出する図形情報抽
出処理方式において、その格子点の方向コードお
よび端点記号の有無を表す格子点ラベルコード設
定手段と、該格子点ラベルコードに基づき、端点
を抽出する端点抽出手段と、クロス点を抽出する
クロス点抽出手段と、まず、端点記号の存在する
格子点、及び、クロス点、端点の格子点ラベルコ
ードの方向コードを消去した後、順次、消去され
た方向コードに対応する方向コードの消去、端点
の格子点ラベルコードの消去を繰り返すことによ
りクロス点を有しないループ系パターンのみを残
して他の線分パターンを消去する端点追跡処理手
段と、該端点追跡処理手段により抽出されたルー
プ系パターンを形成する格子点ラベルコードの１
つをループ系パターンを形成する格子点ラベルコ
ードを追跡するための擬似端点を設定する擬似端
点設定手段と、該擬似端点の格子点ラベルコード
の方向コードに基づいてループ系パターンを形成
する格子点ラベルコードを追跡し変曲点を抽出し
てベクトル化するループ系パターン追跡手段とを
備え、少なくともクロス点を持たないループ系パ
ターンを処理できるようにしたことを特徴とす
る。

本発明を詳述するに先立ち本発明の原理につき
説明する。

例えば第３図において、クロス点を含まないル
ープパターンのみ残し、他の図形を消去する。そ
して残つたループパターンについてその頂点で
も、あるいは辺上の一点でもスタート点として擬
似端点を定め、例えば折線パターンと同様にその
屈折点の情報を含めてこれを記憶することによ
り、ループパターンに対する処理を行なうことが
できる。ループパターンが２つ以上あるときは、
先ずその１つを処理し、順次他を処理すればよ
い。

第７図にクロス点を含まないループパターンの
自動読取図形処理の原理的なフローを示す。

このフローは次の〜により構成される。

パターンの抽出図面上に格子軸を基準に描かれた図形のパタ
ーンの画像情報をとり、各パターンを格子単位
に分割して、格子単位で近似する。

端点の消去格子単位のパターンの近似から端点を意味す
る近似コード（ランド、端点、クロス点等）を
消去する。この端点の消去を繰返すことによ
り、線分パターン、クロス点を有するループパ
ターンやノイズＮは消去され、クロス点をもた
ないループパターンＬのみが残る。

擬似端点の設定このループパターンＬを形成するコード情報
の１つの点に擬似端点を設定する。この擬似端
点は各辺上のどこでもよく、例えばループパタ
ーンを検出するためにスキヤンしたとき、最初
にループパターンが検出された点でもよい。第
７図の例では頂点の１つを擬似端点（×印）と
している。

パターンの記述格子単位で近似されたパターンの情報と擬似
端点（X₁、Y₁）を合成して、擬似端点（X₁、
Y₁）を出発点および終点として屈折点を組込
んだ、｛（X₁、Y₁）、（X₂、Y₂）、（X₃、Y₃）、
（X₄、Y₄）、（X₁、Y₁）｝というベクトルを求
め、かくしてループパターンを記述することが
できる。

第８図はクロス点を含まないループパターン処
理を行なうシステム構成を示す。

パターン抽出回路１０は、格子を基準にして描
かれた線図形のパターンを格子単位のラベルに変
換する回路である。ここで行なわれる変換の方式
および回路構成は既に特願昭56−48252号として
出願ずみである。これにより第９図に示す格子点
ラベルが抽出される。そしてここではパターンの
記述としてその中で８方向コードd₀〜d₇を使用す
る。そしてこの８方向コードd₀〜d₇は、第１０図
の如き方向により定められており、例えば上方向
にパターンが伸びているときには、d₂つまりビツ
ト13のところに「１」が記入される。そしてその
パターンの伸び方向と８方向コードとの具体例が
第１１図に示される。

端点追跡回路１２は、８方向コードd₀〜d₇によ
りラベル付けされた格子点ラベルを用いて、端点
パターンを消去するものである。そしてそのため
に端点コードの消去および第１２図に示すペアと
なる連結の腕の処理を行なうものである。なおこ
こでペアとなる連結の腕とは、第１２図イに示す
如く互に一直線上に位置するような状態の腕をい
い、第１２図イ，ロに示す如く、d₀−d₄′、d₁−
d₅′、d₂−d₆′……がペアとなる連結の腕である。
そして端点コードの消去およびペアとなる連結の
腕の処理を行なうために次のような演算処理を行
なう。

端点を意味する格子点ラベルコードがあれ
ば、このコードをクリアする。例えば第１３図
イの如き端点があれば、その８方向コード
「04」（16進）を「00」（16進）にクリアし、ま
た同ロの如き端点があれば、その８方向コード
「10」（16進）を「00」（16進）にクリアする。

各格子間でペアとなる連結の腕があれば、そ
の格子点ラベルをそのままにして、ペアとなる
腕がなければその腕に対応するビツトをクリア
する。

そして上記、の処理を順次繰返し、、
に相当する格子点ラベルがなくなるまでこれ
を行ない。例えば第１４図イに示す如く、３×
３の窓で格子点ラベルをスキヤンするとき、腕
A₁が端点のため消去され、腕A₂はペアとなる
腕がないので消去される。この結果、第１４図
ロに示すようにそれぞれの８方向コードが変化
する。そして次に３×３の窓でスキヤンされる
とき、今度は同ロの腕A₃がペアとなる腕がな
いため消去され、次のスキヤンのときに今度は
腕A₄が端点となつているため消去される。こ
のようにして腕A₅，A₆が順次消去されること
になる。

第８図における端点追跡回路１２の動作フロー
を第１５図に示し、その構成を第１６図に示す。

第１６図に示す如く、端点追跡回路は、制御部
１５の外に変換チエツク回路１６、第１コード変
換回路１７および第２コード変換回路１８を具備
する。

変換チエツク回路１６は腕の消去変換制御を継
続するか否かを識別するものであつて、その構成
は、第１７図に示されるように、ROM１９、イ
ンバータ２０、アンド回路２１、オア回路２２、
フリツプフロツプ（以下FFという）２３および
インバータ２４を有する。ROM１９には、第９
図に示す格子点ラベルの８方向コードd₀〜d₇が入
され、その動作特性は第１８図に示される。この
第１８図より明らかな如く、８方向コードd₀〜d₇
のいずれか１つにのみ「１」がある場合（16進表
示で「01」、「02」、「04」、「08」のとき）のみこの
ROM１９は「１」を出力する。すなわち端点で
あるときのみROM１９は「１」を出力する。イ
ンバータ２０は、シンボルの有無を示す信号が入
力されるもので、第９図の格子ラベルにおいて第
０番目のビツト、つまりランド記号が「０」のと
き「１」を出力する。それ故アンド回路２１はシ
ンボルでなくて８方向コードが１つのみ「１」の
とき、換言すれば端点が存在するとき「１」を出
力する。この「１」はオア回路２２を経由して
FF２３のＪ端子に印加されFF２３をセツトす
る。そしてこのセツトの結果のＱ端子出力「１」
がオア回路２２を経由してＪ端子に入力されるの
でFF２３は「１」を出力し続ける。そしてこの
FF２３が「１」を出力している間は、消去すべ
き端点が存在していることを示すチエツク信号と
なる。

第１コード変換回路１７は、第１３図の如く、
端点が存在する場合にこれを消去するものであつ
て、その構成は第１９図に示されるように、第
1ROM２５、第2ROM２６、第１選択回路２７、
第２選択回路２８等により構成されている。第
1ROM２５および第2ROM２６は、８方向コー
ドd₀〜d₇が入力され、その結果、第1ROM２５は
第２０図に示す出力動作を行ない、第2ROM２
６は第２１図に示す出力動作を行なうように構成
されている。そして第１選択回路２７は、第９図
の格子点ラベルコードのランドの有無を示す第０
番目のビツト、つまりランド記号が「１」である
（ランドが存在する）とき、シンボル信号「１」
となつて上記d₀〜d₃をそのまま出力し、第９図の
格子点ラベルコードの第０番目のビツト、つまり
ランド記号が「０」である（ランドが存在しな
い）ときにはシンボル信号「０」となり第
1ROM２５からの出力を出力するものである。
また第２選択回路２８はシンボル信号「１」のと
きは上記d₄〜d₇をそのまま出力し、シンボル信号
「０」のとき第2ROM２６から伝達された信号を
出力する。換言すればシンボルに対してはそのま
まの８方向コードd₀〜d₇を出力し、端点に対して
は第1ROM２５および第2ROM２６からの出力
を出力するものである。

例えば第１３図イに示す如き端点が入力された
とき、８方向コードは「04」（16進）のため、第
1ROM２５は、第２０図に示す如く、「０」（16
進）を出力し、第2ROM２６は、第２１図に示
す如く、これまた「０」（16進）を出力する。こ
のときシンボル信号は「０」なので、この結果
「00」（16進）が出力され、端点の消去が行なわれ
る。

第２コード変換回路１８は、第１４図に示す如
く、ペアのない連結の腕を消去するものであつ
て、その構成は第２２図に示す如く、カウンタ２
９、第1RAM３０、第2RAM３１、アンド回路
３２〜３９、出力レジスタ４０およびレジスタ
R₁〜R₉を有する。ここでレジスタR₁〜R₉は３×
３のウインドウを構成するものであり、第１４図
ロの左図に示すウインドウの各部分に対応してい
る。第1RAM３０および第2RAM３１はデー
タ・シフト用のメモリであつてカウンタ２９によ
り制御される。これにより第１４図ロの左側に示
すようなデータがレジスタR₁〜R₉にセツトされ
ることになる。

そしてアンド回路３２〜３９は、レジスタR₅
にセツトされたデータにペアのない連結の腕があ
るときこれを消去するものであり、第１２図に示
すペアの状態で各８方向コードd₀〜d₇に対する他
のレジスタR₁〜R₄，R₆〜R₉とのアンド条件を求
める。すなわち、レジスタR₁に対しては、その
８方向コードのd₃とレジスタR₁のd₇′とのアンド
条件を求める。もしペアになつていればアンド回
路３２は「１」を出力するが、ペアでなければ
「０」を出力する。したがつて、第１４図イ，ロ
に示す場合には、レジスタR₅にセツトされた８
方向コードは「94」（16進）のため、d₂、d₄、d₇
がそれぞれ「１」となつている。これに対しレジ
スタR₄とR₂にセツトされた８方向コードは
「44」、「01」（16進）のために上記d₂とペアの
d₆′は「１」、また上記d₄とペアのd₀′は「１」であ
り、アンド回路３５と３３はオンとなつている。
しかしレジスタR₉にセツトされた８方向コード
は「11」（16進）のため上記d₇とペアのd₃′は
「０」となつておりアンド回路３９はオフである。
したがつて出力レジスタ４０には、このd₇が
「０」となつたことによる「14」（16進）がセツト
されることになる。かくして第１４図イに示す腕
A₂は連結するペアのないために消去される。

したがつて、第１６図に示す如く、テーブル・
メモリ１１に保持された画像データ（格子点ラベ
ル）は制御部１５により順次読出される。そして
第１コード変換回路１７でその端点が１回消去さ
れ、それからこの端点が消去されたデータに対し
て第２コード変換回路１８でペアのない連結の腕
が消去される。例えばテーブル・メモリ１１か
ら、第１４図イに示す如き画像データが出力され
たとき、第１コード変換回路１７で腕A₁が消去
され、続いて第２コード変換回路１８で腕A₂が
消去されることになる。このようなことが何回も
繰返されて端点が追跡され順次消去される。そし
てすべての端点やペアのない連結アームが消去さ
れたとき、変換チエツク回路１６は「０」を出力
し、制御部１５にこれを報告し、かくして追跡処
理が終了することになる。このようにしてノイズ
の消去は勿論のこと、線分の消去が行なわれる。

次に、上記の如き端点追跡処理回路を使用して
ループパターンを追跡するフローを第２３図につ
いて説明する。

例えば第３図に示す如き、複数のパターンが画
像メモリに格納され、このうち、線分や、クロス
点を含むループパターンについてはすでに処理が
終了し、これらに対するデータは記述ずみである
ものとする。そしてこのように処理ずみのデータ
を消去して、未処理のデータのみが入力されてい
るものとする。

まず、このデータが入力されているメモリをス
キヤンして画像データを検出する。画像データが
存在しなければそれで処理が終了となるが、存在
した場合には、そこを始点とする。そして前述の
如く追跡するが、追跡方向のないときはこれはラ
ンドであるので、これのＸ、Ｙ座標をベクトル出
力とし、すべてのランドの座標記入が終つたと
き、処理は終了する。しかし始点がループパター
ンの場合には、これを前述の如く追跡し、その変
曲点（屈折点）を検知してベクトル出力し、始点
まで戻つたときこれが終点となるのでかくして処
理が終了されることになる。

次に本発明の一実施例構成を第２４図について
説明する。

図中、４１はパターン抽出部であつて、例えば
第３図に示される線図形のパターンを前記特願昭
56−48252号に開示したように、格子単位のラベ
ルに変換するものである。また端点記号抽出回路
４２は、ランド記号の如き端点記号を抽出するも
のであり、これは、例えば第９図の格子点ラベル
の区分３〜６においてその種別を４ビツト表示す
るものである。端点抽出回路４３は前記特願昭56
−59196号に開示した手法により端点記号のない
線分の端点を抽出するものである。そしてこれか
ら統合回路４４に送出され、第３図の如きパター
ンに対する第９図に示す格子点ラベルが作成され
る。このとき太線部分については区分７に１ビツ
ト記入して太線部であることを表示する。そして
ランド記号のあるものについては区分０にランド
であることを示す「１」を記入する。そしてこの
「１」はシンボル信号として使用することもでき
る。

このようにしてテーブル・メモリ４５にセツト
された画像データに対し、前記特願昭55−156635
号に開示した手法によりクロス点抽出回路４６に
よりクロス点を検出し、また前記の如く端点を検
出し、これらにもとづき、端点追跡処理回路４７
により、クロス点をもたないループ系以外のパタ
ーンを消去する。そしてクロス点をもたないルー
プ系のパターンが残つたとき、第２３図の如きフ
ローによりこのループ系の処理を行なう。すなわ
ち擬似端点抽出回路４８により始点を求め、これ
より周知の方法でパターンの追跡を追跡処理回路
４９で行なう。そしてこれにより該ループ系パタ
ーンの始点・変曲点（折曲点）、終点等のＸ、Ｙ
座標データが求められ、これをベクトル・メモリ
５０に記述する。

勿論、このクロス点をもたないループ系パター
ンの処理に先立ち、このパターンを、前記各特許
出願に開示した手法により他のパターンに対する
記述コードとして求め、これらをベクトル・メモ
リ５０に格納しておく。

かくして本発明によれば、通常の線図形の処理
に必要とされるクロス点をもたないループ系のパ
ターンをも含めて、これらを例えば記述コードと
して保持することが可能となり、データ処理を非
常に能率的に行なうことができる。

【図面の簡単な説明】

第１図はランド記号の付与されたパターン、第
２図はランド記号のない線分のパターン、第３図
は複数の種類のパターンの混在した図形パター
ン、第４図はベクトル出力された線分の記述コー
ドの説明図、第５図はパターンの種類の説明図、
第６図は、第５図イ，ロ，ハのパターンの処理フ
ロー、第７図はクロス点を含まないループパター
ンの図形処理に対する原理的フロー、第８図はそ
のシステム構成図、第９図は格子点ラベルの説明
図、第１０図は８方向コードの説明図、第１１図
は端点を意味する格子点ラベルコードの説明図、
第１２図はペアとなる連結の腕の説明図、第１３
図は端点消去状態説明図、第１４図は端点追跡状
態及びペアとなる連結の腕のない腕を消去する場
合の説明図、第１５図は端点追跡回路の動作フロ
ー、第１６図は端点追跡回路の構成図、第１７図
は変換チエツク回路の構成図、第１８図はROM
の動作説明図、第１９図は第１コード変換回路の
構成図、第２０図は第1ROMの動作説明図、第
２１図は第2ROMの動作説明図、第２２図は第
２コード変換回路の構成図、第２３図はループパ
ターン追跡フロー、第２４図は本発明の一実施例
構成図である。図中、１はランド記号、２は線分のパターン、
１０はパターン抽出回路、１１はテーブル・メモ
リ、１２は端点追跡回路、１３は擬似端点の設定
回路、１４は追跡処理回路、１５は制御部、１６
は変換チエツク回路、１７は第１コード変換回
路、１８は第２コード変換回路、１９はROM、
２０はインバータ、２１はアンド回路、２２はオ
ア回路、２３はFF、２４はインバータ、２５は
第1ROM、２６は第2ROM、２７は第１選択回
路、２８は第２選択回路、２９はカウンタ、３０
は第1RAM、３１は第2RAM、３２〜３９はア
ンド回路、４０は出力レジスタ、４１はパターン
抽出回路、４２は端点記号抽出回路、４３は端点
抽出回路、４４は統合回路、４５はテーブル・メ
モリ、４６はクロス点抽出回路、４７は端点追跡
処理回路、４８は擬似端点抽出回路、４９は追跡
処理回路、５０はベクトル・メモリをそれぞれ示
す。

Claims

【特許請求の範囲】

１実質上格子線に沿う形で描かれたパターンを
抽出する図形情報抽出処理方式において、その格
子点の方向コードおよび端点記号の有無を表す格
子点ラベルコード設定手段と、該格子点ラベルコ
ードに基づき、端点を抽出する端点抽出手段と、
クロス点を抽出するクロス点抽出手段と、まず、
端点記号の存在する格子点、及び、クロス点、端
点の格子点ラベルコードの方向コードを消去した
後、順次、消去された方向コードに対応する方向
コードの消去、端点の格子点ラベルコードの消去
を繰り返すことによりクロス点を有しないループ
系パターンのみを残して他の線分パターンを消去
する端点追跡処理手段と、該端点追跡処理手段に
より抽出されたループ系パターンを形成する格子
点ラベルコードの１つをループ系パターンを形成
する格子点ラベルコードを追跡するための擬似端
点を設定する擬似端点設定手段と、該擬似端点の
格子点ラベルコードの方向コードに基づいてルー
プ系パターンを形成する格子点ラベルコードを追
跡し変曲点を抽出してベクトル化するループ系パ
ターン追跡手段とを備え、少なくともクロス点を
持たないループ系パターンを処理できるようにし
たことを特徴とする図形情報抽出処理方式。