JPS594709B2

JPS594709B2 - パタ−ン発生装置

Info

Publication number: JPS594709B2
Application number: JP52007747A
Authority: JP
Inventors: 利満浜田; 啓一岡本; 誠治柏岡
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1977-01-28
Filing date: 1977-01-28
Publication date: 1984-01-31
Also published as: JPS5394132A

Description

【発明の詳細な説明】３０本発明は、各走査線上における長方形パターンある
いは長方形領域の開始点、終了点の位置座標を簡単な演
算処理で求め、これにより得られた位置座標にもとづき
、長方形パターンあるいは長方形領域を二次元平面上に
発生させるようにしたパ３５ターン発生装置に関するも
のである。

従来より長方形パターンあるいは長方形領域（以下、単
に長方形パターンと称す）を二次元平′Ｒ３−面上に発
生させることは行なわれているが、これによると各走査
線上における位置座標を指定するのに容量大のレジスタ
等の記憶手段を要するという欠点がある。

第１図は、従来のパターン発生方法を説明するためのも
のである。

図示のように、従来は長方形パターンが存在する走査線
領域Ｙ１〜Ｙ２における各走査線上において、長方形パ
ターンの開始する位置座標Ｘ８ｌ〜ＸＳｌｌと、終了す
る位置座標Ｘｅｌ〜Ｘ８ｌｌとを一般に指定する必要が
あり、これがためにこれらの位置座標Ｘ８ｌ〜ＸＳｌｌ
，Ｘ８ｌ〜Ｘ８ｌｌを記憶するために記憶手段が要され
ているのである．この記憶手段の容量は長方形パターン
が走査線に対して特殊な位置状態、即ち、長方形パター
ンの４辺が各走査線に対して直交または平行である場合
は別として、一般にはその４辺は直交または平行ではな
いと考えなければならないからである。しかし、このよ
うに考えると、一般には長方形パターンの存在する走査
線領域Ｙ１〜Ｙ２め指定の他に、一般にこの領域Ｙ１〜
Ｙ２内に存する殆ど全ての走査線に対し、その長方形パ
ターンの開始する位置座標Ｘ８ｌ〜Ｘ８ｌｌと終了する
位置座標Ｘ８ｌ〜Ｘｅｌｌとを指定する必要があり、こ
のために必然的に記憶手段の容量増大を招いているので
ある。本発明は、以上説明したように従来必要とされて
いた位置座標指定のための記憶手段容量を解消あるいは
軽減するように、長方形パターンが存在する各走査線上
における開始または終了の位置座標の殆どを簡単な演算
により求め、しかも長方形パターンの傾きが４５に付近
より小さいか大きいかによつて第２及び第３の頂点の判
定座標データを切換え、高精度に所望の長方形パターン
を発生させることを目的とするものである。

本発明の特徴は、長方形パターンの各頂点の位置座標デ
ータＸｌ，Ｙｌ，Ｙ２，Ｘ３，Ｙ３と走査線に対して長
方形パターンの特定辺のなす角度Ａが４５し付近より小
さいか大きいかを区別する角度区別情報と、上記角度Ａ
に対応する余接・正接のデータ（ＣＯｔＡ．ｔａｎＡ）
とを指定し、この指定された長方形パターンの最初の頂
点と最後の頂点との走査線位置座標区間において、走査
線上の長方形パターンの開始点Ｘｓ及び終了点Ｘｅの位
置座標を、上記指定された最初の頂点の走査線上の位置
座標Ｘｌ，Ｙｌとした後、上記開始点及び終了点の位置
座標Ｘｓ，Ｘｅを走査線信号が発生する毎に、演算手段
で上記指定された余接・正接のデータを遂次減算・加算
していつて求め、更に上記指定された角度区別情報が４
５て付近より小さいとき長方形パターンの第２の頂点に
おける走査線上の座標Ｘ３と第３の頂点における走査線
の座標Ｙ３とで判定し、または上記指定された角度区別
情報が４５定付近より大きいとき長方形パターンの第２
の頂点における走査線の座標Ｙ３と第３の頂点における
走査線上の座標Ｘ３とで判定し、これら余接・正接のデ
ータ及び減算・加算を切換えて上記開始点及び終了点の
位置座標Ｘｓ，Ｘｅを、走査線信号が発生する毎に、演
算手段で上記指定された正接・余接のデータを遂次加算
・減算していつて最後の頂点Ｙ２まで求め、これら求め
られた位置座標により、２次元的走査の基準となる走査
線信号と走査位置信号とに同期させて走査線と傾斜した
長方形パターンに相当する信号を発生させることである
。

