(57)【要約】【課題】高精度で高速処理が可能なパターンマッチングを実現する。【解決手段】テンプレート画像の投影加算データを求めて投影加算データによるテンプレート画像を作成する処理部４と、対象画像に対して投影加算データによるテンプレート画像を用いた正規化相関法によるパターンマッチングを行って投影加算データによるテンプレート画像と類似する領域を部分画像の候補として抽出する処理部６と、その抽出された領域に対して画素濃度データによるテンプレート画像を用いた正規化相関法によるパターンマッチングを行い、画素濃度データによるテンプレート画像との一致度が最も大きい領域を特定する処理部７を設け、投影加算データを用いた正規化相関法と画素濃度データを用いる正規化相関法のそれぞれの特徴を利用することで、処理速度の高速化と検出の高精度化を達成する。【選択図】図１
2005293152.tif 000002
【特許請求の範囲】
【請求項１】
対象画像の中からテンプレート画像と類似する部分画像を特定するパターンマッチング方法であって、テンプレート画像の投影加算データを求めて投影加算データによるテンプレート画像を作成するステップと、対象画像に対して前記投影加算データによるテンプレート画像を用いた正規化相関法によるパターンマッチングを行って前記投影加算データによるテンプレート画像と類似する領域を部分画像の候補として抽出するステップと、その抽出された領域に対して画素濃度データによるテンプレート画像を用いた正規化相関法によるパターンマッチングを行い、前記画素濃度データによるテンプレート画像との一致度が最も大きい領域を特定するステップを含むことを特徴とするパターンマッチング方法。
【請求項２】
対象画像の中からテンプレート画像と類似する部分画像を特定するパターンマッチング装置であって、テンプレート画像の投影加算データを求めて投影加算データによるテンプレート画像を作成する処理部と、対象画像に対して前記投影加算データによるテンプレート画像を用いた正規化相関法によるパターンマッチングを行って前記投影加算データによるテンプレート画像と類似する領域を部分画像の候補として抽出する処理部と、その抽出された領域に対して画素濃度データによるテンプレート画像を用いた正規化相関法によるパターンマッチングを行い、前記画素濃度データによるテンプレート画像との一致度が最も大きい領域を特定する処理部を備えていることを特徴とするパターンマッチング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、車両等の移動体追跡、同形状物体数のカウント、顔認識などの画像照合に利用されるパターンマッチング方法及びパターンマッチング装置に関する。
【背景技術】
【０００２】
車両等の移動体追跡、同形状物体数のカウント、顔認識などの画像照合において、テンプレート画像を用いてパターンマッチングを行う手法としては、画像の画素濃度を演算対象とする残差マッチングや正規化相関法が一般的に使用されている（例えば、特許文献１及び特許文献２参照。）。
【０００３】
残差マッチングは、対象画像とテンプレート画像について各画素の差の絶対値を求め、その差の絶対値の累積値（残差）が最も小さい領域をテンプレート画像と一致する部分画像として検出する方法である。
【０００４】
画像の画素濃度を用いた正規化相関法（以下、背景技術及び課題の説明では「画素濃度正規化相関法」という）は、対象画像とテンプレート画像との間において各画素の相関値を求め、その相関値が最大となる領域をテンプレート画像と一致する部分画像として検出する方法である。このような画素濃度正規化相関法においては、対象画像に対しテンプレート画像を行・列の各方向に１画素ずつ移動し、その各移動位置でマッチングを行って相関値を求めるという方法が採られている。
【特許文献１】特開平７−９８７５９号公報
【特許文献２】特開２００１−１４８０１４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上記したパターンマッチング手法のうち、残差マッチングは、画素濃度正規化相関法に比べて演算量が少なくて高速な処理が可能であるが、対象画像とテンプレート画像との差の絶対値を求める手法であり、対象画像の明るさが検出精度に大きな影響を与えるため、明度変化・変形などの外乱に弱いという欠点がある。
【０００６】
一方、画素濃度正規化相関法は、対象画像の明度変化・変形などの外乱に影響されないので検出精度が高いという利点がある。しかし、対象画像に対しテンプレート画像を行・列の各方向に１画素ずつ移動しながら相関値を求めているので、演算データ量が多くて処理速度が遅いという欠点がある。例えば、テンプレートの行方向及び列方向の各画素数をそれぞれｉ，ｊとすると、マッチング１回当たりの演算データ量は［ｉ×ｊ］個であり、これを対象画像の全域にわたって１画素ずつ移動してマッチングを行うと多くの処理時間が必要となる。
【０００７】
このような欠点を補うために、画素濃度正規化相関法においては、対象画像の画素データを一定の間隔で取り除いて相関値を求める間引き処理や、局所オペレータ（画像の局所領域で画素の濃度を決定するためのフィルタ（例えば平滑フィルタ））等を用いた多重解像度解析による探索データ量の削減が適用される場合がある。しかしながら、間引き処理による手法では、間引かれた画素に関する情報が完全に欠落するため、点や線・エッジなどの情報が失われやすいという問題がある。
【０００８】
また、演算の高速化のために対象画像の探索範囲を制限する（狭くする）ことが行われている。特に、移動体追跡の場合は移動方向などの情報を利用して移動先の推定を行い、探索範囲を狭めることが行われているが、この場合、移動先の推定が間違った場合、追跡が不能となる可能性がある。
【０００９】
なお、残差マッチングや画素濃度正規化相関法において、演算の高速化の手段として、演算の途中において残差値や相関値の演算値が所定の閾値を超えた時点で演算を打ち切るという方法が適用される場合があるが、演算打ち切りの際の閾値についての指針がなく、適用場面により経験的あるいは従来からの知見をもとに閾値が選択される場合が多く、適用範囲が限られるという問題がある。
【００１０】
本発明はそのような問題を解消するためになされたもので、パターンマッチングの精度を画素濃度正規化相関法と同程度（高精度）に維持しつつ、演算の処理速度を高速にすることが可能なパターンマッチング方法及びパターンマッチング装置の提供を目的とする。
【課題を解決するための手段】
【００１１】
本発明のパターンマッチング方法は、対象画像の中からテンプレート画像と類似する部分画像を特定するパターンマッチング方法であって、テンプレート画像の投影加算データを求めて投影加算データによるテンプレート画像を作成するステップと、対象画像に対して前記投影加算データによるテンプレート画像を用いた正規化相関法によるパターンマッチングを行って前記投影加算データによるテンプレート画像と類似する領域を部分画像の候補として抽出するステップと、その抽出された領域に対して画素濃度データによるテンプレート画像を用いた正規化相関法によるパターンマッチングを行い、前記画素濃度データによるテンプレート画像との一致度が最も大きい領域（部分画像）を特定するステップを含むことを特徴としている。
【００１２】
本発明のパターンマッチング装置は、対象画像の中からテンプレート画像と類似する部分画像を特定するパターンマッチング装置であって、テンプレート画像の投影加算データを求めて投影加算データによるテンプレート画像を作成する処理部と、対象画像に対して前記投影加算データによるテンプレート画像を用いた正規化相関法によるパターンマッチングを行って前記投影加算データによるテンプレート画像と類似する領域を部分画像の候補として抽出する処理部と、その抽出された領域に対して画素濃度データによるテンプレート画像を用いた正規化相関法によるパターンマッチングを行い、前記画素濃度データによるテンプレート画像との一致度が最も大きい領域（部分画像）を特定する処理部を備えていることを特徴としている。
【００１３】
以下、本発明を詳細に説明する。
【００１４】
本発明は、テンプレート画像と一致する部分画像を特定するにあたり、投影加算データを用いた正規化相関法によるテンプレートマッチングと、画素濃度データを用いた正規化相関法によるテンプレートマッチングとを組み合わせた点に特徴がある。このように、テンプレートマッチングに投影加算データを用いた正規化相関法を組み合わせることによる利点を以下に説明する。
【００１５】
まず、投影加算データを用いた正規化相関法では、画素濃度データを用いる正規化相関法よりも演算データ量が激減するので、処理速度が画素濃度データを用いる正規化相関法に比べて高速になるという特徴があり、従って、対象画像の探索範囲（対象画像中でマッチング処理を行う領域）を、画素濃度データを用いる正規化相関法よりも広く設定することが可能となり、高速な移動体であっても見失う可能性つまりテンプレート画像と一致する対象画像中の部分画像が見つからない可能性が低くなる。
【００１６】
また、投影加算データを用いた正規化相関法では、正規化相関の演算結果である相関値が滑らかに変化するという特徴があることから、部分画像の探索に用いる判定閾値の設定においても利点がある。
【００１７】
すなわち、画素濃度データを用いる正規化相関法では、検出精度が高いものの、一致位置で急峻な相関値の変化があるため、時系列画像などを扱うときは時間変化（対象となる物体の形状変化）に敏感であり、最大相関値の急激な変化が見られるので、一致度の判定閾値の設定が困難となる。これに対して、投影加算データを用いた正規化相関法によるパターンマッチングでは、相関値が緩やかに変化するため、多少の時間変化による画像の変化があっても一致度は比較的安定するので、判定閾値の設定が容易である。
【００１８】
そして、本発明では、これら投影加算データを用いた正規化相関法と画素濃度データを用いる正規化相関法のそれぞれの特徴を利用し、高速処理が可能な投影加算データを用いた正規化相関法によるパターンマッチングによってテンプレート画像と一致すると想定される部分画像の候補を対象画像の中から抽出し、その抽出された部分画像の中から、検出精度の高い画素濃度データを用いた正規化相関法によるパターンマッチングによって、テンプレート画像に一致する部分画像の位置を特定するという構成を採用することで、処理速度が高速で高精度の検出を行うことが可能なパターンマッチングを実現している。
【発明の効果】
【００１９】
本発明によれば、パターンマッチングにテンプレート画像の投影加算データを使用することで正規化相関の演算対象データ量の削減をはかることができ、パターンマッチングを高速に行うことができる。しかも、投影加算データを用いた正規化相関法によるパターンマッチングで候補として抽出された領域に対して、画素濃度データを用いた正規化相関法によるパターンマッチングにて部分画像を特定するので、高精度の検出が可能になる。
【００２０】
また、移動体追跡などの処理において探索範囲を広くすることができるので、追跡不能となる可能性が減少する。例えば、車両追跡の場合は画像全体に対して投影加算データを用いたパターンマッチングを行い、相関値がある一定以上存在する領域を候補として抽出する。その後、抽出された領域に対して画素濃度データを用いたパターンマッチングを行うことで高速性と高精度とを両立した車両追跡が可能となる。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の実施形態を図面に基づいて説明する。
【００２２】
図１は本発明のパターンマッチング装置の一例の構成を示すブロック図である。
【００２３】
この例のパターンマッチング装置は、対象画像を取り込む画像入力部１、Ａ／Ｄ変換処理部２、テンプレート画像作成部３、投影加算データ作成部４、データ記憶部５、候補抽出部６、検出処理部７、テンプレート設定部８及び画像表示部９などを備えている。
【００２４】
画像入力部１は、パターンマッチングを実施する対象画像などを取り込む処理部で、この画像入力部１にて取り込んだ対象画像はＡ／Ｄ変換処理部２によってＡ／Ｄ変換された後、テンプレート画像作成部３及び候補抽出部６に供給される。また、Ａ／Ｄ変換後の対象画像（デジタル画像データ）は画像表示部９に表示される。
【００２５】
テンプレート画像作成部３は、画像入力部１が取り込んだ対象画像（Ａ／Ｄ変換処理後の画像データ）の中から、テンプレート設定部８によって指定された領域をテンプレート画像として切り取る。テンプレート画像の切り取り処理は、例えば、Ａ／Ｄ変換処理後の画像データの時系列画像中から動きベクトル抽出など自動判定による切り取り範囲の決定、または、オペレータらが画像表示部９の表示画像をモニタしながら、テンプレート設定部８を操作する等の方法で実施する。このテンプレート画像作成部３にて切り取られたテンプレート画像は投影加算データ作成部４及び検出処理部７に供給される。なお、テンプレート画像は、予め作成したもの（画素濃度データ）を、画像入力部１から取り込んでテンプレート画像作成部３に入力するようにしてもよい。
【００２６】
投影加算データ作成部４は、テンプレート画像作成部３から供給されたテンプレート画像について、水平方向及び垂直方向の各方向の投影加算データを求める。
【００２７】
具体的には、図２に例示するように、テンプレート画像の水平方向（行方向）及び垂直方向（列方向）の各方向について、それぞれ、各ラインごとに画素の濃度を加算するという処理にて投影加算データを求める。その演算後の投影加算データによるテンプレート画像はデータ記憶部５に記憶される。なお、図２に示すテンプレートＴは、行方向及び列方向の各画素数ｉ，ｊがそれぞれｉ＝８，ｊ＝８であるので、投影加算データの演算データ量は［８＋８］である。
【００２８】
候補抽出部６は、画像入力部１で取り込んだ対象画像（Ａ／Ｄ変換処理後の画像データ）と、データ記憶部５に記憶されている投影加算データによるテンプレート画像を用い、その対象画像とテンプレート画像との間において各画素の相関値を求める処理つまり投影加算データを用いた正規化相関法によるパターンマッチングを行い、その投影加算データによるテンプレート画像と類似する領域（部分画像）を候補として抽出する。
【００２９】
具体的には、図３に示すように、投影加算データによるテンプレート画像（テンプレートＴ）を対象画像に対してＸ方向及びＹ方向にそれぞれ１画素ずつ移動しながら、その各移動位置でのテンプレート画像と対象画像との相関値ｒｃｃを下記の（１）式に基づいて演算し、その相関値ｒｃｃが予め設定した設定値（例えば０．８）以上となる領域を候補として抽出する。なお、この例では、水平方向の投影加算データ及び垂直方向の投影加算データの双方を用いて上記したパターンマッチングを実施する。
【００３０】
【数１】
2005293152.tif 000003
ここで、以上のような投影加算データを用いたパターンマッチングでは、マッチング１回当たりの演算データ量が［ｉ＋ｊ＝１６］個であり、画素の濃度を用いて正規化相関法にてマッチングを行った場合のマッチング１回当たりの演算データ量［ｉ×ｊ＝６４］に対して大幅に削減することができる。
【００３１】
そして、検出処理部７は、候補抽出部６にて候補として抽出された領域（部分画像）の画像データと、投影加算データ作成部４に切り出されたテンプレート画像（画素濃度データによるテンプレート画像）を用い、その各領域とテンプレート画像との間において各画素ごとの相関値ｒｃｃを前記した（１）式にて求める処理（テンプレート画像の画素濃度を用いたパターンマッチング）を行い、相関値ｒｃｃが最大となる領域つまりテンプレート画像との一致度が最も大きい部分画像の位置を特定する。
【００３２】
次に、この例のパターンマッチング装置において実施する処理の流れを図４及び図５を参照しながら説明する。
【００３３】
ステップＳ１：画像入力部１に入力された画像からテンプレート画像（画素濃度データ）を取得する。この例では図５（ａ）に示すようなテンプレート画像（車両画像）を取得する。
【００３４】
なお、テンプレート画像は処理を行う対象画像から取得してもよいし、予め取り込んでおいた画像を切り取ってテンプレート画像を取得するようにしてもよい。
【００３５】
ステップＳ２：パターンマッチングを実施する対象画像を取り込む。この例では、図５（ｂ）に示すような対象画像を取り込むものとする。
【００３６】
ステップＳ３：取得したテンプレート画像の投影加算データを演算し（図２参照）、投影加算データによるテンプレート画像を作成する。
【００３７】
ステップＳ４：投影加算データによるテンプレート画像と対象画像とのパターンマッチングを行って類似領域（部分画像）を抽出する。この例では、図５（ｃ）に示すように、３つの領域Ａ１，Ａ２，Ａ３が候補として抽出される。
【００３８】
ここで、投影加算データによるテンプレート画像を用いた正規化相関法によるパターンマッチングにおいては、図２に示すように、投影加算データの包絡線の形状がどの程度似ているかを計算していることになり、従って、多少の形状変化があっても相関値が極端に小さくはならないので、対象物体（車両）が高速移動であってもテンプレート画像と一致する領域（部分画像）が見つからない可能性は低い。
【００３９】
また、投影加算データを用いた正規化相関法によるパターンマッチングでは、画素濃度データを用いた正規化相関法によるパターンマッチングと比較して高速な処理が可能なので、探索領域（パターンマッチングを行う領域）を広く設定することができ、対象物体（車両）が高速に移動している場合でも見つけ出すことができる。
【００４０】
ステップＳ５：抽出した各領域Ａ１，Ａ２，Ａ３に対してのみ、ステップＳ１で取得したテンプレート画像とのパターンマッチング（画素濃度データを用いた正規化相関法によるパターンマッチング）を行い、テンプレート画像との一致度が最も大きい領域Ａ１（相関値が最大の領域）の位置を特定する（図５（ｄ））。
【００４１】
このように、投影加算データを用いた正規化相関法によるパターンマッチングによってテンプレート画像と一致すると想定される部分画像の候補を対象画像の中から抽出し、その抽出された複数の部分画像に対して画素濃度データを用いた正規化相関法によるパターンマッチングを行って一致度が最も大きき部分画像の位置を特定する、という手法を採用することで、処理に要する時間を大幅に短縮することができる。例えば、画素濃度データを用いた正規化相関法によるパターンマッチングのみを行う場合では処理に要する時間が１７２３５ｍｓｅｃである画像に対し、本発明では処理時間を４７ｍｓｅｃにすることができ、処理速度を高速（約３６．６倍高速）にすることができる。従って、従来よりも多くの対象物を追跡することが可能となる。また、リアルタイム性を重視するシステムなどにも適用できる。
【００４２】
なお、以上の例では、投影加算データによるテンプレート画像を作成する際に、水平方向の投影加算データ及び垂直方向の投影加算データの双方を演算し、その両者の投影加算データを正規化相関法によるパターンマッチングに用いているが、本発明はこれに限られることなく、水平方向の投影加算データまたは垂直方向の投影加算データのいずれか一方のデータのみを演算してパターンマッチングを実施するようにしてもよい。また、水平方向や垂直方向の投影加算データのほか、斜め方向の投影加算データを演算してパターンマッチングを実施するようにしてもよい。
【００４３】
また、以上の例では、本発明を車両の追跡に適用した例を示しているが、これに限られることなく、車両以外の移動物体の追跡、チップカウンタ・コロニーカウンタ等の同形状物体数のカウント、半導体のマークや欠陥等の認識あるいは顔認識などの他の各種の画像照合処理にも適用することができる。
【００４４】
ここで、本発明のパターンマッチング装置の各処理部は、専用のハードウェアで構成してもよい。また、本発明のパターンマッチング方法を実行するプログラムを、パーソナルコンピュータやワークステーションなどの汎用的なコンピュータ装置にＣＤ−ＲＯＭやＦＤ（フレキシブルディスク）などの媒体を介して読み込ませるか、あるいは、ネットワークからのダウンロードによりプログラムを読み込ませることによりパターンマッチング装置として動作させることも可能である。
【産業上の利用可能性】
【００４５】
本発明は、車両等の移動体追跡、チップカウンタ・コロニーカウンタ等の同形状物体数のカウント、顔認識などの画像照合処理において、テンプレート画像を用いてパターンマッチングを行うにあたり、高精度の検出と演算の高速化を達成するのに有効に利用することができる。
【図面の簡単な説明】
【００４６】
【図１】本発明のパターンマッチング装置の一例の構成を示すブロック図である。
【図２】テンプレート画像の投影加算データの演算処理の説明図である。
【図３】投影加算データによるテンプレートを用いた正規化相関法によるパターンマッチングの説明図である。
【図４】図１のパターンマッチング装置において実行する処理内容を示す流れ図である。
【図５】図１のパターンマッチング装置において実行する処理内容を模式的に示す図である。
【符号の説明】
【００４７】
１  画像入力部
２  Ａ／Ｄ変換処理部
３  テンプレート画像作成部
４  投影加算データ作成部
５  データ記憶部
６  候補抽出部
７  検出処理部
８  テンプレート設定部
９  画像表示部
Ａ１，Ａ２，Ａ３  領域（部分画像の候補）
Ｔ  テンプレート
【図１】
2005293152.tif 000004
【図２】
2005293152.tif 000005
【図３】
2005293152.tif 000006
【図４】
2005293152.tif 000007
【図５】
2005293152.tif 000008