JPH0962838A - 高速パターンマッチング方法 - Google Patents

Abstract

(57)【要約】 【課題】 入力画像の情報を欠落させることなく演算量
を従来のものより減少させることにより、あらゆる性質
の画像に対して高速かつ高精度のパターンマッチングを
実現させるための方法を提供する。 【解決手段】 参照画像を複数のテンプレートに分割
し、この中の任意の１つを基準テンプレートとして選択
し、基準テンプレートのみを検査対象物画像上に走査さ
せながら各走査位置における基準テンプレートと検査対
象物画像との相関係数を算出する。基準テンプレートの
相関係数が予め設定された閾値以上の場合のみ、他のテ
ンプレートについても相関係数を算出し、全テンプレー
トの相関係数が全て閾値以上の場合、このときの参照画
像の位置を候補の１つとして記憶し、走査終了後全候補
の相関係数に基づいて検査対象物の有無及び存在位置を
認識する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、パターンマッチン
グによる検査対象物の検出及び位置決めを高速に行うた
めに好適なパターンマッチング方法に関する。

【０００２】

【従来の技術】画像処理技術は計測・検査などの自動化
の手段として近年広く利用されるようになった。これ
は、画像処理は２次元データを扱うため非常に大量のデ
ータを処理する必要があるが、近年のコンピュータの処
理速度の向上により、大量のデータを短時間に処理する
ことが可能になってきたことによるものである。しか
し、現在最も入手しやすいカメラの解像度は 500×500
画素程度であるが、この場合でも１画面は25万個もの膨
大な画素からなっているため、仮に１画素当たり１マイ
クロ秒の処理性能を持った比較的高速なコンピュータを
使用した場合でも、すべての画素に対して処理を行うに
は0.25秒を要することになる。実際には画像データの入
力時間や処理データの出力時間等がこれに加わるため、
全体の処理時間は0.25秒を超えることになり、移動する
検査対象物に対して処理を行うような場合には問題とな
る。このため、高速な画像処理を行うためには、コンピ
ュータの性能向上とともに、処理結果の信頼性を損なう
ことなく処理量を減少させることができるような画像処
理のアルゴリズムを開発することが必須となっている。

【０００３】画像処理アルゴリズムの代表的なものとし
て、パターンマッチングと呼ばれる手法が知られてい
る。この手法は見つけたい物体の全体または一部の画像
即ち参照画像を予め記憶しておき、検査対象物を撮影し
て得られた画像即ち検査対象画像から参照画像と同じ画
像領域を見つけだすものである。

【０００４】従来のパターンマッチング方法のほとんど
は参照画像の特徴、例えば明るい領域の大きさや中心位
置などを予め計算しておき、この特徴に近い画像を検査
対象画像から探すというものである。この方法は画像の
特徴という代用特性に置き換えるため処理量を大幅に低
減できるので、処理速度が速いなどの利点があり広く用
いられてきた。しかし、この方法では、検出能力が参照
画像の特徴の選び方によって大きく影響されるため、画
像処理の経験が豊富なエンジニアでないと実用的な検査
装置を作ることができないという欠点があった。

【０００５】他の手法として、参照画像をそのまま記憶
しておき、参照画像と同じ画像を検査対象画像から探し
出すものがある。テンプレートマッチングと呼ばれるこ
の方法の特徴は、参照画像を予め登録しておくだけで、
あとは画像処理装置が設定されたアルゴリズムにしたが
って参照画像に近い画像領域を検査対象画像の中から自
動的に見つけてくれるため、ほとんど専門的な知識が必
要でない点である。しかし、後で述べるように、この手
法は計算量が膨大となるため、処理時間が非常に長くな
るという欠点があった。

【０００６】最近、コンピュータの性能が向上し、また
テンプレートマッチングの高速化手法がいろいろ考案さ
れて、一部で実用化されてきた。テンプレートマッチン
グの方法として現在最も認識能力が高いと言われている
正規化相関係数を用いた方法を説明する。正規化相関係
数φは次に示す式（１）で表わされる。

【０００７】

【数１】

【０００８】ここで、T(i,j)はテンプレート、F(i,j)は
入力画像の各画素の値である。式（１）の演算を例えば
500X500画素で構成される入力画像に対して 50X50画素
の大きさのテンプレートを使用して正規化相関演算を実
行させる場合は、50億回の四則演算を行う必要がある。
この場合、仮に50MIPSの高速演算プロセッサを使用して
も演算には 250秒も必要とする。このように従来の正規
化相関係数を用いたテンプレートマッチングは、画像の
明るさが変動しても安定に認識できるという利点以上
に、演算処理には膨大な時間が必要となるという大きな
問題点があり、実用的ではなかった。