以下、本発明を第２図から第１１図により説明する。

先ず、第２図から第４図では、各長方形パターンの典型
例を示したものである。

第２図における長方形パターンＸは、その４辺が走査線
と直交または平行の場合を示したものであるが、この場
合は明らかに長方形パターンＸの存在する走査線領域Ｙ
１〜Ｙ２内の全走査線に対し、開始位置座標Ｘ１、終了
位置座標Ｘ２は全て同一である。したがつて、走査線に
対してこのような関係にある長方形パターンに対しては
、長方形パターンの存在が開始する走査線Ｙ１、終了す
る走査線Ｙ２の位置座標の他、走査線Ｙ１上における開
始位置座標Ｘ１、終了位置座標Ｘ２が与えられれば、こ
のような長方形パターンは発生されることが容易である
。しかし、第３図、第４図々示のような？方形パターン
Ｙ，ｚは、第２図の場合と異なり、走査線領域Ｙ１〜Ｙ
２内の走査線とはその４辺が直交または平行ではなく、
特定の辺に対しては一定の角度Ａ（＼０）を有するもの
である。このような長方形パターンの発生を特定するた
めに、本発明はミ位置座標Ｘ！１Ｘ３，Ｙ１？Ｙ２ｙＹ
３を指定することにより行なうようにしている。更にＡ
が００である場合、即ち、第２図々示のような長方形パ
タ一ンと区別する意味で１ビツトの制御情報を付加指定
する他、角度Ａが４５ツ以上の場合（４５加〈Ａ〈９０
）（第３図）と４５上未満の場合（００くＡ〈４５（）
（第４図）の場合とでは、ある走査線上での位置座標Ｘ
３、走査線Ｙ３の指定位置が走査線上において異なるの
で、これを区別するための１ビツト制御情報を指定して
いる。このような指定方法を採れば、第３図、第４図の
場合、走査開始の走査線Ｙ１上の位置座標Ｘ１を基準に
して、走査線領域Ｙ１〜Ｙ２における全走査線に対する
長方形パターンＸ，ｙの開始、終了の各位置座標は全て
三角関数手段により求められる。

