TOP > 国内特許検索 > 画像照合装置、画像照合方法及びコンピュータプログラム > 明細書

明細書 :画像照合装置、画像照合方法及びコンピュータプログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5713398号 (P5713398)
公開番号 特開2013-016073 (P2013-016073A)
登録日 平成27年3月20日(2015.3.20)
発行日 平成27年5月7日(2015.5.7)
公開日 平成25年1月24日(2013.1.24)
発明の名称または考案の名称 画像照合装置、画像照合方法及びコンピュータプログラム
国際特許分類 G06T   7/00        (2006.01)
FI G06T 7/00 300F
請求項の数または発明の数 7
全頁数 39
出願番号 特願2011-149428 (P2011-149428)
出願日 平成23年7月5日(2011.7.5)
審査請求日 平成26年6月6日(2014.6.6)
特許権者または実用新案権者 【識別番号】504202472
【氏名又は名称】大学共同利用機関法人情報・システム研究機構
発明者または考案者 【氏名】佐藤 真一
個別代理人の代理人 【識別番号】100099759、【弁理士】、【氏名又は名称】青木 篤
【識別番号】100092624、【弁理士】、【氏名又は名称】鶴田 準一
【識別番号】100114018、【弁理士】、【氏名又は名称】南山 知広
【識別番号】100165191、【弁理士】、【氏名又は名称】河合 章
【識別番号】100133835、【弁理士】、【氏名又は名称】河野 努
審査官 【審査官】佐田 宏史
参考文献・文献 特開平9-330402(JP,A)
特開平11-296653(JP,A)
井上 光平、浦浜 喜一,“画像間相関の上限に基づくフィルタリング検索”,電子情報通信学会技術研究報告,日本,社団法人電子情報通信学会,2003年11月13日,Vol.103, No.450,p.23-28
調査した分野 G06T 1/00,7/00-7/60
特許請求の範囲 【請求項1】
第1画像を複数のブロックに分割し、第2画像を前記第1画像と同数のブロックに分割する画像分割部と、
前記第1画像及び前記第2画像のそれぞれについて、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、前記第1画像の特徴ベクトル及び前記第2画像の特徴ベクトルを算出する特徴ベクトル算出部と、
ラグランジュの未定乗算決定法を利用して2つの画像の正規化相互相関値を求める式から導いた2つの画像の正規化相互相関の上限値を算出する式を用いて、算出された前記第1画像の特徴ベクトル及び前記第2画像の特徴ベクトルに基づき、前記第1画像と前記第2画像の正規化相互相関の上限値を算出する上限値算出部と、
前記上限値が第1の閾値以上であるか否かに基づいて前記第1画像と前記第2画像を照合する第1照合部と、
を有することを特徴とする画像照合装置。
【請求項2】
前記特徴ベクトル算出部は、mを前記ブロック内の画素数、nを前記ブロックの数、φi,jを前記第1画像におけるi番目のブロック内のj番目の画素の画素値、φaveを前記第1画像の全画素の画素値の平均値として、次のベクトルξxを前記第1画像の特徴ベクトルとして算出し、
【数1】
JP0005713398B2_000070t.gif
ψi,jを前記第2画像におけるi番目のブロック内のj番目の画素の画素値、ψaveを前記第2画像の全ての画素の画素値の平均値として、次のベクトルξyを前記第2画像の特徴ベクトルとして算出し、
【数2】
JP0005713398B2_000071t.gif
前記上限値算出部は、前記第1画像の特徴ベクトルと前記第2画像の特徴ベクトルの内積を前記上限値として算出する、請求項1に記載の画像照合装置。
【請求項3】
前記上限値が前記第1の閾値以上である前記第1画像と前記第2画像の正規化相互相関値を算出する正規化相互相関値算出部と、
前記正規化相互相関値が前記第1の閾値以下の値である第2の閾値以上であるか否かに基づいて前記第1画像と前記第2画像を詳細に照合する第2照合部と、をさらに有する、請求項1または2に記載の画像照合装置。
【請求項4】
第1画像を複数のブロックに分割するステップと、
前記第1画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、前記第1画像の特徴ベクトルを算出するステップと、
第2画像を前記第1画像と同数のブロックに分割するステップと、
前記第2画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、前記第2画像の特徴ベクトルを算出するステップと、
ラグランジュの未定乗算決定法を利用して2つの画像の正規化相互相関値を求める式から導いた2つの画像の正規化相互相関の上限値を算出する式を用いて、算出された前記第1画像の特徴ベクトル及び前記第2画像の特徴ベクトルに基づき、前記第1画像と前記第2画像の正規化相互相関の上限値を算出するステップと、
前記上限値が第1の閾値以上であるか否かに基づいて前記第1画像と前記第2画像を照合するステップと、
を含むことを特徴とする画像照合方法。
【請求項5】
前記第1画像の特徴ベクトルを算出するステップにおいて、mを前記ブロック内の画素数、nを前記ブロックの数、φi,jを前記第1画像におけるi番目のブロック内のj番目の画素の画素値、φaveを前記第1画像の全画素の画素値の平均値として、次のベクトルξxを前記第1画像の特徴ベクトルとして算出し、
【数3】
JP0005713398B2_000072t.gif
前記第2画像の特徴ベクトルを算出するステップにおいて、mを前記ブロック内の画素数、nを前記ブロックの数、ψi,jを前記第2画像におけるi番目のブロック内のj番目の画素の画素値、ψaveを前記第2画像の全ての画素の画素値の平均値として、次のベクトルξyを前記第2画像の特徴ベクトルとして算出し、
【数4】
JP0005713398B2_000073t.gif
前記上限値を算出するステップにおいて、前記第1画像の特徴ベクトルと前記第2画像の特徴ベクトルの内積を前記上限値として算出する、請求項4に記載の画像照合方法。
【請求項6】
前記上限値が前記第1の閾値以上である前記第1画像と前記第2画像の正規化相互相関値を算出するステップと、
前記正規化相互相関値が前記第1の閾値以下の値である第2の閾値以上であるか否かに基づいて前記第1画像と前記第2画像を詳細に照合するステップと、をさらに有する、請求項4または5に記載の画像照合方法。
【請求項7】
第1画像を複数のブロックに分割するステップと、
前記第1画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、前記第1画像の特徴ベクトルを算出するステップと、
第2画像を前記第1画像と同数のブロックに分割するステップと、
前記第2画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、前記第2画像の特徴ベクトルを算出するステップと、
ラグランジュの未定乗算決定法を利用して2つの画像の正規化相互相関値を求める式から導いた2つの画像の正規化相互相関の上限値を算出する式を用いて、算出された前記第1画像の特徴ベクトル及び前記第2画像の特徴ベクトルに基づき、前記第1画像と前記第2画像の正規化相互相関の上限値を算出するステップと、
前記上限値が第1の閾値以上であるか否かに基づいて前記第1画像と前記第2画像を照合するステップと、
をコンピュータに実行させることを特徴とするコンピュータプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、画像照合装置、画像照合方法及びコンピュータプログラムに関し、特に、二つの画像が類似するか否かを判定する画像照合装置、画像照合方法及びコンピュータプログラムに関する。
【背景技術】
【0002】
画像照合技術は、テンプレートマッチング、ブロック動き補償、画像圧縮、ステレオビジョン等の、多くの画像を用いたアプリケーションにおける重要な技術の一つである。最近は、画像の近似コピー検出、画像マイニング及びその画像アノテーションへの応用等、大規模な画像/映像データベースにおける画像照合技術の新しいアプリケーションについても研究が開始されている。
【0003】
一般に、画像照合の方法として、画素値の差の絶対値の合計(SAD:Sum of Absolute Difference)、画素値の差の二乗の合計(SSD:Sum of Squared Difference)、正規化相互相関(NCC:Normalized Cross-Correlation)等が用いられている。特に、NCCは、画像間の輝度のずれ、コントラストの違い等による影響が少なく、輝度の補正等がなされた画像間の照合にも適している。例えば、水平方向をx軸、垂直方向をy軸とする画像I1と画像I2についてのNCC値は、式(1)で定義される。
【数1】
JP0005713398B2_000002t.gif
ここで、φx,yは画像I1の座標(x、y)の画素の画素値であり、ψx,yは画像I2の座標(x、y)の画素の画素値であり、φaveは画像I1の全画素の画素値の平均値であり、ψaveは画像I2の全画素の画素値の平均値である。式(1)に示すように、NCC値を算出するためには、対応する画素毎に画素値の相関を計算する必要があるため、特に、照合する画像のサイズが大きい場合には、計算量が大きくなり、算出処理に多大な時間が必要となる。
【0004】
そこで、例えば、非特許文献1には、NCCに基づくテンプレートマッチング処理を高速化するための技術が開示されている。非特許文献1に開示された技術は、画像全体に対してテンプレートをずらしながらスキャンする場合、畳み込み演算を用いて各位置での照合結果を求める。一方、空間領域間の畳み込み演算は、周波数領域間での単純な掛け算に変換できるので、空間領域のデータを高速フーリエ変換(FFT:Fast Fourie Transform)を用いて周波数領域に変換することにより処理を高速化できる。しかし、この技術はある画像に対してテンプレートをスキャンする場合には効果的であるが、複数の画像に対して照合をする場合は各画像に対してFFT及び逆FFTを行う必要があり、かえって処理が遅くなるおそれがある。
【0005】
一方、非特許文献2には、NCCの演算処理を効率化するための技術として、MSEA(multilevel successive elimination algorithm)が開示されている。非特許文献2に開示された技術では、式(2)に示すCauchy-Schwarzの不等式に基づいてNCCの上限値が算出される。
【数2】
JP0005713398B2_000003t.gif

