JPS6246035B2

JPS6246035B2 -

Info

Publication number: JPS6246035B2
Application number: JP55103879A
Authority: JP
Inventors: Masumi Yoshida; Shigemi Osada; Yukikazu Kaburayama; Toshio Matsura
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1980-07-29
Filing date: 1980-07-29
Publication date: 1987-09-30
Also published as: JPS5729171A

Description

【発明の詳細な説明】本発明は、パターン分離識別化処理方式、特
に、ブロツク・パターンに直接接しているワイヤ
リング・パターンの直接接触直線成分に対して１
つのラベルを付与しておいて、それに連結される
直線成分に同一ラベルを付与してゆくようにし、
互に電気的に接続されるべきワイヤリング・パタ
ーンに同一ラベルを付与するようにしたパターン
分離識別化処理方式に関するものである。

論理回路図などの設計に当つては、、予め定め
られた描画規則をもとに図形を手書きし、その
後、この手書き図面上の種々の線分をデザイン・
オートメーシヨン・システムに合致したコードに
変換し、これをもとに回路パターンを自動的に製
造する自動化システムが採用されつつある。

本発明は、上記課題を解決すべく、例えば第１
図図示の如き論理回路原図から、第２図図示太線
の如くワイヤリング・パターンに属する各直線成
分，，……を抽出し、次いで第３図図示の如
く互に連結される直線成分に同一ラベルを附与し
てゆき、その上で第４図図示の如く互に電気的に
接続されるべきワイヤリング・パターンの直線成
分のラベルを統合化するようにすることを目的と
している。即ち、本発明は、第１図図示の論理回
路ブロツク１―１ないし１―１５を無視し、第２
図図示の如くワイヤリング・パターン２に属する
各直線成分，，……の座標（ｘ_s，ｙ_s）（ｘ
_e，ｙ_e）と後述する連結コードとを抽出し、次い
で第３図図示直線成分，，……の如く単一の
ワイヤリング・パターンに共通なラベルを付与す
るようにし、更に第４図図示Ｎの如く電気的な接
続点をもとに同一のワイヤリング・パターンに同
じラベルを附与するようにすることを特徴として
いる。以下図面を参照しつつ説明する。

第１図は本発明の処理対象となる原図形、第２
図は第１図図示の原図形からワイヤリング・パタ
ーンに属する直線成分を抽出した状態を表わす説
明図、第３図は互に連結される直線成分を説明す
る説明図、第４図は本発明にいうラベルの統合化
を説明する説明図、第５図および第６図は本発明
にいう描画規則の一例を説明する説明図、第７図
は本発明の一実施例全体構成図、第８図は本発明
にいう連結コードを説明する説明図、第９図は第
７図図示の直接接触直線成分抽出処理部６による
処理結果の一例、第１０図は第７図図示のワイヤ
リング・パターン・ラベル化処理部７とラベル修
正処理部８との処理をフローチヤートの形で表わ
した説明図、第１１図は第７図図示のワイヤリン
グ・パターン・ラベル化処理部７の一実施例、第
１２図は第１０図図示の処理〔〕における垂直
方向処理に対応する一実施例回路、第１３図は第
７図図示のラベル修正処理部８の一実施例、第１
４図ないし第２０図は第１０図図示の処理
〔〕，〔〕，〔〕を行なう場合の処理の態様、
第２１図は未統合ラベルとその処理態様とを表わ
した説明図、第２２図は第７図図示のラベル統合
化処理部９の一実施例をフローチヤートの形で示
したもの、第２３図は第２２図に示す処理〔〕
の一実施例、第２４図および第２５図は第７図図
示のラベル統合化処理部９による処理態様を説明
する説明図を表わす。

上記手書き図面は、第５図図示の如く、予め定
められたメツシユ３上にパターン４として描かれ
ているものとし、該パターン４を描くに当つて次
の規則が存在しているものとして、以下説明す
る。