即ち、第３図の場合、走査線間隔を単位長さとして、走
査線領域Ｙ１〜Ｙ３内での走査線変化に対する開始位置
座標の変化量は、１つ前の走査線に対して−ＣＯｔＡで
あり、ＣＯｔＡだけ減少させられる。また、走査線領域
Ｙ３〜Ｙ２においては、走査線Ｙ３上における開始位置
座標を基準にして、走査線変化に対する変化量は１つ前
の走査線に対してＴａｎＡだけ増加するので、ＴａｎＡ
である。同様にして、終了位置座標の変化は、終了位置
座標Ｘ１〜Ｘ３間では、ＴａｎＡであり、また終了位置
座標Ｘ３から走査線Ｙ２に至るまでは−ＣＯｔＡと表す
ことができる。このような変化量は、第４図においても
全く同様に考えることができ、開始または終了の位置座
標が走査線上で変化する割合は、−ＣＯｔＡまたはＴａ
ｎＡと表わすことができるのである。第３図、第４図に
おいて、長方形パターンＹ，Ｚの各頂点に対応する点は
、走査線Ｙ１上での位置座標Ｘ１は別としてある走査線
上での位置座標が与えられるか、または走査線の位置座
標が与えられることにより指定されるようにしている。
即ち長方形パターンＹ，ｚにおいて最初に走査線にかか
る頂点には走査線Ｙ１と位置座標Ｘ１を与え、走査線か
らはずれる頂点には走査線Ｙ２を与え、第５図にＰ３，
Ｐ４で示す如くＹ方向に変化なく、Ｘ方向に変化する頂
点には位置座標Ｘ３を与え、第５図にＰｌ，Ｐ２で示す
如くＸ方向に変化なく、Ｙ方向に変化する頂点には走査
線Ｙ３を与える。以上説明したように、走査線に直交ま
たは平行ではない４辺を有する長方形パターンは、走査
線との角度状態が予め知ることができれば、第３図第４
図のように走査線上での長方形パターンの開始、終了の
位置座標は１つ前の走査線に比して、ＴａｎＡまたは−
ＣＯｔＡ変化することにより容易に求められる。しかし
、このためには、予めＴａｎＡｌ一ＣＯｔＡを小数点を
含んだ２進数値としてメモリに記憶しておき、角度Ａの
指定はメモリ上のアドレスとしてインデツクスを指定す
ることにより行ない、インデツクス値によりＴａｎＡ．
ｃＯｔＡの値がメモリから読み出されるようにしている
。したがつて、このＴａｎＡ，−ＣＯｔＡの値を基準と
なるべき走査線上の位置座標、即ち、第３図、第４図の
場合、走査線Ｙ１上の位置座標Ｘ１に加算すればよいこ
とが判る。第６図は、このような加算を模式的に表わし
たものである。この図は、ある走査線上での長方形パタ
ーンの開始または終了の位置座標の値ＸｓｎまたはＸ。
ｎは、その走査線の１つ前の走査線上での位置座標の値
Ｘ８ｎ−，またはＸ８ｎ−，にＴａｎＡまたは−ＣＯｔ
Ａを加算すれば得られることを示している。したがつて
、また、この値ＸｓｎまたはＸｅｎにＴａｎＡまたは−
ＣＯｔＡを加算すれば、次に走査される走査線上での位
置座標Ｘ８ｎ＋１またはＸ８ｎ＋１が得られることは明
らかであろう。この加算演算は、小数点（△印）を含む
２進数値でされることは既に述べたところであるが、実
際には目的とする走査線上での位置座標は整数化される
必要がある。これは、位置座標が画一的に量子化されて
いるからである。したがつて、小数点を含むものとして
得られた位置座標のその小数点以下の数値は場合により
切捨てられ、切り土げされ、または四捨五入されること
になる。第８図から第１１図までは、本発明の実施例を
説明するためのものであるが、第１０図、第１１図の詳
細な説明の前に、基本的な人出力信号を説明しておく。
先ず、第７図は、現に走査されている走査線位置座標と
その走査線上における走査位置座標とが発生されるよう
にしたものである。

基本クロツク４８が座標発生器４９に入力されると、発
生器４９内部に含まれる二段構成のカウンタ手段により
分周され、その二段構成のカウンタ手段のうち、後段の
ものの出力が走査線位置座標３を、また、前段のものの
出力は走査位置座標２１を表示出力するようにされてい
る。但し、このような構成は、特に新規なものではない
。次に、第８図は、第７図で発生されている走査線位置
座標３と、指定された走査線位置座標１，２とに基づい
て、実際に長方形パターンが走査発生中であることの表
示信号８が出力されるようにしたものである。

この場合の走査線位置座標１，２は第２図から第４図に
おける走査線Ｙｌ，Ｙ２の位置座標にそれぞれ対応する
ものである。走査線位置座標３が刻々に変化し、位置座
標１に一致すると、長方形パターンの走査を開始すべき
ことを表示する出力４が比較回路６より判定回路９に出
力されるが、この出力４によりフリツプフロツプなどの
判定回路９は出力状態が反転される。しかし、この反転
状態は、走査線位置座標３が位置座標２に一致するまで
、続行され、位置座標２に一致すると比較回路７より走
査を終了すべきことを表示する出力５が判定回路９に出
力される結果、再び反転される。即ち、判定回路９の出
力信号８は、長方形パターンが発生されるべき走査線領
域Ｙ１〜Ｙ２が実際に走査されている間のみ、出力され
るものである。最後に、第９図であるが、これは、目的
とする角度Ａに対するＴａｎＡ、−ＣＯｔＡの値を出力
するためのものである。