【0006】
画像I1と画像I2についてブロック内画素数がmである、n個のブロックに分割した場合、式(1)のNCC値は、ブロックの番号i(1≦i≦n)及びブロック内の画素の番号j(1≦j≦m)を用いて式(3)で表される。
【数3】
JP0005713398B2_000004t.gif
ここで、xi,j及びyi,jは各画素の正規化画素値であり、式(4)で定義される。
【数4】
JP0005713398B2_000005t.gif
式(2)、(3)から、NCCの上限値UBMSEAは、式(5)で表される。
【数5】
JP0005713398B2_000006t.gif
ここで、XXi及びYYiは式(6)で定義される。
【数6】
JP0005713398B2_000007t.gif
NCC値はこの上限値UBMSEAを越えることがないので、NCC値の代わりに、NCC値よりも簡易に算出できる上限値UBMSEAを用いて二つの画像の類似性を評価することができる。
【先行技術文献】
【0007】

【非特許文献1】Tsai, D.-M., Lin, C.-T., 2003. Fast normalized cross correlation for defect detection. Pattern Recognition Letters 24 (15), 2625-2631.
【非特許文献2】Wei, S.-D., Lai, S.-H., 2007. Efficient normalized cross correlation based on adaptive multilevel successive elimination. In: Proceedings of the 8th Asian conference on Computer vision - Volume Part I. ACCV’07. Springer-Verlag, Berlin, Heidelberg, pp. 638-646
【発明の概要】
【発明が解決しようとする課題】
【0008】
非特許文献2に開示された技術を用いることにより、高速に画像照合を実施することができる。しかしながら、非特許文献2に開示されたNCCの上限値は、NCC値より大きくなりすぎる場合がある。その場合、照合する二画像のNCC値が低いにも関わらず、その二画像の類似性が高いと判定するおそれがあった。
【0009】
そこで、本発明の目的は、画像照合を高速に実施するとともに、画像の類似性を高精度に判定することが可能な画像照合装置、画像照合方法及びそのような画像照合方法をコンピュータに実行させるコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【0010】
本発明に係る画像照合装置は、第1画像を複数のブロックに分割し、第2画像を第1画像と同数のブロックに分割する画像分割部と、第1画像及び第2画像のそれぞれについて、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、第1画像の特徴ベクトル及び第2画像の特徴ベクトルを算出する特徴ベクトル算出部と、ラグランジュの未定乗算決定法を利用して2つの画像の正規化相互相関値を求める式から導いた2つの画像の正規化相互相関の上限値を算出する式を用いて、算出された第1画像の特徴ベクトル及び第2画像の特徴ベクトルに基づき、第1画像と第2画像の正規化相互相関の上限値を算出する上限値算出部と、上限値が第1の閾値以上であるか否かに基づいて第1画像と第2画像を照合する第1照合部と、を有する。
【0011】
さらに、本発明に係る画像照合装置において、特徴ベクトル算出部は、mをブロック内の画素数、nをブロックの数、φi,jを第1画像におけるi番目のブロック内のj番目の画素の画素値、φaveを第1画像の全画素の画素値の平均値として、次のベクトルξxを第1画像の特徴ベクトルとして算出し、
【数7】
JP0005713398B2_000008t.gif
ψi,jを第2画像におけるi番目のブロック内のj番目の画素の画素値、ψaveを第2画像の全ての画素の画素値の平均値として、次のベクトルξyを第2画像の特徴ベクトルとして算出し、
【数8】
JP0005713398B2_000009t.gif
上限値算出部は、第1画像の特徴ベクトルと第2画像の特徴ベクトルの内積を上限値として算出することが好ましい。
【0012】
さらに、本発明に係る画像照合装置において、上限値が第1の閾値以上である第1画像と第2画像の正規化相互相関値を算出する正規化相互相関値算出部と、正規化相互相関値が第1の閾値以下の値である第2の閾値以上であるか否かに基づいて第1画像と第2画像を詳細に照合する第2照合部と、をさらに有することが好ましい。
【0013】
また、本発明に係る画像照合方法は、第1画像を複数のブロックに分割するステップと、第1画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、第1画像の特徴ベクトルを算出するステップと、第2画像を第1画像と同数のブロックに分割するステップと、第2画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、第2画像の特徴ベクトルを算出するステップと、ラグランジュの未定乗算決定法を利用して2つの画像の正規化相互相関値を求める式から導いた2つの画像の正規化相互相関の上限値を算出する式を用いて、算出された第1画像の特徴ベクトル及び第2画像の特徴ベクトルに基づき、第1画像と第2画像の正規化相互相関の上限値を算出するステップと、上限値が第1の閾値以上であるか否かに基づいて第1画像と第2画像を照合するステップと、を含む。
【0014】
さらに、本発明に係る画像照合方法において、第1画像の特徴ベクトルを算出するステップにおいて、mをブロック内の画素数、nをブロックの数、φi,jを第1画像におけるi番目のブロック内のj番目の画素の画素値、φaveを第1画像の全画素の画素値の平均値として、次のベクトルξxを第1画像の特徴ベクトルとして算出し、
【数9】
JP0005713398B2_000010t.gif
第2画像の特徴ベクトルを算出するステップにおいて、mをブロック内の画素数、nをブロックの数、ψi,jを第2画像におけるi番目のブロック内のj番目の画素の画素値、ψaveを第2画像の全ての画素の画素値の平均値として、次のベクトルξyを第2画像の特徴ベクトルとして算出し、
【数10】
JP0005713398B2_000011t.gif
上限値を算出するステップにおいて、第1画像の特徴ベクトルと第2画像の特徴ベクトルの内積を上限値として算出することが好ましい。
【0015】
さらに、本発明に係る画像照合方法において、上限値が第1の閾値以上である第1画像と第2画像の正規化相互相関値を算出するステップと、正規化相互相関値が第1の閾値以下の値である第2の閾値以上であるか否かに基づいて第1画像と第2画像を詳細に照合するステップと、をさらに有することが好ましい。
【0016】
また、本発明に係るコンピュータプログラムは、第1画像を複数のブロックに分割するステップと、第1画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、第1画像の特徴ベクトルを算出するステップと、第2画像を第1画像と同数のブロックに分割するステップと、第2画像について、各ブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づき、第2画像の特徴ベクトルを算出するステップと、ラグランジュの未定乗算決定法を利用して2つの画像の正規化相互相関値を求める式から導いた2つの画像の正規化相互相関の上限値を算出する式を用いて、算出された第1画像の特徴ベクトル及び第2画像の特徴ベクトルに基づき、第1画像と第2画像の正規化相互相関の上限値を算出するステップと、上限値が第1の閾値以上であるか否かに基づいて第1画像と第2画像を照合するステップと、をコンピュータに実行させる。
【発明の効果】
【0017】
本発明によれば、画像照合を高速に実施するとともに、画像の類似性を高精度に判定することが可能な画像照合装置、画像照合方法及びそのような画像照合方法をコンピュータに実行させるコンピュータプログラムを提供することができる。
【図面の簡単な説明】
【0018】
【図1】本発明を適用した画像照合装置の概略構成図である。
【図2】画像照合処理の動作を示すフローチャートである。
【図3】ブロック毎に分割した画像の例である。
【図4】制御部の他の例を示す概略構成図である。
【図5】詳細な画像照合処理の動作を示すフローチャートである。
【図6】制御部の他の例を示す概略構成図である。
【図7】画像の取得処理の動作を示すフローチャートである。
【図8】画像の照合処理の動作を示すフローチャートである。
【図9】特徴量次元数毎のプレシジョンを表すグラフである。
【図10】DCTを用いた低次元特徴量を説明するための概略図である。
【図11】(a)、(b)は、リコールとプレシジョンの関係のグラフである。
【図12】NIHを用いた低次元特徴量を説明するための概略図である。
【図13】(a)、(b)は、リコールとプレシジョンの関係のグラフである。
【図14】(a)~(d)は、特徴量次元数毎のプレシジョンを表すグラフである。
【図15】(a)~(d)は、特徴量次元数毎のプレシジョンを表すグラフである。
【図16】特徴量次元数毎の照合処理時間を示す表である。
【図17】画像照合装置の他の例を示す概略構成図である。
【図18】画像の符号化処理の動作を示すフローチャートである。
【図19】インテグラル画像を説明するための概略図である。
【発明を実施するための形態】
【0019】
以下、本発明に係る画像照合装置、画像照合方法及びコンピュータプログラムについて図を参照しつつ説明する。但し、本発明の技術的範囲はそれらの実施の形態に限定されず、特許請求の範囲に記載された発明とその均等物に及ぶ点に留意されたい。

