JPH0969159A

JPH0969159A - テンプレートマッチング装置

Info

Publication number: JPH0969159A
Application number: JP22336495A
Authority: JP
Inventors: Kazumasa Kioi; 一雅鬼追
Original assignee: Sharp Corp
Current assignee: Sharp Corp
Priority date: 1995-08-31
Filing date: 1995-08-31
Publication date: 1997-03-11

Abstract

(57)【要約】【課題】探索領域が広がると、外部バスを通して転送す
る必要のあるデータ量が多くなって動作周波数を上げる
必要があるため、消費電力が増大する。【解決手段】画像メモリ１０８は、参照画像の全画素デ
ータを記憶する。演算セルアレイ１０２は、探索領域の
画素数以上の個数の演算セル１１１〜１４４からなり、
画像メモリ１０８から供給される探索領域の各画素デー
タをそれぞれ別の演算セル１１１〜１４４で記憶すると
ともに、テンプレートの画素データを逐次的に導入し
て、テンプレートマッチング処理のための演算を行う。
前記画像メモリ１０８から前記演算セル１１１〜１４４
への探索領域の画素データの供給は同一チップ内で行え
るよう形成されている。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、デジタル画像処理
における追尾システム等に用いるテンプレートマッチン
グ装置に関し、特に、処理を短時間で行うことができ、
且つ、消費電力の少ないテンプレートマッチング装置に
関する。

【０００２】

【従来の技術】図形認識等のデジタル画像処理において
は、予め定められたひな型（テンプレート）の画素デー
タと探索領域の画素データ（以下、探索データと記す）
とを照合し、何らかの基準によって類似度を判定し、探
索領域中からテンプレートに最も近い領域を検出するテ
ンプレートマッチング法がよく利用される。動画像にお
いても、このテンプレートマッチング法は画面中の移動
物体の移動距離や移動位置等を検知する際によく利用さ
れている。

【０００３】以下に、テンプレートマッチング法につい
て、探索領域（例えば、時間的に前の画像）の中からテ
ンプレート（例えば、現時点の画像）と略同一の部分を
検出する場合を例にとって説明する。尚、テンプレート
は図３（ａ）に示すようなｎ行×ｎ行の画像領域２０
１、探索領域は図３（ｂ）に示すような（ｎ＋ｋ）行×
（ｎ＋ｋ）行の画像領域２０３であるものとする。ま
た、テンプレート画像２０１中の第ｉ行第ｊ列の画素２
０２をｍ_i，_j、探索領域中の第ｇ行第ｈ列の画素２０４
をＳ_g，_hとする。

【０００４】図３（ｂ）の探索領域２０３の中には（ｋ
＋１）²個のｎ行×ｎ行の領域（以下、候補ブロックと
記す）が存在するが、この候補ブロックの内の第ｇ行第
ｈ列の画素２０４を左上隅の画素とするものをＣＢ_ghと
表す。

【０００５】テンプレートマッチング法においては、各
候補ブロック２０５が、

【０００６】

【数１】

【０００７】で定義される絶対値誤差和Ｄ_g，_hで評価さ
れ、Ｄ_g，_hの最も小さな候補ブロックが、テンプレート
２０１に最も近いものとして選択される。

【０００８】式（１）の演算では一つの候補ブロックに
対するＤ_g，_hを求めるためにｎ²回の絶対値誤差演算及
び加算を要する。したがって、テンプレートマッチング
処理においては、（ｋ＋１）²個の候補ブロックについ
てＤ_g，_hを求めるため、オーダＯ（ｎ²ｋ²）の演算量を
必要とする。このようにテンプレートマッチング処理で
は演算量が非常に多いため、動画像の実時間処理等で
は、通常、並列処理を行うテンプレートマッチング装置
が使用される。

