(57)【要約】【課題】回路規模やメモリ等の必要なリソースを低減しつつも、計算負荷の増加を抑える。【解決手段】複数次元配列の入力情報を複数の分割領域に分割し、複数の分割領域の各々において、それぞれの基準位置からの入力情報の各要素位置における累積値を計算することにより累積情報を生成し、生成された累積情報を、分割領域ごとにメモリに保持する。予め定められた処理範囲について、累積情報を利用した演算処理が行われる。上記複数領域への分割は、隣接する２つの分割領域がオーバーラップ領域を有するように入力情報を分割し、オーバーラップ領域は少なくとも演算処理における処理範囲の全体が収まる大きさを有する。【選択図】図１
2011059819.tif 000002
【特許請求の範囲】
【請求項１】
分割手段が、複数次元配列の入力情報を複数の分割領域に分割する分割工程と、
生成手段が、前記複数の分割領域の各々について、それぞれの基準位置からの前記入力情報の各要素位置における累積値を計算することにより累積情報を生成する生成工程と、
保持手段が、前記生成工程により生成された前記累積情報をメモリに保持する保持工程と、
演算処理手段が、予め定められた処理範囲について、前記累積情報を利用した演算処理を行う演算処理工程とを備え、
前記分割工程では、隣接する２つの分割領域がオーバーラップ領域を有するように前記入力情報を前記複数の分割領域へ分割し、前記オーバーラップ領域は少なくとも前記処理範囲の全体が収まる大きさを有することを特徴とする情報処理方法。
【請求項２】
前記演算処理工程では、１つの処理範囲について利用する累積値の全てを、一つの分割領域に対応して生成された累積情報から取得することを特徴とする請求項１に記載の情報処理方法。
【請求項３】
前記メモリにおいて確保される前記累積情報のビット精度は、前記入力情報の各要素のビット精度と前記分割領域の大きさに基づき決定されることを特徴とする請求項１に記載の情報処理方法。
【請求項４】
前記分割工程では、前記入力情報の複数次元の内、少なくとも一つの次元方向について分割を行わないことを特徴とする請求項１に記載の情報処理方法。
【請求項５】
前記生成工程では、前記複数の分割領域のうちの、前記分割工程において分割を行う次元方向については前記入力情報の全長を有し分割を行わない次元方向については所定長を有する部分領域に含まれる部分の累積情報を前記演算処理工程による処理と同期して順次に生成し、
前記保持工程では、前記部分領域の累積情報を保持することを特徴とする請求項４に記載の情報処理方法。
【請求項６】
前記生成工程では、前記部分領域に対する前記演算処理工程による処理が終了する毎に、前記部分領域を分割を行わない次元方向へシフトさせ、該シフトにより前記部分領域に新たに入った前記入力情報の要素について累積値を追加的に算出することにより、該シフトの後の前記部分領域における累積情報を生成することを特徴とする請求項５に記載の情報処理方法。
【請求項７】
前記生成工程では、前記複数の分割領域のうちの、前記分割工程において分割を行う次元方向については分割領域が有する長さを有し分割を行わない次元方向については所定長を有する部分領域に含まれる部分ごとに基準位置を設定して累積情報を生成し、
前記保持工程では、前記部分領域の累積情報を保持することを特徴とする請求項４に記載の情報処理方法。
【請求項８】
前記保持工程では、隣接する２つの部分領域について得られる累積情報を第１及び第２バッファにそれぞれ保持し、
前記生成工程では、隣接する２つの部分領域により構成されたオーバーラップ領域において当該２つの部分領域に対応するそれぞれの累積情報を生成し、前記第１及び第２バッファに保持することを特徴とする請求項６に記載の情報処理方法。
【請求項９】
前記演算処理工程では、前記処理範囲を前記分割を行う次元方向へシフトしながら所定の処理を繰り返し、
前記生成工程では、前記処理範囲をシフトする毎に、当該シフトにより前記処理範囲に新たに入った前記入力情報の要素について、当該要素が属する部分領域における累積値を算出することを特徴とする請求項６に記載の情報処理方法。
【請求項１０】
前記メモリにおいて確保される前記累積情報のビット精度は、前記要素のビット精度と前記部分領域の大きさに基づいて決定されることを特徴とする請求項５乃至９のいずれか１項に記載の情報処理方法。
【請求項１１】
前記部分領域の前記所定長は前記処理範囲の対応する次元方向の長さと同じであり、前記部分領域の前記分割工程により分割が行われた次元方向の長さは前記処理範囲の対応する次元方向の長さの２倍であり、前記オーバーラップ領域は前記処理範囲と同じ大きさを有し、
前記生成工程では、前記処理範囲が前記分割を行う次元方向へシフトした場合に、該シフトにより新たに処理範囲に入った前記入力情報の要素の累積値を追加的に生成することを特徴とする請求項９に記載の情報処理方法。
【請求項１２】
前記保持工程では、前記累積値を保持するための領域がいっぱいであり、追加的に算出された累積情報を格納する際、追加的に算出された累積情報の分だけ最も古い累積情報を破棄し、その領域に前記追加的に算出された累積情報を保持することを特徴とする請求項６または１１に記載の情報処理方法。
【請求項１３】
前記入力情報は二次元配列の情報であって、前記分割領域の基準位置と前記分割領域の各要素位置を対角とする矩形領域内に対応する前記入力情報の全ての要素の総和値を、前記分割領域の各要素位置に対応する累積値とすることを特徴とする請求項１乃至１２のいずれか１項に記載の情報処理方法。
【請求項１４】
前記入力情報は三次元以上の多次元配列であって、前記分割領域の基準位置と前記分割領域の各要素位置を対角とする超直方体の領域内に対応する前記入力情報の全ての要素の総和値を、前記分割領域の各要素位置に対応する累積値とすることを特徴とする請求項１乃至１２のいずれか１項に記載の情報処理方法。
【請求項１５】
複数次元配列の入力情報を複数の分割領域に分割する分割手段と、
前記複数の分割領域の各々において、それぞれの基準位置からの前記入力情報の各要素位置における累積値を計算することにより累積情報を生成する生成手段と、
前記生成手段により生成された前記累積情報を、前記分割領域ごとにメモリに保持する保持手段と、
予め定められた処理範囲について、前記累積情報を利用した演算処理を行う演算処理手段とを更に備えを備え、
前記分割手段では、隣接する２つの分割領域がオーバーラップ領域を有するように前記入力情報を前記複数の分割領域へ分割し、前記オーバーラップ領域は少なくとも前記処理範囲の全体が収まる大きさを有することを特徴とする情報処理装置。
【請求項１６】
請求項１乃至１４のいずれか１項に記載の情報処理方法の各工程をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理、画像認識、画像合成、情報分析などのための情報処理方法及び装置に関する。
【背景技術】
【０００２】
情報処理分野においては、多次元配列情報を頻繁に取り扱う。その中でも、画像処理、画像認識や画像合成等に関わる一部処理や統計処理等では、特定領域範囲内における要素の総和値を求めて使用することが多い。このため、情報処理を行うアプリケーションの一例として、例えばMicrosoft社のExcel（商標）などの表計算アプリケーションでは、ニ次元の表において、指定された矩形内の要素の和を求める機能がある。また、MathWorks社のMATLAB（商標）などの計算用のプログラミング言語においても、行列の要素の和を求める関数がある。
【０００３】
コンピュータ・グラフィックスの分野では、F.C. Crowが長方形のsummed-areatableと呼ばれる、元の入力画像情報に対する累積画像情報の概念を提案している（非特許文献１）。この文献では、summed-area tableを入力画像と同サイズ（同要素数）のニ次元配列とし、入力画像の座標位置（ｘ,ｙ）の画素値をＩ（ｘ,ｙ）としたとき、summed-areatableの同位置（ｘ,ｙ）の成分Ｃ（ｘ,ｙ）を、
【数１】
2011059819.tif 000003
として定義している。すなわち図４の（ａ）に示すように、元の入力画像において原点位置（０，０）と位置（ｘ,ｙ）の画素を対角とする長方形内の画素の総和値が、図４の（ｂ）に示すsummed-area tableの位置（ｘ,ｙ）の値Ｃ（ｘ,ｙ）となる。尚、非特許文献１のオリジナルのsummed-areatableは、原点位置を画像左下として説明しているが、本明細書では後述の説明と整合させるため左上原点とする。
【０００４】
この定義によれば、入力画像上で水平または垂直に置かれた任意の矩形領域内のＩ（ｘ,ｙ）の和を、次の式を使ってsummed-areatable上の４点を参照するのみで求めることができる。例えば図４の（ｃ）に示すように（ｘ0,ｙ0）と（ｘ1,ｙ1）を対角とする矩形領域内の画素値の総和Ｃ（ｘ0,ｙ0;ｘ1,ｙ1）を求めるには、
【数２】
2011059819.tif 000004
とすればよい。これにより、画像上の任意の矩形領域内の値の総和を高速に求めることが可能となった。
【０００５】
画像認識の分野においては、ViolaとJonesが上記summed-areatableと同等の累積画像情報をIntegral imageと呼んでいる。そして、ViolaとJonesによれば、このIntegral imageを用いた複数の矩形フィルタからなる弱判別器を多数カスケード接続することにより、高速な顔検出処理を実現している（非特許文献２）。また特許文献１〜３も、非特許文献２の考え方に基づく物体検出方法を記載するものである。
【０００６】
非特許文献２に記載されているパターン識別法では図７の（ａ）に示すように、ある特定の大きさの矩形領域である処理ウインドウ８０１を処理対象となる画像８００内で移動させる。そして、各移動先の処理ウインドウ８０１内に人物の顔が含まれるか否かを判定する。処理ウインドウ内における顔検出処理は複数のステージによって実行され、各ステージには、異なる組み合わせの弱判別器が割り当てられている。各弱判別器は所謂Haar-like特徴を検出するもので、矩形フィルタの組み合わせで構成されている。非特許文献２では、このような構成により、顔検出に代表される高速なパターン識別を実現している。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００４−１８５６１１号公報
【特許文献２】特開２００５−０４４３３０号公報
【特許文献３】特開２００５−２９３０６１号公報
【非特許文献】
【０００８】
【非特許文献１】F. C. Crow, “Summed-AreaTablesFor Texture Mapping”, Computer Graphics, 1984.
【非特許文献２】P. Viola, M. Jones, “Rapid ObjectDetection using a Boosted Cascade of Simple Features”, Proc. IEEE Conf.onComputer Vision and Pattern Recognition, Vol. 1, pp.511-518, December 2001.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
入力画像情報から、上述のsummed-area tableあるいはintegralimageと呼ばれる累積画像情報を生成するにあたり、通常は計算され得る最悪値に基づき格納するバッファのビット精度が定められる。そして、ビット精度に基づいてバッファのサイズ（一時に保持する領域の大きさ）が決定される。すなわち、入力画像情報の幅（横方向画素数）をＸimg、高さ（縦方向画素数）をＹimgとし、各画素のビット精度をＮimgビット（但し正の整数）とすると、当該最悪値Ｃmaxとは、全ての画素値が最大値Ｉmaxをとる場合の全画素総和値となる。すなわち、
【数３】
2011059819.tif 000005
【００１０】
従って、累積画像情報を格納するバッファの１要素ビット精度Ｎbufは、Ｃmaxを格納可能なビット精度Ｎbuf_maxとする必要があり、画像サイズにも依存するがＮimgよりもかなり大きな値となる。例えば、ＶＧＡサイズの８ビットGrayscale画像を入力画像とする場合、Ｎimg＝8、Ｘimg＝640、Ｙimg＝480である。したがって、Ｃmax＝78336000＝4AB5000h、つまりＮbuf＝Ｎbuf_max＝27bit精度のバッファを用意する必要がある。入力画像情報に対する累積画像情報を全域分、一時に持つ必要がある場合には、Ｎbuf_max×Ｘimg×Ｙimg＝8294400bitものＲＡＭ等のメモリ領域を準備する必要があり、処理リソースを圧迫する。そこで、バッファのビット精度Ｎbufをなんらかの方法で低減する必要がある。特にこのような累積情報に基づく処理をハードウェアで行う場合、ワークメモリの容量は回路規模に直結するため切実な問題である。また、ソフトウェアによる処理であっても、Ｎbufを低減できれば、より小さい型を用いることが可能となって、リソース消費量を抑えることができる。
【００１１】
非特許文献１においては、バッファのビット精度Ｎbufを低減するための１つの方法について述べられている。すなわち、入力情報を例えば１６×１６画素のブロックに分割し、各々のブロックについて独立にSummed-area tableを計算する。入力情報のビット精度Ｎimg＝８bitであれば、このとき必要なバッファのビット精度は１６bitとなる。そしてこれとは別に、各ブロック毎にその左上端コーナーの左上斜め方向に隣接する画素位置に対応する、元のSummed-areatableの３２bit値を保持するようにする。所望の位置に対応する値を復元するには、当該位置の１６bitの値に、当該位置が含まれるブロックが保持する３２bit値を加算すれば良い、としている。
【００１２】
しかしながら、実際に元のSummed-area tableの値を復元するには、これだけの演算では不十分である。すなわち、従来４点を参照して式（２）のような簡単な加減演算を行うのみで、所望の領域の総和値を求めることができたのに対し、各点の値を復元するための演算が加わることにより、演算負荷は大幅に増大する。ハードウェアによる処理では、演算のための回路規模が増大することになるし、ソフトウェアによる処理を行う場合であっても、処理速度を低下させる。
【００１３】
本発明は上述した課題に鑑みてなされたものであり、演算のための回路規模や処理負荷を増大させることなく、累積情報を保持するバッファ容量を低減することを目的とする。
【課題を解決するための手段】
【００１４】
上記課題を解決するための、本発明の一態様による情報処理方法は、
複数次元配列の入力情報を複数の分割領域に分割する分割工程と、
前記複数の分割領域の各々について、それぞれの基準位置からの前記入力情報の各要素位置における累積値を計算することにより累積情報を生成する生成工程と、
前記生成工程により生成された前記累積情報をメモリに保持する保持工程と、
予め定められた処理範囲について、前記累積情報を利用した演算処理を行う演算処理工程とを備え、
前記分割工程では、隣接する２つの分割領域がオーバーラップ領域を有するように前記入力情報を前記複数の分割領域へ分割し、前記オーバーラップ領域は少なくとも前記処理範囲の全体が収まる大きさを有する。
【発明の効果】
【００１５】
本発明によれば、演算のための回路規模や処理負荷を増大させることなく、累積情報を保持するバッファ容量を低減することが可能となる。
【図面の簡単な説明】
【００１６】
【図１】実施形態による情報処理装置の構成例を示すブロック図である。
【図２】実施形態による情報処理装置の累積情報生成部の構成例を示すブロック図である。
【図３】実施形態による情報処理装置の累積情報利用演算部の構成例を示すブロック図である。
【図４】（ａ），（ｂ）は、二次元入力情報に対する、一般的な累積画像情報の生成方法を説明する図、（Ｃ）は、累積画像情報を用いて、所望の矩形領域内要素の総和値を求める方法を説明する図である。
【図５】累積情報を保持するバッファのビット精度を削減する技術の例を説明する図である。
【図６】（ａ），（ｂ）は、実施形態におけるオーバーラップ分割累積情報の一例を示す図である。
【図７】（ａ）は、パターン認識処理の一例である、顔検出処理を説明する図、（ｂ）は、複数の弱判別器で構成されるパターン識別器の構成例を示す図である。
【図８】複数の弱判別器で構成されるパターン識別器における検出処理を示すフローチャートである。
【図９】本発明の好適な一実施形態である情報処理装置の全体的な処理の流れを示すフローチャートである。
【図１０】（ａ），（ｂ）は、二次元入力情報に対する一次元方向のみの分割によるオーバーラップ分割累積情報の一例を示す図、（ｃ）は、一次元方向のみの分割によるオーバーラップ分割累積情報のバンドバッファによる保持を説明する図である。
【図１１】実施形態の情報処理装置において、オーバーラップ分割累積情報をバンドバッファにより保持した場合の全体の処理の流れを示すフローチャートである。
【図１２】（ａ）〜（ｃ）は、ダブルバッファ型ブロックバッファによるオーバーラップ分割累積情報の保持の一例を説明する図、（ｄ）は、オーバーラップ分割累積情報をブロックバッファにより保持した場合の演算オーバーヘッドの起こる領域を示す図である。
【図１３】実施形態の情報処理装置において、オーバーラップ分割累積情報をダブルバッファ型ブロックバッファにより保持した場合の全体の処理の流れを示すフローチャートである。
【図１４】多次元累積情報の一例である三次元累積情報の説明図である。
【図１５】三次元累積情報の処理ウインドウによるスキャン動作を説明する図である。
【図１６】三次元累積情報を保持するためのバッファの形態の一例を示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明の発明を実施するための実施形態について、図面を用いて説明する。尚、本明細書においては、従来技術で説明したSummed-area tableあるいはIntegral Imageのような、二次元以上の複数次元配列の入力情報に基づき累積加算演算により生成される同次元の配列情報を、単に累積情報と呼んでいる。特に入力情報が二次元配列の画像情報である場合には、累積画像情報と呼ぶ。尚、本実施形態において、入力情報の各要素は正の整数（または固定小数点の数）として表される。なお、入力情報が画像情報である場合、要素とは画素を指すことになる。
【００１８】
［第１実施形態］
（ブロック図解説）
図１は本発明の一実施形態である情報処理装置の構成を示すブロック図である。ＣＰＵ１０１は、バス１０５を介して接続される各部を制御し、情報処理装置が目的とする所望の処理を実現する。情報入力部１０２は複数次元の入力情報、例えば処理対象となる入力画像データ、を装置内に取り込む。情報入力部１０２は、例えばＣＣＤなどの画像センサによって構成されても良いし、ネットワーク等所定の通信経路を持って外部装置から処理したいデータを受信するＩ／Ｆ装置であってもよい。外部メモリ１０４は、ＲＯＭやＲＡＭあるいはＨＤＤ等のストレージ装置で構成され、バス１０５に接続されている。外部メモリ１０４は、ＣＰＵ１０１が動作するためのプログラムコードを記憶したり、各種処理を行う上での作業領域として用いられたりする。また、必要に応じて、入力情報を保持するための領域としても用いられる。ＤＭＡコントローラ１０３（以下、ＤＭＡＣ１０３）は、ＣＰＵ１０１が設定して動作指令することにより、情報入力部１０２、外部メモリ１０４、後述の累積情報演算処理部１００間の所定サイズのデータ転送を、自立的に連続に行うことが可能である。ＤＭＡＣ１０３は、指令された転送動作が完了すると、バス１０５を介して割り込み信号をＣＰＵ１０１に通知する。累積情報演算処理部１００は、バス１０５に接続するためのバスＩ／Ｆ１１０、累積情報生成部１１１、累積情報利用演算部１１２、累積情報保持部１１３、分割制御部１１４を有する。
【００１９】
累積情報保持部１１３は、累積情報を保持するためのビット精度Ｎbufの累積情報保持メモリと、当該メモリへの入出力を制御するメモリコントローラを具備する。なお、ビット精度Ｎbufについては後述する。累積情報生成部１１１は、情報入力部１０２より入力された画像データ等の処理対象情報から累積情報を生成し、累積情報保持部１１３へと格納する。この際、分割制御部１１４の制御により、単純な累積情報ではなく、オーバーラップ分割累積情報を算出する。なお、オーバーラップ分割累積情報とは、処理対象画像を、図６に示されるように境界で所定のオーバーラップ領域を持った分割領域に分割し、それら分割領域ごとに算出された累積情報であり、詳細は後述する。累積情報生成部１１１は、複数の分割領域の各々において、それぞれの基準位置からの入力情報の各要素位置における累積値を計算することにより累積情報を生成するものであり、その詳細は、図２を用いて後述する。累積情報利用演算部１１２は、ＣＰＵ１０１からの要求に従って累積情報保持部１１３に保持されているオーバーラップ分割累積情報を用いた演算処理を行い、結果をＣＰＵ１０１に返す。累積情報利用演算部１１２の詳細は、図３を用いて後述する。
【００２０】
分割制御部１１４には、あらかじめ分割パラメータが設定されており、複数次元配列の入力情報を複数の分割領域に分割する。分割パラメータとは、処理対象画像をどのようなオーバーラップ領域を持っていくつに分割するのか、といった情報を規定するパラメータである。例えば本実施形態では、１６画素×１６画素のサイズの処理ウインドウ（後述）分を分割領域の境界におけるオーバーラップ領域とし、縦横各次元方向を２等分に４分割する（図６参照）、ということが分割パラメータによって規定されているとする。分割パラメータのフォーマットは、分割の状態が表現できるものであれば、任意である。なお、分割パラメータは、あらかじめ何らかの手段（例えばＣＰＵ１０１）により、分割制御部１１４に設定されている。
【００２１】
分割制御部１１４は、分割パラメータにしたがって、オーバーラップ領域情報を含むブロック領域情報を累積情報生成部１１１、累積情報利用演算部１１２に出力する。ブロック領域情報のフォーマットは、オーバーラップ付分割の状態が表現できるものであれば、任意である。例えば図６の場合、第１ブロック７０２１は入力情報のａ，ｅ，ｆ，ｉを合わせた領域、領域ｅ，ｉは第２ブロック７０２３とのオーバーラップ領域、領域ｆ，ｉは第３ブロック７０２３とのオーバーラップ領域、という情報がブロック領域情報となる。また、処理対象画像をオーバーラップ付で分割したそれぞれの小画像をオーバーラップ付分割領域と呼ぶことにする。なお、オーバーラップ領域は後述する顔検出処理等の後段処理において用いられる処理ウインドウの全体が収まる大きさを有する。
【００２２】
（後段処理を含んだ処理の流れ）
次に、本実施形態の情報処理装置における、後段処理まで含んだ全体の処理の流れについて説明する。図９は、本実施形態の情報処理装置による全体処理を示すフローチャートである。
【００２３】
まず、Ｓ１１００において、ＣＰＵ１０１は、累積情報演算処理部１００に対する設定を含む装置の初期設定を行う。この処理では、分割制御部１１４に対する先に説明した分割パラメータの設定や、後段処理における処理ウインドウ位置を入力情報の原点を含む位置に初期化する設定を含む。そして、ユーザの操作や不図示の外部装置からの処理開始トリガに応じて、ＣＰＵ１０１は、情報入力処理Ｓ１１０１を実行する。この処理では、情報入力部１０２より入力情報を受信し、必要に応じて外部メモリ１０４に蓄積する。本実施形態では、複数次元配列の入力情報を、所定サイズの二次元配列として表される画像データであるものとして説明するが、本発明の本質によれば、三次元以上の多次元配列情報が入力情報であってももちろんかまわない。
【００２４】
Ｓ１１０２おいて、累積情報演算処理部１００は、外部メモリ１０４に蓄積された入力情報を用いて累積情報生成処理を行う。本実施形態においては、この処理はオーバーラップ分割累積情報を生成する処理であり、後に詳述するが、入力情報に基づいて分割領域ごとの累積情報を生成し、分割領域ごとに累積情報保持部１１３に保持させる。ＣＰＵ１０１はＤＭＡＣ１０３を設定し、外部メモリ１０４から累積情報演算処理部１００への入力情報要素値の逐次転送を行わせる。またここで、Ｓ１１０２の進行情報に合わせ、Ｓ１１０１とＳ１１０２を並列に処理するような構成とすることも可能である。すなわち、１ライン入力される毎にＳ１１０１とＳ１１０２を繰り返すようにするか、あるいは１要素入力単位でパイプライン的に連続処理させることもできる。このとき後段処理等で入力情報そのものが利用されないならば、ＣＰＵ１０１はＤＭＡＣ１０３に対し、直接、情報入力部１０２から累積情報演算処理部１００へ、入力情報の各要素を逐次自動転送するように設定するようにすることもできる。
【００２５】
累積情報保持部１１３に累積情報が生成されると、Ｓ１１０３において、ＣＰＵ１０１は、累積情報を利用した演算処理を行うメイン処理を実行する。本実施形態の情報処理装置では、メイン処理として、非特許文献２に記載されたようなパターン識別処理（顔検出）を行うものとするが、累積情報を用いる他の処理を適用することももちろん可能である。パターン識別処理等のメイン処理（Ｓ１１０３）が完了した後、ＣＰＵ１０１は、所望の後段処理としてＳ１１０４を行う。これは、例えば外部装置やユーザ等に処理結果等を通知する処理でもよいし、認識結果を利用して行うその他諸々の処理である。尚、本明細書で述べている後段処理とは、累積情報を用いるメイン処理Ｓ１１０３以降の処理を指している。
【００２６】
（Ｓ１１０３のパターン識別処理について）
本実施形態のパターン識別処理では、図７の（ａ）に示すように、ある特定の大きさの矩形領域（８０１）で示される処理範囲（以下「処理ウインドウ」と呼ぶ）を、処理対象となる画像８００内で移動（シフト）させる。そして、各移動先の処理ウインドウ８０１内に人物の顔が含まれるか否かが判定される。図７の（ｂ）は、各移動先位置における処理ウインドウ８０１において行われる顔検出処理の流れを示す図である。処理ウインドウ内における顔検出処理は、複数のステージによって実行され、各ステージには、異なる組み合わせの弱判別器が割り当てられている。各弱判別器は所謂Haar-like特徴を検出するもので、矩形フィルタの組み合わせで構成されている。図７の（ｂ）に示すように、各ステージに割り当てられる弱判別器の数も異なっている。また、各ステージには判定を実施する順番が割り当てられており、各ステージはその順番に従って処理を行う。即ち、例えば図７の（ｂ）において、第１ステージの次に第２ステージが判定を実施し、その次に第３ステージが判定を実施する。
【００２７】
各ステージは、自身に割り当てられた順番に、自身に割り当てられたパターンの弱判別器を用いて、処理ウインドウ内に人物の顔が含まれるか否かを判定する。あるステージにおいて、処理ウインドウ内に人物の顔が含まれないと判定された場合、それ以降の順番のステージでは、この位置における処理ウインドウについての判定は実施されない（カスケード処理は打ち切られる）。そして、最後の順番のステージによる判定で、処理ウインドウ内に人物の顔が含まれると判定された場合に、この移動先における処理ウインドウ内に人物の顔が含まれると判定される。
【００２８】
図８は、顔検出処理の流れを示すフローチャートである。次に、図８を用いて、顔検出処理の具体的な流れについて説明する。顔検出処理において、ＣＰＵ１０１は、まず処理の対象となる処理ウインドウ８０１を顔検出対象画像８００上に配置する（Ｓ１００１）。基本的には、この処理ウインドウは、図７の（ａ）に示されるように顔検出対象画像８００の端から一定間隔で縦方向及び横方向へスキャンすることによって順に網羅的に移動して選択される。例えば、顔検出対象画像８００をラスタスキャンすることによって処理ウインドウが選択される。次に、ＣＰＵ１０１は、選択された処理ウインドウについて、処理ウインドウに人物の顔が含まれるか否かを判定する。この判定は、図７の（ｂ）を用いて説明したように、複数のステージを用いて実施される。このため、まず判定を実施するステージが第一のものから順に選択される（Ｓ１００２）。
【００２９】
選択されたステージは判定処理を実施する（Ｓ１００３）。このステージの判定において、累積得点（説明は後述）がステージごとにあらかじめ決められている閾値を超えなかった場合（Ｓ１００４−ＮＯ）、処理ウインドウに人物の顔が含まれないと判定され（Ｓ１００８）、Ｓ１００７以降の処理が実行される。Ｓ１００７以降の処理については後述する。一方、累積得点（説明は後述）がステージごとにあらかじめ決められている閾値を超えた場合（Ｓ１００４−ＹＥＳ）、その判定処理（Ｓ１００３の判定処理）が最終ステージによる処理であったか否かが判断される。最終ステージでなかった場合（Ｓ１００５−ＮＯ）、Ｓ１００２の処理に戻り次のステージが選択され、新たに選択されたステージによって判定処理が実施される。一方、最終ステージであった場合（Ｓ１００５−ＹＥＳ）、現在の処理ウインドウに人物の顔が含まれるという最終的な判定がなされる（Ｓ１００６）。この時点で、この処理ウインドウに人物の顔が含まれると判断したことになる。
【００３０】
次に、判定の対象となっていた処理ウインドウが、顔検出対象画像の中で最後の処理ウインドウであったか否かを判断する。最後の処理ウインドウではなかった場合（Ｓ１００７−ＮＯ）、Ｓ１００１の処理に戻り、次の処理ウインドウが選択され、Ｓ１００２以降の処理が実行される。一方、最後の処理ウインドウであった場合、この顔検出対象の入力画像に対する顔検出処理は終了する。
【００３１】
次に、各ステージにおける判定の処理内容について説明する。各ステージには、１以上のパターンの弱判別器が割り当てられる。この割り当ては学習処理において、AdaBoost等のブースティング学習アルゴリズムによって実施される。各ステージは、自身に割り当てられたパターンの弱判別器に基づいて、処理ウインドウ内に顔が含まれるか否かの判定を行う。各ステージでは、各ステージに割り当てられた各パターンの弱判別器に基づいて、処理ウインドウ内の複数の矩形領域における特徴量がそれぞれ算出される。このとき用いられる特徴量は、各矩形領域内の画素値の合計や平均等、即ち矩形領域内の画素値の合計を用いて算出される値である。この矩形領域内総和値は、図４の（ｃ）で説明したように、入力画像に対する累積画像情報（Summed-areatableあるいはIntegral Image）を用いることにより高速に計算可能である。そして、本実施形態では、この累積画像情報が累積情報演算処理部１００から高速に取得されることになる。
【００３２】
次に、算出された特徴量について、相対値（例えば比や差分値。ここでは特徴量の差分値が算出されると想定する）としての差分値が算出され、この差分値に基づいて処理ウインドウに人物の顔が含まれるか否かの判定が実施される。具体的には、算出された差分値が、判定に用いられているパターンの弱判別器に設定された閾値よりも大きいか否か又は小さいか否かが判定される。そして、この判定の結果に応じて、処理ウインドウにおける人物の顔の存否が判定される。ただし、この時点での判定は、各パターンの弱判別器それぞれに基づいた判定であり、ステージによる判定ではない。このように、各ステージでは、割り当てられた全てのパターンの弱判別器それぞれに基づいて個別に判定が実施され、それぞれの判定結果が得られる。
【００３３】
次に、ステージにおける累積得点算出される。各パターンの弱判別器には個別のスコアが割り当てられている。処理ウインドウに人物の顔が含まれると判定されると、そのとき使用されたパターンの弱判別器に割り当てられたスコアが参照され、当該ステージの累積スコアに加算される。このようにして、加算されたスコアの総計が、ステージにおける累積スコアとして算出される。そして、このステージにおける累積スコアが特定の閾値（累積スコア閾値）を越えた場合に、このステージでは処理ウインドウに人物の顔が含まれる可能性有りと判定し、次のステージでの処理に移る。一方、このステージにおける累積スコアが累積スコア閾値を越えない場合、このステージでは処理ウインドウに人物の顔が含まれないと判定し、カスケード処理を打ち切る。以上のような手順により、顔検出に代表される高速なパターン識別が実現される。尚、図７の（ｂ）や図８に示した検出器は、予め適正な学習を行っておけば、顔以外のパターン識別器として用いることももちろん可能である。
【００３４】
上述のように、図８のパターン識別処理においては、Ｓ１００３の判定処理において、各弱判別器で所定のHaar-like特徴を検出するため、各矩形領域内要素の総和値を得る必要がある。ＣＰＵ１０１は、累積情報利用演算部１１２を動作させて、この総和値を高速に得ることが可能である。累積情報利用演算部１１２の動作については、後ほど詳しく説明する。以下、累積情報演算処理部１００の各部について詳細に説明する。
【００３５】
（累積情報生成部１１１の動作説明）
続いて累積情報生成部１１１の構成と動作について説明する。
本発明においては、累積情報の算出手順は特に問われないが、本実施形態の累積情報生成部１１１は、非特許文献１（非特許文献２にも同じ手順が記載されている）に記載されている手順で算出するものとする。つまり、入力画像の画素値をＩ（ｘ,ｙ）、累積情報をＣ（ｘ,ｙ）、ある垂直方向座標ｙにおける水平方向の画素値の累積値をＳ（ｘ,ｙ）としたとき、
【数４】
2011059819.tif 000006
により、累積情報が順次算出される。ただし、座標は０から始まるとし（原点は画像左上端）、Ｓ（０,ｙ）＝I（０,ｙ）、Ｃ（ｘ,０）＝Ｓ（ｘ,０）とする（つまり、Ｓ（−１,ｙ）並びにＣ（ｘ,−１）は０とする）。
【００３６】
本実施形態の累積情報生成部１１１は、各々のブロックの累積情報を算出する際、夫々のブロックの原点位置に相当する左上端位置を基準として、式（４）の手順により分割領域累積情報を算出する。例えば、図６の第１ブロック７０２１では、ａの領域の左上端（つまり入力情報の原点位置）を原点と見なしたｘ，ｙ座標系により、（４）式でａ，ｅ，ｆ，ｉの領域内で連続する累積情報が生成される。また、第２ブロック７０２２では、ｅの領域の左上端を原点と見なしたｘ，ｙ座標系により、第１ブロック７０２１とは別の変数領域を用いて、（４）の式によりｅ，ｂ，ｉ，ｇの領域内で連続する累積情報が生成される。同様に第３ブロック７０２３では領域ｆの左上端が、第４ブロック７０２４では領域ｉの左上端が原点位置となるｘ，ｙ座標系が用いられて、夫々の領域に対応する累積情報が生成される。以下、各分割領域（ブロック）における累積値の算出に用いられる原点位置を基準位置という。このようにオーバーラップ分割累積情報を算出する際には、夫々異なった位置を基準とする水平方向累積値（Ｓ）および累積情報値（Ｃ）を使用する必要があり、その判別のために分割制御部１１４から受け取るブロック領域情報が利用される。
【００３７】
図２は、以上のような演算により累積情報を算出する累積情報生成部１１１の構成と、バスＩ／Ｆ１１０および累積情報保持部１１３との接続の様子を示すブロック図である。入力情報サイズ記憶レジスタ２０１は、情報入力部１０２より入力される複数次元配列情報（本実施形態では二次元の画像情報）のサイズを記憶する。入力情報サイズ記憶レジスタ２０１には、バスＩ／Ｆ１１０を介してＣＰＵ１０１により、処理開始前に上記サイズ値が設定される。入力要素値保持レジスタ２０３は、バスＩ／Ｆ１１０を介してＣＰＵ１０１もしくはＤＭＡＣ１０３の制御により入力される入力配列情報の１要素値（本実施形態では画素値）を、順に一時的に保持する。本実施形態では、情報入力部１０２または外部メモリ１０４から、画像情報の１画素ずつがラスタスキャン順に累積情報演算処理部１００に送られ、入力要素値保持レジスタ２０３に保持されるものとする。
【００３８】
アドレスカウンタ２０２は、入力情報サイズ記憶レジスタ２０１に記憶されている入力配列情報のサイズに基づき、入力値保持レジスタに要素値が入力される毎に、対応して生成される累積情報値を格納すべきメモリアドレスを計算する。算出されるメモリアドレスは、累積情報保持部１１３の累積情報保持メモリ１１３１のアドレスである。アドレスカウンタ２０２は、入力情報の最初の画素（原点位置）が入力されると、格納すべきアドレスは０または所定のオフセット値にリセットされると共に、現在の入力画素の座標を原点（０,０）であると記憶する。そして、アドレスカウンタ２０２は、続く画素が入力される毎にｘ軸座標をインクリメントさせ、ｘ軸座標が入力情報サイズ記憶レジスタ２０１に記憶されているｘ軸方向のサイズに達したら０戻すと共に、ｙ軸座標をインクリメントさせる。アドレスカウンタ２０２は、これを入力情報の最終画素の入力まで繰り返すことによって、現在の入力画素座標を計算する。そして、アドレスカウンタ２０２は、分割制御部１１４より送られてくるブロック領域情報を参照し、保持している現在の入力画素座標値から、入力された画素が例えば図６のａ〜ｈのどの領域に属するものかを判別する。各領域に対応する累積情報を生成するブロックは、ブロック領域情報より判別できる。アドレスカウンタ２０２は、対応するブロックに割り当てられた累積情報保持メモリ１１３１の領域アドレスを計算する。このときオーバーラップ領域の画素であれば、アドレスカウンタ２０２は、対応するブロックは複数存在することになるので、夫々の対応する格納先アドレスを計算する。
【００３９】
また、アドレスカウンタ２０２が計算した入力画素座標値は、初期化制御部２０７に出力される。さらにアドレスカウンタ２０２は、入力画素が各ブロックの２ライン目以降であると判定したとき、そのブロックにおける１ライン前の同列位置の累積情報（すなわち式（４）のＣ（ｘ,ｙ−１）に相当）の格納アドレスを計算する。本実施形態において、各ブロックの累積情報は累積情報保持メモリ１１３１の連続するアドレス領域に保持されるようにしているので、このアドレスは先に算出したアドレスから当該ブロックの１ラインの要素個数を引くことにより得られる。逆にこの減算結果が負（もしくはオフセットより小）であれば、当該ブロックにおいては、まだ１ライン目の要素値を投入中であるということが判別できる。アドレスカウンタ２０２が計算したアドレスは、メモリコントローラ１１３２に与えられ、累積情報保持メモリ１１３１の該当するアドレスへの書き込みまたは読み出しが実行される。
【００４０】
前ライン累積情報値参照レジスタ２０５は、アドレスカウンタ２０２が算出した各ブロック毎の一つ前のラインにおける累積情報アドレスを用いて累積情報保持メモリ１１３１から読み出された累積情報値を、一時的に保持する。但し、初期化制御部２０７が初期化指示を出力していれば、累積情報保持メモリ１１３１から読み出された累積情報値に関わらず、前ライン累積情報値参照レジスタ２０５には０がセットされる。現ライン累積値保持レジスタ２０４は、現在投入中の画素に対応するブロック内の１ラインについて、当該ブロック領域の先頭画素（左端）からの累積加算情報値（式（４）のＳ（ｘ−１,ｙ）に相当する値）を保持する。入力要素値保持レジスタ２０３に画素が投入された時点では、その前回までの画素の累積加算値が保持された状態となっている。このレジスタ値は投入中の画素に対応する各ブロック領域内の１ラインについてのみ保持するものである。したがって、ブロック内において次ラインになった場合には、現ライン累積値保持レジスタ２０４は、初期化制御部２０７からの初期化指示により０にセットされる。尚、本実施形態においては、現ライン累積値保持レジスタ２０４および前ライン累積情報値参照レジスタ２０５は、オーバーラップ付分割された複数のブロックそれぞれに対する値を、同時に保持することが可能となっている。
【００４１】
初期化制御部２０７は、分割制御部１１４から送られてくるブロック領域情報を用いて、現ライン累積値保持レジスタ２０４と前ライン累積情報値参照レジスタ２０５に対して夫々のブロックに対応する値の初期化の指示を行う。これは、累積情報演算処理部１００で算出されるのが、原点基準の１つの連続した累積情報でなく、ブロックごとに基準位置を代えて算出された累積情報（オーバーラップ分割累積情報）であるからである。つまり、式（４）を用いて累積情報を算出する際にＳ（−１，ｙ）並びにＣ（ｘ，−１）は０としたが、これと同様の設定を各ブロック毎に行う必要があるためである。初期化制御部２０７は、前ライン累積情報値参照レジスタ２０５に対しては、入力してくる画素が、各ブロックの上端のラインに属する画素である場合には、当該ブロックのための値を保持している領域に対し初期化を指示し、０を設定させる。また、初期化制御部２０７は、現ライン累積値保持レジスタ２０４に対しては、入力してくる画素が各ブロックの左端の列に属する画素である場合には、当該ブロックのための値を保持している領域に対し初期化を指示し、０を設定させる。もちろん、初期化制御部２０７は、これらの条件に当てはまらないブロックのための値を保持している領域については初期化しない。
【００４２】
累積加算処理部２０６は、加算器２０６１と加算器２０６２を具備する。加算器２０６１、２０６２は、入出力共にビット精度がＮbuf（Ｎbufは正の整数）である。加算器２０６１は式（４）の上側の式の加算を担い、加算器２０６２は式（２）の下側の式の加算を担っている。加算器２０６１において、現ラインの累積値（本例では水平方向累積値）と入力画素値との加算が行われる。加算された結果は、新たな水平方向累積値として、現ライン累積値保持レジスタ２０４へフィードバック格納され、次の画素が入力されてきた時に使用される。加算器２０６２においては、加算器２０６１の出力と前ライン累積情報値参照レジスタ２０５に保持されている累積情報値との加算が行われる。この加算結果が当該入力画素位置に対応するオーバーラップ分割累積情報値となり、メモリコントローラ１１３２を介して、累積情報保持メモリ１１３１の先に述べたアドレスカウンタ２０２で計算された格納アドレスに格納される。
【００４３】
尚、本実施形態においてオーバーラップ領域に対応する累積情報値の生成演算は、累積加算処理部２０６を時系列的に順に用いることにより実現している。もちろん生成する累積情報値を保持するブロックに応じて、前ライン累積情報値参照レジスタ２０５や現ライン累積値保持レジスタ２０４の保持する各値、およびアドレスカウンタ２０２で生成された格納先アドレスを切り替えている。
【００４４】
なお、上記実装も可能であり、例えば前ライン累積情報値参照レジスタ２０５、現ライン累積値保持レジスタ２０４、およびアドレスカウンタ２０２を、ブロック毎に別々の専用ハードウェアで実装することもできる。このようにすると、入力要素値保持レジスタ２０３への入力画素値の入力と、各ブロックの累積情報値の演算処理をパイプライン化して同時に行うようにすることができ、累積情報生成処理を高速化することが可能となる。
【００４５】
（累積情報利用演算部の説明）
続いてメイン処理Ｓ１１０３内で用いられている累積情報利用演算部１１２の構成と動作について説明する。
【００４６】
本実施形態では、累積情報を利用した演算結果を用いるメイン処理（後段処理）として、図７〜図８で説明したパターン識別処理を行っている。従って必要とする演算結果は、処理ウインドウ８０１内に相対的に配置される、Haar-like特徴を検出する弱判別器の各矩形内要素の総和値である。入力画像の任意の矩形領域内要素の総和値は、図４の（ｃ）で説明したように累積画像情報の４点の要素値を参照することで計算することができる。
【００４７】
図３は、累積情報利用演算部１１２と、バスＩ／Ｆ１１０および累積情報保持部１１３との接続の構成を示すブロック図である。入力情報サイズ記憶レジスタ２０１は、図２で説明したのと同一のものであり、先に説明したように、累積情報生成前にＣＰＵ１０１によりバスＩ／Ｆ１１０を介して予め入力情報のサイズが設定されている。
【００４８】
ＣＰＵ１０１はまず処理ウインドウ内における総和値を求める特定領域（矩形領域）を特定する。そしてＣＰＵ１０１は、この矩形領域を表す処理ウインドウ内の２点の対角座標（相対座標）を、入力情報の原点からの絶対座標、すなわち図４の（ｃ）における（ｘ0,ｙ0）,（ｘ1,ｙ1）に変換する。そして、バスＩ／Ｆ１１０を介して領域指定レジスタ３０１にこの絶対座標値を設定する。ブロック決定処理部３０６は、分割制御部１１４より送られてくるブロック領域情報に基づき、領域指定レジスタ３０１で指定されている特定領域を完全に含むブロックを選択する処理を行う。尚、このブロック選択処理は、ＣＰＵ１０１から処理ウインドウ位置を通知し、処理ウインドウ位置に基づいて選択する方法を取っても良い。あるいは、ＣＰＵ１０１がどのブロックを用いるか選択し、選択結果を通知してくるように実装することも可能である。
【００４９】
参照アドレス計算部３０２は、分割制御部１１４から送られてくるブロック領域情報と、ブロック決定処理部３０６により選択されたブロック示す選択ブロック番号と、領域指定レジスタ３０１に設定されている値を参照する。そして、指定された特定領域（例えば図４の（ｃ）におけるＡ，Ｂ，Ｃ，Ｄの４点の位置）の値を格納しているブロックの当該累積情報値を格納する累積情報保持メモリ１１３１のアドレスを計算する。そしてこのアドレス値を順にメモリコントローラ１１３２に渡す。メモリコントローラ１１３２は、送られてくるアドレスに基づき累積情報保持メモリ１１３１にアクセスし、順次取得した４点の累積情報値を参照値一時保持レジスタ３０３に格納する。
【００５０】
参照値一時保持レジスタ３０３に４点の累積情報値が保持されると、加減算処理部３０４は４点の値を用いた所定の加減算処理を実行する。ここで所定の加減算処理とは、式（２）に示した演算を行うものである。この演算結果は、演算結果保持レジスタ３０５に保持される。ＣＰＵ１０１は演算完了を、バスＩ／Ｆ１１０を介して割り込み通知や完了フラグの参照等によって知ることができる。そして演算結果保持レジスタ３０５の値を取得し、設定した矩形領域の総和値として使用する。尚、本実施形態において、加減算処理部３０４で用いられている加減算器は、全てＮbufビットの正の値を入出力とするものである。
【００５１】
（本実施形態によるビット削減／演算簡易化の効果について）
ここで、本実施形態によるビット削減効果、演算簡易化の効果をより理解するために、非特許文献１に述べられている、オーバーラップ無しのブロック分割によって、累積情報を保持するバッファのビット精度を削減する方法について説明する。尚、先に述べたとおり非特許文献１に明記されている演算のみでは、元の分割されない累積情報値を復元するには不十分であるので、以下にはこの点に改良を加えた方法について図５を用いて説明する。
【００５２】
図５の（ａ）は、このブロック分割による累積情報の保持方法の一例を説明する図である。６００は、Ｘimg×Ｙimg画素の大きさの入力画像をＸsub×Ｙsub画素のブロックに分割し、夫々のブロック毎に左上端の画素を原点として累積画像情報を生成した様子を示す。各ブロックの累積画像情報をサブ累積情報と呼んでＣsub(j,k)と表し、夫々のブロックにおいて左上端の画素を原点（０,０）としたときの位置（Ｘsub,Ｙsub）の値（サブ累積情報値）をＣsub(j,k)（Ｘsub,Ｙsub）として表す。但し、ｊは横方向のブロック位置、ｋは縦方向のブロック位置（共に０スタートの整数値）を表す。また、０≦ｘsub＜Ｘsub、０≦ｙsub＜Ｙsubである。このとき、各Ｃsub(j,k)（Ｘsub,Ｙsub）の最悪値Ｃmax_subは、
【数５】
2011059819.tif 000007
となって、これを格納可能なビット精度Ｎbuf_subがＣsub(j,k)を格納するために必要なバッファに要求されるビット精度となる。なお、Ｉmaxは、ビット精度Ｎimgの入力情報値として取り得る最大値、すなわち２Ｎimg−１である。
【００５３】
そして別途、各ブロックＣsub(j,k)毎に、夫々の右下端位置における従来の全域で演算した累積情報値Ｒsub(j,k)（代表累積情報値６０１と呼ぶ）を記憶するバッファＲsub６０２を用意する。すなわち、式（１）と対応付けると、
【数６】
2011059819.tif 000008
である。ここで、Ｒsub６０２のビット精度は従来の累積情報であるのでＮbuf_maxである。また、
【数７】
2011059819.tif 000009
とすると、Ｒsubの要素数はブロック数に等しいので（Ｊmax＋１）（Ｋmax＋１）で表される。但し、式中の÷は整数除算であり、余りは切り捨てるものとする。
【００５４】
さて、全てのブロックのサブ累積情報Ｃsub(j,k)一式と、代表累積情報Ｒsubが記憶されているとする。このとき、例えば図５の（ａ）に示す点Ｘの位置に対応する従来の累積画像情報値Ｃ（ｘ,ｙ）を復元するには、画素６１０の位置の代表累積情報値に画素６１１における累積情報値（サブ累積情報値）の値を加えるだけでは不十分である。すなわち、画素６１２１〜６１２５の位置のサブ累積情報値も加算する必要がある。従って、
【数８】
2011059819.tif 000010
として、
【数９】
2011059819.tif 000011
なる計算を行うことにより、所望の位置Ｘの従来の累積情報値を再現することができる。但し、mod(a,b)は整数除算ａ÷ｂを行った際の余である。また、ｊ＝０またはｋ＝０のとき、Ｒsub（ｊ−１,ｋ−１）＝０とする。４点それぞれの値をこのようにして求めたら、通常の累積画像情報と同様に式（２）の計算を行い、矩形領域の総和値を求めることができる。
【００５５】
例えば上述の課題の項で説明したのと同条件すなわち、Ｎimg＝８、Ｘimg＝６４０、Ｙimg＝４８０の入力画像に対し、Ｘsub＝Ｙsub＝１６とする。この場合、上記実施形態の累積情報の保持方法によれば、Ｃmax_sub＝ＩmaxＸsubＹsub＝65280＝FF00ｈであるので、ビット精度はＮbuf_sub＝１６bitとなる。生成する累積情報を一時に全て保持するとしても、用意すべきバッファ容量トータルは、Ｎbuf_sub×Ｘimg×Ｙimg＋Ｎbuf_max×Ｊmax×Ｋmax＝4947600bitとなる。つまり、従来のＣ（ｘ,ｙ）の値全てを保持する場合に比べ、大幅にバッファ容量が削減できていることがわかる。
【００５６】
しかしながら、このようなブロック分割によるバッファ容量削減方法には、以下に述べる問題点がある。すなわち、従来は、４点の値を参照するだけで、式（２）による簡単な加減演算のみを行えば、所望の矩形領域の総和値を求めることができた。これに対し、上述の方法では４点それぞれに対し、さらに値復元のための式（７）,（８）の演算を行わなければならない。つまり、所望の結果を得るための演算負荷が大幅に増大する。特に（７）のような演算に必要な除算器の実装は、ハードウェアによる処理を実現する際に、回路規模を大幅に増大させる。また、式（２）の演算を行うための加減算器は従来の累積情報値を用いるので、バッファのビット精度が削減されているにもかかわらず、従来と同じビット精度Ｎbuf_maxの入力が必要である。これは通常、求める部分領域の総和値を格納するのに必要なビット精度より大きいので、やはり回路規模増大の要因と成り得る。さらに、処理速度を上げるため並列演算処理を行う場合には、これら増大した回路が並列度倍で効いてくるため、より切実な問題となるし、動作クロックやパイプライン段数にも影響する。ソフトウェアにより処理を行う場合であっても、復元演算に相当する処理負荷が増えることになるため、実行速度が大幅に低下することになるのは言うまでも無い。
【００５７】
本実施形態においては、オーバーラップ領域を持ったブロック分割による累積情報を用いることにより、ビット精度の増大化を低減すると共に、計算量の増加を防止する。以下、説明する。
【００５８】
（オーバーラップ付ブロック分割）
本実施形態における累積情報の保持形態を図６に示す。７０１は入力情報である元画像であって、図４の（ａ）と同等のものである。７０２は、入力情報７０１の累積情報を、４分割で生成・保持している様子を示す。このとき入力情報７０１は、図６の（ａ）に示すように９つの領域に分割される。ｅ，ｉ，ｈのブロックは、処理ウインドウ７０３１或いは７０４１に等しい幅であって、入力情報７０１横方向の丁度中央部に配置される。f,i,hのブロックは、処理ウインドウ７０３１或いは７０４１に等しい高さであって、入力情報７０１縦方向の丁度中央部に配置される。
【００５９】
４分割された累積情報７０２は、４つのブロック（７０２1，７０２２，７０２３，７０２４）により構成される。ここで、第１ブロック７０２１は、入力情報７０１の領域ａ，ｅ，ｆ，ｉを合わせた領域に対する累積情報であって、入力情報７０１の原点位置を基準位置として生成される。第２ブロック７０２２は領域ｅ，ｂ，ｉ，ｇを合わせた領域に対する累積情報であって、領域ｅの左上端要素（ｅの原点位置）を基準位置とする。同様に第３ブロック７０２３は領域ｆ，ｉ，ｃ，ｈ、第４ブロック７０２４は領域ｉ，ｇ，ｈ，ｄをそれぞれ合わせた領域の累積情報である。なお、第３ブロック７０２３、第４ブロック７０２４は、それぞれ領域ｆの左上端（ｆの原点位置）、領域ｉの左上端（ｉの原点位置）を基準位置として生成される。
【００６０】
オーバーラップ領域７０５は、同一位置の入力情報値に基づき、２つ以上の累積情報値が生成されていることを表している。例えば第１ブロック７０２１と第２ブロック７０２２の間のオーバーラップ領域７０５は、入力情報における領域ｅ，ｉの値に対応して生成されている。もちろん第１ブロック７０２１と第２ブロック７０２２の基準位置は異なるので、生成される累積値自体は異なる値となる。他の、たとえば領域ｆ，ｈ，ｇに対応するオーバーラップ領域も同様で、隣接する２つの分割ブロック間で、同一の領域を参照して用いられる境界領域を示している。特に領域ｉに対応するオーバーラップ領域は、４つのブロック全てに含まれ、同一領域の入力情報値に基づき４つの累積情報値が生成されることになる。
【００６１】
４つのブロックの累積情報のうち、どの累積情報を用いて総和値等を求める演算を行うかは、入力情報中における処理ウインドウの位置によって決定される。スキャン開始位置（入力情報原点位置）における処理ウインドウ７０３１では、第１ブロック７０２１内の累積情報７０３２が用いられる。スキャンが進み、処理ウインドウが領域ｅと重なる位置から１画素左の位置に入ったときの様子が処理ウインドウ７０４１として示されている。処理ウインドウ７０４１では、使用する累積情報を第２ブロック７０２２に切り替え、累積情報７０４２が用いられる。尚、領域ｅと丁度重なる位置においては、第１ブロック７０２１でも第２ブロック７０２２のどちらの累積情報を使用しても良いが、本実施形態においては第１ブロック７０２１を使用するものとしている。同様に、縦方向に関しては、処理ウインドウが領域ｆ，ｉ，ｇに一致する位置より１画素下の位置に入ったら、使用する累積情報が第３ブロック７０２３あるいは第４ブロック７０２４に切り替えられる。
【００６２】
つまり、一時に使用される累積情報のブロックは、処理ウインドウの位置に応じて、一つだけである。先に述べたとおり、各ブロックは基準位置（＝累積開始地点）の異なった累積情報を保持している。しかし、オーバーラップ領域が存在することにより、一時に同一のブロックからしか矩形領域を示す４点を参照しないことになる。従って、式（８）や（９）に示すような換算等の余分な演算は不要となり、常に式（２）に示す演算を行うのみで、所望の矩形領域の総和値を得ることが可能となる。
【００６３】
このようにすると、各ブロックの右下端の位置すなわち図６の７０６に示す位置において、累積情報値が確実にオーバーフローしないビット精度をバッファのビット精度Ｎbufとすれば良いようになる。つまり１つのブロックの対応する領域において、入力情報が全て最大値を取る場合Ｉmaxのブロック内総和値をオーバーフローさせないビット精度を求めれば良い。もちろん本発明の本質によれば、各ブロックは同サイズでなくとも構わないので、サイズが異なる場合には、最も大きいブロックに基づきビット精度を定めても良いし、各ブロック毎に異なったビット精度としても構わない。
【００６４】
一例として、課題の項において従来技術の説明で例示したのと同条件で考えてみる。すなわちＮimg＝８、Ｘimg＝６４０、Ｙimg＝４８０の入力画像とする。ここで後段処理に用いる処理ウインドウサイズ（＝取り得る最大矩形領域サイズ）を、例えばＸrect_max＝Ｙrect_max＝１６とする。本実施形態のように４分割するとすると、図６の７０１に示す領域ｅ，ｉ，ｈは、Ｘ座標Ｘimg／２−Ｘrect_max／２＝３１２からＸimg／２＋Ｘrect_max／２−１＝３２７の間に位置する。また、領域ｆ，ｉ，ｈは、Ｙ座標Ｙimg／２−Ｙrect_max／２＝２３２からＹimg／２＋Ｙrect_max／２−１＝２４７の間に位置する。つまり１ブロックあたりの大きさ（要素数）は、Ｘblock×Ｙblock＝３２８×２４８となり、この例では４つとも全て同じ大きさとなる。従って、この範囲の入力情報が最大値Ｉmax＝２Ｎimg−１＝２５５をとるとき、累積情報最大値は、Ｃmax_bloc＝ＩmaxＸblockＹblock＝20742720＝13C8240hとなるので、Ｎbuf＝２５bitとなる。このように、確保すべき累積情報のビット精度は、入力情報の各要素のビット精度と分割領域の大きさに基づいて決定され、本例では、２５bitとなる。したがって、入力画像全域に対し生成した累積情報を全て一時に保持する場合、用意すべきバッファ容量は、Ｎbuf×Ｘblock×Ｙbloc×４＝8134400bitとなる。すなわち、課題の項で説明した従来の累積情報を一時に保持する場合と比べ、２０KByte近くバッファ容量を節約できる。
【００６５】
なお、分割制御部１１４による分割方法は本実施形態で説明した４分割に限ったものではなく、分割数を多くする程ビット精度は削減できる。但し、隣接するブロック間でオーバーラップ領域を設ける必要があるため、１ブロックのサイズは最低限、処理ウインドウよりも全次元方向で１画素以上大きい必要がある。また、あまり細かくすると、ビット精度が削減される代わりにオーバーラップ領域が増えることによるバッファ領域増加を伴うので、必ずしも分割数が多い方が良いとは限らない。処理ウインドウの位置からどのブロックの累積情報を用いるかを判断する演算も複雑になる可能性もある。
【００６６】
従って、本実施形態のオーバーラップ付ブロック分割による累積情報保持方法では、図５を用いて上述した方法のようには、バッファ容量は削減できない。しかしながら、この点は、一時には部分的な累積情報しか保持しない方法（バンドバッファ或いはブロックバッファによる）を採用することにより解決できる（後述する）。但し、少なくとも全域にわたる累積値を保持するよりもビット精度を低減することができ、更に、元の累積値を復元するための演算が不要であることから、演算負荷や回路規模の点で図５を用いて説明した方法よりも優れていることは明らかであろう。
【００６７】
（オーバーラップ領域を定める別の方法：矩形基準）
上述のオーバーラップ領域は、後段処理の処理ウインドウのサイズに基づき定めた。これに対し、後段処理で用いる全ての矩形領域（弱判別器が用いる矩形領域）が予め分かっている場合、矩形領域の夫々の次元方向について最大のものをオーバーラップ領域の幅として定めてもよい。つまり図６において、領域ｅ，ｉ，ｈの横方向の長さは矩形領域のうち最も横方向の幅が広いものに合わせるようにしてもよい。また、同様に領域ｆ，ｉ，ｇの縦方向の長さは、矩形領域のうち最も高さの高いものに合わせるようにしてもよい。すなわち、弱判別器が用いる矩形領域を処理範囲とし、オーバーラップ領域は、それら矩形領域（処理範囲）が収まる多きさに設定される。そして、処理ウインドウの位置から所望の矩形領域を表す４点に対し、まずは絶対座標値に変換を行う。そしてこの絶対座標値の４点全てが含まれるブロックを選び、式（２）の計算をすれば所望の矩形領域の総和値を得ることができる。
【００６８】
通常矩形領域は処理ウインドウ内に含まれるものであるので、処理ウインドウよりは小さい。従って、このように最大矩形領域を基準にオーバーラップ領域を定めると、処理ウインドウ基準で定めた場合よりも、領域を小さくでき、バッファ容量をさらに削減することが可能となる。但し、この方法では、使用する矩形領域が固定的に分かっている必要があるので、例えば学習し直し等によって矩形領域が変更される可能性の有る場合には、用いることができない。なお、上述の矩形領域や処理ウインドウ８０１は、累積情報を利用した演算処理を行う後段処理における処理単位であり、本明細書ではこれらの領域を総称して処理範囲と呼ぶ。
【００６９】
［第２実施形態］（バンドバッファによる実装）
第１実施形態では、入力情報を縦横二分割ずつのオーバーラップした４つのブロックに分割して、累積情報を生成し、累積情報保持部１１３に全領域に対応する累積情報を一時に保持した。すなわち、二次元配列の入力情報を、各次元方向について分割する例について説明したが、本発明はこれに限るわけではない。
【００７０】
図１０の（ａ）、（ｂ）は、入力情報を横方向にのみ分割する場合を説明する図である。すなわち、二次元配列の入力情報を、一つの次元方向のみについて分割する例である。図１０の（ａ）において、１２０１は図４の（ａ）に示した入力情報に相当し、７つの領域に分解した様子が示されている。ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇの７つの領域の内、ｅ，ｆ，ｇの３つの領域はオーバーラップ領域であって、それぞれの領域を境界とする２つの累積情報ブロックが、共有する入力情報領域である。
【００７１】
図１０の(ｂ)において、１２０２は入力情報１２０１の、４つのブロック（１２０２１，１２０２２，１２０２３，１２０２４）からなる累積情報である。第１ブロック１２０２１は、領域ａ＋ｅに対応する累積情報であり、入力情報の原点を基準位置とする。第２ブロック１２０２２は領域ｅ＋ｂ＋ｆに対応する累積情報であり、領域ｅの左上端位置（領域ｅの原点に相当）を基準位置として生成される。同様に、第３ブロック１２０２３、第４ブロック１２０２４は、夫々、領域ｆ＋ｃ＋ｇ，領域ｇ＋ｄに対応する累積情報であって、それぞれ領域ｆ，領域ｇの左上端位置を基準位置として生成されるものである。
【００７２】
このようなブロック分割による累積情報の場合、第１実施形態と同様に後段処理の処理ウインドウの位置に応じて使用するブロックを切り替えることができる。すなわち、処理ウインドウ１２０３１に示す開始位置では、第１ブロック１２０２１内の累積情報を用いて範囲１２０３２の矩形領域内総和値を計算する。スキャンが進み、領域ｅの左端より１画素右の位置に処理ウインドウが来たら、第２ブロック１２０２２の累積情報を使用するように切り替える。たとえば、処理ウインドウ１２０４１に関しては、第２ブロック１２０２２内の累積情報を用いて範囲１２０４２の矩形領域内総和値が計算される。以下、第３ブロック１２０２３、第４ブロック１２０２４の累積情報も同様に処理ウインドウの位置に基づき切り替えて使用する。このようにすることにより、第１実施形態と同様、元の累積情報値を復元する必要なく、単純な式（２）の演算のみで、所望の矩形領域内総和値を得ることができる。もちろん、処理ウインドウでなく用いる最大矩形領域の幅基準でオーバーラップ領域を決定してもよいのは、第１実施形態と同様である。
【００７３】
第２実施形態では、４つのブロックは全て同じ幅であるように実装している。すなわち、第１実施形態で例示したのと同条件で、入力画像をＮimg＝８、Ｘimg＝６４０、Ｙimg＝４８０、処理ウインドウをＸrect_max＝Ｙrect_max＝１６とすると、幅Ｘblock＝１７２となる。もちろん縦には分割していないので、高さＹblock＝Ｙimgである。従って、この範囲の入力情報が最大値Ｉmax＝２Ｎimg−１＝２５５をとるとき、累積情報最大値は、Ｃmax_block＝ＩmaxＸblockＹblock＝21052800＝1413D80hとなる。すなわち、確保すべきビット精度は、Ｎbuf＝２５bitとなり第１実施形態に等しいビット精度となる。
【００７４】
これら４つのバッファ全域を一時に保持する場合、用意すべきバッファ容量は、Ｎbuf×Ｘblock×Ｙblock×４＝8256000bitとなり、第１実施形態より若干多くのバッファ容量が必要となる。しかしながら、このような一次元方向を除いた分割とすることにより、次に述べるように、さらにバッファ容量を節約することが可能となる。図１０の（ｃ）は、図１０の（ａ），（ｂ）に示したブロック分割された累積情報を、バンドバッファで保持する方法を示す図である。
【００７５】
図１０の（ｃ）において、１３００は（ｂ）の累積情報１２０２の全域を現している。１３０２は、一時に保持するバンド領域を表し、特に１３０２の位置は処理開始時のバンド領域の位置である。後段処理は、原点位置の処理ウインドウ１３０１より処理を開始し、１画素ずつ右方向へ処理ウインドウを移動させつつ処理を行う。このときバンドバッファに保持されるバンド領域１３０２の累積情報が用いられる。もちろん、図１０の（ａ）の１２０４１に相当する位置に処理ウインドウが来たら、オーバーラップ領域から１画素左の位置の１２０４２に相当する位置の累積情報を用いるのは、先に説明した通りである。
【００７６】
１行分の処理ウインドウのスキャンが完了したら、バンドバッファの保持する累積情報の範囲を、バンド領域１３０２からバンド領域１３０３へと１ライン下方へ移動する。このとき、バンドバッファはリングバッファとして用いられ、最も古い１ライン（すなわち原点を含む１ライン）分の累積情報が破棄され、同領域に新たに計算された１ライン分の累積情報が格納される。先に説明したとおり、累積情報は前ラインに基づき生成することができるので、ここで生成される累積情報は累積情報１２０２のものと正しく等しい。以下、同様に１行スキャンごとに１ライン分の累積情報計算と保持を行い、入力画像最終位置までの累積情報の生成とこれに同期する後段処理が完了できる。
【００７７】
尚、第２実施形態における後段処理は、第１実施形態（図８および図９を用いて説明した処理）と同等のものである。但し、Ｓ１１０３として示したメイン処理に相当する処理は、バンド領域単位で行われる。
【００７８】
上記構成によれば、一時に保持するバンドバッファの高さは、処理ウインドウの高さ以上であれば良い。従ってこのようなバンドバッファによる累積情報の保持を導入すると、用意すべきバッファ容量を著しく節約できる。例えば、先の例でいうと、Ｙblock＝１６とすればよいので、Ｎbuf×Ｘblock×Ｙblock×４＝275200bitとなり、大幅に削減できることが分かる。
【００７９】
図１１は、オーバーラップ付のブロック分割累積情報をバンドバッファで保持する際の、全体の処理の流れを示すフローチャートであり、第１実施形態における図９に相当するものである。Ｓ１４００は初期設定処理である。ここで、ＣＰＵ１０１は、第１実施形態と同様の分割パラメータや、初回の処理バンド（先頭バンド、図１０の（ａ）におけるバンド領域１２０５）の位置および処理バンド内における最初の処理ウインドウ位置を累積情報演算処理部１００に設定する。Ｓ１４０１はＳ１１０１と同等の情報入力処理である。尚、第１実施形態と同様にＳ１４０１も後述するＳ１４０２やＳ１４０５と同期して行うように実装してももちろんかまわない。
【００８０】
Ｓ１４０２は累積情報生成処理であるが、第１実施形態（Ｓ１１０１）とは以下が異なる。すなわち、ＣＰＵ１０１は、入力情報全域ではなく、先頭バンド（バンド領域１２０５）の位置に対応するオーバーラップ分割累積情報のみを生成し、累積情報保持部１１３に保持する。このとき保持されるオーバーラップ分割累積情報は、図１０の（ｃ）における領域１３０２の累積情報となる。尚、ＣＰＵ１０１やＤＭＡＣ１０３、累積情報演算処理部１００の動作は、範囲が異なるだけで基本的に第１実施形態と同様の動作を行う。
【００８１】
Ｓ１４０２により、累積情報保持部１１３におけるバンドバッファが、バンド領域１２０５に示す位置（先頭バンド位置）の累積情報を保持完了すると、メイン処理を行う（Ｓ１４０３）。メイン処理では、第１実施形態と同様に、図８で説明したパターン認識処理が実行されるものとする。まず、処理ウインドウが入力情報においてバンドの先頭位置にあるとき（たとえば処理ウインドウ１２０３１）に、図８のＳ１００２〜Ｓ１００８として説明したのと同等の所定の処理を行う。そして次にＳ１００１に相当する処理として、処理ウインドウ１２０３１を右に１画素ずらした位置に移動させ、再び所定の処理を行う。以後、処理ウインドウが現在の処理バンド（バンド領域１２０５）の右端に達するまで、第１実施形態と同様に所定の処理を繰り返す。つまり、第２実施形態においては、Ｓ１００１はバンドの左端位置から１画素ずつ右に処理ウインドウを移動させる処理であって、Ｓ１００７のスキャン終了とは１バンドの左端までの処理終了を検知する処理である。もちろん、第１実施形態で説明したのと同様、処理ウインドウの横方向の位置に応じて、使用する累積情報のブロックは切り替える。
【００８２】
１バンド分のメイン処理Ｓ１４０３が完了すると、ＣＰＵ１０１は、現在処理していたバンドが入力情報の最終ラインを含む位置であったかどうかを判別する（Ｓ１４０４）。最終ライン位置でなければＳ１４０５に進み、次の１ライン分の累積情報を生成して保持する。このとき前ライン分の累積情報はすでに累積情報保持メモリ１１３１のバンドバッファ上に存在しているので、第１実施形態で説明した生成方法と全く同様に各ブロックにおける１ライン分の累積情報を生成できる。すなわちこの演算において、バンドバッファにしたことによるオーバーヘッドは生じない。Ｓ１４０５において次ラインが生成、保持された後は、累積情報のバンド位置がバンド領域１２０５から１ライン下に移った状態となる。これは図１０の（ｃ）において、１３０３に示した範囲のオーバーラップ分割累積情報が保持された情報である。そして、ＣＰＵ１０１は、再びＳ１４０３のメイン処理を実行する。以後、Ｓ１４０４において最終ラインと判別されるまで、１ラインずつバンドを下方に移動させつつ、同様に処理を繰り返す。Ｓ１４０４で最終ラインに到達したことが判別されると、Ｓ１１０４と同様の後段処理を行って処理完了となる（Ｓ１４０６）。
【００８３】
以上のように、第２実施形態では、分割を行う次元方向については入力情報の全長を有し、分割を行わない次元方向については所定長（本実施形態では処理ウインドウの大きさ）を有する部分領域（バンド領域）について、各分割領域の累積情報が生成される。又、その累積情報の生成においては、部分領域に対する後段処理による処理が終了する毎に、部分領域を分割を行わない次元方向へシフトさせ、該シフトにより部分領域に新たに入った入力情報の要素について累積値が追加的に算出される。したがって、第２実施形態では、オーバーラップ領域の累積情報を除けば、二度以上生成される累積情報は無い。また、第１実施形態と同様に入力情報の１要素の入力処理とパイプライン化し、同一入力情報値に対応するオーバーラップ領域の累積情報値の生成は同時に行うようにすることも可能である。つまりバンド保持にしたことによる、累積情報生成のための時間的オーバーヘッドはなく、処理時間はブロック分割累積情報を全て一時に保持する場合とほとんど変わらない。そして、バッファ容量削減のみをさらに実現できる手法であると言える。また、本実施形態のように全てのバッファを同じ幅とする必要はもちろん無く、例えば計算のし易い２のべき乗等の切りのいいアドレスで分割するようにしても、もちろんかまわない。
【００８４】
また、バンドの高さを実際に用いる矩形領域の最大サイズに基づいて定めることももちろん可能であり、さらにバッファ容量を削減できる可能性がある。但し、この場合は、処理ウインドウ単位の処理ではなく、フィルタ種別単位の処理にするなど、後段処理を変更する必要がある。また、後段処理を変更したことによるオーバーヘッドが生ずる可能性もある。
【００８５】
［第３実施形態］
第２実施形態では、一時に保持する累積情報の範囲をバンド領域にすることで必要なバッファ容量を削減した。第３実施形態では、ブロックバッファでオーバーラップ付の累積情報の一部のみを一時に保持するようにして、更にバッファ容量を削減する。なお、第３実施形態では、ダブルバッファ型のブロックバッファを用いることにより、累積情報の効率の良い生成、保持方法を説明する。
【００８６】
図１２の（ａ）の１５００は、図４の（ａ）に相当する入力情報である。入力情報１５００は、処理ウインドウ１５０１に等しい幅で、横方向に領域を分割している。本実施形態のブロック分割において、オーバーラップ領域は連続的に接して配置される。すなわち、領域ａ，ｂの入力情報に対応して第１ブロックの累積情報を生成し、領域ｂ，ｃで第２ブロックを、領域ｃ，ｄで第３ブロックを、領域ｄ，ｅで第４ブロックが生成される。つまり、領域ｂ，ｃ，ｄは連続したオーバーラップ領域となる。尚、図１２の（ａ）〜（ｃ）では説明を簡単にするため入力情報全域を５等分する幅の処理ウインドウで示しているが、もっと小さい処理ウインドウを用いて、その幅で分割するようにしても、もちろん構わない。図１２の（ｂ）、(ｃ)に示す１５０４と１５０５は、第３実施形態における累積情報を保持するための２つのブロックバッファ（第１バッファ、第２バッファ）を示している。これらはダブルバッファとして構成され、一方を用いて累積情報を利用する所定の演算を行う際には、もう一方は利用されずにただ累積情報を溜める動作を行うようになっている。これについては後ほど詳述する。
【００８７】
第１、第２バッファ１５０４，１５０５の夫々は、１画素分の幅を持つ領域を単位としたリングバッファとなっており、処理ウインドウに一致する要素数すなわちＸrect_max×Ｙrect_maxなるサイズとなっている（詳細は後述する）。また各バッファにおいては、処理ウインドウを横に２つ並べた領域で連続する累積情報の、処理ウインドウ幅分のみを一時に保持する。例えば、第１バッファ１５０４が保持する累積情報は、ａ＋ｂもしくはｃ＋ｄの領域のブロックに対応する累積情報となっている。また、第２バッファ１５０５は、これより処理ウインドウ分シフトした領域すなわち、ｂ＋ｃもしくはｄ＋ｅの領域のブロックに対応する累積情報を保持する。つまり、累積情報のブロックとしてみると、Ｘblock＝２Ｘrect_max、Ｙblock＝Ｙrect_maxの大きさとなっている。より一般化して言えば、ａ＋ｂやｃ＋ｄの領域は、分割が行われた次元方向の長さは処理範囲の対応する次元方向の長さの２倍であり、オーバーラップ領域が処理範囲と同じ大きさを持つ領域である。なお、このような領域を格納する第１バッファ及び第２バッファは、２Ｘrect_max×Ｙrect_maxの容量が必要となるが、本実施形態ではリングバッファの採用によりバッファサイズをＸrect_max×Ｙrect_maxとしている。
【００８８】
各々のブロックの累積情報は、ブロックの左上端位置を基準位置として生成する累積情報となる。従って、その最悪値は、Ｃmax_block＝ＩmaxＸblockＹblock＝２ＩmaxＸrect_maxＹrect_maxで表されるので、Ｃmax_blockを格納可能なビット精度をバッファのビット精度Ｎbufとすればよいことになる。尚、Ｃmax_blockは図１２の（ｂ）の画素１５０６の位置に入る累積値の最大値である。前述の実施形態と同条件で考えると、Ｃmax_block＝130560＝1FE00ｈであるので、バッファに確保すべきビット精度はＮbuf=１７bitとなる。用意すべきバッファ容量は、処理ウインドウ分のダブルバッファであるので、Ｎbuf×Ｘrect_max×Ｙrect_max×２＝8704bitとなり、本形態によると大幅にバッファ容量を削減できることが分かる。
【００８９】
次に第３実施形態のダブルバッファ型ブロックバッファによる累積情報保持を行う場合の全体の処理の流れを、図１３のフローチャートを用いて説明する。尚、必要に応じて図１２の（ａ）〜（ｃ）も再度参照する。
【００９０】
まず、処理の開始時においてＣＰＵ１０１は初期設定処理を行う（Ｓ１６００）。この初期設定処理は、最初に処理を行う入力情報幅且つ処理ウインドウ高さ分の領域（＝処理バンド）を、入力情報の原点位置を含む最上段すなわち図１２の（ａ）のバンド領域１５０２に設定する処理を含む。また、初期設定処理は、最初に処理を行う処理ウインドウ領域として、当該処理バンドの左端の領域を設定する処理を含む。Ｓ１６０１は図９におけるＳ１１０１と同様の情報入力処理である。尚、Ｓ１６０１は第１実施形態と同様、後段の処理で入力情報を直接使うことが無ければ、後述するＳ１６０２やＳ１６０５と同期して、必要な分の入力情報のみを並列に入力するようにしてもよい。或いはＳ１６０２のみに同期して、処理バンド位置に対応してライン単位で入力するようにしてももちろん良い。
【００９１】
続くＳ１６０２において、ＣＰＵ１０１は、現在の処理バンド位置における先頭すなわち左端の処理ウインドウ領域の累積情報を生成、記憶する。すなわち、まず図１２の（ｂ）における領域ａに合致する累積情報を生成し、第１バッファ１５０４に保持する。
【００９２】
次にＳ１６０３のメイン処理が行われる。この処理は図８に示した処理と同等であるが、ここでは１箇所の処理ウインドウ分の処理のみを行えばよいので、Ｓ１００１とＳ１００７の処理は除かれる。もちろん処理ウインドウが左端の開始位置にあるとき、用いられる累積情報は第１バッファ１５０４に保持されたものであるが、処理が進むにつれて処理ウインドウの位置に応じて第２バッファ１５０５を使うときもある。これについては後述する。
【００９３】
現在の処理ウインドウに対するメイン処理が終わると、当該処理ウインドウの位置が、現在の処理バンド（バンド領域１５０２）の最終ブロックの位置、すなわち右端であったかどうかを判定する。右端であるということは、現在の処理バンド位置における処理が完了したことを示す。最終ブロックでなければ、ＣＰＵ１０１は、処理ウインドウの位置を１画素分右へシフトさせる（Ｓ１６０５）。これは図１２の（ａ）、（ｂ）において処理ウインドウ１５０１の位置として表している。このとき領域ａからはみ出た線分領域１５０７の部分が、新たに必要な累積情報値の線分（１画素分の幅をもつ領域）となる。この新規線分の累積情報は、各画素のすぐ左の累積情報値（領域ａの右端の累積情報値）に、新規線分の入力情報値の一番上の画素から各画素までの和（線分の各画素位置までの列方向累積値）を加えた値となる。これは第１実施形態や第２実施形態で、１ラインの累積情報値を計算する際に、当該画素のすぐ上のラインの累積情報値に、１ライン中の当該画素位置までの累積値を加算したのと同様で、横方向を縦方向に変えたものと考えれば理解し易い。つまり、このとき生成される第１バッファ１５０４における新規な線分領域１５０７の値は、領域ａの左上端位置（原点）を基準位置として続けて生成される累積情報値に等しい。
【００９４】
また、第３実施形態において、第１バッファ１５０４および第２バッファ１５０５は処理ウインドウサイズに等しく、線分単位のリングバッファとして構成されている。従って、新規な線分領域１５０７の累積情報を格納する物理領域は、元々原点を含む一番左の線分が保持されていた領域である。以後、１線分追加する毎に、最も古い線分の累積情報が破棄されてゆく。これは第２バッファ１５０５に関しても同様である。
【００９５】
ところで、ステップＳ１６０１において、第１バッファ１５０４に線分領域１５０７の累積情報を生成、保持するのと同時に、第２バッファ１５０５にも同サイズの線分領域の累積情報が生成、保持される。この累積情報は、第１バッファ１５０４のものとは異なり、領域ｂの左上端位置の画素を基準位置として新たに生成される累積情報である。すなわち、ステップＳ１６０５において、オーバーラップ領域（ｂ、ｃ、ｄ）の累積値が算出される際には、第１バッファ１５０４と第２バッファ１５０５には、異なる基準位置からの累積値が算出され、格納されることになる。たとえば、領域ｂでは、第１バッファ１５０４には領域ａの左上を基準位置とした累積値が格納され、第２バッファ１５０５には領域ｂの左上を基準位置とした累積値が格納される。領域ｃでは、第１バッファ１５０４には領域ｃの左上を基準位置とした累積値が格納され、第２バッファ１５０５には領域ｂの左上を基準位置とした累積値が格納されることになる。第１バッファ１５０４も第２バッファ１５０５も、累積情報を生成する上で参照する入力画素は同じであるので、累積情報生成部１１１の入力要素値保持レジスタ２０３（図２）を共用して参照することで同時にこれら２つの累積情報を生成することができる。なお、入力情報の画素の読み込みと、累積情報生成演算をパイプラインとして処理するようにすれば、２つの累積情報を生成することによる時間的オーバーヘッドはほとんど無くすことが可能である。
【００９６】
次に、再びＳ１６０３のメイン処理を移動した処理ウインドウに関して行う。このようにＳ１６０３〜Ｓ１６０５の処理を、現在の処理バンドの終端位置まで行うのであるが、ここで各バッファが保持するのは、先に述べたように、ａ＋ｂあるいはｂ＋ｃ等、あくまで２つの処理ウインドウを並べた範囲のブロックで連続する累積情報である。各バッファにおいて処理ウインドウがこのブロックからはみ出すと、はみ出した分は次のブロックに掛かるので、次のブロックの左上端を基準位置とする累積情報値を保持するように変わる。従って、Ｓ１６０３メイン処理で使用するバッファは、処理ウインドウの位置によって、第１バッファ１５０４か第２バッファ１５０５を切り替える必要がある。
【００９７】
例えば、処理ウインドウ１５０１の場合には、図１２の（ｂ）に示すように第１バッファ１５０４は処理ウインドウ１５０１内で連続した累積情報を保持しているので、第１バッファ１５０４をメイン処理に使用する。処理が進み、処理ウインドウが右へ移動して、処理ウインドウ１５０３のように領域ｂから右にはみ出した位置に処理ウインドウが移動したとする。このとき、第１バッファ１５０４は、図１２の（ｃ）に示すように、領域ａの左上端を基準位置として連続して計算された累積情報値を保持する領域１５０９と、領域ｃの左上端を基準位置として新たに計算された累積情報値を保持する領域１５１０が混在する。しかしながら、このとき第２バッファ１５０５は、領域１５１１に示すように領域ｂの左上端を基準位置とする連続した累積情報を保持している。従って、処理ウインドウ１５０３のように領域ｂと領域ｃにまたがるとき、Ｓ１６０３のメイン処理においては第２バッファ１５０５の累積情報を使用すれば良いことになる。同様に、領域ｃと領域ｄにまたがる処理ウインドウに対しては、再び第１バッファ１５０４を、領域ｄと領域ｅにまたがる処理ウインドウに対しては第２バッファ１５０５を用いることにより、常に連続した累積情報を利用することができる。累積情報利用演算は、基準位置がどこであっても、処理ウインドウ内で連続していれば、計算結果の矩形内総和値は常に保証されるので、このような保持方法が成立するのである。
【００９８】
さて、処理バンドにおける最終位置までの処理が完了したら、ＣＰＵ１０１は、全入力情報における最終ライン位置を処理したかどうかを判定する（Ｓ１６０６）。処理バンドの位置が最終ライン位置に到達していなければ、ＣＰＵ１０１は、処理バンド位置を１ライン下方に移動すると共に、処理ウインドウ位置を処理バンド位置の先頭（左端）位置に戻すよう制御する（Ｓ１６０７）。
【００９９】
そして再度、Ｓ１６０２の処理を繰り返す。このときＳ１６０２で生成されるバンド先頭ブロックの累積情報は、当該処理バンドの左上端を基準位置とするものになる。つまり前回の同ブロックの累積情報に比べ、基準位置が１ライン下方に移動したものとなる。しかし先に述べたとおり、累積情報の利用に際しては、処理ウインドウ内で連続であればよいので基準位置が変わることは問題にはならない。画してＳ１６０６において最終ラインに到達するまで、順に処理を繰り返して入力情報全域に対する処理を行う。そして、Ｓ１１０４と同等の後段処理を行って全体の処理完了となる。
【０１００】
以上説明したように、第３実施形態のダブルバッファ型ブロックバッファによる累積情報の保持方法では、極めて少ないバッファ容量とすることが可能となる。また、累積情報利用時の演算におけるオーバーヘッドもほとんど無く、むしろビット精度Ｎbufを削減できることから、この演算に限っては回路規模を低減できることが期待できる。なお、上記第３実施形態では、オーバーラップ領域が連続するように分割領域を形成したが、これに限られるものではない。たとえば図１０に示したような分割領域を用いることも可能である。その場合、たとえば、第１バッファには領域ａ＋ｅ、ｆ＋ｃ＋ｇが、第２バッファには領域ｅ＋ｂ＋ｆ、ｇ＋ｄの累積情報を格納するように構成すればよい。
【０１０１】
但し、第３実施形態のブロックバッファによる実装では累積情報を生成する上でのオーバーヘッドが生ずる。図１２の（ｄ）は、入力画像全域に対し、累積情報生成のための演算オーバーヘッドが発生する領域を示す図である。入力画像の１ライン目に対応する累積情報が生成されるのは、初回の処理バンド位置における処理ウインドウのスキャンに合わせて、１回だけである。続く２ライン目の位置においては、処理バンドが初回の位置と、次の１ライン下方の位置にあるときに、都合２回の値の異なった累積情報が生成される。同様に２ライン目は３回、４ライン目は４回、と、「最大処理ウインドウ高さ−１」回の累積情報が生成される領域が存在する。２回以上累積情報が生成される領域を示したのが１７０１である。本実施形態のブロックバッファによる構成をとると、この分の演算オーバーヘッドが発生することになるので、バッファ容量削減とのトレードオフで、本実施形態を選択するか否かを判断すればよい。
【０１０２】
［他の実施形態］
本発明の適用は、上述した実施形態に限るものではない。例えば、図６の（ｂ）や図１０の（ｂ）の１２０２として示した、オーバーラップ付でブロック分割した各領域について、一時には一つのブロックに対応する累積情報のみを生成し保持する形態を取るようにすることも可能である。さらにこの１つのブロックに対して、バンドバッファやブロックバッファを適用した生成・保持方法を取っても構わない。
【０１０３】
また、累積情報は三次元以上の多次元配列情報に対しても生成することができる。図１４は三次元の場合の累積情報の様子を例示する図である。三次元配列の入力情報とは、例えば動画情報であって、二次元画像に時間軸の一次元が加わり三次元情報となる。図１４の（ａ）において、三次元累積情報配列の点Xの位置の要素には、入力三次元情報における原点と点Ｘを対角とする直方体の中に含まれる要素の総和値となる。この三次元累積情報を用いて、例えば図１４（ｂ）の１８０１に示す直方体内の要素の総和値を求めることが可能である。ここで、１８０１の対角を示す２点の座標を（ｘ0,ｙ0,ｔ0）,（ｘ1,ｙ1,ｔ1）とする。Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈをそれぞれ、
【数１０】
2011059819.tif 000012
なる位置の累積情報値であるとすると、入力情報の直方体１８０１内要素の総和値Ｓ3dは、
【数１１】
2011059819.tif 000013
として計算することができる。
【０１０４】
この三次元累積情報においては、直方体の処理ウインドウが後段処理単位となる。図１５において１９０１は三次元入力情報時の処理ウインドウの一例を示す。この処理ウインドウをｘ軸方向、ｙ軸方向、ｔ軸方向の順にスキャンし、三次元の入力情報全域に対する処理を実行する。
【０１０５】
このような三次元入力情報に対しても、本発明を適用できることは明らかである。例えば、図１６に示すようなオーバーラップ付のブロック分割による累積情報の保持を行うことができる。図１６において、入力情報２０００と後段処理単位である処理ウインドウ２００１があるとき、累積情報は２００２および２００３に示す２つのバッファに保持される。各バッファは、夫々２００４、２００５として示すオーバーラップ領域を持ち、両オーバーラップ領域の累積情報を生成するための元の入力情報値は、同一の領域から参照される。
【０１０６】
もちろんこの例はｔ軸方向にのみ分割する一例に過ぎず、他の軸方向に分割しても良いし、複数の軸方向あるいは全軸方向に分割しても良いのは二次元の場合と同様である。このとき少なくとも一次元方向の分割を行わないブロック分割であれば、第２実施形態に示したようなバンドバッファを適用可能であるのは言うまでも無い。また、１軸方向を分割せず他の方向を分割するようなブロック分割を行えば、第３実施形態に示した処理ウインドウサイズのダブルバッファ型ブロックバッファによる保持方法を適用できることも明らかであろう。いずれの場合も、処理ウインドウ内においては連続する累積情報値を保持できるため、少なくとも累積情報利用演算における演算のオーバーヘッドはほとんど生じない。但し、分割と保持の方法によっては、累積情報生成演算のためのオーバーヘッドが生ずるのは二次元の場合と同様である。以上のように、三次元を超える多次元入力情報に対する累積情報であっても、同様に超直方体で考えれば、本発明を適用可能であるのは明らかであろう。
【０１０７】
また、本発明はハードウェア回路のみでなく、ソフトウェアによる処理であっても適用可能である。分割後の領域のサイズに応じて、分割無しでは３２bitのlong型配列を用いる必要があったところを、より小さな型を使用することができる可能性がある。或いは、区切りの悪いビット精度が必要な場合であっても、メモリアクセス時間とのトレードオフで、例えばＣ言語のビットフィールド機能等を用いることにより、メモリの利用効率を上げることができることは明らかであろう。
【０１０８】
また、上記実施形態では、バンドバッファやブロックバッファをリングバッファとして使用する例を説明したが、本発明はこのようなメモリの使用方法に限るわけではない。例えば、リングカウンタに対応するメモリアドレステーブルを有し、当該テーブルを参照することで、不連続な領域を所定の処理単位で割り当てながら処理する等の方法でも良い。即ち、本発明で述べたリングバッファとは狭義のリングバッファ或いは循環バッファに限定するものではない。
【０１０９】
また、上述の実施形態でメイン処理として説明した後段処理は、パターン認識処理に限定するものではない。本発明は、従来技術で述べたようなコンピュータグラフィクス等の他分野の処理であっても、累積情報を用い、かつ使用する可能性のある最大領域の大きさが限定できる処理であれば、適用可能であることは言うまでも無い。
【０１１０】
また、本発明は、上記第１乃至第３の実施形態と同等の処理を、コンピュータプログラムでも実現できる。この場合、図１をはじめとする構成要素の各々は関数、もしくはＣＰＵが実行するサブルーチンで機能させれば良い。また、通常、コンピュータプログラムは、ＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されており、それを、コンピュータが有する読取り装置（ＣＤ−ＲＯＭドライブ等）にセットし、システムにコピーもしくはインストールすることで実行可能になる。従って、かかるコンピュータ可読記憶媒体も本発明の範疇にあることは明らかである。
【０１１１】
以上のように、本発明によれば、二次元以上の複数次元配列である入力情報の特定領域の要素の総和値を求める処理のための、累積情報を保持するバッファ容量を低減することができる。また累積情報を利用する演算の処理負荷を低減し、回路規模を低減した高速な同処理のためのハードウェア装置を実現することが可能となる。また、同処理を実行するソフトウェアによる装置においてもバッファ容量を削減することが可能となる。
【図１】
2011059819.tif 000014
【図２】
2011059819.tif 000015
【図３】
2011059819.tif 000016
【図４】
2011059819.tif 000017
【図５】
2011059819.tif 000018
【図６】
2011059819.tif 000019
【図７】
2011059819.tif 000020
【図８】
2011059819.tif 000021
【図９】
2011059819.tif 000022
【図１０】
2011059819.tif 000023
【図１１】
2011059819.tif 000024
【図１２】
2011059819.tif 000025
【図１３】
2011059819.tif 000026
【図１４】
2011059819.tif 000027
【図１５】
2011059819.tif 000028
【図１６】
2011059819.tif 000029