即ち、 (A) メツシユ３上には、予められたＸ座標XH₁な
いしXH₅の如く区切り位置が存在し、論理回路
パターン・ブロツク（ブロツク・パターン）１
の左辺は必らず上記Ｘ座標XH₁，XH₂……のい
ずれかをもつ。したがつて、第６図Ａ図示の如
く、ブロツク１の左辺がＸ座標XH₁などをもた
ないブロツク１は存在しない。

(B) メツシユ３上に描かれるワイヤリング・パタ
ーン２は、メツシユ３上の線分に沿つて上・
下・左・右のいずれかの方にのみ延長されてい
る。したがつて、第６図Ｂ図示の如きワイヤリ
ング・パターンは存在しない。

(C) メツシユ３上に描かれるブロツク・パターン
１の右辺は、上記Ｘ座標XH₁，XH₂，……など
をもつか否かは任意であり、一般には当該座標
に合致しない。

(D) メツシユ３上に描かれるブロツク・パターン
１に対する入力側ワイヤリング・パターン２
は、ブロツク・パターン１の左辺のみからブロ
ツク・パターン１に入力され、かつ出力側ワイ
ヤリング・パターン２は、ブロツク・パターン
１の右辺のみから出力される。したがつて、第
６図Ｃ図示上方の如きパターンは存在しない。

(E) 入出力ワイヤリング・パターン２は、ブロツ
ク・パターン１の左辺または右辺の中間位置に
接する。したがつて、第６図Ｃ図示下方の如き
パターンは存在しない。

(F) ワイヤリング・パターン２についての電気的
接続点は必らずＴ分岐し、かつ図形上の＋分岐
点は電気的には非接点である。

第７図は本発明の一実施例全体構成図を示し、
図中の符号５はベクトル図形であつて第２図図示
の如く存在する各直線成分に区分されているもの
（一般には各直線成分の始端点の座標や終端点の
座標や各端点の後述する連結コードとをテーブル
にまとめられている）を表わす。６は、直接接触
直線成分抽出処理部を表わし、上述の論理回路ブ
ロツク・パターンと直接接しているワイヤリン
グ・パターンの直線成分を抽出する処理を行なう
（該処理については出願人が別に提出した「図形
パターン分離抽出処理方式」に開示されてい
る）。なおそれによる処理結果の情報については
第９図を用いて後述する。７は、ワイヤリング・
パターン・ラベル付け処理部であつて、第１０，
１１，１２図を参照して後述される如く、明らか
にワイヤリング・パターンに属する各直線成分に
ついてラベル付与を行なう処理を行なう。８は、
ラベル修正処理部であつて、第１０，１３図を参
照して後述される如く、処理部７によつて付与さ
れたラベルについて修正し統一化してゆく処理を
行なう。９はラベル統合化処理部であつて、第２
１，２２，２３図を参照して後述する如く、本来
電気的に接続されるべきワイヤリング・パターン
に対して同一ラベルを付与するよう統合化する処
理を行なう。

本発明の説明に先立つて本発明にいう連結コー
ドについて第８図を参照して説明しておく。本発
明の場合、第８図Ａ図示の如く、直線成分の端点
Ｔがあるとして当該端点Ｔからいずれの方向に直
線成分が延長しているかを記述するために「連結
コード」なる概念を導入している。そして、第８
図Ｂ図示の如く、水平右方向に延長している場合
に方向コード「１」に対して論理「１」を与え、
垂直上方向に延長している場合に方向コード
「２」に対して論理「１」を与え、水平左方向に
延長している場合に方向コード「３」に対して論
理「１」を与え、垂直下方向に延長している場合
に方向コード「４」に対して論理「１」を与える
ようにしている。

第９図は、第７図図示の直接接触直線成分抽出
処理部６による処理結果の一例を示している。

今仮にベクトル図形５が第９図Ａに対応するも
のであつたとし、論理回路ブロツク・パターン１
に直接接しているワイヤリング・パターン２の直
線成分が太線で示す図示，，……の如く抽出
されたとする。この場合、テーブルの形に記述し
たベクトル図形５は、第９図Ｂ図示の如く対応づ
けられている。なお第９図Ｂにおける「線分」
，，……は第９図Ａの直線成分（直接接触直
線成分）に対応し、「スタートADD」は当該直線
成分の始端点の座標に対応し、それに続く「連結
コード」は当該始端点の連結コードを表わしてい
る。また「エンドADD」は当該直線成分の終端
点の座標に対応し、それに続く「連結コード」は
当該終端点の連結コードを表わしている。更に図
示「左辺」は左辺コードであつて論理「１」の場
合には当該直線成分が論理回路ブロツク１の左辺
に接していることを意味し、「右辺」は右辺コー
ドであつて論理「１」の場合には当該直線成分が
論理回路ブロツク１の右辺に接していることを意
味する。

