JPS634379A - パタ−ンマツチング装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） この発明は、パターンマツチング装置に関する。

（従来の技術） 従来のパターンマツチング装置は、基準パターンと比較
パターンとを記憶する画像メモリと、両メモリの濃淡に
基いて両画像の相互相関係数（実施例中の数式■〜■参
照）を演算するコンピュータ装置とを備えて構成され、
前記相ｎ相関係数が斗分大ぎな値を示づことでパターン
マツチングを検出するものである。

（発明が解決しようとする問題点） しかしながら、従来のパターンマツチング装置は、両画
像メモリを、穫めて微細に形成されたｉ！ｉｉ素単位で
相互に移動させ、都度、前記相互１１汲１係数を演算す
るような構成であったため、演弾処理に極めて多くの時
間を要することになるという問題点があった。

例えば、集積回路を走査型の電子顕微鏡で捉え、該顕微
鏡で得られたデジタル信号を画像メモリ上に記憶してパ
ターンマツチングしようとする場合、画像メモリの画素
数が多大となり、パターンマツチングに多くの時間が必
要となる。

そこで、この発明は、上記問題点を改善し、画像メモリ
の容量が大きくとも、高速処理をすることができるパタ
ーンマツチング装置を提供することを目的とする。

［発明の構成］ （問題点を解決するための手段） 上記目的を達成するためこの発明では、第１図に示すよ
うに、パターンマツチング装置を、基準パターンＰＳと
比較パターンｐｃを原画像として画像メモリに記憶する
基準及び比較画像形成手段１と、前記画像メモリの複数
画素に対応してこれら画素の平均濃度を単位画素上に表
わしたブロック画像を形成するブロック画像形成手段２
と、前記１パターン及び前記比較パターンに対応するブ
ロック画像に相対的に画素単位の変位を与えつつ両画像
を順次重ね合せる第１重ね合ｔ＝ｉｉＩ制御手段と、重
ね合せの毎に相互相関係数を演紳することにより両画像
のパターンマツチングを検出づる巨視的マツチング検出
手段４と、両原画像上で比較的小さな面積の特徴部を指
定する特徴部指定手段５と、両特徴部を相対的に画素単
位の変位を与えつつ両特徴部を順次重ね合せる第２ｆｆ
ｉね合せ制御手段６と、重ね合せに応じて相互相関係数
を演算することにより両特徴部のパターンマツチングを
検出する精密マツチング検出手段７と、を備えて構成し
た。

（作用） この発明では、ブロック画像形成手段２により、原画像
に対し画素数を１／ｎ　　（ｎは原画像とブロック画像
との対応数）に減少させたブロック画素が得られ、第１
重ね合せ制御手段３及び巨視的マツチング検出手段４に
より、従来よりｎ十α倍速い速度でパターンマツチング
が行われる。倍率ｎ＋αにおけるｎは重ね合せ回数を減
少させることができる利得であり、αは演ｎメ簡易なも
のとすることができることによる利得である。

又、この発明では、次いで、特徴部指定手段５により特
徴部が指定され、第２重ね合せ制御手段６及び精密マツ
チング検出手段７により特徴部についての精密マツチン
グが行われるので、マツチング精度の向上を図ることが
できる。

なお、特徴部指定手段５が指定する特徴部の面積は、比
較パターンに応じて任意に定められるものであるが、こ
れは比較的微小面積について行ねれるので特徴部のパタ
ーンマツチングにＷ”Ｊる時間は微小なもので済む、。

（実施例） 以下、添付図面を用いてこの発明の詳細な説明する。

まず、図面についてｎ単に説明づると、第２図はこの発
明の一実施例にかかるパターンマツチング装置ｔ置のブ
ロック図、第３図は原画像の説明図、第４図＜ａ＞及び
第４図（ｂ）は比較パターン及び基準パターンのブロッ
ク画像を示す説明図である。

又、第５図は第１重ね合せ制御手段の作用を示づ説明図
、第６図（ａ）及び第６図（ｂ）は相互相関係数の演口
対象たる２つのブロック画像についての重なり部分のメ
七り状態を糸す説明図である。

更に、第７図は特徴部指定に際して参酌される濃度勾配
の説明図、第８図は特徴部のブロック位置を承り説明図
、第９図は第２重ね合せ制御手段の作用を示す説明図で
ある。

第２図に示すように、パターンマツチング装置は、３つ
つの画像メＵすＭ　１　、　ｆｖｌ　２、〜１３を備え
た画像プロセッサ８で構成されている。