【0020】
図1は、本発明を適用した画像照合装置の概略構成を示す図である。図1に示すように、画像照合装置1は、インターフェース部11、記憶部12、表示部13及び制御部20を有する。以下、画像照合装置1の各部について詳細に説明する。

【0021】
インターフェース部11は、例えばインターネット、電話回線網(携帯端末回線網、一般電話回線網を含む)、イントラネット等のネットワークを介して他のコンピュータ等と画像データ及び各種のデータを送受信する通信インターフェースであり、接続するネットワークの通信インターフェース回路を有する。また、インターフェース部11は、例えばUSB等のシリアルバスに準じるインターフェース回路を有し、フラッシュメモリ等を接続し、そのフラッシュメモリ等から画像データ及び各種のデータを取得するようにしてもよい。インターフェース部11は、制御部20と接続されており、制御部20により制御される。

【0022】
記憶部12は、RAM、ROM等のメモリ装置、ハードディスク等の固定ディスク装置、又はフレキシブルディスク、光ディスク等の可搬用の記憶装置等を有する。また、記憶部12には、画像照合装置1の各種処理に用いられるコンピュータプログラム、データベース、テーブル等が格納される。記憶部12は、制御部20と接続され、インターフェース部11を介して取得した画像データを格納するとともに、制御部20により画像データについてなされた演算結果を格納する。

【0023】
制御部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は、集積回路、マイクロプロセッサ、ファームウェア等で構成されてもよい。

【0024】
図2は、画像照合装置1による画像照合処理の動作を示すフローチャートである。以下、図2に示したフローチャートを参照しつつ、画像照合処理の動作を説明する。なお、以下に説明する動作のフローは、予め記憶部12に記憶されているプログラムに基づき主に制御部20により画像照合装置1の各要素と協同して実行される。

【0025】
最初に、第1画像取得部21は、インターフェース部11を介して、外部のコンピュータ、フラッシュメモリ等から画像を取得し(以下、第1画像取得部21が取得した画像を第1画像と称する)、記憶部12に保存する(ステップS201)。

【0026】
次に、第1画像分割部22は、記憶部12に保存された第1画像を読み出し、第1画像を所定サイズの複数のブロックに分割する(ステップS202)。例えば、第1画像分割部22は、352×240画素の画像を22×15画素の256ブロックに分割する。

【0027】
図3は、ブロック毎に分割した画像の例を示す模式図である。図3の例では、画像300を、各ブロックの画素数がmであるn個のブロックに分割した画像310を示す。

【0028】
次に、第1特徴ベクトル算出部23は、第1画像について、分割したブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づく特徴ベクトルを算出し、第1画像と関連付けて記憶部12に保存する(ステップS203)。

【0029】
画像x、画像yについてブロック内画素数がmである、n個のブロックに分割した場合のNCC値を、ブロックの番号i(1≦i≦n)及びブロック内の画素の番号j(1≦j≦m)を用いて式(11)で定義する。
【数11】
JP0005713398B2_000012t.gif
ここで、φi,j、ψi,jは、各画素の画素値であり、φaveは画像xの全画素の画素値の平均値であり、ψaveは画像yの全画素の画素値の平均値である。

【0030】
画像x及び画像yの各画素の正規化画素値xi,j及びyi,jを式(12)で定義する。
【数12】
JP0005713398B2_000013t.gif
なお、正規化画素値は、厳密には式(13)とすべきであるが、本実施形態では単純化のため正規化画素値を式(12)で定義する。
【数13】
JP0005713398B2_000014t.gif

【0031】
式(11)のNCC値は、式(12)の正規化画素値xi,j及びyi,jを用いて式(14)で表される。
【数14】
JP0005713398B2_000015t.gif

【0032】
また、画像xのi番目のグループにおける正規化画素値xi,jの総和及び二乗和並びに画像yのi番目のグループにおける正規化画素値yi,jの総和及び二乗和を式(15)~(18)で定義する。
【数15】
JP0005713398B2_000016t.gif
【数16】
JP0005713398B2_000017t.gif
【数17】
JP0005713398B2_000018t.gif
【数18】
JP0005713398B2_000019t.gif
ここで、正規化画素値の性質上、式(19)、(20)が成り立つ。
【数19】
JP0005713398B2_000020t.gif
【数20】
JP0005713398B2_000021t.gif

【0033】
以下、ラグランジュの未定乗数決定法を利用して式(14)から2つの画像のNCCの厳密な上限値を算出する式を求める。本実施形態では、式(21)の関数の極値問題を考える。
【数21】
JP0005713398B2_000022t.gif
ここで、λ1,i、λ2,i、λ3,i、λ4,iは、4n個のラグランジュ未定乗数である。式(21)において、微分係数dΛ=0(全てのi、jについて∂Λ/∂xi,j=0、∂Λ/∂yi,j=0)とすることにより、式(22)、(23)の2mn個の式が得られる。
【数22】
JP0005713398B2_000023t.gif
【数23】
JP0005713398B2_000024t.gif
式(22)、(23)から式(24)が得られる。
【数24】
JP0005713398B2_000025t.gif

【0034】
ここで、式(24)が成立すると仮定すると、xi,j、yi,jは式(25)で求められる。
【数25】
JP0005713398B2_000026t.gif
この場合、式(25)の右辺はi(ブロックの番号)のみにより定まるので、xi,j、yi,jは全てのj(ブロック内の画素)について同一の値をとることになり、条件が強すぎることになる。一方、式(24)が成立しないと仮定すると、式(24)の左辺の行列の行列式から式(26)が得られる。
【数26】
JP0005713398B2_000027t.gif
また、式(22)、(23)、(26)から、式(27)が得られる。
【数27】
JP0005713398B2_000028t.gif
この場合、式(22)と式(23)は、同じ意味を表すことになる。従って、本実施形態では、式(22)のみを用いてNCCの上限値を算出する式を求める。

【0035】
まず、式(22)から式(28)が得られる。
【数28】
JP0005713398B2_000029t.gif
式(28)を式(17)に代入することにより、式(29)が得られる。
【数29】
JP0005713398B2_000030t.gif
一方、式(28)を式(18)に代入することにより、式(30)が得られる。
【数30】
JP0005713398B2_000031t.gif
式(29)より、式(31)が得られる。
【数31】
JP0005713398B2_000032t.gif
式(31)を式(30)に代入することにより、式(32)が得られる。
【数32】
JP0005713398B2_000033t.gif
式(28)、(31)、(32)を式(14)に代入することにより、式(33)が得られる。
【数33】
JP0005713398B2_000034t.gif

【0036】
つまり、NCCの上限値UBは式(34)で与えられ、NCCの下限値LBは式(35)で与えられる。
【数34】
JP0005713398B2_000035t.gif
【数35】
JP0005713398B2_000036t.gif
NCC値はこの上限値UBを越えることがないので、NCC値の代わりに上限値UBを用いて画像xと画像yの類似性を評価することができる。