メモリ１４には、０値〈Ａ〈９０のの範囲にある角度Ａ
に対し、ＴａｎＡ、一ＣＯｔＡの値が記憶されているが
、指定された角度Ａを表わすインデツクス値１０が選択
回路１３に人力されると、メモリ１４から指定された角
度Ａに対するＴａｎＡ、−ＣＯｔＡそれぞれの値出力１
１，１２が得られるようになつている。以下、第２図か
ら第３図における長方形パターンＸ，ｙ，ｚに例を採り
、第１０図、第１１図の回路動作を説明する。

第１０図における回路構成は、第２図におけるのみなら
ず、第３図、第４図のような一般的な任意形状の長方形
パターンをも発生させるものである。第２図における長
方形パターンｘの発生は、次のように説明される。

即ち、この場合は第３図、第４図における長方形パター
ンＹ，ｚと区別する意味で、角度Ａが００であるか否か
に基づく１ビツト制御情報１９が選択回路３０に走査線
Ｙ１上における指定された終了位置座標１６（Ｘ２）を
選択させるとともに、加算回路２７，３４の加算動作を
抑えるので、開始、終了用のそれぞれのレジスタ２４，
３１には、走査線Ｙ１上の開始、終了のそれぞれの位置
座標１５（Ｘ１），１６（Ｘ２）がセツトされている。
これらの位置座標１５（Ｘ１），１６（Ｘ２）は走査線
領域Ｙ１〜Ｙ２内の全走査線に亘つて常に一定であるか
ら、加算回路２４，３４は動作される必要が全くない。
したがつて、レジスタ２４，３１の出力は切上回路２５
、切捨回路３２を介し比較回路２６，３３に入力されて
いる。このような状態で、走査が開始されると走査線位
置座標３と走査位置座標２１とに刻々変化し、走査線位
置座標３が走査線領域Ｙ１〜Ｙ２内にある間は、出力信
号８が出力されることは既に述べたところである。この
出力信号８は判定回路４５に人力されて、判定回路４４
からの出力４６をゲート制御する機能を有するものであ
る。一方、比較回路２６，３３は走査位置座標２１と切
上回路２５、切捨回路３２のそれぞれの出力４０，４１
とを比較しているので、走査線領域Ｙ１〜Ｙ２内外の全
走査線に対し、走査位置座標２１が位置座標１５（Ｘ１
），１６（Ｘ２）に一致する度に一致出力２２，２３を
出力する。

このため、一致出力２２，２３が入力されている判定回
路４４は、位置座標１５（Ｘ１）の出力時点より位置座
標１６（Ｘ２）が出力されるまで間出力４６を出力する
としても、その出力４６のうち、出力信号８が出力され
ている間のもののみが判定回路４５の出力４７となる。
即ち、出力４７は、長方形パターンｘのパターン出力と
なるものであることが判る。次に、第３図における長方
形パターンｙの発生を考える。

この場合は、１ビツト制御情報１９は長方形パターンｙ
の角度Ａは００でないので、選択回路３０に位置座標１
５（Ｘ１）を選択させ、加算回路２７，３４を出力信号
８が出力されている間のみ、加算動作可能にしている。
また角度Ａが４５み以上なので、１ビツト制御情報２０
は選択回路２９に比較回路３７の出力４２を選択させる
ことにより選択回路２８に値出力１２（−ＣＯｔＡ）を
選択させるとともに、選択回路３６に比較回路３８の出
力を選択させることにより選択回路３５に値出力１１（
ＴａｎＡ）を選択させている。更に１ビツト制御情報２
０は選択回路３９に切捨回路３２の出力４１を選択させ
ている。この状態では、レジスタ２４，３１に何れも位
置座標１５（Ｘ１）がセツトされているが、この状態で
走査が開始されると、走査が走査線Ｙ１に一致すること
により出力信号８が出力される。しかして、この出力信
号８が出力されると、加算回路２７，３４は走査線Ｙ１
の走査終了時点より走査線Ｙ２に至るまでの間、走査線
が変わる毎に加算動作を行なうのである。この場合、加
算回路２７では値出力（−ＣＯｔＡ）をレジスタ２４内
の位置座標１５（Ｘ１）に加算し、この力目算結果（Ｘ
１−ＣＯｔＡ）をレジスタ２４にセツトし、走査線が変
化する度に、そのレジスタ２４の値はＸ１からｘ１−Ｃ
ＯｔＡ、Ｘ１−２ｃ０ｔＡ．Ｘ１−３ｃ０ｔＡ、・・・
・・・、と変化する。