画像メモリＭ１は、基準パターンｐｓを基準パターンの
原ｉｉ！ｉｉ像として記憶するしのである。

画像メモリＭ２は、走査型電子顕微鏡９を介して比較パ
ターンＰｃの画像信号を取り込んで、これを比較パター
ンの原画像として記憶するらのである。

画像メモリＭ３は、画像プロセッサ８のワーキング用エ
リアとして利用されるメモリでおる。

画像プロセッサ８はこれらメモリＭ１．Ｍ２゜Ｍ３を備
えて、第１図に示した各手段１〜７を構成するものであ
る。

以下、画像プロロサ８の行う処理の内容を順を追って説
明する。

まず、第１図に示した基準及び比較画像形成手段１は、
第３図に示すように、前記ｉＴｊ象メセメモリに、基準
パターンＰｓ　　（説明を簡易とするため英文字ｒＦＪ
で示す）の原画像ＥＳを記憶させる。

又、同様に、前記画像メモリＭ２に、比較パターンＰｃ
の原画像ＥＣを記憶させる。

記憶は、各画素に２５６（０〜２５５）の段階の濃度デ
ータを記憶して行われる。ここに、データｒＯＪ　＆よ
黒を、データｒ２５５Ｊは白を意味するものであり、黒
地に白の打ち抜き文字ｒＦＪを示した本例では、画像メ
モリＭｌ　（Ｍ２）には、図示の如くにａ淡データが記
憶されるようになる。

ブロック画像形成手段２は、複数（本例では４とする）
画素ごとの平均濃淡データを弾出し、第４図（ａ）、（
ｂ）に示すように、両象メモリＭ３に原画＠Ｅｓ　　（
Ｅｃ　）の１／４の大ささのブロック画像０ｓ（ｃｃ）
を記憶する。

以上の準備的処理を行った後、第１重ね合せ制手段４ひ
及び巨視的マツチング検出手段４の協動作業により、パ
ターンマツチングが行われる。

第１重ね合せ制御手段３は、第５図に示づように、例え
ば基準パターンのブロック画像ａＳを固定とし、比較パ
ターンのブロック画ｉｅｃを左右、上下に一画素単位で
移動させて行く。

−方、巨視的マツチング検出手段４（よ、第１中ね合せ
制御手段３の各画素中位の移動円に、千４ｒり部分１０
について、相互相関係数ＣＯＲを演口する。

相互相関係数ＣＯＲは、まず、第６図（ａ）　、　（ｂ
）　ニ示すように、各ブロック画像の手なり部分１０ｃ
。

１０ｓについて濃淡データの８行す列の行列（ｕｉｊ）
、（ｖｉｊ）を形成し、行列（ｕｉｊ　）　、　　（ｖ
ｉｊ　＞の平均値を、それぞれｍｕ、　ｍｖ、その標準
偏差をσＵ、σＶとして、次式で求められる。

Ｃ０Ｒ＝　　（１／ａ　　−ｂ　　） ・・・■ ここに、 ＩＪ　　ｉｊ＝　　（ｕｉｊ　　−ｍｕ）　　／ａｕ　
　　　　　　　　　　　　　　　−■Ｖｉｊ＝　（ｖｉ
ｊ　−ｍｖ）　／σ■　　　　　　　・・・■である。

巨視的マツチング検出手段４は、第１重ね合せ手段３の
画素単位の移動制御に合せ、上記相互相関係数を都度演
算し、最大値をもってマッヂグの＠適状態とみなす。

以上により、比較パターンＰｃが基準パターンＰｓと巨
視的に一致することが判明でき、又、第５図に示ザよう
に、このときの座標変位量ΔＸ。

Δｙが求まる。

次に、特徴部指定手段５は、第７図に示すように基準パ
ターンＰｓの原画像ＥＳ又は比較パターンＰｃの原画像
ＥＣについて微分を行って、濃度勾配の行列１１をメモ
リＭ３上に形成する。

配列ｉ、ｊの画素の濃度について濃度勾配をｄｉｊとす
ると、 ｄｉｊ　＝ｄ　Ｐ／ｄｘ＋ｄ　Ｐ／ｄｌ／＝（Ｐ！＋＋
、ｊ−Ｐｉ、ｊ　＞ ＋　（Ｐｉ　、Ｊ、Ｉ　ＰＩ　、Ｊ　）　　　　　・・
・■である。

又、特徴部指定手段５（よ、第７図において濃度勾配が
１００以上となる画素を第８図に示すように抽出し、前
記ブロック画Ｄｅｃ＜又はｅｓ）に対応して、勾配値ｄ
ｉｊが１００以上の部分が占める面積が最大となるブロ
ックＢＬＫＳを特徴部とする。

