(57)【要約】【課題】ウィンドウ位置がランダムな場合も対応可能な正規化相関処理装置を提供する。【解決手段】ウィンドウを格納するウィンドウバッファをダブルバッファ構成とし、各バッファに充填する矩形領域のサイズを任意に指定可能とする。ウィンドウ位置の指定がランダムで、ウィンドウ同士が大きく重なるような場合には、１つのウィンドウバッファに複数のウィンドウを格納するようにして、ウィンドウの読み出しの際に、キャッシュ効果が現れるようにする。【選択図】図２
2010113522.tif 000002
【特許請求の範囲】
【請求項１】
画像のパタンマッチング処理をするための正規化相関処理装置であって、
パタンマッチングのためのテンプレートを保持するテンプレートバッファ手段と、
探索矩形を含む矩形データの縦横サイズを任意に指定して、入力画像の前記探索矩形を含む前記矩形データを保持する複数の探索矩形バッファ手段と、
前記探索矩形の位置情報と、前記複数の探索矩形バッファ手段への書き込みを制御するためのデータを保持する制御レジスタ手段と、
前記テンプレートバッファ手段に格納された前記テンプレートと、前記複数の探索矩形バッファ手段の１つに格納された前記探索矩形内のデータとの正規化相関値を演算する演算手段と、
を備えることを特徴とする正規化相関処理装置。
【請求項２】
前記制御レジスタ手段は、正規化相関をとる各探索矩形の位置情報を互いに依存関係なく１つずつ個別に保持すると共に、前記探索矩形の位置が規則的な場合には、先頭探索矩形位置からの縦横サイズと間引き距離によっても前記探索矩形の位置を指定可能であることを特徴とする請求項１に記載の正規化相関処理装置。
【請求項３】
前記複数の探索矩形バッファ手段に含まれる第１の探索矩形バッファ手段に充填されている前記探索矩形を用いて相関値計算を行うとともに、次の相関値計算に用いる探索矩形を、前記複数の探索矩形バッファ手段に含まれる第２の探索矩形バッファ手段に充填することを特徴とする請求項１に記載の正規化相関処理装置。
【請求項４】
第１の探索矩形の計算が終了して、第２の探索矩形の計算を開始するさいに、現在計算に使用している探索矩形バッファに、前記第２の探索矩形が含まれていれば、探索矩形バッファを切替えず、そのまま前記第２の探索矩形の計算に使用し、前記第２の探索矩形が含まれていなければ、探索矩形バッファを切替えて、前記第２の探索矩形の計算に使用することを特徴とする請求項１に記載の処理装置。
【請求項５】
前記第１の探索矩形が現在使用中の探索矩形バッファ手段に入っているかどうか判定する場合に、前記探索矩形の左上座標が前記探索矩形バッファ手段に充填された矩形領域の左上座標より右下にあり、かつ、前記探索矩形の右下座標が前記探索矩形バッファ手段に充填された矩形領域の右下座標より右上にあることにより判定することを特徴とする請求項４に記載の正規化相関処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像マッチングにおける正規化相関処理装置に関する。
【背景技術】
【０００２】
画像処理アプリケーションの分野では、画像のパタンマッチングの１手法として、正規化相関値や差分絶対値和SADを計算する方法がある。この処理はCPUによる計算量が非常に多いため、専用回路化して高速化することが多く行われており、様々な回路構成が提案されている。
【０００３】
正規化相関では、探索したい画像（テクスチャと呼ぶ）と探索対象画像の部分矩形（ウィンドウと呼ぶ）の間で正規化相関値を計算する。そして、これをある１つのテクスチャに対して、探索対象画像のウィンドウ位置を例えばピクセル単位で小刻みに移動させて行うというのが一般的である。
【０００４】
次の式が、正規化相関値ｒの計算式である。
【数１】
2010113522.tif 000003
ここで、ｆは、ソース画像（ウィンドウ）の画素値（輝度値）、ｇは、テンプレート画像（テクスチャ）の画素値（輝度値）、ｎは、テンプレート領域内有効画素数である。そして、マッチングを行う場合には、テクスチャｇを少しずつずらしてｒを計算する。以下、テクスチャを当てた位置を「ウィンドウ」と呼ぶ。以下では、gはx、fはyであらわす。Σｘ、（Σｘ）２、Σｇ２は各ウィンドウで変わらないので予め計算しておく。Σｘｙ、Σｙ２、（Σｙ）２は各ウィンドウで変化するので毎回計算する。これらを「相関要素値」と呼ぶ。
【０００５】
図１３は、正規化相関値の計算方法について説明する図である。
相関要素値のみをアクセラレータで計算し、最後にソフトウエアで相関値を計算する。ウィンドウの左上の座標をウィンドウの位置とし、ウィンドウの位置が（０，０）の場合の相関値をテクスチャ画像ｘとウィンドウ内の元画像ｙとを使って計算する。次に、ウィンドウの位置を１ピクセル横に移動し、ウィンドウの位置が（１，０）の場合に相関値を求める。以上のようにして、ウィンドウの位置が（３，３）の場合など、すべての元画像ｙについて相関値を求める。
【０００６】
図１４は、ウィンドウ位置のとり方について説明する図である。
このとき、ウィンドウの位置の取り方には、二通りの方法があり、規則的な位置を設定する方法と、ランダムな位置をとる方法とがある。
【０００７】
ウィンドウの位置が規則的な場合は、相関値を取りたい各ウィンドウが1または数ピクセルずつ規則的にずれて位置する。ウィンドウ位置がランダムの場合は、相関値を取りたい各ウィンドウ位置に規則性がなく散らばっている。
【０００８】
図１５は、ウィンドウ位置が規則的な場合のアクセラレータにより処理の概要を説明す
る図である。
相関要素値（Σｘｙ、Σｙ、Σｙ２）のみをアクセラレータで計算し、最後にソフトウエアで相関値ｒを計算する。Σｘｙを計算する場合には、ウィンドウ位置（０，０）、（１，０）・・・、（３，３）、・・・などの各位置において乗算器１０でテクスチャとウィンドウのピクセルの乗算ｘｙを計算し、計算結果を加算器１１で加算して、Σｘｙを計算する。計算結果は、レジスタ１２に格納される。Σｘｙの計算に必要なマシンサイクルはウィンドウの大きさｎ×ｍピクセルに相当するｎ×ｍサイクルである。図１５においては、ウィンドウの大きさが、６×４であるので、１つのΣｘｙを計算するのに、２４サイクルかかる。
【０００９】
このようにする場合、この処理を速くするために、並列処理を行うことが考えられる。並列処理には、ウィンドウ単位で並列処理する方法と、ピクセル単位で並列処理する方法とがある。
【００１０】
ウィンドウ単位で並列処理する方法においては、各演算器は各々別のウィンドウを担当する。１ウィンドウあたりのレイテンシはウィンドウの大きさであるｎ×ｍに比例する。スループットが演算器個数倍となるが、ウィンドウの位置を個別に与える、ウィンドウ位置がランダムな場合には、ウィンドウが離れていると、同じピクセルをアクセスして計算することが出来ないので、規則的にウィンドウ位置を与える場合とは異なり、並列処理に向かない。
【００１１】
また、１ウィンドウ内で複数のピクセルを並列に処理する方法がある。この場合には、複数ピクセルを１サイクルの間に処理できる１個の演算器セットを１ウィンドウ処理に全てつぎ込む方式であり、１つのウィンドウ内で並列に処理することが出来るので、ウィンドウ位置に影響されることがなく、ウィンドウ位置がランダムである場合に向く。
【００１２】
図１６は、画像のテンプレートマッチングのためのハードウェア構成例を示す図である。
処理するウィンドウ位置が密集して固定されている場合を示しており、（０，０）から（３，３）までの４×４のウィンドウ位置１６個が並列して処理される。１つの入力イメージからArea１−１６のデータが、GSEU（Gray-scale Search Engine Unit）に入力される。GSEUは、並列に処理するArea１−１６のそれぞれについて１つずつ設けられており、Area１−１６のそれぞれを並列に処理する構成となっている。各GSEUには、それぞれの正規化相関要素値を計算する演算器が設けられており、Area１−１６の入力データと、参照データとを使って、演算を行う。それぞれの演算器が行う処理は、行う処理に応じて１オペレーションであったり、２オペレーションであったり、３オペレーションであったりする。GSEUは、例えば、３００MHｚのクロックで動作しており、演算結果は、バスを介して出力される。
【００１３】
ウィンドウが重なって配置されている場合、あるサイクルで参照すべき参照画像のピクセルを１つだけとすることにより、ウィンドウ位置が規則的な場合のみなら効率的な方法である。もし、ランダムだと、どれか１つのウィンドウしか一度に処理できない。
【００１４】
図１７は、ウィンドウ単位で並列処理する方式を説明する図である。
各演算器は各々別のウィンドウを担当する。図１７では、乗算器１０、加算器１１、レジスタ１２からなる演算器が１６個設けられており、それぞれ、ウィンドウ（０，０）から（３，３）までの１６個のウィンドウを１つずつ担当する。ウィンドウの位置を表す座標は、ウィンドウの左上端の画素の座標である。１ウィンドウあたりのレイテンシは、１ウィンドウの大きさであるピクセル数ｎ×ｍ個に比例する。スループットは、演算器が１つの場合に比べ演算器個数倍良くなる。
【００１５】
一方、１サイクルあたり4 or 8 or 9 or 16ピクセル処理できる１個の演算器セットを１ウィンドウ処理に全てつぎ込む方式や、4 or 8 or 9 or 16ピクセルは2x2 or 4x2 or 3x3 or 4x4などのようにタイル状の領域分けて、領域ごとに処理を行う方式などが考えられる。
【００１６】
図１８は、１ウィンドウで複数ピクセル並列に処理する方式を説明する図である。
図１８では、６×８のテクスチャを４×２のタイル状の領域に分けてピクセルを読み込み、処理する場合を示している。４×２のタイル状領域を単位とすることで、１ウィンドウを６サイクルで読み込み終了となる。入力画像の読み込みも４×２のタイル状領域を単位に読み込むようにする。演算器は、Σｘｙを計算する場合の例であるが、乗算器１０−１〜１０−８の８個を備え、更に、加算器１１とレジスタ１２を備える。
【００１７】
図１９は、従来の正規化相関処理装置の構成を説明する図である。
ウィンドウ位置の制御パラメタは規則アクセス前提とした指定であり、ウィンドウ位置の制御パラメタは、先頭ウィンドウの位置、間引き幅、縦横ウィンドウ数などである。図１９（ａ）に示されるように、制御レジスタ２５には、ウィンドウの読み込み制御を行う制御回路２６に与えるパラメタが格納されており、例えば、バッファ充填サイズｂｈ、ｂｗ、テクスチャサイズｔｈ、ｔｗ、先頭ウィンドウ位置ｘ、ｙ、縦横間引き幅ｃｘ、ｃｙ、縦横ウィンドウ数ｎｘ、ｎｙである。図１９（ｂ）の構成図によれば、メモリ２０がバス２１を介してテクスチャバッファ２２とウィンドウバッファ２３に接続される。テクスチャバッファ２２には、マッチングを取りたいテンプレートを格納する。ウィンドウバッファ２３には、メモリ２０に格納された元画像からマッチングを行う領域の画像データを読み込む。正規化相関演算回路２４は、テクスチャバッファ２２とウィンドウバッファ２３からピクセルデータを読み込んで、正規化相関値を演算する。
【００１８】
図２０は、従来の、ダブルバッファ方式の正規化相関処理装置の構成を説明する図である。
ウィンドウ位置の制御パラメタは規則アクセス前提とした先頭ウィンドウの位置と間引き幅で指定する。図２０（ａ）に示されるように、ウィンドウの読み込みを制御する制御回路２６には、制御レジスタ２５からパラメタが入力される。制御レジスタ２５に格納されるパラメタは、例えば、バッファ充填サイズｂｈ、ｂｗ、テクスチャサイズｔｈ、ｔｗ、先頭ウィンドウ位置ｘ、ｙ、縦横間引き幅ｃｘ、ｃｙ、縦横ウィンドウ数ｎｘ、ｎｙである。図２０（ｂ）のように、メモリ２０は、バス２１に接続され、テクスチャバッファ２２、ウィンドウバッファ＃０  ２３−１、ウィンドウバッファ＃１  ２３−２とデータの送受を行う。ウィンドウバッファ＃０  ２３−１とウィンドウバッファ＃１  ２３−２には、異なるウィンドウが格納され、セレクタ２７で順次切り替えて、正規化相関演算回路２４にウィンドウデータを供給する。
【００１９】
このように、ダブルバッファ化することで、データ供給処理と演算処理を並列化可能となる。
従来の構成では、ウィンドウ位置は、ある矩形内で1ピクセルずつずらして全ての位置で演算を行うというように規則的であることを前提としてその高速化方式を検討してきた。しかし、近年の画像処理アプリケーションではこのような規則的な場合だけでなく、ウィンドウ位置が探索対象画像の任意の位置にランダムに存在するという使い方が多くなってきており、このような場合に従来方式をそのまま適用すると性能が十分に発揮できないという問題があった。
【００２０】
高速化には並列処理が必要となるが、その方法として、ウィンドウ単位の並列処理とピクセル単位の並列処理が考えられる。また、高速化には複数ウィンドウの一括突き放し処
理が必要である。ウィンドウ位置が規則的であるという前提がある場合、メモリアクセス量を減らすためにはウィンドウ単位並列処理の方が効率が良いため、従来はこの方法が取られてきた。しかし、ウィンドウ単位並列処理とすると、位置ランダムな場合、並列処理するウィンドウ毎にランダムなアドレスからのメモリアクセスになり実現が困難になる。また、一括突き放し方式がウィンドウ位置規則的を前提とするため、位置ランダムな場合の突き放しは考慮されてこなかった。
【００２１】
例えば、ウィンドウ単位並列処理を行う従来方式(特許文献１〜３)の場合は並列処理のウィンドウ位置が規則的になっているため、ランダムな場合、一括処理突き放し処理が出来ず、一度に１ウィンドウしか処理できなくなる。
【００２２】
また、画像分割による並列処理を行う従来方式(特許文献４)の場合はデータの局所性を用いてメモリのロードの時間を減らし、かつ、画像分割による並列処理を行うが、ランダムアクセスの場合、データの局所性を利用できず、多くの演算器を搭載しても、メモリアクセス速度がボトルネックとなり、演算器が遊んでしまう。
【特許文献１】特開平０９−００９２６９号公報
【特許文献２】特開平１０−１３４１８３号公報
【特許文献３】特開２００６−０１３８７３号公報
【特許文献４】特開２００８−８４０３４号公報
【発明の開示】
【発明が解決しようとする課題】
【００２３】
以上のように、これまではウィンドウ位置が規則的なことを前提とした方式が考えられてきたが、規則的な場合とランダムな場合の両方に柔軟に対応して高速処理可能な装置構成が必要である。
【００２４】
従来の正規化相関回路方式では探索ウィンドウ位置が規則的に密集していることを前提として、その高速化を行う構成であった。しかし、近年の画像処理アプリケーションではこのような規則的な場合だけでなく、ウィンドウ位置がランダムなことが多くなってきており、このような場合に従来方式をそのまま適用すると性能が十分に発揮できないという問題があった。
【００２５】
本発明の課題は、ウィンドウ位置がランダムな場合も対応可能な正規化相関処理装置を提供することである。
【課題を解決するための手段】
【００２６】
本発明の正規化相関処理装置は、画像のパタンマッチング処理をするための正規化相関処理装置であって、パタンマッチングのためのテンプレートを保持するテンプレートバッファ手段と、探索矩形の縦横サイズを任意に指定して、入力画像の前記探索矩形を保持する複数の探索矩形バッファ手段と、前記探索矩形の位置情報と、前記探索矩形バッファ手段への書き込みを制御するためのデータを保持する制御レジスタ手段と、前記テンプレートバッファ手段に格納されたテンプレートと、前記複数の探索矩形バッファ手段の１つに格納された探索矩形内のデータとの正規化相関値を演算する演算手段とを備える。
【発明の効果】
【００２７】
本発明によれば、ウィンドウ位置がランダムな場合にも対応可能な正規化相関処理装置を提供することが出来る。
【発明を実施するための最良の形態】
【００２８】
本実施形態においては、ウィンドウ位置配列に一括突き放し処理するウィンドウ位置を
ウィンドウ毎に個別指定可能とし、ウィンドウバッファにウィンドウを充填する際にはテクスチャサイズth,twに関係なく縦横サイズbh,bwを任意指定可能とする。ウィンドウバッファはダブルバッファ構成として、演算と平行してウィンドウ充填動作を行う。ダブルバッファの切替えは、現在使用中のバッファに配列番号順で次に処理するウィンドウが入っている場合は切替えないという制御を行う回路により自動で行う。また、他方バッファへの充填すべき領域をハードウェアが自動計算する制御回路があり、ユーザからの利用を容易にする。これらによりウィンドウ位置が規則的かどうかにかかわらず、同じ手続きで処理可能となる。
【００２９】
図１及び図２は、本発明の実施形態の概要を説明する図である。
図１（ａ）に示されるように、制御レジスタ３０には、バッファ充填サイズｂｈ、ｂｗ、テクスチャサイズｔｈ、ｔｗ、ウィンドウ位置配列が設定される。バッファ充填サイズは、ウィンドウバッファに格納する矩形領域のサイズをテクスチャサイズとは関係なく、任意に指定可能とするものである。テクスチャサイズは、テクスチャのサイズを指定する。ウィンドウ位置配列は、ウィンドウの位置がランダムな場合に、ウィンドウのランダムな位置を個別に指定する配列である。ウィンドウの位置が、規則的な場合には、先頭ウィンドウ位置からの縦横サイズと間引き距離によってもウィンドウ位置を指定可能とする。制御回路３１は、ダブルバッファ構成のウィンドウバッファに、次に充填するウィンドウの開始位置を決定するバッファ次充填開始位置探索回路と、処理するべきウィンドウがダブルバッファ構成のバッファのいずれに格納されているかの判断結果に基づいて、読み出しを行うバッファを切り替える回路であるバッファ切り替え判定回路とからなる。これは、パラメタから自動的に切り替え判定、バッファ充填矩形領域決定を行う回路である。
【００３０】
図１（ｂ）は、正規化相関処理装置の構成を示す。メモリ２０からは、バス２１を介して、テクスチャバッファ２２にテクスチャのデータが送られ、ウィンドウバッファ＃０  ２３−１とウィンドウバッファ＃１  ２３−２には、ウィンドウのデータが送られる。本実施形態では、ウィンドウバッファの格納領域の大きさが任意に指定可能となっている。セレクタ２７で選択されたウィンドウバッファからは、ウィンドウデータが読み出され、正規化相関演算回路２４に入力される。正規化相関演算回路２４には、テクスチャバッファ２２からテクスチャデータが入力され、ウィンドウデータと共に、正規化相関演算に使用される。正規化相関演算回路２４は、１ウィンドウ内でピクセル単位の並列処理を行う回路となっている。
【００３１】
図２において、バッファに充填する矩形領域縦横サイズ指定パラメタｂｈ、ｂｗを新たに設けて自由指定可能（ｔｈ≠ｂｈ,ｔｗ≠ｂｗ可能）とする。ウィンドウバッファに充填する矩形サイズを自由に設定可能とすることにより、ランダムに与えられたウィンドウ位置に対し、ウィンドウが重なっている場合には、重なっているウィンドウをすべてウィンドウバッファにまとめて充填する。このことにより、互いに重なったウィンドウについては、読み出す際に、バッファ切り替えを行わずに読み出しを可能とする。
【００３２】
正規化相関処理装置の性能を表すパラメタとしては、以下のようなものがある。
・基本データ供給性能〜1サイクルあたりに外部メモリから持ってくることができるピクセル数
・実データ供給性能〜基本データ供給性能にバッファ内のピクセル再利用によるキャッシュ効果を加味した1サイクルあたりに得られるピクセル数
・演算性能〜演算器が1サイクルあたりに処理可能なピクセル数
【００３３】
図３は、ウィンドウ位置が位置規則的な場合の動作を説明する図である。
図３においては、
・基本データ供給性能＜演算性能であるとする。
・位置配列はA,B,C,D,...,Lの順とする。
・A-D,E-H,I-Lがそれぞれ一括充填されるようにbh,bwが設定されているとする。
・キャッシュ効果により実データ供給性能＞演算性能となるケースとする。
実データ供給性能は、以下の式で与えられる。
(実データ供給性能=基本データ供給性能+キャッシュ効果)
【００３４】
動作は以下の通りとなる。
１．Aの左上座標からｂｈ、ｂｗの矩形をウィンドウバッファ０に充填する。A-Dの領域が充填される。
２．Aの相関値を計算する。同時に、ウィンドウバッファ１に充填する次充填開始ウィンドウ位置Eを、次充填開始ウィンドウ位置探索回路で探索し、バッファ１に充填する。更に次の充填開始ウィンドウ位置Iを次充填開始ウィンドウ位置探索回路で探索する。バッファ０は使用中なので、充填はバッファ０が解放されるまで保留する。
３．Aの計算を完了したら、Bがバッファ０に含まれるか否かをバッファ切替え判定回路で判定する。
４．Bは含まれるので、バッファを切替えずにBを計算する。
５．同様にDまで計算する。
６．Dの計算を完了したら、同様にEがウィンドウバッファ０に含まれるか否かをバッファ切替え判定回路で判定する。
７．Eは含まれないので、バッファをウィンドウバッファ１に切替えてEを読み込み、Eを計算する。平行して、ウィンドウバッファ０が空いたので先に保留されていたIからの矩形の充填を行う。続けて、次充填開始ウィンドウ位置を判定するが、終端Lまで全てがウィンドウバッファ０に含まれるので、充填は終了する。
８．これまでと同様に、F,G,Hと1つのウィンドウが終了するごとにバッファ切替え判定を行いながら計算する。Hまではバッファは切り替わらない。
９．H終了時点でバッファ切替え判定を行うと、Iはウィンドウバッファ１に含まれないので、ウィンドウバッファ０に切替えて処理を終端まで同様に継続する。
【００３５】
図３の例は、テクスチャが比較的小さく、ウィンドウ位置が規則的な場合を示している。また、充填矩形サイズをｂｈ＞ｔｈ,ｂｗ＞ｔｗに設定し、一度に複数ウィンドウを一つのバッファに充填する。
【００３６】
図４は、ウィンドウ位置がランダムな場合の動作を説明する図である。
図４においては、以下の条件が成り立っているとする。
・基本データ供給性能＜演算性能の回路構成の場合とする。
・位置配列はA,B,Cの順とする。
・A,B,Cがそれぞれ一個ずつ充填されるようにｂｈ,ｂｗが設定されているとする。
・キャッシュ効果がなく実データ供給性能＜演算性能となるケースであるとする。
【００３７】
動作は以下のようになる。
１．Aの左上座標からｂｈ、ｂｗの矩形をウィンドウバッファ０に充填する。Aの領域のみが充填される。
２．Aの相関値を計算する。同時に、ウィンドウバッファ１に充填する次充填開始ウィンドウ位置Bを次充填開始ウィンドウ位置探索回路で判定し、ウィドウバッファ１に充填する。更に、次の充填開始ウィンドウ位置Cを次充填開始ウィンドウ位置判定回路で計算する。ウィンドウバッファ０は使用中なので、充填はウィンドウバッファ０が解放されるまで保留する。
３．Aの計算を完了したら、Bがウィンドウバッファ０に含まれるか否かをバッファ切替え判定回路で判定する。
４．Bは含まれないので、バッファを切替えてBが充填されるのを待ってからBを計算する
。平行して、ウィンドウバッファ０が空いたので、先に保留されていたCからの矩形の充填を行う。続けて、次充填開始ウィンドウ位置を判定するが、終端Cまで全てがウィンドウバッファ０に含まれるので、充填は終了する。
５．同様に、Bの計算が終了すると、バッファ切替え判定を行い、Cは含まれないのでバッファを切替えて、Cが充填されるのを待ってからCを計算して終了する。
【００３８】
図４においては、テクスチャが比較的大きく、ウィンドウ位置がランダムな例を示している。充填矩形サイズをテクスチャサイズと同じ（ｂｈ＝ｔｈ,ｂｗ＝ｔｗ）に設定し、通常ダブルバッファとして動作させる。
【００３９】
図５は、キャッシュ効果が生じるウィンドウ位置がランダムな場合の動作を説明する図である。
図５においては、以下の条件が成り立っているとする。
・基本データ供給性能＜演算性能の回路構成の場合とする。
・位置配列はA,B,Cの順とする。
・A,Bがそれぞれウィンドウバッファ０に、Cがウィンドウバッファ１に充填されるようにｂｈ、ｂｗが設定されているとする。
・キャッシュ効果があり実データ供給性能≒演算性能となるケース。
【００４０】
動作は、以下の通りとなる。
１．Aの左上座標からｂｈ、ｂｗの矩形をウィンドウバッファ０に充填する。A,Bの領域が充填される。
２．Aの相関値を計算する。同時に、ウィンドウバッファ１に充填する次充填開始ウィンドウ位置Cを次充填開始ウィンドウ位置探索回路で探索し、ウィンドウバッファ１に充填する。更に、次の充填開始ウィンドウ位置を探索するが、終端まで来たので充填は終了する。
３．Aの計算を完了したら、Bがウィンドウバッファ０に含まれるか否かをバッファ切替え判定回路で判定する。
４．Bは含まれるのでバッファを切り替えずにBを計算する。
５．同様に、Bの計算が終了するとバッファ切替え判定を行い、Cは含まれないのでバッファを切替えてCを計算して終了する。
【００４１】
図５においては、テクスチャが比較的大きく、ウィンドウ位置がランダムの場合を示している。重複領域が大きければ、充填矩形サイズを（ｂｈ＞ｔｈ,ｂｗ＞ｔｗ）に設定すれば、キャッシュ効果が生じ、処理性能が上がる。
【００４２】
図６は、ウィンドウ位置が規則的な場合の動作タイミングを示す図である。
図６では、ABCDがウィンドウバッファ０に一括して充填され、EFGHがウィンドウバッファ１に一括して充填される場合を示している。また、基本データ供給性能<演算性能を想定し、実データ供給性能>基本データ供給性能、実データ供給性能=基本データ供給性能＋キャッシュ効果を想定している。
【００４３】
ウィンドウの位置は、制御レジスタには、ウィンドウA-Lまでのウィンドウ位置が格納されている。最初に、ウィンドウバッファ０に、ウィンドウA-Dを充填する。このとき、ウィンドウA-Dを一括して、１つのバッファに格納するために要する時間は、４つのウィンドウを個別にバッファに格納する時間の合計よりも小さいため、効率が上がる。ウィンドウバッファ０の充填が終わると、ウィンドウAから順に計算処理が行われる。この計算処理の間に、ウィンドウバッファ１に、ウィンドウE-Hを充填する。計算処理と充填処理が並行して実行されるので、ウィンドウ１への充填時間が隠蔽される。ウィンドウバッファ０に対し、ウィンドウDまで処理が終わったら、ウィンドウバッファ１からウィンドウEを読み出し、以降順次ウィンドウの計算処理を行う。ウィンドウバッファ１のウィンドウE-Hを処理している間に、ウィンドウバッファ１に、ウィンドウI以降を充填し、充填時間を隠蔽する。
【００４４】
図７は、ウィンドウ位置ランダム時に通常のダブルバッファとして使う場合であって、キャッシュ効果なしの場合の動作タイミングを示す図である。
基本データ供給性能＜演算性能の構成の場合とすると(例えば8ピクセル／サイクルのデータ供給性能で、16ピクセル／サイクルの演算性能)、充填時間がクリティカルパスとなる。すなわち、図７の場合、ウィンドウA-Cのウィンドウ位置が制御レジスタに格納されているが、各ウィンドウは、１つずつウィンドウバッファに格納される。まず、ウィンドウバッファ０にウィンドウAが充填され、充填が終わると、ウィンドウAが計算処理される。また、ウィンドウバッファ０のウィンドウAの充填が終わると、ウィンドウAの計算処理と並行して、ウィンドウバッファ１の充填が開始される。ウィンドウバッファ１には、ウィンドウBが充填される。ウィンドウBの充填が終わると、ウィンドウBの計算処理の開始と共に、ウィンドウバッファ０へのウィンドウCの充填が開始される。ここで、ウィンドウの計算処理よりもウィンドウバッファへのウィンドウの充填の方が時間がかかるので、処理時間は、ウィンドウバッファの充填時間によって決定される、すなわち、クリティカルパスとなる。
【００４５】
図８は、ウィンドウ位置がランダム時でもキャッシュ効果ある場合の動作タイミングを説明する図である。
図８においては、基本データ供給性能＜演算性能の構成の場合であって、A,Bの重複が大きいため一括充填のキャッシュ効果で充填時間の隠蔽が可能な場合を示している。制御レジスタには、ウィンドウA-Cのウィンドウ位置が格納されている。ウィンドウバッファ０の充填において、ウィンドウAとBの充填が行われる。ウィンドウバッファ０の充填が終わると、ウィンドウAの計算処理と、ウィンドウバッファ１の充填が開始される。１つのウィンドウの計算処理時間は、ウィンドウバッファの充填時間より短いが、ウィンドウバッファ０には、２つのウィンドウが格納されているので、ウィンドウバッファ０内のウィンドウの計算処理が終わるまでに、ウィンドウバッファ１の充填が終わり、充填時間の隠蔽が可能である。また、ウィンドウバッファ０にウィンドウA、Bを一括して充填する場合には、ウィンドウAとBを別個に充填する時間の合計よりも充填時間が短くてすむので、実データ供給性能が良くなる。
【００４６】
図９は、ウィンドウバッファの充填方法とキャッシュ効果について説明する図である。ウィンドウバッファはダブルバッファ構成（バッファ０,１）とし、テクスチャサイズは、例えば、最大16KB(128x128相当)とする。また、バッファフィルサイズbh,bwは自由設定可能であり、テクスチャサイズth, tw固定としない。
【００４７】
ウィンドウバッファの切替え判定は、以下の通りである。
次ウィンドウが現在使用中のバッファにはいっていればバッファを切り替えない。これは、次ウィンドウ位置からハードウェア内部で自動判定する。開始時、a)ウィンドウ位置配列の先頭エントリのbh, bw矩形を１つのバッファ０に充填する。b)先頭エントリから順番にエントリをみていき、バッファ１に充填した矩形に含まれないエントリxに到達したら、そのエントリxのbh, bw矩形をバッファ１に充填する。ウィンドウの充填に用いたエントリの処理に到達したら、b)と同様に、そのエントリ以降で現在の矩形に含まれないエントリの矩形を他方のバッファに充填する。
【００４８】
図９（ａ）は、ウィンドウ位置が規則的な場合であり、バッファ容量に比べテクスチャが比較的小さい場合である。ウィンドウA-Dをウィンドウバッファ０に格納し、ウィンドウE-Hをウィンドウバッファ１に格納する。ウィンドウバッファ０内のウィンドウすべて
が処理し終わったら、ウィンドウバッファ０にウィンドウI-Lを充填する。図９（ｂ）は、ウィンドウ位置がランダムで、キャッシュ効果がない場合である。ウィンドウAは、ウィンドウバッファ０に格納され、ウィンドウBは、ウィンドウバッファ１に格納される。ウィンドウ同士の重なりが少ないため、複数のウィンドウを１つのウィンドウバッファに格納できない場合には、１つのウィンドウを１つのウィンドウバッファに格納する。一方、図９（ｃ）の場合は、ウィンドウ位置がランダムで、キャッシュ効果がある場合である。ウィンドウAとBの重なりが多く、ウィンドウAとBが１つのウィンドウバッファに収まる場合を示している。複数のウィンドウが１つのウィンドウバッファに格納できる場合には、１つのウィンドウバッファに複数のウィンドウを充填するようにする。複数のウィンドウを一括して１つのウィンドウバッファに格納するので、データの転送効率がよく、また、計算処理するウィンドウを切り替える場合にも、バッファを切り替える必要がないので、ウィンドウのデータの読み込みを早くすることが出来る。
【００４９】
図１０は、ウィンドウバッファの充填のための処理フローを示す図である。
図１０において、win[i]は、 i番目のウィンドウ（i⊂{0,1,…,N-1}）であり、buf[b]は、bバッファ,（b⊂{0,1}、ダブルバッファ時）である。
【００５０】
ウィンドウは、０〜N-1のN個あるものとする。ステップS１０において、ｉ＝０、ｂ＝０と初期化する。ステップＳ１１において、ウィンドウバッファbuf[b]へ、win[i]を開始位置とする矩形を充填する。ステップS１２において、ｉを１増加し、ステップS１３において、ｉがＮ以上か否かを判断する。ステップＳ１３の判断がＹｅｓの場合には、処理を終了し、ステップＳ１３の判断がＮｏの場合には、ステップＳ１４において、ｉ番目のウィンドウがｂのウィンドウバッファbuf[b]に充填可能か否かを判断する。ステップＳ１４の判断がＹｅｓの場合には、バッファを充填し、ステップＳ１２に戻り、Ｎｏの場合には、ステップＳ１５に進む。ステップＳ１５においては、ｂを、ｂのビット反転したもの（０を１に、１を０にする）に置き換え、ステップＳ１６に進む。ステップＳ１６では、バッファbuf[b]は空か否かを判断する。ステップS１６の判断がＮｏの場合には、バッファが空になるまでステップS１６のステップを繰り返す。ステップS１６の判断がＹｅｓの場合には、ステップS１１に戻る。
【００５１】
図１１は、ウィンドウバッファの切り替え処理フローを示す図である。
図１１の次のウィンドウ処理に使うバッファの決定を行うフローにおいては、現在使用中のバッファに入っていないときだけ切替える。
【００５２】
図１１において、icは、現在処理しているウィンドウ番号、bcは、現在使用しているバッファ番号、bnは、次に使用するバッファ番号である。ステップＳ２０において、i=ic+1、b=bcと初期化し、ステップＳ２１において、ウィンドウwin[i]がウィンドウバッファbuf[b]に充填されているか否かを判断する。ステップＳ２１の判断がＹｅｓの場合には、ステップＳ２３に進み、Ｎｏの場合には、ステップＳ２２に進む。ステップＳ２２においては、ｂのビットを反転し、ステップＳ２３において、ｂｎにｂを設定し、処理を終了する。
【００５３】
図１２は、ウィンドウバッファの充填、切り替えの自動判定方法を説明する図である。
winがbuf内にある条件 win[i]⊆buf[b]?（図１０、図１１）の判定方法は、以下の通りである。
【００５４】
win[i]の左上座標(x,y)、buf[b]の左上座標(px,py)とする。winの左上座標がbufの左上座標より右下にあり、かつ、winの右下座標がbufの右下座標より右上にあるという意味の以下の判断式を判断する。
((px<=x) && (py<=y)) && (((px+bw)>=(x+tw)) && ((py+bh)>=(y+th)))
図１２は、(px,py)=(x0,y0), (x,y)=(x1,y1)の場合の例である。初期設定値としては、ｂｈ（バッファの高さ）、ｂｗ（バッファ幅）、ｔｈ（ウィンドウの高さ）、ｔｗ（ウィンドウの幅）がある。win[i]として、ウィンドウの位置配列ｘ、ｙが与えられる。px<=x&&py<=yは、winの左上座標が、bufの左上座標の右下にあるという意味の判断式である。また、((px+bw)>=(x+tw)) && ((py+bh)>=(y+th))は、winの右下座標がbufの右下座標より右上にあるという意味の判断式である。
【００５５】
バッファ充填動作fill win[i], buf[b]のためのアドレス生成方法は、以下の通りである。入力画像は、主記憶上で連続アドレス前提とする。iB（入力画像の先頭のアドレス）, ih（入力画像の高さ１列分のアドレスの変化分）, iw（入力画像の幅１つ分のアドレスの変化分）, bh（バッファの高さ）, bw（バッファの幅）, win[i]座標のx, yから以下の式に従って、アドレスを生成する。
iB+(y+H)*iw+x+W, 
where 0<=H<=bh, 0<=W<=bw
HとWは、ウィンドウの左上の位置である。
a) ランダムなウィンドウ位置でのアクセス、b)規則的なウィンドウ位置でのアクセスの両方のアクセスパタンを両立することによって、以下のような効果がある。
a)大テクスチャ、ランダムの場合は、th, tw = bh, bwとすれば、通常のダブルバッファとして使える。
b)小テクスチャ、規則の場合は、th, tw < bh, bwと設定することで、はじめのウィンドウ充填時に周辺ウィンドウもバッファに持って来られる。バッファ切り替えを当該バッファにウィンドウが入っている間は切替えないようにすればレイテンシを隠蔽できる。
【００５６】
上記実施形態によれば、ウィンドウ位置が規則的な場合とランダムな場合の両方に柔軟に対応でできる。更に、ウィンドウ位置が規則的、ランダムのどちらのケースであってもユーザはバッファの切り替えや充填すべき領域をユーザが指定する必要がなく、ウィンドウの位置順win[N]、および、バッファに充填する縦横サイズbh,bwを指定するだけで、同一の利用方法で一貫して扱うことができる。
【００５７】
上記実施形態のほかに、以下の付記を開示する。
（付記１）
画像のパタンマッチング処理をするための正規化相関処理装置であって、
パタンマッチングのためのテンプレートを保持するテンプレートバッファ手段と、
探索矩形を含む矩形データの縦横サイズを任意に指定して、入力画像の前記探索矩形を含む前記矩形データを保持する複数の探索矩形バッファ手段と、
前記探索矩形の位置情報と、前記複数の探索矩形バッファ手段への書き込みを制御するためのデータを保持する制御レジスタ手段と、
前記テンプレートバッファ手段に格納された前記テンプレートと、前記複数の探索矩形バッファ手段の１つに格納された前記探索矩形内のデータとの正規化相関値を演算する演算手段と、
を備えることを特徴とする正規化相関処理装置。
（付記２）
前記制御レジスタ手段は、正規化相関をとる各探索矩形の位置情報を互いに依存関係なく１つずつ個別に保持すると共に、前記探索矩形の位置が規則的な場合には、先頭探索矩形位置からの縦横サイズと間引き距離によっても前記探索矩形の位置を指定可能であることを特徴とする付記１に記載の正規化相関処理装置。
（付記３）
前記複数の探索矩形バッファ手段に含まれる第１の探索矩形バッファ手段に充填されている前記探索矩形を用いて相関値計算を行うとともに、次の相関値計算に用いる探索矩形を、前記複数の探索矩形バッファ手段に含まれる第２の探索矩形バッファ手段に充填する
ことを特徴とする付記１に記載の正規化相関処理装置。
（付記４）
第１の探索矩形の計算が終了して、第２の探索矩形の計算を開始するさいに、現在計算に使用している探索矩形バッファに、前記第２の探索矩形が含まれていれば、探索矩形バッファを切替えず、そのまま前記第２の探索矩形の計算に使用し、前記第２の探索矩形が含まれていなければ、探索矩形バッファを切替えて、前記第２の探索矩形の計算に使用することを特徴とする付記１に記載の処理装置。
（付記５）
前記第１の探索矩形が現在使用中の探索矩形バッファ手段に入っているかどうか判定する場合に、前記探索矩形の左上座標が前記探索矩形バッファ手段に充填された矩形領域の左上座標より右下にあり、かつ、前記探索矩形の右下座標が前記探索矩形バッファ手段に充填された矩形領域の右下座標より右上にあることにより判定することを特徴とする付記４に記載の正規化相関処理装置。
（付記６）
現在使用していない他の前記探索矩形バッファ手段への矩形データの充填の際に、現在使用中の前記探索矩形バッファ手段に、前記探索矩形の位置配列の順番に現在処理している探索矩形の次の探索矩形が含まれているか順番に判定して、含まれていない探索矩形に到達したら、それを先頭として次に矩形データを前記探索矩形バッファ手段の１つに充填することを特徴とする付記４に記載の正規化相関処理装置。
（付記７）
前記演算手段は、複数のピクセルを並列に処理可能であることを特徴とする付記１に記載の正規化相関処理装置。
置
（付記８）
前記演算手段は、正規化相関値の要素値となる、探索矩形内の各ピクセル値の総和、探索矩形内の各画素値の自乗の総和、探索矩形内の各画素値とテンプレート内の各画素値の同一位置ピクセルについての積の総和、を計算することを特徴とする付記１に記載の正規化相関処理装置。
（付記９）
前記探索矩形を含む矩形データのサイズは、前記テンプレートのサイズに対して非依存であることを特徴とする付記１に記載の正規化相関処理装置。
【図面の簡単な説明】
【００５８】
【図１】本発明の実施形態の概要を説明する図（その１）である。
【図２】本発明の実施形態の概要を説明する図（その２）である。
【図３】ウィンドウ位置が位置規則的な場合の動作を説明する図である。
【図４】ウィンドウ位置がランダムな場合の動作を説明する図である。
【図５】キャッシュ効果が生じるウィンドウ位置がランダムな場合の動作を説明する図である。
【図６】ウィンドウ位置が規則的な場合の動作タイミングを示す図である。
【図７】ウィンドウ位置ランダム時に通常のダブルバッファとして使う場合であって、キャッシュ効果なしの場合の動作タイミングを示す図である。
【図８】ウィンドウ位置がランダム時でもキャッシュ効果ある場合の動作タイミングを説明する図である。
【図９】ウィンドウバッファの充填方法とキャッシュ効果について説明する図である。
【図１０】ウィンドウバッファの充填のための処理フローを示す図である。
【図１１】ウィンドウバッファの切り替え処理フローを示す図である。
【図１２】ウィンドウバッファの充填、切り替えの自動判定方法を説明する図である。
【図１３】正規化相関値の計算方法について説明する図である。
【図１４】ウィンドウ位置のとり方について説明する図である。
【図１５】ウィンドウ位置が規則的な場合のアクセラレータにより処理の概要を説明する図である。
【図１６】画像のテンプレートマッチングのためのハードウェア構成例を示す図である。
【図１７】ウィンドウ単位で並列処理する方式を説明する図である。
【図１８】１ウィンドウで複数ピクセル並列に処理する方式を説明する図である。
【図１９】１ウィンドウで複数ピクセル並列に処理する方式を説明する図である。
【図２０】従来の、ダブルバッファ方式の正規化相関処理装置の構成を説明する図である。
【符号の説明】
【００５９】
１０、１０−１〜１０−８      乗算器
１１      加算器
１２      レジスタ
２０      メモリ
２１      バス
２２      テクスチャバッファ
２３、２３−１、２３−２      ウィンドウバッファ
２４      正規化相関演算回路
２５、３０      制御レジスタ
２６、３１      制御回路
２７      セレクタ
【図１】
2010113522.tif 000004
【図２】
2010113522.tif 000005
【図３】
2010113522.tif 000006
【図４】
2010113522.tif 000007
【図５】
2010113522.tif 000008
【図６】
2010113522.tif 000009
【図７】
2010113522.tif 000010
【図８】
2010113522.tif 000011
【図１０】
2010113522.tif 000012
【図１１】
2010113522.tif 000013
【図１２】
2010113522.tif 000014
【図１４】
2010113522.tif 000015
【図９】
2010113522.tif 000016
【図１３】
2010113522.tif 000017
【図１５】
2010113522.tif 000018
【図１６】
2010113522.tif 000019
【図１７】
2010113522.tif 000020
【図１８】
2010113522.tif 000021
【図１９】
2010113522.tif 000022
【図２０】
2010113522.tif 000023