【０００９】図１１は従来のテンプレートマッチング装
置の構成を示すブロック図である（テンプレートの画素
数が４の場合のブロック図である）。このテンプレート
マッチング装置では、入力制御部７０１の動作に基づい
て、画像メモリ７０２内の画像データが外部バス７０４
を通り、演算セル７１１，７１２，７２１，７２２、レ
ジスタ７３１に供給されて、演算が行われる。そして、
結果格納部７０４に結果が送られ、出力制御部７０５の
動作に基づいて結果が出力される。

【００１０】図１２は、図１１のテンプレートマッチン
グ装置７００を用いたテンプレートマッチング法の一例
を説明する図である。図１２において、画像データ
Ｉ₁，Ｉ₂は画像データであり、外部からＩ₁，Ｉ₂の順に
外部バス７０４を通って送られてくる。ここでは、画像
データＩ₂の一部分をテンプレートとし、画像データＩ₁
の一部分を探索領域としてテンプレートマッチングを行
う場合について説明する。

【００１１】まず、画像メモリ７５１が外部バスを通じ
て送られてきた画像Ｉ₁を記憶する（ステップ１）。

【００１２】次に、画像メモリ７５２が外部バスを通じ
て送られてきた画像Ｉ₂を記憶していく（ステップ
２）。

【００１３】そして、テンプレートデータを画像メモリ
７５２から外部バス７０４を通じてテンプレートマッチ
ング装置７００へプリロードする（ステップ３）。

【００１４】プリロードされたテンプレートに対する探
索領域のデータを画像メモリ７５１から外部バス７０４
を通じてテンプレートマッチング装置７００へ供給す
る。テンプレートマッチング装置７００はその探索領域
の中でテンプレートに最も似通った部分を算出する（ス
テップ４）。

【００１５】上記のステップ１〜ステップ４により、１
つのテンプレートに対するテンプレートマッチング処理
が行われる。画像データＩ₂すべてについてテンプレー
トマッチングを行う場合には、上記のステップ３〜ステ
ップ４を繰り返す必要がある。

【００１６】次に、テンプレートマッチング装置７００
の内部処理について具体的に説明する。ここでは、図４
（ａ）に示す入力画像（現在の画像）４０１と図５
（ａ）に示す参照画像（時間的に前の画像）５０１との
テンプレートマッチングを行うものとし、入力画像４０
１を２画素×２画素のブロックに分割し、各ブロックを
テンプレートとして処理を行うものとする。このとき、
入力画像４０１に対しては２０個のブロックが得られる
ので、２０回のテンプレートマッチングを実行すること
になる。尚、ここでは、説明を簡単にするため、図４
（ａ）に示すような水平方向１０×垂直方向８画素の画
面４０１の処理について説明するが、一般に使用される
画面はもっと画素数が多く、例えば、テレビの一規格で
あるＮＴＳＣ規格では一画面は水平７２０画素×垂直４
８０画素のものである。

【００１７】まず、入力画像４０１中のある注目ブロッ
ク４０２（図４（ａ）参照）がテンプレートの場合の処
理について説明する。ここで、探索領域は、参照画像５
０１においてテンプレート４０２と同一部分のブロック
に上下、左右方向に１画素づつ加えた領域５０２（図５
（ａ）参照）であるものとする。また、テンプレート４
０２及び探索領域５０２の各画素を、それぞれ、図４
（ｂ），図５（ｂ）に示すようにｍ₁₁〜ｍ₁₂，ｓ₁₁〜ｓ
₄₄とする。

【００１８】図６は、探索領域５０２の中の９個（（２
＋１）²個）の候補ブロックＣＢ₁₁〜ＣＢ₃₃を示す図で
ある。テンプレートマッチング法では、この９個のブロ
ックＣＢ₁₁〜ＣＢ₃₃とテンプレート４０２とを比較し、
式（１）で定義される絶対値誤差和が最も小さい候補ブ
ロックを求める。図１３〜図１８はその演算処理工程を
示す図であり、これらの図では演算セル７１１，７１
２，７２１，７２２とレジスタ７３１，結果格納部７０
４の同一時刻における状態を横一列に並べて示してい
る。