更に、特徴部指定手段５は、前記座標変位旧ΔＸ、Δｙ
を参酌して他のパターンの原画像ＥＣ（又はＥｓ）上に
、第８図に示したブロックＢしＫに対応する部分を、他
のパターンについての特徴部（ブロックＢＬＫＣと称づ
）に指定する。

そこで、第２重ね合せ制御手段６は、かくして得られた
ブロック８ＬＫｓ　、ＢＬＫｃの一方を他のブロックに
対し、第５図に示したと同様に第９図に示すように画素
ｌ！愉で移動させ、又、精密マッヂング検出手段７は、
この移動に合せて■〜■式に示したと同様の演算を行っ
て精密なパターンマツチングを行う。

パターンマツチングが良好に行われＩＣか否かの判断は
、前記巨視的マツチング検出手段４の検出結果と、前記
精密マッヂンン検出手段７の検出結果を総合すれば良い
のである。

以上により、本実施例では、パターンマツチングが高速
に行すれ、例えば集積回路のパターンマツチングを２〜
３分で行うことが可能となる。

又、パターンマツチを巨視的に、更に、精密に行うので
、より完全なマツチング処理を実行することが可能であ
る。

本例では、特徴部指定手段５は濃度勾配の大きなブロッ
クを１ケ所指定したが、特徴部の指定は例えば、複数部
分について指定するなどパターン種に応じ任意に行われ
て良いものである。

また、本例では、原画像の４画素を１ブロツクとしたが
、この数は６，９，８．１２．１６等他の数であっても
良いこと勿論である。

又、本例では、第９図に示した精密マツチングに、おけ
る画素数を第４図（，１）、（ｂ）及び、第８図に示し
たブロックど同じ大きさで示したが、聞密マツチングは
、指定されたｖｔ徴部に対し、例えば６　（８（拡張円
）、９侶〈拡張角）笠、広領域について行っても良いも
のである。

この発明は以上示した実施例に限定されるものではなく
、この他通貨の設３１的変更を行うことにより、各種の
態様で実施できるものである。

［発明の効果］ 以上の通り、この発明に係るパターンマツチング装置に
よれば、巨視的、微視的にパターンマツチングを行うの
で、画像メモリの容量が大きくとも、高速処理をするこ
とができる。

【図面の簡単な説明】

第１図はこの発明の概要を示す図、第２図ｔよこの発明
の一実施例にかかるパターンマツチング装置のブロック
図、第３図は原画像の説明図、第４図（ａ）及び第４図
（ｂ）は比較パターン及び基準パターンのブロック画像
を示ず説明図、第５図は第１巾ね合せ制御手段の作用を
示す説明図、第６図＜ａ）及び第６図（ｂ）は相互相関
係数の演綽対象たる２つのブロック画像についての重な
り部分のメモリ状態を示す説明図、第７図は特徴部指定
に際して参酌される濃度勾配の説明図、第８図ｔよ特徴
部のブロック位置を示す説明図、第９図は第２重ね合ｔ
！１１−手段の作用を示す説明図である。 １・・・基準及び比較画像形成手段 ２・・・ブロック画像形成手段 ３・・・第１重ね合せ制御手段 ４・・・巨視的マツチング検出手段 ５・・・特徴部指定手段 ６・・・第２重ね合せ制御手段 ７・・・精密マツチング検出手段 ｐｓ・・・基準パターン ｐｃ・・・比較パターン

Claims (1)

【特許請求の範囲】
1. 基準パターンと比較パターンを原画像として画像メモリ
   に記憶する基準及び比較画像形成手段と、前記画像メモ
   リの複数画素に対応してこれら画素の平均濃度を単位画
   素上に表わしたブロック画像を形成するブロック画像形
   成手段と、前記基準パターン及び前記比較パターンに対
   応するブロック画像に相対的に画素単位の変位を与えつ
   つ両画像を順次重ね合せる第１重ね合せ制御手段と、重
   ね合せの毎に相互相関係数を演算することにより両画像
   のパターンマッチングを検出する巨視的マッチング検出
   手段と、両原画像上で比較的小さな面積の特徴部を指定
   する特徴部指定手段と、両特徴部を相対的に画素単位の
   変位を与えつつ両特徴部を順次重ね合せる第２重ね合せ
   制御手段と、重ね合せに応じて相互相関係数を演算する
   ことにより両特徴部のパターンマッチングを検出する精
   密マッチング検出手段と、を備えて構成されるパターン
   マッチング装置。