【0037】
一方、式(34)の上限値UBは、式(36)に示されるように、式(37)、(38)で示される特徴ベクトルξxとξyの内積となる。
【数36】
JP0005713398B2_000037t.gif
【数37】
JP0005713398B2_000038t.gif
【数38】
JP0005713398B2_000039t.gif
式(37)、(38)に示されるように、特徴ベクトルξx及びξyは、それぞれ画像x、画像yのみから算出することができる。つまり、画像照合装置1は、予め画像x、画像yをそれぞれ2n個の要素をもつ特徴ベクトルξx及びξyに変換しておくことにより、その内積を算出して上限値UBを求めることができ、特に、ある画像を複数の画像と照合するときに高速に照合することができる。そこで、第1特徴ベクトル算出部23は、第1画像の特徴ベクトルとして第1画像について式(37)の特徴ベクトルξxを算出する。

【0038】
次に、第2画像取得部24は、インターフェース部11を介して、外部のコンピュータ、フラッシュメモリ等から画像を取得し(以下、第2画像取得部24が取得した画像を第2画像と称する)、記憶部12に保存する(ステップS204)。

【0039】
次に、第2画像分割部25は、記憶部12に保存された第2画像を読み出し、第1画像を分割したブロックとそれぞれ同サイズ、同数の複数のブロックに分割する(ステップS205)。

【0040】
次に、第2特徴ベクトル算出部26は、第2画像について、分割したブロックに含まれる画素の正規化画素値の総和及び各ブロックに含まれる画素の正規化画素値の二乗和に基づく特徴ベクトル、つまり式(38)の特徴ベクトルξyを算出し、第2画像と関連付けて記憶部12に保存する(ステップS206)。

【0041】
次に、上限値算出部27は、式(36)に示すように特徴ベクトルξx、ξyの内積を算出して、上限値UBを求める(ステップS207)。

【0042】
次に、第1照合部28は、上限値UBが所定の閾値θ1以上であるか否かに基づいて第1画像と前記第2画像を照合する。まず、第1照合部28は、上限値UBが閾値θ1以上であるか否かを判定する(ステップS208)。この閾値θ1は、NCCを用いて二つの画像が類似するか否かを判定するときに、NCC値と比較する閾値θ0(-1≪θ0<1)と同じ値である。あるいは、閾値θ1は、閾値θ0より大きい値としてもよい。

【0043】
第1照合部28は、上限値UBが閾値θ1以上である場合、第1画像が第2画像と類似すると判定し(ステップS209)、一連のステップを終了する。一方、第1照合部28は、上限値UBが閾値θ1未満である場合、第1画像が第2画像と類似しないと判定し(ステップS210)、一連のステップを終了する。

【0044】
例えば、画像照合装置1は、類似すると判定した画像のペアを利用者が確認できるように、表示部13に表示する。あるいは、画像照合装置1は、類似すると判定した画像のペアの情報をインターフェース部11を介して外部のコンピュータ(不図示)に通知してもよい。

【0045】
なお、上限値UBと下限値LBの間の範囲が狭いほど、上限値UBは、NCC値をより正確に近似していることになる。上限値UBと下限値LBの間の範囲は、式(34)、(35)から、式(39)により求めることができる。
【数39】
JP0005713398B2_000040t.gif
一方、
【数40】
JP0005713398B2_000041t.gif
であり、ここで、Gj,k=xi,ji,j-xi,ji,kとすると、式(41)が成り立つ。
【数41】
JP0005713398B2_000042t.gif
従って、式(40)は、式(42)で表される。
【数42】
JP0005713398B2_000043t.gif
ここで、Ekはkにわたる期待値であり、Vari(xi,j)はi番目のブロック内のxi,jの分散である。同様に、
【数43】
JP0005713398B2_000044t.gif
が成立し、式(39)は、式(44)で表される。
【数44】
JP0005713398B2_000045t.gif

【0046】
つまり、上限値UBと下限値LBの間の範囲を狭くするためには、各ブロック内部の正規化画素値の分散を小さくするか、一ブロック内の画素数mを小さくする必要がある。しかし、一ブロック内の画素数mを小さくすると、ブロック数nが大きくなり、特徴ベクトルξxとξyの次元数が大きくなるため、現実的でない。従って、同一ブロック内の画素の間の正規化画素値の差が可能な限り小さくなるように各ブロックを構成し、各ブロック内部の正規化画素値の分散を小さくすることが好ましい。一般に、画像のマルコフ性により、近傍の画素の(正規化)画素値は、非常に近い値をもつことが知られている。従って、例えばブロックの形状を、長方形、特に正方形に近い形にすることにより、各ブロック内の画素の画素値を近付け、上限値UBをよりNCC値に近似させることができる。

【0047】
なお、MSEAにより算出されるNCCの上限値UBMSEAは、式(5)から式(45)のように表される。
【数45】
JP0005713398B2_000046t.gif
本実施形態により算出されるNCCの上限値UBと、MSEAにより算出されるNCCの上限値UBMSEAについて、式(34)と式(45)のルート内の式を比較することにより式(46)が成立する。
【数46】
JP0005713398B2_000047t.gif
従って、式(47)が成立し、本実施形態により算出されるNCCの上限値UBは、MSEAにより算出されるNCCの上限値UBMSEA以下となる。
【数47】
JP0005713398B2_000048t.gif
つまり、本実施形態により算出されるNCCの上限値UBは、MSEAにより算出されるNCCの上限値UBMSEAより正確にNCC値を近似していることが理論的に示される。

【0048】
以上詳述したように、図2に示したフローチャートに従って動作することによって、画像照合装置1は、元の情報量(数万程度の画素数)から大幅に圧縮した(数十~百程度の)特徴ベクトル(すなわち低次元特徴量)を用いて、画像の類似性を高速かつ高精度に判定することが可能となった。

【0049】
なお、画像照合装置1は、照合する二画像のサイズが異なる場合、二画像のサイズを同一サイズに正規化することにより、サイズの異なる二画像についても低次元特徴量を用いた画像照合をすることができる。

【0050】
図4は、制御部の他の例を示す概略構成図である。図4に示す制御部30は、図1に示す制御部20の代わりに用いることが可能である。図4に示す制御部30は、図1に示す制御部20の各部に加えて、NCC値算出部31と第2照合部32を有する。

【0051】
図5は、図4に示す制御部30を用いる画像照合装置1による詳細な画像照合処理の動作を示すフローチャートである。以下、図5に示したフローチャートを参照しつつ、詳細な画像照合処理の動作を説明する。なお、以下に説明する動作のフローは、予め記憶部12に記憶されているプログラムに基づき主に制御部30により画像照合装置1の各要素と協同して実行される。また、図5に示したフローチャートは、図2に示したフローチャートにより、類似すると判定された画像のペアに対して実行される。

【0052】
最初に、NCC値算出部31は、類似すると判定された第1画像と第2画像について式(11)を用いてNCC値を算出する(ステップS501)。

【0053】
次に、第2照合部32は、NCC値算出部31により算出されたNCC値が所定の閾値θ0(例えば0.9)以上であるか否かに基づいて第1画像と第2画像を詳細に照合する。まず、第2照合部32は、NCC値が閾値θ0以上であるか否かを判定する(ステップS502)。なお、上述した通り、この閾値θ0は閾値θ1以下の値の閾値である。

【0054】
第2照合部32は、NCC値が閾値θ0以上である場合、第1画像と第2画像は類似すると判定し(ステップS503)、一連のステップを終了する。一方、第2照合部23は、NCC値が閾値θ0未満である場合、第1画像と第2画像は類似しないと判定し(ステップS504)、一連のステップを終了する。

【0055】
例えば、画像照合装置1は、図5に示したフローチャートにより類似すると判定した画像のペアを表示部13に表示する。あるいは、画像照合装置1は、図5に示したフローチャートにより類似すると判定した画像のペアの情報をインターフェース部11を介して外部のコンピュータ(不図示)に通知してもよい。

【0056】
なお、制御部20は、第1画像取得部21と第2画像取得部24の代わりに、第1画像及び第2画像の何れをも取得できる画像取得部を備えることもできる。また、第1画像分割部22と第2画像分割部25の代わりに第1画像及び第2画像の何れをも所定のブロックに分割できる画像分割部を備えることもできる。さらに、第1特徴ベクトル算出部23と第2特徴ベクトル算出部26の代わりに第1画像の特徴ベクトル及び第2画像の特徴ベクトルの何れをも算出できる特徴ベクトル算出部を備えることもできる。