【００１９】まず、時刻ｔ＝１（図１３参照）で、入力
制御部７０１の指示に従い、テンプレート４０２の画素
データ（以下、テンプレートデータと記す）ｍ₁₁がテン
プレートマッチング装置内の演算セル７２２に入力され
る。続いて時刻ｔ＝２，３，４でｍ₂₁，ｍ₁₂，ｍ₂₂が順
にテンプレートマッチング装置内に入力される。このと
き、先に入力されていたテンプレートデータは隣の演算
セル７１２，７２１，７１１へと順次転送され、ｔ＝４
においては、テンプレート４０２のすべてのテンプレー
トデータが演算セル７１１，７２１，７１２，７２２中
に１個づつ記憶されている。

【００２０】図１４の時刻ｔ＝５以降では、図５（ｂ）
に示した探索領域５０２の画素データｓ₁₁〜ｓ₄₄が入力
制御部７０１を介して演算セル７２２に入力される。こ
のとき、演算セル７２２に新たなデータが入力される度
に、各演算セルから隣の演算セルに探索データが転送さ
れていくが、探索データの転送の場合には演算セル７１
２の次にレジスタ７３１に一旦保持されて（時刻ｔ＝７
参照）から演算セル７２１に転送（時刻ｔ＝８参照）さ
れる。これは、テンプレートと探索領域の組み合わせを
調整するためのデータバッファリングであり、テンプレ
ートと探索領域の垂直方向の画素数差によって、必要な
レジスタの個数が決まる。図１４の時刻ｔ＝８までは探
索データのローディングのみであり、実質的な演算は行
われない。

【００２１】次に、図１５に記載の時刻ｔ＝９から演算
が開始される。尚、図１５〜図１８では活性となってい
る演算セルは実践枠で記しており、図中ｄ^a _bは｜ｓ_b−
ｍ_a｜の演算結果を示している。

【００２２】時刻ｔ＝９における演算セル７２１はテン
プレートデータｍ₂₁及び探索データｓ₂₁をセル内部のレ
ジスタに記憶しており、絶対値誤差ｄ²¹ ₂₁＝｜ｓ₂₁−ｍ
₂₁｜の演算を行う。同様に、演算セル７１１は絶対値誤
差ｄ¹¹ ₁₁＝｜ｓ₁₁−ｍ₁₁｜の演算を行う。

【００２３】時刻ｔ＝１０では、演算セル７２１，７１
１での演算結果が演算セル７２２及び７１２にそれぞれ
転送される。そして、演算セル７２２は、自身のレジス
タに記憶しているｍ₂₂とｓ₂₂から得られた絶対値誤差ｄ
²² ₂₂＝｜ｓ₂₂−ｍ₂₂｜の演算を行った上で演算セル７２
１から転送されてきたｄ²¹ ₂₁との和ｄ²¹ ₂₁＋ｄ²² ₂₂を演
算する。同様に、演算セル７１２は絶対値誤差和ｄ¹² ₁₂
＝｜ｓ₁₂−ｍ₁₂｜の演算を行った上で演算セル７１１か
ら転送されてきたｄ¹¹ ₁₁との和ｄ¹¹ ₁₁＋ｄ¹² ₁₂を演算す
る。

【００２４】時刻ｔ＝１１において、上記の演算セル７
１１，７１２での演算結果が結果格納部７０４に転送さ
れる。そして、それらが加算されて絶対値誤差和Ｄ₁，₁
が得られる。この絶対値誤差和Ｄ₁，₁は図６で示した候
補ブロックＣＢ₁₁と図４（ｂ）に示したテンプレート４
０２との絶対値誤差和である。

【００２５】演算セル７１１，７２１，７１２，７２
２，結果格納部７０４では、時刻ｔ＝１１以降も上記と
同様の処理が行われ、図１６，図１７に示すように、各
候補ブロックに対する絶対値誤差和が求められる。そし
て、ｔ＝２１においてすべての絶対値誤差和が得られ
る。これらの絶対値誤差和の比較を行うことにより、テ
ンプレート４０２に最も近い候補ブロックを知ることが
できる。

