JPH10171987A

JPH10171987A - パターンマッチング装置

Info

Publication number: JPH10171987A
Application number: JP33123296A
Authority: JP
Inventors: Tokumi Harada; 徳実原田
Original assignee: Sharp Corp
Current assignee: Sharp Corp
Priority date: 1996-12-11
Filing date: 1996-12-11
Publication date: 1998-06-26

Abstract

(57)【要約】【課題】基準パターンを用いたパターン認識を比較的
小さな回路規模のハードウェアで精度良く実現すると共
に、ＣＣＤカメラ等からの映像信号をリアルタイム処理
できるパターンマッチング装置を提供する。【解決手段】パターンマッチング装置は、基準パター
ンに対してこれと一致するパターンが認識対象画像の中
に存在するか否かを調べるために、認識対象画像から基
準パターンの比較対象となる部分画像を順次シフトさせ
つつ生成する部分画像生成手段８と、部分画像を垂直方
向に縮小し垂直縮小画像を生成する画像垂直縮小手段９
と、垂直縮小画像を水平方向に縮小し部分画像の縮小画
像を生成する画像水平縮小手段１０と、部分画像の縮小
画像と縮小された基準パターンとの一致度を算出する一
致度演算回路１１とを備えている。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、対象物の基準パタ
ーンを用いてパターン認識するためのパターンマッチン
グ装置に関する。

【０００２】

【従来の技術】パターンマッチングとは、ある基準とな
るパターンがあり、これと一致するパターンが認識対象
画像中に存在するかどうかを調べる処理である。例え
ば、基準パターン１が図６に示すように形状‘ア’とい
うものであり、これに対し、認識対象画像２は図７に示
すように形状ア、イ、ウ、…と様々な形状が入り組んで
いた場合、認識対象画像２の中から基準パターン‘ア’
と同じパターンを探索し、同じパターンが見つかれば、
その位置を求めるものである。

【０００３】したがって、パターンマッチングの基本的
な処理方法としては、まず、図８に示すように、認識対
象画像２から基準パターン１と同じ大きさの部分画像３
を取り出して、この部分画像３と基準パターン１との比
較演算を行い、パターンがどの程度類似しているかを一
致度という数値データで表して評価する。

【０００４】次に、図９に示すように、この部分画像３
を認識対象画像２中で少しずつずらしながら認識対象画
像２全体を走査して、それぞれの位置で発生した部分画
像３に対し基準パターン１との一致度を算出する。

【０００５】最後に、それぞれの部分画像３から得られ
た一致度で一定値以上のものがあれば、基準パターン１
と同じ形状のパターンが存在すると判断できるので、さ
らにその周辺の部分画像３の一致度を調べて、一致度が
極大となる位置を求めることにより、見つけられたパタ
ーンの正確な位置と基準パターン１との類似性を表す一
致度を求めることができる。

【０００６】認識対象画像の部分画像と基準パターンと
の類似性を調べるための一致度を算出する方法として、
濃度差加算や正規化相関などが広く知られている。濃度
差加算は、基準パターンと認識対象画像の部分画像との
対応する画素間の濃度差の累積を求める方法であり、計
算式は次の式（１）で表される。

【０００７】Ｒ₁＝Σ｜Ｉ_ij−Ｍ_ij｜ …（１）ただし、上式において、Ｒ₁＝濃度差加算値、Ｉ_ij＝部
分画像の各画素の濃度値、Ｍ_ij＝基準パターンの濃度値
である。

【０００８】一方、正規化相関は、基準パターンと認識
対象画像の部分画像との対応する画素間の相互相関係数
を求める方法であり、計算式は式（２）で表される。

【０００９】Ｒ₂＝（ｎΣＭＩ−ΣＭΣＩ）／ √（ｎΣＭ²−（ΣＭ）²）・√（ｎΣＩ²−（ΣＩ）²） …（２）ただし、上式において、Ｒ₂＝正規化相関値、Ｉ＝部分
画像の各画素の濃度値、Ｍ＝基準パターンの濃度値であ
る。

【００１０】ところが、上記いずれの方法においても、
認識対象画像の全ての部分画像に対して上記演算を行う
と計算量が膨大になり、処理時間が長くかかるという問
題を有している。したがって、従来からピラミッド法や
特徴点抽出法などにより計算量を減らす工夫がされてい
る。

