JPH0514945B2 - - Google Patents

Description

【発明の詳細な説明】 産業上の利用分野 この発明は、たとえば、IC部品を回路基板に
搭載するときに必要となる、撮像装置から得られ
る画像パターン中に存在する特定パターンの位置
を高速に検出する、２次元位置検出方法に使用す
るパターンマツチング方法に関するものである。

従来の技術 従来のパターンマツチングによる位置検出方法
を大別すると、 １ 撮像装置から得た画像パターン１フレーム分
を半導体メモリなどの画像パターン記憶装置に
格納した後、標準パターンとの照合処理を行う
方法。

と、 ２ 撮像装置が走査している位置の座標を発生す
る装置と、標準パターンとのマツチングに必要
な最小限度の容量を持つた、半導体メモリなど
の画像パターン記憶装置によつて、標準パター
ンとの照合処理を画像パターンを取り込みなが
ら行う方法。

の２つに分類できる。

そこでこれら２つのパターンマツチング方法に
ついて、処理速度・処理の拡張性・コストの３項
目について検討してみる。

まず処理高速であるが、第１の方法は画像パタ
ーン１フレーム分を記憶装置に取り込んだ後で照
合処理を行うため、一般的に処理時間を要しリア
ルタイム処理には向いていない。画像パターン１
フレーム分を記憶装置に取り込むのに要する時間
をT_i、記憶装置に取り込まれた１フレーム分の画
像パターンと標準パターンとの照合処理に要する
時間をT_pとすると、第１の方法によるパターン
マツチング要する時間T_n1は、T_iとT_pの和によつ
て(1)式の T_n1＝T_i＋T_p ……(1) ように表わされる。第２の方法は、画像パターン
を取り込みながら、画像パターンを取り込むのに
要する時間で、照合処理を行うため、処理時間は
短くリアルタイム処理に向いている。第２の方法
によるパターンマツチングに要する時間T_n2は、
T_iに等しく(2)式のように表わされる。

T_n2＝T_i ……(2) 次の処理の拡張性について延べる。第１の方法
は撮影装置より得た画像パターンを記憶装置に保
持しているため、標準パターンとの照合処理の前
処理であるフイルタリング等の処理において、オ
ペレータの重みづけを自由に設定したり、照合処
理の終了後、その結果によつて画像パターンの特
定領域をもう一度取り出して確認処理を施すとい
つたこうとが選択的にできる。また照合処理を行
う際にも、照合の基準となる画像パターンと標準
パターンの位置合せ点（以下照合基準点と呼ぶ）
を、撮像装置の走査する方向と直角の方向に走査
させることも可能である。第２の方法においても
フイルタリング等の前処理や照合処理後の確認処
理は可能であるが、前処理に関しては固定でフイ
ルタリング時のオペレータの重みなどを容易に変
更することはできないし、また照合処理後の確認
処理も照合結果を得た同一画面に対して行うこと
はできない。

最後にこれら２つの方法によつてパターンマツ
チング装置を実現した時の価格について述べる。
第１の方法は画像パターンを１フレーム分記憶す
るために、第２の方法に比べて半導体ICメモリ
等の記憶素子を多く必要とし、第２の方法ではリ
アルタイムで送られてくる画像パターンを標準パ
ターンと照合処理するため、第１の方法に比べて
論理ICを多く必要とする。従来、半導体ICメモ
リが高価であり、第１の方法を安価に実現するこ
とは難しかつたが、近年半導体ICメモリの集積
度が急速に高まり、単位記憶容量あたりの価格は
低下して、第２の方法を実現するための論理IC
の価格よりも安価になつてきている。したがつて
現在では、第１の方法を採用した方が、安価にパ
ターンマツチング装置を実現できる。

上記の２つのパターンマツチング方法のうち、
第１の方法はリモートセンシングの分野で、第２
の方法はIC部品の組立ての分野で広く用いられ
てきている。また第１の方法では高速化を図るた
めに、画像パターン上に数画素毎に照合基準点を
粗く設けておいてまず照合を行い、次にそれらの
照合結果より得られる一致度が高い照合基準点か
ら、探索手法を用いた詳しい照合によつて認識点
を捜すという階層的パターンマツチング方法が採
用されることが多い。