【０００９】そこで、この演算処理時間の問題を解決す
るために、演算処理を高速に行わせる数々の手法が考え
出されている。その中で最も一般的かつ簡単な方法とし
て知られているのが、入力画像からある一定の間隔で画
素データを間引いて抽出し、この間引いて抽出した画素
データにより正規化相関演算を行う方法である。式
（１）で示される正規化相関係数の計算は自乗項で構成
されるため、間引き法と呼ばれるこの方法では、演算す
る画素数が減少すると演算時間も急速に短縮することが
できる。例えば、４画素おきに抽出するとすれば、演算
量は１６分の１に減少するため、演算時間が短縮化され
る。

【００１０】また、他の方法として、特開平５−１８９
５７０号公報では、通常は２次元で表されるテンプレー
トを、独立な２軸であるＸ方向とＹ方向のそれぞれに画
素の濃度を加算して２つの１次元テンプレートに変換
し、入力画像にも同様の変換を施した後、１次元のウィ
ンドウを走査し、１次元の類似度計算を行い、この２つ
の１次元テンプレートで算出された類似度を合成するこ
とにより、Ｘ、Ｙ両方向で高いマッチング精度が得られ
るとしている。この方法では、正規化相関演算の演算量
は１次元の演算処理程度に減少されるため、ハードウェ
アは小規模な回路で実現でき、演算時間についてもかな
り短縮される。

【００１１】

【発明が解決しようとする課題】しかし、前者の方法で
は、抽出された画像が入力画像に比して情報が欠落した
ものとなってしまうため、対象画像の輪郭形状が複雑な
場合は、画像情報の欠落により高精度なマッチングでき
なくなる恐れが生じる。また、後者の方法では、前者の
方法のように画素の情報が欠落してしまうことはない
が、濃度加算は微妙な濃度変化を打ち消してしまうとい
う欠点があるため、画像の濃度が急激に変動するような
画像では、高いマッチング精度が得られないという問題
がある。

【００１２】本発明の課題は、正規化相関演算を用いた
パターンマッチング方法において、入力画像の情報を欠
落させることなく、演算量を従来のものより減少させる
ことにより、画像の濃度が急激に変動するような画像も
含めたあらゆる性質の画像に対して、高速かつ高精度の
パターンマッチングを実現させるための方法を提供する
ことにある。

【００１３】

【課題を解決するための手段】これらの課題を解決する
ために、本発明では、マスターとなる対象物を撮影して
得た参照画像を複数のテンプレートに分割し、これら複
数のテンプレートの中の任意の１つを基準テンプレート
として選択し、この基準テンプレートのみを検査対象物
を撮影して得た検査対象物画像上に走査させながら、各
走査位置における基準テンプレートと検査対象物画像と
の類似度を算出するための正規化相関演算を行い、相関
係数を逐次算出する。

【００１４】この走査の過程において、算出された基準
テンプレートの相関係数が予め設定された閾値以上の場
合のみ、基準テンプレート以外のテンプレートについて
も、このときの基準テンプレートの位置に対応する各テ
ンプレートの位置における相関係数をそれぞれ算出し、
かつ算出された全テンプレートの相関係数が全て閾値以
上の場合、このときの全テンプレートの位置すなわち参
照画像の位置を検査対象物が存在する位置の候補の１つ
として記憶する。

【００１５】そして、基準テンプレートが検査対象物画
像上を全て走査し終えたとき、候補が１つもなかった場
合は参照画像に類似する検査対象物は存在しないものと
判定し、また候補が１つだけ存在した場合はこの候補に
検査対象物が存在するものと判定し、さらに候補が複数
個存在した場合は各候補毎に算出された全テンプレート
の相関係数についてその合計値を算出し、この合計値が
最大となる候補に前記検査対象物が存在するものと判定
する。

【００１６】

【発明の実施の形態】本発明の一実施の形態を図面に基
づいて説明する。図１は本発明が適用される画像処理装
置を用いた対象物体の位置姿勢認識システムの概略図を
示したものである。検査対象物４をカメラ１により撮影
し、この画像を画像処理装置２に取り込み、所定の画像
処理を行い、判定結果をモニタ３に表示させる。図示し
ないロボットシステムに適用する場合は、カメラ１をロ
ボットアームの先端に保持させ、画像処理後のデータを
画像処理装置２からの出力信号としてロボットのコント
ローラに送信し、ロボットを制御する位置データや姿勢
データを補正する。なお、図１において、モニタ３に映
し出されている検査対象物の周囲に描かれている四角形
の枠は、ウィンドウと呼ばれる画像処理領域を表してい
る。