【００１１】ピラミッド法は、一般的な画像処理の手法
であり、画像処理にかかる時間を短縮するため、元の画
像を縦横それぞれ１／２に縮小した縮小画像を作り、こ
の縮小画像を用いパターンマッチングなどの画像処理を
行う。そして、求められた縮小画像の位置に対応する原
画像の位置を求めて、その位置に対してのみ、元の画像
にて詳細な処理を行う。また、縮小画像をさらに縦横そ
れぞれ１／２に縮小して同様の処理を行うことで、処理
速度をさらに高速化できる。

【００１２】図１０は、パターンマッチングをピラミッ
ド法で処理した場合のフローチャートである。この方法
では、図１１に示すように、あらかじめ基準パターン１
とその基準パターン１を縦横それぞれ１／４に縮小して
得られる基準パターン４とを画像メモリなどに記憶して
おく。そして、まず、ＣＣＤカメラ等から認識対象画像
を入力し、画像メモリに一時記憶しておく（ｓ１１）。
また、図１２に示すように、認識対象画像２を縦横それ
ぞれ１／４に縮小した縮小画像５を作成する（ｓ１
２）。

【００１３】次に、基準パターン４と縮小画像５とによ
りパターンマッチングを行い、縮小画像５の中に基準パ
ターン４と同じパターンが存在するかどうかを調べ、存
在すればその位置を求める（ｓ１３）。

【００１４】最後に、縮小画像５で求めた位置に対応す
る認識対象画像２の位置の周辺で、基準パターン１との
パターンマッチングを行い、一致点が極大となる位置を
求める（ｓ１４）。

【００１５】図１３は、パターンマッチングを特徴点抽
出法で処理した場合のフローチャートである。この方法
では、あらかじめ、基準パターン１の中で特徴のある点
を複数個選択しておく。特徴点の取り方としては、例え
ば特開平６−４６７０号公報記載のように、基準パター
ン１からエッジ抽出などにより特徴のある点を抽出する
方法がある。

【００１６】そして、まず、ＣＣＤカメラ等から認識対
象画像２を入力し、画像メモリに一時記憶しておく（ｓ
２１）。次に、基準パターン１と認識対象画像２とのパ
ターンマッチングを、あらかじめ選択しておいた特徴点
についてのみ比較演算を行い、一致度を算出する（ｓ２
２）。最後に、認識対象画像２全体で最も一致度の高い
位置を求める（ｓ２３）。

【００１７】

【発明が解決しようとする課題】しかしながら、上記ピ
ラミッド法では、例えば図１４に示す形状‘Ａ’のよう
な画像を１／４に縮小するときに、実線で区切った枠内
を平均して得られる縮小画像と、点線で区切った枠内を
平均して得られる縮小画像とは多少の差異を生じること
となる。したがって、縮小画像のパターンマッチングで
は、縮小する領域の取り方によって基準パターンの形状
に多少の差異を生じ、パターンマッチングしたときの一
致度が低下する。この一致度の低下は、一般に複雑なパ
ターンほど顕著になる。

【００１８】また、縮小画像によるパターンマッチング
で得られた位置は、縮小した単位でしか求まらない。例
えば、１／４縮小の画像の場合、求められる位置の単位
は４画素になる。したがって、通常は、さらにその周囲
において元の画像でのパターンマッチングを行い、１画
素単位の位置を検出しているが、そのために処理速度の
低下を招いている。

【００１９】また、ピラミッド法では、縮小率を上げる
ほど比較演算量は減少するものの、縮小画像と元の画像
との差異は大きくなり、例えば図１５に示すように、形
状‘８’と形状‘Ｂ’のような似ているパターン同士の
区別がつきにくくなることがある。

【００２０】一方、特徴点抽出法は、計算の対象となる
画素が不規則に存在するためハードウェア化が困難であ
り、リアルタイム処理を行うことは困難である。

【００２１】本発明は、上記問題点に鑑みなされたもの
であり、その目的は、基準パターンを用いたパターン認
識を比較的小さな回路規模のハードウェアで精度良く実
現すると共に、ＣＣＤカメラ等からの映像信号をリアル
タイム処理できるパターンマッチング装置を提供するこ
とにある。

【００２２】