【0057】
また、ステップS204~S206の第2画像に対する処理は、ステップS201~S203の第1画像に対する処理より前に実施してもよい。また、画像照合装置1が複数のCPUを備えること等により、並列処理が可能な場合には、ステップS204~S206の第2画像に対する処理と、ステップS201~S203の第1画像に対する処理を並列に実施してもよい。

【0058】
以上詳述したように、図5に示したフローチャートに従って動作することによって、画像照合装置1は、低次元空間での類似性が高い(NCCの上限値UBが閾値θ1以上の)画像のペアのうち、オリジナル空間での類似性が低い(NCC値が閾値θ0未満の)画像のペアを取り除く(クレンジングする)ことができる。これにより、画像照合装置1は、ある画像のペアに対して低負荷で類似性を判定しておき、その判定において類似性が高いと判定した画像のペアのみについて高負荷で高精度に類似性を判定するので、効率よく画像を照合できるようになった。

【0059】
図6は、画像照合装置を画像検索サーバに適用する場合の制御部の概略構成図である。図6に示す制御部40は、図1に示す制御部20又は図4に示す制御部30の代わりに用いることが可能である。図6に示す制御部40は、図4に示す制御部30の各部に加えて、インデックス判定部41を有する。なお、以下では、第1画像を事前に記憶部12に格納された照合元の画像とし、第2画像を外部のコンピュータ(不図示)等から検索を要求された問合せ画像として説明する。

【0060】
図7は、図6に示す制御部40を用いる画像照合装置1による画像の取得処理の動作を示すフローチャートである。以下、図7に示したフローチャートを参照しつつ、画像取得処理の動作を説明する。なお、以下に説明する動作のフローは、予め記憶部12に記憶されているプログラムに基づき主に制御部40により画像照合装置1の各要素と協同して実行される。

【0061】
図7に示すフローチャートでは、画像照合装置1は、第1画像の取得のみを実施し、第1画像と第2画像の照合処理は、後述するフローチャートで説明する。図7に示すステップS701~S703の処理は、図2に示すステップS201~S203の処理と同じであるため、説明を省略する。

【0062】
第1特徴ベクトル算出部23は、第1画像について特徴ベクトルを算出すると、算出した特徴ベクトルに基づいて多次元インデックスを作成する(ステップS704)。

【0063】
式(48)、(49)に示すように、式(37)、(38)で求められる特徴ベクトルξx、ξyのノルムは1になる。
【数48】
JP0005713398B2_000049t.gif
【数49】
JP0005713398B2_000050t.gif
つまり、式(50)に示すように、特徴ベクトルξxとξyの内積は、特徴ベクトルξxとξyのユークリッド距離に変換することができる。
【数50】
JP0005713398B2_000051t.gif
つまり、特徴ベクトルξxとξyのユークリッド距離が式(51)の条件を満たす場合、特徴ベクトルξxとξyの内積は閾値θ1以上となり、NCCの上限値UBは閾値θ1以上となる。
【数51】
JP0005713398B2_000052t.gif

【0064】
従って、画像照合装置1は、特徴ベクトルξxとξyの内積を算出する代わりに、特徴ベクトルξxとξyのユークリッド空間における距離探索を行うことにより、式(52)の条件を満たす画像のペアを抽出することができる。
【数52】
JP0005713398B2_000053t.gif

【0065】
この場合、画像照合装置1は、ユークリッド距離を用いた距離探索をサポートする、多次元データに対するインデキシング技術(Bohm, C., Berchtold, S., Keim, D. A., September 2001. Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases. ACM Computing Surveys 33 (3), 322-373.)を適用することができ、画像照合のさらなる高速化を図ることができる。画像照合装置1は、多次元インデキシング技術として、例えば、木構造を用いるANN(Approximate Nearest Neighbors)(Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., Wu, A. Y., November 1998. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM 45, 891-923.)、ハッシュを用いるLSH(Locality Sensitive Hashing)(Andoni, A., Indyk, P., 2008. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51 (1), 117-122.)、階層的ベクトル量子化(Nister, D., Stewenius, H., 2006. Scalable recognition with a vocabulary tree. In: Proc. of CVPR. Vol. 2. pp. 2161-2168.)、ベクトル量子化及びスカラー量子化(ハミングエンベディング)(Douze, M., Je´gou, H., Sandhawalia, H., Amsaleg, L., Schmid, C., 2009. Evaluation of gist descriptors for web-scale image search. In: Proceeding of the ACM International Conference on Image and Video Retrieval. CIVR ’09. ACM, New York, NY, USA, pp. 19:1-19:8.)等の、高次元空間におけるk近傍法(k-NN探索)を用いた技術を利用できる。

【0066】
例えば、多次元インデキシング技術としてLSHを利用する場合、第1特徴ベクトル算出部23は、特徴ベクトルに対して、予め定められた複数のハッシュ関数を用いて複数のハッシュ値を算出し、多次元インデックスとする。

【0067】
あるいは、多次元インデキシング技術としてANNを利用する場合、画像照合装置1は、特徴ベクトルについての特徴空間を予め所定の領域に分割しておく。そして、第1特徴ベクトル算出部23は、特徴ベクトルが属する特徴空間の領域を多次元インデックスとする。

【0068】
第1特徴ベクトル算出部23は、多次元インデックスを作成すると、第1画像と関連付けて記憶部12に格納し(ステップS705)、一連のステップを終了する。

【0069】
図8は、画像照合装置1が画像検索サーバとして動作する場合の画像照合処理の動作を示すフローチャートである。以下、図8に示したフローチャートを参照しつつ、画像照合処理の動作を説明する。なお、以下に説明する動作のフローは、予め記憶部12に記憶されているプログラムに基づき主に制御部40により画像照合装置1の各要素と協同して実行される。

【0070】
なお、図8に示すステップS801~S803の処理は、図2に示すステップS204~S206の処理と同じであるため、説明を省略する。ただし、多次元インデキシング技術としてLSHを利用する場合、第2特徴ベクトル算出部26は、ステップS803で第2画像について特徴ベクトルを算出した後、その特徴ベクトルについて、第1画像の特徴ベクトルに対してハッシュ値を算出したのと同一の、複数のハッシュ関数を用いて複数のハッシュ値を算出する。

【0071】
ステップS804~S808の処理は、記憶部12に格納された全ての第1画像に対して各画像毎に実施される。

【0072】
ステップS804において、インデックス判定部41は、第2特徴ベクトル算出部26により第2画像について特徴ベクトルが算出されると、記憶部12から第1画像の特徴ベクトル及び多次元インデックスを読み出す(ステップS804)。

【0073】
次に、インデックス判定部41は、第1画像の特徴ベクトルと第2画像の特徴ベクトルが多次元インデックスに基づく条件を満たしているか否かを判定する(ステップS805)。

【0074】
例えば、多次元インデキシング技術としてLSHを利用する場合、インデックス判定部41は、記憶部12から読み出した第1画像の特徴ベクトルのハッシュ値が、第2画像の特徴ベクトルの対応するハッシュ値と所定数(例えば、全ハッシュ値のうちの半数)以上一致するか否かにより、多次元インデックスに基づく条件を満たしているか否かを判定する。

【0075】
あるいは、多次元インデキシング技術としてANNを利用する場合、インデックス判定部41は、第1画像の特徴ベクトルが属する特徴空間の領域が、第2画像の特徴ベクトルとのユークリッド距離が(2-2θ1)以下となる部分を含むか否かにより、多次元インデックスに基づく条件を満たしているか否かを判定する。

【0076】
インデックス判定部41が多次元インデックスに基づく条件を満たしていると判定した場合、第1照合部28は、第1画像の特徴ベクトルと第2画像の特徴ベクトルのユークリッド距離が式(51)の条件を満たすか否かを判定する(ステップS806)。

【0077】
第1照合部28は、式(51)の条件が満たされている場合、その第1画像を第2画像に類似する画像の候補(以下、類似画像候補と称する)として抽出する(ステップS807)。

【0078】
一方、ステップS805でインデックス判定部41が多次元インデックスに基づく条件が満たされていないと判定した場合、ステップS806で第1照合部28が式(51)の条件が満たされていないと判定した場合、又は、ステップS807で第1照合部28が類似画像候補を抽出した場合、制御部40は、第2画像を全ての第1画像と比較したか否かを判定する(ステップS808)。

【0079】
制御部40は、まだ第2画像と比較していない第1画像がある場合、ステップS804~S807の処理を繰り返し、全ての第2画像と第1画像との比較が完了すると、一連のステップを終了する。