また、一方の加算回路３４では、レジスタ３１には同様
に走査線が変化する度にその値はＸ１よりＸ１＋Ｔａｎ
Ａ，．Ｘ，＋２ｔａｎＡ，．Ｘ１＋３ｔａｎＡ１・・・
・・・、と変化するのである。レジスタ２４，３１の値
はこの間、切上回路２５、切捨回路３２を介して整数化
された後、比較回路２６，３３で走査位置座標２１と比
較され、既に述べたようにして長方形パターンｙのパタ
ーン出力は判定回路４５より取り出される。しかし、レ
ジスタ３１の値は、既に述べたように走査線が変わる度
にその値は増加する傾向にあり、その値を切捨回路３２
の出力４１の側よりみたとき、位置座標１７（Ｘ３）に
一致する走査線位置がある筈である。

このような走査線位置に走査が至れば、切捨回路３２の
出力４１は選択回路３９を介して比較回路３８で位置座
標１７（Ｘ３）と比較され、一致出力が得られる。こＯ
一致出力は、選択回路３６を介して選択回路３５に以後
値出力１２（−ＣＯｔＡ）を選択させ、位置座標１７（
Ｘ３）よりも僅かに大きい近傍の値を基準にしてレジス
タ３１の値は減少されるようになる。また、更に走査が
進み、走査位置座標３が走査線Ｙ３の位置座標１８に一
致すると、比較回路３７での一致出力４２が選択回路２
９を介して選択回路２８にそれまでの値出力１２（−Ｃ
ＯｔＡ）に代わつて値出力１１（ＴａｎＡ）を選択させ
、レジスタ２４の値は、走査線が変わる度に増加される
ようになる。このようにして走査が進み、走査線位置座
標３が走査線Ｙ２の位置座標２に一致すれば、出力信号
８は出力されなくなる。

したがつて、判定回路４５の出力４７には出力信号８が
出力されている間のみ、長方形パターンｙのパターン出
力が得られることになる。最後に第４図における長方形
パターンＺの発生を考えると、この長方形パターンｚの
発生は、第３図の場合より容易に考えられるものである
。

即ち、レジスタ２４，３１には第３図と同様に位置座標
１５（Ｘ１）がセツトされた状態で走査が開始されるが
、選択回路２８，３５による値出力１１（ＴａｎＡ），
１２（−ＣＯｔＡ）の選択順序は同じであるとしても、
その選択のされかたが異る。これは、１ビツト制御情報
２０が第３図の場合と制御状態が異なるからである。選
択回路２８は、初めは値出力１２（−ＣＯｔＡ）を選択
しているが、レジスタ２４の値が位置座標１７（Ｘ３）
近くになると値出力１１（ＴａｎＡ）を選択するように
なり、また選択回路３５は、初めは値出力１１（Ｔａｎ
Ａ）を選択しているが走査線位置座標３が走査線Ｙ３の
位置座標１８に一致すると、以後は値出力（−ＣＯｔＡ
）を選択するようになるのである。この他の動作は、１
ビツト制御情報２０によるものを除けば、第３図の場合
と全く同様となることは明らかであろう。以上、詳細に
説明したように本発明によれば、走査線上の長方形パタ
ーンの開始点及び終了点の位置座標Ｘｓ，Ｘｅを、長方
形パターンの各頂点の位置座標データＸｌ，Ｙｌ，Ｙ２
，Ｘ３，Ｙ３に基いて走査線に対して長方形パターンの
特定辺のなす角度Ａに対応する余接・正接のデータＣＯ
ｔＡ，ｔａｎＡを走査に同期させて少数のレジスタと加
算回路からなる演算手段で遂次減算・加算Ｌ２ていつて
求め、上記角度Ａが４５次付近より小さいとき第２の頂
点においては走査線上の座標Ｘ２、第３の頂点において
は走査線の座標Ｙ３で判定し、上記角度Ａが４５は付近
より大きいとき第２の頂点においては走査線の座標Ｙ３
、第３の頂点においては走査線上の座標Ｘ３で判定し、
これら余接・正接のデータＣＯｔＡ．ｔａｎＡ及び減算
・加算を切換えるようにしたので、メモリ容量を減少さ
せることが出来、しかも長方形パターンの傾き角の変化
に対応させて精度よく長方形パターンを発生させること
ができる効果を奏する。