例えば直線成分についてみるに、当該成分
の始端点（x₁，y₁）は垂直上方向に直線成分が存
在しないことから連結コード「1011」が与えら
れ、終端点（x₁′，y₁′）は水平左方向に成分が存
在しないことから連結コード「0111」が与えら
れ、論理回路ブロツク・パターン１の左辺に接し
ていることから左辺コードに論理「１」が与えら
れている。

以下、本明細書においては、第９図図示の結果
が既に得られているものとして、それ以降につい
て具体的に説明する。

第１０図は、第７図に示すワイヤリング・パタ
ーン・ラベル化処理部７とラベル修正処理部８と
の処理をフローチヤートの形で表わした説明図で
あり、処理は図示の場合全体として処理〔〕段
階と処理〔〕段階と処理〔〕段階との３つの
段階に分けて行なわれる。

処理〔〕は、第９図Ｂ図示の如く、論理回路
ブロツク・パターン１の左辺の直接接する直線成
分に或るラベルを与え、当該直線成分に連結され
る他の直線成分に対してラベルを付与してゆく。
そしてその上でラベルの修正を行なう。

次いで処理〔〕は、第９図Ｂ図示のベクトル
図形５上で論理回路ブロツク・パターン１の左辺
または右辺のいずれにも直接接してなくかつ端点
の連結コードが「1000」から「0100」か「0010」
か「0001」かをもつ直線成分（第９図Ｂ上には図
示されていない―例えば第２図においてで示す
端点をもつ直線成分）を抽出し、当該成分に或る
コードを与え、当該直線成分に連結される他の直
線成分に対してラベルを付与してゆく。その上
で、更に第９図Ｂ図示如く、論理回路ブロツク・
パターン１の右辺に直接接する直線成分に或るラ
ベルを与え、当該直線成分に連結される他の直線
成分に対してラベルを付与してゆく。そしてラベ
ルの修正を行なう。

次いでＴ分岐によつてラベル化が行なわれなか
つた直線成分について、ラベル化を行なう。

第１１図は、第７図図示のワイヤリング・パタ
ーン・ラベル化処理部７の一実施例を示す。

今第９図に示す如きベクトル図形５が、第１１
図ＡまたはＢ図示の如きものであつたとする。こ
の場合、ベクトル図形５から判る如く、直線成分
，，が論理回路ブロツク・パターン１の左
辺と直接接している（左辺コード論理「１」）。こ
のベクトル図形５について、第１１図Ｃ図示の如
く左辺コードが論理「１」をもつ直線成分を抽出
する（なお第１１図Ｃ中の空欄は記述を省略され
ているものである）。このとき抽出された直線成
分，，に対して、第１１図Ｃ図示の如く、
ラベルを順に「１」，「２」，「３」と付与する。

そして、第１０図図示処理〔〕に示す垂直方
向処理と水平方向処理とによつて、ラベルを付与
された成分に対して垂直方向に連結されている他
の直線成分を抽出して同じラベルを与え、次にそ
の直線成分に対して水平方向に連結されている他
の直線成分を抽出して同じラベルを与え、更にそ
の直線成分に対して垂直方向に連結されている他
の直線成分を抽出して同じラベルを与え、……て
ゆく。この間の処理はラベルを既に付与された成
分やＴ分岐に達すると停止する。

第１１図図示の直線成分，，についてみ
ると、１回目の垂直方向処理において、第１１図
Ｄ図示の如く、成分についてラベル「１」や付
与され、成分についてラベル「２」が付与さ
れ、成分についてラベル「３」が付与される。
そして、次の水平方向処理において、第１１図Ｅ
図示の如く、成分についてラベル「２」が付与
される。