【0080】
制御部40は、図8のフローチャートを終了した後、さらに、図5に示したフローチャートを実施し、第2画像の類似画像候補として抽出した第1画像についてNCC値を用いて詳細に画像照合を行う。そして、制御部40は、第2画像と類似すると判定した第1画像の情報をインターフェース部11を介して検索を要求したコンピュータに通知する。あるいは、制御部40は、図8のフローチャートにより類似画像候補として抽出した第1画像の情報をインターフェース部11を介して検索を要求したコンピュータに通知してもよい。

【0081】
以上詳述したように、図8に示したフローチャートに従って動作することによって、画像照合装置1は、画像検索サーバとして動作し、複数の画像に対する画像照合を高速かつ高精度に実施することが可能となった。また、所定の画像を複数の画像と照合する場合に多次元インデックス構造を利用して照合処理を高速化することが可能となった。

【0082】
以下、本実施形態の低次元変換方法による類似画像の抽出精度について説明する。複数の画像Ii1を有する画像セットIS1(IS1={Ii1})と複数の画像Ii2を有する画像セットIS2(IS2={Ii2})において、NCC値が閾値θ0より大きくなる画像のペアの集合IIPSは、式(53)のように表される。
【数53】
JP0005713398B2_000054t.gif
この集合IIPSは、本実施形態で算出されるNCCの上限値UBが閾値θ0より大きくなる、つまり式(54)で表される画像のペアの集合IIPS'に近似できる。
【数54】
JP0005713398B2_000055t.gif

【0083】
上述した通り、NCC値は上限値UB以下となるので、上限値UBがθ0以下である場合、NCC値は確実にθ0以下となり、対応する画像のペアは確実にIIPSに含まれないと判断できる。つまり、式(55)の関係が成立し、IIPSに含まれる画像のペアがIIPS'から取りこぼされることはない。
【数55】
JP0005713398B2_000056t.gif

【0084】
一方、IIPSに対してIIPS'が大きくなりすぎると、類似しない画像まで類似画像として抽出していることになり、類似画像の抽出精度が低いということになる。このように、低次元変換の効果及び抽出した画像の類似性は、類似画像の抽出精度(以下、プレシジョンと称する)と、類似画像の非取りこぼし率(以下、リコールと称する)を用いて評価することができる。式(56)はプレシジョンの算出式であり、式(57)はリコールの算出式である。
【数56】
JP0005713398B2_000057t.gif
【数57】
JP0005713398B2_000058t.gif
例えば、IIPS'を非常に大きくする(極端な例ではIIPS'をIIPSの全集合とする)ことにより、リコールを容易に100%にすることができるが、その場合、プレシジョンが低くなる。低次元変換においてはリコールを100%に保ちつつ、プレシジョンを可能な限り高くすることが好ましい。

【0085】
図9は、本実施形態及び他の低次元変換方法においてリコールを100%にしたときのプレシジョンを表すグラフである。図9では、他の低次元変換方法としてMSEAと、離散コサイン変換(DCT:Discrete Cosine Transform)が用いられる。

【0086】
図9に示すグラフ900において、グラフ901は本実施形態によるプレシジョンを示し、グラフ902はMSEAによるプレシジョンを示し、グラフ903はDCTによるプレシジョンを示す。グラフ900の横軸は各低次元変換における特徴量(特徴ベクトル)の次元数を示し、縦軸はプレシジョンを示す。なお、図9は、1時間のビデオからランダムに選択された1万フレームの画像と他の1時間のビデオからランダムに選択された1万フレームの画像についてのプレシジョンを示す。この二つの異なる1時間のビデオは、異なった日の同じ時間帯に同じチャンネルで放送された映像であり、オープニング、エンディングの画像等、同一の画像が幾つか含まれている。各画像は352×240画素の画像であり、閾値θ0及びθ1は0.9に設定されている。

【0087】
式(5)の上限値UBMSEAは、式(58)に示すように、式(59)、(60)で示される特徴ベクトルの内積で表される。
【数58】
JP0005713398B2_000059t.gif
【数59】
JP0005713398B2_000060t.gif
【数60】
JP0005713398B2_000061t.gif
そこで、MSEAを用いた低次元変換方法では、低次元特徴量として式(59)、(60)に示す特徴ベクトルを使用し、その内積が閾値θ1以上となる二画像を類似画像として抽出する。

【0088】
図10は、DCTを用いた低次元変換方法を説明するための概略図である。DCTを用いた低次元変換方法では、まず、各画像の正規化画像を所定のブロックに分割し、二次元DCTにより周波数成分に変換する。図10のブロック1000内の各要素(a0、a1、a2、...)は、二次元DCTにより変換されたDCT係数を示す。図10に示すように、二次元DCTにより変換されたDCT係数は、MPEG、JPEG等で用いられるジグザグスキャンにより低周波数成分側から順に並べられる。そして、式(61)に示すように、低周波数成分側から順に選択されたDCT係数による特徴ベクトルがDCTによる低次元特徴量となる。
【数61】
JP0005713398B2_000062t.gif
なお、DCT係数は正規化画像から生成され、DC成分は常に0となるため省略される。

【0089】
DCTにより変換された周波数成分の全パワーは元の画像のパワーと一致する。つまり、全DCT係数を用いて計算したユークリッド距離がNCC値に対応するので、DCT係数の一部(又は全部)を用いて計算したユークリッド距離が(2-2θ0)以下である場合、NCC値がθ0以上となることはない。そこで、この方法では、式(62)に示すように、それぞれのDCT成分がai、biである二つの画像の特徴ベクトルのユークリッド距離を求め、ユークリッド距離が(2-2θ1)(θ1≧θ0)以下となる二画像を類似画像として抽出する。
【数62】
JP0005713398B2_000063t.gif

【0090】
なお、図9に示すグラフ900では、式(62)に示すユークリッド距離が(2-2θ1)以下となる画像のペアの集合をIIPS'とし、NCC値がθ0以上となる画像のペアの集合をIIPSとしてプレシジョン及びリコールを算出している。

【0091】
図9に示すように、(特に次元数が低い場合)プレシジョンは必ずしも高くない。プレシジョンは、最も高くても15%未満であり(次元数が1024の場合)、次元数が64の場合は5~6%まで落ちる。また、DCTによるプレシジョンは、本実施形態によるプレシジョンとほとんど同じ値であるが、MSEAによるプレシジョンは、極めて低い値となる。

【0092】
一方、例えば、NCCの上限値UBについての閾値θ1をNCC値についての閾値θ0より大きい値にすると(つまり、類似画像を正確にフィルタリングするのではなく、近似的にフィルタリングすると)、リコールは100%にならなくなるが、プレシジョンを高くすることができる。

【0093】
図11(a)は、本実施形態及び他の低次元変換方法においてリコールを100%以下にしたときのリコールとプレシジョンの関係のグラフを示し、図11(b)は、その拡大図を示す。図11(a)、(b)に示すグラフ1100、1110では、他の低次元変換方法として、MSEAと、DCTと、正規化輝度ヒストグラム(以下、NIH(Normalized intensity histograms)と称する)が用いられる。

【0094】
図12は、NIHを用いた低次元変換方法を説明するための概略図である。NIHを用いた低次元変換方法では、まず、各画像の正規化画像1200を(2×2、3×3等の)サブ領域1210に分割し、各サブ領域について、一定範囲毎に量子化した正規化輝度のヒストグラム1220を算出する。そして、式(63)に示すように、全てのサブ領域のヒストグラムの分布値ai,j(iはサブ領域の番号、jは各ヒストグラムの量子化レベルの番号)を順番に並べたベクトルがNIHによる低次元特徴量となる。
【数63】
JP0005713398B2_000064t.gif
この方法では、式(64)に示すように、各ヒストグラムの分布値がai,j、bi,jである二つの画像の特徴ベクトルのユークリッド距離を求め、ユークリッド距離が(2-2θ1)以下となる二画像を類似画像として抽出する。
【数64】
JP0005713398B2_000065t.gif

【0095】
また、この方法では、サブ領域の数と正規化輝度の量子化レベルを変更することにより、特徴量の次元数を変更することができる。例えば、サブ領域を2×2にし、正規化輝度の量子化を4レベルにした場合、特徴量の次元数は、2×2×4となる。NIHを用いて類似画像を抽出する場合、NCCの上限値は算出されないのでNCC値が閾値θ0以上になる画像のペアの集合IIPSに対するリコールは100%とならないが、リコール及びプレシジョンが非常に高くなることが知られている。