発明が解決しようとする問題点 本発明は、上記の第１の方法によつて、２次元
の位置検出をリアルタイムで行うためパターンマ
ツチング方法に関するものである。高速処理に不
向きな第１の方法をあえて採用したのは、上述し
たようにパターンマツチング処理の自由度が高く
柔軟な処理ができることと、第２の方法より安価
に実現できることによる。また、本発明は、上述
した粗い照合と詳しい照合による階層的パターン
マツチング方法という高速処理方法を取り入れる
ことを前提としている。

しかしながら上記のような構成では、たとえ
ば、IC部品を回路基板に搭載するときに要求さ
れる処理時間内で、IC部品の位置検出を行うこ
とは難しい。その理由は、画像パターン上に数画
素毎に照合基準点を粗く設けたとしても、これら
の照合基準点における照合処理だけで画像取り込
み時間T_iの数倍の処理時間を要するからである。

本発明は上記問題点に鑑み、画像パターン上に
粗く設けられた照合基準点における画像パターン
と標準パターンとの照合に先立つて、標準パター
ンの窓枠内に含まれる画像パターンの各画素にお
ける輝度の総和を算出し、この算出された値によ
つて画像パターンと標準パターンの照合処理を行
うかとうか判定することによつて、処理の高速化
を図るパターンマツチング方法を提供するもので
ある。

問題点を解決するための手段 本発明は上記問題点を解決するために、撮像手
段より得られる映像信号をデジタル化して、各画
素に対応する輝度という数値情報で得られた画像
パターンを記憶手段に保持しておき、あらかじめ
上記画像パターンと同じ方法で記憶手段に保持さ
れている標準パターンと画素ごとに照合を行つ
て、一致度が極大となる位置を求めるパターンマ
ツチング処理において、上記画像パターンと上記
標準パターンの画素ごとの照合を行う前に、上記
標準パターンの窓枠内に含まれる上記画像パター
ンの各画素に対する輝度の総和を算出し、上記輝
度の総和が、あらかじめ与えれている２つの基準
値のうち、小さい方の基準値よりも小さいが、あ
るいは、大きい方の基準値よりも大きい場合に
は、上記画像パターンと上記標準パターンの画素
ごとの照合を行わず、上記輝度の総和が、上記小
さい方の基準値以上かつ、上記大きい方の基準値
以下である場合にのみ、上記画像パターンと上記
標準パターンの画素ごとの照合を行うようにした
ものである。

作 用 まず簡略化のために画像パターンと標準パター
ンの輝度値は“０”か“１”の２値とし、また標
準パターンは画像パターン中の特徴的な部分を取
り出したものであるから、標準パターン中では
“０”と“１”がある一定以上の割合で混在して
いるものと考える。以上の仮定は、本発明のパタ
ーンマツチング方法による照合処理の高速化手法
を述べる上で、何ら一般性を失うものではない。
また、本発明の特徴である、標準パターンの窓枠
内に含まれる画像パターンの画素ごとの輝度の総
和の算出は、上記の仮定のように画像パターンが
２値の場合には、画像パターン中に含まれる
“１”の数を数えていることにほかならず、すな
わちこれは標準パターンの窓枠内に含まれる画像
パターンの“１”の領域の面積を算出することに
等しい。そこで、以後標準パターンの窓枠内に含
まれる画像パターンの画素ごとの輝度の総和の算
出は、面積計算と呼ぶことにする。

以上の仮定に基づいて、この技術的手段による
作用を図面を参照しながら説明する。

第２図は、Ｍ×Ｍの大きさを持つた標準パター
ン２２と、Ｎ×Ｎの大きさを持つた画像パターン
２３、画像パターン２３上にｎ画素毎に設けられ
た照合基準点２４を示している。画像パターン２
３上に存在する照合基準点２４の総数は、標準パ
ターン２２の大きさを考慮して次の(3)式で与えら
れる。記号〔ａ〕は、ａを越えない最大の整数を
表わしている。

