Top > Search of Japanese Patents > IMAGE COLLATION DEVICE, IMAGE COLLATION METHOD AND COMPUTER PROGRAM

IMAGE COLLATION DEVICE, IMAGE COLLATION METHOD AND COMPUTER PROGRAM

Patent code P130008503
File No. S2011-0871-N0
Posted date Jan 30, 2013
Application number P2011-149428
Publication number P2013-016073A
Patent number P5713398
Date of filing Jul 5, 2011
Date of publication of application Jan 24, 2013
Date of registration Mar 20, 2015
Inventor
  • (In Japanese)佐藤 真一
Applicant
  • Research Organization of Information and Systems
Title IMAGE COLLATION DEVICE, IMAGE COLLATION METHOD AND COMPUTER PROGRAM
Abstract PROBLEM TO BE SOLVED: To provide an image collation device and an image collation method in which image collation is executed at high speed and similarity of images can be determined highly accurately.
SOLUTION: An image collation device 1 has: image dividing sections 22, 25 that divide the first image and the second image into a plurality of blocks; feature vector calculation sections 23, 26 that calculate a feature vector of the first image and a feature vector of the second image on the basis of the sum total and the square sum of a normalized pixel value of pixels included in each block regarding the first image and the second image; an upper limit value calculation section 27 that calculates an upper limit value of normalized cross collation of the first image and the second image on the basis of the feature vector of the first image and the feature vector of the second image by using a formula for calculating the upper limit value of normalized cross collation which is derived by using Lagrange's undetermined multiplication determining method; and a first collation section 28 that collates the first image and the second image on the basis of whether or not the upper limit value is a first threshold value or higher.
Outline of related art and contending technology (In Japanese)

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

一般に、画像照合の方法として、画素値の差の絶対値の合計(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を用いて二つの画像の類似性を評価することができる。

Field of industrial application (In Japanese)

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

Scope of claims (In Japanese)
【請求項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(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

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


PAGE TOP

close
close
close
close
close
close
close