(57)【要約】【課題】初期の想定よりも大きなサイズの矩形領域内の画素値の総和値の算出が必要になった場合でも、正確に総和値の算出ができるようにする。【解決手段】２次元配列の処理対象情報内の各要素位置に対応する累積情報値として、処理対象情報の原点と各要素位置とを対角とする領域内の全ての要素値の総和値の下位の所定ビットを保持する累積情報値保持部１０２と、処理対象情報内に規定される矩形領域内の要素値の総和値を、累積情報値保持部１０２が保持している累積情報値を用いて算出する矩形領域内総和値算出部１０３とを備える。矩形領域内総和値算出部１０３は、矩形領域のサイズと所定の基準領域サイズとの比較結果に基づいて、矩形領域の分割を決定する矩形領域分割決定部１０４と、分割された矩形領域ごとに分割領域内の総和値を分割矩形領域内総和値として算出する分割矩形領域内総和値算出部１０５とを有する。【選択図】図１
2014153937.tif 000002
【特許請求の範囲】
【請求項１】
複数次元配列の処理対象情報内の各要素位置に対応する累積情報値として、前記処理対象情報の原点と前記処理対象情報の各要素位置とを対角とする領域内の全ての要素値の総和値の下位の所定ビットを保持する累積情報値保持手段と、
前記処理対象情報内に規定される特定領域内の要素値の総和値を、前記累積情報値保持手段が保持している前記累積情報値を用いて算出する特定領域内総和値算出手段とを備え、
前記特定領域内総和値算出手段は、
前記特定領域のサイズと予め設定された所定の基準領域サイズとの比較結果に基づいて、前記特定領域の分割を決定する特定領域分割決定手段と、
前記分割された特定領域ごとに分割領域内の総和値を分割特定領域内総和値として算出する分割特定領域内総和値算出手段とを有することを特徴とする特徴量算出装置。
【請求項２】
前記所定ビットのビット数は、前記所定の基準領域サイズ内の全ての要素が最大値をとるときの総和値をオーバーフローせずに格納するのに必要なビット数以上であることを特徴とする請求項１に記載の特徴量算出装置。
【請求項３】
前記特定領域分割決定手段では、前記特定領域を分割して得られる全ての分割特定領域が、前記所定の基準領域のサイズ以下になるように、前記特定領域を分割することを特徴とする請求項１又は２に記載の特徴量算出装置。
【請求項４】
前記分割特定領域内総和値算出手段では、前記累積情報値保持手段で保持されている複数の前記累積情報値の間で加減算を行い、前記加減算の結果の下位の所定ビットの部分を前記分割特定領域内総和値として算出することを特徴とする請求項１乃至３のいずれか１項に記載の特徴量算出装置。
【請求項５】
前記特定領域内総和値算出手段では、前記分割特定領域内総和値をさらに総和したものを前記特定領域内の総和値とすることを特徴とする請求項１乃至４のいずれか１項に記載の特徴量算出装置。
【請求項６】
前記複数次元配列は２次元配列であって、前記累積情報値を算出する領域は矩形領域であることを特徴とする請求項１乃至５のいずれか１項に記載の特徴量算出装置。
【請求項７】
前記特定領域とは矩形領域であることを特徴とする請求項１乃至６のいずれか１項に記載の特徴量算出装置。
【請求項８】
前記複数次元配列は３次元以上の多次元配列であって、前記累積情報値を算出する領域は超直方体の領域であることを特徴とする請求項１乃至５のいずれか１項に記載の特徴量算出装置。
【請求項９】
前記特定領域とは超直方体の領域であることを特徴とする請求項１乃至６のいずれか１項に記載の特徴量算出装置。
【請求項１０】
請求項１乃至９のいずれか１項に記載の特徴量算出装置を備えたことを特徴とするパターン認識システム。
【請求項１１】
複数次元配列の処理対象情報内の各要素位置に対応する累積情報値として、前記処理対象情報の原点と前記処理対象情報の各要素位置とを対角とする領域内の全ての要素値の総和値を算出し、前記総和値の下位の所定ビットを抽出するステップと、
前記処理対象情報内に規定される特定領域内の要素値の総和値を、前記累積情報値を用いて算出するステップとを有し、
前記特定領域内の要素値の総和値を算出するステップは、
前記特定領域のサイズと予め設定された所定の基準領域サイズとの比較結果に基づいて、前記特定領域の分割を決定するステップと、
前記分割された特定領域ごとに分割領域内の総和値を分割特定領域内総和値として算出するステップとを有することを特徴とする特徴量算出方法。
【請求項１２】
複数次元配列の処理対象情報内の各要素位置に対応する累積情報値として、前記処理対象情報の原点と前記処理対象情報の各要素位置とを対角とする領域内の全ての要素値の総和値を算出し、前記総和値の下位の所定ビットを抽出する処理と、
前記処理対象情報内に規定される特定領域内の要素値の総和値を、前記累積情報値を用いて算出する処理とをコンピュータに実行させ、
前記特定領域内の要素値の総和値を算出する処理では、
前記特定領域のサイズと予め設定された所定の基準領域サイズとの比較結果に基づいて、前記特定領域の分割を決定する処理と、
前記分割された特定領域ごとに分割領域内の総和値を分割特定領域内総和値として算出する処理とをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像の特徴量を算出するのに利用して好適な特徴量算出装置、方法及びプログラムに関する。
【背景技術】
【０００２】
情報処理の分野では、多次元配列を頻繁に扱う。その中で、特定範囲内の要素の和を求めることが多い。
特にコンピュータ・グラフィックスの分野では、矩形領域の累積情報（この情報は、summed-area tableやIntegral Imageや積分画像とも呼ばれている。本明細書では「累積情報」と呼ぶ。また、各要素位置に対応する累積情報の値を「累積情報値」と呼ぶ）の概念が提案されている。
図８を参照して、累積情報を用いた矩形領域内の画素値の総和の算出処理について説明する。累積情報とは、任意の点における要素値が、元画像の原点（ここでは元画像の左上を原点とする）とその任意の点とを対角とする領域内の画素値の総和となるようなデータである。例えば図８の要素１は、元画像における領域Ａに含まれる全画素の画素値の総和を要素値として持つ。このため、例えば元画像における領域Ｄに含まれる全画素の画素値の合計は、要素４の要素値から要素２及び要素３の要素値を減算し、要素１の要素値を加算することによって算出される。このように、元画像での矩形領域の画素値の総和が、累積情報を用いれば、矩形領域の四隅のデータ値を加減算することで高速に求めることができる。
つまり、入力画像の画素値をＩ(ｘ，ｙ)として、累積情報Ｃ(ｘ，ｙ)を次式（１）として定義した場合、入力画像に置かれた任意の矩形領域内のＩ(ｘ，ｙ)の総和値を、次式（２）を使って累積情報上の４点を参照するのみで求めることができる。
【０００３】
【数１】
2014153937.tif 000003
【０００４】
ここで、（ｘ0，ｙ0）は長方形の左上の頂点座標、（ｘ1，ｙ1）は右下の頂点座標である。これにより、画像上の矩形領域内の値の和を高速に求めることが可能となる。ただし、座標は０から始まるとし、Ｃ(ｘ，−１)及びＣ(−１，ｙ)は０とする。
このように累積情報とは、任意の点における要素値が、元画像の原点（ここでは元画像の左上を原点とする）とその任意の点とを対角とする領域内の画素値の総和となるようなデータである。よって、累積情報の要素値は、元画像の原点から離れていく（右下方向）に従って単調に増加する。従って、累積情報を配列（メモリ）に格納しようとした場合、その配列は、累積情報の右下のデータ値（元画像の原点である左上から、最も離れた位置の累積情報値、つまり、累積情報の最大の要素値）が格納できるだけのビット幅を持つ必要がある。
【０００５】
この場合、元画像のサイズが大きくなればなるほど、累積情報の桁数が増加し、そのため累積情報を格納するのに必要な配列のビット幅が大きくなり、その結果、配列全体のサイズが巨大になるという課題がある。
この問題を解決する手法として、特許文献１では、画素の総和値を算出する矩形領域の最大サイズを想定することで、累積情報を格納する配列のサイズを削減できる累積情報の算出手法が提案されている。
また、特許文献２では、元画像を分割し、分割した画像ごとに累積情報を算出することで、累積情報を格納する配列のサイズを削減できる累積情報の算出手法が提案されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−２９９６２７号公報
【特許文献２】特開２０１０−１３４６９２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
累積情報を格納する配列のサイズを削減できる手法として、特許文献１、２のような手法が提案されているが、それぞれ以下のような問題点がある。
特許文献１の手法では、想定している最大サイズを超えるようなサイズの矩形領域内の画素値の総和の算出手法に関しては、考慮されていない。
特許文献２の手法では、矩形領域のサイズに関わらず、画像分割を跨ぐような矩形領域であれば、画素値の総和算出を分割して行う必要がある。
【０００８】
本発明は上記のような点に鑑みてなされたものであり、初期の想定よりも大きなサイズの矩形領域内の画素値の総和値の算出が必要になった場合でも、正確に総和値の算出ができるようにすることを目的とする。
【課題を解決するための手段】
【０００９】
本発明の特徴量算出装置は、複数次元配列の処理対象情報内の各要素位置に対応する累積情報値として、前記処理対象情報の原点と前記処理対象情報の各要素位置とを対角とする領域内の全ての要素値の総和値の下位の所定ビットを保持する累積情報値保持手段と、前記処理対象情報内に規定される特定領域内の要素値の総和値を、前記累積情報値保持手段が保持している前記累積情報値を用いて算出する特定領域内総和値算出手段とを備え、前記特定領域内総和値算出手段は、前記特定領域のサイズと予め設定された所定の基準領域サイズとの比較結果に基づいて、前記特定領域の分割を決定する特定領域分割決定手段と、前記分割された特定領域ごとに分割領域内の総和値を分割特定領域内総和値として算出する分割特定領域内総和値算出手段とを有することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、初期の想定（初期想定の矩形領域のサイズを基準領域サイズと呼ぶ）よりも大きなサイズの矩形領域内の画素値の総和値の算出が必要になった場合でも、正確に総和値の算出ができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態に係る特徴量算出装置の構成を示すブロック図である。
【図２】総和値算出対象矩形領域の分割の手順を示すフローチャートである。
【図３】総和値算出対象矩形領域の分割手法を示す模式図である。
【図４】特徴量算出の手順を示すフローチャートである。
【図５】総和値算出対象矩形領域の分割手法を示す模式図である。
【図６】総和値算出対象矩形領域の分割手法を示す模式図である。
【図７】総和値算出対象矩形領域の分割手法を示す模式図である。
【図８】累積情報を用いた矩形領域内の画素値の総和の算出処理について説明するための図である。
【図９】解像度別に所望の特定領域内の要素の総和値を求める方法の説明図である。
【図１０】解像度別に特徴量算出をする場合の手順を示すフローチャートである。
【図１１】総和値算出対象矩形領域の分割手法を示す模式図である。
【図１２】多次元累積情報の一例である三次元累積情報の説明図である。
【発明を実施するための形態】
【００１２】
以下、添付図面を参照して、本発明の好適な実施形態について説明する。
（第１の実施形態）
本発明では、特許文献１で示された手順により算出された累積情報（Integral Image）を使用して、任意のサイズの矩形領域に含まれる要素の総和値を算出する。
本実施形態では、説明の簡単のため、累積情報を算出する対象となる複数次元配列の処理対象情報を２次元輝度画像データとする（この２次元輝度画像を「特徴量算出対象画像」と呼ぶ）。その場合、データの要素は各画素で、総和値を算出する要素値は各画素の輝度値となる。つまり、本実施形態では、２次元輝度画像を対象として、特許文献１の手順で算出した累積情報を使用して、画像中に規定される任意サイズの特定領域（本実施形態では矩形領域）に含まれる画素の輝度値の総和値を算出する場合を示す。本実施形態では、輝度値は８ビット（０〜２５５）とする。
【００１３】
ここで、特許文献１で示された累積情報算出の手順を簡単に説明する（詳細な手順に関しては特許文献１を参照のこと）。
特許文献１で示された累積情報算出では、まず最大矩形領域サイズを規定する。ここで、画素の総和値を算出することが想定されている矩形領域のうち最大のものを最大矩形領域といい、その最大矩形領域のサイズを最大矩形領域サイズという。その上で、最大矩形領域サイズで画素値の総和値を算出した場合に、桁溢れしない（オーバーフローチャートしない）ビット数を算出する（このビット数を「最大矩形領域総和値格納可能ビット数」と呼ぶ）。続いて、通常の累積情報の算出手順で得られる累積情報の下位の所定ビットとして最大矩形領域総和値格納可能ビット数分を抽出したものが、特許文献１の手法で算出される累積情報となる。通常の累積情報の算出手順に関しては特に問わないが、例えば、"F. C. Crow, "Summed-Area Tables For Texture Mapping", Computer Graphics, 1984" 記載の手法がある。
例えば、最大矩形領域サイズが水平方向１６画素、垂直方向１６画素の場合には、その総和値の最大値は、全ての画素が輝度値２５５をとった場合に、１６×１６×２５５＝６５２８０＝0xFF00（１６進数表示）となる。従って、最大矩形領域総和値格納可能ビット数は１６となる。この場合には、通常の累積情報の算出手順で得られる累積情報の下位１６ビット分が、特許文献１で示された累積情報となる。
以上のようにして、特許文献１で示された手順により累積情報が算出される。
【００１４】
この特許文献１で示された手順により算出された累積情報を用いて矩形領域の画素の総和値を算出する場合、その矩形領域のサイズが最大矩形領域サイズ以下であれば、式（２）に示した総和値算出式で得られる総和値から下位最大矩形領域総和値格納可能ビットを抽出することにより、正確な総和値の算出が可能である。しかしながら、今回総和値を算出しようとしている矩形領域のサイズが、何らかの理由により、最大矩形領域サイズを超えてしまった場合には、式（２）による総和値算出では、正確な総和値が算出できない。
本実施形態では、特許文献１で示された手順により算出された累積情報を使用して、任意のサイズ（最大矩形領域サイズを超えるサイズを含む）の矩形領域に含まれる画素の総和値を算出する手順を説明する。
【００１５】
図１は、本実施形態に係る特徴量算出装置１０１の構成を示すブロック図である。特徴量算出装置１０１は、２次元輝度画像の特徴量として、画像中に規定される矩形領域内の画素の総和値を算出することを行う。
１０２は累積情報値保持部である。累積情報値保持部１０２には、特許文献１で示された手順により算出された累積情報が格納されている。累積情報値保持部１０２はメモリで構成される。上述のように、特許文献１で示された手順により算出された累積情報は、最大矩形領域総和値格納可能ビット数以下である。従って、累積情報値保持部１０２をメモリで構成する場合には、最大矩形領域総和値格納可能ビット数以上のメモリ幅を持つメモリを使用すればよい。また、メモリの深さは、特徴量算出対象画像の画像サイズ以上であればよい。
累積情報値保持部１０２は、矩形領域内総和値算出部１０３から要素位置（メモリのアドレスに相当する）が入力されると、その要素位置に対応した累積情報値を出力する。本実施形態では、累積情報値保持部１０２に格納されている累積情報は、２次元輝度画像データから算出されたものである。従って、要素位置として、画像上の座標を指定すると、累積情報値として、画像原点とその座標を対角線とする矩形領域内の画素の総和値（特許文献１で示された手順により算出された総和値であるので、真の総和値の下位から最大矩形領域総和値格納可能ビット数分を取出したもの）が出力されることになる。
【００１６】
１０３は特定領域内総和値算出手段としての矩形領域内総和値算出部である。矩形領域内総和値算出部１０３には、総和値を算出したい矩形領域を規定する矩形領域情報が入力され、その矩形領域情報に基づいて算出された総和値が出力される。
矩形領域内総和値算出部１０３は、特定領域分割決定手段としての矩形領域分割決定部１０４、分割特定領域内総和値算出手段としての分割矩形領域内総和値算出部１０５、分割矩形領域内総和値加算部１０６から構成される。それぞれの詳細な説明は後述するが、簡単に総和値算出の手順をここで述べておく。まず、総和値を算出したい矩形領域（この領域を「総和値算出対象矩形領域」と呼ぶ）を規定する矩形領域情報が入力されると、矩形領域分割決定部１０４において、予め設定されている基準領域サイズと、総和値算出対象矩形領域とのサイズ比較が行われ、総和値算出対象矩形領域を分割するか否か、及び分割する場合にはどのように分割するかが決定される。ここで、基準領域サイズとは、特許文献１で示された累積情報算出の手順において用いられた最大矩形領域サイズのことを指す。分割矩形領域内総和値算出部１０５では、分割された矩形領域ごとに総和値を算出する。分割矩形領域内総和値加算部１０６では、分割された矩形領域ごとに算出された総和値をさらに加算して、総和値として出力する。
このように、総和値算出対象矩形領域を基準領域サイズ以下の矩形領域に分割すれば、分割した矩形領域それぞれに対しては、総和値が正確に算出できる。さらに、その正確に算出された総和値を、全ての分割された矩形領域に亘って加算すれば、全体としても正確な総和値が算出される。矩形領域内総和値算出部１０３は全体として以上のように動作する。
【００１７】
矩形領域分割決定部１０４には、今回画素の総和値を算出しようとしている矩形領域のサイズが算出できる情報が、矩形領域情報として入力される。ここで上述のように、今回総和値を算出しようとしている矩形領域を、総和値算出対象矩形領域と呼ぶことにする。矩形領域情報としては、総和値算出対象矩形領域の位置情報（例えば、総和値算出対象矩形領域の左上頂点の座標と、右下頂点の座標）が含まれているとする。また矩形領域分割決定部１０４には、累積情報を算出するときに用いた最大矩形領域サイズが基準領域サイズとして入力される。
矩形領域分割決定部１０４では上述のように、基準領域サイズ（累積情報を算出するときに用いた最大矩形領域サイズ）と、総和値算出対象矩形領域とのサイズ比較が行われる。そして、その比較結果に基づいて、総和値算出対象矩形領域を分割するか否か、及び分割する場合にはどのように分割するかが決定される。
ここで、基準領域サイズに関して説明をしておく。本実施形態では、基準領域サイズは、累積情報を算出するときに用いた最大矩形領域サイズとしている。そして、基準領域サイズ（最大矩形領域サイズ）と、画素値（輝度値）のビット数から、累積情報値保持部１０２で使用するメモリの（最少）ビット幅を決定している。後述する第３の実施形態では、逆に、累積情報値保持部１０２で使用するメモリのビット幅を先に決定し、そのビット幅に整合するように基準領域サイズを決定している。このように基準領域サイズの決め方には複数のやり方が存在する。
【００１８】
図２に、矩形領域分割決定部１０４による総和値算出対象矩形領域の分割の手順を示す。
ステップＳ２０１で、総和値算出対象矩形領域のサイズを算出する。ここでいうサイズとは矩形領域の面積を指す。総和値算出対象矩形領域の面積は、入力される矩形領域情報から算出される。
ステップＳ２０２で、総和値算出対象矩形領域のサイズと基準領域のサイズとを比較する。総和値算出対象矩形領域サイズが基準領域サイズ以下であった場合（Ｎｏの場合）、総和値算出対象矩形領域の分割を行わない。逆に、総和値算出対象矩形領域サイズが基準領域サイズを超えていた場合（Ｙｅｓの場合）、総和値算出対象矩形領域の分割を行う。
ステップＳ２０３で、総和値算出対象矩形領域を所定の方向に二分割する。図３に、分割の様子に示す。図３（Ａ）は、元の総和値算出対象矩形領域を示している。ステップＳ２０３において、例えば垂直方向に沿って二分割する処理が行われた場合、図３（Ｂ）に示すように、破線で分割される。分割はなるべく等分割されるように行う。
ステップＳ２０４で、これまでの分割処理で得られる分割矩形領域のうち最大のサイズのものを探索する。これまでの分割が全て等分割になっている場合には、どの分割矩形領域のサイズを選択してもよい。
ステップＳ２０５で、ステップＳ２０４において探索した最大の分割矩形領域のサイズと、基準領域のサイズとを比較する。最大の分割矩形領域のサイズが基準領域サイズ以下であった場合（Ｎｏの場合）、これ以上矩形領域の分割を行わない。逆に、最大の分割矩形領域のサイズが基準領域サイズを超えていた場合（Ｙｅｓの場合）、さらに矩形領域の分割を行う。
ステップＳ２０６で、前回の分割方向と直交する方向で、これまでに分割されてきた全ての分割領域を分割する。例えば図３（Ｂ）に示すように分割されていた場合には、今回の分割で図３（Ｃ）に示すように分割される。さらに、次回の分割（分割する必要がある場合）では、図３（Ｄ）に示すように分割される。
【００１９】
以上のように矩形領域分割決定部１０４による総和値算出対象矩形領域の分割は実現される。この手順では、分割された一つの分割矩形領域のサイズは、分割されるごとに（約）半分になる。
さらに、矩形領域分割決定部１０４は、このようにして得られる分割矩形領域それぞれの位置情報を算出する。矩形領域分割決定部１０４には、矩形領域情報として、総和値算出対象矩形領域の位置情報（例えば、総和値算出対象矩形領域の左上頂点の座標と、右下頂点の座標）が入力されるので、この情報から分割矩形領域ごとの位置情報は簡単に算出できる。この分割矩形領域ごとの位置情報を分割矩形領域情報として、分割矩形領域内総和値算出部１０５に出力する。
【００２０】
分割矩形領域内総和値算出部１０５では、入力される分割矩形領域ごとの位置情報（例えば、各分割矩形領域の左上頂点の座標と、右下頂点の座標）から、各分割矩形領域内の画素の総和値を算出する。算出には、累積情報値保持部１０２に保持されている累積情報を用いる。つまり、各分割矩形領域ごとに、式（２）を用いて、画素の総和値を算出する。このとき式（２）の演算結果の下位から最大矩形領域総和値格納可能ビットの部分を取出したものが、各分割矩形領域内の画素の総和値となる。
【００２１】
分割矩形領域内総和値加算部１０６では、分割矩形領域内総和値算出部１０５で算出された分割矩形領域ごとの総和値を全て加算して、元の総和値算出対象矩形領域の画素の総和値として出力する。
【００２２】
以上のようにして、総和値算出対象矩形領域の画素の総和値を算出する。また、矩形領域分割決定部１０４において、総和値算出対象矩形領域が一度も分割されなかった場合でも、総分割数が１である場合として、上記の手順で総和値算出対象矩形領域の総和値の算出が可能である。
【００２３】
次に、図４を参照して、特徴量算出装置１０１を用いて、どのような手順で特徴量（本実施形態では、矩形領域内の画素値の総和値）を算出するのかを説明する。
ステップＳ４０１で、総和値算出対象矩形領域（総和値を算出したい矩形領域）の矩形領域情報を用いて、総和値算出対象矩形領域のサイズを算出する。サイズの算出は矩形領域分割決定部１０４で行われる。
ステップＳ４０２で、総和値算出対象矩形領域を、基準領域サイズ以下の複数の矩形領域に分割する。分割は、矩形領域分割決定部１０４において、図２に示した手順に従って行われる。
ステップＳ４０３で、分割矩形領域ごとに頂点の座標を算出する。この処理も、矩形領域分割決定部１０４で行われる。
ステップＳ４０４で、分割矩形領域ごとに、その領域内の画素の総和値を算出する。この処理は、分割矩形領域内総和値算出部１０５が、累積情報値保持部１０２にアクセスして分割矩形領域の各頂点に対応する累積情報値を読み出して、式（２）を実行し、その演算結果の下位から最大矩形領域総和値格納可能ビット数分を取出すことで実現される。
ステップＳ４０５で、分割矩形領域ごとの総和値のさらに総和値を算出する。この処理は、分割矩形領域内総和値加算部１０６で行われる。
以上のような手順で、総和値算出対象矩形領域内の画素値の総和値が算出される。
【００２４】
上記の説明では、総和値算出対象矩形領域の分割の仕方として、水平方向に分割、垂直方向に分割を交互に行うとしている。しかしながら、本発明で対象とする総和値算出対象矩形領域の分割の方法はこれに限らない。最終的に基準領域サイズ以下の矩形領域に分割されるようなやり方であれば、どのように分割していってもよい。
例えば、図５に示すように、分割する毎に同じ一方向に沿って分割するような手法でもよい（図５（Ａ）、（Ｂ）、（Ｃ）、（Ｄ）の順に分割が進んでいく）。
図６に、同じ八分割した時の分割の様子を、図３の分割手順の場合（図６（Ａ））と、図５の分割手順の場合（図６（Ｂ））とについて示す。本発明では分割の手法は問わないので、図６（Ａ）のように分割しても、図６（Ｂ）のように分割してもよい。ただ、その後に行われる、分割矩形領域ごとにその領域内の画素の総和値を算出する手順（ステップＳ４０４）において、各分割矩形領域の頂点座標に対応する累積情報値へのアクセスが発生する。このため、なるべく分割矩形領域の頂点数が少ないように分割する方が、処理時間の観点で有利となる。図６では、各分割矩形領域の頂点を黒丸で示している。図６（Ａ）では頂点数は１５、図６（Ｂ）では頂点数は１８となるので、図３に示したように分割していく方が有利となる。
【００２５】
また、図７に別の分割手法で分割した場合の分割の様子を示している。図７（Ａ）は基準領域を示している。基準領域は、水平方向９画素、垂直方向２４画素のサイズとし、総和値算出対象矩形領域は、水平方向４８画素、垂直方向２４画素のサイズとする。図７（Ｂ）は、総和値算出対象矩形領域を、基準領域サイズの領域と残りの領域とに二分割（等分割ではない）した様子を表している。この場合、残りの領域は基準領域よりも大きいので、さらに基準領域サイズと残りに分割される（図７（Ｃ））。これを繰り返して、全ての分割矩形領域が基準領域サイズ以下になったのが図７（Ｄ）である。同じサイズの基準領域、総和値算出対象矩形領域に対して、図３の分割手法、図５の分割手法を適用すると、それぞれ、図６（Ａ）、（Ｂ）の分割状態となるまで分割される。この場合、図７（Ｄ）では分割矩形領域の頂点数は１４となり、さらに有利な分割手法であるといえる。
【００２６】
また、別の分割手法としては、総和値算出対象矩形領域の形状やサイズごとに、最適な分割を予め検討しておいて、その結果に従って分割するという手法でもよい。ここで最適というのは、分割後の分割矩形領域の頂点数が最も少なくなるという意味である。最適な分割を、総和値算出対象矩形領域の形状やサイズごとに参照できるように、テーブル等で予め設定しておいて、実際の分割の際には、そのテーブルを参照して分割してもよい。
また、分割された各分割矩形領域のサイズや形状はそれぞれ異なっていてもよい。
【００２７】
特徴量算出装置をこのように構成することで、基準領域サイズを超えるようなサイズの矩形領域に対しても、その領域内の画素値の総和値が正確に算出される。また、基準領域サイズを超えないようなサイズの矩形領域に対しては、分割する必要無しに、その領域内の画素値の総和値が正確に算出される。
つまり、基準領域サイズを超えるようなサイズの矩形領域に対しては、基準領域サイズ以下になるように矩形領域を分割することで、それぞれの分割矩形領域において、画素値の総和値が正確に算出される。さらにそれらの総和値を、全ての分割矩形領域に亘って加算することで、元の矩形領域内の画素値の総和値が正確に算出される。
このことにより、本来、解像度の違う画像ごとに累積情報が必要な場合でも、高解像度の画像の累積情報があれば、低解像度の画像の累積情報としても用いることが可能となる。
また、矩形領域の分割の手法として、なるべく分割後の矩形領域の総頂点数が少なくなるように分割すれば、総和値算出の際に必要となる累積情報値保持部へのアクセス回数が単純に増加するのを抑えることができる。
【００２８】
（第２の実施形態）
本実施形態では、パターン認識システムに本発明を適用した例を示す。特にパターン認識として、顔検出を実現した場合の例を示す。
本実施形態に係る顔検出システムでは、顔検出を行いたい入力画像に対して、累積情報（Integral Image）を算出する。累積情報を用いた顔検出アルゴリズムとしては、" 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."がよく知られている。本実施形態では、特徴量算出装置を用いて算出した累積情報を、上記の顔検出アルゴリズムで使用する例を示す。
【００２９】
上記顔検出アルゴリズムでは、図９（Ａ）に示すように、ある特定の大きさの処理ウインドウ９０２を、処理対象となる画像（顔検出対象画像）９０１内で移動させ、各移動先の処理ウインドウ９０２内に人物の顔が含まれるか否かを判定する処理を行う。顔が含まれるか否かの判定には、処理ウインドウ９０２内に所定の矩形領域９０３、９０４を設定し、その矩形領域内の画素値の総和を算出する処理を含む一連の処理により実現されている（処理の詳細は上記文献を参照のこと。本発明は、矩形領域内の画素値の総和を算出する処理のみを対象とした発明であるので、それ以外の処理に関する説明は割愛する）。
図９では、説明の簡単のため、処理ウインドウ９０２中に、画素値の総和を算出する矩形領域は９０３と９０４の２矩形しか示していない。しかしながら、これらの矩形領域の数、位置、サイズは、機械学習によって決定されるものであり、現実にはもっと多量の矩形領域が存在し、それらの画素値の総和を算出することになる。
また、一般に顔検出対象画像９０１内に存在する顔の大きさは未知である。従って、上記の「処理ウインドウ９０２を顔検出対象画像９０１内で移動させながら、各移動先の処理ウインドウ９０２内に人物の顔が含まれるか否かを判定する処理」を、画像９０１の解像度を変化させながら行うことになる。
【００３０】
ここで、画像の解像度を変化させた時に、累積情報（Integral Image）を用いた矩形領域内画素値の総和値を求める手順がどう変化するかについて説明する。
単純には画像の解像度別に累積情報を算出すればよいが、累積情報算出の手順が解像度数に相当する回数繰り返されることになる。その手間を回避するために、最も高解像度の画像（この解像度を「基本解像度」と呼ぶことにする）に対して、累積情報を算出しておき、それ以外のより低解像度の画像に対しては、その累積情報を使いまわす方法が考えられる。図９を参照して、その手順を説明する。本実施形態では、低解像度の画像を作成する手法としては、線形補間手法を用いるとする。
図９（Ａ）は、基本解像度の顔検出対象画像９０１を示している。また、図９（Ｃ）は、基本解像度の顔検出対象画像９０１から作成した累積情報を示している。９２１は顔検出対象画像９０１から作成した累積情報を示している。９２２は処理ウインドウ９０２に対応する累積情報上の処理ウインドウの位置を示している。９２３、９２４はそれぞれ矩形領域９０３、９０４に対応する累積情報上の矩形領域の位置を示している。従って例えば、矩形領域９０３内の画素値の総和値を算出する場合には、累積情報上の矩形領域９２３の４頂点座標に対応する累積情報値にアクセスし、式（２）の手順で演算すれば算出できる。
図９（Ｂ）は、基本解像度の顔検出対象画像９０１を１／４サイズ（水平方向、垂直方向ともに１／２サイズに縮小）に縮小した図を示している。縮小処理は、線形補間手法を用いるが、図９の場合はちょうど１／４サイズへの縮小処理なので、近傍４画素の平均を算出し、その値を縮小画像の画素値とする。９１１は縮小処理された顔検出対象画像、９１２は処理ウインドウ、９１３と９１４は矩形領域を示している。
また、図９（Ｄ）は、縮小処理された顔検出対象画像９１１に対する顔検出処理を、基本解像度の顔検出対象画像９０１から作成した累積情報を用いて行う場合の図を示している。９３１は基本解像度の顔検出対象画像９０１から作成した累積情報であり、９２１と同じものである。９３２は処理ウインドウ９１２に対応する累積情報上の処理ウインドウの位置を示している。９３３、９３４はそれぞれ矩形領域９１３、９１４に対応する累積情報上の矩形領域の位置を示している。画像９１１は累積情報９３１に比べて、解像度が縦横それぞれ１／２倍になっているので、画像９１１中の座標を２倍すれば、累積情報上での座標になる。従って例えば、矩形領域９１３内の画素値の総和値を算出する場合には、累積情報上の矩形領域９３３の４頂点座標に対応する累積情報値にアクセスし、式（２）の手順で演算した結果を解像度の比で割れば（図９の場合は４で割れば）算出できる。
【００３１】
図１０は、顔検出処理の流れを示すフローチャートである。次に、図１０を用いて、顔検出処理の具体的な流れについて説明する。本顔検出処理の中心的処理である、矩形領域内の画素値の総和値を算出する処理では、第１の実施形態の図１で示した特徴量算出装置１０１が用いられる。
ステップＳ１００１で、基本解像度の顔検出対象画像に対して累積情報を算出する。この累積情報算出の手順は、特許文献１で示された累積情報算出の手順に従って行う。このとき、累積情報算出の手順で必要となる、想定する最大矩形領域（画素の総和値を算出することが想定されている矩形領域のうち最大のもの）は、基本解像度において算出が想定されている矩形領域の最大サイズのものとなる。つまり、図９の矩形領域９０３、９０４のうちの最大サイズのものを最大矩形領域サイズ（基準領域サイズ）として想定して、累積情報９２２を算出する。前述のように図９では説明の簡単のため、画素値の総和を算出する矩形領域は９０３と９０４の２矩形しか示していない。そのサイズは、矩形領域９０３の方が矩形領域９０４より大きいので、このような場合には、最大矩形領域サイズは、矩形領域９０３のサイズとなる。もちろん現実には、顔検出にはもっと多量の矩形領域の画素値の総和を算出する必要があるので、その多量の矩形領域のうちで最大のサイズのものを最大矩形領域サイズとする。ここで算出した累積情報は、図１の累積情報値保持部１０２に格納される。
【００３２】
ステップＳ１００２で、顔検出対象画像の解像度を決定する。最初は入力画像そのままの解像度（基本解像度）に対して以降の顔検出処理を行う。
【００３３】
ステップＳ１００３で、処理の対象となる処理ウインドウ９０２が顔検出対象画像９０１上に配置される。基本的には、この処理ウインドウは、図９（Ａ）に示すように顔検出対象画像９０１の端から一定間隔で縦方向及び横方向へスキャンすることによって順に網羅的に移動して選択される。例えば、顔検出対象画像９０１をラスタスキャンすることによって処理ウインドウが選択される。
【００３４】
ステップＳ１００４で、選択された処理ウインドウについて、処理ウインドウ内の矩形領域に対して、その領域内の画素値の総和値を算出する。総和値の算出には、特徴量算出装置１０１が用いられる。
ステップＳ１００４における総和値算出の手順は、図２に示されたものであるが、本実施形態に沿って再度説明する。
まず、特徴量算出装置１０１に、総和値を算出したい矩形領域（図９の矩形領域９０３や９０４）を規定する矩形領域情報が入力され、矩形領域のサイズが算出される。ここで、矩形領域のサイズとは、累積情報が算出された解像度でのサイズをいう。最初の解像度（基本解像度）であれば、累積情報が算出された解像度（図９（Ｃ）に相当）と、現在顔検出処理を行っている画像の解像度（図９（Ａ）に相当）は等しいので、画像中での矩形領域のサイズが、累積情報が算出された解像度でのサイズとなる。この解像度では、全ての矩形領域のサイズは、最大矩形領域サイズ以下であるので、矩形領域内の画素値の総和値を算出するために矩形領域を分割する処理は発生しない（ステップＳ２０２でＮｏが選ばれる）。以降、図２の手順に従うことで、総和値が算出される。
【００３５】
しかしながら、本実施形態のように、顔検出対象画像に対して、解像度を変更（低解像度化）しながら顔検出する場合には、初回以降の解像度では、顔検出対象画像は基本解像度から縮小されていく（例えば図９（Ｂ）に相当）。従って、縮小画像中での指定された矩形領域のサイズは、累積情報が算出された解像度では画像縮小率に応じて大きなサイズになる。例えば、図９の矩形領域９１３と矩形領域９３３、或いは矩形領域９１４と矩形領域９３４の関係のようになる。図９（Ｂ）の場合には、縮小画像中での指定された矩形領域９１３のサイズを４倍したものが、累積情報が算出された解像度での矩形領域９３３のサイズとなる。
従って、顔検出対象画像が、基本解像度から縮小処理されたものの場合には、基本解像度で想定した最大矩形領域サイズを超えるサイズの矩形領域に対して、矩形領域内の画素値の総和値を算出する必要が発生する。そのような場合でも、最大矩形領域サイズ（基準領域サイズ）と、今回の矩形領域サイズ（累積情報が算出された解像度でのサイズ）とを比較して（ステップＳ２０２）、図２の手順に従うことで、総和値が算出される。
例えば、図９において矩形領域９０３のサイズ（最大矩形領域サイズ）は、矩形領域９０４のサイズの４倍（水平方向、垂直方向各２倍）であったとする。その場合、累積情報が算出された解像度での、矩形領域９１３、９１４のサイズは、それぞれ矩形領域９３３、９３４のサイズになる。従って、矩形領域９１３内の画素値の総和値を、累積情報９３１を用いて算出する場合には、分割して行うことになる。また、累積情報が算出された解像度での、矩形領域９１４のサイズは、矩形領域９３４のサイズになる。このサイズは基本領域サイズに等しいので、矩形領域９１４内の画素値の総和値を、累積情報９３１を用いて算出する場合には、分割する必要は生じない。
この一連の処理が、ステップＳ１００４では、各矩形領域に関して行われる。
【００３６】
ステップＳ１００５で、ステップＳ１００４における結果を用いて、処理ウインドウに人物の顔が含まれるか否かの判定が実施される。この判定処理の詳細は、本発明に無関係であるので、説明は割愛する。
【００３７】
ステップＳ１００６で、判定の対象となっていた処理ウインドウが、顔検出対象画像の中で最後の処理ウインドウであったか否かを判断する。最後の処理ウインドウではなかった場合（Ｎｏの場合）、ステップＳ１００３の処理に戻り、次の処理ウインドウが選択され、ステップＳ１００４以降の処理が実行される。一方、最後の処理ウインドウであった場合（Ｙｅｓの場合）、顔検出対象の入力画像に対するこの解像度での顔検出処理は終了する。
【００３８】
ステップＳ１００７で、顔検出処理で必要な解像度処理が終了したか否かを判断する。全ての解像度に対して顔検出処理が行われてない場合（Ｎｏの場合）、ステップＳ１００２に戻り、次の解像度が選択される。一方、全ての解像度に対して顔検出処理が行われた場合（Ｙｅｓの場合）、顔検出処理を終了する。どれだけの範囲の解像度に対して顔検出処理を行うのかは、検出したい顔のサイズの上限、下限に依存する。また、解像度の刻みは、機械学習を行う際の条件設定や、求められる顔検出の性能に応じて決定される。
【００３９】
以上のように、最も高解像度の画像（基本解像度）で累積情報を算出すれば、それ以外のより低解像度の画像に対しては、その累積情報を使いまわすことが可能となる。
この場合、低解像度の画像に対しては、基本解像度で想定した最大矩形領域サイズを超えるサイズの矩形領域に対して、矩形領域内の画素値の総和値を算出する必要が発生する。
しかしながら、そのような場合でも、矩形領域を分割して、分割した矩形領域ごとに総和値を算出することで、元の矩形領域内の画素値の総和値が算出できる。
本実施形態で説明した顔検出処理では、処理ウインドウをスキャンさせながら、矩形領域の総和値を算出する手順となる。このような手順おいて、矩形領域を分割させる必要がある場合には、隣接するスキャン位置で分割境界が共通化できるような分割を行えば、スキャン位置が変わっても、累積情報へのアクセスが共通化できる利点が生じる。
【００４０】
図１１に、一連のスキャン処理中の処理ウインドウと、処理ウインドウ内の矩形領域の様子を示す。図１１では、画像（図示せず）中を（Ａ）、（Ｂ）、（Ｃ）の順で処理ウインドウをスキャンさせている様子を示しており、１１０１、１１０２、１１０３は処理ウインドウ、１１０４、１１０５、１１０６は総和値算出対象矩形領域を示している。つまり、処理ウインドウ１１０１を一つ進めたものが、処理ウインドウ１１０２で、さらに一つ進めたものが処理ウインドウ１１０３となっている様子を示している。
ここで、総和値算出対象矩形領域１１０４は分割が必要なサイズあるとし、図中の点線のように分割されるとする。続いて一つスキャンを進めた総和値算出対象矩形領域１１０５を分割する場合には、分割する位置（矩形内の位置ではなくて、画像中の位置）を１１０４の分割と同じ位置にする。さらに一つスキャンを進めた総和値算出対象矩形領域１１０６を分割する場合にも、分割する位置（矩形内の位置ではなくて、画像中の位置）を１１０４の分割と同じ位置にする。つまり、図１１の総和値算出対象矩形領域の分割矩形領域の各頂点のうちハッチングされた丸印で示された頂点は、画像中で同じ位置となるように、総和値算出対象矩形領域１１０４、１１０５、１１０６を分割する。つまり、図１１中の頂点Ｕ、Ｕ’、Ｕ’’は画像中で同じ位置、頂点Ｖ、Ｖ’、Ｖ’’は画像中で同じ位置、…となるように、分割する。
このように分割することによって、総和値算出対象矩形領域１１０４での分割矩形領域のハッチングされた丸印の頂点座標に対応する累積情報値を記憶しておけば、総和値算出対象矩形領域１１０５での分割矩形領域の総和値の算出や、総和値算出対象矩形領域１１０６での分割矩形領域の総和値の算出にも使いまわすことが可能である。つまり、総和値算出対象矩形領域１１０４の総和値を算出する際に累積情報を参照して得たＵ、Ｖ、Ｗ、Ｘ、Ｙ、Ｚの各頂点の累積情報値を記憶しておけば、総和値算出対象矩形領域１１０５や総和値算出対象矩形領域１１０６の総和値の算出のときに、累積情報を参照する必要はなくなる。このことにより、累積情報へのアクセス回数を減少させることができるので、処理時間の観点で有利となる。隣接するどれだけの処理ウインドウの間で、分割矩形領域の頂点が共通化できるかは、処理ウインドウのステップ数や、分割の手法に依存する。
このように、処理ウインドウをスキャンさせながら、矩形領域の総和値を算出する手順の場合には、隣接するスキャン位置で分割境界が共通化できるような分割を行うことで、処理の高速化も可能となる。
【００４１】
（第３の実施形態）
本実施形態では、累積情報値保持部１０２をメモリやレジスタ等のハードウエアリソースを用いて構成する場合に関する実施形態を説明する。
第１の実施形態で説明したように、特許文献１で示された手順により算出された累積情報をメモリに格納する場合には、最大矩形領域総和値格納可能ビット数以上のメモリ幅を持ち、特徴量算出対象画像の画像サイズ以上のメモリ深さを持つメモリを用いればよい。レジスタに格納する場合も同様に、最大矩形領域総和値格納可能ビット数以上のビット幅を持つレジスタを、特徴量算出対象画像の画像サイズ以上個用いればよい。
このように、これまでの実施形態では、想定する最大矩形領域サイズを基準領域サイズとして、そのサイズの矩形領域内での画素値の総和値を算出した場合に桁溢れしないように、最大矩形領域総和値格納可能ビット数を算出した。
本実施形態では、逆に、累積情報を格納するメモリやレジスタのリソースの制限から最大矩形領域総和値格納可能ビット数を設定し、その設定に整合するように基準領域を算出する場合の例を示す。
例えばハードウエアリソースの制限から、累積情報を格納するメモリとしてメモリ幅が１２ビットのメモリを使用せざるを得ないような場合、メモリに格納できる最大値は４０９５（0xFFF）である。累積情報を算出する特徴量算出対象画像として、８ビット輝度値（０〜２５５）を持つ画像であるとすると、画素値の総和値が１２ビットで桁あふれしない最大の領域サイズは、４０９５／２５５＝１６（小数点以下切り捨て）となる。従って、この場合には、基準領域サイズ１６となる。
このようにして算出した基準領域を用いて算出した累積情報に対しても、特徴量算出装置を用いて、任意のサイズの矩形領域内の画素値の総和値を算出することができる。なお総和値算出の手順は、これまでの実施形態で示したものと同様なので、ここでは説明を割愛する。
【００４２】
これまでの実施形態では、２次元配列の処理対象情報に対し分割領域累積情報を算出し、その分割領域累積情報を利用して、２次元の特定領域の要素値の総和を求めているが、本実施形態では、本発明を３次元以上の処理対象情報に適用する場合を示す。
累積情報は３次元以上の多次元配列情報に対しても生成することができる。図１２は３次元の場合の累積情報の様子を例示する図である。３次元配列の入力情報とは、例えば動画情報であって、２次元画像に時間軸の１次元が加わり３次元情報となる。
図１２（ａ）において、３次元累積情報配列の点Ｘの位置の要素には、入力３次元情報における原点と点Ｘを対角とする直方体の中に含まれる要素の総和値となる。
この３次元累積情報を用いて、例えば図１２（ｂ）に示す直方体１２０１内の要素の総和値を求めることが可能である。ここで、直方体１２０１の対角を示す２点の座標を（ｘ0，ｙ0，ｔ0）、（ｘ1，ｙ1，ｔ1）とする。Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈをそれぞれ次式（３）なる位置の累積情報値であるとすると、入力情報の直方体１２０１内要素の総和値Ｓ3dは、次式（４）として計算することができる。
【００４３】
【数２】
2014153937.tif 000004
【００４４】
この３次元累積情報に対し、本発明の考え方を適用することももちろん可能である。この場合の分割領域は３次元の直方体になる。また基準領域は３次元の直方体であり、その直方体中にある全要素の総和が桁あふれしないだけのビット数が、最大矩形領域総和値格納可能ビット数となる。また、２次元情報に対する矩形領域のサイズとは矩形領域の面積であったが、３次元情報に対しては直方体の体積となる。例えば、基準領域のサイズとは、基準直方体の体積となる。
３次元を超える多次元入力情報に対する累積情報も、同様に超直方体で考えれば、本発明を適用可能であるのは明らかである。
また、分割領域累積情報を用いた情報処理としては、パターン認識処理に限定するものではない。本発明は、従来技術で述べたようなコンピュータグラフィクス等の他分野の処理であっても、累積情報を用いる処理であれば、適用可能であることは言うまでも無い。
【００４５】
（その他の実施形態）
また、本発明は、以下の処理を実行することによっても実現される。すなわち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【符号の説明】
【００４６】
１０１：特徴量算出装置、１０２：累積情報値保持部、１０３：矩形領域内総和値算出部、１０４：矩形領域分割決定部、１０５：分割矩形領域内総和値算出部、１０６：分割矩形領域内総和値加算部
【図１】
2014153937.tif 000005
【図２】
2014153937.tif 000006
【図３】
2014153937.tif 000007
【図４】
2014153937.tif 000008
【図５】
2014153937.tif 000009
【図６】
2014153937.tif 000010
【図７】
2014153937.tif 000011
【図８】
2014153937.tif 000012
【図９】
2014153937.tif 000013
【図１０】
2014153937.tif 000014
【図１１】
2014153937.tif 000015
【図１２】
2014153937.tif 000016