(57)【特許請求の範囲】
【請求項１】
所定次元の配列に格納された複数のデータ要素を含む入力情報の当該複数のデータ要素の各々について、データ要素の前記配列における位置に対応する累積情報値を計算する計算手段と、
計算した前記累積情報値の各々を、前記配列の次元毎にそれぞれ定められた分配数だけ配列された複数の記憶手段に対して、当該累積情報値に対応する前記配列における位置の各次元成分のそれぞれの分配数に対する剰余に基づいて、前記複数の記憶手段の対応する１つに書き込む書込手段と、
前記入力情報において、前記配列の次元毎の分配数により定まる前記複数の記憶手段の排他読み出し条件を満たす形状の局所領域に対して、当該局所領域の位置に対応する複数の累積情報値を、それぞれが分配して書き込まれた前記複数の記憶手段から並列に読み出す読出手段と、
前記複数の記憶手段から読み出した前記複数の累積情報値を用いて、前記局所領域の特徴量を算出する算出手段と、
算出した前記特徴量と、予め設定された辞書データとを比較して、前記局所領域に所定のパターンが存在するか否かを判定する判定手段と
を備えることを特徴とするパターン識別装置。
【請求項２】
前記書込手段は、前記配列において互いに隣接する位置に存在するデータ要素に対応する前記累積情報値を、それぞれ異なる前記記憶手段に書き込むことを特徴とする請求項１に記載のパターン識別装置。
【請求項３】
前記配列の次元毎の分配数により定まる前記複数の記憶手段の排他読み出し条件を満たす形状の局所領域を用いて、前記辞書データを学習する学習手段を更に備えることを特徴とする請求項１または２に記載のパターン識別装置。
【請求項４】
前記局所領域の形状を示すパラメータ情報を前記複数の記憶手段の排他読み出し条件に基づいて変換する変換手段を更に備え、
前記読出手段は、変換された前記パラメータ情報に基づいて、前記累積情報値を読み出す記憶手段及びメモリアドレスを決定する
ことを特徴とする請求項１から３のいずれか１項に記載のパターン識別装置。
【請求項５】
前記配列は２次元配列であり、
前記複数の記憶手段は、Ｐ×Ｑ個（Ｐ、Ｑは(Ｐ,Ｑ)≠(１,１)なる１以上の整数）の記憶手段Ｍpq（pは０からＰ−１の整数、qは０からＱ−１の整数）であり、
前記書込手段は、前記２次元配列の座標（ｘ,ｙ）のデータ要素に対応する前記累積情報値を、p＝ｘ％Ｐ、q＝ｙ％Ｑ（%は剰余演算）に従い、前記記憶手段Ｍpqに書き込む
ことを特徴とする請求項１から４のいずれか１項に記載のパターン識別装置。
【請求項６】
前記配列は１次元配列であり、
前記複数の記憶手段は、Ｐ個（Ｐは２以上の整数）の記憶手段Ｍp（pは０からＰ−１の整数）であり、
前記書込手段は、前記１次元配列の座標（ｘ）のデータ要素に対応する前記累積情報値を、p＝ｘ％Ｐ（%は剰余演算）に従い、前記記憶手段Ｍpに書き込む
ことを特徴とする請求項１から４のいずれか１項に記載のパターン識別装置。
【請求項７】
前記配列は３次元配列であり、
前記複数の記憶手段は、Ｐ×Ｑ×Ｒ個（Ｐ、Ｑ、Ｒは(Ｐ,Ｑ,Ｒ)≠(１,１,１)なる１以上の整数）の記憶手段Ｍpqr（pは０からＰ−１の整数、qは０からＱ−１の整数、rは０からＲ−１の整数）であり、
前記書込手段は、前記３次元配列の座標（ｘ,ｙ,ｔ）のデータ要素に対応する前記累積情報値を、p＝ｘ％Ｐ、q＝ｙ％Ｑ、r＝ｔ％Ｒ（%は剰余演算）に従い、前記記憶手段Ｍpqrに書き込む
ことを特徴とする請求項１から４のいずれか１項に記載のパターン識別装置。
【請求項８】
計算手段が、所定次元の配列に格納された複数のデータ要素を含む入力情報の当該複数のデータ要素の各々について、データ要素の前記配列における位置に対応する累積情報値を計算する計算工程と、
書込手段が、計算した前記累積情報値の各々を、前記配列の次元毎にそれぞれ定められた分配数だけ配列された複数の記憶手段に対して、当該累積情報値に対応する前記配列における位置の各次元成分のそれぞれの分配数に対する剰余に基づいて、前記複数の記憶手段の対応する１つに書き込む書込工程と、
読出手段が、前記入力情報において、前記配列の次元毎の分配数により定まる前記複数の記憶手段の排他読み出し条件を満たす形状の局所領域に対して、当該局所領域の位置に対応する複数の累積情報値を、それぞれが分配して書き込まれた前記複数の記憶手段から並列に読み出す読出工程と、
算出手段が、前記複数の記憶手段から読み出した前記複数の累積情報値を用いて、前記局所領域の特徴量を算出する算出工程と、
判定手段が、算出した前記特徴量と、予め設定された辞書データとを比較して、前記局所領域に所定のパターンが存在するか否かを判定する判定工程と
を備えることを特徴とするパターン識別装置の制御方法。
【請求項９】
コンピュータを請求項１から７のいずれか１項に記載のパターン識別装置が備える各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はパターン識別装置及びその制御方法、プログラムに関し、特に、累積情報を用いた画像認識、或いは情報分析などを行うための技術に関する。
【背景技術】
【０００２】
情報処理分野においては、多次元配列情報を頻繁に取り扱う。その中でも、画像処理、画像認識や画像合成等に関わる一部処理や統計処理等では、特定領域範囲内における要素の総和値を求めて使用することが多い。
【０００３】
コンピュータ・グラフィックスの分野では、F. C. Crowが矩形のsummed-area tableと呼ばれる、元の入力画像情報に対する累積情報の概念を提案している（非特許文献１）。この文献のsummed-area tableは入力画像と同サイズ（同要素数）の２次元配列である。入力画像の座標(x,y)の画素値をI(x,y)とすると、summed-area tableの位置(x,y)の成分C(x,y)は式（１）のように定義される。
【０００４】
【数１】
0005759126.tif 000002
すなわち図７に示すように、元の入力画像(a)において原点位置(0,0)と位置(x,y)の画素を対角とする矩形内の画素の総和値がsummed-area table(b)の位置(x,y)の値C(x,y)となる。なお、非特許文献１のオリジナルのsummed-area tableは、原点位置を画像左下として説明しているが、本明細書では後述の説明と整合させるため左上原点とする。
【０００５】
この定義によれば、入力画像上で水平または垂直に置かれた任意の矩形領域内のI(x,y)の和を、次の式を使ってsummed-area table上の4点を参照するのみで、求めることができる。例えば図８に示すように(x0,y0)と(x1,y1)を対角とする矩形領域内の画素値の総和C(x0,y0;x1,y1)を求めるには、式（２）の計算を行えばよい。
【０００６】
Ｃ(x0,y0;x1,y1)＝
Ｃ(x0−１,y0−１)−Ｃ(x0−１,y1)−Ｃ(x1,y0−１)＋Ｃ(x1,y1)          (2)
これにより、画像上の任意の矩形領域内の値の総和を高速に求めることが可能となった。特許文献１には式（２）に基づいて累積情報を計算する構成が記載されている。
【０００７】
画像認識の分野では、ViolaとJonesが上記summed-area tableと同等の累積情報をIntegral Imageと呼んでいる。そのIntegral Imageを用いて複数の局所領域で特徴量を算出し、パターン識別を行っている（非特許文献２）。局所領域（local area）とは、入力画像から切り出された画像領域の部分領域を示す。
【０００８】
パターン識別では複数の局所領域で特徴量を算出するが、これら特徴量には予め学習によって求められたパラメータが使われる。パラメータは特徴量を算出する局所領域の位置や大きさなどの情報が含まれる。
【０００９】
パターン識別は参照する局所領域の数が非常に多く、特徴量算出のために累積情報が頻繁に読み出される。例えば、一度に１つのデータの読み出しが行えるシングルポート型のメモリに累積情報を格納した場合、４頂点分の読み出しはシリアル化され４回のメモリアクセスで処理される。１回のメモリアクセスに１サイクルかかるとすると１つの矩形領域を求めるためには最低でも４サイクルが必要となる。
【００１０】
検出条件（フレームレート、画像サイズ、検出対象物の数などの条件）によってはメモリアクセスがボトルネックとなる場合がある。この場合、４回の読み出しをシリアル化せずにアクセスを全部または一部、並列に処理できるようにし、高速化することが要求される。
【００１１】
この読み出し時間を削減する手法の１つとして、一度に２つの読み出しを行えるデュアルポート型のメモリに累積情報を格納し、読み出し時間を削減することがあげられる。また他の手法として、同一の累積情報を４つのシングルポート型のメモリに書き込んでおくことで、４頂点をそれぞれのメモリから同時に読み出すこともあげられる。
【００１２】
さらに、特許文献２には、画像を複数の積算領域に分割し、当該積算領域ごとにいずれかの角に位置する画素を起点とするインテグラルイメージを生成し、当該インテグラルイメージに基づいて画像の読み出し領域の総和を算出することが記載されている。この構成では、読み出し領域のいずれかの角または辺を、インテグラルイメージ生成の基点となる画素に合わせることで、読み出し回数を削減している。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２００８−２９９６２７号公報
【特許文献２】特開２００８−１０２７９２号公報
【非特許文献】
【００１４】
【非特許文献１】F. C. Crow, “Summed-Area Tables For Texture Mapping”, Computer Graphics, 1984.
【非特許文献２】P. Viola, M. Jones, “Rapid Object Detection using a Boosted Cascade of Simple Features”, Proc. IEEE Conf. on Computer Vision and Pattern Recognition, Vol. 1, pp.511-518, December 2001.
【発明の概要】
【発明が解決しようとする課題】
【００１５】
しかしながら、デュアルポート型のメモリを使うようにポート数を増やす手法では増やしたポート数分、回路規模が大きくなる。４頂点の同時読み出しのためにはさらにポートを増やして４ポートにする必要があるが実装上の制約も増え、実現が難しくなる。また、４個のメモリに同じ値を格納する手法は４倍の回路規模が必要となり、メモリサイズを多く確保できない状況下では実現は難しい。
【００１６】
また、特許文献１に示される手法は、累積情報を格納するメモリではなく、バッファのサイズを削減することで回路規模を削減するものである。この手法は、メモリの読み書きを高速化するものではない。
【００１７】
さらに、特許文献２に示される手法は、読み出し位置によっては従来と同じ４回の読み出しが必要となるという課題がある。すなわち、この手法では、読み出し領域のいずれかの角または辺を上記基点画素に合わせることができる範囲でのみ有効であるが、積算領域の中の任意の４点の読み出しについては、上述のような従来技術の課題が依然として存在する。
【００１８】
本発明は上記課題に鑑みなされたものであり、メモリ容量を増大させずに累積画像を高速に読み書き可能とするための技術を提供することを目的とする。
【課題を解決するための手段】
【００１９】
上記目的を達成するため、本発明によるパターン識別装置は以下の構成を備える。即ち、
所定次元の配列に格納された複数のデータ要素を含む入力情報の当該複数のデータ要素の各々について、データ要素の前記配列における位置に対応する累積情報値を計算する計算手段と、
計算した前記累積情報値の各々を、前記配列の次元毎にそれぞれ定められた分配数だけ配列された複数の記憶手段に対して、当該累積情報値に対応する前記配列における位置の各次元成分のそれぞれの分配数に対する剰余に基づいて、前記複数の記憶手段の対応する１つに書き込む書込手段と、
前記入力情報において、前記配列の次元毎の分配数により定まる前記複数の記憶手段の排他読み出し条件を満たす形状の局所領域に対して、当該局所領域の位置に対応する複数の累積情報値を、それぞれが分配して書き込まれた前記複数の記憶手段から並列に読み出す読出手段と、
前記複数の記憶手段から読み出した前記複数の累積情報値を用いて、前記局所領域の特徴量を算出する算出手段と、
算出した前記特徴量と、予め設定された辞書データとを比較して、前記局所領域に所定のパターンが存在するか否かを判定する判定手段と
を備える。
【発明の効果】
【００２０】
本発明によれば、メモリ容量を増大させずに累積画像を高速に読み書き可能とするための技術を提供することができる。
【図面の簡単な説明】
【００２１】
【図１】実施形態１に係るパターン識別装置の構成を示すブロック図
【図２】実施形態１に係る全体処理のフローチャート
【図３】実施形態１に係るパターン識別処理のフローチャート
【図４】実施形態１に係るメモリへの分配を説明する図
【図５】実施形態１に係る局所領域と読み出し座標を説明する図
【図６】実施形態１に係る同時読み出しを説明する図
【図７】入力画像情報に対する累積画像情報の生成方法を説明する図
【図８】総和算出のため累積画像情報から読み出す座標を説明する図
【図９】処理ウィンドウを説明する図
【図１０】実施形態２に係るパターン識別装置の構成を示すブロック図
【図１１】実施形態２に係るパラメータ変換処理のフローチャート
【図１２】実施形態３に係る一次元累積情報のメモリへの分配を説明する図
【図１３】実施形態４に係る三次元累積情報と局所空間を説明する図
【図１４】累積情報を異なるメモリに分配する例を示す図
【発明を実施するための形態】
【００２２】
＜＜実施形態１＞＞
以下、本発明の一実施形態について、図面を参照して説明する。本実施形態においては、従来技術で説明したSummed-area tableあるいはIntegral Imageのような、二次元配列の情報を累積画像情報と呼ぶ。また、二次元配列の画像情報（RGB画像やGrayscale画像のような画像情報だけでなく一次微分フィルタをかけた画像など、加工された画像情報も含む）を入力画像情報と呼ぶ。
【００２３】
（パターン識別装置の構成）
本実施形態ではまずパターン識別装置の構成について説明する。その後、累積画像情報のメモリへの分配方法と同時読み出しについて説明し、最後に学習について説明する。
【００２４】
図１は実施形態１に係るパターン識別装置の構成を示すブロック図である。101はCPUであって、バス105を介して接続される各部を制御する。102は入力画像情報を入力するデータ入力部であって、処理対象となる入力画像情報を装置内に取り込む。データ入力部102は、例えばCCDなどの画像センサによって構成されてもよいし、ネットワーク等所定の通信経路を持って外部装置から処理したいデータを受信するＩ／Ｆ装置であってもよい。
【００２５】
104はバス105に接続される外部メモリであって、ROMやRAMあるいはHDD等のストレージ装置で構成されている。外部メモリ104は、CPU101が動作するためのプログラムコードを記憶したり、各種処理を行う上での作業領域として用いられる。また、必要に応じて、入力画像情報やパターン識別に使用する各種情報を保持するための領域としても用いられる。103はDMAコントローラ（以下、DMAC）であって、CPU101が設定して動作指令することにより、データ入力部102、外部メモリ104、パターン識別部107に所定サイズのデータ転送を、自律的に連続に行うことが可能である。指令された転送動作が完了すると、バス105を介して割り込み信号をCPU101に通知する。
【００２６】
107はパターン識別部であって、DMAC103からバス105を介して送られてくる入力画像情報をパターン識別処理する。パターン識別処理は入力画像情報に所定の検出パターン（例えば顔や人体の立像など）か否かを判定し、検出位置、検出形状、尤度などの検出情報を出力する。検出情報はバス105を介して外部メモリ104に書き込まれる。
【００２７】
パターン識別部107は以下の構成要素を有する。
・バスインタフェース111。
・累積画像情報生成部112。
・分配書き込み処理部113。
・メモリアクセス制御部114。
・メモリ115〜118。
・識別処理制御部119。
・辞書記憶部120。
・特徴量算出部121。
・判定処理部122。
・処理ウィンドウ管理部123。
本実施形態のメモリ115〜118はシングルポート型のメモリである。ただし、デュアルポート型のメモリや他の多ポート型のメモリで構成しても構わない。パターン識別部107が備える各構成要素の役割・動作については後述する。
【００２８】
（全体処理）
次に図１のパターン識別装置の詳細と全体の処理の流れを、図２のフローチャートを参照して説明する。
【００２９】
○データ入力処理
実施形態１に係るパターン識別装置は、ユーザの操作や不図示の外部装置からの処理開始トリガによって、まずデータ入力処理S201を実行する。S201では最初に、CPU101の指示によってデータ入力部102より入力画像情報を受信し、バス105を介して外部メモリ104に蓄積する。次に外部メモリ104に蓄積された入力画像情報をDMAC103によってパターン識別部107に転送される。
【００３０】
パターン識別部107はバス105を介して転送されてくる入力画像情報をバスインタフェース111で受け、累積画像情報生成部112に転送する。本実施形態では入力画像情報は画像左上の画素から画素単位でラスタ順に入力される場合の例を説明する。
【００３１】
○累積画像情報生成処理
次に、S202では累積画像情報生成処理を行う。累積画像情報生成部112はラスタ順で送られる入力画像情報を累積処理し、累積画像情報を生成する。累積画像情報は入力画像情報の画像左上の画素を原点として画素値を累積し、累積結果を順次、分配書き込み処理部113に転送する。累積処理の詳細については従来技術で説明した通りであり、説明は省略する。
【００３２】
○分配書き込み処理
次にS203では累積画像情報の分配書き込み処理を行う。分配書き込み処理部113はまずメモリに対して書き込みを行ってよいか処理ウィンドウ管理部123に問い合わせる。処理ウィンドウ管理部123は分配書き込み処理部113からのメモリの書き込みと識別処理制御部119からの読み出しの排他制御を管理している。
【００３３】
処理ウィンドウとはパターン識別処理が処理を行う単位である。図９は処理ウィンドウを説明する図である。900は入力画像情報で、901は１つの処理ウィンドウを示し、処理ウィンドウ901の画像領域がパターン識別処理を行う１単位である。そして、処理ウィンドウ901に対してパターン識別処理を行い、この処理ウィンドウ901に所定の検出パターンが存在するかどうかを判定する。処理ウィンドウは入力画像情報900の左上の処理ウィンドウ901から順に右方向に移動し、それぞれの位置でパターン識別処理をする。右端に達したら左端にもどって下方向に移動する。以上の移動を繰り返し右下位置まで順に移動させる。
【００３４】
分配書き込み処理部113は処理ウィンドウ管理部123から所定個数の書き込み許可を受ける。そして、分配書き込み処理部113は累積画像情報の画素単位で書き込み先のメモリ番号（メモリ115〜118）とアドレスを決定し、メモリアクセス制御部114に書き込み（書込処理）を指示する。メモリ番号とアドレスの決定方法の詳細は累積情報のメモリへの分配方法として後述する。
【００３５】
メモリアクセス制御部114は、指示されたメモリ番号とアドレスに従ってメモリ115〜118に累積画像情報を格納する。分配書き込み処理部113は、所定個数の書き込みが終了すると処理ウィンドウ管理部123に書き込み終了を通知する。
【００３６】
○パターン識別処理
次にS204でパターン識別処理を行う。パターン識別処理は従来技術で説明したような複数の弱判別器で判定を行う。弱判別器を使った処理方法はいくつかあるが、ここではある処理ウィンドウにおいて局所領域の総和を算出し、その算出結果を用いて弱判別器で判定する処理を複数回繰り返す。以下、パターン識別処理の詳細を図３のフローチャートにて示す。
【００３７】
パターン識別処理はまずS301で処理ウィンドウを要求する。識別処理制御部119は処理ウィンドウ管理部123に対して処理対象となる処理ウィンドウを要求する。処理ウィンドウ分のデータがメモリ115から118に準備できたら次のS302に移る。
【００３８】
次にS302では辞書データの読み込み処理を行う。識別処理制御部119は辞書記憶部120に格納されている辞書データをもとに識別処理を開始する。辞書データは予め学習によって得られたパラメータ群である。辞書データには累積画像情報から特徴量を算出する局所領域の位置や形状、判定処理の係数や閾値などのパラメータが格納されている。
【００３９】
次にS303では特徴量パラメータの送信処理を行う。識別処理制御部119は辞書データのパラメータから局所領域の４頂点分のメモリ番号とアドレスを算出し、メモリアクセス制御部114に累積画像情報の読み出しを指示する。また、特徴量算出部121、判定処理部122で使用するパラメータ（係数、閾値など）も辞書データから取り出して特徴量算出部121、判定処理部122に設定する。
【００４０】
次にS304では累積画像情報の読み出し処理（読出処理）を行う。メモリアクセス制御部114は指示されたメモリ番号とアドレスに対応するメモリからデータを読み出して、特徴量算出部121に送る。メモリアクセス制御部114は読み出し時において、メモリ番号が排他関係にある場合、すなわち、メモリ番号が互いに異なる場合に同時読み出しを行う機能を備える。同時読み出しの詳細は後述する。本実施形態の構成は４頂点を読み出すメモリを常に排他関係にし同時読み出しできるようにする。
【００４１】
次にS305では特徴量を算出する処理を行う。特徴量算出部121は読み出した４頂点の値から総和値を算出し、S303で設定されたパラメータを使用して特徴量を算出する。そして、特徴量の算出結果は判定処理部122に送られる。
【００４２】
次にS306では結果判定の処理を行う。判定処理部122は特徴量の算出結果とS303で設定されたパラメータとを使用・比較して判定を行う。設定されるパラメータは例えば閾値で特徴量の算出結果がその閾値よりも高ければ所定の検出パターンである（以下、True判定）、閾値よりも低ければ所定の検出パターンでない（以下、False判定）という判定がなされる。True判定の場合、判定結果は識別処理制御部119に送られ、S307に移る。一方、False判定の場合、判定が確定（以下、False確定）し、S308に移る。
【００４３】
次にS307では全局所領域の識別が終了したか判定する。識別処理制御部119は判定結果がTrue判定であればS302に戻り次の局所領域用の辞書データを読み込み、S302からS306の処理を所定の局所領域数分繰り返し行う。所定の局所領域全てでTrue判定が得られたら、所定の検出パターンであることが確定（以下、True確定）し、S308に移る。
【００４４】
次にS308では処理ウィンドウの終了通知を行う。識別処理制御部119は処理ウィンドウ管理部123に対して処理が終了したことを通知する。通知を受けた処理ウィンドウ管理部123は次の処理ウィンドウを準備する処理を開始する。
【００４５】
識別処理制御部119は処理対象となった処理ウィンドウの最終結果がTrue確定の場合、識別処理制御部119はその処理ウィンドウの位置情報をバスインタフェース111を介して外部メモリ104に書き出す。一方、False確定の場合は、判定結果は書き出さない。
【００４６】
以上のパターン識別処理が入力画像情報の全処理ウィンドウにわたって処理が繰り返される。全ての処理ウィンドウについて処理が終了すると（S309でTrue）、パターン識別処理を終了し、S205に移る。
【００４７】
○後処理
次にS205では後処理を行う。後処理では、識別処理制御部119は全処理ウィンドウのパターン識別処理が終了したことをCPU101に対して通知する処理等を実行する。
【００４８】
（メモリへの分配）
次に累積画像情報のメモリへの分配方法と同時読み出し、そして学習について説明する。まず累積画像情報を本実施形態における所定の規則に従ってメモリへ分配する方法について説明する。本実施形態における所定の規則とは隣接する画素を異なるメモリに分配する方法である。
【００４９】
図４の400は累積画像情報を示す。ここでは累積画像情報400の左上を原点、横方向をｘ、縦方向をｙとして各画素の座標を（x,y）で表す。原点座標は(0,0)とする。累積画像情報400の１つの四角が１画素を示す。
【００５０】
次に本実施形態における上記所定の規則について一般化したものを説明する。累積画像情報400の座標(ｘ,ｙ)の画素値をC(x,y)で表す。そして、ｘ方向の分配数をP、ｙ方向の分配数をQとする。P,QはP=1かつQ=1を除く１以上の整数であり（すなわち、(Ｐ,Ｑ)≠(１,１)）、分配するメモリの総数はＰ×Ｑ個とし、メモリはMpqで表す（記憶手段Ｍpq）。p,qはメモリ番号で、pはｘ方向のメモリ番号値、qはｙ方向のメモリ番号値を示す。
【００５１】
このとき、C(x, y)の格納先は式（３）のように表される。
Mpq[address] = C(x,y)                                  (3)
また、座標(x,y)の画素値を格納するメモリ番号p,qは次式（４）（５）で表される。
p = ｘ％Ｐ                                            (4)
q = ｙ％Ｑ                                            (5)
ただし、% は剰余演算を表す。
【００５２】
そして、メモリMpqの各座標（x',y'）は式（６）（７）で表される。
x' = x ／ P                                           (6)
y' = y ／ Q                                           (7)
なお、x', y' を算出する際の除算（／）においては、小数点以下を切り捨てる。
【００５３】
また、メモリMpqに格納する画像の幅をm_width として定義すると、m_widthは分配元の累積画像情報の幅widthとPの値から以下のような式で表すことができる。
m_width = width ／ P                                   (8)
なお、m_widthを算出する際の除算（／）においては、小数点以下を切り上げる。
【００５４】
格納先のメモリMpqへのaddressは次式で表される。
address = m_width * y' + x'                             (9)
以上が累積画像情報を所定の規則に従ってメモリへ分配するために一般化した式である。
【００５５】
次に、具体的に本実施形態で説明したメモリ115〜メモリ118に分配する場合について図４を用いて説明する。図４では、ｘ方向の分配数を２（P=2）、ｙ方向の分配数を２（Q=2）としたものである。また、メモリMpqに格納する画像の幅m_widthは累積画像情報400の画像幅width=8で、P=2なので４となる。以上を踏まえて各座標の累積画像情報400を分配する。
【００５６】
例えばC(3,2)の格納先は式(4),(5)より、p=1, q=0、式(6),(7)より、x'=1, y'=1、式(9)より、address=5となる。この結果、式(3)はM10[5]=C(3,2)であらわされ、C(3,2)の値はメモリ(M10)のaddress=5に格納することになる。これらの計算によって累積画像情報400は図４のメモリ115から118に分配されて格納される。図４の410から413は各メモリの配列を２次元的に表現したものである。メモリと２次元表現の画素データ中に記載された数値は対応する累積画像情報400の座標を示している。
以上が本実施形態における累積画像情報のメモリへの分配方法である。
【００５７】
本実施形態ではラスタ順に累積画像情報が入力されることを説明したが、この場合、格納先のメモリ番号の計算、アドレス計算の代わりにカウンタを使って加算計算のみで実装することも可能である。本実施形態の構成は、式（３）から（９）で示される関係でメモリに分配して格納することが重要であって、実装方法の違いに制約されるものではない。
【００５８】
次に、分配して格納した累積画像情報から局所領域の４頂点の値を同時に読み出す方法について説明する。同時読み出しを行うためには、読み出すメモリを排他関係にしなければならない。そのため局所領域の形状に対して次の条件を定義する。まずは一般化した条件式について説明する。
【００５９】
局所領域の形状として幅la_widthと高さla_heightを定義すると、本実施形態の分配規則に応じて導出される条件式は式（１０）（１１）で示される。
la_width != P * n                                (10)
la_height != Q * m                               (11)
ただし、 n, mはともに１以上の整数である。また、条件式（１０）、（１１）で使われている!=は否定を表す。つまりla_widthはPの倍数以外の値であること、la_heightはQの倍数以外の値であることを示す。
【００６０】
以上の条件式（１０）、（１１）の両方を満たすことで読み出すメモリを排他関係にすることができ、局所領域の４頂点の値を同時に読み出すことができるようになる。また、条件式（１０）、（１１）のどちらか一方を満たすことができれば局所領域の２頂点の値を同時に読み出すこともできる。また、P、Qの値を３以上に増やした場合、条件式（１０）、（１１）よりla_width、la_heightの値域がP=2、Q=2のときに比べて広がることがわかる。例えばP=2の場合、la_widthは奇数となるので幅１から５までの中から選択できるものは１，３の２個となる。一方、P=5の場合は５の倍数以外となるので、１，２，３，４の４個となり選択肢が広がることがわかる。
【００６１】
（累積画像の読み出し）
次に具体的に本実施形態で説明したメモリ115〜メモリ118より４頂点のデータを同時に読み出す方法について説明する。図５は分配前の累積画像情報400に局所領域を重ねた図である。図５の500の太枠の矩形が局所領域を示す。そして、画素501から504が局所領域の読み出す４頂点の画素である。局所領域500は条件式（１０）、（１１）に示される条件を満たすla_width=3、la_height=3の矩形領域である。図５の累積画像情報400の模様は図４のメモリへの分配で説明したものと対応しており、画素501〜504は別々のメモリに格納されている画素であることがわかる。また、図６はメモリ115からメモリ118の中身を表した図で、メモリ内に記載されている数値は累積画像情報400に対応する座標である。画素501はメモリ(M10)、画素502はメモリ(M00)、画素503はメモリ(M11)、画素504はメモリ(M01)に排他関係になっていることがわかる。そして、これらのデータは排他関係にあるためメモリアクセス制御部114によって同時に読み出すことができる。
【００６２】
（学習）
次に学習について説明する。これまで同時読み出しの条件について説明したがここではこの条件を満たすための学習方法について説明する。学習はパターン識別処理において画像中に含まれるものが検出パターンかどうか識別するための基準を決定する手法として広く使用されている。本実施形態では学習によって決定されたパラメータを辞書データと呼んでいる。
【００６３】
学習とは、所定の検出パターンを含むことがわかっている複数のサンプル画像と所定の検出パターンを含まないことがわかっている複数のサンプル画像の各々から所定のパラメータを導出し、記録することをいう。この所定のパラメータの中には局所領域の位置、大きさの導出が含まれている。
【００６４】
学習方法の一例では、局所領域のパラメータは学習によって各サンプル画像内のあらゆる局所領域が評価され、決定されている。本実施形態ではこの学習の局所領域の評価において、上記同時読み出しの条件を加え決定するようにしている。具体的には、各サンプル画像内で従来評価していた局所領域群から幅と高さが条件式（１０）、（１１）に合致するものだけを取り出す。そして、学習は取り出された局所領域群を使って評価、決定する。
【００６５】
以上学習の一例を説明したが、本実施形態の構成は、条件式（１０）、（１１）の両方または片方の条件が成り立つように学習に組み込むことが重要であって、学習自体の方法によって制約されるものではない。以上のような方法で学習された辞書データの局所領域の幅、高さは全て条件式（１０）、（１１）に合致するものとなる。この結果、メモリアクセス制御部114より常に同時読み出しができるようになる。
【００６６】
上記のように、本実施形態の構成では、累積画像情報を排他的に複数のメモリに格納し、当該複数のメモリから並列的に複数の累積画像情報を読み出して局所領域の特徴量を算出して、パターン識別を行う。このため、メモリの容量を増大させずに累積画像情報を高速に読み出すことが可能となる。
【００６７】
また、本実施形態では、２次元配列に格納された複数のデータ要素からなる入力情報（画像情報）について、互いに隣接する位置に存在するデータ要素に対応する累積情報値を、それぞれ異なるメモリに書き込むようにしている。このため、縦横の長さがそれぞれ１画素の長さの奇数倍である限り、任意の大きさの局所領域についてパターン識別を行うことが可能である。
【００６８】
また、所定のパターンが含まれることが予め判明している画像情報と、所定のパターンが含まれないことが予め判明している画像情報とを用いて、辞書データを更新することで、パラメータを学習することが可能である。
【００６９】
以上、メモリへの分配規則、同時読み出しの条件を定義し、学習時にその条件を加えることで、総メモリサイズを増やさずに、局所領域の頂点位置の累積情報を複数のメモリから常に同時に読み出すことができるようになる。
【００７０】
＜＜実施形態２＞＞
実施形態１ではメモリへの分配規則、同時読み出しの条件を定義し、学習時にその条件を満たすようにしたが、これに限るわけではない。実施形態２ではメモリへの分配規則、同時読み出しの条件に合致するようにパラメータを変換する方法について説明する。実施形態２に係る構成は、実施形態１に係る構成と共通する部分があるため相違点のみ説明する。
【００７１】
実施形態２に係るパターン識別装置の構成を図１０に示す。構成上の相違点はパラメータ変換部1001が識別処理制御部119とメモリアクセス制御部114の間に追加されていることである。
【００７２】
パラメータ変換部1001は識別処理制御部119から指示される局所領域の４頂点分のメモリ読み出しを条件式（１０）、（１１）に合致するようにパラメータを変換する。本実施形態における計算処理を図１１のフローチャートに示す。実施形態１では識別処理制御部119で局所領域の４頂点分のメモリ番号とアドレスを算出していたが、実施形態２では識別処理制御部119は局所領域を左上座標と幅、高さで指定する。
【００７３】
まず、S1101でパラメータ変換部1001は識別処理制御部119から指示される局所領域の左上座標と幅、高さを取得する。
【００７４】
次に、S1102で局所領域の幅が条件式（１０）と合致しているかどうかを判定する。そして、合致している場合（S1102でYES）はS1104に移り、合致しない場合（S1102でNO）はS1103に移る。
【００７５】
S1103では、局所領域幅計算を行い条件式（１０）に合致させるための計算を行う。ここで指示される局所領域の幅をla_w、条件式（１０）に合致させた後の局所領域の幅をla_widthとすると次のように表される。
la_width = la_w - 1                                      (12)
S1103の処理を終えると、S1104へ進む。
【００７６】
S1104では、局所領域の高さが条件式（１１）と合致しているかどうかを判定する。そして、合致している場合はS1106に移り、合致しない場合はS1105に移る。
【００７７】
S1105では、局所領域高さ計算を行い条件式（１１）に合致させるための計算を行う。ここで指示される局所領域の高さをla_h、条件式（１１）に合致させた後の局所領域の高さをla_heightとすると次のように表される。
la_height = la_h - 1                                   (13)
S1105の処理を終えると、S1106へ進む。
【００７８】
S1106では、メモリアクセス制御部114によって読み出す４頂点のメモリ番号とアドレスを算出する。算出は左上座標(x0,y0)と幅、高さより４頂点の座標を求め、式（４）から式（９）によりメモリ番号、アドレスを算出する。
【００７９】
上記のように、本実施形態では、局所領域の形状を示すパラメータ情報を予め定められたメモリへの分配に係る規則に基づいて変換する。そして、累積画像情報の読み出しの際は、変換されたパラメータ情報に基づいて、累積情報値を読み出すメモリ（記憶手段）及びメモリアドレスを決定する。このため、本実施形態の構成によれば、パラメータ情報をメモリへの分配の規則に基づいて自動的に変換して同時読み出しを実行することが可能となる。
【００８０】
以上、パラメータ変換部1001の処理によって、局所領域の幅、高さは条件式（１０）、（１１）に合致するものとなる。この結果、メモリアクセス制御部114より常に同時読み出しができるようになる。
【００８１】
なお、実施形態２では識別処理中にパラメータ変換部1001で変換を行った例を説明したが、同様の変換処理を予め辞書データに対して行っておき、変換済みの辞書データを使ってパターン識別処理を行ってもよい。この場合、実施形態１の図１の構成となる。また、実施形態２では他に変換式（１２）、（１３）の一方を成り立たせるようにして、一部だけ同時読み出しを行っても構わない。
【００８２】
また、変換式（１２）、（１３）は近傍座標にずらすための一例であり、辞書データの局所領域の幅、高さに+１する計算であっても構わない。重要なのは条件式（１０）、（１１）に合致するような局所領域の形状に変換することである。
【００８３】
また、実施形態２では元々の辞書データのパラメータから、読み出し座標位置をずらすことになるので局所領域の形状の変換前と変換後の総和値に差が出てしまう。この対処方法として、局所領域の形状の変換前と変換後の面積比を変換後の総和値S2dに乗じてS2d'として以下のような式(14)で総和値を補間してもよい。
S2d'=(la_width×la_height) ／ (la_w×la_H)×S2d                         (14)
【００８４】
＜＜実施形態３＞＞
実施形態１、２では累積画像情報と呼ぶ２次元配列の情報での例を説明したが、実施形態３では同様の手法を１次元の情報に適用する方法を説明する。実施形態３では１次元配列のデータを入力とし、その入力データを一次元入力情報と呼ぶ。また、一次元入力情報を累積した情報を一次元累積情報と呼ぶ。
【００８５】
実施形態３での一次元配列の累積情報は図１２に示すようになる。図１２ではデータ1201を開始点として、ｘ方向にデータの値を累積させたものを一次元累積情報1200としている。データ中の括弧内の数値はｘ方向の座標を示す。
【００８６】
実施形態３のパターン識別装置の構成は実施形態１とほぼ同じであり、実施形態１との相違点はメモリ数が２つであることである。また、処理内容は一部実施形態１との相違があり、その相違点はメモリへの分配方法、同時読み出しの条件である。ここではその相違点について説明する。
【００８７】
（メモリへの分配）
まず、一次元累積情報のメモリへの分配方法について説明する。一次元累積情報の座標(x)の値をC(x)で表す。そして、ｘ方向の分配数をPとする。Pは２以上の整数であり、分配するメモリの総数はＰ個とし、メモリはMpで表す（記憶手段Ｍp）。pはメモリ番号で、pはｘ方向のメモリ番号値を示す。そして、C(x)の格納先を式（１５）のように表す。
Mp[address] = C(x)                                     (15)
座標(x)の画素値を格納するメモリ番号pは次式（１６）で表される。
p = x % P                                            (16)
ここで、% は剰余演算を表す。
【００８８】
メモリMpの各座標（x'）は式（１７）で表される。
x' = x ／ P                                           (17)
なお、x'を算出する際の除算（／）においては、小数点以下を切り捨てる。
【００８９】
このとき、格納先のメモリMpへのaddressは次式で表される。
address = x'                                          (18)
以上が一次元累積情報を所定の規則に従ってメモリへ分配するための式である。
【００９０】
実施形態３では図１２のようにP=2で、メモリ(M0(1211))とメモリ(M1(1212))に格納する。以上を踏まえて各座標の一次元累積情報1200を分配する。例えばC(3)の格納先のメモリは式(16)より、メモリ(M1)となる。そして、格納先のアドレスは式(17)より、x'=1、式(18)より、address=1となる。この結果、式(15)はM1[1]=C(3)であらわされ、C(3)の値はメモリ(M1)のaddress=1に格納することになる。これらの計算によって一次元累積情報1200は図１２のメモリ1211から1212に分配されて格納される。
【００９１】
（累積画像の読み出し）
次に、同時読み出しの条件について説明する。一次元累積情報の実施形態１で説明した局所領域に相当するものは直線の区分1220（以下、一次元累積情報では局所区分（local piecewise）と呼ぶ）となる。ここで、局所区分1220の両端を示す２点の座標を(x0),(x1)とする。
【００９２】
A,Bをそれぞれ、式（１９）で示される位置の累積情報値であるとする。
A:(x0-1)
B:(x1)                                                          (19)
このとき、一次元入力情報の局所区分1220内要素の総和値S1dは、式（２０）により計算することができる。
Sld=B-A                                                                    (20)
このときこの局所区分の長さをla_lengthと定義すると、本実施形態の分配規則に応じて導出される条件式は式（２１）のように示される。
la_length != P * n                                   (21)
ここで nは１以上の整数である。また、条件式（21）で使われている!=は否定を表す。つまりla_lengthはPの倍数以外の値であることを示す。
以上の条件式（21）を満たすことで読み出すメモリを排他関係にすることができ、局所区分の両端2点の値を同時に読み出すことができるようになる。
【００９３】
以上、メモリへの分配規則、同時読み出しの条件を定義し、学習時にその条件を加えることで、１次元の情報についても、総メモリサイズを増やさずに、局所区分の両端位置の累積情報を複数のメモリから常に同時に読み出すことができるようになる。
【００９４】
＜＜実施形態４＞＞
実施形態４では上記手法を３次元の情報に適用した例で説明する。実施形態４では３次元配列のデータを入力とし、その入力データを三次元入力情報と呼ぶ。三次元入力情報とは例えば動画情報であって、二次元画像に時間軸の一次元が加わり三次元入力情報となる。また、三次元入力情報を累積した情報を三次元累積情報と呼ぶ。
【００９５】
実施形態４での三次元配列の累積情報は図１３に示すようになる。図１３では三次元入力情報1300の原点Oを開始点として、ｘ方向、ｙ方向、ｔ方向に値を累積させたものを三次元累積情報1310としている。例えば点1302の座標(x,y,t)の三次元累積情報1310での値は原点Oと点1302を対角とする直方体1301に含まれるデータの合計値となる。本実施形態では直方体を動画情報で考え、ｘ方向を幅、ｙ方向を高さ、ｔ方向を時間で定義する。ここでｔ方向は時間軸で定義したが、もし立体空間であればｚ方向として奥行きと定義してもよい。
【００９６】
実施形態４のパターン識別装置の構成は実施形態１とほぼ同じで、実施形態４との相違点はメモリ数のみで、メモリを８つ使用する。また、処理内容に実施形態１との相違点があり、この相違点はメモリへの分配方法、同時読み出しの条件である。ここではその相違点について説明する。
【００９７】
（メモリへの分配）
まず、三次元累積情報のメモリへの分配方法について説明する。三次元累積情報の座標(ｘ,ｙ,ｔ)の値をC(x,y,t)で表す。そして、ｘ方向の分配数をP、ｙ方向の分配数をQ、ｔ方向の分配数をRとする。P,Q,RはP=1かつQ=1かつR=1を除く１以上の整数であり（(Ｐ,Ｑ,Ｒ)≠(１,１,１)）、分配するメモリの総数はＰ×Ｑ×Ｒ個とし、メモリはMpqrで表す（記憶手段Ｍpqr）。p,q,rはメモリ番号で、pはｘ方向のメモリ番号値、qはｙ方向のメモリ番号値、rはｔ方向のメモリ番号値を示す。
そして、C(x,y,t)の格納先は式（２２）のように表される。
Mpqr[address] = C(x,y,t)                               (22)
そして、座標(x,y,t)の画素値を格納するメモリ番号p,q,rは次式（２３）〜（２５）で表される。
p = ｘ％Ｐ                                            (23)
q = ｙ％Ｑ                                            (24)
r = ｔ％Ｒ                                            (25)
ただし、% は剰余演算を表す。
【００９８】
そして、メモリMpqrの各座標（x', y', t'）は式（２６）〜（２８）で表される。
x' = x ／ P                                           (26)
y' = y ／ Q                                           (27)
t' = t ／ R                                           (28)
なお、x', y', t'を算出する際の除算（／）においては、小数点以下を切り捨てる。
【００９９】
また、メモリMpqrに格納する三次元累積情報の幅をm_width、高さをm_height とする。このとき、m_width、m_heightは、分配元の三次元累積情報の幅width、高さheightとP,Q,Rの値から、次式（２９）（３０）に基づいて算出することができる。
m_width = width ／ P                                   (29)
m_height = height ／ Q                                   (30)
なお、m_width, m_heightを算出する際の除算（／）においては、小数点以下を切り上げる。
【０１００】
格納先のメモリMpqrへのaddressは次式で表される。
address = (m_width * m_height) * t' + m_width * y' + x'        (31)
以上が三次元累積情報を所定の規則に従ってメモリへ分配するための式である。実施形態４ではP=2,Q=2,R=2で、各座標の三次元累積情報1310をメモリ(M000)からメモリ（M111）に分配して格納する。
【０１０１】
（累積画像の読み出し）
次に、同時読み出しの条件について説明する。三次元累積情報における実施形態１で説明した局所領域に相当するものは直方体の空間1312（以下、三次元累積情報では局所空間(local space)と呼ぶ）となる。ここで、局所空間1312の対角を示す２点の座標を(x0,y0,t0),(x1,y1,t1)とする。A,B,C,D,E,F,G,Hをそれぞれ、次式（３２）で示される位置の累積情報値であるとする。
A:(x0-1,y0-1,t0-1),
B:(x1,y0-1,t0-1),
C:(x0-1,y1,t0-1),
D:(x1,y1,t0-1),
E:(x0-1,y0-1,t1),
F:(x1,y0-1,t1),
G:(x0-1,y1,t1),
H:(x1,y1,t1)                              (32)
このとき、三次元入力情報の局所空間1312内要素の総和値S3dは、次式（３３）で計算することができる。
S3d=H-D-F+B-(G-C-E+A)                                           (33)
このときこの局所空間の幅(ｘ方向)をla_width, 高さ(ｙ方向)をla_height、時間（ｔ方向）をla_timeと定義する。この場合、本実施形態の分配規則に応じて導出される条件式は次式（３４）〜（３６）で示される。
la_width != P * l                                   (34) 
la_height != Q * n                                   (35) 
la_time != R * m                                   (36)
ただし、l, m, nは各々１以上の整数である。また、条件式（34）から(36)で使われている!=は否定を表す。つまりla_widthはPの倍数以外の値であること、la_heightはQの倍数以外の値であること，la_timeはRの倍数以外の値であることを示す。
【０１０２】
以上の条件式（34）から(36)を全て満たすことで読み出すメモリを排他関係にすることができ、局所空間の８頂点の値を同時に読み出すことができるようになる。また、条件式（34）から(36)のいずれか１つ、または２つを満たすことができれば局所空間の８頂点の値を部分的に同時に読み出すこともできる。
【０１０３】
以上、メモリへの分配規則、同時読み出しの条件を定義し、学習時にその条件を加えることで、３次元の情報についても、総メモリサイズを増やさずに、局所空間の頂点位置の累積情報を複数のメモリから常に同時に読み出すことができるようになる。
【０１０４】
＜＜その他の実施形態＞＞
以上の実施形態では一次元から三次元について説明した。さらに、三次元を超える多次元入力情報に対する累積情報であっても、超直方体について同様の手法を適用可能であることは明らかである。
【０１０５】
また、以上の実施形態ではパターン識別処理に弱判別器を使った例で説明したが、これに限らない。実際、パターン識別処理には様々なものが提案されており、実装も多岐にわたっている。これらパターン識別処理において累積情報を使用し特徴量を算出するものは、いずれも同様の手法を適用できることは明らかである。
【０１０６】
以上の実施形態では所定の規則で分配する方法として元の累積情報において上下左右に隣接するデータを異なるメモリに分配する方法を説明したが、これに限らない。例えば近傍の累積情報を局所的にまとめて異なるメモリに分配しても構わない。図１４にその例を示す。1401は分配前の積分画像である。積分画像1401に振ってあるＡ，Ｂ，Ｃ，Ｄは分配先のメモリの種類を示す。ＡはＭ００（1420）、ＢはＭ１０（1421）、ＣはＭ０１（1422）、ＤはＭ１１（1423）に分配する。そして、積分画像1401から局所領域1402の総和を求めるために1410、1411、1412、1413の画素を読み出す。このとき読み出し先のメモリはＭ００からＭ１１にすべて分かれていることがわかる。以上のように近傍の累積情報をメモリに分配しても同様の効果が得られることは明らかである。
【０１０７】
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【０１０８】
以上のように、上記構成においては、インテグラルイメージを複数のメモリに所定の規則で保存し、総和値算出のために必要な複数の値の読み出し先メモリが排他関係となるように局所領域のパラメータを予め前記規則に応じて学習しておく。これにより、総和値算出に必要な複数の読み出しを同時に行うことができるようになる。すなわち、メモリのポート数、総メモリサイズを増やさずに、局所領域の各頂点の位置の累積情報を複数のメモリから同時に読み出すことが可能になる。
【図１】
0005759126.tif 000003
【図２】
0005759126.tif 000004
【図３】
0005759126.tif 000005
【図４】
0005759126.tif 000006
【図５】
0005759126.tif 000007
【図６】
0005759126.tif 000008
【図８】
0005759126.tif 000009
【図９】
0005759126.tif 000010
【図１０】
0005759126.tif 000011
【図１１】
0005759126.tif 000012
【図１２】
0005759126.tif 000013
【図１４】
0005759126.tif 000014
【図７】
0005759126.tif 000015
【図１３】
0005759126.tif 000016