【００１７】以下、本実施形態の処理フローについて記
述するが、記述中「（ステップ＊＊）」の語句は、図５
に示す本発明のテンプレートマッチングの処理フローを
示すフローチャートの各処理ステップに相当する。

【００１８】まず、本発明における参照画像の教示につ
いて説明する。一般にテンプレートマッチングにおける
参照画像の教示過程では、図１に示したモニタ３に示さ
れているウィンドウをマスターとなる対象物に対して設
定し、このマスターとなる対象物の画像データを参照画
像として画像処理装置内の記憶装置に記憶させている。
本発明ではさらに、記憶された参照画像をテンプレート
と呼ばれる複数の小領域に分割し、このテンプレートを
画像処理装置内の記憶装置に記憶させる（ステップ３
２）。このように本発明では、マスターとなる対象物全
体を撮影して得られた画像データを参照画像と称し、参
照画像を複数の小領域に分割して得られた画像データを
テンプレートと称することにする。

【００１９】本実施形態では、図２に示すように、参照
画像を４個のテンプレートに等分割する。この場合、画
像処理装置内の記憶装置には図３に示すようなテンプレ
ート１乃至テンプレート４の４個のテンプレートの画像
データが記憶されることになる。なお、本発明において
は１つのテンプレートを中心に処理が行われるので、分
割された複数のテンプレートの中の任意の１つをこの処
理の中心となる基準テンプレートとして設定することに
する。本実施形態では、テンプレート１を基準テンプレ
ートとして設定する。

【００２０】次に、本発明における検査対象物と参照画
像とのマッチングについて説明する。図４に実際の検査
対象物を撮影したモニタ画面の例を示す。なお、本発明
においては、この検査対象物を撮影したモニタ画面上の
画像を検査対象物画像と称する。参照画像と検査対象物
画像とのマッチングにおいては、まず、基準テンプレー
トとして設定したテンプレート１と検査対象物画像のマ
ッチングを行わせることから始まる。具体的には、検査
対象物画像の最も左上にテンプレート１を置き（ステッ
プ３３）、この位置におけるテンプレート１と検査対象
物画像との間で式（１）の演算を行い相関係数を求める
（ステップ３５）。ここで算出された相関係数は０以上
１以下の値をとり、０で一致度０％、１で一致度１００
％を表すことになる。通常はノイズ等の画像への微妙な
影響のため、実際にはテンプレート１と検査対象物画像
が完全に一致している状態でも相関係数は１に達するこ
とはない。一般には相関係数が０．９以上ならばかなり
高い一致度を示していることになる。

【００２１】次に、算出されたテンプレート１の相関係
数を予め設定された閾値と比較する。このように、テン
プレートの任意の位置でのテンプレートと検査対象物画
像との相関係数の算出と、算出された相関係数と閾値と
の比較を、本発明ではテンプレートのマッチングと称す
る。閾値の値は相関係数と同様に０以上１以下の値を設
定することになる。しかし、先に述べたようにテンプレ
ートと検査対象物画像が完全に一致している状態でも相
関係数は１には達しないから、閾値の値を極度に高く設
定すると一致する箇所が１つもないということが起こり
うるし、逆に閾値の値を極度に低く設定すると一致する
箇所が多数現れてしまい、判定での処理時間が長くなっ
てしまうので、閾値の設定では検査対象物の性質に応じ
た値を適宜設定することになる。

【００２２】算出された相関係数と閾値との比較におい
て、相関係数が閾値以下の場合は（ステップ３６Ｎ）、
この位置にテンプレート１の画像データに対応する検査
対象物の画像データは存在しないものと判定し、テンプ
レート１を入力画像に対して１画素右にずらして（ステ
ップ４５）、再度前述と同様にマッチングを行う（ステ
ップ３５）。このようにマッチングの過程においてテン
プレートを１画素ずつずらす操作をテンプレートの走査
と呼ぶ。走査方法としてはいろいろあるが、最も一般的
に行われている方法では、まず検査対象物画像の最も左
上にテンプレートを置き、次いで１画素ずつテンプレー
トを右方向に移動させ、テンプレートが検査対象物画像
の右端まで到達した後は、テンプレートを検査対象物画
像の左端に戻した上さらに１画素下にずらし、再度右方
向に移動させ、最終的にテンプレートが検査対象物画像
の最も右下まで移動するまでこれを繰り返す。