【００２６】図１８に示すｔ＝２２〜２５では、演算セ
ル７１１，７２１，７１２，７２２中の探索データを排
出する操作が行われ、演算は実行されない。

【００２７】上記した図１３〜図１８の処理により、テ
ンプレート４０２に対するテンプレートマッチングが行
われる。従って、図４（ａ）の入力画像４０１全体で
は、図１３〜図１８の処理をテンプレートの個数回（２
０回）行う必要がある。

【００２８】

【発明が解決しようとする課題】図１１に示したテンプ
レートマッチング装置７００では、演算セル７１１〜７
２２が同時並列的に演算を実行するため、多くの演算を
同時に実行することができ、演算量の多いテンプレート
マッチングに適している。

【００２９】しかしながら、上記のテンプレートマッチ
ング装置では、探索データを外部バスを通じて演算セル
に逐次的に供給するため、外部バスを通過する情報量が
多いという問題がある。例えば、一画面の画素数を水平
方向ｐ画素，垂直方向ｑ画素、テンプレートの大きさを
ｎ画素×ｎ画素、探索領域の大きさを（ｎ＋ｋ）画素×
（ｎ＋ｋ）画素とすると、一画面全体についてのテンプ
レートマッチングでは、（ｎ＋ｋ）²×｛（ｐ／ｎ）×
（ｑ／ｎ）｝＝（ｎ＋ｋ）²ｐｑ／ｎ²個のデータを外部
バスを通じて転送する必要がある。一般に、１画面あた
りの処理時間は一定であるから画面の画素数および探索
領域の画素数が大きくなればなるほど、実時間処理を行
うためには動作周波数を上げる必要があり、これによ
り、消費電力が増大してしまう。

【００３０】本発明は、上記問題を解決するためになさ
れたものであって、探索領域が広がっても動作周波数を
上げる必要がなく、低消費電力で動作するテンプレート
マッチング装置を提供することを目的とする。

【００３１】

【課題を解決するための手段】請求項１に記載のテンプ
レートマッチング装置は、参照画像の全画素データを記
憶する画像記憶手段と、探索領域の画素数以上の個数の
演算器からなり、画像記憶手段から供給される探索領域
の各画素データをそれぞれ別の演算器で保持するととも
に、テンプレートの画素データを逐次的に導入して、テ
ンプレートマッチング処理のための演算を行う演算手段
と、を有してなり、画像記憶手段から演算手段への探索
領域の画素データの供給が同一チップ内で行えるよう形
成されてなるものである。

【００３２】このような構成では、参照画像の全画素デ
ータをテンプレートマッチング装置内に記憶しているた
め、外部バスを通して転送する必要のあるデータはテン
プレートの画素データのみとなる。そして、画像メモリ
から演算器への探索領域の画素データの転送を、同一チ
ップ内の複数の転送経路を用いて並列に行うため、探索
領域が広がっても動作周波数を上げる必要がなく、消費
電力を減少させることが可能となる。

【００３３】請求項２に記載のテンプレートマッチング
装置は、請求項１に記載のテンプレートマッチング装置
において、画像記憶手段が参照画像の全画素データを行
単位で記憶する複数の行記憶手段からなるものである。

【００３４】この構成では、行記憶手段が参照画像の画
素データを行単位で記憶しており、その行記憶手段から
並列に画素データを読み出すことができるため、画像記
憶手段から演算手段への同一チップ内のデータ転送にお
いて、異なる探索領域で重複する画素データの転送を省
略することが可能となる。このため、演算をより短時間
で行うことができる。

【００３５】また、請求項３に記載のテンプレートマッ
チング装置は、請求項２に記載のテンプレートマッチン
グ装置において、画像記憶手段と演算手段は複数のチッ
プ上に分かれて形成されており、各チップ上に少なくと
も複数の行記憶手段と探索領域の画素数以上の個数の演
算器が形成されてなるものである。