【課題を解決するための手段】請求項１の発明に係るパ
ターンマッチング装置は、上記の課題を解決するため
に、対象物の基準パターンと、入力された認識対象画像
とのパターンマッチングを行うパターンマッチング装置
において、前記基準パターンの比較対象となる前記認識
対象画像の部分画像を、該認識対象画像に対し所定の位
置ずつずらしながら順次生成する部分画像生成手段と、
前記部分画像を垂直方向または水平方向のいずれか一方
の方向に縮小し第１の縮小画像を生成する第１画像縮小
手段と、前記第１の縮小画像を垂直方向または水平方向
のいずれかで前記一方の方向とは異なる方向に縮小し、
前記部分画像の縮小画像を生成する第２画像縮小手段
と、前記部分画像の縮小画像と、前記部分画像と同程度
に縮小された前記基準パターンとの一致度を算出する一
致度演算手段とを備えることを特徴としている。

【００２３】上記の構成によれば、認識対象画像に対し
例えば１画素ずつ位置をずらしながら、基準パターンと
同じ大きさの部分画像が順次生成される。さらに、部分
画像が第１および第２画像縮小手段によって所定の大き
さに縮小された後、この縮小画像と予め記憶等されてい
る縮小された基準パターンとの比較演算が一致度演算手
段によって行われる。

【００２４】上記の部分画像の生成については、部分画
像は、例えば動作クロック毎に順次生成されるものとす
る。

【００２５】上記のように、部分画像の縮小画像と、縮
小された基準パターンとによってパターンマッチングを
行うことで、基準パターンと一致するパターンが存在す
る認識対象画像の位置をより精度良く検出することがで
きる。

【００２６】また、縮小する単位の取り方によって基準
パターンの形状に多少の差異を生じる問題も、部分画像
を細かい単位で取ることによりその影響が少なくなる。

【００２７】さらに、上記構成とすることで、演算処理
をハードウェア化することができ、これにより、画像入
力と平行して演算処理を行い、画像入力の終了と同時に
処理を終え対象物の位置を求めるリアルタイム処理（実
時間処理）が可能になる。したがって、映像信号を一旦
画像メモリなどに格納してから処理を行う方法に比し
て、より高速にパターンマッチング処理を行うことがで
きる。

【００２８】なお、第１画像縮小手段は、部分画像生成
手段の出力を加算平均することにより所定の方向に部分
画像を縮小し第１の縮小画像を生成するものとしてもよ
いし、部分画像生成手段の出力を間引くことにより所定
の方向に部分画像を縮小し第１の縮小画像を生成するも
のとしてもよい。

【００２９】また、第２画像縮小手段は、第１画像縮小
手段の出力を加算平均することにより所定の方向に第１
の縮小画像を縮小し部分画像の縮小画像を生成するもの
としてもよいし、第１画像縮小手段の出力を間引くこと
により所定の方向に第１の縮小画像を縮小し部分画像の
縮小画像を生成するものとしてもよい。

【００３０】さらに、一致度演算手段は、部分画像の縮
小画像と縮小された基準パターンとの正規化相関値を算
出して対象物の位置を求めるものとしてもよいし、部分
画像の縮小画像と縮小された基準パターンとの濃度差加
算値を算出して対象物の位置を求めるものとしてもよ
い。

【００３１】請求項２の発明に係るパターンマッチング
装置は、上記の課題を解決するために、請求項１の構成
に加えて、前記認識対象画像を撮像する撮像素子と、前
記撮像素子からのアナログ映像信号をディジタル信号に
変換するＡ／Ｄ変換手段とを備えることを特徴としてい
る。

【００３２】上記の構成によれば、撮像素子として例え
ば光学像をアナログ映像信号に変換するＣＣＤカメラ等
を備えると共に、Ａ／Ｄ変換手段を備えている。Ａ／Ｄ
変換手段は、例えば、ＣＣＤカメラからのアナログ映像
信号を、動作クロックによるサンプリングと量子化によ
りディジタル信号に変換する。これにより、動作クロッ
ク毎に例えば１画素ずつ位置をシフトさせつつ部分画像
を順次発生させ、動作クロック毎にその部分画像と基準
パターンとの一致度を演算するリアルタイム処理が可能
になる。

【００３３】

