(57)【特許請求の範囲】
【請求項１】
検査画像に対してテンプレート画像を移動させて両画像のマッチングスコアーを算出し、最高値のマッチングスコアーを得ることによりマッチング位置を求めるパターンマッチング方法において、
最高値のマッチングスコアーに対して、その隣接する位置のマッチングスコアーを考慮した補正量を加えることにより、画素ずれによるマッチングスコアーの修正を行い、
上記隣接する位置のマッチングスコアーを考慮した補正量は、ｃｏｎｓｔ１×（縦方向の下の値−縦方向の上の値）2＋ｃｏｎｓｔ２×（縦方向の右の値−縦方向の左の値）2である、パターンマッチング方法。
【請求項２】
検査画像に対してテンプレート画像を移動させて両画像のマッチングスコアーを算出し、最高値のマッチングスコアーを得ることによりマッチング位置を求めるパターンマッチング方法において、
テンプレート画像を所定画素飛ばしで移動してマッチングスコアーを算出し、そのうちのマッチングスコアー最高値に対応する位置を求める第１のステップと、
第１のステップで得られた最高値の位置をスタートとして、順次、その周囲４画素（上下左右）についてマッチングを実施し、より高いマッチングスコアーに対応する位置を求める第２のステップと、
最高のマッチングスコアーに到達すると停止する第３のステップと、
第３のステップで得られた最高値のマッチングスコアーに対して、その隣接する位置のマッチングスコアーを考慮した補正量を加えることにより、画素ずれによるマッチングスコアーの修正を行う第４のステップとを備え、
上記隣接する位置のマッチングスコアーを考慮した補正量は、ｃｏｎｓｔ１×（縦方向の下の値−縦方向の上の値）2＋ｃｏｎｓｔ２×（縦方向の右の値−縦方向の左の値）2である、パターンマッチング方法。
【請求項３】
検査画像に対してテンプレート画像を移動させて両画像のマッチングスコアーを算出し、最高値のマッチングスコアーを得ることによりマッチング位置を求めるパターンマッチング方法において、
テンプレート画像を所定画素飛ばしで移動してマッチングスコアーを算出し、そのうち所定値以上のマッチングスコアーに対応する位置を求める第１のステップと、
第１のステップで得られた位置をスタートとして、順次、その周囲４画素（上下左右）についてマッチングを実施し、より高いマッチングスコアーに対応する位置を求める第２のステップと、
最高のマッチングスコアーに到達すると停止する第３のステップと、
第３のステップで得られた最高値のマッチングスコアーに対して、その隣接する位置のマッチングスコアーを考慮した補正量を加えることにより、画素ずれによるマッチングスコアーの修正を行う第４のステップとを備え、
上記隣接する位置のマッチングスコアーを考慮した補正量は、ｃｏｎｓｔ１×（縦方向の下の値−縦方向の上の値）2＋ｃｏｎｓｔ２×（縦方向の右の値−縦方向の左の値）2である、パターンマッチング方法。
【請求項４】
検査画像に対してテンプレート画像を移動させて両画像のマッチングスコアーを算出し、最高値のマッチングスコアーを得ることによりマッチング位置を求めるパターンマッチング方法において、
最高値のマッチングスコアーに対して、その隣接する位置のマッチングスコアーを考慮した補正量を加えることにより、画素ずれによるマッチングスコアーの修正を行い、
上記隣接する位置のマッチングスコアーを考慮した補正量は、ｃｏｎｓｔ３×ａｂｓ（縦方向の下の値−縦方向の上の値）＋ｃｏｎｓｔ４×ａｂｓ（縦方向の右の値−縦方向の左の値）である、パターンマッチング方法。ただし、ａｂｓは絶対値を表わす。
【請求項５】
検査画像に対してテンプレート画像を移動させて両画像のマッチングスコアーを算出し、最高値のマッチングスコアーを得ることによりマッチング位置を求めるパターンマッチング方法において、
テンプレート画像を所定画素飛ばしで移動してマッチングスコアーを算出し、そのうちのマッチングスコアー最高値に対応する位置を求める第１のステップと、
第１のステップで得られた最高値の位置をスタートとして、順次、その周囲４画素（上下左右）についてマッチングを実施し、より高いマッチングスコアーに対応する位置を求める第２のステップと、
最高のマッチングスコアーに到達すると停止する第３のステップと、
第３のステップで得られた最高値のマッチングスコアーに対して、その隣接する位置のマッチングスコアーを考慮した補正量を加えることにより、画素ずれによるマッチングスコアーの修正を行う第４のステップとを備え、
上記隣接する位置のマッチングスコアーを考慮した補正量は、ｃｏｎｓｔ３×ａｂｓ（縦方向の下の値−縦方向の上の値）＋ｃｏｎｓｔ４×ａｂｓ（縦方向の右の値−縦方向の左の値）である、パターンマッチング方法。ただし、ａｂｓは絶対値を表わす。
【請求項６】
検査画像に対してテンプレート画像を移動させて両画像のマッチングスコアーを算出し、最高値のマッチングスコアーを得ることによりマッチング位置を求めるパターンマッチング方法において、
テンプレート画像を所定画素飛ばしで移動してマッチングスコアーを算出し、そのうち所定値以上のマッチングスコアーに対応する位置を求める第１のステップと、
第１のステップで得られた位置をスタートとして、順次、その周囲４画素（上下左右）についてマッチングを実施し、より高いマッチングスコアーに対応する位置を求める第２のステップと、
最高のマッチングスコアーに到達すると停止する第３のステップと、
第３のステップで得られた最高値のマッチングスコアーに対して、その隣接する位置のマッチングスコアーを考慮した補正量を加えることにより、画素ずれによるマッチングスコアーの修正を行う第４のステップとを備え、
上記隣接する位置のマッチングスコアーを考慮した補正量は、ｃｏｎｓｔ３×ａｂｓ（縦方向の下の値−縦方向の上の値）＋ｃｏｎｓｔ４×ａｂｓ（縦方向の右の値−縦方向の左の値）である、パターンマッチング方法。ただし、ａｂｓは絶対値を表わす。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、例えば半導体デバイスのパッケージ表面に印字されたマークの検査に使用する濃淡パターンマッチング方法に係り、特にパターンマッチングによる最高値スコアーを修正する方法及び最高値スコアーに高速に到達する方法に関するものである。
【０００２】
【従来の技術】
半導体パッケージ等に印字されたマークを検査する方法として、テレビカメラ画像を使用した濃淡パターンマッチング法が有名である。このパターンマッチング法には色々な使い方があるが、以下に代表的な方法の概略を説明する。
【０００３】
図１はこの種の濃淡パターンマッチングを行う装置の構成例を示す概略図である。
（１）図１において、印刷された対象物の正面、すなわち半導体デバイス１の上面をテレビカメラ２により撮影する。この時、印刷された最小線幅が３画素以上になるようにテレビカメラ２の視野を調整する。
【０００４】
（２）テレビカメラ２からの映像信号はデジタル化され、パーソナルコンピュータ３のメモリに記録される。メモリに記録するときはパーソナルコンピュータ３から読み出しやすいように考慮する。すなわち、テレビ画面の縦方向をＹ方向、横方向をＸ方向と表現して個々の画素の明るさを２次元の配列、例えばｂｒ［ｙ］［ｘ］（ｂｒ＝ｂｒｉｇｈｔ；明るい）として読み出すことが出来るように構成する。記録されたメモリの内容はもう一度読み出されてアナログ信号に戻され、モニターテレビ５に表示されることも行なわれる。また、パーソナルコンピュータ３にはマウス６などのオペレータとのインターフェースを行う手段が接続される。
【０００５】
（３）同じ文字が印字されている最初のデバイス１が撮影される。オペレータはマウス６を使い、文字が印字されている領域をドラッグする。パーソナルコンピュータ３の画像処理ソフトウエアはドラッグした領域内で文字を１文字ずつ切り出す。文字を切り出す操作は次の（３．１）〜（３．３）のようになる。
【０００６】
（３．１）ドラッグした範囲内の明るさの最大値、最小値、及び中間値を求める。
（３．２）ドラッグした範囲内で上から下に順に横方向の範囲内の明るさの最大値を求める。ここで、前記（３．１）の中間値を超えている列は文字がある列と判る。その結果、縦方向にみた文字列の始まった位置と終わった位置すなわち文字列がある範囲が判る。
（３．３）個々の文字列の範囲ごとに、左から右に向かい縦方向に前記と同様に明るさの最大値を求める。中間値を超えている列があるとそこには文字があることになる。以上の処理により１文字の上下左右の範囲の位置が判る。
【０００７】
（４）全文字について、各文字ごとに２次元平面の文字範囲内の明るさをテンプレートとして記録する。
【０００８】
（５）そして、次のデバイスを撮影する。
【０００９】
（６）デバイスが置かれた位置の再現性、デバイスの中で印刷された文字の位置の再現性等を考慮して、最初のデバイスの文字と次のデバイスの文字の位置の予想される最大ズレの範囲を決める。
【００１０】
（７）予想される最大ズレ範囲内で入力した画像に対しテンプレートを順に当てはめ、画像が最もよく似た位置を求める。このときの具体的な方法は次の通りである。図８はこの部分のパターンマッチング方法の手順を示すフローチャートである。
【００１１】
（７．１）最初に「スコアー最大値」を０に初期設定する。そして最初のデバイスで最初の文字が現れた位置を中心に最大のズレ範囲を設定する。縦方向の範囲と横方向の範囲を設定する。
【００１２】
（７．２）最初の位置において次の（１）式に従いマッチングスコアーを計算する。これは、一般的に正規化相関の濃淡パターンマッチングと呼ばれる方法である。
【００１３】
ｒ2＝｛ｎΣｆｇ−ΣｆΣｇ｝2／｛ｎΣｆ2−（Σｆ）2｝｛ｎΣｇ2−（Σｇ）2｝…（１）
ただし、ｒ2＝スコアー（一致度）、ｆ＝入力画像の各画素の明るさ、ｇ＝テンプレートの各画素の明るさ、ｎ＝テンプレートの有効画素数。
【００１４】
（７．３）上記の計算で得たスコアーが「スコアー最大値」より大きいと「スコアー最大値」を更新し、そのときの縦、横の位置座標を記録する。
【００１５】
（７．４）横方向のスキャン範囲内では横方向の位置を右に１画素だけ進めて前記（７．２），（７．３）の計算が繰り返す。
【００１６】
（７．５）横方向のスキャン範囲を超えると縦方向のスキャン範囲かの判断が行われ、範囲内であると縦方向に１画素だけ下の位置で改めて左から右に向けて横方向のスキャンが繰り返される。
【００１７】
（７．６）縦方向のスキャン範囲を超えたら終了する。
【００１８】
（８）ここで得られた「スコアー最大値」が最初のデバイスと次のデバイスの間の最初の文字の一致度である。似ているほど点数が高く、似ていないと点数が低い。
【００１９】
（９）最初のデバイスの第２文字をテンプレートとして次の文字のマッチングをとる。この手順は前記（７）の通りである。
【００２０】
（１０）同様にして第３文字以降の処理を行う。各文字ごとのスコアー最大値の最も低いスコアーが前もって定めた閾値より低いと第２のデバイスは不良と判定される。
【００２１】
（１１）第３のデバイスについても同様な検査が行われる。そして同じ文字のデバイスが続くかぎり上記の処理が続けられる。
【００２２】
【発明が解決しようとする課題】
前記の濃淡パターンマッチングを実行する上での大きな問題点は次の（Ａ）及び（Ｂ）である。
【００２３】
（Ａ）図９はテンプレート画像、テンプレート画像と検査画像とが一致した例、及びずれている例を表わし、図９ｄで示すようにアルファベットのＦの文字の一部に対応している。文字の線幅は上記で説明した３画素である。図９ａはテンプレートの一部を示し、図９ｂはテンプレートと検査する画像がぴったり一致した文字の一部を示している。図９ｃはテンプレートと検査する画像が半画素だけ横方向にずれてカメラに撮影されて取り込まれた例を示している。四角の中の濃い密な斜線は１００％の明るさの画素を示し、薄い疎な斜線は５０％の明るさの画素を示す。
【００２４】
図１０はテンプレートを横方向に１画素ずつずらした場合のスコアーの変化を示している。この例で示すように図１０ａの場合はテンプレートと１００％一致する高いスコアーが得られる点があるが、図１０ｂの場合は一部に不一致の部分がありスコアーが低下する。このようにカメラで撮影するときの条件で図１０に示す誤差が発生する。
【００２５】
アルファベットの大文字と数字だけの単純な文字検査を考えた場合でも、ここで発生するような誤差が発生することにより、より一致度の差の少ない似た文字、例えば“Ｑ”と“Ｏ”の文字の違いを異なった文字と識別できなくなる。
【００２６】
（Ｂ）前記の手順（６）で説明した２個目以降のデバイスの文字検査で文字が出現する可能性がある範囲を１画素ずつ２次元の平面でパターンマッチングの演算を繰り返す必要があり、長い時間を消費する問題がある。
【００２７】
この発明は、上記のような問題点を解消するためになされたものであり、パターンマッチング時の画素ずれによるマッチングスコアーの低下を補正して常に最高のマッチングスコアーを得ることにより、従来困難であった似た文字の異文字チェック等を高精度で実行することを目的とする。
【００２８】
また、所定画素（４画素）飛ばしのスキャンにより最もマッチングスコアーの高い点を開始点に設定し、その開始点から山登り探索法により上下左右の４画素のマッチングを行い、高得点のマッチングスコアーを順次探索することにより、最高値スコアーまで高速に到達することを目的とする。
【００２９】
【課題を解決するための手段】
請求項１の発明は、検査画像に対してテンプレート画像を移動させて両画像のマッチングスコアーを算出し、最高値のマッチングスコアーを得ることによりマッチング位置を求めるパターンマッチング方法において、最高値のマッチングスコアーに対してその隣接する位置のマッチングスコアーを考慮した補正量を加えることにより、画素ずれによるマッチングスコアーの修正を行うことを特徴とする。
【００３０】
請求項２の発明は、検査画像に対してテンプレート画像を移動させて両画像のマッチングスコアーを算出し、最高値のマッチングスコアーを得ることによりマッチング位置を求めるパターンマッチング方法において、テンプレート画像を所定画素飛ばしで移動してマッチングスコアーを算出し、そのうちのマッチングスコアー最高値に対応する位置を求める第１のステップと、第１のステップで得られた最高値の位置をスタートとして、順次、その周囲４画素（上下左右）についてマッチングを実施し、より高いマッチングスコアーに対応する位置を求める第２のステップと、最高のマッチングスコアーに到達すると停止する第３のステップと、第３のステップで得られた最高値のマッチングスコアーに対して、その隣接する位置のマッチングスコアーを考慮した補正量を加えることにより、画素ずれによるマッチングスコアーの修正を行う第４のステップからなる。
【００３１】
請求項３の発明は、検査画像に対してテンプレート画像を移動させて両画像のマッチングスコアーを算出し、最高値のマッチングスコアーを得ることによりマッチング位置を求めるパターンマッチング方法において、テンプレート画像を所定画素飛ばしで移動してマッチングスコアーを算出し、そのうち所定値以上のマッチングスコアーに対応する位置を求める第１のステップと、第１のステップで得られた位置をスタートとして、順次、その周囲４画素（上下左右）についてマッチングを実施し、より高いマッチングスコアーに対応する位置を求める第２のステップと、最高のマッチングスコアーに到達すると停止する第３のステップと、第３のステップで得られた最高値のマッチングスコアーに対して、その隣接する位置のマッチングスコアーを考慮した補正量を加えることにより、画素ずれによるマッチングスコアーの修正を行う第４のステップからなる。
【００３２】
請求項４の発明は、請求項１から請求項３の発明において、隣接する位置のマッチングスコアーを考慮した補正量として、ｃｏｎｓｔ１×（縦方向の下の値−縦方向の上の値）2＋ｃｏｎｓｔ２×（縦方向の右の値−縦方向の左の値）2としたことを特徴とする。
【００３３】
請求項５の発明は、請求項１から請求項３の発明において、隣接する位置のマッチングスコアーを考慮した補正量として、ｃｏｎｓｔ３×ａｂｓ（縦方向の下の値−縦方向の上の値）＋ｃｏｎｓｔ４×ａｂｓ（縦方向の右の値−縦方向の左の値）としたことを特徴とする。ただし、ａｂｓは絶対値を表わす。
【００３４】
請求項６の発明は、検査画像に対してテンプレート画像を移動させて両画像のマッチングスコアーを算出し、最高値のマッチングスコアーを得ることによりマッチング位置を求めるパターンマッチング方法において、テンプレート画像を所定画素飛ばしで移動してマッチングスコアーを算出し、そのうちのマッチングスコアー最高値に対応する位置を求める第１のステップと、第１のステップで得られた最高値の位置をスタートとして、順次、その周囲４画素（上下左右）についてマッチングを実施し、より高いマッチングスコアーに対応する位置を求める第２のステップと、最高のマッチングスコアーに到達すると停止する第３のステップからなる。
【００３５】
請求項７の発明は、検査画像に対してテンプレート画像を移動させて両画像のマッチングスコアーを算出し、最高値のマッチングスコアーを得ることによりマッチング位置を求めるパターンマッチング方法において、テンプレート画像を所定画素飛ばしで移動してマッチングスコアーを算出し、そのうち所定値以上のマッチングスコアーに対応する位置を求める第１のステップと、第１のステップで得られた位置をスタートとして、順次、その周囲４画素（上下左右）についてマッチングを実施し、より高いマッチングスコアーに対応する位置を求める第２のステップと、最高のマッチングスコアーに到達すると停止する第３のステップからなる。
【００３６】
【発明の実施の形態】
実施の形態１．
実施の形態１は上記（Ａ）の問題点を解消するためになされたものであり、検査画像とテンプレートのマッチングスコアーが画素ずれ等で低下するのを、隣接する位置（上下左右の４点）のスコアーを考慮した補正量を加えることで修正することを目的とする。
【００３７】
図９に示すように、検査画像とテンプレートが一致したもの（図９ｂ）が半画素だけずれて撮影されると図９ｃのようになる。このとき濃い密な斜線は１００％の明るさで、薄い疎な斜線は５０％の明るさである。図９ｂのテンプレートと検査画像の濃淡マッチングをとり、良く一致した時と左右に１画素ずらした状態のスコアーをとると図１０ａのようになる。同じく図９ｃの１画素ずらしたマッチングスコアーをとると、図１０ｂのように左でも右でも同じ値となり、図１０ａのマッチングスコアーより相当低い点数しか得られない。そこで、実施の形態１では、図１０に示す補正量（誤差）を図１０ｂの最高値に加えることで修正するようにする。すなわち、補正量は次の（２）式により演算する。
【００３８】
補正後のスコアー＝補正前のスコアー＋ｃｏｎｓｔ１×（縦方向の下の値−縦方向の上の値）2＋ｃｏｎｓｔ２×（縦方向の右の値−縦方向の左の値）2…（２）
【００３９】
次に、実施の形態１のパターンマッチング法を具体的に説明する。なお、パターンマッチング法を実施する機器構成は図１の通りである。
【００４０】
（１）図２は実施の形態１によるマッチングスコアーを補正する演算を示すフローチャートを示し、図８のフローチャートにＡＡの部分が追加される。すなわち、図２において、予想される最大ズレ範囲内で入力した画像に対しテンプレートを順に当てはめ、画像が最もよく似た位置を求める。このときの具体的な方法は次の通りである。
【００４１】
（１．１）最初に「スコアー最大値」を０に初期設定する。そして最初のデバイスで最初の文字が現れた位置を中心に最大のズレ範囲を設定する。縦方向の範囲と横方向の範囲を設定する。
【００４２】
（１．２）最初の位置において次の（１）式に従いマッチングスコアーを計算する。これは、一般的に正規化相関の濃淡パターンマッチングと呼ばれる方法である。
【００４３】
ｒ2＝｛ｎΣｆｇ−ΣｆΣｇ｝2／｛ｎΣｆ2−（Σｆ）2｝｛ｎΣｇ2−（Σｇ）2｝…（１）
ただし、ｒ2＝スコアー（一致度）、ｆ＝入力画像の各画素の明るさ、ｇ＝テンプレートの各画素の明るさ、ｎ＝テンプレートの有効画素数。
【００４４】
（１．３）そしてＡＡに追加したように、上記で得たスコアーをｓｃｏｒ［ｙ］［ｘ］に記録する。
【００４５】
（１．４）その後、上記スコアーが「スコアー最大値」より大きいと「スコアー最大値」を更新し、そのときの縦、横の位置座標を記録する。
【００４６】
（１．５）横方向のスキャン範囲内では横方向の位置を右に１画素だけ進めて前記（１．２），（１．４）の計算を繰り返す。
【００４７】
（１．６）横方向のスキャン範囲を超えると縦方向のスキャン範囲かの判断が行われ、範囲内であると縦方向に１画素だけ下の位置で改めて左から右に向けて横方向のスキャンが繰り返される。
【００４８】
（１．７）縦方向のスキャン範囲を超えたら終了する。
【００４９】
以上のように、スキャン範囲の各画素対応で求めたスコアーを配列のｓｃｏｒ［ｙ］［ｘ］に記録する。
【００５０】
（２）次に、前記（２）式に従い補正後のスコアーを求める。スコアー最大値をｓｃｏｒｍａｘ、スコアー最大値を得たときの座標をｙｍａｘ，ｘｍａｘとして配列部分をＣ言語風に表現すると次の（３）式になる。
【００５１】
補正後のスコアー＝ｓｃｏｒｍａｘ＋ｃｏｎｓｔ１×（ｓｃｏｒ［ｙｍａｘ＋１］［ｘｍａｘ］−ｓｃｏｒ［ｙｍａｘ−１］［ｘｍａｘ］）2＋ｃｏｎｓｔ２×（ｓｃｏｒ［ｙｍａｘ］［ｘｍａｘ＋１］−ｓｃｏｒ［ｙｍａｘ］［ｘｍａｘ−１］）2…（３）
【００５２】
（３）ここで、最も良く一致したときのスコアーが１０００点になるように演算式を組み立てたときのｃｏｎｓｔ１，ｃｏｎｓｔ２の値は０．００２前後の値が選ばれる。この値を得るには同一デバイスをカメラの前で少し動かすたびに撮影してマッチング結果のスコアーの配列“ｓｃｏｒ［ｙ］［ｘ］”を観察し、図１０のａ及びｂに近い事例を見つけ誤差及び補正量をいくらにするかを決め、又スコアー最大値を中心とした上下左右の画素の値の差から決定する。なお、この値はカメラ倍率や文字サイズなどの条件が同じ場合は変更しなくて良い。
【００５３】
（４）上記の補正の計算は１文字のパターンマッチングが終わる度にそのスコアー最大値に対して実施する。
【００５４】
実施の形態１の変形例として（３）式を変形した次の（４）式でも得られる効果はほとんど変わらず演算時間を短縮できる。
【００５５】
補正後のスコアー＝ｓｃｏｒｍａｘ＋ｃｏｎｓｔ３×ａｂｓ（ｓｃｏｒ［ｙｍａｘ＋１］［ｘｍａｘ］−ｓｃｏｒ［ｙｍａｘ−１］［ｘｍａｘ］）＋ｃｏｎｓｔ４×ａｂｓ（ｓｃｏｒ［ｙｍａｘ］［ｘｍａｘ＋１］−ｓｃｏｒ［ｙｍａｘ］［ｘｍａｘ−１］）…（４）
ただし、ａｂｓは絶対値（ａｂｓｏｌｕｔｅ  ｖａｌｕｅ）を表わす。
【００５６】
このときのｃｏｎｓｔ３，ｃｏｎｓｔ４は０．１程度が適している。
【００５７】
以上のように実施の形態１によれば、以下の効果を達成することができる。
１）微少な撮影位置の移動によりスコアーがばらつくことを防止し、変動が少なくなることから閾値を微妙に調節することが出来るようになり、違いの少ない文字を識別できるようになる。
２）補正の計算が単純であり、演算時間の負担が少ない効果がある。
【００５８】
実施の形態２．
テンプレートを使用したパターンマッチングの場合、２個目のデバイスの入力画像信号に対してテンプレートマッチングの演算を実施しなければならない範囲の決定は、デバイスが位置決めされるときのばらつき範囲と、デバイスの中に文字を印刷するときのばらつき範囲の２つを考慮して行われる。
【００５９】
先に述べた従来例では、マッチング演算をする範囲内の全てを順に１画素ずつ左上から右下まで実施していた。図３（ａ）は高さ及び幅が１３画素の２次元平面を単純に１画素ずつずらしてマッチング演算を行っているところを示している。この方法では合計したばらつき範囲を片側７画素と仮定しても１３画素の二乗である１６９回のマッチング演算が必要となり多大の時間を要する。もう少し合理化した方法として、例えば図３（ｂ）に示すように、縦横方向に４画素とばし（５回の二乗で２５回）でマッチング演算を実施し（図３（ｂ）の濃い斜線の丸）、その中の最も良いマッチングスコアーが出た位置（図中黒丸）を中心に前後左右の片側４画素７の二乗の４９画素（図３（ｂ）の白丸）を検査するような方法がある。この合理化した方法では合計７４回でほぼマッチング回数が半減したことになる。
【００６０】
実施の形態２では、上記に加えて上記マッチング回数を更に少なくしようとするものであり、図４に基づいて具体的に説明する。
【００６１】
図４は実施の形態２の４画素飛ばしで到達した点（黒丸）から最高スコアーの点（薄い斜線の丸）の位置まで到達するところを図示したものである。
【００６２】
１）すなわち、上述の様に４画素飛ばしでマッチングを取り（図４の濃い斜線の丸）、そのスコアー最大値の位置を次のスタート点とする（図４の黒丸）。
【００６３】
２）スタート点（図４の黒丸）の周囲４画素（上下左右）についてマッチングを取りスコアーを得る。このとき、図５の１回目のようなスコアーが得られたものとする。
【００６４】
３）スタート点の周囲４画素の最高点は上の３００点であり、中央の１００点より高い値なので次に進む。そして、３００点の位置をスタート点として前記と同様にしてマッチングスコアーが高い点に順次進む（図５の２回目から４回目参照）。
【００６５】
４）図５の４回目の最高点９００点を中心として周囲４カ所のマッチングスコアーを得る（図６）。この周囲４カ所のスコアーが中央の９００点より低いのでそれ以上先に進まず、探索しながら進む作業は終了する。図４にはスタート点（黒丸）から最高点（薄い密な斜線丸）まで探索しながら進んだ軌跡を矢印で示している。
【００６６】
以上が本実施の形態の具体的な手法である。この方式の利点は最高点に達するまでのマッチング回数が少ないことである。この例の場合で４回あれば最高点に達することが出来、最後の最高点の確認を含み５×４で２０回あればよい。しかしながら、図４を見れば分かるようにこの例の最高点（薄い密な斜線の丸）は４回飛ばしで検索した濃い斜線の丸の中間位置にある。平均すれば４回ではなく２回あれば最高点に達することができ、最後の最高点の確認を含み３×４で１２回あればよい。最初の４画素とばしを含んでも３７回でよく、実施の形態２の最初で述べた１６９回、７４回より遥かに少ない回数で済み、従来の手法と比較して非常に有効な方法といえる。
【００６７】
ここでは、最初に４画素飛ばしで２５回実施し、その中の最高点から高い点を求めて１画素ずつ進む２段階の方法を説明した。４画素飛ばしよりも別の数の飛ばし方が良いか否かの判断は、文字の大きさなどにより決まるので利用する対象で選択する。
【００６８】
また上記の説明では、４画素飛ばしを２５回全て完了した後で最もスコアーが良かった位置から第２段階目の検索を始めているが、例えば１００以上のスコアーが出てきたらその位置から第２段階の検索に入る方法もある。画像の対象の条件を考慮して選ぶと良い。
【００６９】
実施の形態３．
実施の形態２の後で実施の形態１を続けて実施すると実施の形態１の説明よりももっと簡単に実施できるという効果が生まれる。
【００７０】
図７は実施の形態３によるパターンマッチング手法を示すフローチャートであり、図７に基づいて実施の形態３の手法及び効果を明確に表現できる関係箇所について説明する。
１）まず４画素飛ばしで検索し、マッチングスコアーが最も高かった位置からスタートする。そして、本実施の形態３で説明するところの山登り検索のループ（いわゆるｗｈｉｌｅループ）を設定する。
２）すなわち、スタート位置より周囲４画素のマッチングを行うに当って、１回目は右、２回目は下、３回目は左、４回目は上の順にマッチングを実施するものとし、その都度正規化相関演算によりマッチングスコアーを算出する。そして、各々のマッチング結果は、スコアーの結果の配列ｓｃｏｒ１［０］からｓｃｏｒ１［３］に記録する。
３）スコアーの結果の配列ｓｃｏｒ１［０］からｓｃｏｒ１［３］のうち最も高い点数を上げた画素位置を記録すると共に、その位置のスコアーをｍａｘｓｃｏｒｅとして更新する。
４）上記４回のループが終了すると、スタート地点である中央スコアー値とｍａｘｓｃｏｒｅを比較して、ｍａｘｓｃｏｒｅが高ければｍａｘｓｃｏｒｅを上げた画素位置を中央位置とし、その中央スコアー値をｍａｘｓｃｏｒｅとして周囲４画素のマッチングを算出する。
５）スタート地点の周囲４画素から得たスコアーのどれよりも中央のスコアー値が高いとそこで山登り検索のループを終了する。
６）その後、実施の形態１で説明したピーク値の補正の演算に入る。このときｓｃｏｒ１［ｎ］の配列に記録したスコアーがあるから、実施の形態１で説明したピークスコアーを補正するための演算式は次式（５）のように変わる。
【００７１】
補正後のスコアー＝ｓｃｏｒｍａｘ＋ｃｏｎｓｔ１×（ｓｃｏｒ１［０］−ｓｃｏｒ１［２］）2＋ｃｏｎｓｔ２×（ｓｃｏｒ１［１］−ｓｃｏｒ１［３］）2…（５）
【００７２】
以上のように実施の形態３によれば、以下の効果を奏する。
１）ｓｃｏｒ１［ｎ］は周囲４画素のマッチングスコアーを計算する度に新しい値に更新されるので、演算に当っては最後に更新された値をそのまま使用すればよくなり、絶対位置座標でのスコアーを探すなどの実施の形態１のような複雑な演算を省略することができる。
２）実施の形態１に示したｓｃｏｒ［ｙ］［ｘ］の配列は、１画面分の６４０×４８０画素分の３０００個に及ぶメモリ使用するのに対して、この実施の形態では４個のメモリを準備するだけで良い効果がある。
【００７３】
【発明の効果】
請求項１，４，５の発明によれば、微少な撮影位置の移動によりマッチングスコアーがばらつくことを防止し、変動が少なくなることから閾値を微妙に調節することが出来るようになり、違いの少ない文字を識別できるようになる。また、補正の計算が単純であり、演算時間の負担が少ない効果がある。
【００７４】
請求項２，３，４，５の発明によれば、演算に当っては最後に更新された値をそのまま使用すればよくなり、絶対位置座標でのスコアーを探すなど複雑な演算を省略することができる。また、少ないメモリを準備するだけで演算できる効果がある。
【００７５】
請求項２，３，６，７の発明によれば、最高点に達するまでのマッチング回数が少なくなり、高速に最高点まで到達することができる。
【図面の簡単な説明】
【図１】  この発明のパターンマッチング法を実施するための機器構成を示す図である。
【図２】  この発明の実施の形態１によるマッチングスコアーを補正する演算を示すフローチャートである。
【図３】  高さ及び幅が１３画素の２次元平面を単純に１画素ずつマッチングを演算した方法と、４画素飛ばしで荒く検索しその最適値から９×９画素範囲だけを詳細に演算する方法を示す図である。
【図４】  この発明の実施の形態２によるパターンマッチング法を示し、４画素飛ばしで到達した黒丸から最高スコアーの薄い斜線の丸の位置まで到達する状態を示す図である。
【図５】  この発明の実施の形態２による最高スコアーの位置まで到達する途中のスコアーを示す図である。
【図６】  この発明の実施の形態２による最高スコアーに到達した状態を示し、周囲４個の値より中央が高い点数となることを示す図である。
【図７】  この発明の実施の形態３によるパターンマッチング法の手順を示すフローチャートである。
【図８】  従来のパターンマッチング法の手順を示すフローチャートである。
【図９】  テレビカメラに撮影されたときに対象物がわずかにずれると微少に異なった信号となることを”Ｆ”の文字を例として説明している図である。
【図１０】  わずかに異なった画像でマッチングスコアーの演算結果が異なっていることを表わす図である。
【符号の説明】
１  デバイス、２  テレビカメラ、３  パーソナルコンピュータ、４  画像入力増設基板、５  モニターテレビ、６  マウス。
【図１】
0004454075.tif 000002
【図２】
0004454075.tif 000003
【図３】
0004454075.tif 000004
【図４】
0004454075.tif 000005
【図５】
0004454075.tif 000006
【図６】
0004454075.tif 000007
【図７】
0004454075.tif 000008
【図８】
0004454075.tif 000009
【図９】
0004454075.tif 000010
【図１０】
0004454075.tif 000011