〔Ｎ−Ｍ／ｎ＋１〕² ……(3) この照合基準点２４の総数は、たとえば、Ｎ＝
512，Ｍ＝16，ｎ＝４とすれば、約15600もの膨大
な値となる。第２図に示すようにこれらの照合基
準点の中には、標準パターンの窓枠が完全に画像
パターンの“１”の領域中に含まれるような位置
にある照合基準点２５や、像パターンの“０”領
域中に含まれるような位置にある照合基準点２６
が多数存在している。照合基準点２５における画
像パターン２３と標準パターン２２の照合処理
は、標準パターン２２に含まれる“１”の領域の
面積計算処理であり、照合基準点２６における照
合処理は、標準パターン２２に含まれる。“０”
の領域の面積計算処理である。照合処理は通常、
画像パターンを記憶手段から読み出す、読み
出した画像パターンと標準パターンの画素ごとの
論理演算を行つて一致度を算出する、の２つの過
程によつて実行されるが、標準パターンの大きさ
によつてこれら、の処理は何回かに分割して
行われるので、この場合さらに、その結果得ら
れた一致度を累積加算する、が加えられた３つの
過程によつて実行される。とことが上記の場合の
ような、照合基準点２４，２５における照合処理
では、の論理演算が全く意味をなさない無駄な
処理になつている。照合処理を意味を持つような
照合基準点においては、標準パターンの窓枠内に
含まれる“０”と“１”が混在する割合は、最初
に仮定した標準パターン自身の“０”と“１”の
混在する割合にある程度近くなつているはずだか
らである。そこで本発明では画像パターン上に粗
く設けられた照合基準点において、上記のの処
理を省いた、の処理による面積計算をまず行
い、その結果得られた面積が、あらかじめ与えら
れている２つの基準値のうち、小さい方の基準値
より小さいか、あるいは大きい方の基準値より大
きい場合には、照合処理は行わずに次の照合基準
点に移動し、上記面積が、あらかじめ与えられて
いる２つの基準値のうち、小さい方の基準値以
上、かつ大きい方の基準値以下であつ場合に限つ
てその照合基準点において照合処理を行うことに
した。また、面積計算はそもそも本発明の最終目
標である２次元パターンの位置検出に密接に関係
しているものでないので、厳密に行つてもその効
果は充分反映されない。そこで本発明では、第３
図に示したように標準パターン３１の部分領域３
２だけの面積計算を行うことにした。しかし、標
準パターン３２の面積計算時における窓枠の間引
きの程度や、また、画像パターン上に設ける照合
基準点の間隔によつては、画像パターンの面積に
関する情報が正しく得られないことがある。そこ
で、これらの値を設定する際には、安全率を充分
に考えて設定しなければならない。また、面積計
算時に判定に用いる２つの基準値を表わす“０”
と“１”の混在の割合は、最初に仮定した標準パ
ターン中での“０”と“１”が混在する割合より
も充分低く設定しておいて、照合基準点を数画素
ごとに設けたことと、標準パターンの窓枠内を間
引いたことによつて生じる面積時の誤差に対応で
きるようにしておく。

以上のようにして、画像パターン上に数画素毎
に設けられた膨大な数の照合基準点における照合
処理に必要な時間を大幅に削減することができ
る。

実施例 以下本発明の一実施例のパターンマツチング方
法について、図面を参照しながら説明する。