【００２３】一方、基準テンプレートとしたテンプレー
ト１の走査の途中において、このテンプレート１の相関
係数が閾値より大きくなった場合は（ステップ３６
Ｙ）、基準テンプレート以外のテンプレート、すなわち
テンプレート２以降のテンプレートについてもマッチン
グを行う。ここで、基準テンプレート以外のテンプレー
トの基準テンプレートに対する相対的な位置は、参照画
像を複数のテンプレートに分割した段階で決まっている
ため、基準テンプレート以外のテンプレートについては
基準テンプレートのように走査を行わせる必要はなく、
マッチングは各テンプレートの基準テンプレートに対す
る相対的な位置においてのみ行えばよいことになる（ス
テップ３９）。

【００２４】すなわち、本実施形態では図３に示すよう
に参照画像を分割したのであるから、テンプレート２の
基準テンプレート（テンプレート１）に対する相対的な
位置はテンプレート１の右隣ということになり、この位
置でのみテンプレート２のマッチングを行う。テンプレ
ート３及びテンプレート４についても同様に順次マッチ
ングを行っていく。この場合、テンプレート３はテンプ
レート１の下隣、テンプレート４はテンプレート１の右
下すなわちテンプレート３の右隣に配置することにな
る。

【００２５】４つのテンプレート全てに対して相関係数
が閾値以上であった場合は、この位置を検査対象物が存
在する位置の候補の一つとしてカウントし、画像処理装
置内の記憶装置に記憶する（ステップ４３）。なお、検
査対象物の形状や閾値の設定によっては候補が複数存在
することもあり得るので、通常は処理の途中で候補が見
つかってもさらに処理を続行し、全ての候補を抽出す
る。

【００２６】そして、画面全体の走査が終了した時点
で、抽出された全ての候補の中から、各候補の相関係数
に基づいて検査対象物が存在する位置を判定する。具体
的には、候補が１つもない場合は（ステップ４６Ｎ）、
参照画像に類似する検査対象物は存在しないものと判定
し（ステップ４８）、また候補が１つだけ存在した場合
は（ステップ４６Ｙ）、この候補に検査対象物が存在す
るものと判定し、さらに候補が複数個存在した場合は
（ステップ４６Ｙ）、各候補毎に算出された全テンプレ
ートの相関係数についてその合計値を算出し、この合計
値が最大となる候補に検査対象物が存在するものと判定
する（ステップ４７）。

【００２７】本実施形態によれば、参照画像を４個のテ
ンプレートに等分割しているため、テンプレート１個の
面積は参照画像に比べて１／４となっている。式（１）
に示されるように、相関係数の演算量はテンプレートの
面積の自乗で利いてくるため、この場合は演算量が１／
１６に減少するので、相関係数の演算自体に要する処理
時間も１／１６で済むことになる。複数の存在候補の中
から検査対象物が存在する位置を絞り込むための演算時
間を含めた判定に要する処理時間を加えても、全体の処
理時間は参照画像の全領域でマッチングを行うものと比
較して１／１０以下に短縮される。

【００２８】このように本実施形態によれば、従来の参
照画像の全領域についてマッチングを行うものと比較し
て処理時間が大幅に短縮されるにも係わらず、検査対象
物が存在すると判定された位置においては、結局、参照
画像を分割することによって生成された４つのテンプレ
ート全てについてマッチングを行ったことになるので、
認識精度は参照画像の全領域についてマッチングを行っ
たものと全く同じとなる。

【００２９】なお、先に述べたように、本実施形態で
は、基準テンプレートとしたテンプレート１の相関係数
が閾値より大きくなった場合のみ、基準テンプレート以
外のテンプレート、すなわちテンプレート２乃至４のテ
ンプレートについてマッチングを行うとしているが、４
つのテンプレート全てに対して相関係数が閾値以上であ
った場合のみこの位置を検査対象物が存在する位置の候
補の一つとして記憶するようにしているので、テンプレ
ート２乃至４のマッチングの過程でも、これら全てのテ
ンプレートについてマッチングを行う必要はなく、例え
ば、テンプレート２のマッチングにおいてこのテンプレ
ート２の相関係数が閾値より小さくなった場合は、この
位置は検査対象物が存在する位置の候補ではないという
ことになるから、残りのテンプレート３及び４について
はマッチングを行わないようにしてもよい（ステップ４
１Ｎ）。

【００３０】このようにすれば、参照画像の分割数を多
く設定した場合や、あるいは閾値を低く設定したために
相関係数が閾値以上となる基準テンプレートが多くなっ
たりした場合など、基準テンプレート以外のテンプレー
トの演算量が多くなったときに、不必要なマッチング処
理がなくなり、処理時間の一層の短縮が図れるものとな
る。