また本発明によれば傾き角度の異なる長方形や正方形パ
ターンの発生方法を適当に組合せることによつて任意形
状を有する半導体集積回路パターン等を合成することが
可能となり、半導体集積回路パターンなどの自動検査に
おける検査の基準となる標準パターン発生などに応用す
ることができる。更に、２値映像に対して領域を指定し
、領域内のいわゆる論理”１゛を計数することによる自
動検査、位置認識などにも応用可能なものである。

【図面の簡単な説明】

第１図は、従来のパターン発生方法のための説明図、第
２図から第６図は、本発明によるパターン発生方法のた
めの説明図、第７図は、走査線位置座標と走査位置座標
の発生構成図、第８図から第１１図は、本発明のパター
ン発生方法の１実施態様のプロツク図である。１・・・・・・走査開始が指定された走査線（Ｙ１）の
位置座標、２・・・・・・走査終了が指定された走査線
（Ｙ２）の位置座標、３・・・・・・走査線位置情報、
８・・・・・・走査中表示信号、１０・・・・・−イン
デツクス、１１・・・・・・値出力（ＴａｎＡ）、１２
・・・・・・値出力（−ＣＯｔＡ）、１４・・・・・・
メモリ、１５，１６，１７・・・・・・位置座標、１８
・・・・・・走査線（Ｙ３）の位置座標、１９，２０・
・・・・・１ビツト制御情報、２１・・・・・・走査位
置情報、２４，３１・・・・・・レジスタ、２７，３４
・・・・・・加算回路、２６，３３，３７，３８・・・
・・・比較回路、４７・・・・・・パターン出力。

Claims

【特許請求の範囲】１走査していつて最初に走査線に現われる長方形パタ
ーンの頂点を最初の頂点とし、次の走査線に現われる長
方形パターンの頂点を第２の頂点とし、次の走査線に現
われる長方形パターンの頂点を第３の頂点とし、走査線
から消える長方形パターンの頂点を最終の頂点とし、上
記長方形パターンの最初の頂点としては走査線の座標デ
ータ及び走査線上の座標データ、第２の頂点としては走
査線上の座標データ、第３の頂点としては走査線の座標
データ、最後の頂点としては走査線の座標データと、走
査線に対して長方形パターンの特定辺のなす角度が４５
°付近より小さいか大きいかを区別する角度区別情報と
、上記角度に対応する余接・正接のデータとを指定する
指定手段を設け、走査線が長方形パターンの第２、及び
第３の頂点に達したことを第２の頂点における走査線上
の座標、及び第３の頂点における走査線の座標で判定す
る判定手段を設け、上記指定手段で指定された最初の頂
点と最後の頂点との走査線位置座標区間において、走査
線上の長方形パターンの開始点及び終了点の位置座標を
、上記指定された最初の頂点の走査線上の位置座標とし
た後、上記開始点及び終了点の位置座標を走査線信号が
発生する毎に上記指定手段で指定された余接・正接のデ
ータを逐次減算・加算していつて求め、上記判定手段で
判定された信号により、これら余接・正接のデータ及び
減算・加算を切換えて上記開始点及び終了点の位置座標
を走査線信号が発生する毎に上記指定手段で指定された
正接・余接データを逐次加算・減算していつて最後の頂
点まで求める演算手段を設け、該演算手段で求められた
位置座標により、２次元的走査の基準となる走査線信号
と走査位置信号とに同期させて走査線と傾斜した長方形
パターンに相当する信号を発生させることを特徴とする
パターン発生装置。２上記指定手段の内、正接・余接のデータは、メモリ
に記憶させ、インデックス指定により上記メモリに記憶
されたデータを読み出すように構成したことを徴徴とす
る特許請求の範囲第１項記載のパターン発生装置。