(57)【特許請求の範囲】
【請求項１】
幾何変換パラメータ算出部が、入力画像のペア間において対応する特徴点のペアである第１対応点の各々について、幾何変換パラメータを算出するステップと、
擬似幾何変換パラメータ算出部が、前記第１対応点の各々について、前記幾何変換パラメータ算出部により前記第１対応点について算出された幾何変換パラメータと、前記第１対応点と異なる第２対応点とに基づいて、擬似幾何変換パラメータを算出するステップと、
投票ヒストグラム作成部が、前記幾何変換パラメータ算出部により前記第１対応点の各々について算出された幾何変換パラメータと、前記擬似幾何変換パラメータ算出部により前記第１対応点の各々について算出された擬似幾何変換パラメータとについて、予め定められた幾何変換空間の離散化区間に投票することにより、投票ヒストグラムを作成するステップと、
を含む画像照合方法。
【請求項２】
前記擬似幾何変換パラメータ算出部が擬似幾何変換パラメータを算出するステップは、前記第１対応点の各々について、前記第１対応点の近傍に存在する少なくとも１つの第２対応点の各々に対し、前記幾何変換パラメータ算出部により前記第１対応点について算出された幾何変換パラメータと、前記第２対応点とに基づいて、擬似幾何変換パラメータを算出する請求項１に記載の画像照合方法。
【請求項３】
幾何変換パラメータ算出部が、入力画像のペア間において対応する特徴点のペアである第１対応点の各々について、幾何変換パラメータを算出するステップと、
擬似幾何変換パラメータ算出部が、前記第１対応点の各々について、前記幾何変換パラメータ算出部により前記第１対応点について算出された幾何変換パラメータと、前記第１対応点と異なる第２対応点とに基づいて、擬似幾何変換パラメータを算出するステップと、
投票ヒストグラム作成部が、前記幾何変換パラメータ算出部により前記第１対応点の各々について算出された幾何変換パラメータと、前記擬似幾何変換パラメータ算出部により前記第１対応点の各々について算出された擬似幾何変換パラメータとについて、予め定められた幾何変換空間の離散化区間に投票することにより、投票ヒストグラムを作成し、前記投票ヒストグラムの情報量と、一様分布の情報量との差分を、前記入力画像のペア間の類似度として算出するステップと、
を含む画像照合方法。
【請求項４】
前記投票ヒストグラム作成部が前記入力画像のペア間の類似度を算出するステップは、前記幾何変換パラメータ算出部により前記第１対応点の各々について算出された幾何変換パラメータについて、前記幾何変換空間の離散化区間に投票するときに、以下（１）式により表される線形対数関数の差分係数Δ（ｙ）の値を格納したＬｏｏｋｕｐ Ｔａｂｌｅを用いて、以下（２）式により前記入力画像のペア間の類似度Ｄを更新することを繰り返す請求項３に記載の画像照合方法。
【数１】
0006322593.tif 000026
ただし、ｙは前記幾何変換パラメータについての投票により得られる、前記幾何変換空間の離散化区間の投票値を表す。
【請求項５】
前記擬似幾何変換パラメータ算出部が擬似幾何変換パラメータを算出するステップは、前記第１対応点の各々について、前記第１対応点の近傍に存在する少なくとも１つの第２対応点の各々に対し、前記幾何変換パラメータ算出部により前記第１対応点について算出された幾何変換パラメータと、前記第２対応点とに基づいて、擬似幾何変換パラメータを算出する請求項３又は請求項４に記載の画像照合方法。
【請求項６】
入力画像のペア間において対応する特徴点のペアである第１対応点の各々について、幾何変換パラメータを算出する幾何変換パラメータ算出部と、
前記第１対応点の各々について、前記幾何変換パラメータ算出部により前記第１対応点について算出された幾何変換パラメータと、前記第１対応点と異なる第２対応点とに基づいて、擬似幾何変換パラメータを算出する擬似幾何変換パラメータ算出部と、
前記幾何変換パラメータ算出部により前記第１対応点の各々について算出された幾何変換パラメータと、前記擬似幾何変換パラメータ算出部により前記第１対応点の各々について算出された擬似幾何変換パラメータとについて、予め定められた幾何変換空間の離散化区間に投票することにより、投票ヒストグラムを作成する投票ヒストグラム作成部と、
を含む画像照合装置。
【請求項７】
入力画像のペア間において対応する特徴点のペアである第１対応点の各々について、幾何変換パラメータを算出する幾何変換パラメータ算出部と、
前記第１対応点の各々について、前記幾何変換パラメータ算出部により前記第１対応点について算出された幾何変換パラメータと、前記第１対応点と異なる第２対応点とに基づいて、擬似幾何変換パラメータを算出する擬似幾何変換パラメータ算出部と、
前記幾何変換パラメータ算出部により前記第１対応点の各々について算出された幾何変換パラメータと、前記擬似幾何変換パラメータ算出部により前記第１対応点の各々について算出された擬似幾何変換パラメータとについて、予め定められた幾何変換空間の離散化区間に投票することにより、投票ヒストグラムを作成し、前記投票ヒストグラムの情報量と、一様分布の情報量との差分を、前記入力画像のペア間の類似度として算出する投票ヒストグラム作成部と、
を含む画像照合装置。
【請求項８】
コンピュータを、請求項６に記載の画像照合装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像照合装置、及び方法に係り、特に、画像間の類似度を求めるための画像照合装置、及び方法に関する。
【背景技術】
【０００２】
局所特徴量に基づく画像照合は、２枚の入力画像から抽出した多数の特徴点から局所特徴量を算出し、第１画像の特徴点と第２画像の特徴点とを比較し、局所特徴量の類似度が高いか否かを判定する技術である。画像照合によって、同一画像検索や類似画像検索、又は画像認識等の課題が実現可能となる。以下、第１画像と、第１画像に写っている物体と異なる物体を写した第２画像の対を、非関連画像と呼ぶ。第１画像と、第１画像に写っている物体と同一の物体を写した第２画像の対を、関連画像と呼ぶ。既存技術では、２枚の非関連画像に対して、市松模様のような繰り返しパターンや肌理の細かい模様等が両方の画像に含まれる場合、画像の間で誤って合致する特徴点が多く存在するため、同一物体を写した画像の対であると誤った照合結果が生じることが多い。
【０００３】
このような問題の影響を抑制するために、幾何変換の整合性を考慮した画像照合装置が発明されている。特に、画像間の対応点から算出した幾何変換パラメータをハフ変換に用いることによって画像照合を実現する装置（非特許文献１〜非特許文献３参照）は、照合精度と処理速度とメモリ使用量とのバランスが良いことが報告されている。対応点とは、２枚の画像の間で合致したか、又は局所特徴量の類似度が高いと判定した特徴点の対のことである。
【０００４】
非特許文献１に開示されている画像照合装置は、入力画像間の対応点から線形変換パラメータ（拡大縮小倍率と回転角度）を算出する処理と、線形変換パラメータに基づいて当該対応点を２次元空間に投票して投票ヒストグラムを作成する処理と、投票ヒストグラム上の最大値に基づいて入力画像間の類似度を算出する処理によって構成されている。非特許文献２に開示されている画像照合装置は、入力画像間の対応点から２次元の変位ベクトルを算出する処理と、変位ベクトルに基づいて当該対応点を２次元空間に投票して投票ヒストグラムを作成する処理と、投票ヒストグラム上の最大値に基づいて入力画像間の類似度を算出する処理によって構成されている。非特許文献３に開示されている画像照合装置は、入力画像間の対応点から２次元の線形変換パラメータと２次元の変位ベクトルを算出する処理と、線形変換パラメータに基づいて変位ベクトルを補正する処理と、線形変換パラメータと補正した変位ベクトルに基づいて当該対応点を４次元空間に投票して投票ヒストグラムを作成する処理と、投票ヒストグラムに基づいて入力画像間の類似度を算出する処理によって構成されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Herve Jegou, MatthijsDouze, and Cordelia Schmid. Improving bag-of-features for large scale image search. International Journal of Computer Vision, Vol. 87, No. 3,pp. 316-336, 2010.
【非特許文献２】Yimeng Zhang, Zhaoyin Jia, and Tsuhan Chen. Image retrieval with geometry-preserving visual phrases. In CVPR, pp. 809-816, 2011.
【非特許文献３】Yannis S. Avrithis and GiorgosTolias. Hough pyramid matching: Speeded-up geometry re-ranking for large scale image retrieval. International Journal of Computer Vision, Vol. 107, No. 1, pp. 1-19, 2014.
【非特許文献４】Krystian Mikolajczyk and CordeliaSchmid. Scale & affine invariant interest point detectors. International Journal of Computer Vision, Vol. 60, No. 1, pp. 63-86,2004.
【非特許文献５】David G. Lowe. Distinctive image features from scale invariant keypoints.InternationalJournal of Computer Vision, Vol. 60, No. 2, pp. 91-110, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、２枚の関連画像において、同一物体の内部にある正しい対応点（誤合致ではない対応点）であっても、特徴点抽出の誤差によって幾何変換パラメータを正確に算出できないことが多いという問題がある。また、２つの正しい対応点において、対応点を幾何変換空間における同一の区間に投票しなければならないが、対応点から算出した２組の幾何変換パラメータにわずかの差異しか存在しない場合でも、パラメータ離散化の誤差によって対応点が幾何変換空間の異なる区間に投票されることが多いという問題がある。
【０００７】
非特許文献３に開示されている画像照合装置は、対応点の投票が４次元の幾何変換パラメータに基づくため、非特許文献１又は非特許文献２に開示されている２次元の幾何変換パラメータのみに基づく画像照合装置と比べて、離散化誤差の発生確率がはるかに高い。しかし、該装置は、１つの対応点から算出した幾何変換パラメータは１組のみであるため、特徴点抽出又はパラメータ離散化の誤差が生じた場合、それに対処できず、複数の正しい対応点を誤って異なる離散化区間に投票することが多い。結果的に、投票ヒストグラムに誤りが存在することとなり、関連画像間の類似度を正しく算出できなくなる。
【０００８】
非特許文献１に開示されている画像照合装置は、対応点の投票が２次元の線形変換パラメータのみに基づくため、離散化誤差の発生確率がより低く、上記の問題に対する影響に耐性がある。しかし、該装置は、入力画像間の変位を全く考慮しないため、対応点が誤合致であるが線形変換パラメータが偶然類似する場合、それが誤合致であると正しく判定できないことが多い。同様に、非特許文献２に開示されている画像照合装置は、入力画像間の線形変換を全く考慮しないため、変位ベクトルが偶然類似する誤合致への弁別力が低い。また、該装置は、画像照合の精度が、線形変換が存在しないとの仮定に強く依存する。そのため、２枚の関連画像において、第１画像に対して第２画像が相対的に回転したり拡大縮小したりする幾何変換が生じた場合、幾何変換に伴って変位ベクトルが変動し、複数の正しい対応点から算出した変位ベクトルの整合性がなくなり、関連画像であると正しく判定できなくなる。
【０００９】
誤合致への弁別力をより高く保つためには、入力画像間の対応点の投票が線形変換と変位の両方に準じなければならない。しかし、従来の非特許文献３に開示されている画像照合装置のように１つの対応点から算出した幾何変換パラメータは１組のみである場合、特徴点抽出とパラメータ離散化の誤差に対処できない。該問題は、本発明で解決する第１の課題である。
【００１０】
また、関連画像に同一物体が複数写している場合、もしくは、写している同一物体が複数の平面で構成されている場合、関連画像間の幾何変換が複数存在することとなる。しかし、投票ヒストグラム上の最大値に基づいて入力画像間の類似度を算出する非特許文献１及び２に開示されている画像照合装置は、投票ヒストグラム上の最大値が１組の幾何変換パラメータにしか該当しないため、関連画像間の類似度を正確に算出できないことが多い。このような問題は、本発明で解決する第２の課題である。
【００１１】
また、誤合致への弁別力が高いのが原因で、非特許文献３に開示されている画像照合装置は、非特許文献１及び２に開示されている画像照合装置と比べて、より高い照合精度を実現できると報告されている。しかし、離散化区間の数が非常に多いため、幾何変換パラメータの離散化及びそれに基づいた対応点の投票において、処理速度が遅い問題がある。誤合致への弁別力を犠牲にせず、より速い処理速度を実現するのが、本発明で解決する第３の課題である。
【００１２】
本発明は、上記問題点を解決するために成されたものであり、精度よく、画像間の類似度を求めることができる画像照合装置、及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するために、第１の発明に係る画像照合方法は、幾何変換パラメータ算出部が、入力画像のペア間において対応する特徴点のペアである第１対応点の各々について、幾何変換パラメータを算出するステップと、擬似幾何変換パラメータ算出部が、前記第１対応点の各々について、前記幾何変換パラメータ算出部により前記第１対応点について算出された幾何変換パラメータと、前記第１対応点と異なる第２対応点とに基づいて、擬似幾何変換パラメータを算出するステップと、投票ヒストグラム作成部が、前記幾何変換パラメータ算出部により前記第１対応点の各々について算出された幾何変換パラメータと、前記擬似幾何変換パラメータ算出部により前記第１対応点の各々について算出された擬似幾何変換パラメータとについて、予め定められた幾何変換空間の離散化区間に投票することにより、投票ヒストグラムを作成するステップと、を含んで実行することを特徴とする。
【００１４】
また、第１の発明に係る画像照合方法において、前記擬似幾何変換パラメータ算出部が擬似幾何変換パラメータを算出するステップは、前記第１対応点の各々について、前記第１対応点の近傍に存在する少なくとも１つの第２対応点の各々に対し、前記幾何変換パラメータ算出部により前記第１対応点について算出された幾何変換パラメータと、前記第２対応点とに基づいて、擬似幾何変換パラメータを算出するようにしてもよい。
【００１５】
第２の発明に係る画像照合方法は、幾何変換パラメータ算出部が、入力画像のペア間において対応する特徴点のペアである対応点の各々について、幾何変換パラメータを算出するステップと、投票ヒストグラム作成部が、前記幾何変換パラメータ算出部により前記対応点の各々について算出された幾何変換パラメータについて、予め定められた幾何変換空間の離散化区間に投票することにより、投票ヒストグラムを作成し、前記投票ヒストグラムの情報量と、一様分布の情報量との差分を、前記入力画像のペア間の類似度として算出するステップと、を含んで実行することを特徴とする。
【００１６】
また、第２の発明に係る画像照合方法において、前記投票ヒストグラム作成部が前記入力画像のペア間の類似度を算出するステップは、前記幾何変換パラメータ算出部により前記対応点の各々について算出された幾何変換パラメータについて、前記幾何変換空間の離散化区間に投票するときに、以下（１）式により表される線形対数関数の差分係数Δ（ｙ）の値を格納したＬｏｏｋｕｐ Ｔａｂｌｅを用いて、以下（２）式により前記入力画像のペア間の類似度Ｄを更新することを繰り返すようにしてもよい。
【００１７】
【数１】
0006322593.tif 000002
【００１８】
ただし、ｙは前記幾何変換パラメータについての投票により得られる、前記幾何変換空間の離散化区間の投票値を表す。
【００１９】
また、第２の発明に係る画像照合方法において、擬似幾何変換パラメータ算出部によって擬似幾何変換パラメータを算出するステップを更に含み、前記幾何変換パラメータ算出部によって幾何変換パラメータを算出するステップは、前記入力画像のペア間において対応する特徴点のペアである第１対応点の各々について、幾何変換パラメータを算出し、前記擬似幾何変換パラメータ算出部によって擬似幾何変換パラメータを算出するステップは、前記第１対応点の各々について、前記幾何変換パラメータ算出部により前記第１対応点について算出された幾何変換パラメータと、前記第１対応点と異なる第２対応点とに基づいて、擬似幾何変換パラメータを算出し、前記投票ヒストグラム作成部によって前記入力画像のペア間の類似度を算出するステップは、前記幾何変換パラメータ算出部により前記第１対応点の各々について算出された幾何変換パラメータと、前記擬似幾何変換パラメータ算出部により前記第１対応点の各々について算出された擬似幾何変換パラメータとについて、前記幾何変換空間の離散化区間に投票することにより、投票ヒストグラムを作成し、前記入力画像のペア間の類似度を算出するようにしてもよい。
【００２０】
また、第２の発明に係る画像照合方法において、前記擬似幾何変換パラメータ算出部が擬似幾何変換パラメータを算出するステップは、前記第１対応点の各々について、前記第１対応点の近傍に存在する少なくとも１つの第２対応点の各々に対し、前記幾何変換パラメータ算出部により前記第１対応点について算出された幾何変換パラメータと、前記第２対応点とに基づいて、擬似幾何変換パラメータを算出するようにしてもよい。
【００２１】
第３の発明に係る画像照合装置は、入力画像のペア間において対応する特徴点のペアである第１対応点の各々について、幾何変換パラメータを算出する幾何変換パラメータ算出部と、前記第１対応点の各々について、前記幾何変換パラメータ算出部により前記第１対応点について算出された幾何変換パラメータと、前記第１対応点と異なる第２対応点とに基づいて、擬似幾何変換パラメータを算出する擬似幾何変換パラメータ算出部と、前記幾何変換パラメータ算出部により前記第１対応点の各々について算出された幾何変換パラメータと、前記擬似幾何変換パラメータ算出部により前記第１対応点の各々について算出された擬似幾何変換パラメータとについて、予め定められた幾何変換空間の離散化区間に投票することにより、投票ヒストグラムを作成する投票ヒストグラム作成部と、を含んで構成されている。
【００２２】
第４の発明に係る画像照合装置は、入力画像のペア間において対応する特徴点のペアである対応点の各々について、幾何変換パラメータを算出する幾何変換パラメータ算出部と、前記幾何変換パラメータ算出部により前記対応点の各々について算出された幾何変換パラメータについて、予め定められた幾何変換空間の離散化区間に投票することにより、投票ヒストグラムを作成し、前記投票ヒストグラムの情報量と、一様分布の情報量との差分を、前記入力画像のペア間の類似度として算出する投票ヒストグラム作成部と、を含んで構成されている。
【発明の効果】
【００２３】
本発明の画像照合装置、方法によれば、精度よく、画像間の類似度を求めることができる、という効果が得られる。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施の形態に係る前処理装置の構成を示すブロック図である。
【図２】本発明の実施の形態に係る前処理装置のビジュアルワード作成部の構成を示すブロック図である。
【図３】本発明の実施の形態に係る前処理装置のＴＦ−ＩＤＦ算出部の構成を示すブロック図である。
【図４】本発明の実施の形態に係る画像照合装置の構成を示すブロック図である。
【図５】本発明の実施の形態に係る画像照合装置の空間的類似度算出部の構成を示すブロック図である。
【図６】本発明の実施の形態に係る画像照合装置の空間的類似度算出処理のアルゴリズムを示す図である。
【図７】本発明の実施の形態に係る画像照合装置のＬｏｏｋｕｐ Ｔａｂｌｅ作成処理のアルゴリズムを示す図である。
【図８】本発明の実施の形態に係る画像照合装置の投票ヒストグラム作成部の構成を示すブロック図である。
【図９】本発明の実施の形態に係る画像照合装置の投票ヒストグラム作成処理のアルゴリズムを示す図である。
【図１０】本発明の実施の形態に係る画像照合装置における画像照合処理ルーチンを示すフローチャートである。
【図１１】本発明の実施の形態に係る画像照合装置における画像照合処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００２５】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２６】
＜本発明の実施の形態に係る前処理装置の構成＞
【００２７】
次に、本発明の実施の形態に係る前処理装置の構成について説明する。図１に示すように、本発明の実施の形態に係る前処理装置１００は、ＣＰＵと、ＲＡＭと、前処理を実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この前処理装置１００は、機能的には図１に示すように演算部２０を備えている。
【００２８】
演算部２０は、ビジュアルワード辞書２８と、ビジュアルワード作成部３０と、ＴＦ−ＩＤＦ類似度算出部３２と、対応点抽出部３４とを含んで構成されている。
【００２９】
ビジュアルワード辞書２８は、大量の画像から抽出した全ての特徴点を局所特徴量に基づいてクラスタリングして得られた、クラスタのＩＤ（ビジュアルワード）と中心ベクトル及び当該ビジュアルワードの逆文書頻度（ＩＤＦ）を格納する配列（集合）である。本実施形態では、ビジュアルワード辞書を作成する方法として、事前に５，０００枚前後のビジュアルワード辞書作成用の画像を用意し、全ての画像から抽出した特徴点を近似ｋ平均法を用いて分類する。ビジュアルワード辞書のサイズ（ビジュアルワードの数）ｋ は、１０６に設定する。各ビジュアルワードｔの逆文書頻度ｉｄｆ(ｔ)は、以下（３）式 によって算出できる。
【００３０】
【数２】
0006322593.tif 000003
【００３１】
ここで、Ｄはビジュアルワード辞書作成用の画像の集合、｜Ｄ｜は当該集合にある画像の数、｜｛ｄ∈Ｄ：ｔ∈ｄ｝｜はビジュアルワードｔを含む画像の数である。
【００３２】
ビジュアルワード作成部３０は、図２に示すように、入力画像のペアから対応する特徴点ペアを抽出する特徴点抽出部２３０と、各特徴点から局所特徴量を算出する局所特徴量算出部２３２と、ビジュアルワード辞書に基づいて各特徴点をビジュアルワードに変換する局所特徴量量子化部２３４とを含んで構成されている。また、本実施の形態では、第１画像及び第２画像の各々に対するビジュアルワード作成部３０があり、第１画像及び第２画像の各々に対するビジュアルワード集合を出力する。
【００３３】
特徴点抽出部２３０は、入力画像から特徴点を抽出する。本実施形態では、非特許文献４に開示されているHessian Affine Region Detector を駆使する。代案として、非特許文献５に開示されているScale-Invariant Feature Transform (SIFT) 特徴点検出装置を駆使する方法もある。特徴点抽出部は、各特徴点に対して、特徴点のスケール（Scale）と特性角（Characteristic Angle）及び２次元の位置座標が出力される。
【００３４】
局所特徴量算出部２３２は、各特徴点から局所特徴量を算出する。本実施形態では、非特許文献５に開示されているＳＩＦＴ局所特徴量記述器を用いる。局所特徴量計算部は、各特徴点に対して、１本の１２８次元の局所特徴量ベクトルが出力される。
【００３５】
局所特徴量量子化部２３４は、ビジュアルワード辞書２８に基づいて、各特徴点をビジュアルワードに変換する。各特徴点に対して、局所特徴量算出部２３２で算出された当該特徴点の局所特徴量と、ビジュアルワード辞書２８にある各クラスタの中心ベクトルとを比較し、類似度の最も高いクラスタのＩＤ（ビジュアルワード）を当該特徴点に割り当てる。当該処理を入力画像から抽出した全ての特徴点に対して実行し、得られた１個のビジュアルワード集合を出力する。本実施形態では、局所特徴量との類似度の最も高いクラスタを特定する方法として、近似最近傍探索法を駆使する。
【００３６】
ＴＦ−ＩＤＦ類似度算出部３２は、図３に示すように、入力画像に対応するビジュアルワード集合にある各ビジュアルワードのＴＦ−ＩＤＦを算出するＴＦ−ＩＤＦ算出部３３０と、２個のＴＦ−ＩＤＦベクトルのコサイン類似度を算出するコサイン類似度算出部３３２とを含んで構成されている。ＴＦ−ＩＤＦ類似度算出部３２には、２枚の入力画像のそれぞれに対応する計２個のビジュアルワード集合と、ビジュアルワード辞書２８とが入力され、入力画像のペア間のＴＦ−ＩＤＦ類似度が出力される。
【００３７】
ＴＦ−ＩＤＦ算出部３３０は、入力画像に対応するビジュアルワード集合にある各ビジュアルワードのＴＦ−ＩＤＦを算出する。各ビジュアルワードに対して、該ビジュアルワードの出現頻度（ＴＦ）とビジュアルワード辞書にある該ビジュアルワードの逆文書頻度に基づいて、当該ビジュアルワードのＴＦ−ＩＤＦを以下（４）式によって算出する。
【００３８】
【数３】
0006322593.tif 000004
【００３９】
ここで、f(ｔ，ｄ) は、ビジュアルワードｔの画像ｄにおける出現回数である。ビジュアルワード辞書にあるビジュアルワードの数をｎで表す場合、ＴＦ−ＩＤＦ算出部３３０は、入力画像に対応する１個のｎ次元のＴＦ−ＩＤＦベクトルが出力され、各次元の要素はビジュアルワード辞書にある各ビジュアルワードの入力画像におけるＴＦ−ＩＤＦである。ビジュアルワード辞書にあるが入力画像にないビジュアルワードには、実数０をＴＦ−ＩＤＦとして割り当てる。
【００４０】
コサイン類似度算出部３３２は、２個のＴＦ−ＩＤＦベクトルのコサイン類似度を（５）式によって算出する。
【００４１】
【数４】
0006322593.tif 000005
【００４２】
任意の二枚の画像に対して、画像間のコサイン類似度は常に［０，１］の範囲にある。
【００４３】
対応点抽出部３４は、入力画像のペア間において対応する特徴点ペアである対応点からなる対応点集合を作成する。ビジュアルワード作成部３０により作成された、２枚の入力画像のそれぞれに対応する計２個のビジュアルワード集合から、同一のビジュアルワードが割り当てられた特徴点同士を特定し、該特徴点同士で構成された対を対応点と見なして抽出し、得られた１個の対応点集合を出力する。
【００４４】
＜本発明の実施の形態に係る画像照合装置の構成＞
【００４５】
次に、本発明の実施の形態に係る画像照合装置の構成について説明する。図４に示すように、本発明の実施の形態に係る画像照合装置５００は、ＣＰＵと、ＲＡＭと、後述する画像照合処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この画像照合装置５００は、機能的には図４に示すように演算部５２０と、出力部５５０とを備えている。
【００４６】
演算部５２０は、空間的類似度算出部５３０と、加重平均部５３２とを含んで構成されている。
【００４７】
空間的類似度算出部５３０は、前処理装置１００により抽出された対応点集合を受け付けて、以下に説明する各部の処理により、投票ヒストグラムを作成し、入力画像のペア間の類似度を算出する。
【００４８】
空間的類似度算出部５３０は、図５に示すように、入力画像のペア間の対応点に対して位置座標空間において最も近いｋ個の近傍を特定するＫ近傍探索部１５３０と、入力画像のペア間の対応点から幾何変換パラメータを算出する幾何変換パラメータ算出部１５３２と、幾何変換パラメータ又は擬似幾何変換パラメータを離散化して、投票先となる幾何変換空間の離散化区間を特定するパラメータ離散化部１５３４と、第１対応点から算出した幾何変換パラメータと第１対応点のｋ近傍集合にある第２対応点の位置座標に基づいて新たな擬似幾何変換パラメータを算出する擬似幾何変換パラメータ算出部１５３６と、線形対数関数の差分係数のＬｏｏｋｕｐ Ｔａｂｌｅを作成するＬｏｏｋｕｐ Ｔａｂｌｅ作成部１５３８と、パラメータ離散化部１５３４の出力に基づいて幾何変換空間に投票して投票ヒストグラムを作成し、入力画像のペア間の空間的類似度を算出する投票ヒストグラム作成部１５４０とを含んで構成されている。
【００４９】
空間的類似度算出部５３０は、Ｋ近傍探索部１５３０、幾何変換パラメータ算出部１５３２、パラメータ離散化部１５３４、擬似幾何変換パラメータ算出部１５３６、Ｌｏｏｋｕｐ Ｔａｂｌｅ作成部１５３８、及び投票ヒストグラム作成部１５４０により、図６に示すＡｌｇｏｒｉｔｈｍ１に従って、第１の反復処理及び第２の反復処理を実行する。第１反復処理は、第１対応点に該当して実行され、Ａｌｇｏｒｉｔｈｍ１の１０〜２１行に相当し、第２反復処理は、第２対応点に該当して実行され、Ａｌｇｏｒｉｔｈｍ１の１３〜２０行に相当する。
【００５０】
Ｋ近傍探索部１５３０は、以下に説明するように、入力画像のペア間の対応点の各々に対して、当該対応点を第１対応点とし、位置座標空間において最も近いｋ個の第２対応点を得る。以下、対応点を構成した２個の特徴点において、第１画像にある特徴点を第１特徴点と呼ぶ。本実施形態では、第１特徴点ｐに対して、ｐの位置座標とｐ以外の第１特徴点ｐ′の位置座標とを比較し、ユークリッド距離の最も近いｐ′からｋ個の第１特徴点を特定し、ｐのｋ近傍と見なす。以下、ｐを含む対応点をｃで、ｐ′を含む対応点をｃ′で表す。ｐのｋ近傍集合にある各ｐ′に対して、各ｐ′を含む対応点ｃ′を対応点ｃのｋ近傍とみなす。本実施の形態では対応点ｃを第１対応点とし、対応点ｃ′を第２対応点とする。ｋ近傍探索部１５３０では、入力画像のペア間の対応点集合に含まれる第１対応点毎に、第２対応点からなる１個のｋ近傍集合が出力される。なお、本実施形態では、近傍の数ｋを[１０，１５］の範囲にある整数に設定する。
【００５１】
幾何変換パラメータ算出部１５３２は、以下に説明するように、第１対応点の各々について、幾何変換パラメータを算出する。
【００５２】
幾何変換パラメータ算出部１５３２においては、以下、第１画像から抽出した特徴点の集合をＰで、第２画像から抽出した特徴点の集合をＱで表す。集合Ｐにある各特徴点ｐ∈Ｐに対して、当該特徴点のスケールをσ（ｐ）で、特性角をθ（ｐ）で、位置座標をｔ＾（ｐ）＝［ｘ（ｐ）ｙ（ｐ）］Ｔで、ビジュアルワードをｕ（ｐ）で表す。第１画像と第２画像の間の第１対応点をｃ＝（ｐ，ｑ）で表し、当該第１対応点は、ｐ∈Ｐとｑ∈Ｑ及びｕ（ｐ）＝ｕ（ｑ）の条件を満たす。第１対応点の集合をＣ＝｛ｃ｝で表す。なお、ベクトルを表す記号には、記号の後ろに「＾」を付して表現する。
【００５３】
幾何変換パラメータ算出部１５３２は、具体的は、以下の処理を行って幾何変換パラメータを算出する。まず、第１対応点の集合Ｃにおける各第１対応点ｃの入力を受け付ける。本実施形態では、ｃに対する幾何変換パラメータは、２次元の線形変換パラメータと２次元の変位ベクトルによって構成され、計４次元からなる。線形変換パラメータは、拡大縮小倍率σ（ｃ）と回転角度θ（ｃ）によって構成され、（６）式及び（７）式によって算出される。
【００５４】
【数５】
0006322593.tif 000006
【００５５】
また、２×２の線形変換行列Ｍ（ｃ）を定義し、以下（８）式及び（９）式によって算出する。
【００５６】
【数６】
0006322593.tif 000007
【００５７】
次に、変位ベクトルｔ＾（ｃ）＝［ｘ（ｃ）ｙ（ｃ）］Ｔを以下（１０）式によって算出する。
【００５８】
【数７】
0006322593.tif 000008
【００５９】
以上のようにして、幾何変換パラメータ算出部１５３２では、各第１対応点ｃに対して、拡大縮小倍率σ（ｃ）、回転角度θ（ｃ）、及び変位ベクトルｔ＾（ｃ）を算出することにより、以下（１１）式に示す計４次元の幾何変換パラメータＦ（ｃ）を出力する。
【００６０】
【数８】
0006322593.tif 000009
【００６１】
パラメータ離散化部１５３４には、幾何変換パラメータ算出部１５３２により算出された幾何変換パラメータＦ（ｃ）、又は後述する擬似幾何変換パラメータ算出部１５３６により算出された擬似幾何変換パラメータＦｉ（ｊ）に基づいて、離散化区間であるＩＤ（Ｆ）を算出し、算出した離散化区間を投票ヒストグラム記憶部２５４０に記憶する。
【００６２】
パラメータ離散化部１５３４における具体的な処理を以下に説明する。まず、幾何変換パラメータや後述する擬似幾何変換パラメータを離散化して、投票先となる幾何変換空間の離散化区間を特定する。以下説明のため、上記（１１）式に示す幾何変換パラメータをＦ＝〈σ，θ，ｘ，ｙ〉に略して表記する。
【００６３】
拡大縮小倍率θは、以下（１２）式によって離散化され、離散化区間のＩＤβｓ（Ｆ） に変換される。σｍは、θの範囲を制御するパラメータであり、［１０，１５］の範囲にある実数に設定する。ｎｓは、σの離散化区間の数を表し、整数１６に設定する。βs（Ｆ）＝−１の場合、該当する対応点をノイズとみなし、進行中の処理を中断して次の繰り返しを開始する。
【００６４】
【数９】
0006322593.tif 000010
【００６５】
回転角度θは、以下（１３）式及び（１４）式によって離散化され、離散化区間のＩＤβｒ（Ｆ）に変換される。ｎｒは、θの離散化区間の数を表し、整数８に設定する。
【００６６】
【数１０】
0006322593.tif 000011
【００６７】
変位ベクトルの要素ｘ及びｙは、それぞれ以下（１５）式及び（１６）式によって離散化され、離散化区間のＩＤβｘ（Ｆ）とβｙ（Ｆ）に変換される。ρは、該当する対応点を含む入力画像の幅と高さの最大値を表す。δは、ｘ及びｙの範囲を制御するパラメータであり、［１．５，２．５］の範囲にある実数に設定する。ｎｘとｎｙは、それぞれｘとｙ の離散化区間の数を表し、両方とも整数１６に設定する。βｘ（Ｆ）＝−１もしくはβｙ（Ｆ）＝−１の場合、該当する対応点をノイズと見なし、進行中の処理を中断して次の繰り返しを開始する。
【００６８】
【数１１】
0006322593.tif 000012
【００６９】
従って、投票先となる幾何変換空間の離散化区間のＩＤβ（Ｆ）は、以下（１７）式によって算出できる。
【００７０】
【数１２】
0006322593.tif 000013
【００７１】
本実施形態では、（Ｆ）の可能値の数が８×１６３＝３２７６８となる。すなわち、後述する投票ヒストグラムを構成した離散化区間の数が３２７６８となる。
【００７２】
擬似幾何変換パラメータ算出部１５３６は、以下に説明するように、第１対応点の各々について、幾何変換パラメータ算出部１５３２により第１対応点から算出された幾何変換パラメータと、Ｋ近傍探索部１５３０により得られた第１対応点に対応する第２対応点の各々とに基づいて、当該第１対応点に対する第２対応点の各々に対し、擬似幾何変換パラメータを算出する。
【００７３】
擬似幾何変換パラメータ算出部１５３６においては、以下、第１対応点をｃｊで、ｃｊのｋ近傍集合をＮ（ｃｊ）で、第２対応点をｃｉ∈Ｎ（ｃｊ）で表す。ｃｉとｃｊのそれぞれから算出した幾何変換パラメータをそれぞれＦｉとＦｊで表す。擬似幾何変換パラメータ算出部１５３６における擬似幾何変換パラメータの算出処理を実行する前に、パラメータ離散化部１５３４による離散化結果に基づいて、以下（１８）式に示す条件が真であるか否かの判断を実行し、条件が真の場合には擬似幾何変換パラメータ算出部１５３６の擬似幾何変換パラメータの算出処理を実行し、そうでない場合には進行中の処理を中断して次の繰り返し処理を開始する。
【００７４】
【数１３】
0006322593.tif 000014
【００７５】
擬似幾何変換パラメータ算出部１５３６の具体的な処理について以下に説明する。まず、処理対象の第１対応点ｃｊと、当該第１対応点に対する第２対応点ｃｉの入力を受け付け、新たな擬似変位ベクトルｔ＾（ｃｉ｜ｃｊ）を以下（１９）式によって算出する。Ｍ（ｃｊ）は幾何変換パラメータ算出部１５３２により第１対応点ｃｊから算出した線形変換行列であり、ｔ＾（ｐｉ）及びｔ＾（ｐｊ）は第２対応点ｃｉを構成した２個の特徴点ｐｉ及びｐｊそれぞれの位置座標である。
【００７６】
【数１４】
0006322593.tif 000015
【００７７】
次に、Ｍ（ｃｊ）及びｔ（ｃｉ｜ｃｊ）を組み合わせ、新たな擬似幾何変換パラメータを作成する。
【００７８】
【数１５】
0006322593.tif 000016
【００７９】
従って、擬似幾何変換パラメータ算出部１５３６は、上記（２０）式に示すＦｉ（ｊ）を第２対応点ｃｉに対する擬似幾何変換パラメータと定義して出力する。
【００８０】
Ｌｏｏｋｕｐ Ｔａｂｌｅ作成部１５３８は、線形対数関数の差分係数のＬｏｏｋｕｐ Ｔａｂｌｅ（ＬＵＴ）を作成して出力する。線形対数関数は以下（２１）式で表される。
【００８１】
【数１６】
0006322593.tif 000017
【００８２】
Ｌｏｏｋｕｐ Ｔａｂｌｅ作成部１５３８においては、自然数ｙの各値について、以下（２２）式により算出する、線形対数関数の差分係数Δ（ｙ）の値を格納したＬｏｏｋｕｐ Ｔａｂｌｅを作成する。
【００８３】
【数１７】
0006322593.tif 000018
【００８４】
Ｌｏｏｋｕｐ Ｔａｂｌｅ作成部１５３８は、例えば、図７のＡｌｇｏｒｉｔｈｍ２に示す処理を実行することによりＬｏｏｋｕｐ Ｔａｂｌｅを作成する。
【００８５】
投票ヒストグラム作成部１５４０は、図８に示すように、幾何変換パラメータ又は擬似幾何変換パラメータの各々について幾何変換空間の離散化区間に投票して投票ヒストグラムを更新する投票ヒストグラム更新部２５３０と、Ｌｏｏｋｕｐ Ｔａｂｌｅを用いて入力画像のペア間の空間的類似度を更新する類似度更新部２５３２と、共通ビジュアルワード配列を更新する共通ビジュアルワード配列更新部２５３４と、投票ヒストグラム記憶部２５４０と、空間的類似度記憶部２５４２と、共通ビジュアルワード配列記憶部２５４４とを含んで構成されている。投票ヒストグラム作成部１５４０は、例えば、図９のＡｌｇｏｒｉｔｈｍ３に示す処理を実行することにより空間的類似度を更新する。また、投票ヒストグラム作成部１５４０においては、下記（２３）式の条件が真であるか否かの判断を実行する。
【００８６】
【数１８】
0006322593.tif 000019
【００８７】
ここで、β（Ｆｊ）は第１対応点ｃｊに対する幾何変換パラメータの離散化区間を、β（Ｆｊ（ｊ））は第２対応点ｃｉに対する擬似幾何変換パラメータの離散化区間を表す。上記（２３）式の条件が真の場合には投票ヒストグラム更新部２５３０、類似度更新部２５３２、及び共通ビジュアルワード配列更新部２５３４の処理を実行し、そうでない場合には進行中の処理を中断して、次の対応点に対する処理を行う。
【００８８】
投票ヒストグラム記憶部２５４０には、幾何変換空間における離散化区間の各々の投票値が記憶されている。なお、空間的類似度算出部５３０の処理を実行する前に、全ての離散化区間の投票値が整数の０に初期化されている（上記図６のＡｌｇｏｒｉｔｈｍ１の４行目を参照）。
【００８９】
空間的類似度記憶部２５４２には、類似度更新部２５３２により更新された空間的類似度が記憶される。なお、空間的類似度算出部５３０の処理を実行する前に、入力画像のペア間の空間的類似度が実数の０に初期化されている（上記図６のＡｌｇｏｒｉｔｈｍ１の２行目を参照）。
【００９０】
共通ビジュアルワード配列記憶部２５４４には、各離散化区間において投票された共通ビジュアルワード配列が記憶されている。共通ビジュアルワード配列は、３２７６８のビジュアルワード集合によって構成され、空間的類似度算出部５３０の処理を実行する前に、全てのビジュアルワード集合が空集合に初期化されている（Ａｌｇｏｒｉｔｈｍ１の５行目を参照）。記憶される。
【００９１】
投票ヒストグラム更新部２５３０は、幾何変換パラメータ算出部１５３２により第１対応点の各々について算出された幾何変換パラメータと、擬似幾何変換パラメータ算出部１５３６により第１対応点の各々に対する第２対応点の各々について算出された擬似幾何変換パラメータとについて、パラメータ離散化部１５３４により特定された幾何変換空間の離散化区間に投票して投票ヒストグラムを更新する。以下、説明のため第１対応点又は第２対応点を対応点と省略する。
【００９２】
投票ヒストグラム更新部２５３０は、具体的には以下の処理を行う。まず、投票ヒストグラム更新の処理を実行する前に、以下（２４）式に示す条件が真であるか否かの判断を実行する。
【００９３】
【数１９】
0006322593.tif 000020
【００９４】
ここで、ｕ（ｃ）は、処理対象となっている幾何変換パラメータ又は擬似幾何変換パラメータに対する対応点ｃのビジュアルワードを、β（Ｆ（ｃ））は対応点ｃに対する幾何変換パラメータ又は擬似幾何変換パラメータの離散化区間を表す。Ｘ（・）は、共通ビジュアルワード配列記憶部２５４４に記憶されている共通ビジュアルワード配列を表し、投票ヒストグラムを構成した各離散化区間において、当該離散化区間に既に投票された幾何変換パラメータ又は擬似幾何変換パラメータに対する対応点のビジュアルワードが記録される。上記（２４）式の条件が真の場合には投票ヒストグラム更新部２５３０の投票ヒストグラム更新処理を実行し、そうでない場合には進行中の処理を中断して、次の対応点に対する処理を行う。
【００９５】
投票ヒストグラム更新部２５３０は、上記（２４）式の条件が真の場合は、処理対象となっている幾何変換パラメータ又は擬似幾何変換パラメータについて、投票ヒストグラム記憶部２５４０に記憶されている幾何変換空間の離散化区間に投票して投票ヒストグラムを更新する。
【００９６】
また、投票ヒストグラム更新部２５３０には、処理対象の処理対象となっている幾何変換パラメータ又は擬似幾何変換パラメータについての離散化区間β（Ｆ）が入力される。投票ヒストグラム記憶部２５４０に記憶されている投票ヒストグラムにおいて、離散化区間β（Ｆ）の投票値ｈ（ｂ）に対し、１だけインクリメントし、投票ヒストグラムを更新する。更新した投票値を出力し、後述する類似度更新部２５３２に出力する。なお、本実施形態では、投票ヒストグラムは、３２７６８の離散化区間によって構成されている。
【００９７】
類似度更新部２５３２は、投票ヒストグラム更新部２５３０による投票値の更新に基づいて、入力画像のペア間の類似度を更新することを繰り返して、入力画像のペア間の類似度を算出する。
【００９８】
類似度更新部２５３２では、以下に説明するように、入力画像のペア間の類似度は、投票ヒストグラムの情報量と、一様分布の情報量との差分により表すことができる。ここでは、投票ヒストグラムをｈで、離散化区間をｂで、ｂに対する投票値をｈ（ｂ）で表す。一様分布の情報量は以下（２５）式で表される。
【００９９】
【数２０】
0006322593.tif 000021
【０１００】
また、投票ヒストグラムの情報量は以下（２６）式により表される。
【０１０１】
【数２１】
0006322593.tif 000022
【０１０２】
そして、類似度更新部２５３２では、以下（２７）式により、一様分布の情報量と投票ヒストグラムの情報量との差分を、空間的類似度Ｄとして表すことができる。
【０１０３】
【数２２】
0006322593.tif 000023
【０１０４】
類似度更新部２５３２では、Ｌｏｏｋｕｐ Ｔａｂｌｅ作成部１５３８で作成されたＬｏｏｋｕｐ Ｔａｂｌｅを用いて、投票ヒストグラム更新部２５３０により更新された投票値ｈ（ｂ）に対する差分係数Δ（ｙ）を取得し、以下（２８）式に従って、入力画像のペア間の空間的類似度を更新する。
【０１０５】
【数２３】
0006322593.tif 000024
【０１０６】
ここで、ｙは、投票ヒストグラム更新部２５３０により更新された投票値ｈ（ｂ）を表す。
【０１０７】
共通ビジュアルワード配列更新部２５３４は、共通ビジュアルワード配列記憶部２５４４に記憶されている離散化区間β（Ｆ）の共通ビジュアルワード配列に対して、処理対象となる幾何変換パラメータ又は擬似幾何変換パラメータに対する対応点ｃのビジュアルワードｕ（ｃ）を挿入し、共通ビジュアルワード配列を更新する。
【０１０８】
加重平均部５３２は、前処理装置１００から受け付けたＴＦ−ＩＤＦ類似度と、空間的類似度算出部５３０により算出された空間的類似度との加重平均を算出する。入力画像のペア間のＴＦ−ＩＤＦ類似度をＤｔｆｉｄｆで、空間的類似度をＤで表す場合、入力画像のペア間の全般的類似度Ｄｏｖｅｒａｌｌを、以下（２９）式によって算出する。
【０１０９】
【数２４】
0006322593.tif 000025
【０１１０】
ここで、ｗは、ＴＦ−ＩＤＦ類似度と空間的類似度の重みを制御するパラメータで、本実施形態では、［０．５，１］の範囲にある実数に設定する。
【０１１１】
＜本発明の実施の形態に係る画像照合装置の作用＞
【０１１２】
次に、本発明の実施の形態に係る画像照合装置５００の作用について説明する。前処理装置１００により出力された、入力画像のペア間の対応点の集合及びＴＦ−ＩＤＦ類似度を受け付けると、画像照合装置５００は、図１０及び図１１に示す画像照合処理ルーチンを実行する。
【０１１３】
まず、ステップＳ１００では、自然数ｙの各値について、上記（２２）式に従って、線形対数関数の差分係数Δ（ｙ）の値を算出して、Ｌｏｏｋｕｐ Ｔａｂｌｅに格納する。
【０１１４】
ステップＳ１０２では、入力画像のペア間の空間的類似度Ｄを０に初期化して空間的類似度記憶部２５４２に記憶する。
【０１１５】
ステップＳ１０４では、幾何変換空間における各離散化区間の投票値を０に初期化して投票ヒストグラム記憶部２５４０に記憶する。
【０１１６】
ステップＳ１０６では、共通ビジュアルワード配列におけるビジュアルワード集合を空集合に初期化して共通ビジュアルワード配列記憶部２５４４に記憶する。
【０１１７】
ステップＳ１０８では、受け付けた入力画像のペア間の対応点の集合に含まれる対応点の各々に対して、当該対応点を第１対応点とし、位置座標空間において最も近いｋ個の第２対応点を得る。
【０１１８】
ステップＳ１１０では、受け付けた対応点の集合から処理対象とする第１対応点を選択する。
【０１１９】
ステップＳ１１２では、ステップＳ１１０で選択した第１対応点について、幾何変換パラメータを算出する。
【０１２０】
ステップＳ１１４では、ステップＳ１１２で算出された第１対応点の幾何変換パラメータを離散化して、投票先となる幾何変換空間の離散化区間を特定する。
【０１２１】
ステップＳ１１５では、第１対応点のビジュアルワードｕ（ｃ）について、上記（２４）式に示す条件が真かを判定し、真であればステップＳ１１６へ移行し、真でなければステップＳ１２２へ移行する。
【０１２２】
ステップＳ１１６では、ステップＳ１１２で算出された幾何変換パラメータについて、ステップＳ１１４で特定された第１対応点に対する離散化区間に投票し、投票値ｈ（ｂ）を１だけインクリメントして投票ヒストグラムを更新し、投票ヒストグラム記憶部２５４０に記憶する。
【０１２３】
ステップＳ１１８では、ステップＳ１００で算出したＬｏｏｋｕｐ Ｔａｂｌｅを用いて、ステップＳ１１６で更新された投票値ｈ（ｂ）に対する差分係数Δ（ｙ）を取得し、上記（２８）式に従って、空間的類似度Ｄを更新して、空間的類似度記憶部２５４２に記憶する。
【０１２４】
ステップＳ１２０では、共通ビジュアルワード配列記憶部２５４４に記憶されている共通ビジュアルワード配列の、上記ステップ１１４で特定された離散化区間に対応する要素に対して、ステップＳ１１２で算出された幾何変換パラメータに対する対応点ｃのビジュアルワードｕ（ｃ）を挿入し、共通ビジュアルワード配列を更新する。
【０１２５】
ステップＳ１２２では、ステップＳ１０８で得た、第１対応点に対する第２対応点の何れか１つを選択する。
【０１２６】
ステップＳ１２４では、離散化区間について、上記（１８）式の条件が真かを判定し、真であればステップＳ１２８へ移行し、真でなければステップＳ１３８へ移行する。
【０１２７】
ステップＳ１２６では、ステップＳ１１２で算出された幾何変換パラメータに基づいて、ステップＳ１２２で選択した第２対応点について、擬似幾何変換パラメータを算出する。
【０１２８】
ステップＳ１２８では、ステップＳ１２６で算出された第２対応点の擬似幾何変換パラメータを離散化して、投票先となる幾何変換空間の離散化区間を特定する。
【０１２９】
ステップＳ１２９では、離散化区間について、上記（２３）式が真かを判定し、真であればステップＳ１３０へ移行し、真でなければステップＳ１３８へ移行する。
【０１３０】
ステップＳ１３０では、第２対応点のビジュアルワードｕ（ｃ）について、上記（２４）式が真かを判定し、真であればステップＳ１３２へ移行し、真でなければステップＳ１３８へ移行する。
【０１３１】
ステップＳ１３２では、ステップＳ１２６で算出された擬似幾何変換パラメータについて、ステップＳ１２８で特定された第２対応点に対する離散化区間に投票し、投票値ｈ（ｂ）を１だけインクリメントして投票ヒストグラムを更新し、投票ヒストグラム記憶部２５４０に記憶する。
【０１３２】
ステップＳ１３４では、ステップＳ１００で算出したＬｏｏｋｕｐ Ｔａｂｌｅを用いて、ステップＳ１３２で更新された投票値ｈ（ｂ）に対する差分係数Δ（ｙ）を取得し、上記（２８）式に従って、空間的類似度Ｄを更新して、空間的類似度記憶部２５４２に記憶する。
【０１３３】
ステップＳ１３６では、共通ビジュアルワード配列記憶部２５４４に記憶されている共通ビジュアルワード配列の、上記ステップ１２８で特定された離散化区間に対応する要素に対して、ステップＳ１２６で算出された擬似幾何変換パラメータに対する第２対応点ｃのビジュアルワードｕ（ｃ）を挿入し、共通ビジュアルワード配列を更新する。
【０１３４】
ステップＳ１３８では、ステップＳ１１０で選択した第１対応点に対するすべての第２対応点について処理を終了したかを判定し、終了していればステップＳ１４０へ移行し、終了していなければステップＳ１２２へ移行して次の第２対応点を選択して処理を繰り返す。
【０１３５】
ステップＳ１４０では、すべての第１対応点について処理を終了したかを判定し、終了していればステップＳ１４０へ移行し、終了していなければステップＳ１１０へ移行して次の第１対応点を選択して処理を繰り返す。
【０１３６】
ステップＳ１４２では、最終的に得られた算出された空間的類似度Ｄと、受け付けたＴＦ−ＩＤＦ類似度との加重平均を算出し、本ステップの算出結果、並びにステップＳ１１６及びステップＳ１３２で更新した投票ヒストグラムを出力部５５０に出力して処理を終了する。
【０１３７】
以上説明したように、本発明に実施の形態に係る画像照合装置によれば、第１対応点の各々について、幾何変換パラメータを算出し、幾何変換パラメータと、第１対応点と異なる第２対応点とに基づいて、擬似幾何変換パラメータを算出し、幾何変換パラメータ又は擬似幾何変換パラメータについて幾何変換空間の離散化区間を特定し、幾何変換パラメータと、擬似幾何変換パラメータとについて、幾何変換空間の離散化区間に投票することにより、入力画像のペア間の類似度を求めるための投票ヒストグラムを作成することで、精度よく、画像間の類似度を求めることができる。
【０１３８】
また、上述した実施の形態に係る手法により投票ヒストグラムを作成することにより、非特許文献１及び非特許文献２に開示されている画像照合装置と比べて、非関連画像間の特徴点の誤合致への弁別力をより高く保つことが可能である。
【０１３９】
また、上述した実施の形態に係る手法により投票ヒストグラムを作成することにより、非特許文献３に開示されている画像照合装置と比べて、関連画像における特徴点抽出の誤差とハフ変換におけるパラメータ離散化の誤差をより効果的に吸収可能である。
【０１４０】
また、上述した実施の形態に係る手法により、第１対応点のｋ個の近傍となる第２対応点から算出した擬似幾何変換パラメータを用いて投票ヒストグラムを作成することにより、非関連画像間の特徴点の誤合致への弁別力をより高く保つことが可能である。
【０１４１】
また、上述した実施の形態に係る手法により、投票ヒストグラムを作成するだけでなく、空間的類似度を算出することにより、関連画像間の幾何変換が複数存在する場合でも、空間的類似度をより正確に算出することが可能になり、より効果的に画像を照合可能である。
【０１４２】
また、上述した実施の形態に係る手法により、投票ヒストグラムを作成するだけでなく、空間的類似度を算出することにより、ハフ変換におけるパラメータ離散化の誤差をより効果的に吸収することが可能である。
【０１４３】
また、上述した実施の形態に係る手法により、Ｌｏｏｋｕｐ Ｔａｂｌｅを用いて更新された投票値ｈ（ｂ）に対する差分係数Δ（ｙ）を取得して空間的類似度を更新することを繰り返して空間的類似度を算出することにより、ハフ変換処理と投票ヒストグラムに基づく類似度算出処理とを同時に実行することが可能であり、空間的類似度の算出を連続的に離散化区間ごとに実行する場合に比べて、より少ない計算量で実行可能であり、より速い処理速度を実現可能である。
【０１４４】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１４５】
例えば、上述した実施の形態では、算出された空間的類似度と、ＴＦ−ＩＤＦ類似度との加重平均を算出する場合を例に説明したが、これに限定されるものではなく、ＴＦ−ＩＤＦ類似度を算出せず、加重平均を行わなくてもよい。
【０１４６】
また、上述した実施の形態では、前処理装置１００で入力画像のペア間について作成した対応点集合を受け付けて、受け付けた対応点集合に基づいて、入力画像のペア間の投票ヒストグラムを作成し、空間的類似度を算出する場合を例に説明したが、これに限定されるものではなく、画像照合装置が、入力画像のペア間について対応点集合を作成して、入力画像のペア間の投票ヒストグラムを作成し、空間的類似度を算出するようにしてもよい。
【０１４７】
また、Ｌｏｏｋｕｐ Ｔａｂｌｅを用いて更新された投票値ｈ（ｂ）に対する差分係数Δ（ｙ）を取得して空間的類似度を更新する場合を例に説明したが、これに限定されるものではなく、Ｌｏｏｋｕｐ Ｔａｂｌｅを用いずに、更新された投票値ｈ（ｂ）に対する差分係数Δ（ｙ）を算出して空間的類似度を更新するようにしてもよい。
【０１４８】
また、更新された投票値ｈ（ｂ）に対する差分係数Δ（ｙ）を取得して空間的類似度を更新することを繰り返す場合を例に説明したが、これに限定されるものではなく、最終的に生成された投票ヒストグラムに基づいて、上記（２７）式に従って、類似度を算出するようにしてもよい。
【符号の説明】
【０１４９】
２０、５２０  演算部
２８   ビジュアルワード辞書
３０   ビジュアルワード作成部
３２   類似度算出部
３４   対応点抽出部
１００ 前処理装置
２３０ 特徴点抽出部
２３２ 局所特徴量算出部
２３４ 局所特徴量量子化部
３３０ ＴＦ−ＩＤＦ算出部
３３２ コサイン類似度算出部
５００ 画像照合装置
５３０ 空間的類似度算出部
５３２ 加重平均部
５５０ 出力部
１５３０      近傍探索部
１５３２      幾何変換パラメータ算出部
１５３４      パラメータ離散化部
１５３６      擬似幾何変換パラメータ算出部
１５３８      Ｌｏｏｋｕｐ Ｔａｂｌｅ作成部
１５４０      投票ヒストグラム作成部
２５３０      投票ヒストグラム更新部
２５３２      類似度更新部
２５３４      共通ビジュアルワード配列更新部
２５４０      投票ヒストグラム記憶部
２５４２      空間的類似度記憶部
２５４４      共通ビジュアルワード配列記憶部
【図１】
0006322593.tif 000027
【図２】
0006322593.tif 000028
【図３】
0006322593.tif 000029
【図４】
0006322593.tif 000030
【図５】
0006322593.tif 000031
【図６】
0006322593.tif 000032
【図７】
0006322593.tif 000033
【図８】
0006322593.tif 000034
【図９】
0006322593.tif 000035
【図１０】
0006322593.tif 000036
【図１１】
0006322593.tif 000037