【発明の実施の形態】本発明の実施の一形態について図
１〜図９および図１１に基づいて説明すれば、以下の通
りである。

【００３４】図１は、本実施形態に係るパターンマッチ
ング装置の概略的構成を示すブロック図である。同図に
示すように、本装置は、ＣＣＤカメラ（撮像素子）６、
Ａ／Ｄ変換器（Ａ／Ｄ変換手段）７、部分画像生成手段
８、画像垂直縮小手段（第１画像縮小手段）９、画像水
平縮小手段（第２画像縮小手段）１０および一致度演算
回路（一致度演算手段）１１を備えている。

【００３５】ＣＣＤカメラ６は、例えば認識対象画像２
（図７参照）の画像を撮像し、アナログの映像信号を出
力する。ＣＣＤカメラ６がノンインターレース型の場
合、ＣＣＤカメラ６から出力されるアナログ映像信号
は、例えば図３に示すように、上の行から０、１、２、
３、４、…、４７９行の順序に走査される。また、ＣＣ
Ｄカメラ６がインターレース型の場合、ＣＣＤカメラ６
から出力されるアナログ映像信号は、例えば図４に示す
ように、まず奇数行のみ上の行から１、３、５、７、
９、…、４７９行の順序で下の行まで走査され、続いて
偶数行のみ上の行から０、２、４、６、８、…、４７８
行の順序で下の行まで走査される。

【００３６】本実施形態では、ＣＣＤカメラ６がノンイ
ンターレース型の場合について説明を行うが、ＣＣＤカ
メラ６がインターレース型の場合でも、Ａ／Ｄ変換器７
によりディジタル信号に変換後、一旦、画像メモリに格
納し、その画像メモリの内容を上の行から順番に読み出
すことにより、ノンインターレース型のＣＣＤカメラ６
を用いる場合と同様に、部分画像生成手段８以降の処理
を行うことができる。ただし、その場合は処理時間が長
くなる。

【００３７】Ａ／Ｄ変換器７は、ＣＣＤカメラ６から出
力されたアナログ信号を、動作クロックによるサンプリ
ングと量子化によりディジタル信号に変換する。このデ
ィジタル信号を、図５に示すように格子状にマッピング
すると、各画素の濃度値がＩ（ｘ，ｙ）のディジタル画
像になる。なお、本実施形態では、認識対象画像２の大
きさが５１２×４８０画素の場合について説明を行う。

【００３８】部分画像生成手段８は、認識対象画像２の
部分画像３（図８参照）を生成するため、１ライン分の
画像データを保持する６３個のラインバッファＡ（図１
中Ａ₀〜Ａ₆₂にて示される）を有している。なお、本実
施形態では、部分画像３の大きさが６４×６４画素の場
合について説明を行う。

【００３９】画像垂直縮小手段９は、部分画像生成手段
８より出力される６４個の画像データを垂直方向に１／
４に縮小処理を行い、１６個の縮小画像データを出力す
るために、１６個の演算回路Ｂ（図１中Ｂ₀〜Ｂ_fにて
示される）を有している。各演算回路Ｂは、動作クロッ
ク毎に、それぞれに接続されている部分画像生成手段８
のラインバッファＡより出力された画像データを４個単
位で縮小処理を行い、１個のデータを出力する。このと
きの縮小処理は、例えば、４個のデータを加算平均した
値を出力したり、あるいは、４個の内３個のデータを間
引いて残り１個のデータを出力したりしてもよい。

【００４０】画像水平縮小手段１０は、１画素分の画像
データを記憶できる６３×１６個のバッファＣと、画像
データの縮小処理を行う１６×１６個の演算回路Ｄ（図
１中Ｄ₀₀〜Ｄ_ffにて示される）とを有している。図１に
おいて、最左列の各バッファＣは、動作クロック毎に、
保持している１画素分の画像データを出力し、演算回路
Ｂから出力される画像データを内部のメモリに格納し保
持する。また、その他のバッファＣは、動作クロック毎
に、保持している１画素分の画像データを出力し、その
左側のバッファＣから出力された画像データをメモリに
格納し保持する。各演算回路Ｄは、動作クロック毎に、
それぞれに接続されているバッファＣより出力された４
個のデータの縮小処理を行い、１個のデータを出力す
る。このときの縮小処理は、例えば、４個のデータを加
算平均した値を出力したり、あるいは、４個の内３個の
データを間引いて残り１個のデータを出力したりしても
よい。

