(57)【要約】【課題】マッチング対象画像とテンプレート画像との対応付けが、大きさの違いや微小な変化の影響を受けることなく効率良く行えるテンプレートマッチング方法及びそれを用いた画像処理装置を提供することにある。【解決手段】テンプレート処理部４は、マッチング対象画像の輪郭線上の各画素の諸元値からマッチング対象画像側の一次元の数値列に対応する画素の全てと、予めテンプレート記憶部５で記憶してあるテンプレート画像側の一次元の数値列に対応する画素の全てとを前後の配列順序が逆転しないように対応付けるとともに、対応付けられた画素同士の数値の相違量を相違量演算手段４２で算出してその求めた相違量の総和中、最も小さな総和をマッチング判断部６へ出力する。マッチング判断部６は、テンプレート処理部４から出力される相違量と閾値とを比較してマッチング対象対象画像とテンプレート画像とが同一であるか否かを判断する。【選択図】図１
2007026320.tif 000002
【特許請求の範囲】
【請求項１】
テンプレート画像及びマッチング対象画像の輪郭線上の各画素が持つ諸元値に基づいた数値からなる一次元の数値列を用いて物体のマッチング処理を行うに当たり、テンプレート画像側の数値列に対応する画素の全てとマッチング対象画像側の数値列に対応する画素の全てとを前後の配列順序が逆転しないように対応付ける処理を行い、対応付けられた画素同士の数値の相違量を算出してその相違量の総和を求める処理を行い、求めた総和が最も小さな対応付けがテンプレート画像とマッチング対象画像とが最もマッチングしている対応付けと判断することを特徴とするテンプレートマッチング方法。
【請求項２】
最もマッチングした対応付けと判断された相違量の総和が、予め設定した閾値よりも小さければ、マッチング対象画像とテンプレート画像とが同一であると判断することを特徴とする請求項１記載のテンプレートマッチング方法。
【請求項３】
求めた総和が最も小さな対応付けがテンプレート画像とマッチング対象画像とが最もマッチングしている対応付けと判断したときの各対応付けた画素同士の相違量の分布を調べて、相違量が所定の範囲内にある対応付け数に基づいてマッチング対象画像とテンプレート画像とが同一か否かを判断する請求項１記載のテンプレートマッチング方法。
【請求項４】
上記各数値列は、画素が示す明るさの変化方向を基に算出した前記輪郭線の接線方向角度若しくは法線方向角度を配列した列であることを特徴とする請求項１乃至３の何れか記載のテンプレートマッチング方法。
【請求項５】
上記各数値例は、輪郭線の接線方向角度若しくは法線方向角度を配列した列であって、輪郭線上のある注目画素の前後の画素位置を用いて、その前後の画素が為す角度を、当該注目画素の輪郭線の接線方向角度としていることを特徴とする請求項１乃至３記載のテンプレートマッチング方法。
【請求項６】
前記相違量が接線方向角度又は法線方向角度の差分値であって、２個のベクトルで構成される角度のうち小さい方とすることを特徴とする請求項１乃至５の何れか記載のテンプレートマッチング方法。
【請求項７】
上記数値列の数値として、濃淡画像であれば輪郭線位置に対応する画素の輝度値、カラー画像であれば輪郭線位置に対応する画素のＨＬＳ値を用いることを特徴とする請求項１乃至３の何れか記載のテンプレートマッチング方法。
【請求項８】
テンプレート画像側の数値列と、マッチング対象画像側の数値列の相違量に基づいてマトリクスを作成し、このマトリクスの各段の夫々の右端の升目から左端までの升目方向へ順に注目する升目を最下段から最上段まで順次移動しながら、升目が持つ値の累積加算値が最小となる升目を辿る経路を決定する過程を有し、経路の始端となる最下段の右端の升目以外の注目升目での経路決定は、当該注目升目に対して右、右下、下において存在する升目の累積加算値を比較して決定することを特徴とする請求項１乃至３の何れか記載のテンプレートマッチング方法。
【請求項９】
注目画素の経路決定時に於いて累積加算値がマッチング判断に用いる閾値よりも大きいときに、当該累積加算値を経路決定時に比較する累積加算値から除外することを特徴とする請求項８記載のテンプレートマッチング方法。
【請求項１０】
マッチング対象画像の輪郭線を抽出する輪郭線抽出手段と、該輪郭線抽出手段で抽出した輪郭線上の各画素の諸元値からマッチング対象画像側の一次元の数値列を生成する数値列生成手段と、該数値列生成手段で生成したマッチング対象画像側の一次元の数値列に対応する画素の全てと、予め記憶してあるテンプレート画像から抽出した輪郭線上の各画素の諸元値から求めたテンプレート画像側の一次元の数値列に対応する画素の全てとを前後の配列順序が逆転しないように対応付けるとともに、対応付けられた画素同士の数値の相違量を算出してその相違量の総和を求める相違量演算手段とを備え、この相違量演算手段で求める相違量の総和に基づいて対象画像とテンプレート画像とが同一であると判断することを特徴とする画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テンプレートマッチング方法及びそれを用いた画像処理装置に関するものである。
【背景技術】
【０００２】
従来、監視用画像処理において、移動物体を検出するに当たり、一般的に良く用いられる方法としては背景差分方法がある。この背景差分方法は、図１２（ｂ）に示す移動物体が存在しない画像を背景画像として記憶しておき、逐次入力される検出用の入力画像（図１２（ａ））から背景画像を引き算して差分値を求める方法である。つまり背景画像にない物体が入力画像中に現われた場合に、差分値が０でなくなる。この、差分値が０でない領域が移動物体領域、つまりマッチング対象画像の領域であって、例えば移動中の人（図１２（ｃ）の黒部分）や車の画像が面的に抽出できる。
【０００３】
そしてこの抽出した物体が、本当に人なのか違うのかを判断する方法として、画像処理ではテンプレートマッチングが一般的に行われている（例えば特許文献１）。
【０００４】
一般的なテンプレートマッチングにおいては、テンプレート画像と入力画像から抽出した濃淡画像からなるマッチング対象画像の各画素毎の濃度値Ｉ（ｉ，ｊ）、Ｔ（ｉ，ｊ）から、下記の式１１で示す残差Ｒや式１２で示す相互相関係数Ｃ（これらを総称して「相関値」と呼ぶ）を求め、該相関値から両画像の一致度を判定している。
【０００５】
【数１】
2007026320.tif 000003
【特許文献１】特開平８−２４９４６号公報（第３−７頁、図１）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで人か否かの判断を面的なテンプレートマッチングを行うためには、抽出した物体画像の位置と大きさに、テンプレートの位置と大きさを一致させる必要がある。。しかし、位置合わせ、大きさ変化、微細な形の違いに対して面的なテンプレートマッチングでは処理時間がかかったり、また、誤検出誤判断の場合がある。
【０００７】
つまり、位置合わせは、最も相関の高いところを画像中を走査しながら探して行い、テンプレート画像の大きさについては、複数の大きさのテンプレート画像を準備しておき、同様に最も相関の高いところを画像中を走査しながら探す。この場合、入力画像から抽出するマッチング対象画像がどの程度大きさが変化しているかは不明であり、結果として様々な大きさのテンプレートを準備することになる。また、例えば０．９倍と０．８倍のテンプレートを準備していても、入力画像が０．８５倍であれば、相関値の低下となり、誤検出誤判断の可能性が増加する。
【０００８】
一方で形状の若干の変動分を吸収すべく、判断閥値を低下させると、人以外のものを人と判断してしまう可能性がある。例えば微細な形状の違いとしては、手が出ていたり、脚の開き具合や、手荷物の有無などで、抽出された人の形状が異なるが、そのままテンプレートマッチングを行うと、人ではないと判断する可能性が高くなる。
【０００９】
上述の課題について具体的に説明すると、図１３（ａ）に示すテンプレート画像の人物に比べて図１３（ｂ）に示すマッチング対象画像のように人物の脚部の隙間が少ない場合、（式１１、式１２）でマッチング処理を行う場合、相違量の最も小さくなる位置をマッチングした位置と判定する。
【００１０】
従って、図１３（ｃ）の位置でマッチングしてほしいのだが、図１３（ｃ）で示すように脚部と足先部の合計でマッチングしたはうが、相違量は少なくなるため上下方向に位置がずれることになるが、この位置でマッチングするのは間違いといえる。
【００１１】
また、図１４（ａ）に示すテンプレート画像の人物に比べて図１４（ｂ）で示すマッチング対象画像の人物がテンプレート画像の人物に比べて面積比で約２倍（寸法比で約√２倍）大きい場合に、図１４（ｃ），（ｄ）のように相違量の最も小さい位置が複数個存在するが、倍率も位置も誤っていることになる。従ってテンプレート画像として人物の大きさが１倍の画像から１．５倍までの画像を０．１倍刻みで準備していても、わずかに異なる位置でマッチングしたと判断してしまう。
【００１２】
従って正しい位置でマッチングさせるには膨大な処理時間が必要になってしまうという問題がある。
【００１３】
本発明は、上述の点に鑑みて為されたもので、その目的とするところはマッチング対象画像とテンプレート画像との対応付けが、大きさの違いや微小な変化の影響を受けることなく効率良く行えるテンプレートマッチング方法及びそれを用いた画像処理装置を提供することにある。
【課題を解決するための手段】
【００１４】
上述の目的を達成するために請求項１のテンプレートマッチング方法では、テンプレート画像及びマッチング対象画像の輪郭線上の各画素が持つ諸元値に基づいた数値からなる一次元の数値列を用いて物体のマッチング処理を行うに当たり、テンプレート画像側の数値列に対応する画素の全てとマッチング対象画像側の数値列に対応する画素の全てとを前後の配列順序が逆転しないように対応付ける処理を行い、対応付けられた画素同士の数値の相違量を算出してその相違量の総和を求める処理を行い、求めた総和が最も小さな対応付けがテンプレート画像とマッチング対象画像とが最もマッチングしている対応付けと判断することを特徴とする。
【００１５】
請求項１のテンプレートマッチング方法の発明によれば、テンプレート画像と、マッチング対象画像の大きさの違いを吸収し、また微小な変化があっても影響を受けることなく、マッチング対象画像とテンプレート画像との最もマッチしている対応付けが、効率良く行える。
【００１６】
請求項２のテンプレートマッチング方法の発明では、請求項１の発明において、最もマッチングした対応付けと判断された相違量の総和が、予め設定した閾値よりも小さければ、マッチング対象画像とテンプレート画像とが同一であると判断することを特徴とする。
【００１７】
請求項２のテンプレートマッチング方法の発明によれば、テンプレート画像とマッチング対象画像との大きさの違いを吸収し、また微小な変化があっても影響を受けることなく、マッチング対象画像とテンプレート対象画像とのマッチング判断が正確に行える。
【００１８】
請求項３のテンプレートマッチング方法の発明では、請求項１の発明において、求めた総和が最も小さな対応付けがテンプレート画像とマッチング対象画像とが最もマッチングしている対応付けと判断したときの各対応付けた画素同士の相違量の分布を調べて、相違量が所定の範囲内にある対応付け数に基づいてマッチング対象画像とテンプレート画像とが同一か否かを判断することを特徴とする。
【００１９】
請求項３のテンプレートマッチング方法の発明によれば、相違量の分布状態を用いることにより、相違量の総和によるマッチング判断に加えて、マッチング判断の確度を高めることができる。
【００２０】
請求項４のテンプレートマッチング方法では、請求項１乃至３の何れかの発明において、上記各数値列は、画素が示す明るさの変化方向を基に算出した前記輪郭線の接線方向角度若しくは法線方向角度を配列した列であることを特徴とする。
【００２１】
請求項４のテンプレートマッチング方法の発明によれば、凹凸の少ない輪郭について、微分フィルタを適用するだけで容易に接線或いは法線方向を算出できる。
【００２２】
請求項５のテンプレートマッチング方法の発明では、請求項１乃至３の何れかの発明において、上記各数値例は、輪郭線の接線方向角度若しくは法線方向角度を配列した列であって、輪郭線上のある注目画素の前後の画素位置を用いて、その前後の画素が為す角度を、当該注目画素の輪郭線の接線方向角度としていることを特徴とする。
【００２３】
請求項５のテンプレートマッチング方法の発明によれば、凹凸の激しい画像に対して適切なマッチング処理が行える。
【００２４】
請求項６のテンプレートマッチング方法の発明では、請求項１乃至５の何れかの発明において、前記相違量が接線方向角度又は法線方向角度の差分値であって、２個のベクトルで構成される角度のうち小さい方とすることを特徴とする。
【００２５】
請求項６のテンプレートマッチング方法の発明によれば、数値によっては複数の差分確度を一意に表現でき、そのため正しくマッチング判断ができる。
【００２６】
請求項７のテンプレートマッチング方法の発明では、請求項１乃至３の何れかの発明において、上記数値列の数値として、濃淡画像であれば輪郭線位置に対応する画素の輝度値、カラー画像であれば輪郭線位置に対応する画素のＨＬＳ値を用いることを特徴とする。
【００２７】
請求項７のテンプレートマッチング方法の発明によれば、人の頭髪部や肌色を用いた人検出や、逐次入力される入力画像中から特定の人を追跡する場合などに有効となる。
【００２８】
請求項８のテンプレートマッチング方法の発明では、請求項１乃至３の何れかの発明において、テンプレート画像側の数値列と、マッチング対象画像側の数値列の相違量に基づいてマトリクスを作成し、このマトリクスの各段の夫々の右端の升目から左端までの升目方向へ順に注目する升目を最下段から最上段まで順次移動しながら、升目が持つ値の累積加算値が最小となる升目を辿る経路を決定する過程を有し、経路の始端となる最下段の右端の升目以外の注目升目での経路決定は、当該注目升目に対して右、右下、下において存在する升目の累積加算値を比較して決定することを特徴とする。
【００２９】
請求項８のテンプレートマッチング方法の発明によれば、決定した経路がテンプレート画像とマッチング対象画像とが最もマッチングしている対応付けを示すことになり、相違量の総和を求める際の処理時間の短縮が図れる。
【００３０】
請求項９のテンプレートマッチング方法の発明では、請求項８の発明において、注目画素の経路決定時に於いて累積加算値がマッチング判断に用いる閾値よりも大きいときに、当該累積加算値を経路決定時に比較する累積加算値から除外することを特徴とする。
【００３１】
請求項９のテンプレートマッチング方法の発明によれば、更なる処理時間の短縮が図れる。
【００３２】
請求項１０の画像処理装置の発明では、マッチング対象画像の輪郭線を抽出する輪郭線抽出手段と、該輪郭線抽出手段で抽出した輪郭線上の各画素の諸元値からマッチング対象画像側の一次元の数値列を生成する数値列生成手段と、該数値列生成手段で生成したマッチング対象画像側の一次元の数値列に対応する画素の全てと、予め記憶してあるテンプレート画像から抽出した輪郭線上の各画素の諸元値から求めたテンプレート画像側の一次元の数値列に対応する画素の全てとを前後の配列順序が逆転しないように対応付けるとともに、対応付けられた画素同士の数値の相違量を算出してその相違量の総和を求める相違量演算手段とを備え、この相違量演算手段で求める相違量の総和に基づいて対象画像とテンプレート画像とが同一であると判断することを特徴とする。
【００３３】
請求項１０の画像処理装置の発明によれば、テンプレート画像と、マッチング対象画像の大きさの違いを吸収し、また微小な変化があっても影響を受けることなく、画像マッチング対象画像とテンプレート画像との最もマッチしている対応付けが効率良く行え、テンプレート画像とマッチング対象画像との同一判断正確に行える画像処理装置を提供できる。
【発明の効果】
【００３４】
本発明のテンプレートマッチング方法及びそれを用いた画像処理装置は、テンプレート画像と、マッチング対象画像の大きさの違いを吸収し、また微小な変化があっても影響を受けることなく、画像マッチング対象画像とテンプレート画像との最もマッチしている対応付けが、効率良く行えるという効果がある。
【発明を実施するための最良の形態】
【００３５】
図１（ａ）は本発明の実施形態の人検出に用いる画像処理装置の全体構成を示しており、この画像処理装置は、監視エリアを撮像する撮像カメラ１と、撮像カメラ１からの画像を取り込んだ後、Ａ／Ｄ変換して出力する画像入力部２と、この画像入力部２で２値化された入力画像と予め監視エリアを撮像して記憶している背景画像との差分から背景画像以外の領域を入力画像から抽出する領域抽出部３と、検知対象となる人体のテンプレート画像にかかるデータを記憶しているテンプレート記憶部５と、領域抽出部３で抽出された領域画像とテンプレート画像とを後述する対応付けによりマッチング処理を行うためのテンプレート処理部４と、テンプレート処理部４でのマッチング処理から抽出領域の画像（以下マッチング対象画像という）とテンプレート画像との同一判断を行うためのマッチング判断部６と、マッチング判断結果を出力する結果出力部７とで構成される。
【００３６】
ここでテンプレート記憶部５は予めテンプレート画像である人物画像の輪郭線上の各画素の前後所定番目（以下Ｎ番目とする）の座標情報を使用して算出した接線方向角度（或いは法線方向角度）からなる数値を、ある座標点の画素の数値を開始点として終点の画素の数値までを並べて形成される一次元の数値列Ａをテンプレート画像のデータとして記憶している。
【００３７】
領域抽出部３は、背景画像と入力画像との差分、つまり背景差分によってマッチング対象画像を抽出し２値化処理してからテンプレート処理部４へ出力しているが、必ずしも背景差分である必要はなく、マッチング対象領域が抽出できる方法であれば他の方法でも良い。例えば、ステレオ視によって得られる３次元距離画像において、カメラから或る距離までの物体を切り出せば、容易に２値化されたマッチング対象画像が得られる。
【００３８】
テンプレート処理部４は、図１（ｂ）に示すように領域抽出部３で抽出され、２値化されたマッチング対象画像の輪郭線を抽出する輪郭線抽出手段４０と、輪郭線抽出手段４０で抽出された輪郭線上の各画素毎に、後述する方法により接線方向角度からなる数値を求め、所定の位置の画素を開始点とし、終点の画素までの一次元の数値列Ｂを生成する数値列生成手段４１と、テンプレート記憶部５からの数値列Ａと数値列生成手段４１で抽出した数値列Ｂの各画素の対応付け処理と、対応付けした画素同士の数値の相違値(相違量）を算出してその算出した相違量の総和を求める処理とを行う相違量演算手段４２とからなる。
【００３９】
ここで輪郭線抽出手段４０の動作を図２に基づいて簡単に説明する。
【００４０】
先ず輪郭線抽出手段４０は、２値化されたマッチング対象画像（図２（ａ））を取り込むと、図２（ｂ）に示すように左端から走査して白画素を探索し、最初に探索された白画素ａを開始点とし、この開始点の周囲８近傍画素を反時計回りに探索し、最初の白画素（図２（ｃ）で開始点画素の左下）の画素ｂに移動する。次に右上の画素ａから移動してきたので、画素ｂの周囲８近傍画素を、図２（ｄ）に示すように上、左上、左、左下、下、右下、右順で探索して、最初の画素ｃに移動する（図２（ｅ））。この移動後、上述の場合と同様に右上の画素ｂから移動してきたので、画素ｃの周囲８近傍画素を探索し、最初の白画素ｄに移動する。以後開始点に戻るか、白画素が見つからなくなるまで繰り返すことで、図２（ｆ）に示すように白画素ａ〜ｊからなる輪郭線及びその座標列を抽出することになる。
【００４１】
このように抽出した輪郭線からマッチングに用いる数値列を数値列生成手段４１で求める方法を次に説明する。
【００４２】
本実施形態では、輪郭形状に基づく輪郭線の接線方向角度（或いは法線方向角度）を用いる方法により数値列を生成するのであるが、その一つの例としては、輪郭線の接線方向角度を輪郭線上の注目画素から前後Ｎ番目の画素位置を用いて２点の画素が為す角度を注目画素の輪郭線の接線方向角度として求める方法を採用している。
【００４３】
具体的には輪郭線抽出手段４０で抽出した図３（ｂ）に示す輪郭線座標列が入力された数値列生成手段４１は、図３（ａ）に示すように輪郭線（イ）上の所定の注目画素の前後Ｎ番目の画素の座標情報を使用して接線方向角度を算出し、その算出結果を当該画素の輪郭接線方向角度とする。
【００４４】
この場合、座標（Ｙ，Ｘ）が（１４，１２）の画素を注目画素とし、Ｎを４とした場合、注目画素の４個前の画素の座標（１６，１０）及び４個後の画素の座標（１０，１０）の座標を用いて次のように算出する。
【００４５】
ｄｘ＝Ｘ（＋Ｎ）−Ｘ（−Ｎ）＝１０−１０＝０
ｄｙ＝Ｙ（＋Ｎ）−Ｙ（−Ｎ）＝１０−１６＝−６
Ａｎｇ＝ａｔａｎ２（−ｄｘ，ｄｙ）＝ａｔａｎ２（０，１６）＝２７０度＝−９０度
となる。図３（ｂ）は注目画素（１４，１２）を中心として前後４番目の画素の座標との関係を示している。尚図３（ｂ）において、−４〜−１は注目画素から後の４番目〜１番目の画素を示し、＋１〜＋４は注目画素から前の１番目〜４番目の画素を示す。
【００４６】
図４（ａ）は、人体を撮影した画像から領域抽出部３で人体の領域を抽出した２値画像を示し、このマッチング対象画像（白部分）から輪郭線抽出手段４０により輪郭抽出を行った結果が図４（ｂ）である。数値列生成手段４１は、抽出された輪郭線画像を○印の位置から矢印方向（ロ）に画素追跡を行って、上述のような各画素の接線方向角度を算出し、この算出した結果を追跡の開始点から終点まで並べて一次元の数値列Ｂを生成するのである。尚図４（ｃ）は角度方向を示す。また表１は図４（ｂ）での輪郭線上の各画素の座標と算出した輪郭線接線方向角度の一部を示した表である。
【００４７】
【表１】
2007026320.tif 000004
【００４８】
この方法では、凹凸による急激な角度変化を吸収する方向、つまり平滑化する効果がある。換言するとノイズによる微細な凹凸変化の影響を避けられるという効果がある。
【００４９】
尚Ｎ値は大きい程微細な凹凸を無視して平滑化の効果が大きくなるので、テンプレートマッチングにおいて必要な微細構造に応じて決定される数値である。対象によって平滑化効果を可変することができる。
【００５０】
輪郭線の法線方向角度や接線方向角度を算出する方法の別の例として、輪郭線上の各画素の値（明るさ）の変化方向を基に算出する方法がある。この場合輝度値の変化する方向を算出し、変化する方向を法線方向、垂直な方向を接線方向とする。この方法の場合には、例えばソーベル微分フィルターを用いて、明るさの変化方向を抽出すれば良い。この方法によれば凹凸形状の少ない単純な形状、例えば、円、楕円、ハート型のマッチング等に有効な方法である。
【００５１】
このソーベル微分フィルターを用いる場合には、マスクサイズが３×３のソーベルフィルタＦｘ，Ｆｙを図５（ａ）に示すように用いて輪郭線上の全ての画素に適用することで、局所空間微分を行い、各画素におけるｘ方向の微分値ｄｘと、ｙ方向の微分値ｄｙとを下式により求める。但しａ〜ｉは図５（ｂ）に示すように注目画素とその８近傍の画素における画素値（濃度値）を表すものとする。
【００５２】
ｄｘ＝（ａ＋２ｄ＋ｇ）−（ｃ＋２ｆ＋ｉ）
ｄｙ＝（ａ＋２ｂ＋ｃ）−（ｇ＋２ｈ＋ｉ）
法線方向角度＝ａｔａｎ（ｄｙ／ｄｘ）
数値列Ａと数値列Ｂの対応付けにおいて対応付けた画素間の相違量を算出するに当たり、例えば数値列Ａの１番目の画素の輪郭線接線方向角度をθ１，数値列Ｂの２番目の画素の輪郭線施線方向角度θ２としたときに、画素間の相違量は、図５に示すように２つのベクトルＡ１、Ｂ２が為す角度θ１，θ２のうち、小さい方向の角度θとし、更に正数とする。算出した相違量が、後述する図８（ｃ）のマトリクスのＡ１とＢ２の交点の値となる。また数値によっては複数の表現がある差分角度を一意に表現できるので正しくマッチング評価ができるようになる。
【００５３】
例えば、
Ａ１＝１００度、Ｂ２＝２０度ならばＡ１−Ｂ２＝８０度
Ａ１＝  ２０度、Ｂ２＝１００度ならばＡ１−Ｂ２＝−８０度→２８０度→８０度
Ａ１＝  ２０度、Ｂ２＝２５０度ならばＡ１−Ｂ２＝−２３０度→１３０度
さて、上述のように数値列生成手段４１で角度による数値列が生成されると、相違値演算手段４２は、テンプレート記憶部５で記憶してある数値列Ａと数値列Ｂとを画素（要素）毎に対応付ける処理を行うとともに、対応付けた画素の数値の相違量を求め、更にその相違量の総和を求める処理を行う。この総和は領域抽出した画像と、テンプレート画像との類似度を示すことになる。
【００５４】
上述の数値列Ａ，Ｂの対応付けは数値列の伸縮を行いながら相手との対応関係を決めておき、相違量の総和が最も小さくなる対応関係を最もマッチした状態とするのである。
【００５５】
例えば、テンプレート画像に対して入力画像から抽出した領域の画像が同じ大きさで且つ類似（同一）形状である場合には各数値列Ａ，Ｂの画素同士の対応付けは、図７（ａ）に示すように１対１となる。そして両画素の数値の相違量を演算するとともにその相違量の総和を求める。この場合マッチング対象画像と、テンプレート画像とが同じ形状で場合には各相違量が０であるため、その総和は０となる。
【００５６】
一方入力画像から抽出したマッチング対象画像が、例えばテンプレート画像に対して面積比で寸法比が２倍の相似形の場合（或いは逆の場合）には、図７（ｂ）に示すように数値列Ａの各画素が数値列Ｂの２つの画素に対応させる形となる。この場合対応付けた各画素間の数値の相違量は０で、その総和も０となる。つまり相似形状の場合の大きさ違いを吸収することができる。
【００５７】
またマッチング対象画像と、テンプレート画像とが異なる形状の場合には、同じ形状部分に対応する画素については図７（ｃ）に示すように１対１で対応させることでき、その相違量は０となるが、異なる形状部分に対応する画素同士の対応（太線で示す）では、相違量が０とならない。そのため相違量の総和も０とならない。
【００５８】
ここで、本実施形態において、上述の数値列Ａ，Ｂの対応付けにおいて対応付けた画素間の相違量を累積加算してその総和（累積加算値）を求める場合、数値列Ａ，Ｂに対応する画素を総当たりさせる形で対応関係を想定し、夫々の対応関係での相違量の総和を求めて、求めた複数の総和のうち最小となる総和を用いる方法では、処理時間が膨大となる。
【００５９】
そこで、処理時間を短縮して最小となる総和を求める方法を本実施形態では採用しており、その方法を以下に説明する。
【００６０】
先ず、図８（ａ）に示す数値列Ａと、図８（ｂ）に示す数値列Ｂとの差分のマトリクスを作成すると、図８（ｃ）のようになり、このマトリクスの最下行の右端の升目から最上行の左端の升目に向かって移動しつつ、各升目の差分値を累積加算していくことは、２つの数値列Ａ，Ｂにおいて、数値列Ｂ側の或る画素は全て数値列Ａ側の何れかの画素に対応し、数値列Ａ側のある画素は全て数値列Ｂ側の何れかの要素に対応し、しかも何れの対応関係も前後の順序が逆転しない対応付けとした複数あるもののうちの一つの対応関係を示し、対応関係のある画素の数値の相違量を累積加算していることと同値である。
【００６１】
ここで図９（ｂ）に示すようにテンプレート画像αと、マッチング対象画像βとが同一である場合、数値列Ａ，Ｂの画素同士の対応関係は上述のように１対１の一つのみとなり、差分のマトリクスは図９（ａ）のようになる。そして対応した画素間の相違量に応じた輝度値として示したマトリクス画像γは図９（ｂ）に示すようになり、図９（ａ）に示すように対応関係のある画素同士の相違量（この場合は０）に対応した輝度値で示す画素を結ぶ線はマトリクス画像γの対角線Ｉとなる。
【００６２】
一方図１０に示すようにテンプレート画像αと、マッチング処理画像βとが異なる場合、例えば人検出において、テンプレート画像αには両手が存在しないものの、領域抽出の画像βには両手が存在するため、数値列Ａ，Ｂの対応付けの際に、一つの画素に複数の画素が対応付けられ、しかも相違量が０とならない対応付けが存在することになって、相違量の総和が０とならない場合には、マトリクス画像γは図示するようになり、対応付けた画素同士の相違量に対応したマトリクス画像を結ぶ線Ｉは、相違量０となる対応付けができず、輝度値が０でない画素上を通る部分（縦線部分）IIが現われることになる。
【００６３】
そこで、マトリクス画像を用いて相違量の総和(累積加算値）が最小となる経路を、次のような方法で求めるのである。
【００６４】
ここで説明を簡単にするために数値列Ａ，Ｂの各画素（要素)数を４とした場合について説明する。先ず相違量演算手段４２は、数値列Ａ，Ｂから各画素間の相違量に基づいた画素値を持つ４×４のマトリクス画像データを作り、マトリクス画像データの左上から右下までの各画素に順次画素番号を付す。図１１（ａ）はこのマトリクス画像データの内容を示す。
【００６５】
このマトリクス画像データの右下画素（１６）から最下段各画素までの最短経路を決定する。図１１（ｂ）はこの決定時の内容を示し、図において経路コストとは経路での画素値の累積和を示す。最下段の各画素における右下画素（１６）への最短経路は右方向のみである。
【００６６】
次に図１１（ｃ）に示すようにある注目する画素（例えば１１）から右、右下、下に夫々位置する画素（１２）、（１６）、（１５）における最短経路の画素値の各累積＜右では５（＝４＋１），右下では４，下では１３（＝４＋９）＞を比較して右下画素（１６）から注目画素（１１）までの最短経路を決定してその総和を求める。つまり最短経路は右下であって、その場合の画素値の累積和は４＋６＝９となる（図１１（ｄ）参照）。
【００６７】
次の注目する画素（１０）では、右、右下、下に夫々位置する画素（１１）、（１５）、（１４）における最短経路の画素値の各累積加算値９、１３、１５を比較して右下画素（１６）から注目画素（１０）での最短経路を決定してその累積和を求める。この場合最短経路は右であって、その場合の画素値の累積和は９＋１０＝１９となる（図１１（ｅ）参照）。以上のようにして順次最短経路を決定し、図１１（ｆ）に示すように左上の画素（１）までの最短経路を決定すると、その時点で左上の画素（１）から右下までの画素（１６）までの最短経路とその画素値の最小の累積和が決定していることになる。ここで画素値は数値列Ａ，Ｂの対応する画素同士の相違量に対応するものであるので、画素値の累積は相違量の総和に対応することになる。
【００６８】
尚経路は逆戻り（上、左、左上）を辿らないものことを前提とするため、注目画素が最下段の場合には最小累積和を比較する右下、下の画素が存在しないので比較するのは右の画素のみとする。また最下段の右端の画素では比較する他の画素で存在しない。また最下段でないが右端の注目画素の場合には、右に画素が存在しないので、最小累積和の比較するのは右下、下の画素とする。
【００６９】
而して本方法によれば、注目画素（升目）までの最小の累積和及びその経路を決めれば、次の注目画素の最小累積和及び経路のための計算処理を繰り返す必要がなくなり、処理時間が短縮されることになるのである。
【００７０】
尚上述の或る注目画素（升目）の最小累積和が上述のマッチング判断部６での判断に用いる閾値を超えた場合に、その注目画素について他の注目画素において、参照されるときには累積和の比較対象から外せば、計算時間の短縮化を図ることができる。
【００７１】
自身が最下段であったり右端であれば比較するべき右又は右下又は下の升目が存在しないときは、それ以外で比較する。
【００７２】
尚最小累積和を求めるための升目の移動は、上述の最下行の右端の升目から最上行の左端への移動以外に、最上行の左端の升目から最下行の右端への移動等であっても良い。
【００７３】
而して相違量演算手段４２はテンプレート画像の輪郭線上の画素に対応した数値列Ａとを、テンプレート画像側の数値列Ａに対応する画素の全てとマッチング対象画像側の数値列Ｂに対応する画素の全てとを前後の配列順序が逆転しないように対応付ける処理を行い、対応付けた画素同士の数値の相違量を求めるとともに最小となる相違量の総和を類似度が最も高いことを示すものとして、マッチング判断部６へ出力するのである。
【００７４】
マッチング判断部６は、予めテンプレート画像とマッチング対象画像とが同じであると判断するための閾値が予め設定されており、この閾値と相違量演算手段４２が出力する総和とを比較して、総和が閾値より小さい場合には、テンプレート画像とマッチング対象画像とが同一であると判断し、逆に総和が閾値より大きい場合には、同一でないと判断し、それらの判断結果を結果出力部７に出力する。結果出力部７は判断結果に応じて所定形式の結果信号を外部へ出力するのである。
【００７５】
尚上述の最短経路を求める際に累積加算値が閾値を超える注目画素がある場合、当該注目画素の累積加算値を、最短経路を求める際の比較対象から除外することで、演算処理を短縮するようにしても良い。
【００７６】
また本実施形態では、数値列Ａ，Ｂを構成する数値としては各画素の輪郭線の接線方向角度(或いは法線方向角度）を用いているが、濃淡画像を用いてその輪郭線上の画素の輝度値を数値として用いるか、或いはカラー画像の場合にはその輪郭線上のＨＬＳ値を用いても良く、前者の場合には人の頭髪部の黒、顔や手の肌色を用いた人検出に有効であり、また後者はある瞬間に検出した人画像をテンプレート画像として用い、その人の服の色や頭髪の範囲などから逐次入力されるマッチング対象画像からその人を特定して追跡する場合に有効である。この追跡の場合にはテンプレート画像となる画像を取り込んだ後、上述のような領域抽出、輪郭線抽出、更に数値列生成をマッチング処理の開始前に行い、その生成された数値列をテンプレート記憶部５に記憶させる処理を行う。
【００７７】
更に、本実施形態では、マッチング判断部６が閾値と、相違量演算手段４２から出力される相違量の総和とを比較して、マッチング対象画像がテンプレート画像と同一であるか否かを判断しているが、対応付けた数(図７で画素同士を結ぶ線の数）Ｙで相違量の総和の正規化を下式（１）のように行っても良い。この場合大きさが極端に異なる画像同士の比較において互いの類似度を正しく判断することが可能となる。更にテンプレート画像に対応した輪郭線の画素数Ｎ１と、マッチング対象画像に対応した輪郭線の画素数Ｎ２を用いて相違量の総和の値を下式（２）に示すように正規化しても同様な利点がある。
【００７８】
正規化された相違量の総和＝相違量の総和／対応付け数          …（１）
正規化された相違量の総和＝相違量の総和／（Ｎ１×Ｎ２）      …（２）
更に相違量演算手段４２で求めた全てにおける相違量の分布状態を調べて、相違量が所定の範囲内にある対応付けの数に基づいて、マッチング対象画像とテンプレート画像とが同一であるか否かを判断する方法を用いても良い。例えば対応付け数Ｙに対して相違量が所定の範囲以内（相違量が０以上５以下）の対応関係の比率が予め設定した値とを比較して同一であるか否かを判断するのである。
【図面の簡単な説明】
【００７９】
【図１】（ａ）は本発明方法を用いた画像処理装置のブロック図、（ｂ）は同上の画像処理装置のマッチング処理部のブロック図である。
【図２】同上の画像処理装置のマッチング処理部内の輪郭線抽出部の輪郭線追跡方法の説明図である。
【図３】同上の画像処理装置のマッチング処理部内の数値列生成部の接線方向角度の算出方法の説明図である。
【図４】同上の画像処理装置のマッチング処理部の具体例に対する処理動作の説明図である。
【図５】同上の画像処理装置のマッチング処理部の数値列生成部の別の角度算出方法の説明図である。
【図６】同上の画像処理装置のマッチング処理部の数値列生成部で数値列の数値として求める角度の説明図である。
【図７】同上の画像処理装置のマッチング処理部の相違量演算部の説明図である。
【図８】同上の画像処理装置のマッチング処理部の相違量演算部の総和の演算方法の説明図である。
【図９】同上の画像処理装置のマッチング処理部の相違量演算部で生成する差分マトリクスとマトリクス画像の一例の説明図である。
【図１０】同上の画像処理装置のマッチング処理部の相違量演算部で生成する差分マトリクスとマトリクス画像の他例の説明図である。
【図１１】同上の画像処理装置の累積加算値が最小となる最短経路を求める方法の説明図である。
【図１２】入力画像からマッチング対象画像を背景画像との差分で得る方法の説明図である。
【図１３】従来のテンプレートマッチングの説明図である。
【図１４】従来のテンプレートマッチングの課題説明図である。
【符号の説明】
【００８０】
１  撮像カメラ
２  画像入力部
３  領域抽出部
４  テンプレート処理部
４０  輪郭線抽出手段
４１  数値列生成手段
４２  相違量演算手段
５  テンプレート記憶部
６  マッチング判断部
７  結果出力部
【図１】
2007026320.tif 000005
【図２】
2007026320.tif 000006
【図３】
2007026320.tif 000007
【図５】
2007026320.tif 000008
【図６】
2007026320.tif 000009
【図７】
2007026320.tif 000010
【図８】
2007026320.tif 000011
【図９】
2007026320.tif 000012
【図１０】
2007026320.tif 000013
【図１１】
2007026320.tif 000014
【図１３】
2007026320.tif 000015
【図１４】
2007026320.tif 000016
【図４】
2007026320.tif 000017
【図１２】
2007026320.tif 000018