【００３６】上記構成では、テンプレートマッチング装
置を複数のチップに分けて構成しても、画像記憶手段か
ら演算手段へのデータ転送を同一チップ内で行うように
することができる。このため、参照画像の画素数が多
く、１チップ内に演算手段と画像記憶手段を集積化する
ことができない場合でも、低消費電力で動作させること
が可能となる。

【００３７】

【発明の実施の形態】以下、本発明のテンプレートマッ
チング装置の実施形態について説明する。

【００３８】図１は本発明のテンプレートマッチング装
置の一構成例を示すブロック図である（探索領域の画素
数が１６以下の場合の一構成例を示すブロック図であ
る）。本テンプレートマッチング装置は１チップで構成
されており、画像メモリ（特許請求の範囲における画像
記憶手段）１０８，演算セルアレイ（特許請求の範囲に
おける演算手段）１０２，結果格納部１０５，入出力制
御部１０６からなっている。画像メモリ１０８は複数の
行メモリ（特許請求の範囲における行記憶手段）１０１
からなっており、一画面の画素データを行単位で記憶し
ている。入出力制御部１０６は、外部バス１０７とのデ
ータの入出力を制御するものである。演算セルアレイ１
０２は演算セル（特許請求の範囲における演算器）１１
１〜１４４からなっている。

【００３９】図２は、上記構成のテンプレートマッチン
グ装置を用いたテンプレートマッチング法の一例を説明
する図である。図２において、Ｉ₁，Ｉ₂は画像データで
あり、外部からＩ₁，Ｉ₂の順に外部バス１０７を通って
送られてくる。以下、画像データＩ₂の一部分をテンプ
レートとし、画像データＩ₁の一部分を探索領域とし
て、２つのテンプレートマッチング装置１００ａ，１０
０ｂを使用してテンプレートマッチングを行う場合につ
いて説明する。

【００４０】まず、外部バス１０７を通って送られてき
た画像データＩ₁のデータを入出力制御部１０６ａを介
して画像メモリ１０８ａに記憶する（ステップ１）。

【００４１】次に、画像データＩ₂のデータを、入出力
制御部１０６ｂを介して画像メモリ１０８ｂに記憶する
（ステップ２）。

【００４２】テンプレート（画像データＩ₂の一部分）
に対応する探索データ（画像データＩ₁の一部分）を、
入出力制御部１０６ａの指示に基づいて、テンプレート
マッチング装置１００ａの画像メモリ１０８ａから演算
セルアレイ１０２ａにプリロードする（ステップ３）。

【００４３】テンプレートデータを、入出力制御部１０
６ａ，１０６ｂの指示に基づいて、テンプレートマッチ
ング装置１００ｂの画像メモリ１０８ｂから外部バス１
０７を介してテンプレートマッチング装置１００ａに供
給し、テンプレートマッチング装置１００ａの演算セル
アレイ１０２ａにおいてテンプレートに最も似通った探
索領域の部分を算出する（ステップ４）。

【００４４】上記のステップ１〜ステップ４により、１
つのテンプレートに対するテンプレートマッチング処理
が行われる。画像データＩ₂の一画面全体についてテン
プレートマッチングを行う場合には、上記のステップ３
〜ステップ４を繰り返せばよい。このとき本実施形態で
は画像メモリ１０８を複数の行メモリ１０１としてお
り、データを行単位で記憶しているため、ステップ３に
おける探索データのプリロードにおいて、他の探索デー
タと重複する部分のプリロードを省略することが可能と
なる。このため、より短時間での演算が可能となる。