【００４１】一致度演算回路１１は、基準パターン４
（図１１参照）を記憶する１６×１６個のメモリＥと、
部分画像３と基準パターン４との画素間の一致度を算出
する１６×１６個の演算回路Ｆ（図１中Ｆ₀₀〜Ｆ_ffにて
示される）と、演算回路Ｆの結果を集計する演算回路Ｇ
とを有している。演算回路Ｆは、動作クロック毎に、演
算回路Ｄから出力されたデータとメモリＥとの各画素間
において、正規化相関値、あるいは、濃度差加算値の演
算を行う。演算回路Ｇは、動作クロック毎に、演算回路
Ｆの演算結果を集計し、部分画像３と基準パターン４と
の一致度を算出する。また、一致度が高い画素の座標を
ソートしながら記憶していくことにより、認識対象画像
２の全ての部分画像３に対する処理が終了後、目的の対
象物の位置を早く検索することができる。

【００４２】次に、図２に示すフローチャートにしたが
って、本装置によるパターンマッチングの処理手順につ
いて説明する。

【００４３】本処理手順では、パターンマッチング処理
を行う前に、ＣＣＤカメラ６から入力した認識対象画像
２の中から探索するための基準となるパターンをあらか
じめ登録しておく。例えば、ＣＣＤカメラ６から入力し
た認識対象画像２が、図７に示すように形状‘ア’、形
状‘イ’、形状‘ウ’などから構成された画像であり、
その画像中から形状‘ア’というパターンを探索したい
場合、図６に示すように、形状‘ア’のパターンを基準
パターン１として登録しておく。

【００４４】また、例えば、パターンマッチングすると
きの縮小率が縦横それぞれ１／４の場合、図１１に示す
ように、基準パターン１に対し縦横それぞれ１／４に縮
小した基準パターン４を、本パターンマッチング処理を
行う前にあらかじめ作成し、一致度演算回路１１のメモ
リＥに記憶しておく。このとき、基準パターン１の画像
の大きさが６４×６４画素の場合、基準パターン４の画
像の大きさは１６×１６画素になる。

【００４５】上記の基準パターン１を縮小する方法とし
ては、縮小の単位となる４×４画素の画像データの加算
平均を取ってもよいし、４×４の画像データの中の一部
のデータのみ参照（その他のデータを間引く）してもよ
い。本実施形態では、以下、４×４画素の加算平均を取
った場合の説明を行う。

【００４６】本処理では、まず、ＣＣＤカメラ６から認
識対象画像２を入力する（図２のＳ１参照）。ＣＣＤカ
メラ６から出力される映像信号はアナログ信号なので、
Ａ／Ｄ変換器７によりディジタル信号に変換され、図５
に示される各画素の濃度値を表す画像データＩ（ｘ，
ｙ）がラスタ順に出力される。

【００４７】次に、部分画像３を発生させる動作につい
て説明する。まず、図８に示すような、認識対象画像２
の（ｘ，ｙ）＝（０，０）の位置が当該部分画像の左上
座標になるような部分画像３を発生させる。認識対象画
像２の座標（０，６３）の位置の画像データＩ（０，６
３）が部分画像生成手段８に入力されたとき、部分画像
生成手段８のラインバッファＡ₆₂からは、Ｉ（０，６
３）の１ライン前の画像データＩ（０，６２）が出力さ
れる。同様に、各ラインバッファＡから、Ｉ（０，６
１）、Ｉ（０，６０）、…、Ｉ（０，０）の画像データ
が出力される。したがって、このとき、部分画像生成手
段８の６４個の出力からは、左上座標が（０，０）の部
分画像３に対して、左から縦１ライン目の画像データが
同時に出力されることになる。

【００４８】また、次の動作クロックで、認識対象画像
２の（１，６３）の位置の画像データＩ（１，６３）が
部分画像生成手段８に入力されるが、このときの、部分
画像生成手段８の出力は、部分画像３の左から縦２ライ
ン目の画像データＩ（１，０）〜Ｉ（１，６３）にな
る。以降、動作クロック毎に、部分画像３の左から縦３
ライン目、縦４ライン目、縦５ライン目、…、縦６４ラ
イン目の画像データが部分画像生成手段８から出力され
るので、これらの画像データを合わせると、左上座標が
（０，０）の部分画像３になる（図２のＳ２参照）。