【００３１】なお、本実施形態においては、参照画像を
４個のテンプレートに等分割したが、これに限定され
ず、テンプレートの分割数や形状は使用形態に合わせて
任意に設定してよい。しかし、分割数については、これ
が多いほど候補の絞り込みが確実にでき、この結果認識
精度が向上するが、あまり多すぎると処理時間の増加を
招くことになるので、使用するハードウェアの性能や検
査対象物の性質に応じた値を適宜設定することが望まし
いと言える。

【００３２】また、本実施形態においては、各候補毎に
算出された４個の相関係数を合計し、この合計値が最大
となる候補の位置に検査対象物が存在するものと判定し
たが、これに限定されず、各候補毎に算出された４個の
相関係数の平均値を算出し、この平均値が最大となる候
補の位置に検査対象物が存在するものと判定してもよい
し、また、各候補毎に算出された４個の相関係数の最小
値を抽出し、この最小値が最大となる候補の位置に検査
対象物が存在するものと判定してもよい。

【００３３】さらに、本実施形態においては、分割され
た全てのテンプレートについて閾値を１つ設定するよう
にしたが、これに限定されず、各テンプレートに対応し
た閾値をそれぞれ設定するようにしてもよい。

【００３４】

【発明の効果】このように本発明は、教示された参照画
像を複数のテンプレートに分割し、この中から任意に１
個のテンプレートを基準テンプレートとして選択し、最
初にこの基準テンプレートにおいてマッチングを行い相
関係数が予め設定された閾値以上になった位置におい
て、更に残りのテンプレートにおいても同様に順次マッ
チングを行うようにしたので、マッチングのためのテン
プレートの相関係数の演算は基準テンプレートの相関係
数の演算にほとんど費やされることになり、参照画像の
全領域でマッチングを行わせる従来の方法と比較して著
しく処理時間が短縮される。

【００３５】また、検査対象物が存在すると判定された
位置においては、結局、全てのテンプレートについてマ
ッチングを行うことになるため、参照画像の全領域でマ
ッチングを行った場合と全く同じ精度の結果が得られ
る。

【００３６】このように、本発明によれば、認識精度に
ついては参照画像の全領域においてマッチングを行わせ
る従来の方法と同レベルに維持しつつ、処理時間につい
ては大幅に短縮することができるので、検査対象物の画
像情報を欠落させたり変換させることなく、高速かつ高
精度のパターンマッチングを実現させることが可能とな
った。

【図面の簡単な説明】

【図１】本発明が適用される画像処理装置を用いた対象
物体の位置姿勢認識システムの概略図を示したものであ
る。

【図２】本発明の一実施の形態において、参照画像を４
つのテンプレートに等分割したものを示したものであ
る。

【図３】本発明の一実施の形態において、分割された４
つのテンプレートの画像例を表したものである。

【図４】マッチング時のモニタの画像例である。

【図５】本発明のテンプレートマッチングの処理フロー
を示すフローチャートである。

【符号の説明】

２ 画像処理装置 ４ 検査対象物

Claims (1)

【特許請求の範囲】
1. 【請求項１】 検査対象物を撮影して得られた検査対象
   物画像上に予め記憶された参照画像を走査させ、両画像
   の類似度を算出するための正規化相関演算を行い、該正
   規化相関演算により算出された両画像の相関係数に基づ
   いて前記検査対象物画像のうち前記参照画像と類似した
   画像領域を抽出する画像処理装置のパターンマッチング
   方法において、前記参照画像を任意の形状を持つ複数の
   テンプレートに分割し、該複数のテンプレートの中の任
   意の１つを基準テンプレートとして選択し、該基準テン
   プレートのみを前記検査対象物画像上に走査させながら
   各走査位置における基準テンプレートと検査対象物画像
   との相関係数を逐次算出し、該相関係数が予め設定され
   た閾値以上の場合のみ前記基準テンプレート以外のテン
   プレートについても相関係数を算出し、かつ算出された
   全テンプレートの相関係数が全て前記閾値以上の場合こ
   のときの全テンプレートの位置すなわち前記参照画像の
   位置を前記検査対象物が存在する位置の候補として記憶
   し、前記基準テンプレートが前記検査対象物画像上を全
   て走査し終えたとき、前記候補が１つもない場合は前記
   参照画像に類似する前記検査対象物は存在しないものと
   判定し、かつ前記候補が１つだけ存在した場合はこの候
   補に前記検査対象物が存在するものと判定し、かつ前記
   候補が複数個存在した場合は各候補毎に算出された全テ
   ンプレートの相関係数についてその合計値を算出し該合
   計値が最大となる候補に前記検査対象物が存在するもの
   と判定するようにしたことを特徴とする高速パターンマ
   ッチング方法。