【0096】
なお、図11に示すグラフ1100では、式(64)に示すユークリッド距離が(2-2θ1)以下となる画像のペアの集合をIIPS'とし、NCC値がθ0以上の画像のペアの集合をIIPSとしてプレシジョン及びリコールを算出している。

【0097】
図11(a)、(b)に示すグラフ1100において、「prop 16D」、「prop 64D」、「prop 256D」、「prop 1024D」のグラフは、本実施形態の低次元変換方法で特徴量次元数がそれぞれ16、64、256、1024のときのリコールとプレシジョンの関係を示す。また、「DCT 5D」、「DCT 44D」、「DCT 209D」のグラフは、DCTによる低次元変換方法で特徴量次元数がそれぞれ5、44、209のときのリコールとプレシジョンの関係を示す。また、「NIH 2×2×4」、「NIH 4×4×4」、「NIH 4×4×8」のグラフは、NIHによる低次元変換方法で特徴量次元数がそれぞれ2×2×4、4×4×4、4×4×8のときのリコールとプレシジョンの関係を示す。また、「MSEA 16D」、「MSEA 64D」、「MSEA 512D」のグラフは、MSEAによる低次元変換方法で特徴量次元数がそれぞれ16、64、512のときのリコールとプレシジョンの関係を示す。グラフ1100、1110の横軸はリコールの値を示し、縦軸はプレシジョンの値を示す。

【0098】
図11(a)、(b)に示すように、本実施形態の低次元変換方法では、特徴量次元数が64と256の場合、リコールを97%に保ちつつ、プレシジョンが70%以上となる。特に、リコールが非常に高い(95%以上)場合、DCT、NIH、MSEAよりプレシジョンが高くなる。

【0099】
図13(a)は、図11(a)とは異なる画像セットのペア(それぞれ、類似する放送映像から取得した1万画像)についてのリコールとプレシジョンの関係のグラフを示し、図13(b)は、その拡大図を示す。図13(a)、(b)のグラフ1300、1310では、ほとんど全てのタイプで、図11(a)、(b)のグラフ1100、1110より高いリコールとプレシジョンの組合せが得られる。図13(b)に示すように、本実施形態の低次元変換方法で特徴量次元数が1024又は256のときに最も高いパフォーマンスが得られ、次いでMSEAによる低次元変換方法で特徴量次元数が512のとき、本実施形態の低次元変換方法で特徴量次元数が64又は16のとき、MSEAによる低次元変換方法で特徴量次元数が64のときの順に高いパフォーマンスが得られる。一方、DCTによる低次元変換方法では、あまり高いパフォーマンスが得られない。また、MSEAによる低次元変換方法で特徴量次元数が16の場合のパフォーマンスは、本実施形態の低次元変換方法で特徴量次元数が16の場合より非常に低くなる。つまり、本実施形態の低次元変換方法は、全ての特徴量次元数において、他の低次元変換方法より高いパフォーマンスを得ることができる。