【００４９】同様に、左上座標が（ｘ，ｙ）の部分画像
３を発生させる場合、認識対象画像２の座標（ｘ，ｙ＋
６３）の位置の画像データＩ（ｘ，ｙ＋６３）が部分画
像生成手段８に入力されたときから、認識対象画像２の
（ｘ＋６３，ｙ＋６３）の位置の画像データＩ（ｘ＋６
３，ｙ＋６３）が部分画像生成手段８に入力されたとき
までの間に部分画像生成手段８から出力される画像デー
タを合わせるとよい。したがって、この処理を、認識対
象画像２のｘ＝０〜４４８，ｙ＝０〜４１６に対して行
うと、図９に示すように、部分画像３を認識対象画像２
の中で少しずつずらしながら認識対象画像２全体を走査
することができる。

【００５０】次に、左上座標が（ｘ，ｙ）の部分画像３
の縮小画像を作成するときの動作を説明する。認識対象
画像２の（ｘ，ｙ＋６３）の位置の画像データＩ（ｘ，
ｙ＋６３）が部分画像生成手段８に入力されたとき、部
分画像生成手段８からＩ（ｘ，ｙ）〜Ｉ（ｘ，ｙ＋６
３）の画像データが出力される。このデータは、左上座
標が（ｘ，ｙ）の部分画像３の左から縦１ライン目の６
４画素の画像データに相当する。このとき、各演算回路
Ｂでは入力された画像データについて４画素単位に加算
平均を求め、次の式で表される画像データを出力する。

【００５１】I'(0,j)=｛I(x,y+4j)+I(x,y+4j+1)+I(x,y+
4j+2)+I(x,y+4j+3) ｝／４ただし、ｊ＝０、１、２、…、15 以降、動作クロック毎に、各演算回路Ｂから出力される
画像データは、左上座標が（ｘ，ｙ）の部分画像３の左
から縦ｉライン目の画像データを１／４縮小した１６個
の画像データに相当する。このとき、各演算回路Ｂから
出力される画像データは次の式で表される。

【００５２】I'(i,j)=｛I(x+i,y+4j)+I(x+i,y+4j+1)+I
(x+i,y+4j+2)+I(x+i,y+4j+3) ｝／４ただし、ｉ＝０、１、２、…、63 ｊ＝０、１、２、…、15 つまり、図２のＳ３に示すように、部分画像３が垂直方
向に１／４縮小されることとなる。

【００５３】バッファＣは６３個直列に並んだものが１
６組並列に配置されており、動作クロック毎に、保持し
ている１画素分の画像データを、その右側のバッファＣ
へ移動させる。したがって、各演算回路Ｂから出力され
る画像データを、６３クロック分だけ保持している。

