第1画像を複数のブロックに分割し、第2画像を前記第1画像と同数のブロックに分割する画像分割部と、前記第1画像及び前記第2画像のそれぞれについて、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、前記第1画像の特徴ベクトル及び前記第2画像の特徴ベクトルを算出する特徴ベクトル算出部と、ラグランジュの未定乗算決定法を利用して2つの画像の正規化相互相関値を求める式から導いた2つの画像の正規化相互相関の上限値を算出する式を用いて、算出された前記第1画像の特徴ベクトル及び前記第2画像の特徴ベクトルに基づき、前記第1画像と前記第2画像の正規化相互相関の上限値を算出する上限値算出部と、前記上限値が第1の閾値以上であるか否かに基づいて前記第1画像と前記第2画像を照合する第1照合部と、を有することを特徴とする画像照合装置。前記特徴ベクトル算出部は、mを前記ブロック内の画素数、nを前記ブロックの数、φijを前記第1画像におけるi番目のブロック内のj番目の画素の画素値、φaveを前記第1画像の全画素の画素値の平均値として、次のベクトルξxを前記第1画像の特徴ベクトルとして算出し、ψijを前記第2画像におけるi番目のブロック内のj番目の画素の画素値、ψaveを前記第2画像の全ての画素の画素値の平均値として、次のベクトルξyを前記第2画像の特徴ベクトルとして算出し、前記上限値算出部は、前記第1画像の特徴ベクトルと前記第2画像の特徴ベクトルの内積を前記上限値として算出する、請求項1に記載の画像照合装置。前記上限値が前記第1の閾値以上である前記第1画像と前記第2画像の正規化相互相関値を算出する正規化相互相関値算出部と、前記正規化相互相関値が前記第1の閾値以下の値である第2の閾値以上であるか否かに基づいて前記第1画像と前記第2画像を詳細に照合する第2照合部と、をさらに有する、請求項1または2に記載の画像照合装置。第1画像を複数のブロックに分割するステップと、前記第1画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、前記第1画像の特徴ベクトルを算出するステップと、第2画像を前記第1画像と同数のブロックに分割するステップと、前記第2画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、前記第2画像の特徴ベクトルを算出するステップと、ラグランジュの未定乗算決定法を利用して2つの画像の正規化相互相関値を求める式から導いた2つの画像の正規化相互相関の上限値を算出する式を用いて、算出された前記第1画像の特徴ベクトル及び前記第2画像の特徴ベクトルに基づき、前記第1画像と前記第2画像の正規化相互相関の上限値を算出するステップと、前記上限値が第1の閾値以上であるか否かに基づいて前記第1画像と前記第2画像を照合するステップと、を含むことを特徴とする画像照合方法。前記第1画像の特徴ベクトルを算出するステップにおいて、mを前記ブロック内の画素数、nを前記ブロックの数、φijを前記第1画像におけるi番目のブロック内のj番目の画素の画素値、φaveを前記第1画像の全画素の画素値の平均値として、次のベクトルξxを前記第1画像の特徴ベクトルとして算出し、前記第2画像の特徴ベクトルを算出するステップにおいて、mを前記ブロック内の画素数、nを前記ブロックの数、ψijを前記第2画像におけるi番目のブロック内のj番目の画素の画素値、ψaveを前記第2画像の全ての画素の画素値の平均値として、次のベクトルξyを前記第2画像の特徴ベクトルとして算出し、前記上限値を算出するステップにおいて、前記第1画像の特徴ベクトルと前記第2画像の特徴ベクトルの内積を前記上限値として算出する、請求項4に記載の画像照合方法。前記上限値が前記第1の閾値以上である前記第1画像と前記第2画像の正規化相互相関値を算出するステップと、前記正規化相互相関値が前記第1の閾値以下の値である第2の閾値以上であるか否かに基づいて前記第1画像と前記第2画像を詳細に照合するステップと、をさらに有する、請求項4または5に記載の画像照合方法。第1画像を複数のブロックに分割するステップと、前記第1画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、前記第1画像の特徴ベクトルを算出するステップと、第2画像を前記第1画像と同数のブロックに分割するステップと、前記第2画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、前記第2画像の特徴ベクトルを算出するステップと、ラグランジュの未定乗算決定法を利用して2つの画像の正規化相互相関値を求める式から導いた2つの画像の正規化相互相関の上限値を算出する式を用いて、算出された前記第1画像の特徴ベクトル及び前記第2画像の特徴ベクトルに基づき、前記第1画像と前記第2画像の正規化相互相関の上限値を算出するステップと、前記上限値が第1の閾値以上であるか否かに基づいて前記第1画像と前記第2画像を照合するステップと、をコンピュータに実行させることを特徴とするコンピュータプログラム。非特許文献2に開示された技術を用いることにより、高速に画像照合を実施することができる。しかしながら、非特許文献2に開示されたNCCの上限値は、NCC値より大きくなりすぎる場合がある。その場合、照合する二画像のNCC値が低いにも関わらず、その二画像の類似性が高いと判定するおそれがあった。そこで、本発明の目的は、画像照合を高速に実施するとともに、画像の類似性を高精度に判定することが可能な画像照合装置、画像照合方法及びそのような画像照合方法をコンピュータに実行させるコンピュータプログラムを提供することにある。本発明に係る画像照合装置は、第1画像を複数のブロックに分割し、第2画像を第1画像と同数のブロックに分割する画像分割部と、第1画像及び第2画像のそれぞれについて、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、第1画像の特徴ベクトル及び第2画像の特徴ベクトルを算出する特徴ベクトル算出部と、ラグランジュの未定乗算決定法を利用して2つの画像の正規化相互相関値を求める式から導いた2つの画像の正規化相互相関の上限値を算出する式を用いて、算出された第1画像の特徴ベクトル及び第2画像の特徴ベクトルに基づき、第1画像と第2画像の正規化相互相関の上限値を算出する上限値算出部と、上限値が第1の閾値以上であるか否かに基づいて第1画像と第2画像を照合する第1照合部と、を有する。さらに、本発明に係る画像照合装置において、特徴ベクトル算出部は、mをブロック内の画素数、nをブロックの数、φijを第1画像におけるi番目のブロック内のj番目の画素の画素値、φaveを第1画像の全画素の画素値の平均値として、次のベクトルξxを第1画像の特徴ベクトルとして算出し、ψijを第2画像におけるi番目のブロック内のj番目の画素の画素値、ψaveを第2画像の全ての画素の画素値の平均値として、次のベクトルξyを第2画像の特徴ベクトルとして算出し、上限値算出部は、第1画像の特徴ベクトルと第2画像の特徴ベクトルの内積を上限値として算出することが好ましい。さらに、本発明に係る画像照合装置において、上限値が第1の閾値以上である第1画像と第2画像の正規化相互相関値を算出する正規化相互相関値算出部と、正規化相互相関値が第1の閾値以下の値である第2の閾値以上であるか否かに基づいて第1画像と第2画像を詳細に照合する第2照合部と、をさらに有することが好ましい。また、本発明に係る画像照合方法は、第1画像を複数のブロックに分割するステップと、第1画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、第1画像の特徴ベクトルを算出するステップと、第2画像を第1画像と同数のブロックに分割するステップと、第2画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、第2画像の特徴ベクトルを算出するステップと、ラグランジュの未定乗算決定法を利用して2つの画像の正規化相互相関値を求める式から導いた2つの画像の正規化相互相関の上限値を算出する式を用いて、算出された第1画像の特徴ベクトル及び第2画像の特徴ベクトルに基づき、第1画像と第2画像の正規化相互相関の上限値を算出するステップと、上限値が第1の閾値以上であるか否かに基づいて第1画像と第2画像を照合するステップと、を含む。さらに、本発明に係る画像照合方法において、第1画像の特徴ベクトルを算出するステップにおいて、mをブロック内の画素数、nをブロックの数、φijを第1画像におけるi番目のブロック内のj番目の画素の画素値、φaveを第1画像の全画素の画素値の平均値として、次のベクトルξxを第1画像の特徴ベクトルとして算出し、第2画像の特徴ベクトルを算出するステップにおいて、mをブロック内の画素数、nをブロックの数、ψijを第2画像におけるi番目のブロック内のj番目の画素の画素値、ψaveを第2画像の全ての画素の画素値の平均値として、次のベクトルξyを第2画像の特徴ベクトルとして算出し、上限値を算出するステップにおいて、第1画像の特徴ベクトルと第2画像の特徴ベクトルの内積を上限値として算出することが好ましい。さらに、本発明に係る画像照合方法において、上限値が第1の閾値以上である第1画像と第2画像の正規化相互相関値を算出するステップと、正規化相互相関値が第1の閾値以下の値である第2の閾値以上であるか否かに基づいて第1画像と第2画像を詳細に照合するステップと、をさらに有することが好ましい。また、本発明に係るコンピュータプログラムは、第1画像を複数のブロックに分割するステップと、第1画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、第1画像の特徴ベクトルを算出するステップと、第2画像を第1画像と同数のブロックに分割するステップと、第2画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、第2画像の特徴ベクトルを算出するステップと、ラグランジュの未定乗算決定法を利用して2つの画像の正規化相互相関値を求める式から導いた2つの画像の正規化相互相関の上限値を算出する式を用いて、算出された第1画像の特徴ベクトル及び第2画像の特徴ベクトルに基づき、第1画像と第2画像の正規化相互相関の上限値を算出するステップと、上限値が第1の閾値以上であるか否かに基づいて第1画像と第2画像を照合するステップと、をコンピュータに実行させる。本発明によれば、画像照合を高速に実施するとともに、画像の類似性を高精度に判定することが可能な画像照合装置、画像照合方法及びそのような画像照合方法をコンピュータに実行させるコンピュータプログラムを提供することができる。以下、本発明に係る画像照合装置、画像照合方法及びコンピュータプログラムについて図を参照しつつ説明する。但し、本発明の技術的範囲はそれらの実施の形態に限定されず、特許請求の範囲に記載された発明とその均等物に及ぶ点に留意されたい。図1は、本発明を適用した画像照合装置の概略構成を示す図である。図1に示すように、画像照合装置1は、インターフェース部11、記憶部12、表示部13及び制御部20を有する。以下、画像照合装置1の各部について詳細に説明する。インターフェース部11は、例えばインターネット、電話回線網携帯端末回線網、一般電話回線網を含む、イントラネット等のネットワークを介して他のコンピュータ等と画像データ及び各種のデータを送受信する通信インターフェースであり、接続するネットワークの通信インターフェース回路を有する。また、インターフェース部11は、例えばUSB等のシリアルバスに準じるインターフェース回路を有し、フラッシュメモリ等を接続し、そのフラッシュメモリ等から画像データ及び各種のデータを取得するようにしてもよい。インターフェース部11は、制御部20と接続されており、制御部20により制御される。記憶部12は、RAM、ROM等のメモリ装置、ハードディスク等の固定ディスク装置、又はフレキシブルディスク、光ディスク等の可搬用の記憶装置等を有する。また、記憶部12には、画像照合装置1の各種処理に用いられるコンピュータプログラム、データベース、テーブル等が格納される。記憶部12は、制御部20と接続され、インターフェース部11を介して取得した画像データを格納するとともに、制御部20により画像データについてなされた演算結果を格納する。制御部20は、複数の画像について特徴ベクトルを算出し、各画像が類似するか否かを判定する。そのために、制御部20は、第1画像取得部21、第1画像分割部22、第1特徴ベクトル算出部23、第2画像取得部24、第2画像分割部25、第2特徴ベクトル算出部26、上限値算出部27及び第1照合部28を有する。また、制御部20は、インターフェース部11、記憶部12及び表示部13と接続され、インターフェース部11のデータ送受信制御、記憶部12の制御、表示部13の表示制御等を行う。制御部20は、予め記憶部12に記憶されているプログラムに基づいて動作する。あるいは、制御部20は、集積回路、マイクロプロセッサ、ファームウェア等で構成されてもよい。図2は、画像照合装置1による画像照合処理の動作を示すフローチャートである。以下、図2に示したフローチャートを参照しつつ、画像照合処理の動作を説明する。なお、以下に説明する動作のフローは、予め記憶部12に記憶されているプログラムに基づき主に制御部20により画像照合装置1の各要素と協同して実行される。最初に、第1画像取得部21は、インターフェース部11を介して、外部のコンピュータ、フラッシュメモリ等から画像を取得し以下、第1画像取得部21が取得した画像を第1画像と称する、記憶部12に保存するステップS201。次に、第1画像分割部22は、記憶部12に保存された第1画像を読み出し、第1画像を所定サイズの複数のブロックに分割するステップS202。例えば、第1画像分割部22は、352×240画素の画像を22×15画素の256ブロックに分割する。図3は、ブロック毎に分割した画像の例を示す模式図である。図3の例では、画像300を、各ブロックの画素数がmであるn個のブロックに分割した画像310を示す。次に、第1特徴ベクトル算出部23は、第1画像について、分割したブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づく特徴ベクトルを算出し、第1画像と関連付けて記憶部12に保存するステップS203。画像x、画像yについてブロック内画素数がmである、n個のブロックに分割した場合のNCC値を、ブロックの番号i1≦i≦n及びブロック内の画素の番号j1≦j≦mを用いて式11で定義する。ここで、φij、ψijは、各画素の画素値であり、φaveは画像xの全画素の画素値の平均値であり、ψaveは画像yの全画素の画素値の平均値である。画像x及び画像yの各画素の正規化画素値xij及びyijを式12で定義する。なお、正規化画素値は、厳密には式13とすべきであるが、本実施形態では単純化のため正規化画素値を式12で定義する。式11のNCC値は、式12の正規化画素値xij及びyijを用いて式14で表される。また、画像xのi番目のグループにおける正規化画素値xijの総和及び二乗和並びに画像yのi番目のグループにおける正規化画素値yijの総和及び二乗和を式15~18で定義する。ここで、正規化画素値の性質上、式19、20が成り立つ。以下、ラグランジュの未定乗数決定法を利用して式14から2つの画像のNCCの厳密な上限値を算出する式を求める。本実施形態では、式21の関数の極値問題を考える。ここで、λ1i、λ2i、λ3i、λ4iは、4n個のラグランジュ未定乗数である。式21において、微分係数dΛ=0全てのi、jについて∂Λ∂xij=0、∂Λ∂yij=0とすることにより、式22、23の2mn個の式が得られる。式22、23から式24が得られる。ここで、式24が成立すると仮定すると、xij、yijは式25で求められる。この場合、式25の右辺はiブロックの番号のみにより定まるので、xij、yijは全てのjブロック内の画素について同一の値をとることになり、条件が強すぎることになる。一方、式24が成立しないと仮定すると、式24の左辺の行列の行列式から式26が得られる。また、式22、23、26から、式27が得られる。この場合、式22と式23は、同じ意味を表すことになる。従って、本実施形態では、式22のみを用いてNCCの上限値を算出する式を求める。まず、式22から式28が得られる。式28を式17に代入することにより、式29が得られる。一方、式28を式18に代入することにより、式30が得られる。式29より、式31が得られる。式31を式30に代入することにより、式32が得られる。式28、31、32を式14に代入することにより、式33が得られる。つまり、NCCの上限値UBは式34で与えられ、NCCの下限値LBは式35で与えられる。NCC値はこの上限値UBを越えることがないので、NCC値の代わりに上限値UBを用いて画像xと画像yの類似性を評価することができる。一方、式34の上限値UBは、式36に示されるように、式37、38で示される特徴ベクトルξxとξyの内積となる。式37、38に示されるように、特徴ベクトルξx及びξyは、それぞれ画像x、画像yのみから算出することができる。つまり、画像照合装置1は、予め画像x、画像yをそれぞれ2n個の要素をもつ特徴ベクトルξx及びξyに変換しておくことにより、その内積を算出して上限値UBを求めることができ、特に、ある画像を複数の画像と照合するときに高速に照合することができる。そこで、第1特徴ベクトル算出部23は、第1画像の特徴ベクトルとして第1画像について式37の特徴ベクトルξxを算出する。次に、第2画像取得部24は、インターフェース部11を介して、外部のコンピュータ、フラッシュメモリ等から画像を取得し以下、第2画像取得部24が取得した画像を第2画像と称する、記憶部12に保存するステップS204。次に、第2画像分割部25は、記憶部12に保存された第2画像を読み出し、第1画像を分割したブロックとそれぞれ同サイズ、同数の複数のブロックに分割するステップS205。次に、第2特徴ベクトル算出部26は、第2画像について、分割したブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づく特徴ベクトル、つまり式38の特徴ベクトルξyを算出し、第2画像と関連付けて記憶部12に保存するステップS206。次に、上限値算出部27は、式36に示すように特徴ベクトルξx、ξyの内積を算出して、上限値UBを求めるステップS207。次に、第1照合部28は、上限値UBが所定の閾値θ1以上であるか否かに基づいて第1画像と前記第2画像を照合する。まず、第1照合部28は、上限値UBが閾値θ1以上であるか否かを判定するステップS208。この閾値θ1は、NCCを用いて二つの画像が類似するか否かを判定するときに、NCC値と比較する閾値θ0-1≪θ0<1と同じ値である。あるいは、閾値θ1は、閾値θ0より大きい値としてもよい。第1照合部28は、上限値UBが閾値θ1以上である場合、第1画像が第2画像と類似すると判定しステップS209、一連のステップを終了する。一方、第1照合部28は、上限値UBが閾値θ1未満である場合、第1画像が第2画像と類似しないと判定しステップS210、一連のステップを終了する。例えば、画像照合装置1は、類似すると判定した画像のペアを利用者が確認できるように、表示部13に表示する。あるいは、画像照合装置1は、類似すると判定した画像のペアの情報をインターフェース部11を介して外部のコンピュータ不図示に通知してもよい。なお、上限値UBと下限値LBの間の範囲が狭いほど、上限値UBは、NCC値をより正確に近似していることになる。上限値UBと下限値LBの間の範囲は、式34、35から、式39により求めることができる。一方、であり、ここで、Gjk=xijxij-xijxikとすると、式41が成り立つ。従って、式40は、式42で表される。ここで、Ekはkにわたる期待値であり、Variはi番目のブロック内のxijの分散である。同様に、が成立し、式39は、式44で表される。つまり、上限値UBと下限値LBの間の範囲を狭くするためには、各ブロック内部の正規化画素値の分散を小さくするか、一ブロック内の画素数mを小さくする必要がある。しかし、一ブロック内の画素数mを小さくすると、ブロック数nが大きくなり、特徴ベクトルξxとξyの次元数が大きくなるため、現実的でない。従って、同一ブロック内の画素の間の正規化画素値の差が可能な限り小さくなるように各ブロックを構成し、各ブロック内部の正規化画素値の分散を小さくすることが好ましい。一般に、画像のマルコフ性により、近傍の画素の正規化画素値は、非常に近い値をもつことが知られている。従って、例えばブロックの形状を、長方形、特に正方形に近い形にすることにより、各ブロック内の画素の画素値を近付け、上限値UBをよりNCC値に近似させることができる。なお、MSEAにより算出されるNCCの上限値UBMSEAは、式5から式45のように表される。本実施形態により算出されるNCCの上限値UBと、MSEAにより算出されるNCCの上限値UBMSEAについて、式34と式45のルート内の式を比較することにより式46が成立する。従って、式47が成立し、本実施形態により算出されるNCCの上限値UBは、MSEAにより算出されるNCCの上限値UBMSEA以下となる。つまり、本実施形態により算出されるNCCの上限値UBは、MSEAにより算出されるNCCの上限値UBMSEAより正確にNCC値を近似していることが理論的に示される。以上詳述したように、図2に示したフローチャートに従って動作することによって、画像照合装置1は、元の情報量数万程度の画素数から大幅に圧縮した数十~百程度の特徴ベクトルすなわち低次元特徴量を用いて、画像の類似性を高速かつ高精度に判定することが可能となった。なお、画像照合装置1は、照合する二画像のサイズが異なる場合、二画像のサイズを同一サイズに正規化することにより、サイズの異なる二画像についても低次元特徴量を用いた画像照合をすることができる。図4は、制御部の他の例を示す概略構成図である。図4に示す制御部30は、図1に示す制御部20の代わりに用いることが可能である。図4に示す制御部30は、図1に示す制御部20の各部に加えて、NCC値算出部31と第2照合部32を有する。図5は、図4に示す制御部30を用いる画像照合装置1による詳細な画像照合処理の動作を示すフローチャートである。以下、図5に示したフローチャートを参照しつつ、詳細な画像照合処理の動作を説明する。なお、以下に説明する動作のフローは、予め記憶部12に記憶されているプログラムに基づき主に制御部30により画像照合装置1の各要素と協同して実行される。また、図5に示したフローチャートは、図2に示したフローチャートにより、類似すると判定された画像のペアに対して実行される。最初に、NCC値算出部31は、類似すると判定された第1画像と第2画像について式11を用いてNCC値を算出するステップS501。次に、第2照合部32は、NCC値算出部31により算出されたNCC値が所定の閾値θ0例えば0.9以上であるか否かに基づいて第1画像と第2画像を詳細に照合する。まず、第2照合部32は、NCC値が閾値θ0以上であるか否かを判定するステップS502。なお、上述した通り、この閾値θ0は閾値θ1以下の値の閾値である。第2照合部32は、NCC値が閾値θ0以上である場合、第1画像と第2画像は類似すると判定しステップS503、一連のステップを終了する。一方、第2照合部23は、NCC値が閾値θ0未満である場合、第1画像と第2画像は類似しないと判定しステップS504、一連のステップを終了する。例えば、画像照合装置1は、図5に示したフローチャートにより類似すると判定した画像のペアを表示部13に表示する。あるいは、画像照合装置1は、図5に示したフローチャートにより類似すると判定した画像のペアの情報をインターフェース部11を介して外部のコンピュータ不図示に通知してもよい。なお、制御部20は、第1画像取得部21と第2画像取得部24の代わりに、第1画像及び第2画像の何れをも取得できる画像取得部を備えることもできる。また、第1画像分割部22と第2画像分割部25の代わりに第1画像及び第2画像の何れをも所定のブロックに分割できる画像分割部を備えることもできる。さらに、第1特徴ベクトル算出部23と第2特徴ベクトル算出部26の代わりに第1画像の特徴ベクトル及び第2画像の特徴ベクトルの何れをも算出できる特徴ベクトル算出部を備えることもできる。また、ステップS204~S206の第2画像に対する処理は、ステップS201~S203の第1画像に対する処理より前に実施してもよい。また、画像照合装置1が複数のCPUを備えること等により、並列処理が可能な場合には、ステップS204~S206の第2画像に対する処理と、ステップS201~S203の第1画像に対する処理を並列に実施してもよい。以上詳述したように、図5に示したフローチャートに従って動作することによって、画像照合装置1は、低次元空間での類似性が高いNCCの上限値UBが閾値θ1以上の画像のペアのうち、オリジナル空間での類似性が低いNCC値が閾値θ0未満の画像のペアを取り除くクレンジングすることができる。これにより、画像照合装置1は、ある画像のペアに対して低負荷で類似性を判定しておき、その判定において類似性が高いと判定した画像のペアのみについて高負荷で高精度に類似性を判定するので、効率よく画像を照合できるようになった。図6は、画像照合装置を画像検索サーバに適用する場合の制御部の概略構成図である。図6に示す制御部40は、図1に示す制御部20又は図4に示す制御部30の代わりに用いることが可能である。図6に示す制御部40は、図4に示す制御部30の各部に加えて、インデックス判定部41を有する。なお、以下では、第1画像を事前に記憶部12に格納された照合元の画像とし、第2画像を外部のコンピュータ不図示等から検索を要求された問合せ画像として説明する。図7は、図6に示す制御部40を用いる画像照合装置1による画像の取得処理の動作を示すフローチャートである。以下、図7に示したフローチャートを参照しつつ、画像取得処理の動作を説明する。なお、以下に説明する動作のフローは、予め記憶部12に記憶されているプログラムに基づき主に制御部40により画像照合装置1の各要素と協同して実行される。図7に示すフローチャートでは、画像照合装置1は、第1画像の取得のみを実施し、第1画像と第2画像の照合処理は、後述するフローチャートで説明する。図7に示すステップS701~S703の処理は、図2に示すステップS201~S203の処理と同じであるため、説明を省略する。第1特徴ベクトル算出部23は、第1画像について特徴ベクトルを算出すると、算出した特徴ベクトルに基づいて多次元インデックスを作成するステップS704。式48、49に示すように、式37、38で求められる特徴ベクトルξx、ξyのノルムは1になる。つまり、式50に示すように、特徴ベクトルξxとξyの内積は、特徴ベクトルξxとξyのユークリッド距離に変換することができる。つまり、特徴ベクトルξxとξyのユークリッド距離が式51の条件を満たす場合、特徴ベクトルξxとξyの内積は閾値θ1以上となり、NCCの上限値UBは閾値θ1以上となる。従って、画像照合装置1は、特徴ベクトルξxとξyの内積を算出する代わりに、特徴ベクトルξxとξyのユークリッド空間における距離探索を行うことにより、式52の条件を満たす画像のペアを抽出することができる。この場合、画像照合装置1は、ユークリッド距離を用いた距離探索をサポートする、多次元データに対するインデキシング技術BohmCBerchtoldSKeimDASeptember2001SearchinginhighdimensionalspacesIndexstructuresforimprovingtheperformanceofmultimediadatabasesACMComputingSurveys33322373を適用することができ、画像照合のさらなる高速化を図ることができる。画像照合装置1は、多次元インデキシング技術として、例えば、木構造を用いるANNApproximateNearestNeighborsAryaSMountDMNetanyahuNSSilvermanRWuAYNovember1998AnoptimalalgorithmforapproximatenearestneighborsearchingfixeddimensionsJACM45891923、ハッシュを用いるLSHLocalitySensitiveHashingAndoniAIndykP2008NearoptimalhashingalgorithmsforapproximatenearestneighborinhighdimensionsCommunACM51117122、階層的ベクトル量子化NisterDSteweniusH2006ScalablerecognitionwithavocabularytreeInProcofCVPRVol2pp21612168、ベクトル量子化及びスカラー量子化ハミングエンベディングDouzeMJe ́gouHSandhawaliaHAmsalegLSchmidC2009EvaluationofgistdescriptorsforwebscaleimagesearchInProceedingoftheACMInternationalConferenceonImageandVideoRetrievalCIVR’09ACMNewYorkNYUSApp191198等の、高次元空間におけるk近傍法k-NN探索を用いた技術を利用できる。例えば、多次元インデキシング技術としてLSHを利用する場合、第1特徴ベクトル算出部23は、特徴ベクトルに対して、予め定められた複数のハッシュ関数を用いて複数のハッシュ値を算出し、多次元インデックスとする。あるいは、多次元インデキシング技術としてANNを利用する場合、画像照合装置1は、特徴ベクトルについての特徴空間を予め所定の領域に分割しておく。そして、第1特徴ベクトル算出部23は、特徴ベクトルが属する特徴空間の領域を多次元インデックスとする。第1特徴ベクトル算出部23は、多次元インデックスを作成すると、第1画像と関連付けて記憶部12に格納しステップS705、一連のステップを終了する。図8は、画像照合装置1が画像検索サーバとして動作する場合の画像照合処理の動作を示すフローチャートである。以下、図8に示したフローチャートを参照しつつ、画像照合処理の動作を説明する。なお、以下に説明する動作のフローは、予め記憶部12に記憶されているプログラムに基づき主に制御部40により画像照合装置1の各要素と協同して実行される。なお、図8に示すステップS801~S803の処理は、図2に示すステップS204~S206の処理と同じであるため、説明を省略する。ただし、多次元インデキシング技術としてLSHを利用する場合、第2特徴ベクトル算出部26は、ステップS803で第2画像について特徴ベクトルを算出した後、その特徴ベクトルについて、第1画像の特徴ベクトルに対してハッシュ値を算出したのと同一の、複数のハッシュ関数を用いて複数のハッシュ値を算出する。ステップS804~S808の処理は、記憶部12に格納された全ての第1画像に対して各画像毎に実施される。ステップS804において、インデックス判定部41は、第2特徴ベクトル算出部26により第2画像について特徴ベクトルが算出されると、記憶部12から第1画像の特徴ベクトル及び多次元インデックスを読み出すステップS804。次に、インデックス判定部41は、第1画像の特徴ベクトルと第2画像の特徴ベクトルが多次元インデックスに基づく条件を満たしているか否かを判定するステップS805。例えば、多次元インデキシング技術としてLSHを利用する場合、インデックス判定部41は、記憶部12から読み出した第1画像の特徴ベクトルのハッシュ値が、第2画像の特徴ベクトルの対応するハッシュ値と所定数例えば、全ハッシュ値のうちの半数以上一致するか否かにより、多次元インデックスに基づく条件を満たしているか否かを判定する。あるいは、多次元インデキシング技術としてANNを利用する場合、インデックス判定部41は、第1画像の特徴ベクトルが属する特徴空間の領域が、第2画像の特徴ベクトルとのユークリッド距離が2-2θ1以下となる部分を含むか否かにより、多次元インデックスに基づく条件を満たしているか否かを判定する。インデックス判定部41が多次元インデックスに基づく条件を満たしていると判定した場合、第1照合部28は、第1画像の特徴ベクトルと第2画像の特徴ベクトルのユークリッド距離が式51の条件を満たすか否かを判定するステップS806。第1照合部28は、式51の条件が満たされている場合、その第1画像を第2画像に類似する画像の候補以下、類似画像候補と称するとして抽出するステップS807。一方、ステップS805でインデックス判定部41が多次元インデックスに基づく条件が満たされていないと判定した場合、ステップS806で第1照合部28が式51の条件が満たされていないと判定した場合、又は、ステップS807で第1照合部28が類似画像候補を抽出した場合、制御部40は、第2画像を全ての第1画像と比較したか否かを判定するステップS808。制御部40は、まだ第2画像と比較していない第1画像がある場合、ステップS804~S807の処理を繰り返し、全ての第2画像と第1画像との比較が完了すると、一連のステップを終了する。制御部40は、図8のフローチャートを終了した後、さらに、図5に示したフローチャートを実施し、第2画像の類似画像候補として抽出した第1画像についてNCC値を用いて詳細に画像照合を行う。そして、制御部40は、第2画像と類似すると判定した第1画像の情報をインターフェース部11を介して検索を要求したコンピュータに通知する。あるいは、制御部40は、図8のフローチャートにより類似画像候補として抽出した第1画像の情報をインターフェース部11を介して検索を要求したコンピュータに通知してもよい。以上詳述したように、図8に示したフローチャートに従って動作することによって、画像照合装置1は、画像検索サーバとして動作し、複数の画像に対する画像照合を高速かつ高精度に実施することが可能となった。また、所定の画像を複数の画像と照合する場合に多次元インデックス構造を利用して照合処理を高速化することが可能となった。以下、本実施形態の低次元変換方法による類似画像の抽出精度について説明する。複数の画像Ii1を有する画像セットIS1IS1{Ii1}と複数の画像Ii2を有する画像セットIS2IS2{Ii2}において、NCC値が閾値θ0より大きくなる画像のペアの集合IIPSは、式53のように表される。この集合IIPSは、本実施形態で算出されるNCCの上限値UBが閾値θ0より大きくなる、つまり式54で表される画像のペアの集合IIPSに近似できる。上述した通り、NCC値は上限値UB以下となるので、上限値UBがθ0以下である場合、NCC値は確実にθ0以下となり、対応する画像のペアは確実にIIPSに含まれないと判断できる。つまり、式55の関係が成立し、IIPSに含まれる画像のペアがIIPSから取りこぼされることはない。一方、IIPSに対してIIPSが大きくなりすぎると、類似しない画像まで類似画像として抽出していることになり、類似画像の抽出精度が低いということになる。このように、低次元変換の効果及び抽出した画像の類似性は、類似画像の抽出精度以下、プレシジョンと称すると、類似画像の非取りこぼし率以下、リコールと称するを用いて評価することができる。式56はプレシジョンの算出式であり、式57はリコールの算出式である。例えば、IIPSを非常に大きくする極端な例ではIIPSをIIPSの全集合とすることにより、リコールを容易に100にすることができるが、その場合、プレシジョンが低くなる。低次元変換においてはリコールを100に保ちつつ、プレシジョンを可能な限り高くすることが好ましい。図9は、本実施形態及び他の低次元変換方法においてリコールを100にしたときのプレシジョンを表すグラフである。図9では、他の低次元変換方法としてMSEAと、離散コサイン変換DCT:DiscreteCosineTransformが用いられる。図9に示すグラフ900において、グラフ901は本実施形態によるプレシジョンを示し、グラフ902はMSEAによるプレシジョンを示し、グラフ903はDCTによるプレシジョンを示す。グラフ900の横軸は各低次元変換における特徴量特徴ベクトルの次元数を示し、縦軸はプレシジョンを示す。なお、図9は、1時間のビデオからランダムに選択された1万フレームの画像と他の1時間のビデオからランダムに選択された1万フレームの画像についてのプレシジョンを示す。この二つの異なる1時間のビデオは、異なった日の同じ時間帯に同じチャンネルで放送された映像であり、オープニング、エンディングの画像等、同一の画像が幾つか含まれている。各画像は352×240画素の画像であり、閾値θ0及びθ1は0.9に設定されている。式5の上限値UBMSEAは、式58に示すように、式59、60で示される特徴ベクトルの内積で表される。そこで、MSEAを用いた低次元変換方法では、低次元特徴量として式59、60に示す特徴ベクトルを使用し、その内積が閾値θ1以上となる二画像を類似画像として抽出する。図10は、DCTを用いた低次元変換方法を説明するための概略図である。DCTを用いた低次元変換方法では、まず、各画像の正規化画像を所定のブロックに分割し、二次元DCTにより周波数成分に変換する。図10のブロック1000内の各要素a0、a1、a2、は、二次元DCTにより変換されたDCT係数を示す。図10に示すように、二次元DCTにより変換されたDCT係数は、MPEG、JPEG等で用いられるジグザグスキャンにより低周波数成分側から順に並べられる。そして、式61に示すように、低周波数成分側から順に選択されたDCT係数による特徴ベクトルがDCTによる低次元特徴量となる。なお、DCT係数は正規化画像から生成され、DC成分は常に0となるため省略される。DCTにより変換された周波数成分の全パワーは元の画像のパワーと一致する。つまり、全DCT係数を用いて計算したユークリッド距離がNCC値に対応するので、DCT係数の一部又は全部を用いて計算したユークリッド距離が2-2θ0以下である場合、NCC値がθ0以上となることはない。そこで、この方法では、式62に示すように、それぞれのDCT成分がai、biである二つの画像の特徴ベクトルのユークリッド距離を求め、ユークリッド距離が2-2θ1θ1≧θ0以下となる二画像を類似画像として抽出する。なお、図9に示すグラフ900では、式62に示すユークリッド距離が2-2θ1以下となる画像のペアの集合をIIPSとし、NCC値がθ0以上となる画像のペアの集合をIIPSとしてプレシジョン及びリコールを算出している。図9に示すように、特に次元数が低い場合プレシジョンは必ずしも高くない。プレシジョンは、最も高くても15未満であり次元数が1024の場合、次元数が64の場合は5~6まで落ちる。また、DCTによるプレシジョンは、本実施形態によるプレシジョンとほとんど同じ値であるが、MSEAによるプレシジョンは、極めて低い値となる。一方、例えば、NCCの上限値UBについての閾値θ1をNCC値についての閾値θ0より大きい値にするとつまり、類似画像を正確にフィルタリングするのではなく、近似的にフィルタリングすると、リコールは100にならなくなるが、プレシジョンを高くすることができる。図11aは、本実施形態及び他の低次元変換方法においてリコールを100以下にしたときのリコールとプレシジョンの関係のグラフを示し、図11bは、その拡大図を示す。図11a、bに示すグラフ1100、1110では、他の低次元変換方法として、MSEAと、DCTと、正規化輝度ヒストグラム以下、NIHNormalizedintensityhistogramsと称するが用いられる。図12は、NIHを用いた低次元変換方法を説明するための概略図である。NIHを用いた低次元変換方法では、まず、各画像の正規化画像1200を2×2、3×3等のサブ領域1210に分割し、各サブ領域について、一定範囲毎に量子化した正規化輝度のヒストグラム1220を算出する。そして、式63に示すように、全てのサブ領域のヒストグラムの分布値aijiはサブ領域の番号、jは各ヒストグラムの量子化レベルの番号を順番に並べたベクトルがNIHによる低次元特徴量となる。この方法では、式64に示すように、各ヒストグラムの分布値がaij、bijである二つの画像の特徴ベクトルのユークリッド距離を求め、ユークリッド距離が2-2θ1以下となる二画像を類似画像として抽出する。また、この方法では、サブ領域の数と正規化輝度の量子化レベルを変更することにより、特徴量の次元数を変更することができる。例えば、サブ領域を2×2にし、正規化輝度の量子化を4レベルにした場合、特徴量の次元数は、2×2×4となる。NIHを用いて類似画像を抽出する場合、NCCの上限値は算出されないのでNCC値が閾値θ0以上になる画像のペアの集合IIPSに対するリコールは100とならないが、リコール及びプレシジョンが非常に高くなることが知られている。なお、図11に示すグラフ1100では、式64に示すユークリッド距離が2-2θ1以下となる画像のペアの集合をIIPSとし、NCC値がθ0以上の画像のペアの集合をIIPSとしてプレシジョン及びリコールを算出している。図11a、bに示すグラフ1100において、prop16D、prop64D、prop256D、prop1024Dのグラフは、本実施形態の低次元変換方法で特徴量次元数がそれぞれ16、64、256、1024のときのリコールとプレシジョンの関係を示す。また、DCT5D、DCT44D、DCT209Dのグラフは、DCTによる低次元変換方法で特徴量次元数がそれぞれ5、44、209のときのリコールとプレシジョンの関係を示す。また、NIH2×2×4、NIH4×4×4、NIH4×4×8のグラフは、NIHによる低次元変換方法で特徴量次元数がそれぞれ2×2×4、4×4×4、4×4×8のときのリコールとプレシジョンの関係を示す。また、MSEA16D、MSEA64D、MSEA512Dのグラフは、MSEAによる低次元変換方法で特徴量次元数がそれぞれ16、64、512のときのリコールとプレシジョンの関係を示す。グラフ1100、1110の横軸はリコールの値を示し、縦軸はプレシジョンの値を示す。図11a、bに示すように、本実施形態の低次元変換方法では、特徴量次元数が64と256の場合、リコールを97に保ちつつ、プレシジョンが70以上となる。特に、リコールが非常に高い95以上場合、DCT、NIH、MSEAよりプレシジョンが高くなる。図13aは、図11aとは異なる画像セットのペアそれぞれ、類似する放送映像から取得した1万画像についてのリコールとプレシジョンの関係のグラフを示し、図13bは、その拡大図を示す。図13a、bのグラフ1300、1310では、ほとんど全てのタイプで、図11a、bのグラフ1100、1110より高いリコールとプレシジョンの組合せが得られる。図13bに示すように、本実施形態の低次元変換方法で特徴量次元数が1024又は256のときに最も高いパフォーマンスが得られ、次いでMSEAによる低次元変換方法で特徴量次元数が512のとき、本実施形態の低次元変換方法で特徴量次元数が64又は16のとき、MSEAによる低次元変換方法で特徴量次元数が64のときの順に高いパフォーマンスが得られる。一方、DCTによる低次元変換方法では、あまり高いパフォーマンスが得られない。また、MSEAによる低次元変換方法で特徴量次元数が16の場合のパフォーマンスは、本実施形態の低次元変換方法で特徴量次元数が16の場合より非常に低くなる。つまり、本実施形態の低次元変換方法は、全ての特徴量次元数において、他の低次元変換方法より高いパフォーマンスを得ることができる。図14a、b、c、dは、それぞれリコールを0.95、0.97、0.98、0.99に固定したときの各低次元変換方法での特徴量次元数とプレシジョンの関係のグラフを示す。図14a、b、c、dに示すグラフ1400、1410、1420、1430において、それぞれ、グラフ1401、1411、1421、1431は本実施形態の低次元変換方法でのプレシジョンを示し、グラフ1402、1412、1422、1432はMSEAによる低次元変換方法でのプレシジョンを示し、グラフ1403、1413、1423、1433はDCTによる低次元変換方法でのプレシジョンを示し、グラフ1404、1414、1424、1434はNIHによる低次元変換方法でのプレシジョンを示す。グラフ1400~1430の横軸は特徴量次元数を示し、縦軸はプレシジョンを示す。図14a~dに示すように、リコールを非常に高い値にした場合、本実施形態の低次元変換方法でのプレシジョンは、他の低次元変換方法でのプレシジョンより高くなることが明らかである。図14dに示すように、リコールが0.99の場合、本実施形態の低次元変換方法では、DCTによる低次元変換方法よりわずかにパフォーマンスが低くなるが、この場合、そもそもプレシジョンが0.14以下であり、極めて低い。また、例えば、図14aに示すように、リコールが0.95の場合、本実施形態の低次元変換方法において、特徴量次元数が低い方が高いパフォーマンスを示している特徴量次元数が64、128、256の方が、特徴量次元数が512のときよりもプレシジョンが高い。類似した現象がMSEAでもみられる特徴量次元数が16、32、64の方が、特徴量次元数が128のときよりもプレシジョンが高い。これは、これらの方法が複数ブロックへ分割するものであるためと考えられる。そのため、リコールを100としない場合、適切なサイズのブロックに分割する必要がある。図14a~dから、本実施形態の低次元変換方法でのプレシジョンは、特徴量次元数が64のとき、すなわち、分割するブロック数が32のとき、最も高くなると考えられる。図15a~dは、図14a~dとは異なる画像セットのペアについて、それぞれリコールを0.95、0.97、0.98、0.99に固定したときの各低次元変換方法での特徴量次元数とプレシジョンの関係のグラフを示す。図15a、b、c、dに示すグラフ1500、1510、1520、1530において、それぞれ、グラフ1501、1511、1521、1531は本実施形態の低次元変換方法でのプレシジョンを示し、グラフ1502、1512、1522、1532はMSEAによる低次元変換方法でのプレシジョンを示し、グラフ1503、1513、1523、1533はDCTによる低次元変換方法でのプレシジョンを示し、グラフ1504、1514、1524、1534はNIHによる低次元変換方法でのプレシジョンを示す。グラフ1500~1530の横軸は特徴量次元数を示し、縦軸はプレシジョンを示す。図15a~dに示すグラフ1500~1530では、プレシジョンが比較的高くなっている。例えば、図15dでは、リコールが0.99に固定されているにも関わらず、プレシジョンは略0.6となる。図15a~cに示すように、リコールが比較的低い0.95~0.98場合、本実施形態の低次元変換方法とMSEAによる低次元変換方法はDCT及びNIHによる低次元変換方法よりパフォーマンスがよい。一方、図15dに示すように、リコールが高い0.99場合、本実施形態の低次元変換方法とDCT及びNIHによる低次元変換方法はMSEAによる低次元変換方法よりパフォーマンスが高い。つまり、全体として、本実施形態の低次元変換方法は他の低次元変換方法より高いパフォーマンスを得ることができる。以上、図9、図11a、b、図13a、b、図14a~d、図15a~dを用いて説明したように、本実施形態の低次元変換方法を用いることにより、他の低次元変換方法より高精度に類似性の高い画像を抽出することが可能となる。本実施形態の低次元変換方法では、ラグランジュの未定乗数決定法を用いてNCCの上限値を算出する。これにより、NCC値が上限値に近いとき、そのNCCの微分係数は非常に0に近くなり、上限値から離れているとき、微分係数は0から離れる。そのため、NCC値が上限値に近いリコールが高い場合、上限値をわずかに大きくしても、微分係数が0に近いのでリコールは大きく変化しない。一方、NCC値が上限値から離れている場合、微分係数は0から離れているので、プレシジョンは大幅に増加する。これにより、本実施形態の低次元変換方法では、リコールを高く保ちつつ、プレシジョンを高くできると考えられる。図16は、本実施形態による照合処理の時間を示す表である。図16の表1600は、それぞれ1万画像352×240画素からなる二つの画像セットにおいて、全ての画像ペアの組合せについて特徴ベクトルのユークリッド距離により全数照合したときの時間を示す。なお、この時間には、特徴ベクトルの算出時間は含まれない。表1600の行1610と行1630は低次元特徴量による照合処理を、行1620と行1640は低次元特徴量による照合処理及びそれにより抽出した類似画像のペアに対するNCCによる照合処理を示す。また、行1610と行1620ではリコールが100になるようにし低次元特徴量による照合処理における閾値θ1=NCCによる照合処理における閾値θ0=0.9、行1630と行1640ではリコールが95になるようにしているθ1>θ0。各行において、さらに特徴量の次元数毎に処理結果が示される。一方、列1650は特徴量次元数を、列1660はプレシジョンを、列1670はリコールを、列1680は処理時間秒をそれぞれ示す。行1610と行1630に示すように、照合処理時間は、概ね特徴量の次元数に比例している。これに基づくと、全ての画像ペアの組合せについてNCCによる照合処理つまり、352×240次元の演算を実施した場合、約40時間かかると考えられる。リコールが100の場合、行1610に示すようにプレシジョン値は比較的低くなり、類似画像として多くの画像が抽出されるため、行1620に示すようにNCCによる照合処理時間は非常に長くなる。一方、リコールが95の場合、行1630に示すようにプレシジョンが大幅に高くなるため、類似画像の抽出数が抑制され、行1640に示すようにNCCによる照合処理時間はあまり長くならない。従って、わずかにリコールを減少させる95のがリーズナブルであると考えられる。なお、上述したように、行1610と行1630の照合処理時間は、特徴量の次元数に応じて異なるものであり、本実施形態とMSEAとで差は生じない。また、1万画像352×240画素について、本実施形態に基づく低次元特徴量の算出時間とMSEAに基づく低次元特徴量の算出時間は、その次元数に関わらず、それぞれ、約35秒と約32秒であり、ほとんど差がなかった。つまり、次元数が同じ場合、本実施形態の低次元変換方法とMSEAによる低次元変換方法とで類似画像を抽出するのにかかる時間は、ほとんど同じとなる。一方、本実施形態の低次元変換方法では、MSEAによる低次元変換方法より、類似画像として抽出する画像のペアが少なくなるので、その後のNCCによる照合処理時間は短くなり、トータルの照合時間は短くなる。図17は、画像照合装置を画像符号化装置に適用する場合の例を示す概略構成図である。図17に示す画像照合装置2は、図1に示す画像照合装置1の各部に加えて画像入力部53を有する。また、画像照合装置2の制御部60は、インテグラル画像生成部61、符号化処理部62、画像分割部63、特徴ベクトル算出部64、上限値算出部65、第1照合部66、NCC値算出部67及び第2照合部68を有する。なお、画像分割部63は、図1に示す第1画像分割部22と第2画像分割部25の機能を備え、特徴ベクトル算出部64は、図1に示す第1特徴ベクトル算出部23と第2特徴ベクトル算出部26の機能を備える。画像入力部53は、CCD、CMOS等の光電変換器で構成された2次元検出器と、その2次元検出器上に撮影対象の像を結像する結像光学系等を有する。画像入力部53は、一定の時間間隔例えば1/30秒毎に撮影を行い、撮影画像を、例えば352×240画素のデジタル画像に変換し、そのデジタル画像を記憶部52に記憶する。図18は、図17に示す画像照合装置2による画像の符号化処理の動作を示すフローチャートである。以下、図18に示したフローチャートを参照しつつ、画像符号化処理の動作を説明する。なお、以下に説明する動作のフローは、予め記憶部52に記憶されているプログラムに基づき主に制御部60により画像照合装置2の各要素と協同して実行される。最初に、画像入力部53は、撮影対象を撮影した画像をデジタル画像に変換し、そのデジタル画像を記憶部52に記憶するステップS1801。次に、インテグラル画像生成部61は、記憶部12に保存されたデジタル画像を読み出し、インテグラル画像を生成し、記憶部52に記憶するステップS1802。デジタル画像及びインテグラル画像の水平方向をx軸、垂直方向をy軸とし、デジタル画像の座標a、bにおける正規化画素値をIa、bとする。インテグラル画像生成部67は、各画素が式65、66からなるインテグラル画像ViolaPJonesMMay2004RobustrealtimefacedetectionInternationalJournalofComputerVision57137154をそれぞれ生成する。つまり、式65により算出されるインテグラル画像の各画素値は、原点からその画素までの全ての画素の正規化画素値の総和であり、式66により算出されるインテグラル画像の各画素値は、原点からその画素までの全ての画素の正規化画素値の二乗和である。図19は、インテグラル画像を説明するための概略図である。例えば、インテグラル画像1900において、座標x1、y1、x1、y2、x2、y1、x2、y2で囲まれた領域Dの正規化画素値の総和と正規化画素値の二乗和は、それぞれ、式67、68により算出することができる。従って、予めインテグラル画像を作成しておくことにより、所定領域内の正規化画素値の総和と二乗和の算出処理を高速化できるので、特徴ベクトルの算出を高速化できる。次に、符号化処理部62は、記憶部12に保存されたデジタル画像を読み出し、デジタル画像のフォーマット画素数変換、8×8画素、16×16画素等の符号化ブロックへの分割等の符号化前処理を実施するステップS1803。以下のステップS1804~S1814の処理は、符号化ブロック毎に実施される。まず、画像分割部63は、符号化ブロックをさらに所定サイズの複数のブロックに分割するステップS1804。例えば、画像分割部63は、16×16画素の画像を4×4画素の16ブロックに分割する。次に、特徴ベクトル算出部64は、インテグラル画像を用いて、符号化ブロックについて、式37に示す特徴ベクトルを算出し、符号化ブロックと関連付けて記憶部12に保存するステップS1805。次に、上限値算出部65は、記憶部12から照合元ブロックの特徴ベクトルを取得するステップS1806。この照合元ブロックは、例えば、1フレーム前のデジタル画像における各符号化ブロックである。なお、前方向予測だけでなく、後方向予測も用いる場合、上限値算出部65は、1フレーム後のデジタル画像における各符号化ブロックも照合元ブロックとして用いる。次に、上限値算出部65は、符号化ブロックの特徴ベクトルと照合元ブロックの特徴ベクトルの内積を算出して、符号化ブロックと照合元ブロックについて、NCCの上限値UBを求めるステップS1807。次に、第1照合部66は、符号化ブロックと照合元ブロックについての上限値UBが閾値θ1以上であるか否かを判定するステップS1808。上限値UBが閾値θ1以上である場合、第1照合部65は、その照合元ブロックを符号化ブロックと類似すると判定し、NCC値算出部67は、その符号化ブロックと照合元ブロックについてNCC値を算出するステップS1809。次に、第2照合部68は、NCC値算出部67が算出したNCC値がその符号化ブロックについて算出されたNCC値のうち最大であるか否かを判定するステップS1810。NCC値算出部67が算出したNCC値がその符号化ブロックについて算出されたNCC値のうち最大である場合、第2照合部68は、その照合元ブロックを動き検出用ブロックとして記憶部52に記憶すでに記憶されている場合、更新するステップS1811。一方、上限値UBが閾値θ1未満である場合、NCC値算出部67が算出したNCC値がその符号化ブロックについて算出されたNCC値のうち最大でない場合、又は、第2照合部68が照合元ブロックを動き検出用ブロックとして記憶部52に記憶した場合、制御部60は、符号化ブロックを全ての照合元ブロックと比較したか否かを判定するステップS1812。制御部60は、まだ比較していない照合元ブロックがある場合、ステップS1807~S1811の処理を繰り返し、全ての照合元ブロックとの比較が完了すると、符号化処理部62は、記憶部52に記憶された動き検出用ブロックの候補を用いて動き補償を行う。また、符号化処理部62は、DCT変換、量子化等の符号化処理を実施するステップS1813。次に、制御部60は、全ての符号化ブロックの符号化処理が完了したか否かを判定するステップS1814。全ての符号化ブロックの符号化処理が完了していない場合、ステップS1803~S1813の処理を繰り返し、全ての符号化ブロックの符号化処理が完了すると、制御部60は、一連のステップを終了する。このようにして符号化されたデータは、インターフェース部51を介して、外部のデコード装置不図示に送信される。なお、第2照合部68は、符号化ブロックと全ての照合元ブロックについての上限値UBが閾値θ1未満であった場合は、その符号化ブロックに類似する照合元ブロックが存在しないと判断し、任意の照合元ブロックを動き検出用ブロックとして選択する。あるいは、その場合、上限値UBが最も高かった照合元ブロックを動き検出用ブロックとして選択してもよい。以上詳述したように、図18に示したフローチャートに従って動作することによって、画像照合装置2は、画像符号化装置として動作し、高速に動き検出処理を実施することが可能となった。また、インテグラル画像を用いて特徴量算出処理を高速化することが可能となった。また、本実施形態による方法は、スライディングウィンドウに基づく探索WeiSDLaiSH2007EfficientnormalizedcrosscorrelationbasedonadaptivemultilevelsuccessiveeliminationInProceedingsofthe8thAsianconferenceonComputervisionVolumePartIACCV’07SpringerVerlagBerlinHeidelbergpp638646とも親和性が高い。