【0100】
図14(a)、(b)、(c)、(d)は、それぞれリコールを0.95、0.97、0.98、0.99に固定したときの各低次元変換方法での特徴量次元数とプレシジョンの関係のグラフを示す。図14(a)、(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の横軸は特徴量次元数を示し、縦軸はプレシジョンを示す。

【0101】
図14(a)~(d)に示すように、リコールを非常に高い値にした場合、本実施形態の低次元変換方法でのプレシジョンは、他の低次元変換方法でのプレシジョンより高くなることが明らかである。図14(d)に示すように、リコールが0.99の場合、本実施形態の低次元変換方法では、DCTによる低次元変換方法よりわずかにパフォーマンスが低くなるが、この場合、そもそもプレシジョンが0.14以下であり、極めて低い。また、例えば、図14(a)に示すように、リコールが0.95の場合、本実施形態の低次元変換方法において、特徴量次元数が低い方が高いパフォーマンスを示している(特徴量次元数が64、128、256の方が、特徴量次元数が512のときよりもプレシジョンが高い)。類似した現象がMSEAでもみられる(特徴量次元数が16、32、64の方が、特徴量次元数が128のときよりもプレシジョンが高い)。これは、これらの方法が複数ブロックへ分割するものであるためと考えられる。そのため、リコールを100%としない場合、適切なサイズのブロックに分割する必要がある。図14(a)~(d)から、本実施形態の低次元変換方法でのプレシジョンは、特徴量次元数が64のとき、すなわち、分割するブロック数が32のとき、最も高くなると考えられる。

【0102】
図15(a)~(d)は、図14(a)~(d)とは異なる画像セットのペアについて、それぞれリコールを0.95、0.97、0.98、0.99に固定したときの各低次元変換方法での特徴量次元数とプレシジョンの関係のグラフを示す。図15(a)、(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の横軸は特徴量次元数を示し、縦軸はプレシジョンを示す。

【0103】
図15(a)~(d)に示すグラフ1500~1530では、プレシジョンが比較的高くなっている。例えば、図15(d)では、リコールが0.99に固定されているにも関わらず、プレシジョンは略0.6となる。図15(a)~(c)に示すように、リコールが比較的低い(0.95~0.98)場合、本実施形態の低次元変換方法とMSEAによる低次元変換方法はDCT及びNIHによる低次元変換方法よりパフォーマンスがよい。一方、図15(d)に示すように、リコールが高い(0.99)場合、本実施形態の低次元変換方法とDCT及びNIHによる低次元変換方法はMSEAによる低次元変換方法よりパフォーマンスが高い。つまり、全体として、本実施形態の低次元変換方法は他の低次元変換方法より高いパフォーマンスを得ることができる。

【0104】
以上、図9、図11(a)、(b)、図13(a)、(b)、図14(a)~(d)、図15(a)~(d)を用いて説明したように、本実施形態の低次元変換方法を用いることにより、他の低次元変換方法より高精度に類似性の高い画像を抽出することが可能となる。

【0105】
本実施形態の低次元変換方法では、ラグランジュの未定乗数決定法を用いてNCCの上限値を算出する。これにより、NCC値が上限値に近いとき、そのNCCの微分係数は非常に0に近くなり、上限値から離れているとき、微分係数は0から離れる。そのため、NCC値が上限値に近い(リコールが高い)場合、上限値をわずかに大きくしても、微分係数が0に近いのでリコールは大きく変化しない。一方、NCC値が上限値から離れている場合、微分係数は0から離れているので、プレシジョンは大幅に増加する。これにより、本実施形態の低次元変換方法では、リコールを高く保ちつつ、プレシジョンを高くできると考えられる。

【0106】
図16は、本実施形態による照合処理の時間を示す表である。図16の表1600は、それぞれ1万画像(352×240画素)からなる二つの画像セットにおいて、全ての画像ペアの組合せについて特徴ベクトルのユークリッド距離により全数照合したときの時間を示す。なお、この時間には、特徴ベクトルの算出時間は含まれない。

【0107】
表1600の行1610と行1630は低次元特徴量による照合処理を、行1620と行1640は低次元特徴量による照合処理及びそれにより抽出した類似画像のペアに対するNCCによる照合処理を示す。また、行1610と行1620ではリコールが100%になるようにし(低次元特徴量による照合処理における閾値θ1=NCCによる照合処理における閾値θ0=0.9)、行1630と行1640ではリコールが95%になるようにしている(θ1>θ0)。各行において、さらに特徴量の次元数毎に処理結果が示される。一方、列1650は特徴量次元数を、列1660はプレシジョンを、列1670はリコールを、列1680は処理時間(秒)をそれぞれ示す。

【0108】
行1610と行1630に示すように、照合処理時間は、概ね特徴量の次元数に比例している。これに基づくと、全ての画像ペアの組合せについてNCCによる照合処理(つまり、352×240次元の演算)を実施した場合、約40時間かかると考えられる。リコールが100%の場合、行1610に示すようにプレシジョン値は比較的低くなり、類似画像として多くの画像が抽出されるため、行1620に示すようにNCCによる照合処理時間は非常に長くなる。一方、リコールが95%の場合、行1630に示すようにプレシジョンが大幅に高くなるため、類似画像の抽出数が抑制され、行1640に示すようにNCCによる照合処理時間はあまり長くならない。従って、わずかにリコールを減少させる(95%)のがリーズナブルであると考えられる。

【0109】
なお、上述したように、行1610と行1630の照合処理時間は、特徴量の次元数に応じて異なるものであり、本実施形態とMSEAとで差は生じない。また、1万画像(352×240画素)について、本実施形態に基づく低次元特徴量の算出時間とMSEAに基づく低次元特徴量の算出時間は、その次元数に関わらず、それぞれ、約35秒と約32秒であり、ほとんど差がなかった。つまり、次元数が同じ場合、本実施形態の低次元変換方法とMSEAによる低次元変換方法とで類似画像を抽出するのにかかる時間は、ほとんど同じとなる。一方、本実施形態の低次元変換方法では、MSEAによる低次元変換方法より、類似画像として抽出する画像のペアが少なくなるので、その後のNCCによる照合処理時間は短くなり、トータルの照合時間は短くなる。

【0110】
図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の機能を備える。

【0111】
画像入力部53は、CCD、CMOS等の光電変換器で構成された2次元検出器と、その2次元検出器上に撮影対象の像を結像する結像光学系等を有する。画像入力部53は、一定の時間間隔(例えば1/30秒)毎に撮影を行い、撮影画像を、例えば352×240画素のデジタル画像に変換し、そのデジタル画像を記憶部52に記憶する。

【0112】
図18は、図17に示す画像照合装置2による画像の符号化処理の動作を示すフローチャートである。以下、図18に示したフローチャートを参照しつつ、画像符号化処理の動作を説明する。なお、以下に説明する動作のフローは、予め記憶部52に記憶されているプログラムに基づき主に制御部60により画像照合装置2の各要素と協同して実行される。

【0113】
最初に、画像入力部53は、撮影対象を撮影した画像をデジタル画像に変換し、そのデジタル画像を記憶部52に記憶する(ステップS1801)。

【0114】
次に、インテグラル画像生成部61は、記憶部12に保存されたデジタル画像を読み出し、インテグラル画像を生成し、記憶部52に記憶する(ステップS1802)。

【0115】
デジタル画像及びインテグラル画像の水平方向をx軸、垂直方向をy軸とし、デジタル画像の座標(a、b)における正規化画素値をI(a、b)とする。インテグラル画像生成部67は、各画素が式(65)、(66)からなるインテグラル画像(Viola, P., Jones, M., May 2004. Robust real-time face detection. International Journal of Computer Vision 57 (2), 137-154.)をそれぞれ生成する。
【数65】
JP0005713398B2_000066t.gif
【数66】
JP0005713398B2_000067t.gif
つまり、式(65)により算出されるインテグラル画像の各画素値は、原点からその画素までの全ての画素の正規化画素値の総和であり、式(66)により算出されるインテグラル画像の各画素値は、原点からその画素までの全ての画素の正規化画素値の二乗和である。

【0116】
図19は、インテグラル画像を説明するための概略図である。例えば、インテグラル画像1900において、座標(x1、y1)、(x1、y2)、(x2、y1)、(x2、y2)で囲まれた領域Dの正規化画素値の総和と正規化画素値の二乗和は、それぞれ、式(67)、(68)により算出することができる。
【数67】
JP0005713398B2_000068t.gif
【数68】
JP0005713398B2_000069t.gif
従って、予めインテグラル画像を作成しておくことにより、所定領域内の正規化画素値の総和と二乗和の算出処理を高速化できるので、特徴ベクトルの算出を高速化できる。

【0117】
次に、符号化処理部62は、記憶部12に保存されたデジタル画像を読み出し、デジタル画像のフォーマット(画素数)変換、8×8画素、16×16画素等の符号化ブロックへの分割等の符号化前処理を実施する(ステップS1803)。

【0118】
以下のステップS1804~S1814の処理は、符号化ブロック毎に実施される。まず、画像分割部63は、符号化ブロックをさらに所定サイズの複数のブロックに分割する(ステップS1804)。例えば、画像分割部63は、16×16画素の画像を4×4画素の16ブロックに分割する。

【0119】
次に、特徴ベクトル算出部64は、インテグラル画像を用いて、符号化ブロックについて、式(37)に示す特徴ベクトルを算出し、符号化ブロックと関連付けて記憶部12に保存する(ステップS1805)。

【0120】
次に、上限値算出部65は、記憶部12から照合元ブロックの特徴ベクトルを取得する(ステップS1806)。

【0121】
この照合元ブロックは、例えば、1フレーム前のデジタル画像における各符号化ブロックである。なお、前方向予測だけでなく、後方向予測も用いる場合、上限値算出部65は、1フレーム後のデジタル画像における各符号化ブロックも照合元ブロックとして用いる。

【0122】
次に、上限値算出部65は、符号化ブロックの特徴ベクトルと照合元ブロックの特徴ベクトルの内積を算出して、符号化ブロックと照合元ブロックについて、NCCの上限値UBを求める(ステップS1807)。

【0123】
次に、第1照合部66は、符号化ブロックと照合元ブロックについての上限値UBが閾値θ1以上であるか否かを判定する(ステップS1808)。

【0124】
上限値UBが閾値θ1以上である場合、第1照合部65は、その照合元ブロックを符号化ブロックと類似すると判定し、NCC値算出部67は、その符号化ブロックと照合元ブロックについてNCC値を算出する(ステップS1809)。

【0125】
次に、第2照合部68は、NCC値算出部67が算出したNCC値がその符号化ブロックについて算出されたNCC値のうち最大であるか否かを判定する(ステップS1810)。

【0126】
NCC値算出部67が算出したNCC値がその符号化ブロックについて算出されたNCC値のうち最大である場合、第2照合部68は、その照合元ブロックを動き検出用ブロックとして記憶部52に記憶(すでに記憶されている場合、更新)する(ステップS1811)。

【0127】
一方、上限値UBが閾値θ1未満である場合、NCC値算出部67が算出したNCC値がその符号化ブロックについて算出されたNCC値のうち最大でない場合、又は、第2照合部68が照合元ブロックを動き検出用ブロックとして記憶部52に記憶した場合、制御部60は、符号化ブロックを全ての照合元ブロックと比較したか否かを判定する(ステップS1812)。

【0128】
制御部60は、まだ比較していない照合元ブロックがある場合、ステップS1807~S1811の処理を繰り返し、全ての照合元ブロックとの比較が完了すると、符号化処理部62は、記憶部52に記憶された動き検出用ブロックの候補を用いて動き補償を行う。また、符号化処理部62は、DCT変換、量子化等の符号化処理を実施する(ステップS1813)。

【0129】
次に、制御部60は、全ての符号化ブロックの符号化処理が完了したか否かを判定する(ステップS1814)。全ての符号化ブロックの符号化処理が完了していない場合、ステップS1803~S1813の処理を繰り返し、全ての符号化ブロックの符号化処理が完了すると、制御部60は、一連のステップを終了する。

【0130】
このようにして符号化されたデータは、インターフェース部51を介して、外部のデコード装置(不図示)に送信される。

【0131】
なお、第2照合部68は、符号化ブロックと全ての照合元ブロックについての上限値UBが閾値θ1未満であった場合は、その符号化ブロックに類似する照合元ブロックが存在しないと判断し、任意の照合元ブロックを動き検出用ブロックとして選択する。あるいは、その場合、上限値UBが最も高かった照合元ブロックを動き検出用ブロックとして選択してもよい。

【0132】
以上詳述したように、図18に示したフローチャートに従って動作することによって、画像照合装置2は、画像符号化装置として動作し、高速に動き検出処理を実施することが可能となった。また、インテグラル画像を用いて特徴量算出処理を高速化することが可能となった。また、本実施形態による方法は、スライディングウィンドウに基づく探索(Wei, S.-D., Lai, S.-H., 2007. Efficient normalized cross correlation based on adaptive multilevel successive elimination. In: Proceedings of the 8th Asian conference on Computer vision - Volume Part I. ACCV’07. Springer-Verlag, Berlin, Heidelberg, pp. 638-646.)とも親和性が高い。
【符号の説明】
【0133】
1、2 画像照合装置
11、51 インターフェース部
12、52 記憶部
20、30、40、60 制御部
21 第1画像取得部
22 第1画像分割部
23 第1特徴ベクトル算出部
24 第2画像取得部
25 第2画像分割部
26 第2特徴ベクトル算出部
27、65 上限値算出部
28、66 第1照合部
31、67 NCC値算出部
32、68 第2照合部
41 インデックス判定部
53 画像入力部
61 インテグラル画像生成部
62 符号化処理部
63 画像分割部
64 特徴ベクトル算出部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18