【００４５】また、本実施形態において、演算のために
外部バス１０７を通す必要のある情報量（画素数）は、
テンプレートマッチング装置１００ｂからテンプレート
マッチング装置１００ｂへ転送する必要のある画素数で
あるため、一画面を水平方向ｐ画素，垂直方向ｑ画素、
テンプレートをｎ画素×ｎ画素とすると、（ｎ×ｎ）×
｛（ｐ／ｎ）×（ｑ／ｎ）｝＝ｐｑ画素であり、従来の
ように探索領域の画素数（（ｎ＋ｋ）×（ｎ＋ｋ）画
素）には依存せず（従来：ｐｑ＋（ｎ＋ｋ）²ｐｑ／ｎ²
画素）、外部バス１０７を通す必要のある情報量を低減
させることが可能である。このため、消費電力を低減さ
せることができる。

【００４６】次に、このテンプレートマッチング装置の
内部処理について具体的に説明する。ここでは、簡単の
ため、従来例で説明した処理と同様の処理を行う場合に
ついて説明する。つまり、図４に示す１０画素×８画素
の入力画像と、図５に示す１０画素×８画素の参照画像
とのテンプレートマッチングを行う場合について説明す
る。ここで、テンプレートは２画素×２画素であり、探
索領域は４画素×４画素であるものとする。

【００４７】まず、テンプレートを図４（ａ）の４０２
とし、探索領域を参照画像５０１においてテンプレート
４０２と同一部分のブロックに上下、左右方向に１画素
づつ加えた領域５０２（図５（ａ）参照）としてテンプ
レートマッチングを行う場合について説明する。尚、テ
ンプレート４０２の各画素を図４（ｂ）に示すようにｍ
₁₁〜ｍ₂₂とし、探索領域５０２の各画素を図５（ｂ）に
示すようにｓ₁₁〜ｓ₄₄とする。

【００４８】図６は、この探索領域５０２の中の９個
（（２＋１）²個）の候補ブロックＣＢ₁₁乃至ＣＢ₃₃を
示す図である。テンプレートマッチング法では、この９
個のブロックＣＢ₁₁乃至ＣＢ₃₃とテンプレート４０２と
を比較し、式（１）で定義される絶対値誤差和が最も小
さい候補ブロックを求める。

【００４９】図７〜図９は図１のテンプレートマッチン
グ装置の処理を説明する図である。以下、これらの図に
基づいて、テンプレートマッチング装置の動作を説明す
る。尚、図８〜図９において、ｄ^a _bはテンプレートデー
タｍ_aと探索データｓ_bとの絶対値誤差｜ｓ_b−ｍ_a｜を示
しており、Ｄ_g，_hは式（１）に示した絶対値誤差和（第
ｇ行第ｈ列を左上隅とする候補ブロックとの絶対値誤差
和）を示している。

【００５０】時刻ｔ＝１〜４では、演算セル１１１〜１
４４への探索データの供給が行われる。まず、時刻ｔ＝
１において、画像メモリ１０８から、探索データｓ₁₁，
ｓ₂₁，ｓ₃₁，ｓ₄₁がそれぞれ対応する行の演算セル１１
４，１２４，１３４，１４４に入力される。続いて、時
刻ｔ＝２において、上記の演算セル１１４，１２４，１
３４，１４４内部のデータがそれぞれ演算セル１１３，
１２３，１３３，１４３に転送され、演算セル１１４，
１２４，１３４，１４４には画像メモリ１０８からそれ
ぞれ探索データｓ１２，ｓ２２，ｓ３２，ｓ４２が入力
される。時刻ｔ＝３，４においても同様に、隣の演算セ
ルへのデータの転送と、演算セル１１４，１２４，１３
４，１４４への新たなデータの入力が行われる。そし
て、時刻ｔ＝４において、すべての探索データがそれぞ
れ一つの演算セルにセットされる。

【００５１】続いて、図８に示す時刻ｔ＝５において、
演算セル１１１〜１１４及び１３１〜１３４にテンプレ
ート４０２の画素データｍ₁₁が供給され、演算セル１２
１〜１２４及び１４１〜１４４にはテンプレート４０２
の画素データｍ₂₁が供給される。そして、演算セル１１
４，１２４，１３４，１４４以外の演算セルにおいて絶
対値誤差が計算される。例えば、演算セル１１１では、
テンプレートデータｍ₁₁と探索データｓ₁₁を用いてｄ¹¹
₁₁＝｜ｓ₁₁−ｍ₁₁｜が計算される。尚、図８，図９にお
いては、活性な演算セル（演算の行われる演算セル）を
実線で囲んでいる。