第１図は本発明の一実施例であるパターンマツ
チング方法のブロツク図を示すものである。第１
図において、テレビカメラ等の撮像手段１より得
た映像信号２は、２値化手段３によつて２値化さ
れ画像パターン４となつて画像パターン記憶手段
５に格納される。画像パターン記憶手段５は、画
像パターン制御手段６によつて制御されており、
画像パターンの入出力は、中央処理手段７からの
命令８によつて行われる。画像パターン制御手段
６には、画像パターン記憶手段５中の特定部分の
画像パターンを読み出すための、画像パターンの
ｘ座標、ｙ座標記憶手段などによつて構成されて
いる。一方、標準パターン９は、パターンマツチ
ング処理に先立つて、教示時に画像パターン記憶
手段５中より切り出され、標準パターン記憶手段
１０中に保持される。標準パターン記憶手段１０
は、標準パターン制御手段１１によつて制御され
ており、標準パターンの入出力は、中央処理手段
７からの命令１２によつて行われる。中央処理手
段７は、また、画像パターンと標準パターンの照
合処理を行う際に、論理演算を行うデータがそれ
ぞれ画像パターン記憶手段５と標準パターン記憶
手段１０から読み出され、論理演算手段１３に入
力されるように、画像パターン制御手段６に対し
て命令８を、標準パターン制御手段１０に対して
命令１２を送信する役割や、第１図の各ブロツク
を制御する役割を持つ。論理演算手段１３に入力
された２つのパターンデータは、そこで排他的論
理和の否定がとられ、２つのパターンデータで対
応する画素が一致する場合にビツトが“１”とな
る。第４図に示すように標準パターン４１がＡ×
Ｂ画素から成る時には、この論理演算はＡビツト
ずつ行われ、論理演算の結果得られたＡビツトの
データ１４がビツトカウント手段１５に入力さ
れ、そこでＡビツト中で一致した画素数である
“１”の数がカウントされ、その結果得られたデ
ータＡビツト中の一致度１６が累積加算手段１７
に入力される。Ａ×Ｂ画素から成る標準パターン
４１に対しては、以上の処理をＢ回繰り返すこと
によつて標準パターン全域に対する処理が完了す
る。画像パターンと標準パターンの照合結果であ
る一致度１８は中央処理手段７で判定され一致度
が高い場合にはその時の照合基準点の座標値か照
合結果記憶手段１９に格納される。画像パターン
の面積計算は、画像パターンが画像パターン記憶
手段５より読み出され、論理演算手段１３を経ず
に直接ビツトカウント手段１５に、Ａビツトの情
報２０として入力されることによつてなされる。

以上のように構成されたパターンマツチング方
法について、以下第１図、第５図および第６図を
用いてその動作を説明する。第５図は、大きさが
Ａ×Ｂ画素である標準パターン５１とその照合基
準点５２および画像パターン５３（ただしパター
ンは図示されていない）上に設けられた照合基準
点５４を表わしている。照合処理の開始点を画像
パターン５３の左上端の照合基準点５５とする
と、標準パターン５１の照合基準点５２を画像パ
ターン５３の照合基準点５５に合わせて、まず標
準パターン５１の窓枠内に含まれる画像パターン
５３の面積を計算する。この時の面積計算を行う
のは、第６図に示したＡ×Ｂ画素の大きさを持つ
標準パターンの窓枠６１内の一部の領域６２のみ
であり、この図では画像パターンがＡビツトずつ
４回に分けて、第１図のビツトカウント手段１５
に入力され累積加算手段１７によつて面積が計算
される。そしてこの面積があらかじめ与えられた
２つの基準値と中央処理手段７において比較さ
れ、小さい方の基準値よりも小さいか、あるいは
大きい方の基準値よりも大きい場合には、第５図
に示される次の照合基準点５６に進んで再び面積
計算を行うことになる。また算出した面積が２つ
の基準値の小さい方の基準値以上かつ大きい方の
基準値以下の場合には、その照合基準点５５にお
いて画像パターン５３と標準パターン５１の照合
を行つて、その結果得られた一致度を第１図の中
央処理手段７にて判定し、高い一致度が得られた
場合には照合結果記憶手段１９にその照合基準点
の座標値を格納しておき、第５図の照合基準点５
５における処理を終了して次の照合基準点５６で
の面積計算処理に移る。画像パターン５３上での
照合基準点の移動の方法は、画面上を垂直方向に
走査する場合には、基準点５５から基準点５６へ
とまず下方向に移動し、最下基準点５７までくれ
ば隣の最上基準点５８に移り、終点である基準点
５９まで上記の面積計算、照合処理が行われる。

