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

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

国内特許コード P130008503
整理番号 S2011-0871-N0
掲載日 2013年1月30日
出願番号 特願2011-149428
公開番号 特開2013-016073
登録番号 特許第5713398号
出願日 平成23年7月5日(2011.7.5)
公開日 平成25年1月24日(2013.1.24)
登録日 平成27年3月20日(2015.3.20)
発明者
  • 佐藤 真一
出願人
  • 大学共同利用機関法人情報・システム研究機構
発明の名称 画像照合装置、画像照合方法及びコンピュータプログラム
発明の概要 【課題】画像照合を高速に実施するとともに、画像の類似性を高精度に判定することが可能な画像照合装置、画像照合方法を提供する。
【解決手段】画像照合装置1は、第1画像及び第2画像を複数のブロックに分割する画像分割部22、25と、第1画像及び第2画像について、各ブロックに含まれる画素の正規化画素値の総和及び二乗和に基づき、第1画像の特徴ベクトル及び第2画像の特徴ベクトルを算出する特徴ベクトル算出部23、26と、ラグランジュの未定乗算決定法を利用して導いた正規化相互相関の上限値を算出する式を用いて、第1画像の特徴ベクトル及び第2画像の特徴ベクトルに基づき、第1画像と第2画像の正規化相互相関の上限値を算出する上限値算出部27と、上限値が第1の閾値以上であるか否かに基づいて第1画像と第2画像を照合する第1照合部28とを有する。
【選択図】図1
従来技術、競合技術の概要



画像照合技術は、テンプレートマッチング、ブロック動き補償、画像圧縮、ステレオビジョン等の、多くの画像を用いたアプリケーションにおける重要な技術の一つである。最近は、画像の近似コピー検出、画像マイニング及びその画像アノテーションへの応用等、大規模な画像/映像データベースにおける画像照合技術の新しいアプリケーションについても研究が開始されている。





一般に、画像照合の方法として、画素値の差の絶対値の合計(SAD:Sum of Absolute Difference)、画素値の差の二乗の合計(SSD:Sum of Squared Difference)、正規化相互相関(NCC:Normalized Cross-Correlation)等が用いられている。特に、NCCは、画像間の輝度のずれ、コントラストの違い等による影響が少なく、輝度の補正等がなされた画像間の照合にも適している。例えば、水平方向をx軸、垂直方向をy軸とする画像I1と画像I2についてのNCC値は、式(1)で定義される。

【数1】




ここで、φx,yは画像I1の座標(x、y)の画素の画素値であり、ψx,yは画像I2の座標(x、y)の画素の画素値であり、φaveは画像I1の全画素の画素値の平均値であり、ψaveは画像I2の全画素の画素値の平均値である。式(1)に示すように、NCC値を算出するためには、対応する画素毎に画素値の相関を計算する必要があるため、特に、照合する画像のサイズが大きい場合には、計算量が大きくなり、算出処理に多大な時間が必要となる。





そこで、例えば、非特許文献1には、NCCに基づくテンプレートマッチング処理を高速化するための技術が開示されている。非特許文献1に開示された技術は、画像全体に対してテンプレートをずらしながらスキャンする場合、畳み込み演算を用いて各位置での照合結果を求める。一方、空間領域間の畳み込み演算は、周波数領域間での単純な掛け算に変換できるので、空間領域のデータを高速フーリエ変換(FFT:Fast Fourie Transform)を用いて周波数領域に変換することにより処理を高速化できる。しかし、この技術はある画像に対してテンプレートをスキャンする場合には効果的であるが、複数の画像に対して照合をする場合は各画像に対してFFT及び逆FFTを行う必要があり、かえって処理が遅くなるおそれがある。





一方、非特許文献2には、NCCの演算処理を効率化するための技術として、MSEA(multilevel successive elimination algorithm)が開示されている。非特許文献2に開示された技術では、式(2)に示すCauchy-Schwarzの不等式に基づいてNCCの上限値が算出される。

【数2】








画像I1と画像I2についてブロック内画素数がmである、n個のブロックに分割した場合、式(1)のNCC値は、ブロックの番号i(1≦i≦n)及びブロック内の画素の番号j(1≦j≦m)を用いて式(3)で表される。

【数3】




ここで、xi,j及びyi,jは各画素の正規化画素値であり、式(4)で定義される。

【数4】




式(2)、(3)から、NCCの上限値UBMSEAは、式(5)で表される。

【数5】




ここで、XXi及びYYiは式(6)で定義される。

【数6】




NCC値はこの上限値UBMSEAを越えることがないので、NCC値の代わりに、NCC値よりも簡易に算出できる上限値UBMSEAを用いて二つの画像の類似性を評価することができる。

産業上の利用分野


本発明は、画像照合装置、画像照合方法及びコンピュータプログラムに関し、特に、二つの画像が類似するか否かを判定する画像照合装置、画像照合方法及びコンピュータプログラムに関する。

特許請求の範囲 【請求項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】


ψi,jを前記第2画像におけるi番目のブロック内のj番目の画素の画素値、ψaveを前記第2画像の全ての画素の画素値の平均値として、次のベクトルξyを前記第2画像の特徴ベクトルとして算出し、
【数2】


前記上限値算出部は、前記第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】


前記第2画像の特徴ベクトルを算出するステップにおいて、mを前記ブロック内の画素数、nを前記ブロックの数、ψi,jを前記第2画像におけるi番目のブロック内のj番目の画素の画素値、ψaveを前記第2画像の全ての画素の画素値の平均値として、次のベクトルξyを前記第2画像の特徴ベクトルとして算出し、
【数4】


前記上限値を算出するステップにおいて、前記第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画像を照合するステップと、
をコンピュータに実行させることを特徴とするコンピュータプログラム。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2011149428thum.jpg
出願権利状態 登録
※ 情報・システム研究機構 国立情報学研究所(NII)は、我が国唯一の情報系に特化した研究所です。NIIでは、外部資金による研究成果の社会還元を中心に、技術移転活動に積極的に取り組んでいます。上記の発明にライセンス対象や共同開発対象として関心をお持ちいただいた方は、国立情報学研究所 社会連携推進室までお気軽にお問合せください。


PAGE TOP

close
close
close
close
close
close
close