【００５２】時刻ｔ＝６では、演算セル１１１〜１１４
及び１３１〜１３４にテンプレートデータｍ₁₂が供給さ
れ、演算セル１２１〜１２４及び１４１〜１４４にはテ
ンプレートデータｍ₂₂が供給される。そして、演算セル
１１１，１２１，１３１，１４１以外の演算セルにおい
て絶対値誤差が計算され、その計算結果と各演算セルの
左隣の演算セルから転送されてきたｔ＝５における演算
結果との和が計算される。

【００５３】更に、時刻ｔ＝７においては、ｔ＝６にお
ける演算結果が右隣の演算セルへ転送される。このと
き、右端の演算セル１１４，１２４，１３４，１４４か
らは結果格納部１０５への演算結果の転送が行われる。
そして、結果格納部１０５において、図６で示した候補
ブロックＣＢ₁₃及びＣＢ₃₃と図４で示したテンプレート
４０２との絶対値誤差和Ｄ₁，₃及びＤ₃，₃が得られる。

【００５４】以下、同様の手順を繰り返すことにより、
図６で示したすべての候補ブロックに対して図４で示し
たテンプレート４０２との絶対値誤差和が結果格納部１
０５において得られる。

【００５５】尚、時刻ｔ＝５からｔ＝１２までの活性な
演算セルにおいては、基本的に同一の処理を行ってい
る。例えば、時刻ｔ＝５においては隣接セルから転送さ
れてくる演算データがないため、有意な加算処理が行わ
れていないだけで、時刻ｔ＝６における演算処理を実行
するために必要な機能があれば、時刻ｔ＝５における処
理は実行できる。

【００５６】以上のように、本発明によれば、１チップ
内に画像メモリ１０８と演算セルアレイ１０２を含んで
いるため、探索データ５０２は外部バス１０７を介する
ことなく演算セル１１１〜１４４に供給される。このた
め、低消費電力で演算を行うことが可能となる。しかし
ながら、参照画面の画素数が増大すると、１チップ内に
画像メモリ１０８と演算セルアレイ１０２を形成するこ
とが困難になる。

【００５７】上記のような場合、テンプレートマッチン
グ装置を図１０に示すように構成すればよい。すなわ
ち、画像メモリを複数の行メモリ毎に分割してそれぞれ
を別々のチップ上に形成する（図１０では３つのチップ
Ｔ₁〜Ｔ₃上に形成されている）。そして、各チップ上に
探索領域の画素数以上の演算セルを形成して、画像メモ
リから演算セルへの探索データの転送は同一チップ内で
行うようにする。この構成により、チップ間でデータ転
送を行う必要のあるものは絶対値誤差和を求めるための
部分和だけであるので、探索データ５０２をチップ間で
転送する必要は生じない。また、探索範囲を大きくした
場合においても、外部バスを介して転送する必要のある
情報量は変わらないため、実時間処理を行う際にも動作
周波数を高くする必要はなく、消費電力を低減すること
ができる。尚、図１０においては、入出力制御部１０６
と結果格納部１０５は省略している。

【００５８】

【発明の効果】請求項１に記載のテンプレートマッチン
グ装置では、画像メモリに一画面分の画素データを記憶
し、同一チップ内で探索領域の画素データの転送を行う
ため、外部バスを介して探索データを転送する必要がな
い。このため、探索領域の画素数が多くなっても動作周
波数を大きくする必要がないため、消費電力を低減する
ことができる。

【００５９】また、請求項２に記載のテンプレート装置
では、画像メモリが行メモリとなっているため、画像メ
モリから演算セルアレイへのプリロードを効率よく行う
ことができ、処理を高速化することができる。

