(57)【特許請求の範囲】
【請求項１】
ある領域に対応する入力データから該領域の各位置に対応する累積情報を生成する生成手段と、
前記累積情報を保持する複数の記憶手段と、
前記累積情報を対応する位置に関する所定の規則に従って前記複数の記憶手段のいずれかに書き込む書き込み手段と、
前記複数の記憶手段から前記累積情報を並列に読み出す並列読み出し手段と、
前記並列に読み出された累積情報を用いて前記入力データの局所領域の特徴量を算出する特徴量算出手段と、
複数の前記特徴量を用いて前記入力データ内の所定のパターンを識別する識別手段とを備え、
前記入力データに対応する領域の少なくとも１つの次元について、割り当てられた前記記憶手段の個数と前記累積情報の読み出し間隔とが互いに素の関係であることを特徴とするパターン識別装置。
【請求項２】
前記局所領域の特徴量を算出するためのパラメータは、前記並列読み出し手段にて前記累積情報を並列に読み出せるように学習されていることを特徴とする請求項１に記載のパターン識別装置。
【請求項３】
前記書き込み手段は、前記累積情報の対応する位置の座標と各次元に割り当てられた記憶手段の個数とに基づいて書き込むべき記憶手段を決定することを特徴とする請求項１に記載のパターン識別装置。
【請求項４】
前記入力データは２次元のデータであり、累積情報は２次元配列から作られたものであって、前記書き込み手段はＰ1×Ｐ2個の前記記憶手段に前記累積情報を割り当てることを特徴とする請求項１乃至３の何れか１項に記載のパターン識別装置。
【請求項５】
前記Ｐ1を素数、前記Ｐ2を１とすることを特徴とする請求項４に記載のパターン識別装置。
【請求項６】
前記Ｐ2に対応する次元の位置に応じて、前記Ｐ1に対応する次元の位相を変化させることで前記累積情報の前記複数の記憶手段への割り当てを変化させることを特徴とする請求項５に記載のパターン識別装置。
【請求項７】
前記入力データは１次元のデータであり、前記累積情報は１次元配列から作られたものであって、前記書き込み手段はＰ1個の前記記憶手段に前記累積情報を割り当てることを特徴とする請求項１に記載のパターン識別装置。
【請求項８】
前記入力データは３次元のデータであり、前記累積情報は３次元配列から作られたものであって、前記書き込み手段はＰ1×Ｐ2×Ｐ3個の前記記憶手段に前記累積情報を割り当てることを特徴とする請求項１に記載のパターン識別装置。
【請求項９】
ある領域に対応する入力データから該領域の各位置に対応する累積情報を生成する生成工程と、
前記累積情報を対応する位置に関する所定の規則に従って複数の記憶手段のいずれかに書き込む書き込み工程と、
前記複数の記憶手段から前記累積情報を並列に読み出す並列読み出し工程と、
前記並列に読み出された累積情報を用いて前記入力データの局所領域の特徴量を算出する特徴量算出工程と、
複数の前記特徴量を用いて前記入力データ内の所定のパターンを識別する識別工程とを備え、
前記入力データに対応する領域の少なくとも１つの次元について、割り当てられた前記記憶手段の個数と前記累積情報の読み出し間隔とが互いに素の関係であることを特徴とするパターン識別方法。
【請求項１０】
請求項９に記載のパターン識別方法の各工程をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、累積情報を用いた画像認識、或いは情報分析などを行うパターン識別装置、パターン識別方法及びプログラムに関する。
【背景技術】
【０００２】
情報処理分野においては、多次元配列情報を頻繁に取り扱う。その中でも、画像処理、画像認識や画像合成等に関わる一部処理や統計処理等では、特定領域範囲内における要素の総和値を求めて使用することが多い。コンピュータ・グラフィックスの分野では、例えば、矩形のsummed-area tableと呼ばれる、元の入力画像情報に対する累積情報の概念が提案されている（例えば、非特許文献１参照）。この非特許文献１では、summed-area tableを入力画像と同サイズ（同要素数）の２次元配列とし、入力画像の座標（ｘ，ｙ）の画素値をＩ（ｘ，ｙ）と定義する。そして、summed-area tableの同位置（ｘ，ｙ）の成分Ｃ（ｘ，ｙ）を以下の式（１）により定義する。
【０００３】
【数１】
0005777458.tif 000002
【０００４】
すなわち、図７（ａ）の元の入力画像において原点位置（０，０）と位置（ｘ，ｙ）との画素を対角とする矩形内の画素の総和値が、図７（ｂ）に示すsummed-area tableの位置（ｘ，ｙ）の値Ｃ（ｘ，ｙ）となる。なお、非特許文献１のオリジナルのsummed-area tableは、原点位置を画像左下として説明しているが、以下の説明では後述の説明と整合させるため左上原点とする。
【０００５】
この定義によれば、入力画像上で水平または垂直に置かれた任意の矩形領域内のＩ（ｘ，ｙ）の和を、summed-area table上の４点を参照するのみで、求めることができる。例えば図８に示すように（ｘ0，ｙ0）と（ｘ1，ｙ1）を対角とする矩形領域内の画素値の総和Ｃ（ｘ0，ｙ0；ｘ1，ｙ1）を求めるには、以下の式（２）を用いる。
【０００６】
【数２】
0005777458.tif 000003
【０００７】
これにより、画像上の任意の矩形領域内の値の総和を高速に求めることができる。
【０００８】
また、特許文献１には、累積情報の実装方法の１つが開示されている。
【０００９】
画像認識の分野では、上記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.
【非特許文献３】S. Yan, S. Shan, X. Chen, and W. Gao. Locally assembled binary(lab) feature with feature-centric cascade for fast and accurate facedetection. 26th IEEE Conference on Computer Vision and Pattern Recognition, CVPR, 2008.
【発明の概要】
【発明が解決しようとする課題】
【００１５】
非特許文献３には、認識精度向上のため特徴量算出で参照する領域を図１３のような形状で読み出すことが提案されている。図１３に示す参照領域は、幅及び高さが同じブロック１５５０〜１５５８をタイル状に並べたものであり、各ブロック内の画素の総和から特徴量が算出される。これは積分画像を使って各ブロックの頂点１５０１〜１５１６の１６点を読み出して総和を算出すればよい。しかし、従来のような局所領域の４頂点の読み出しに比べ４倍ものメモリ読み出しが必要となる。また、高速化のために局所領域の形状に制約を設けると認識精度に影響を与える場合がある。認識精度向上のためにはできるだけ制約を少なくすることも必要である。
【００１６】
本発明は前述の問題点に鑑み、積分画像のメモリアクセスのボトルネックを解消し、少ない制約で高速化できるようにすることを目的としている。
【課題を解決するための手段】
【００１７】
本発明のパターン識別装置は、ある領域に対応する入力データから該領域の各位置に対応する累積情報を生成する生成手段と、前記累積情報を保持する複数の記憶手段と、前記累積情報を対応する位置に関する所定の規則に従って前記複数の記憶手段のいずれかに書き込む書き込み手段と、前記複数の記憶手段から前記累積情報を並列に読み出す並列読み出し手段と、前記並列に読み出された累積情報を用いて前記入力データの局所領域の特徴量を算出する特徴量算出手段と、複数の前記特徴量を用いて前記入力データ内の所定のパターンを識別する識別手段とを備え、前記入力データに対応する領域の少なくとも１つの次元について、割り当てられた前記記憶手段の個数と前記累積情報の読み出し間隔とが互いに素の関係であることを特徴とする。
【発明の効果】
【００１８】
本発明によれば、次元毎に割り当てられた記憶手段の数と累積情報の読み出しの関係を互いに素の関係することで積分画像のメモリアクセスのボトルネックを解消し、少ない制約で高速化できる。
【図面の簡単な説明】
【００１９】
【図１】実施形態のパターン識別装置の構成例を示すブロック図である。
【図２】第１の実施形態における全体処理の手順の一例を示すフローチャートである。
【図３】第１の実施形態におけるパターン識別処理の手順の一例を示すフローチャートである。
【図４】累積画像情報を示す図である。
【図５】ｘ軸、ｙ軸の各次元に素数個のメモリ５個に割り当てた例を示す図である。
【図６】第２の実施形態に係る並列読み出しを説明する図である。
【図７】入力画像情報に対する累積画像情報の生成方法を説明する図である。
【図８】総和算出のため累積画像情報から読み出す座標を説明する図である。
【図９】処理ウィンドウを説明する図である。
【図１０】第３の実施形態における１次元配列の累積情報を示す図である。
【図１１】第４の実施形態における３次元配列の累積情報を示す図である。
【図１２】その他の実施形態に係る近傍の累積情報のメモリへの割り当てを説明する図である。
【図１３】特徴量算出のための３×３ブロックの読み出しを説明する図である。
【図１４】Ｐ1×Ｐ2個のメモリ群の構成を説明する図である。
【図１５】メモリ割り当て数とストライドとの関係を説明する図である。
【発明を実施するための形態】
【００２０】
（第１の実施形態）
以下、本発明を実施するための第１の実施形態について、図面を用いて説明する。なお、本実施形態においては、Summed-area tableあるいはIntegral Imageのような、２次元配列の情報を累積画像情報（または積分画像）と呼ぶ。また、二次元配列の画像情報（ＲＧＢ画像やGrayscale画像のような画像情報だけでなく一次微分フィルタをかけた画像など、加工された画像情報も含む）を入力画像情報と呼ぶ。本実施形態ではパターン識別装置の構成、累積画像情報のメモリへの割り当て方法及び並列読み出しについて説明し、さらに学習について説明する。
【００２１】
図１は、本実施形態のパターン識別装置の構成例を示すブロック図である。
図１において、１０１はＣＰＵであって、バス１０５を介して接続される各部を制御する。１０２は入力画像情報を入力するデータ入力部であって、処理対象となる入力画像情報を装置内に取り込む。データ入力部１０２は、例えばＣＣＤなどの画像センサによって構成されてもよいし、ネットワーク等所定の通信経路を持って外部装置から処理したいデータを受信するＩ／Ｆ装置であってもよい。
【００２２】
１０４はバス１０５に接続される外部メモリであって、ＲＯＭやＲＡＭあるいはＨＤＤ等のストレージ装置で構成されている。外部メモリ１０４は、ＣＰＵ１０１が動作するためのプログラムコードを記憶したり、各種処理を行う上での作業領域として用いられたりする。また、必要に応じて入力画像情報やパターン識別に使用する各種情報を保持するための領域としても用いられる。１０３はＤＭＡコントローラ（以下、ＤＭＡＣ）であって、ＣＰＵ１０１が設定して動作指令することにより、データ入力部１０２、外部メモリ１０４、パターン識別部１０７に所定サイズのデータ転送を、自立的に連続に行うことが可能である。ＤＭＡＣ１０３は指令された転送動作が完了すると、バス１０５を介して割り込み信号をＣＰＵ１０１に通知する。
【００２３】
１０７はパターン識別部であって、ＤＭＡＣ１０３からバス１０５を介して送られてくる入力画像情報をパターン識別処理する。パターン識別処理では、入力画像情報に所定の検出パターン（例えば顔や人体の立像など）が検出されるか否かを判定し、検出位置、検出形状、尤度などの検出情報を出力する。検出情報はバス１０５を介して外部メモリ１０４に書き込まれる。
【００２４】
パターン識別部１０７は、バスインタフェース（バスＩ／Ｆ）１１１、累積画像情報生成部１１２、割り当て書き込み処理部１１３、メモリアクセス制御部１１４、及びメモリＭ００〜Ｍ（Ｐ2−１）（Ｐ1−１）を有する。さらに、識別処理制御部１１９、辞書記憶部１２０、特徴量算出部１２１、判定処理部１２２、及び処理ウィンドウ管理部１２３を有する。
【００２５】
本実施形態のメモリＭ００〜Ｍ（Ｐ2−１）（Ｐ1−１）にはシングルポート型のメモリが使用され、図１４のメモリ群１６０１に示すように二次元状に割り合てられたＰ1×Ｐ2個のメモリとして使用される。Ｐ1は横方向に割り当てられたメモリの数でＰ2は縦方向に割り当てられたメモリの数を表す。また、Ｐ1、Ｐ2はそれぞれ１または素数である。本実施形態の説明上ではＰ1＝５、Ｐ2＝５とする。図１４の１６０２は、アドレス、データ等の一般的なシングルポート型のメモリインタフェースである。メモリインタフェースはＰ1×Ｐ2個それぞれのメモリに備えられている。メモリの入出力制御はメモリアクセス制御部１１４にてこれらメモリインタフェースを介して制御される。
【００２６】
次に、図１のパターン識別装置の詳細と全体の処理の流れを、図２のフローチャートを使って説明する。
本実施形態のパターン識別装置は、ユーザの操作や不図示の外部装置からの処理開始トリガによって、まずデータ入力処理ステップＳ２０１を実行する。ステップＳ２０１では最初にＣＰＵ１０１の指示によってデータ入力部１０２より入力画像情報を受信し、バス１０５を介して外部メモリ１０４に蓄積する。そして外部メモリ１０４に蓄積された入力画像情報をＤＭＡＣ１０３によってパターン識別部１０７に転送する。パターン識別部１０７は、バス１０５を介して転送されてくる入力画像情報をバスインタフェース１１１で受け、累積画像情報生成部１１２に転送する。本実施形態では、入力画像情報は画像左上の画素から画素単位でラスタ順に入力されるものとする。
【００２７】
次に、ステップＳ２０２では、累積画像情報生成処理を行う。累積画像情報生成部１１２は、ラスタ順で送られる入力画像情報を累積処理し、累積画像情報を生成する。累積画像情報は入力画像情報の画像左上の画素を原点として画素値を累積し、累積結果を順次、割り当て書き込み処理部１１３に転送する。累積処理の詳細については従来技術の通りであり、説明は省略する。
【００２８】
次に、ステップＳ２０３では累積画像情報の割り当て書き込み処理を行う。割り当て書き込み処理部１１３は、まずメモリに対して書き込みを行ってよいか処理ウィンドウ管理部１２３に問い合わせる。処理ウィンドウ管理部１２３は割り当て書き込み処理部１１３からのメモリの書き込みと識別処理制御部１１９からの読み出しの排他制御を管理している。
【００２９】
ここで処理ウィンドウとは、パターン識別処理が処理を行う単位である。図９は処理ウィンドウを説明する図である。９００は入力画像情報であり、９０１は１つの処理ウィンドウである。処理ウィンドウ９０１の画像領域がパターン識別処理を行う１単位である。そして、処理ウィンドウ９０１に対してパターン識別処理を行い、この処理ウィンドウ９０１に所定の検出パターンが存在するかどうかを判定する。処理ウィンドウは入力画像情報９００の左上の処理ウィンドウ９０１から順に右方向に移動し、それぞれの位置でパターン識別処理をする。右端に達したら左端にもどって下方向に移動する。以上の移動を繰り返し右下位置まで順に移動させる。
【００３０】
割り当て書き込み処理部１１３は、処理ウィンドウ管理部１２３から所定個数の書き込み許可を受ける。そして、割り当て書き込み処理部１１３は累積画像情報の画素単位で書き込み先のメモリＭ００〜Ｍ（Ｐ2−１）（Ｐ1−１）とアドレスを決定し、メモリアクセス制御部１１４に書き込みを指示する。メモリとアドレスの決定方法の詳細は累積情報のメモリへの割り当て方法として後述する。
【００３１】
そして、メモリアクセス制御部１１４は、指示されたメモリとアドレスに従ってメモリＭ００〜Ｍ（Ｐ2−１）（Ｐ1−１）に累積画像情報を格納する。割り当て書き込み処理部１１３は、所定個数の書き込みが終了すると処理ウィンドウ管理部１２３に書き込み終了を通知する。
【００３２】
次に、ステップＳ２０４でパターン識別処理を行う。パターン識別処理は従来技術で説明したような複数の弱判別器で判定を行う。弱判別器を使った処理方法はいくつかあるが、ここではある処理ウィンドウにおいて局所領域の総和を算出し、その算出結果を用いて弱判別器で判定する処理を複数回繰り返す。以下、パターン識別処理の詳細を図３のフローチャートにて示す。
【００３３】
パターン識別処理では、まずステップＳ３０１で処理ウィンドウを要求する。識別処理制御部１１９は、処理ウィンドウ管理部１２３に対して処理対象となる処理ウィンドウを要求する。処理ウィンドウ分のデータがメモリＭ００〜Ｍ（Ｐ2−１）（Ｐ1−１）に準備できたら次のステップＳ３０２に移る。
【００３４】
次に、ステップＳ３０２では辞書データの読み込み処理を行う。識別処理制御部１１９は辞書記憶部１２０に格納されている辞書データをもとに識別処理を開始する。辞書データは予め学習によって得られたパラメータ群である。辞書データには累積画像情報から特徴量を算出する局所領域の位置や形状、判定処理の係数や閾値などのパラメータが格納されている。
【００３５】
次に、ステップＳ３０３では特徴量パラメータの送信処理を行う。識別処理制御部１１９は、辞書データのパラメータから図１３に示す参照領域の１６点分のメモリ番号とアドレスを算出し、メモリアクセス制御部１１４に累積画像情報の読み出しを指示する。また、特徴量算出部１２１、判定処理部１２２で使用するパラメータ（係数、閾値など）も辞書データから取り出して特徴量算出部１２１、判定処理部１２２に設定する。
【００３６】
次に、ステップＳ３０４では累積画像情報の読み出し処理を行う。メモリアクセス制御部１１４は指示されたメモリ番号とアドレスに対応するメモリからデータを読み出して、特徴量算出部１２１に送る。メモリアクセス制御部１１４は読み出しにおいてメモリ番号が排他関係にあれば並列読み出しを行う機能を備える。なお、並列読み出しの詳細は後述する。
【００３７】
次に、ステップＳ３０５では特徴量を算出する処理を行う。特徴量算出部１２１は読み出した１６点の値から各ブロックの総和値を算出し、ステップＳ３０３で設定されたパラメータを使用して特徴量を算出する。そして、特徴量の算出結果は判定処理部１２２に送られる。
【００３８】
次に、ステップＳ３０６では結果判定の処理を行う。判定処理部１２２は特徴量の算出結果とステップＳ３０３で設定されたパラメータとを使用して判定を行う。設定されるパラメータは例えば閾値であって特徴量の算出結果がその閾値よりも高ければTrue、閾値よりも低ければFalseという判定がなされる。True判定の場合、判定結果は識別処理制御部１１９に送られ、ステップＳ３０７に移る。一方、False判定の場合、所定の検出パターンではないという判定が確定（以下、False確定）し、ステップＳ３０８に移る。
【００３９】
次に、ステップＳ３０７では全局所領域の識別が終了したか否かをチェックする。識別処理制御部１１９は次に処理する局所領域が残っていればステップＳ３０２に戻る。そしてステップＳ３０２からステップＳ３０６の処理を全局所領域数分繰り返す。全局所領域にてTrue判定が得られたら、所定の検出パターンであることが確定（以下、True確定）し、ステップＳ３０８に移る。
【００４０】
次に、ステップＳ３０８では処理ウィンドウの終了通知を行う。識別処理制御部１１９は処理ウィンドウ管理部１２３に対して処理が終了したことを通知する。通知を受けた処理ウィンドウ管理部１２３は次の処理ウィンドウを準備する処理を開始する。True確定となった処理ウィンドウの情報は識別処理制御部１１９によってバスインタフェース１１１を介して外部メモリ１０４に書き出される。一方、False確定となった処理ウィンドウの情報は書き出さない。
【００４１】
次に、ステップＳ３０９では全処理ウィンドウの識別終了が完了したかどうか確認する。全処理ウィンドウの処理が終了していない場合はFalseに移り次の処理ウィンドウの処理を行う。一方、全処理ウィンドウの処理が終了した場合はTrueに移る。以上のパターン識別処理が入力画像情報の全処理ウィンドウに渡って処理が繰り返され、終了した後、図２のステップＳ２０５に移る。
【００４２】
次に、ステップＳ２０５では後処理を行う。識別処理制御部１１９は全処理ウィンドウのパターン識別処理が終了したことをＣＰＵ１０１に対して通知する。以上がパターン識別処理の全体の処理の流れである。
【００４３】
次に、累積画像情報のメモリへの割り当て方法と並列読み出し、そして学習について説明する。まず、累積画像情報を本実施形態における所定の規則に従ってメモリへ割り当てる方法について説明する。ここで、本実施形態における所定の規則とは隣接する画素を異なるメモリに割り当てる方法である。
【００４４】
図４は、累積画像情報４００を示す図である。ここでは累積画像情報４００の左上を原点とし、水平方向をｘ、垂直方向をｙとして各画素の座標を（ｘ，ｙ）で表す。なお、原点座標は（０，０）とする。また、累積画像情報４００の１つの箱が１画素を示す。図４の４１０から４１３は各メモリの配列を２次元的に表現したもので、それらの右隣に、物理的な格納イメージを示す。各メモリと２次元表現の画素データ中とに記載された数値は対応する累積画像情報４００の座標を示している。
【００４５】
次に、本実施形態における上記所定の規則について一般化したものを説明する。累積画像情報４００の座標（ｘ，ｙ）の画素値をＣ（ｘ，ｙ）で表す。メモリは図１４に示す構成でメモリＭ００〜Ｍ（Ｐ2−１）（Ｐ1−１）が割り当てられる。Ｐ1はｘ方向のメモリ数でＰ2はｙ方向のメモリ数である。そして、Ｐ1，Ｐ2は１または素数である。
【００４６】
また、各メモリはＭｐ2ｐ1で表す。ｐ1、ｐ2は０を起点とするメモリ番号でｐ1は水平方向のメモリ番号値、ｐ2は垂直方向のメモリ番号値を示す。そして、Ｃ（ｘ，ｙ）の格納先は以下の式（３）のように表す。
Ｍｐ2ｐ1［address］＝Ｃ（ｘ，ｙ）          ・・・（３）
【００４７】
また、座標（ｘ，ｙ）の画素値を格納するメモリ番号ｐ1、ｐ2は以下の式（４）及び式（５）で表される。
ｐ1＝ｘ％Ｐ1          ・・・（４）
ｐ2＝ｙ％Ｐ2          ・・・（５）
ここで、％は剰余（modulo arithmetic）を表す。
【００４８】
そして、メモリＭｐ2ｐ1上の座標（ｘ'，ｙ'）は、以下の式（６）及び式（７）で表される。
ｘ'＝ｘ／Ｐ1          ・・・（６）
ｙ'＝ｙ／Ｐ2          ・・・（７）
なお、ｘ'，ｙ'は小数点以下切り捨て
【００４９】
また、メモリＭｐ2ｐ1に格納する画像の幅をm＿widthとして定義すると、幅m＿widthは割り当てる前の累積画像情報の幅widthとＰ1の値とから以下の式（８）で表すことができる。
m＿width＝width／Ｐ1          ・・・（８）
ここで、m＿widthは切り上げ
【００５０】
格納先のメモリMp2p1のaddressは以下の式（９）で表される。
address＝m＿width＊ｙ'＋ｘ'          ・・・（９）
【００５１】
以上が累積画像情報を所定の規則に従ってメモリへ割り当てるために一般化した式である。
【００５２】
次に、具体的に本実施形態で説明したメモリＭ００〜Ｍ（Ｐ2−１）（Ｐ1−１）に割り当てる場合について図４を用いて説明する。図４では、ｘ方向の割り当て数を５（Ｐ1＝５）、ｙ方向の割り当て数を５（Ｐ2＝５）とした例を示している。また、メモリＭｐ2ｐ1に格納する画像の幅については、累積画像情報４００の画像の幅width＝２０、Ｐ1＝５より幅m＿width＝４となる。以上を踏まえて各座標の累積画像情報４００を割り当てる。
【００５３】
例えば、Ｃ（５，６）の格納先は式（４）、（５）より、ｐ1＝０、ｐ2＝１、式（６）、（７）より、ｘ'＝１、ｙ'＝１、式（９）より、address＝５となる。この結果、式（３）はＭ１０［５］＝Ｃ（５，６）で表され、Ｃ（５，６）の値はメモリＭ１０のaddress＝５に格納することになる。
【００５４】
以上が本実施形態における累積画像情報のメモリへの割り当て方法である。本実施形態では累積画像情報をラスタ順に入力することを説明したが、本実施形態では、式（３）から式（９）で示される関係で素数個のメモリに割り当てて格納することが重要であって、累積画像情報の入力順序の違いに制約されるものではない。
【００５５】
次に、割り当てて格納した累積画像情報から図１３に示す１６点の値を並列に読み出す方法について説明する。並列読み出しを行うためには、読み出すメモリを排他関係にしなければならない。ここで重要となるのが次元毎の読み出し点の間隔（以下、ストライドと呼ぶ）と各次元に割り当てられたメモリ個数とを互いに素の関係にすることである。本実施形態では各次元のメモリの個数を素数個にし、ストライドとの関係を互いに素にしているがその理由について図１５を用いて説明する。ここでは説明のため１次元配列の方向（ｘ軸）にだけ注目する。
【００５６】
まず、データを５個のメモリに割り当て、あるストライドで５個のデータを読み込むケースを考える。図１５の表１７０１〜１７０７には、ストライドを１から７に変化させた時の読み出し先メモリが示されている。各表で示されるメモリには同じデータが同じアドレスに格納されている。黒塗りされた部分が読み出し先のデータである。また、１行目の＃１から＃５がメモリ番号であり、２行目以降の数値がｘ座標値である。例えばｘ＝６のデータはメモリ番号＃２のアドレス＝１に格納される。
【００５７】
次に、ストライド＝４の表１７０４を代表に説明する。最初の読み出しデータはメモリ番号＃１のアドレス＝０（ｘ＝０）とすると、次の読み出しデータはｘ＋４＝４で、メモリ番号＃５のアドレス＝０である。そして次の読み出しデータはｘ＋８＝８でメモリ番号＃４のアドレス＝１となる。これを繰り返した結果分かることはストライド＝４で５点連続して読み出した場合、読み出し先のメモリがすべて異なるということである。これは先頭座標をどこにずらしても他の読み出し座標も同様にずれることから読み出し先のメモリはすべて異なる。これはメモリ数とストライドとが互いに素の関係にあると得られる性質である。
【００５８】
図１５の例では、互いに素の関係にないストライド＝５を除くストライドでも同様に読み出し先のメモリがすべて異なることが確認できる。これはストライドが８以上の場合でも成り立つ（但し、ストライドが５の倍数を除く）。以上のように読み出し先のメモリをすべて異ならせることがメモリ数とストライドとを互いに素の関係とした理由である。この性質は２次元配列に拡張した場合も同様の効果が得られる。以下、具体例について説明する。
【００５９】
図５は、ｘ軸、ｙ軸の各次元に素数個のメモリ５個に割り当てた例を示す図であり、これに対して図１３に示すような３×３ブロックの読み出しを行う。図５（ａ）には、ブロックの幅＝２、高さ＝２での３×３ブロック（５０１〜５０９）それぞれの総和を求める例を示す。読み出す点は１６点（網掛けの画素）で左上の座標（２，１）を起点に１６点の読み出しを行う。この読み出しでは縦横共にストライドは２で各次元方向のメモリ数５に対して互いに素の関係にある。
【００６０】
図５（ｂ）は、累積画像情報と各画素の割り当て先のメモリとの関係を示す図である。座標（０，０）の画素はメモリＭ００に割り当てられていることを示している。図５（ｂ）には、読み出す１６点の座標それぞれに割り当てられたメモリ（Ｍｐ2ｐ1）が記載されている。図５（ｂ）では１６点の読み出しすべてが異なるメモリを指していることがわかる。これは他のストライドでも同様でｘ方向、ｙ方向それぞれ５の倍数以外のストライドであれば起点がどの位置であっても１６点の読み出しをすべて異ならせることができる。
【００６１】
次に、並列読み出しするためのブロック読み出し条件を式で表す。ｘ方向のブロック数をＢ1、ｙ方向のブロック数をＢ2とし、Ｂ1×Ｂ2ブロックとする。そして各ブロックの形状は幅b＿width及び高さb＿heightと定義すると、条件式はそれぞれ以下の式（１０）及び式（１１）で表される。
b＿width≠Ｐ1＊ｎ          ・・・（１０）
b＿height≠Ｐ2＊ｍ          ・・・（１１）
Ｐ1、Ｐ2は素数。ｎ、ｍは１以上の整数
【００６２】
次に学習について説明する。これまで並列読み出しの条件について説明したが、ここではこの条件を満たすための学習方法について説明する。学習はパターン識別処理において画像中に含まれるものが検出パターンかどうか識別するための基準を決定する手法として広く使用されている。本実施形態では学習によって決定されたパラメータを辞書データと呼んでいる。
【００６３】
学習は所定の検出パターンを含むことがわかっている複数のサンプル画像と所定の検出パターンを含まないことがわかっている複数のサンプル画像との各々から所定のパラメータを導出し、記録しておくものである。この所定のパラメータの中には局所領域（本実施形態ではブロックを指す）の位置、大きさの導出が含まれている。
【００６４】
学習方法の一例では、局所領域のパラメータは学習によって各サンプル画像内のあらゆる局所領域が評価され、決定されている。本実施形態ではこの学習の局所領域の評価において、上記並列読み出しの条件を加えて決定するようにしている。具体的には各サンプル画像内で従来評価していた局所領域群から幅と高さが式（１０）、（１１）に合致するものだけを取り出す。そして、学習は取り出された局所領域群を使って評価及び決定を行う。
【００６５】
以上のように学習の一例を説明したが、本実施形態では式（１０）、（１１）が成り立つように学習に組み込むことが重要であって、学習自体の方法によって制約されるものではない。以上のような方法で学習された辞書データの局所領域の幅、高さは全て条件式（１０）、（１１）に合致するものとなる。この結果、メモリアクセス制御部１１４より常に並列読み出しができるようになる。
【００６６】
以上、累積画像情報を図１４のメモリ構成に画素単位で割り当て、読み出しの偏るケースを学習で制約することで図１３に示す画素を並列に読み出すことができるようになる。また、読み出しの偏るケースはブロックの形状（幅、高さ）制約で各次元に割り当てられたメモリ数の倍数を除くだけにできる。
【００６７】
（第２の実施形態）
第１の実施形態では累積画像情報をｘ方向、ｙ方向それぞれに素数個のメモリに割り当てる方法を示した。本実施形態では使用するメモリの個数を抑えるために累積画像情報のｘ方向は素数個のメモリにインタリーブし、かつｙ方向の位置に応じて位相を変化させて図１３の１６点を読み出す方法を説明する。本実施形態では位相を変化させる方法が図１３の１６点読み出しだけでなく基本となる矩形領域の４点読み出しに対しても有効であることを示す。また、本実施形態では第１の実施形態と説明が重なる部分があるため差分のみ説明する。
【００６８】
本実施形態のパターン識別装置の構成は、第１の実施形態と同様である。異なるのはメモリ構成のパラメータと割り当て書き込み処理部１１３の処理である。本実施形態のメモリ構成のパラメータはＰ1＝５、Ｐ2＝１とし、割り当て書き込み処理部１１３はｙ方向に応じて位相を変える処理を行う。
【００６９】
次に、図６を用いて位相を変えたメモリの割り当てとその効果を説明する。図６（ａ）〜図６（ｃ）は第１の実施形態の方法で割り当てた例であり、図６（ｄ）〜図６（ｆ）はｙ方向の位置に応じて位相を変えたメモリの割り当ての例である。
【００７０】
図６（ａ）は、第１の実施形態の方法で累積画像情報４００をＰ1＝５、Ｐ2＝１でメモリに割り当てた例を示している。画素６０１はＭ００に割り当てられ、画素６０２のＭ０４まで順に割り当てられる。そして次の画素６０３はＭ００に割り当てられ、これらの割り当てが右端まで繰り返される。そして、次の行の先頭画素６０４は１行目同様にＭ００に割り当てられる。
【００７１】
図６（ｄ）は、累積画像情報４００をＰ1＝５、Ｐ2＝１でｙ方向の位置に応じて位相を変えてメモリに割り当てた例を示している。１行目は図６（ａ）と同じであるが２行目の先頭画素６０５はメモリＭ０２に割り当てられており、図６（ａ）と違いｙ方向に１行進む毎に割り当て先のメモリが＋１ずつずれていることがわかる。本実施形態における位相の変化とはこのずれのことである。
【００７２】
次に、割り当て先のメモリＭ０ｐ1（ｐ2＝０）及びaddressの式については、位相の変化量はＳで表すと、座標（ｘ，ｙ）の画素値を格納するメモリ番号p1は以下の式（１２）で表される。
ｐ1＝（ｙ×Ｓ＋ｘ）％Ｐ1          ・・・（１２）
ここで、％は剰余（modulo arithmetic）を表す。
【００７３】
次に、累積画像情報の幅をwidthとすると、addressは以下の式（１３）で表される。
address＝（width／Ｐ1）＊ｙ＋ｘ／Ｐ1          ・・・（１３）
【００７４】
図６（ａ）及び図６（ｄ）の２パターンで１６点読み出しと４点読み出しとを考える。まずは１６点読み出しを図６（ｂ）及び図６（ｅ）に示す。１６点読み出しは、図６（ｂ）及び図６（ｅ）に示す例では、各行の４点が並列読み出しできることから４回に分けて１６点を読み出すことが可能である。これは第１の実施形態で説明したように各行でメモリ数とストライドが互いに素の関係にあることから実現できることである。
【００７５】
次に、４点読み出しを図６（ｃ）及び図６（ｆ）に示す。４点読み出しは、図６（ｃ）の例と図６（ｆ）の例とで状況が大きく変わる。図６（ｃ）では、矩形領域６１０の４頂点はｘ方向で並列読み出しできるが、ｙ方向では同じメモリに当たるので常に２回に分けたアクセスが必要になることがわかる。これはどのような位置、形状の矩形領域でも同様である。一方、図６（ｆ）では、位相を変えたことで矩形領域６１１の４頂点を並列読み出しできることがわかる。但し、対角が一致する条件が存在するため全てのケースで並列読み出しできるわけではない。
【００７６】
次に、並列読み出しするための条件を式で示す。矩形領域の幅をra＿width、高さra＿height、メモリ数Ｐ1、位相の変化量Ｓ（０＜Ｓ＜Ｐ1、図６（ｄ）の例はＳ＝１）とする。Ｐ1の倍数と矩形領域の対角の点が一致するケースを除くために、以下の式（１４）〜式（１７）が定義される。
ra＿width≠Ｐ1＊ｎ          ・・・（１４）
ra＿height≠Ｐ1＊ｍ          ・・・（１５）
ここで、Ｐ1は素数。ｎ、ｍは１以上の整数
（Ｓ×ra＿height＋ra＿width）％Ｐ1≠０          ・・・（１６）
（Ｓ×ra＿height−ra＿width）％Ｐ1≠０          ・・・（１７）
ここで、％は剰余（modulo arithmetic）を表す。
【００７７】
そして、これらの式（１４）〜式（１７）の４つの条件を満たすra＿width、ra＿heightの組み合わせを学習で使うことで並列読み出しが可能になる。
【００７８】
次に、学習に使える形状（ra＿width、ra＿heightの組み合わせ）の数とra＿width、ra＿height、及びＰ1の関係と、学習に使える形状とＳとの関係について具体例で説明する。ra＿width、ra＿heightの値域を１以上５以下とすると組み合わせは２５通りとなる。Ｐ1＝５、Ｓ＝１の場合、式（１４）〜式（１７）を満たす形状は７通りで全体の２５通りに対して２８％となる。他の構成としてメモリを増やしたＰ1＝７、Ｓ＝１の場合、式（１４）〜式（１７）を満たす形状は１６通りで全体の２５通りに対して６４％となり制約が緩和されていることがわかる。これはra＿width、ra＿heightの値域に合わせて最適なＰ1を決めれば形状制約を緩和できることがわかる。
【００７９】
次に、学習に使える形状とＳの関係を説明する。学習に使える形状はＳの値によって変化する。Ｐ1＝５、Ｓ＝１の場合、１×１（ra＿width×ra＿height）の矩形領域の４点は並列に読み出せないがＳ＝２では並列に読み出せる。一方、Ｐ1＝５、Ｓ＝２の場合、３×４の矩形領域の４点は並列に読み出せないがＳ＝１では並列に読み出せる。学習に使いたい形状があればそれを考慮して最適なＳを決めることも可能であることがわかる。
【００８０】
以上のように本実施形態では、メモリの個数を抑えるためにｘ方向のみ素数個のメモリにインタリーブし、かつｙ方向の位置に応じて位相を変化させる方法を示した。そしてこの方法が図１３の１６点読み出しと矩形領域の４点読み出しとにおいて効率の高い読み出しができることがわかる。
【００８１】
（第３の実施形態）
第１及び第２の実施形態では、累積画像情報と呼ぶ２次元配列の情報での例を説明したが、本実施形態では１次元の情報に適用する方法を説明する。本実施形態では１次元配列のデータを入力とし、その入力データを１次元入力情報と呼ぶ。また、１次元入力情報を累積した情報を１次元累積情報と呼ぶ。
【００８２】
本実施形態での１次元配列の累積情報を図１０に示す。図１０では左端のデータを開始点として、ｘ方向にデータの値を累積させたものを１次元累積情報１２００としている。データ中の括弧内の数値はｘ方向の座標を示す。
【００８３】
本実施形態のパターン識別装置の構成は第１の実施形態と同様であるが、メモリ数が５個であるところが異なる。また、処理内容に第１の実施形態と一部差があり、その差分はメモリへの割り当て方法、並列読み出しの条件である。ここではその差分について説明する。
【００８４】
まず、１次元累積情報のメモリへの割り当て方法について説明する。１次元累積情報の座標（ｘ）の値をＣ（ｘ）で表す。そして、ｘ方向の割り当て数をＰ1とする。Ｐ1は素数であり、割り当てるメモリ数はＰ1個とし、メモリはＭｐ1で表す。ｐ1はメモリ番号で、ｐ1はｘ方向のメモリ番号値を示す。そして、Ｃ（ｘ）の格納先は以下の式（１８）で表される。
Ｍｐ1［address］＝Ｃ（ｘ）          ・・・（１８）
【００８５】
また、座標（ｘ）の画素値を格納するメモリ番号ｐ1は以下の式（１９）で表される。
ｐ1＝ｘ％Ｐ1          ・・・（１９）
ここで、％は剰余を表す。
【００８６】
そして、格納先のメモリＭｐ1へのaddressは以下の式（２０）で表される。
address＝ｘ／Ｐ1          ・・・（２０）
なお、除算は小数点以下切り捨て
【００８７】
以上が１次元累積情報を所定の規則に従ってメモリへ割り当てるための式である。本実施形態では、図１０のようにＰ1＝５で、Ｍ０（１２２０）からＭ４（１２２４）に格納する。以上を踏まえて各座標の１次元累積情報１２００を割り当てる。例えば、Ｃ（３）の格納先のメモリ番号は式（１９）より、メモリＭ１となる。そして、格納先のアドレスは式（２０）より、address＝１となる。この結果、式（１８）はＭ１［１］＝Ｃ（３）で表され、Ｃ（３）の値はメモリＭ１のaddress＝１に格納することになる。これらの計算によって１次元累積情報１２００は図１０のＭ０（１２２０）からＭ４（１２２４）に格納される。
【００８８】
次に、一定間隔の４点の並列読み出しについて説明する。１次元累積情報の第１の実施形態で説明した局所領域に相当するものは直線の区分１２１０（以下、１次元累積情報では局所区分（local piecewise）と呼ぶ）となる。ここでは３つの連続する局所区分１２１０、１２１１、１２１２の総和を求める例で説明する。
【００８９】
まずは１つの局所区分１２１０の総和の計算方法について説明する。局所区分１２１０の両端２点の座標をｘ0、ｘ1としそれぞれＡ、Ｂとすると、Ａ、Ｂは以下の式（２１）で表される。
Ａ：（ｘ0−１）
Ｂ：（ｘ1）          ・・・（２１）
【００９０】
そして、Ａ、Ｂの位置の累積情報値を読み出して、一次元入力情報の局所区分１２１０内の要素の総和値Ｓ1dは以下の式（２２）により計算される。
Ｓ1d＝Ｂ−Ａ          ・・・（２２）
【００９１】
以上のことから３つの連続する局所区分１２１０、１２１１、１２１２の総和を求めるにはデータ１２０１から１２０４の４点を読み出す必要がある。ここではこれらデータの間隔は３でメモリの割り当て数は５となり互いに素の関係であることがわかる。このため第１の実施形態でも説明した通り、連続する４点の読み出し先のメモリは異なる。図１０では斜線部のデータが連続する４点がメモリＭ０、Ｍ１、Ｍ３、Ｍ４に分かれていることが分かる。
【００９２】
次に、並列読み出しが行える条件式を示す。メモリへの割り当て数をＰ1、局所区分の長さをla＿lengthと定義すると、本実施形態の割り当て規則に応じて導出される条件式は以下の式（１３）で表される。
la＿length≠Ｐ1＊ｎ          ・・・（２３）
ここで、ｎは１以上の整数
【００９３】
但し、並列読み出しできる一定間隔の連続読み出し回数は２以上Ｐ1以下となる。そして、この条件式（２３）を満たすla＿length、連続読み出し回数になるように学習することで並列読み出しが可能となる。
【００９４】
（第４の実施形態）
本実施形態では、３次元の情報に適用した例について説明する。本実施形態では、３次元配列のデータを入力とし、その入力データを３次元入力情報と呼ぶ。３次元入力情報とは例えば動画情報であって、２次元画像に時間軸の１次元が加わり３次元入力情報となる。また、３次元入力情報を累積した情報を３次元累積情報と呼ぶ。
【００９５】
本実施形態での３次元配列の累積情報を図１１に示す。図１１では３次元入力情報１３００の原点Ｏを開始点として、ｘ方向、ｙ方向、t方向に値を累積させたものを３次元累積情報１３１０としている。例えば点１３０２の座標（ｘ，ｙ，ｔ）の３次元累積情報１３１０での値は原点Ｏと点１３０２を対角とする直方体１３０１に含まれるデータの合計値となる。本実施形態では直方体を動画情報で考え、ｘ方向を幅、ｙ方向を高さ、ｔ方向を時間で定義する。ここでｔ方向は時間軸で定義したが、もし立体空間であればｚ方向として奥行きと定義してもよい。
【００９６】
本実施形態のパターン識別装置の構成は第１の実施形態と同様であるが、メモリ数が１２５個であるところが異なる。これは各次元に５個ずつのメモリ割り当てるためで、５×５×５の計１２５個となる。また、処理内容に第１の実施形態との差分があり、差分はメモリへの割り当て方法、並列読み出しの条件である。ここではその差分について説明する。
【００９７】
まず、３次元累積情報のメモリへの割り当て方法について説明する。３次元累積情報の座標（ｘ，ｙ，ｔ）の値をＣ（ｘ，ｙ，ｔ）で表す。そして、ｘ方向の割り当て数をＰ1、ｙ方向の割り当て数をＰ2、ｔ方向の割り当て数をＰ3とする。Ｐ1、Ｐ2、Ｐ3は素数であり、割り当てるメモリの総数はＰ1、Ｐ2、Ｐ3個とし、メモリはＭｐ3ｐ2ｐ1で表す。ｐ1、ｐ2、ｐ3はメモリ番号で、ｐ1はｘ方向のメモリ番号、ｐ2はｙ方向のメモリ番号、ｐ3はｔ方向のメモリ番号を示す。そして、Ｃ（ｘ，ｙ，ｔ）の格納先は以下の式（２２）で表される。
Ｍｐ3ｐ2ｐ1［address］＝Ｃ（ｘ，ｙ，ｔ）          ・・・（２２）
【００９８】
また、座標（ｘ，ｙ，ｔ）の画素値を格納するメモリ番号ｐ1、ｐ2、ｐ3はそれぞれ以下の式（２３）〜式（２５）で表される。
ｐ1＝ｘ％Ｐ1          ・・・（２３）
ｐ2＝ｙ％Ｐ2          ・・・（２４）
ｐ3＝ｔ％Ｐ3          ・・・（２５）
ここで％は剰余を表す。
【００９９】
そして、３次元累積情報の幅width、高さheightとすると、格納先のメモリＭｐ3ｐ2ｐ1へのaddressは以下の式（２６）で表される。
address＝（（width／Ｐ1）＊（height／Ｐ2））＊（ｔ／Ｐ3）
＋（width／Ｐ1）＊（ｙ／Ｐ2）
＋（ｘ／Ｐ1）          ・・・（２６）
なお、除算は小数点以下切り捨て
【０１００】
以上が３次元累積情報を所定の規則に従ってメモリへ割り当てるための式である。本実施形態ではＰ1＝５、Ｐ2＝５、Ｐ3＝５で、各座標の３次元累積情報１３１０をメモリ（Ｍ０００）からメモリ（Ｍ５５５）に格納される。
【０１０１】
次に、図１１の１３２１に示される３×３×３の立体空間の読み出しについて説明する。３×３×３に並べられる各立体空間の形状は同じである。３次元累積情報における第１の実施形態で説明した局所領域に相当するものは直方体の空間１３１２（以下、３次元累積情報では局所空間（local space）と呼ぶ）となる。ここでは３×３×３の計２７個の局所空間それぞれの総和を求める例で説明する。
【０１０２】
まず、１つの局所空間１３１２の総和の計算方法について説明する。局所空間１３１２の対角を示す２点の座標を（ｘ0，ｙ0，ｔ0）、（ｘ1，ｙ1，ｔ1）とすると、Ａ〜Ｈはそれぞれ、以下の式（２７）で表される。
Ａ：（ｘ0−１，ｙ0−１，ｔ0−１）
Ｂ：（ｘ1，ｙ0−１，ｔ0−１）
Ｃ：（ｘ0−１，ｙ1，ｔ0−１）
Ｄ：（ｘ1，ｙ1，ｔ0−１）
Ｅ：（ｘ0−１，ｙ0−１，ｔ1）
Ｆ：（ｘ1，ｙ0−１，ｔ1）
Ｇ：（ｘ0−１，ｙ1，ｔ1）
Ｈ：（ｘ1，ｙ1，ｔ1）          ・・・（２７）
【０１０３】
そして、式（２７）に示す位置の累積情報値であるとすると、３次元入力情報の局所空間１３１２内要素の総和値Ｓ3dは、以下の式（２８）により計算することができる。
Ｓ３ｄ＝Ｈ−Ｄ−Ｆ＋Ｂ−（Ｇ−Ｃ−Ｅ＋Ａ）          ・・・（２８）
【０１０４】
以上のことから３×３×３の計２７個の局所空間それぞれの総和を求めるには局所空間１３２１の４×４×４の計６４点を読み出す必要がある。本実施形態ではこれらデータの各次元方向の間隔とメモリ割り当て数を互いに素の関係にする。互いに素の関係にあると第１の実施形態でも説明した通り、連続する等間隔の点は読み出し先のメモリが異なるので並列読み出しが可能となる。
【０１０５】
次に並列読み出しが行える条件を示す。各次元のメモリへの割り当て数をＰ1、Ｐ2、Ｐ3、１つの局所空間の幅（ｘ方向）をla＿width、高さ（ｙ方向）をla＿height、時間（ｔ方向）をla＿timeと定義する。本実施形態の割り当て規則に応じて導出される条件式は、以下の式（２９）〜式（３１）となる。
la＿width≠Ｐ1＊ｌ          ・・・（２９）
la＿height≠Ｐ2＊ｎ          ・・・（３０）
la＿time≠Ｐ3＊ｍ          ・・・（３１）
ここで、ｌ、ｎ、ｍは１以上の整数
【０１０６】
但し、並列読み出しできる一定間隔の連続読み出し回数はｘ方向で２以上Ｐ1以下、ｙ方向で２以上Ｐ2以下、ｔ方向で２以上Ｐ3以下となる。以上の式（２９）〜式（３１）を全て満たすことにより、読み出すメモリを排他関係にすることができ、局所空間１３２１の６４点の値を並列に読み出すことができるようになる。また、式（２９）〜式（３１）の少なくとも１つを満たすことができれば局所空間の６４点の値を部分的に並列に読み出すこともできる。
【０１０７】
以上のように、メモリへの割り当て規則、並列読み出しの条件を定義し学習時にその条件を加えることで、総メモリサイズを増やさずに、局所空間の頂点位置の累積情報を複数のメモリから常に並列に読み出すことができるようになる。
【０１０８】
（その他の実施形態）
以上の実施形態では１次元から３次元について説明した。さらに、３次元を超える多次元入力情報に対する累積情報であっても、同様に超直方体で考えれば、本発明を適用可能であるのは明らかである。また、第２の実施形態で説明した２次元の累積画像情報をｙ方向の位置に応じて位相を変えて割り当てる方法はその他の次元においても適用可能である。
【０１０９】
以上の実施形態では、累積情報を素数個のメモリに割り当て、矩形領域の形状制約を学習にて実施する方法を説明した。本発明は累積情報を読み出す間隔とメモリ数を互いに素の関係にすることが重要であって第１〜第４の実施形態の例に限るものではない。ここで、メモリ数が素数以外の場合について説明する。１次元の累積情報を例にすると累積情報を割り当てるメモリ数が４の場合、互いに素の関係となる局所区間の長さは１、３、５、７、９、・・・である。つまり局所区間の長さとメモリ数とを互いに素の関係にすることで並列読み出しを実現できることは明らかである。また、２次元、３次元、多次元でも同様に適用可能であることも明らかである。
【０１１０】
以上の実施形態では素数個のメモリを使った例を示したが、例えば装置内に素数個ではない６個のメモリが備わっており、その内の素数の５個のメモリを使うという装置であっても構わない。また、以上の実施形態ではパターン識別処理に弱判別器を使った例で説明したが本発明はこれに限らない。実際、パターン識別処理には様々なものが提案されており、実装も多岐にわたっている。しかし、これらパターン識別処理において累積情報を使用し特徴量を算出するものはいずれも本発明が適用できることは明らかである。
【０１１１】
以上の実施形態では所定の規則で割り当てる方法として元の累積情報において上下左右に隣接するデータを異なるメモリに割り当てる方法を説明したが本発明はこれに限らない。例えば近傍の累積情報を局所的にまとめて異なるメモリに割り当てても構わない。図１２にその例を示す。１４０１は割り当て前の積分画像である。積分画像１４０１に振ってあるＡ，Ｂ，Ｃ，Ｄは割り当て先のメモリの種類を示す。ＡはＭ００（１４２０）、ＢはＭ１０（１４２１）、ＣはＭ０１（１４２２）、ＤはＭ１１（１４２３）に割り当てる。そして、積分画像１４０１から局所領域１４０２の総和を求めるために１４１０、１４１１、１４１２、１４１３の画素を読み出す。このとき読み出し先のメモリはＭ００からＭ１１にすべて分かれていることがわかる。以上のように近傍の累積情報をメモリに割り当てても本発明の効果が得られることは明らかである。
【０１１２】
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【符号の説明】
【０１１３】
１１２  累積画像情報生成部
１１３  割り当て書き込み処理部
１１４  メモリアクセス制御部
１１９  識別処理制御部
１２３  処理ウィンドウ管理部
【図１】
0005777458.tif 000004
【図２】
0005777458.tif 000005
【図３】
0005777458.tif 000006
【図４】
0005777458.tif 000007
【図５】
0005777458.tif 000008
【図６】
0005777458.tif 000009
【図７】
0005777458.tif 000010
【図８】
0005777458.tif 000011
【図９】
0005777458.tif 000012
【図１０】
0005777458.tif 000013
【図１１】
0005777458.tif 000014
【図１２】
0005777458.tif 000015
【図１３】
0005777458.tif 000016
【図１４】
0005777458.tif 000017
【図１５】
0005777458.tif 000018