以上の処理が終つた段階では、第５図の画像パ
ターン５３中に存在する照合基準点５４のうち、
認識点の付近に存在していると思われる照合基準
点の座標値が、第１図の照合結果記憶手段１９中
に格納されていることになる。そこで次に、照合
結果記憶手段１９中に格納されている各座標にお
いて探索手法を用い詳しい照合を行うことによつ
て、その照合基準点付近に存在する一致度が極大
にはる位置を検出することができる。そして、検
出された位置データ２１はこの位置検出装置を利
用しているメインコントローラ等へ送信される。

以上のように本実施例によれば、標準パターン
の窓枠に含まれる画像パターンの面積を計算する
ことによつて、膨大な数存在する照合基準点にお
ける照合処理を減少させ、パターンマツチング処
理を高速化することができる。

発明の効果 第７図は本発明の効果を説明する図である。
“１”によつて表わされる白い背景領域７１の中
に、“０”によつて表わされる黒い十字パターン
７２が存在する場合と、黒い背景領域７３の中
に、白い十字パターン７４が存在する場合が示さ
れている。このいずれの場合においても、照合処
理に先だつて各照合基準点における標準パターン
の窓枠内に含まれる画像パターンの面積を計算
し、この面積の値があらかじめ定めた２つの基準
値のうち、小さい方の基準値より小さいか、ある
いは大きい方の基準値より大きい場合には、照合
処理を行わないようにすることによつて、照合処
理を行う必要がある照合基準点が存在する領域
を、画面全体から十字パターンの輪郭部付近の小
さい領域７５に狭めることができ、パターンマツ
チング処理を高速化することができる。

【図面の簡単な説明】

第１図は本発明の一実施例であるパターンマツ
チング方法の構成を示すブロツク図、第２図は標
準パターンと画像パターンの大きさおよび画像パ
ターン上に存在する照合基準点を示す図、第３図
は標準パターンの窓枠内における面積計算の対象
となる領域を示す図、第４図は標準パターンの大
きさを示す図、第５図は画像パターン上の照合基
準点に対する標準パターンの移動方法を示す図、
第６図は標準パターンの窓枠内における面積計算
の対象となる領域を示す図、第７図は本発明の効
果を示す図である。 ５……画像パターン記憶手段、６……画像パタ
ーン制御手段、７……中央処理手段、１０……標
準パターン記憶手段、１１……標準パターン制御
手段、１３……論理演算手段、１５……ビツトカ
ウント手段、１７……累積加算手段、１９……照
合結果記憶手段、２２……標準パターン、２３…
…画像パターン、２４……照合基準点、３１……
標準パターン窓枠、３２……面積計算対象領域、
４１……標準パターン、５１……標準パターン、
５３……画像パターン、５４……照合基準点、６
１……標準パターン窓枠、６２……面積計算対象
領域。

Claims (1)

【特許請求の範囲】
1. １ 撮像手段より得られる映像信号をデジタル化
   して、各画素に対応する輝度という数値情報で得
   られた画像パターンを記憶手段に保持しておき、
   あらかじめ上記画像パターンと同じ方法で記憶手
   段に保持されている標準パターンと画素ごとに照
   合を行つて、一致度が極大となる位置を求めるパ
   ターンマツチング処理において、上記画像パター
   ンと上記標準パターンの画素ごとの照合を行う前
   に、上記標準パターンの窓枠内に含まれる上記画
   像パターンの各画素に対する輝度の総和を算出
   し、上記化輝度の総和が、あらかじめ与えれてい
   る２つの基準値のうち、小さい方の基準値よりも
   小さいか、あるいは、大きい方の基準値よりも大
   きい場合には、上記画像パターンと上記標準パタ
   ーンの画素ごとの照合を行わず、上記輝度の総和
   が、上記小さい方の基準値以上かつ、上記大きい
   方の基準値以下である場合にのみ、上記画像パタ
   ーンと上記標準パターンの画素ごとの照合を行う
   ことを特徴とするパターンマツチング方法。