第１２図は、第１０図図示の処理〔〕におけ
る垂直方向処理に対応する一実施例回路を示す。
図中の符号１０，１１は夫々ナンド回路、１２な
いし２１は夫々アンド回路、２２，２３は夫々オ
ア回路、２４はラベル化部であつて例えば第１１
図Ｃ図示のベクトル図形５において「ラベル」欄
に所望のラベルＬを記述するようにするものを表
わしている。そして図中「ｉ連結コード」は処理
対象直線成分の始端点連結コード、「i′連結コー
ド」は同じく終端点連結コード、ｘ_i，ｙ_iは同じ
く始端点座標、ｘ_i′，ｙ_i′は同じく終端点座標、
ラベルＬは当該処理対象直線成分が連結されてい
るラベル付与済み直線成分のベル、ｘ_L，ｙ_Lは当
該ラベル付与済み直線成分の始端点座標、ｘ_L′，
ｙ_L′は同じく終端点座標を表わしている。説明を
省略するが、図示信号ａは処理対象象直線成分の
端点がＴ分岐点でないことを表わし、図示信号ｂ
はラベル付与済み直線成分に対して処理対象直線
成分が垂直であることを表わし、図示信号Ｃはラ
ベル付与済み直線成分がラベル・セツト済みであ
ることを表わしている。そして、アンド回路２１
がオンされたことにもとづいて、処理対象直線成
分に対してラベル付与済み直線成分のラベルと同
じラベルＬが付与される。なお、水平方向処理に
当つては、入力の座標ｘとｙとを交換すればよく
同一回路構成を用いることができ、第１０図図示
の処理〔〕における垂直方向処理や水平方向処
理においても同様である。

第１３図は、第７図図示のラベル修正処理部８
の一実施例を示す。第７図図示のラベル付け処理
部８までの処理によつて得られた結果のベクトル
図形５が第１３図ＡまたはＢ図示のものであつた
とする。即ち、第１３図Ａを見ると判る如く、成
分，に対してラベル「１」が付与され、成分
，，に対してラベル「２」が付与され、成
分，に対してラベル「３」が付与されている
とする。この場合、成分，，，，は１
つのワイヤリング・パターンに属するものであ
り、本来同一ラベルを付与されるべきものであ
る。第１３図図示のラベル修正処理部８は、この
修正処理を行ない、１つの直線成分の両端に夫々
連結される直線成分のラベルが異なる直線成分を
抽出する。図示の場合、成分を抽出し、例えば
成分に対するラベル「２」を成分のラベル
「３」に修正し、以下順次ラベルの修正を行なつ
て、第１３図Ｃ図示の如きベクトル図形を得る。
図示の場合、ラベル「２」がラベル「３」に修正
されている。

次いで、第１０図図示の処理部〔〕に入り、
当該時点でラベル付与が終了していないワイヤリ
ングパターンの直線成分であつて連結コードが
「1000」か「0100」か「0010」か「0001」かをも
つ成分を抽出して、ラベルを付与する。そして、
上記と同様に垂直方向処理と水平方向処理とを行
なう。そして次に論理回路ブロツク・パターンの
右辺に直接接している末ラベルの直線成分を抽出
し、ラベルを付与して、垂直方向処理と水平方向
処理とを行なう。更にこの上で、上記第１３図を
参照して説明した如きラベル修正処理を行なう。

その後、第１０図図示の処理〔〕に入り、第
１２図の回路図から判る如く、Ｔ分岐が存在する
とラベル化処理が停止されることから、１つのＴ
分岐と他のＴ分岐との間に存在する直線成分はラ
ベル化処理が行なわれないことが生じている。こ
のためそのような直線成分について新しくラベル
を付与してゆく。