【００５４】各演算回路ＢからＩ'(63，ｊ）の画像デー
タが出力されたときに、各演算回路Ｄに対して、Ｉ'
(ｉ，ｊ）、ｉ＝０、１、…、６３の画像データが入力
される。このとき、各演算回路Ｄでは入力された画像デ
ータを４個単位で加算平均を求め、次の式で表される画
像データを出力する。

【００５５】 I''(i,j) =｛I'(4i,j)+I'(4i+1,j)+I'(4i+2,j)+I'(4i+3,j) ｝／４ =｛I(x+4i,y+4j)+I(x+4i+1,y+4j)+I(x+4i+2,y+4j)+I(x+4i+3,y+4j) +I(x+4i,y+4j+1)+I(x+4i+1,y+4j+1)+I(x+4i+2,y+4j+1)+I(x+4i+3,y+4j+1) +I(x+4i,y+4j+2)+I(x+4i+1,y+4j+2)+I(x+4i+2,y+4j+2)+I(x+4i+3,y+4j+2) +I(x+4i,y+4j+3)+I(x+4i+1,y+4j+3)+I(x+4i+2,y+4j+3)+I(x+4i+3,y+4j+3) ｝／16 ただし、ｉ＝０、１、２、…、15 ｊ＝０、１、２、…、15 上の式から明らかなように、各演算回路Ｄから出力され
る画像データI''(ｘ，ｙ）は、左上座標が（ｘ，ｙ）の
部分画像３を、４×４画素の加算平均により縮小した画
像になる（図２のＳ４参照）。

【００５６】したがって、認識対象画像２の（ｘ＋６
３，ｙ＋６３）の位置の画像データＩ（ｘ＋６３，ｙ＋
６３）が部分画像生成手段８に入力されたとき、各演算
回路Ｄから左上座標が（ｘ，ｙ）の部分画像３を縦横１
／４縮小した縮小画像が出力され、同様に、次の動作ク
ロックでは、認識対象画像２の（ｘ＋６４，ｙ＋６３）
の位置の画像データＩ（ｘ＋６４，ｙ＋６３）が部分画
像生成手段８に入力されたとき、各演算回路Ｄから左上
座標が（ｘ＋１，ｙ）の部分画像３を縦横１／４縮小し
た縮小画像が出力される。以降、動作クロック毎に、認
識対象画像２中で１画素ずつずらした位置の部分画像３
を縮小した縮小画像が各演算回路Ｄから出力されること
になる。

【００５７】次に、各演算回路Ｆでは、各演算回路Ｄの
出力とメモリＥに記憶されている基準パターン４との一
致度を算出する。この算出方法は、前記した式（１）の
濃度差加算値により求めてもよいし、前記した式（２）
の正規化相関係数により求めてもよい。

【００５８】演算回路Ｇでは、各演算回路Ｆで求めた一
致度を集計し、部分画像３の縮小画像と基準パターン４
との一致度を算出する（図２のＳ５参照）。また、それ
ぞれの位置での部分画像３の縮小画像と基準パターン４
との一致度を記憶したり、あるいは、一致度が高い順に
その座標を記憶する。

【００５９】最後に、Ａ／Ｄ変換器７から認識対象画像
２の（５１１，４７９）の位置の画像データＩ（５１
１，４７９）が入力された段階で、図９に示すように、
認識対象画像２全体での部分画像３の走査が終わり、演
算回路Ｇに記憶された一致度と座標のデータから、求め
るパターンの位置と一致度、あるいは、認識対象画像２
中に存在するパターンの個数を求めることができる（図
２のＳ６参照）。

【００６０】以上のように、本実施形態のパターンマッ
チング装置では、ある基準パターン１に対してこれと一
致するパターンが認識対象画像２の中に存在するか否か
を調べるために、認識対象画像２から基準パターン１の
比較対象となる部分画像３を順次シフトさせつつ生成す
る部分画像生成手段８と、部分画像３を垂直方向に縮小
し垂直縮小画像を生成する画像垂直縮小手段９と、垂直
縮小画像を水平方向に縮小し部分画像３の縮小画像を生
成する画像水平縮小手段１０と、部分画像３の縮小画像
と縮小された基準パターン４との一致度を算出する一致
度演算回路１１とを備えている。

【００６１】これによって、従来の方法を採る装置に比
較して、基準パターン１と一致するパターンが認識対象
画像２の中に存在する場合に、その位置をより精度良く
検出することができる。例えば、従来のピラミッド法に
より縦横それぞれ１／４に縮小した画像でのパターンマ
ッチングを行った場合、縮小画像５（図１２参照）の部
分画像は、元の画像である認識対象画像２に対応する部
分画像３としては、縦横それぞれ４画素単位になり、精
度が良くない。

【００６２】これに対して、本実施形態では、部分画像
３の縮小画像と、縮小された基準パターン４とによって
パターンマッチングを行うことで、基準パターン１と一
致する認識対象画像２の位置をより精度良く検出するこ
とができる。

【００６３】また、上記構成とすることで、比較的小さ
な回路規模でのハードウェア化が容易になり、ＣＣＤカ
メラ６からの映像信号をリアルタイム処理することが可
能になる。

【００６４】

【発明の効果】請求項１の発明に係るパターンマッチン
グ装置は、以上のように、基準パターンの比較対象とな
る認識対象画像の部分画像を、該認識対象画像に対し所
定の位置ずつずらしながら順次生成する部分画像生成手
段と、前記部分画像を垂直方向または水平方向のいずれ
か一方の方向に縮小し第１の縮小画像を生成する第１画
像縮小手段と、前記第１の縮小画像を垂直方向または水
平方向のいずれかで前記一方の方向とは異なる方向に縮
小し、前記部分画像の縮小画像を生成する第２画像縮小
手段と、前記部分画像の縮小画像と、前記部分画像と同
程度に縮小された前記基準パターンとの一致度を算出す
る一致度演算手段とを備える構成である。

【００６５】これにより、基準パターンと一致するパタ
ーンが存在する認識対象画像の位置をより精度良く検出
することができる。また、演算処理を比較的小さな回路
規模でハードウェア化することができ、ＣＣＤカメラ等
からの映像信号をリアルタイム処理することが可能にな
る。したがって、より高速にパターンマッチング処理を
行うことができる。

【００６６】請求項２の発明に係るパターンマッチング
装置は、以上のように、請求項１の構成に加えて、前記
認識対象画像を撮像する撮像素子と、前記撮像素子から
のアナログ映像信号をディジタル信号に変換するＡ／Ｄ
変換手段とを備える構成である。

【００６７】これにより、ＣＣＤカメラ等からのアナロ
グ映像信号を、動作クロックによるサンプリングと量子
化によりディジタル信号に変換すると共に、動作クロッ
ク毎に例えば１画素ずつ位置をシフトさせつつ部分画像
を順次発生させ、動作クロック毎にその部分画像と基準
パターンとの一致度を演算するリアルタイム処理が可能
になる。

【図面の簡単な説明】

【図１】本発明の実施の一形態に係るパターンマッチン
グ装置の概略的構成を示すブロック図である。

【図２】上記パターンマッチング装置によるパターンマ
ッチング処理を示すフローチャートである。

【図３】ノンインターレース型のＣＣＤカメラから出力
される映像信号の走査方向を説明する図である。

【図４】インターレース型のＣＣＤカメラから出力され
る映像信号の走査方向を説明する図である。

【図５】動作クロックによるサンプリングと量子化によ
りディジタル信号に変換された画像データを説明する図
である。

【図６】基準パターンを示す説明図である。

【図７】認識対象画像を示す説明図である。

【図８】認識対象画像における部分画像を示す説明図で
ある。

【図９】部分画像の走査方法を説明する図である。

【図１０】従来技術のピラミッド法によるパターンマッ
チング処理を示すフローチャートである。

【図１１】縮小された基準パターンを示す説明図であ
る。

【図１２】上記ピラミッド法において用いられる認識対
象画像の縮小画像を示す説明図である。

【図１３】従来技術の特徴点抽出法によるパターンマッ
チング処理を示すフローチャートである。

【図１４】上記ピラミッド法において、基準パターンの
縮小する単位の取り方によってパターンの形状に多少の
差異を生じることを示す説明図である。

【図１５】上記ピラミッド法において、縮小率を上げる
ほど元の画像との差異が大きくなることを示す説明図で
ある。

【符号の説明】

１基準パターン２認識対象画像３部分画像４縮小された基準パターン６ＣＣＤカメラ（撮像素子）７Ａ／Ｄ変換器（Ａ／Ｄ変換手段）８部分画像生成手段９画像垂直縮小手段（第１画像縮小手段）１０画像水平縮小手段（第２画像縮小手段）１１一致度演算回路（一致度演算手段）

Claims

【特許請求の範囲】

【請求項１】対象物の基準パターンと、入力された認識
対象画像とのパターンマッチングを行うパターンマッチ
ング装置において、前記基準パターンの比較対象となる前記認識対象画像の
部分画像を、該認識対象画像に対し所定の位置ずつずら
しながら順次生成する部分画像生成手段と、前記部分画像を垂直方向または水平方向のいずれか一方
の方向に縮小し第１の縮小画像を生成する第１画像縮小
手段と、前記第１の縮小画像を垂直方向または水平方向のいずれ
かで前記一方の方向とは異なる方向に縮小し、前記部分
画像の縮小画像を生成する第２画像縮小手段と、前記部分画像の縮小画像と、前記部分画像と同程度に縮
小された前記基準パターンとの一致度を算出する一致度
演算手段とを備えることを特徴とするパターンマッチン
グ装置。
【請求項２】前記認識対象画像を撮像する撮像素子と、前記撮像素子からのアナログ映像信号をディジタル信号
に変換するＡ／Ｄ変換手段とを備えることを特徴とする
請求項１記載のパターンマッチング装置。