【００６０】更に、請求項３に記載のテンプレートマッ
チング装置によれば、テンプレートマッチング装置を複
数のチップに分けて構成しても、画像メモリから演算セ
ルへのデータ転送を同一チップ内で行うようにすること
ができる。このため、参照画像の画素数が多く、１チッ
プ内に画像メモリと演算セルアレイを構成することがで
きない場合でも、低消費電力で動作させることが可能と
なる。

【図面の簡単な説明】

【図１】本発明のテンプレートマッチング装置の一構成
例を示すブロック図である。

【図２】テンプレートマッチング法の一例を説明する図
である。

【図３】テンプレート及び探索データを説明する図であ
る。

【図４】入力画像の一例を示す図である。

【図５】参照画像の一例を示す図である。

【図６】候補ブロックを示す図である。

【図７】図１のテンプレートマッチング装置の処理過程
（ｔ＝１〜４）を説明する図である。

【図８】図１のテンプレートマッチング装置の処理過程
（ｔ＝５〜９）を説明する図である。

【図９】図１のテンプレートマッチング装置の処理過程
（ｔ＝１０〜１２）を説明する図である。

【図１０】複数チップに形成されたテンプレートマッチ
ング装置の一構成例を示すブロック図である。

【図１１】従来のテンプレートマッチング装置の構成を
示すブロック図である。

【図１２】従来のテンプレートマッチング法の一例を説
明する図である。

【図１３】従来のテンプレートマッチング装置の処理過
程（ｔ＝１〜４）を説明する図である。

【図１４】従来のテンプレートマッチング装置の処理過
程（ｔ＝５〜８）を説明する図である。

【図１５】従来のテンプレートマッチング装置の処理過
程（ｔ＝９〜１３）を説明する図である。

【図１６】従来のテンプレートマッチング装置の処理過
程（ｔ＝１４〜１７）を説明する図である。

【図１７】従来のテンプレートマッチング装置の処理過
程（ｔ＝１８〜２１）を説明する図である。

【図１８】従来のテンプレートマッチング装置の処理過
程（ｔ＝２２〜２５）を説明する図である。

【符号の説明】

１０１行メモリ１０２演算セルアレイ１０５結果格納部１０６入出力制御部１０８画像メモリ１１１〜１４４演算セル４０２テンプレート５０２探索データＴ₁〜Ｔ₃ チップｍ₁₁〜ｍ₂₂ テンプレートデータｓ₁₁〜ｓ₄₄ 探索データ

Claims

【特許請求の範囲】

【請求項１】参照画像中の探索領域の画素データとテン
プレートの画素データに所定の演算を行うことにより、
前記探索領域の中から前記テンプレートと最も近い領域
を抽出するテンプレートマッチング装置において、前記参照画像の全画素データを記憶する画像記憶手段
と、前記探索領域の画素数以上の個数の演算器からなり、前
記画像記憶手段から供給される前記探索領域の各画素デ
ータをそれぞれ別の前記演算器で保持するとともに、前
記テンプレートの画素データを逐次的に導入して、前記
所定の演算を行う演算手段と、を有してなり、前記画像記憶手段から前記演算手段への前記探索領域の
画素データの供給が同一チップ内で行えるよう形成され
てなることを特徴とするテンプレートマッチング装置。
【請求項２】請求項１に記載のテンプレートマッチング
装置において、前記画像記憶手段は、前記参照画像の全画素データを前
記参照画像の行単位で記憶する複数の行記憶手段からな
ることを特徴とするテンプレートマッチング装置。
【請求項３】請求項２に記載のテンプレートマッチング
装置において、前記画像記憶手段と前記演算手段は複数のチップ上に分
かれて形成されており、各チップ上に、少なくとも複数の前記行記憶手段と前記
探索領域の画素数以上の個数の前記演算器が形成されて
なることを特徴とするテンプレートマッチング装置。