第１４図ないし第２０図は、第１０図図示の処
理〔〕、〔〕、〔〕を行なつた場合の処理の態
様を表わしている。なお第１４図は処理〔〕に
おける論理回路ブロツクの左辺に直接接している
直線成分に対してラベル「１」ないし「38」を付
与した段階を示す。第１５図は第１４図図示の状
態に対して１回目の垂直方向処理を行なつた段階
を示す。第１６図は第１０図図示の処理〔〕に
おけるラベルの修正を行なう直前の段階を示し、
ラベル「13」と「30」とが競合している。第１７
図は第１６図図示の状態に対してラベルの修正を
行なつた段階を示す。第１８図は第１０図図示の
「端点」に対してラベル付けを行なつた上で垂直
方向処理と水平方向処理とを行なつた段階を示
す。第１９図は第１０図図示処理の論理回路ブロ
ツク・パターンの右辺に直接接する直線成分にラ
ベル付けを行なつた上で垂直方向処理と水平方向
処理とを行なつた段階を示す。第２０図は第１０
図図示の処理〔〕を行なつた段階を示す。

第７図図示のラベル修正処理部８までの処理に
おいて、第１４図ないし第２０図に示した如きラ
ベル付け処理とラベル修正処理とが行なわれる。
しかし、このままでは特に第２０図に示した如く
Ｔ分岐で挾まれる部分の直線成分に典型的に現わ
れるように、本来他のラベルに統合されるべきも
のが末統合のまま残ることとなる。

第２１図ＡおよびＢは夫々このような未統合ラ
ベルとその処理態様とを表わした説明図であり、
第２１図Ａ図示の場合にはラベル「１」、「２」、
「３」、「４」、「５」、をもつ成分に後述する如く連
結ラベル〓を付与してゆき、当該連結ラベルをも
つ成分に同一のラベル例えば「６」を付与するよ
うにする。第２１図Ｂ図示の場合も同様である。

第２２図は、第７図図示のラベル統合化処理部
９の一実施例をフローチヤートの形で示したもの
で、処理〔〕と〔〕と〔〕との多段階にわ
けて統合化処理が行なわれる。なお処理〔〕は
第２１図Ａに対応する処理であり、処理〔〕は
第２１図Ｂに対応する処理と考えてよい。また処
理〔〕は全体的なラベルの統合処理を行なう。

処理〔〕の場合、まずＴ分岐（T₁とする）
をもつ成分を抽出して当該成分に連結ラベルＫを
設定する。そして、当該成分に連結されていて当
該成分と同じラベル（第７図図示ラベル修正処理
部８までに付与したラベル）をもつ直線成分をた
どつてゆき、次にＴ分岐を検出したとき当該Ｔ分
岐をT₂とする。そして２つのＴ分岐間（T₁―
T₂）に存在する成分のすべてに対して、上記設定
した連結ラベルＫを共通に設定する。次いで上記
Ｔ分岐T₁とT₂とに連結される直線成分について
上記と同じ連結ラベルＫを設定する。この状態で
Ｔ分岐をもつて連結される成分間で互に異なる連
結ラベルをもつことが生じるが、当該相互の連結
ラベルを１つに統合する。

処理〔〕の場合、上記処理〔〕が終了した
段階で、上記連結ラベルが設定されていないＴ分
岐を有する成分を抽出し、１つの成分に連結ラベ
ルＫを設定する。

そして処理〔〕において、Ｔ分岐をもつて連
結される成分間で互に異なる連結ラベルをもつ場
合、これらを共通の連結ラベルに統合する。

第２３図は、第２２図に示す処理〔〕の一実
施例を示す。第７図図示のラベル修正処理部８ま
での処理結果のベクトル図形５が第２３図Ａに示
すものであるとき、例えば第２３図Ａ図示の太線
成分，を抽出して、夫々に連結ラベル〓と〓
とを設定する。次いで当該成分ととに夫々連
結される成分に対して、第２３図Ｂ図示の如く、
連結ラベルを設定する。

次いで、図示の場合成分のＴ分岐点に注目し
て、第２３図Ｃ図示の如く連結ラベル〓と〓とを
１つに統合する。

第２４図は第７図図示のラベル統合化処理部９
による処理対象部分を太線と×印とで表わしたも
のであり、第２５図は第２４図図示の処理対象部
分に設定した連結ラベルを表わしている。

以上説明した如く、本発明によれば、ワイヤリ
ング・パターンの直線成分について、電気的に接
続されるべきもの毎に夫々異なつたラベルを附与
してゆくことができ、デザイン・オートメーシヨ
ン・システムによる設定のために有効な入力情報
を抽出することが可能となる。

【図面の簡単な説明】

第１図は本発明の処理対象となる原図形、第２
図は第１図図示の原図形からワイヤリング・パタ
ーンに属する直線成分を抽出した状態を表わす説
明図、第３図は互に連結される直線成分を説明す
る説明図、第４図は本発明にいうラベルの統合化
を説明する説明図、第５図および第６図は本発明
にいう描画規則の一例を説明する説明図、第７図
は本発明の一実施例全体構成図、第８図は本発明
にいう連結コードを説明する説明図、第９図は第
７図図示の直接接触直線成分抽出処理部６による
処理結果の一例、第１０図は第７図図示のワイヤ
リング・パターン・ラベル化処理部７とラベル修
正処理部８との処理をフローチヤートの形で表わ
した説明図、第１１図は第７図図示のワイヤリン
グ・パターン・ラベル化処理部７の一実施例、第
１２図は第１０図図示の処理〔〕における垂直
方向処理に対応する一実施例回路、第１３図は第
７図図示のラベル修正処理部８の一実施例、第１
４図ないし第２０図は第１０図図示の処理
〔〕、〔〕、〔〕を行なう場合の処理の態様、
第２１図は未統合ラベルとその処理態様とを表わ
した説明図、第２２図は第７図図示のラベル統合
化処理部９の一実施例をフローチヤートの形で示
したもの、第２３図は第２２図に示す処理〔〕
の一実施例、第２４図および第２５図は第７図図
示のラベル統合化処理部９による処理態様を説明
する説明図を表わす。図中の符号１はブロツク・パターン、２はワイ
ヤリング・パターン、３はメツシユ、５はベクト
ル図形、６は直接接触直線成分抽出処理部、７は
ワイヤリング・パターン・ラベル付け処理部、８
はラベル修正処理部、９はラベル統合化処理部を
表わす。

Claims

【特許請求の範囲】１予め定められたメツシユ上に描かれたブロツ
ク・パターンと当該ブロツク・パターンに交差す
るワイヤリング・パターンとが上・下・左・右の
直線成分によつて形成された原図形から当該原図
形上の各直線成分について始端点座標と終端点座
標とを抽出し、該抽出された原図形直線座標情報
にもとづいて上記原図形に存在する上記ブロツ
ク・パターンと上記ワイヤリング・パターンとを
データ処理装置への入力情報として抽出する図形
処理システムにおいて、Ａ上記ブロツク・パターンに直接接するワイヤ
リング・パターンの直接接触直線成分が抽出さ
れかつ当該直線成分についての上記始端点およ
び／または上記終端点における連結状態を表わ
す連結コードが抽出されている状態のもとで、
上記抽出されている各直接接触直線成分から上
記連結コードにもとづいて当該直接接触直線成
分に連結されるワイヤリング・パターンの直線
成分に当該直接接触直線成分と同一ラベルを附
与してゆくワイヤリング・パターン・ラベル付
け処理部、Ｂ上記ワイヤリング・パターン・ラベル付け処
理部によつてラベル付けされたワイヤリング・
パターンについて、互に連結されている直線成
分相互で異なつたラベルが附与されているもの
を抽出し、かつ当該互に連結している直線成分
に同一ラベルを附与し替えて、順次ラベルを統
一化するラベル修正処理部、Ｃおよび上記ラベル修正処理部によつて修正さ
れた結果に対して、Ｔ分岐をもつ直線成分であ
つて当該直線成分の両端に連結されている他の
直線成分に対して互に異なつたラベル付けをさ
れるものを抽出し、当該直線成分の両端に連結
されている上記他の直線成分に対するラベルを
統一化するラベル統合化処理部、をそなえ、互に電気的に接続されるべきワイヤリ
ング・パターンに対して同一のラベルを付与して
各ワイヤリング・パターン相互を区別して抽出す
るようにしたことを特徴とするパターン分離識別
化処理方式。