(57)【要約】  画像照合装置は、入力画像のペア間において対応する特徴点のペアである複数の暫定対応点を抽出する暫定対応点抽出部と、暫定対応点抽出部によって抽出された暫定対応点の組み合わせである暫定対応点のペアの各々について、暫定対応点の幾何変換パラメータの比較又は差分に基づく、拡大縮小倍率の整合性に関する制約条件、回転角度の整合性に関する制約条件、及び相対位置関係の整合性に関する制約条件の全てに基づいて入力画像のペア間の類似度を評価する空間検証部と、を含む。
2017006852.tif 000002
【特許請求の範囲】
【請求項１】
入力画像のペア間において対応する特徴点のペアである複数の暫定対応点を抽出する暫定対応点抽出部と、
前記暫定対応点抽出部によって抽出された前記暫定対応点の組み合わせである前記暫定対応点のペアの各々について、前記暫定対応点の幾何変換パラメータの比較又は差分に基づく、拡大縮小倍率の整合性に関する制約条件、回転角度の整合性に関する制約条件、及び相対位置関係の整合性に関する制約条件の全てに基づいて前記入力画像のペア間の類似度を評価する空間検証部と、
を含む画像照合装置。
【請求項２】
前記暫定対応点のペアの各々から、前記暫定対応点のペアにおける前記特徴点それぞれのｋ近傍の前記特徴点の集合に基づいて、近傍同士となる前記暫定対応点のペアを抽出するＫ近傍探索部を更に含み、
前記空間検証部は、前記Ｋ近傍探索部によって抽出された、近傍同士となる前記暫定対応点のペアの各々に対する制約条件の全てに基づいて前記入力画像のペア間の類似度を評価する、
請求項１記載の画像照合装置。
【請求項３】
前記拡大縮小倍率の整合性に関する制約条件は、
前記暫定対応点のペアをなす第１及び第２の暫定対応点における前記特徴点と前記入力画像のペアをなす第１及び第２の入力画像とに関し、
前記第１の入力画像内における前記特徴点のスケールの大小関係と、前記第２の入力画像内における前記特徴点のスケールの大小関係とにおいて、前記第１又は第２の暫定対応点のいずれか一方の前記特徴点のスケールがともに大きいか、又は、
前記第１の暫定対応点における前記特徴点のスケールの大小関係と、前記第２の暫定対応点における前記特徴点のスケールの大小関係とにおいて、前記第１又は第２の入力画像のいずれか一方の前記特徴点のスケールがともに大きいことである、
請求項１記載の画像照合装置。
【請求項４】
前記回転角度の整合性に関する制約条件は、
前記暫定対応点のペアをなす第１及び第２の暫定対応点における前記特徴点と前記入力画像のペアをなす第１及び第２の入力画像とに関し、
前記第１の入力画像における前記第１の暫定対応点の特性角と前記第２の入力画像における前記第１の暫定対応点の特性角との差である第１の回転角度と、前記第１の入力画像における前記第２の暫定対応点の特性角と前記第２の入力画像における前記第２の暫定対応点の特性角との差である第２の回転角度との差分の絶対値が予め定められた第１の閾値より小さいことである、
請求項１記載の画像照合装置。
【請求項５】
前記相対位置関係の整合性に関する制約条件は、
前記暫定対応点のペアをなす第１及び第２の暫定対応点それぞれの前記特徴点と前記入力画像のペアをなす第１及び第２の入力画像とに関し、
前記第１の入力画像における前記第１の暫定対応点の前記特徴点と前記第２の暫定対応点の前記特徴点との位置の差を示す第１の相対位置ベクトルと、前記第２の入力画像における前記第１の暫定対応点の前記特徴点と前記第２の暫定対応点の前記特徴点との位置の差を示す第２の相対位置ベクトルとの差分である差分ベクトルの長さの最大値が予め定められた第２の閾値より小さいこと、
前記第１及び第２の相対位置ベクトルを極座標に変換して得られる動径それぞれが予め定められた第３の閾値より大きいこと、及び、
前記第１及び第２の相対位置ベクトルを極座標に変換して得られる偏角の差分の絶対値が予め定められた第４の閾値より小さいこと、である、
請求項１に記載の画像照合装置。
【請求項６】
前記空間検証部は、前記拡大縮小倍率の整合性に関する制約条件、前記回転角度の整合性に関する制約条件、及び前記相対位置関係の整合性に関する制約条件の全てを満たす前記暫定対応点のペアに基づいて、前記入力画像のペア間の類似度を評価する、
請求項１記載の画像照合装置。
【請求項７】
暫定対応点抽出部及び空間検証部を含む画像照合装置における画像照合方法であって、
前記暫定対応点抽出部によって、入力画像のペア間において対応する特徴点のペアである複数の暫定対応点を抽出し、
前記空間検証部によって、前記暫定対応点抽出部によって抽出された前記暫定対応点の組み合わせである前記暫定対応点のペアの各々について、前記暫定対応点の幾何変換パラメータの比較又は差分に基づく、拡大縮小倍率の整合性に関する制約条件、回転角度の整合性に関する制約条件、及び相対位置関係の整合性に関する制約条件の全てに基づいて前記入力画像のペア間の類似度を評価する、
画像照合方法。
【請求項８】
前記画像照合装置は更にＫ近傍探索部を含み、
前記Ｋ近傍探索部によって、前記暫定対応点のペアの各々から、前記暫定対応点のペアにおける前記特徴点それぞれのｋ近傍の前記特徴点の集合に基づいて、近傍同士となる前記暫定対応点のペアを抽出し、
前記空間検証部は、前記Ｋ近傍探索部によって抽出された、近傍同士となる前記暫定対応点のペアの各々に対する制約条件の全てに基づいて前記入力画像のペア間の類似度を評価する、
請求項７記載の画像照合方法。
【請求項９】
前記拡大縮小倍率の整合性に関する制約条件は、
前記暫定対応点のペアをなす第１及び第２の暫定対応点における前記特徴点と前記入力画像のペアをなす第１及び第２の入力画像とに関し、
前記第１の入力画像内における前記特徴点のスケールの大小関係と、前記第２の入力画像内における前記特徴点のスケールの大小関係とにおいて、前記第１又は第２の暫定対応点のいずれか一方の前記特徴点のスケールがともに大きいか、又は、
前記第１の暫定対応点における前記特徴点のスケールの大小関係と、前記第２の暫定対応点における前記特徴点のスケールの大小関係とにおいて、前記第１又は第２の入力画像のいずれか一方の前記特徴点のスケールがともに大きいことである、
請求項７記載の画像照合方法。
【請求項１０】
前記回転角度の整合性に関する制約条件は、
前記暫定対応点のペアをなす第１及び第２の暫定対応点における前記特徴点と前記入力画像のペアをなす第１及び第２の入力画像とに関し、
前記第１の入力画像における前記第１の暫定対応点の特性角と前記第２の入力画像における前記第１の暫定対応点の特性角との差である第１の回転角度と、前記第１の入力画像における前記第２の暫定対応点の特性角と前記第２の入力画像における前記第２の暫定対応点の特性角との差である第２の回転角度との差分の絶対値が予め定められた第１の閾値より小さいことである、
請求項７記載の画像照合方法。
【請求項１１】
前記相対位置関係の整合性に関する制約条件は、
前記暫定対応点のペアをなす第１及び第２の暫定対応点それぞれの前記特徴点と前記入力画像のペアをなす第１及び第２の入力画像とに関し、
前記第１の入力画像における前記第１の暫定対応点の前記特徴点と前記第２の暫定対応点の前記特徴点との位置の差を示す第１の相対位置ベクトルと、前記第２の入力画像における前記第１の暫定対応点の前記特徴点と前記第２の暫定対応点の前記特徴点との位置の差を示す第２の相対位置ベクトルとの差分である差分ベクトルの長さの最大値が予め定められた第２の閾値より小さいこと、
前記第１及び第２の相対位置ベクトルを極座標に変換して得られる動径それぞれが予め定められた第３の閾値より大きいこと、及び、
前記第１及び第２の相対位置ベクトルを極座標に変換して得られる偏角の差分の絶対値が予め定められた第４の閾値より小さいこと、である、
請求項７記載の画像照合方法。
【請求項１２】
前記空間検証部は、前記拡大縮小倍率の整合性に関する制約条件、前記回転角度の整合性に関する制約条件、及び前記相対位置関係の整合性に関する制約条件の全てを満たす前記暫定対応点のペアに基づいて、前記入力画像のペア間の類似度を評価する、
請求項７記載の画像照合方法。
【請求項１３】
コンピュータを、請求項１記載の画像照合装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像照合装置、画像照合方法、及びプログラムに係り、特に、画像間の類似度を求めるための画像照合装置、画像照合方法、及びプログラムに関する。
本願は、２０１５年７月６日に、日本に出願された特願２０１５−１３５２９７号に基づき優先権を主張し、その内容をここに援用する。
【背景技術】
【０００２】
局所特徴量に基づく画像照合は、２枚の入力画像から抽出した多数の特徴点から局所特徴量を算出し、第１画像の特徴点と第２画像の特徴点とを比較し、局所特徴量の類似度が高いか否かを判定する技術である。画像照合によって、同一画像検索や類似画像検索、又は画像認識等の課題が実現可能となる。以下、第１画像と、第１画像に写っている物体と異なる物体を写した第２画像のペアを、非関連画像と呼ぶ。第１画像と、第１画像に写っている物体と同一の物体を写した第２画像のペアを、関連画像と呼ぶ。既存技術では、２枚の非関連画像に対して、市松模様のような繰り返しパターンや肌理の細かい模様等が両方の画像に含まれる場合、画像の間で誤って合致する特徴点が多く存在するため、非関連画像が関連画像であると誤認されることが多い。【０００３】
前記問題の影響を抑えるために、空間関係や幾何変換等の整合性を考慮した画像照合装置が発明されている。空間関係とは、特徴点の間の近接関係や相対位置関係等のことである。以下、２枚の画像の間において、局所特徴量の類似度が高い特徴点のペアを、暫定対応点と呼ぶ。幾何変換とは、暫定対応点を構成した２点の特徴点の幾何特性から算出した線形変換パラメータや変位ベクトル等のことである。以下、暫定対応点のうち、空間関係や幾何変換等の制約条件を満たすものを、正対応点と呼ぶ。【０００４】
非特許文献１、２に開示されている画像照合装置は、入力画像内の特徴点の位置座標空間における近傍を探索する処理と、近傍同士となる特徴点のペアから相対位置ベクトルを算出する処理と、相対位置ベクトルを量子化する処理と、特徴点の局所特徴量を量子化する処理と、量子化の結果に基づいて転置インデックスを作成する処理と、転置インデックスによって正対応点のペアを同定する処理と、正対応点のペアに基づいて画像間の類似度を算出する処理によって構成される。非特許文献３に開示されている画像照合装置は、入力画像間の暫定対応点から拡大縮小、回転、変位を表す幾何変換パラメータを算出する処理と、幾何変換パラメータを量子化する処理と、量子化の結果に基づいて投票ヒストグラムを作成する処理と、投票ヒストグラムに基づいて画像間の類似度を算出する処理によって構成されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Zhen Liu, Houqiang Li, Wengang Zhou, and Qi Tian. Embedding spatial context information into inverted file for large-scale image retrieval. In ACM Multimedia, pp.199-208, 2012.
【非特許文献２】Xiaomeng Wu and Kunio Kashino. Image retrieval based on anisotropic scaling and shearing invariant geometric coherence. In ICPR, pp. 3951-3956, 2014.
【非特許文献３】Yannis S. Avrithis and Giorgos Tolias. 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.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１、２に開示されている画像照合装置は、入力画像内の特徴点のペアに着目し、「近接関係の整合性」と「相対位置関係の整合性」、計２種類の空間関係の制約を用いて正対応点のペアを同定する。非特許文献３に開示されている画像照合装置は、入力画像間の暫定対応点に着目し、「拡大縮小倍率の整合性」、「回転角度の整合性」、「変位ベクトルの整合性」、計３種類の幾何変換の制約を用いて誤って合致した暫定対応点を除去する。以下、空間関係の制約と幾何変換の制約を総じて空間制約と呼ぶ。前記既存技術では、正対応点の同定に用いる空間制約の数と種類が限られているため、誤って合致した暫定対応点への識別力が不充分な場合が多い。量子化の解像度を上げるなど、空間制約の強度を強制的に高める方法が考えられるが、正対応点の探索漏れや過剰除去等が生じる。正対応点の探索漏れ等を回避しつつ、誤って合致した暫定対応点への識別力をいかに高められるかが、本発明で解決する第１の課題である。【０００７】
空間関係の制約と幾何変換の制約を結合すれば、前記課題を解決できるが、既存技術では、両方を組み合わせるのが困難である。例えば、非特許文献１、２に開示されている画像照合装置は、暫定対応点を抽出する前に、入力画像内の特徴点のペアに着目し、そのペアから空間関係の特徴量を算出する。この技術を利用する段階では、暫定対応点がまだ抽出されていないため、幾何変換パラメータの算出が不可能である。従って、この技術に幾何変換の制約を加えることが不可能である。一方、非特許文献３に開示されている画像照合装置は、暫定対応点を抽出した後に、入力画像間の暫定対応点に着目し、幾何変換パラメータを算出する。その後、各単一の暫定対応点を、その幾何変換パラメータに相当するパラメータ区間に投票し、投票ヒストグラムを作成する。この投票は、各単一の暫定対応点でなければできないのに対して、空間関係の特徴量の算出は、少なくとも二つの対応点がなければできない。従って、この技術に空間関係の制約を加えることが不可能である。【０００８】
空間関係の制約を用いる画像照合装置（非特許文献１、２）は、入力画像内の特徴点のペアを対象に特徴量算出とインデックス作成を行うため、画像照合の際に必要となるメモリ使用量と探索空間の大きさ（探索の所要時間の長さ）が特徴点のペアの数に比例する。例えば、千枚の画像がデータベースにある場合、メモリ使用量が約８ＧＢであり、百万枚の画像の場合、約８ＴＢとなる。探索の正確性を犠牲にせず、メモリ使用量と探索空間（探索の所要時間）をいかに抑制できるかが、本発明で解決する第２の課題である。【０００９】
本発明は、上記課題を解決するために成されたものであり、非関連画像間の特徴点の合致数が高く、関連画像間の幾何変換が大きい場合でも、正確且つ高速に画像を照合することができる画像照合装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の第１の実施態様は、入力画像のペア間において対応する特徴点のペアである複数の暫定対応点を抽出する暫定対応点抽出部と、前記暫定対応点抽出部によって抽出された前記暫定対応点の組み合わせである前記暫定対応点のペアの各々について、前記暫定対応点の幾何変換パラメータの比較又は差分に基づく、拡大縮小倍率の整合性に関する制約条件、回転角度の整合性に関する制約条件、及び相対位置関係の整合性に関する制約条件の全てに基づいて前記入力画像のペア間の類似度を評価する空間検証部と、を含む画像照合装置である。【００１１】
本発明の第２の実施態様は、上記第１の実施態様の画像照合装置において、前記暫定対応点のペアの各々から、前記暫定対応点のペアにおける前記特徴点それぞれのｋ近傍の前記特徴点の集合に基づいて、近傍同士となる前記暫定対応点のペアを抽出するＫ近傍探索部を更に含み、前記空間検証部は、前記Ｋ近傍探索部によって抽出された、近傍同士となる前記暫定対応点のペアの各々に対する制約条件の全てに基づいて前記入力画像のペア間の類似度を評価する。【００１２】
本発明の第３の実施態様は、上記第１又は第２の実施態様の画像照合装置において、前記拡大縮小倍率の整合性に関する制約条件は、前記暫定対応点のペアをなす第１及び第２の暫定対応点における前記特徴点と前記入力画像のペアをなす第１及び第２の入力画像とに関し、前記第１の入力画像内における前記特徴点のスケールの大小関係と、前記第２の入力画像内における前記特徴点のスケールの大小関係とにおいて、前記第１又は第２の暫定対応点のいずれか一方の前記特徴点のスケールがともに大きいか、又は、前記第１の暫定対応点における前記特徴点のスケールの大小関係と、前記第２の暫定対応点における前記特徴点のスケールの大小関係とにおいて、前記第１又は第２の入力画像のいずれか一方の前記特徴点のスケールがともに大きいことである。【００１３】
本発明の第４の実施態様は、上記第１から第３の実施態様のいずれか一つの画像照合装置において、前記回転角度の整合性に関する制約条件は、前記暫定対応点のペアをなす第１及び第２の暫定対応点における前記特徴点と前記入力画像のペアをなす第１及び第２の入力画像とに関し、前記第１の入力画像における前記第１の暫定対応点の特性角と前記第２の入力画像における前記第１の暫定対応点の特性角との差である第１の回転角度と、前記第１の入力画像における前記第２の暫定対応点の特性角と前記第２の入力画像における前記第２の暫定対応点の特性角との差である第２の回転角度との差分の絶対値が予め定められた第１の閾値より小さいことである。【００１４】
本発明の第５の実施態様は、上記第１から第４の実施態様のいずれか一つの画像照合装置において、前記相対位置関係の整合性に関する制約条件は、前記暫定対応点のペアをなす第１及び第２の暫定対応点それぞれの前記特徴点と前記入力画像のペアをなす第１及び第２の入力画像とに関し、前記第１の入力画像における前記第１の暫定対応点の前記特徴点と前記第２の暫定対応点の前記特徴点との位置の差を示す第１の相対位置ベクトルと、前記第２の入力画像における前記第１の暫定対応点の前記特徴点と前記第２の暫定対応点の前記特徴点との位置の差を示す第２の相対位置ベクトルとの差分である差分ベクトルの長さの最大値が予め定められた第２の閾値より小さいこと、前記第１及び第２の相対位置ベクトルを極座標に変換して得られる動径それぞれが予め定められた第３の閾値より大きいこと、及び、前記第１及び第２の相対位置ベクトルを極座標に変換して得られる偏角の差分の絶対値が予め定められた第４の閾値より小さいこと、である。【００１５】
本発明の第６の実施態様は、上記第１から第５の実施態様のいずれか一つの画像照合装置において、前記空間検証部は、前記拡大縮小倍率の整合性に関する制約条件、前記回転角度の整合性に関する制約条件、及び前記相対位置関係の整合性に関する制約条件の全てを満たす前記暫定対応点のペアに基づいて、前記入力画像のペア間の類似度を評価する。【００１６】
本発明の第７の実施態様は、暫定対応点抽出部及び空間検証部を含む画像照合装置における画像照合方法であって、前記暫定対応点抽出部によって、入力画像のペア間において対応する特徴点のペアである複数の暫定対応点を抽出し、前記空間検証部によって、前記暫定対応点抽出部によって抽出された前記暫定対応点の組み合わせである前記暫定対応点のペアの各々について、前記暫定対応点の幾何変換パラメータの比較又は差分に基づく、拡大縮小倍率の整合性に関する制約条件、回転角度の整合性に関する制約条件、及び相対位置関係の整合性に関する制約条件の全てに基づいて前記入力画像のペア間の類似度を評価する、画像照合方法である。【００１７】
本発明の第８の実施態様は、上記第７の実施態様の画像照合方法において、前記画像照合装置は更にＫ近傍探索部を含み、前記Ｋ近傍探索部によって、前記暫定対応点のペアの各々から、前記暫定対応点のペアにおける前記特徴点それぞれのｋ近傍の前記特徴点の集合に基づいて、近傍同士となる前記暫定対応点のペアを抽出し、前記空間検証部は、前記Ｋ近傍探索部によって抽出された、近傍同士となる前記暫定対応点のペアの各々に対する制約条件の全てに基づいて前記入力画像のペア間の類似度を評価する。【００１８】
本発明の第９の実施態様は、上記第７又は第８の実施態様の画像照合方法において、前記拡大縮小倍率の整合性に関する制約条件は、前記暫定対応点のペアをなす第１及び第２の暫定対応点における前記特徴点と前記入力画像のペアをなす第１及び第２の入力画像とに関し、前記第１の入力画像内における前記特徴点のスケールの大小関係と、前記第２の入力画像内における前記特徴点のスケールの大小関係とにおいて、前記第１又は第２の暫定対応点のいずれか一方の前記特徴点のスケールがともに大きいか、又は、前記第１の暫定対応点における前記特徴点のスケールの大小関係と、前記第２の暫定対応点における前記特徴点のスケールの大小関係とにおいて、前記第１又は第２の入力画像のいずれか一方の前記特徴点のスケールがともに大きいことである。【００１９】
本発明の第１０の実施態様は、上記第７から第９の実施態様のいずれか一つの画像照合方法において、前記回転角度の整合性に関する制約条件は、前記暫定対応点のペアをなす第１及び第２の暫定対応点における前記特徴点と前記入力画像のペアをなす第１及び第２の入力画像とに関し、前記第１の入力画像における前記第１の暫定対応点の特性角と前記第２の入力画像における前記第１の暫定対応点の特性角との差である第１の回転角度と、前記第１の入力画像における前記第２の暫定対応点の特性角と前記第２の入力画像における前記第２の暫定対応点の特性角との差である第２の回転角度との差分の絶対値が予め定められた第１の閾値より小さいことである。【００２０】
本発明の第１１の実施態様は、上記第７から第１０の実施態様のいずれか一つの画像照合方法において、前記相対位置関係の整合性に関する制約条件は、前記暫定対応点のペアをなす第１及び第２の暫定対応点それぞれの前記特徴点と前記入力画像のペアをなす第１及び第２の入力画像とに関し、前記第１の入力画像における前記第１の暫定対応点の前記特徴点と前記第２の暫定対応点の前記特徴点との位置の差を示す第１の相対位置ベクトルと、前記第２の入力画像における前記第１の暫定対応点の前記特徴点と前記第２の暫定対応点の前記特徴点との位置の差を示す第２の相対位置ベクトルとの差分である差分ベクトルの長さの最大値が予め定められた第２の閾値より小さいこと、前記第１及び第２の相対位置ベクトルを極座標に変換して得られる動径それぞれが予め定められた第３の閾値より大きいこと、及び、前記第１及び第２の相対位置ベクトルを極座標に変換して得られる偏角の差分の絶対値が予め定められた第４の閾値より小さいこと、である。【００２１】
本発明の第１２の実施態様は、上記第７から第１１の実施態様のいずれか一つの画像照合方法において、前記空間検証部は、前記拡大縮小倍率の整合性に関する制約条件、前記回転角度の整合性に関する制約条件、及び前記相対位置関係の整合性に関する制約条件の全てを満たす前記暫定対応点のペアに基づいて、前記入力画像のペア間の類似度を評価する。【００２２】
本発明に係るプログラムは、コンピュータを、上記第１から第６の実施態様のいずれか一つの画像照合装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００２３】
本発明の画像照合装置、画像照合方法、及びプログラムによれば、暫定対応点のペアの各々について、暫定対応点の幾何変換パラメータの比較又は差分に基づく、拡大縮小倍率の整合性に関する制約条件、回転角度の整合性に関する制約条件、及び相対位置関係の整合性に関する制約条件の全てを満たすか否かを判定し、全ての制約条件を満たすと判定された暫定対応点のペアの数を、入力画像のペア間の類似度として出力することにより、非関連画像間の特徴点の合致数が高く、関連画像間の幾何変換が大きい場合でも、正確且つ高速に画像を照合することができる、という効果が得られる。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施の形態に係る画像照合装置の構成を示すブロック図である。
【図２】本発明の実施の形態に係る画像照合装置の暫定対応点抽出部の構成を示すブロック図である。
【図３】本発明の実施の形態に係る画像照合装置の空間検証部の構成を示すブロック図である。
【図４】本発明の実施の形態に係る画像照合装置における画像照合処理ルーチンを示すフローチャートである。
【図５】本発明の実施の形態に係る画像照合装置における空間制約を検証する処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００２５】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２６】
＜本発明の実施の形態の概要＞
「局所特徴量の類似性」を使用し、入力画像の特徴点から先に暫定対応点を抽出する。その後、暫定対応点のペアに着目し、「拡大縮小倍率の整合性」、「回転角度の整合性」、「相対位置関係の整合性」、計３種類の空間制約からなる全ての制約条件を満たす、画像間の暫定対応点のペアを、正対応点のペアと判定する。また、幾何変換の制約を用いるには、各単一の暫定対応点に依存する投票の処理（ハフ変換）ではなく、暫定対応点のペアに着目し、幾何変換パラメータの差分又は比較に基づいて制約条件を設計する。このように、先に暫定対応点を抽出し、その後、暫定対応点のペアに着目することによって、空間関係の制約と幾何変換の制約を組み合わせることが可能となる。空間関係の制約と幾何変換の制約を結合することで、空間制約の数と種類を増やし、上記第１の課題を解決する。
【００２７】
また、入力画像間の暫定対応点に対して、特徴点から位置座標空間において最も近いｋ個の特徴点を用いて、近傍同士となる暫定対応点のペアを探し出す。空間制約の条件を満たすか否かを検証する際に、全ての暫定対応点のペアを対象にするのではなく、近傍同士となる暫定対応点のペアのみに対して、空間制約を用いて、制約条件を満たす暫定対応点のペアを正対応点のペアと判定する。上記の非特許文献１、２に開示されている画像照合装置のように特徴点のペアを対象にするのではなく、「局所特徴量の類似性」に基づいて暫定対応点を先に同定し、次に暫定対応点のペアを対象に空間制約の条件を満たすか否かを検証する。
【００２８】
また、暫定対応点を抽出する際に、特徴点のデータを転置インデックスに組み込むだけで良く、特徴点のペアのデータをインデックスに組み込む必要がなくなる。特徴点のペアに比べて、特徴点の数がはるかに少ないため、画像照合の際に必要となるメモリ使用量が小さくなる。一方、全ての暫定対応点のペアを対象にするのではなく、位置座標空間において近傍同士となる暫定対応点のペアのみを対象にすることによって、空間制約の条件検証の回数を低く抑制すると共に、探索空間を小さく、探索の所要時間を短くし、上記第２の課題を解決する。
【００２９】
＜本発明の実施の形態に係る画像照合装置の構成＞
次に、本発明の実施の形態に係る画像照合装置の構成について説明する。図１に示すように、本発明の実施の形態に係る画像照合装置１００は、ＣＰＵと、ＲＡＭと、後述する画像照合処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この画像照合装置１００は、機能的には図１に示すように、入力部１０と、演算部２０と、出力部５０とを備えている。
【００３０】
演算部２０は、入力画像のペアから暫定対応点を抽出する暫定対応点抽出部２２と、暫定対応点に対して位置座標空間における特徴点のｋ近傍を用いて、近傍同士となる暫定対応点のペアを探索するＫ近傍探索部２４と、近傍同士となる暫定対応点のペアから正対応点のペアを同定する空間検証部２６とを含んで構成されている。本発明の実施形態による画像照合装置１００は、２枚の入力画像を入力とし、正対応点のペアの数を画像間の類似度として出力する。
【００３１】
＜暫定対応点抽出部＞
図２は、暫定対応点抽出部２２の構成の一例を示すブロック図である。暫定対応点抽出部２２は、入力画像から特徴点を抽出し、特徴点の集合を算出する特徴点抽出部３０、３２と、特徴点集合から局所特徴量集合を算出する局所特徴量算出部３４、３６と、事前に作成したビジュアルワード辞書に基づいて局所特徴量集合をビジュアルワードの集合に量子化するベクトル量子化部３８、４０と、２枚の入力画像から得られたビジュアルワードの集合から同一のビジュアルワードが指定された特徴点のペアを暫定対応点集合として探索するビジュアルワード探索部４２とを含んで構成される。暫定対応点抽出部２２は、２枚の入力画像と事前に作成したビジュアルワード辞書を入力とし、暫定対応点の集合を出力する。
【００３２】
特徴点抽出部３０は、入力画像のペアのうちの第１画像から特徴点を抽出し特徴点の集合を出力する。本実施形態では、非特許文献４に開示されている Hessian Affine Region Detector を用いる。
【００３３】
［非特許文献４］：Krystian Mikolajczyk and Cordelia Schmid. Scale & affine invariant interest point detectors. International Journal of Computer Vision, Vol. 60, No. 1, pp. 63-86, 2004.
【００３４】
具体的には、特徴点抽出部３０は、入力画像のペアのうちの第１画像を入力とし、特徴点の集合を出力する。各特徴点は、スケール（Scale）と特性角（Characteristic Angle）及び２次元の位置座標として表される。本実施の形態では、入力画像から抽出した特徴点の集合Ｐにある各特徴点ｐ∈Ｐにおいて、スケールをσ（ｐ）で、特性角をθ（ｐ）で、２次元の位置座標をｔ（ｐ）＝［ｘ（ｐ）  ｙ（ｐ）］Ｔで表す。
【００３５】
特徴点抽出部３２は、入力画像のペアのうちの第２画像を入力とし、特徴点抽出部３０と同様に、特徴点を抽出し、特徴点の集合を出力する。
【００３６】
局所特徴量算出部３４は、特徴点抽出部３０から出力された特徴点の集合を入力とし、特徴点の集合に含まれる各特徴点から局所特徴量を算出し、局所特徴量の集合を出力する。本実施形態では、非特許文献５に開示されている Scale-Invariant Feature Transform （SIFT）を用いて局所特徴量を算出する。各局所特徴量は、１２８次元のベクトルとして表される。
【００３７】
［非特許文献５］：David G. Lowe. Distinctive image features from scale invariant keypoints. International Journal of Computer Vision, Vol. 60, No. 2, pp. 91-110, 2004.
【００３８】
局所特徴量算出部３６は、特徴点抽出部３２によって出力された特徴点の集合を入力とし、局所特徴量算出部３４と同様に、局所特徴量の集合を出力する。
【００３９】
ベクトル量子化部３８は、事前に作成したビジュアルワード辞書に基づいて、局所特徴量算出部３４によって出力された局所特徴量の集合に含まれる各局所特徴量をビジュアルワードに量子化する。ビジュアルワード辞書とは、多数の画像から算出した局所特徴量をクラスタリングして得られた、クラスタのＩＤ（ビジュアルワード）と平均ベクトルを格納する配列（集合）である。本実施形態では、ビジュアルワード辞書を作成する方法として、事前に約５千枚の画像を用意し、画像から算出した局所特徴量を近似ｋ平均法（非特許文献６を参照）によってクラスタリングする。
【００４０】
［非特許文献６］：James Philbin, Ondrej Chum, Michael Isard, Josef Sivic, and Andrew Zisserman. Object retrieval with large vocabularies and fast spatial matching. In CVPR, 2007.
【００４１】
具体的には、ベクトル量子化部３８は、局所特徴量算出部３４によって出力された局所特徴量の集合とビジュアルワード辞書を入力とし、入力画像のペアのうちの第１画像から算出した局所特徴量とビジュアルワード辞書にあるクラスタの平均ベクトルとを比較し、ベクトル間のユークリッド距離が最短のクラスタのＩＤをビジュアルワードとして該当する特徴点に指定し、ビジュアルワードの集合を出力する。
【００４２】
本実施形態では、ユークリッド距離が最短のクラスタのＩＤを探索する方法として、非特許文献７に開示されている近似最近傍探索法 Randomized KD-tree を用いる。
【００４３】
［非特許文献７］：Marius Muja and David G. Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. In VISAPP, pp. 331-340, 2009.
【００４４】
各ビジュアルワードは、整数として表される。具体的に、各特徴点ｐ∈Ｐにおいて、指定されたビジュアルワードをｕ（ｐ）で表す。
【００４５】
ベクトル量子化部４０は、局所特徴量算出部３６によって出力された局所特徴量の集合とビジュアルワード辞書を入力とし、ベクトル量子化部３８と同様に、ビジュアルワードの集合を出力する。
【００４６】
ビジュアルワード探索部４２は、２枚の入力画像から得られたビジュアルワードの集合を入力とし、２枚の入力画像から得られたビジュアルワードの集合から同一のビジュアルワードが指定された特徴点のペア（暫定対応点）を探索し、暫定対応点の集合を出力する。本実施形態では、大規模画像データベース検索を想定し、転置インデックスを作成し、それに基づく探索方法を用いる。各暫定対応点は、１個のビジュアルワードと、暫定対応点を構成した２点の特徴点のスケールと特性角及び２次元の位置座標として表される。具体的に、２枚の入力画像から抽出した特徴点の集合をＰとＱで、暫定対応点の集合をＣで、各暫定対応点ｃ∈Ｃをｃ＝（ｐ；ｑ）で表す。Ｃ⊆Ｐ×Ｑは、式（１）によって得られる。Ｐ×Ｑは、ＰとＱの直積集合である。
【００４７】
【数１】
2017006852.tif 000003
【００４８】
各暫定対応点ｃ∈Ｃは、式（２）として表される。
【００４９】
【数２】
2017006852.tif 000004
【００５０】
＜Ｋ近傍探索部＞
Ｋ近傍探索部２４は、暫定対応点の集合を入力とし、暫定対応点に対して、位置座標空間における特徴点のｋ近傍を用いて、近傍同士となる暫定対応点のペアを探索し、近傍同士となる暫定対応点のペアの集合を出力する。本実施形態では、上記非特許文献７に開示されている近似最近傍探索法 Randomized KD-tree を用いる。具体的に、暫定対応点のペアを（ｃａ；ｃｂ）で、暫定対応点をｃａ＝（ｐａ；ｑａ）とｃｂ＝（ｐｂ；ｑｂ）で、特徴点のｋ近傍の集合をＮｋ（・）で表す。「近接関係の整合性」の空間制約ｈＮは、式（３）として表される。［・］は、アイバーソンの記法で、角括弧中の条件が真ならば１で偽ならば０である。「∧」は、論理積を表す。
【００５１】
【数３】
2017006852.tif 000005
【００５２】
近傍同士となる暫定対応点のペアの集合ＧＮ⊆Ｃ２は、式（４）によって得られる。Ｃ２＝Ｃ×Ｃは、ＣとＣの直積集合である。
【００５３】
【数４】
2017006852.tif 000006
【００５４】
＜空間検証部＞
図３は、空間検証部２６の構成の一例を示すブロック図である。空間検証部２６は、拡大縮小倍率検証部４４、回転角度検証部４６、及び相対位置関係検証部４８を含んで構成されている。検証部の順序は、任意に変更できる。空間検証部２６は、Ｋ近傍探索部２４によって出力された、近傍同士となる暫定対応点のペアの集合を入力とし、正対応点のペアの数を２枚の入力画像の間の類似度として出力する。
【００５５】
拡大縮小倍率検証部４４は、暫定対応点のペアが、暫定対応点の幾何変換パラメータの比較に基づく、「拡大縮小倍率の整合性」の空間制約の条件を満たすか否かを検証する。本実施形態では、暫定対応点のペアにおいて、入力画像内の特徴点のスケールの大小関係が等しいか否かを検証し、入力画像間の特徴点のスケールの大小関係が等しいか否かを検証する。具体的に、入力画像内の特徴点のスケールの大小関係に基づく制約条件ｈ’σは式（５）で、入力画像間の特徴点のスケールの大小関係に基づく制約条件ｈ”σは式（６）で表す。
【００５６】
【数５】
2017006852.tif 000007
【００５７】
「拡大縮小倍率の整合性」の空間制約ｈσは、式（７）として表される。暫定対応点のペア（ｃａ；ｃｂ）において、ｈσ（ｃａ；ｃｂ）＝１の場合に真と判定し、ｈσ（ｃａ；ｃｂ）＝０の場合に偽と判定する。「∨」は、論理和を表す。
【００５８】
【数６】
2017006852.tif 000008
【００５９】
回転角度検証部４６は、暫定対応点のペアが、暫定対応点の幾何変換パラメータの差分に基づく「回転角度の整合性」の空間制約の条件を満たすか否かを検証する。本実施形態では、暫定対応点のペアにおいて、２点の暫定対応点から算出される回転角度の差分の絶対値が事前に設定した閾値εθより小さいか否かを検証する。具体的に、暫定対応点の回転角度をθ（ｃ）＝θ（ｐ）−θ（ｑ）で算出する。「回転角度の整合性」の空間制約ｈθは、式（８）として表される。暫定対応点のペア（ｃａ；ｃｂ）において、ｈθ（ｃａ；ｃｂ）＝１の場合に真と判定し、ｈθ（ｃａ；ｃｂ）＝０の場合に偽と判定する。
【００６０】
【数７】
2017006852.tif 000009
【００６１】
相対位置関係検証部４８は、暫定対応点のペアが、暫定対応点の幾何変換パラメータの比較又は差分に基づく「相対位置関係の整合性」の空間制約の条件を満たすか否かを検証する。本実施形態では、暫定対応点のペアにおいて、後述する第１制約条件及び第２制約条件からなる計２種類の制約条件の組み合わせを「相対位置関係の整合性」の空間制約として用いる。第１制約条件の検証では、２枚の入力画像内における特徴点間の相対位置ベクトルを算出し、相対位置ベクトルの差分ベクトルの長さの最大値が事前に設定した閾値εｖより小さいか否かを検証する。具体的に、入力画像にある２点の特徴点ｐａとｐｂにおいて、ｐａからｐｂへ向かう相対位置ベクトルは、式（９）で算出する。
【００６２】
【数８】
2017006852.tif 000010
【００６３】
Ｍ（ｐ）は、特徴点ｐの幾何特性を表す行列で、式（１０）で算出する。
【００６４】
【数９】
2017006852.tif 000011
【００６５】
第１制約条件ｈ’ｖは、式（１１）として表される。||・||２は、ユークリッドノルムを表す。
【００６６】
【数１０】
2017006852.tif 000012
【００６７】
第２制約条件の検証では、相対位置ベクトルを極座標（動径と偏角）に変換し、動径と事前に設定した閾値との大小関係が等しいか否かを検証し、偏角の差分の絶対値が事前に設定した閾値εαより小さいか否かを検証する。具体的に、相対位置ベクトルｖの動径をρで、偏角をαで表す。第２制約条件ｈ”ｖは、式（１２）として表される。
【００６８】
【数１１】
2017006852.tif 000013
【００６９】
「相対位置関係の整合性」の空間制約ｈｖは、式（１３）として表される。暫定対応点のペア（ｃａ；ｃｂ）において、ｈｖ（ｃａ；ｃｂ）＝１の場合に真と判定し、ｈｖ（ｃａ；ｃｂ）＝０の場合に偽と判定する。
【００７０】
【数１２】
2017006852.tif 000014
【００７１】
上述したように、空間検証部２６は、Ｋ近傍探索部２４によって出力された、近傍同士となる暫定対応点のペアの集合を入力とし、正対応点のペアの数を２枚の入力画像の間の類似度として出力する。本実施形態では、正対応点のペアの同定に用いる空間制約の集合をＨ＝｛ｈσ，ｈθ，ｈｖ｝で表す。正対応点のペアの集合＾Ｇは、式（１４）によって得られる。
【００７２】
【数１３】
2017006852.tif 000015
【００７３】
正対応点のペアの数は、＾Ｇの要素の個数｜＾Ｇ｜によって得られ、出力部５０により出力される。
【００７４】
＜本発明の実施の形態に係る画像照合装置の作用＞
次に、本発明の実施の形態に係る画像照合装置１００の作用について説明する。入力部１０によって、入力画像のペア、及びビジュアルワード辞書を受け付けると、画像照合装置１００は、図４に示す画像照合処理ルーチンを実行する。
【００７５】
まず、ステップＳ１００では、入力画像のペアのうちの第１画像の特徴点の集合を抽出する。ステップＳ１０２では、上記ステップＳ１００で抽出された第１画像の特徴点の集合に含まれる各特徴点について局所特徴量を抽出し、局所特徴量の集合を出力する。
【００７６】
ステップＳ１０４では、ビジュアルワード辞書と、上記ステップＳ１０２で抽出された各特徴点の局所特徴量とに基づいて、第１画像の特徴点の集合について、局所特徴量の集合をビジュアルワードに量子化する。
【００７７】
そして、ステップＳ１０６では、入力画像のペアのうちの第２画像の特徴点の集合を抽出する。ステップＳ１０８では、上記ステップＳ１０６で抽出された第２画像の特徴点の集合に含まれる各特徴点について局所特徴量を抽出し、局所特徴量の集合を出力する。
【００７８】
ステップＳ１１０では、ビジュアルワード辞書と、上記ステップＳ１０８で抽出された各特徴点の局所特徴量とに基づいて、第２画像の特徴点の集合について、局所特徴量の集合をビジュアルワードに量子化する。
【００７９】
次のステップＳ１１２では、上記ステップＳ１０４で得られた、第１画像の特徴点の集合に含まれる各特徴点についてのビジュアルワードと、上記ステップＳ１１０で得られた、第２画像の特徴点の集合に含まれる各特徴点についてのビジュアルワードとに基づいて、暫定対応点の集合を抽出する。
【００８０】
ステップＳ１１４では、上記ステップＳ１１２で抽出された暫定対応点の集合から、各特徴点について求められるｋ近傍の集合に基づいて、上記式（３）に従って、近傍同士となる暫定対応点のペアの集合を抽出する。
【００８１】
ステップＳ１１６では、上記ステップＳ１１４で抽出された、近傍同士となる暫定対応点のペアの集合から、暫定対応点ペアを選択する。
【００８２】
ステップＳ１１８では、上記ステップＳ１１６で選択された暫定対応点ペアについて、拡大縮小倍率の整合性に関する制約条件、回転角度の整合性に関する制約条件、及び相対位置関係の整合性に関する制約条件の全てを満たすか否かを判定し、正対応点のペアであるか誤対応点のペアであるかを判定する。
【００８３】
そして、ステップＳ１２０では、近傍同士となる暫定対応点のペアの集合に含まれる、全ての暫定対応点ペアについて、上記ステップＳ１１８の処理を実行したか否かを判定する。上記ステップＳ１１８の処理を実行していない暫定対応点ペアが存在する場合には、上記ステップＳ１１６へ戻り、当該暫定対応点ペアを選択する。一方、近傍同士となる暫定対応点のペアの集合に含まれる、全ての暫定対応点ペアについて、上記ステップＳ１１８の処理を実行した場合には、ステップＳ１１２において、正対応点のペアの数を入力画像のペア間の類似度として出力部５０により出力し、画像照合処理ルーチンを終了する。
【００８４】
上記ステップＳ１１８は、図５に示す処理ルーチンによって実現される。
【００８５】
ステップＳ１３０では、上記ステップＳ１１６で選択された暫定対応点ペアについて、上記式（７）に従って、拡大縮小倍率の整合性に関する制約条件を満たすか否かを判定する。拡大縮小倍率の整合性に関する制約条件を満たす場合には、ステップＳ１３２へ移行する。一方、拡大縮小倍率の整合性に関する制約条件を満たさない場合には、ステップＳ１３８へ移行し、誤対応点のペアであると判断する。
【００８６】
ステップＳ１３２では、上記ステップＳ１１６で選択された暫定対応点ペアについて、上記式（８）に従って、回転角度の整合性に関する制約条件を満たすか否かを判定する。回転角度の整合性に関する制約条件を満たす場合には、ステップＳ１３４へ移行する。一方、回転角度の整合性に関する制約条件を満たさない場合には、ステップＳ１３８へ移行し、誤対応点のペアであると判断する。
【００８７】
ステップＳ１３４では、上記ステップＳ１１６で選択された暫定対応点ペアについて、上記式（１３）に従って、相対位置関係の整合性に関する制約条件を満たすか否かを判定する。相対位置関係の整合性に関する制約条件を満たす場合には、ステップＳ１３６へ移行し、正対応点のペアであると判断する。一方、相対位置関係の整合性に関する制約条件を満たさない場合には、ステップＳ１３８へ移行し、誤対応点のペアであると判断する。
【００８８】
以上説明したように、本発明に実施の形態に係る画像照合装置によれば、非関連画像間の特徴点の合致数が高く、関連画像間の幾何変換が大きい場合でも、正確且つ高速に画像を照合することができる。
【００８９】
また、空間関係の制約と幾何変換の制約を結合し、正対応点のペアの同定に用いる空間制約の数と種類を増やすことによって、正対応点の探索漏れや過剰除去等を回避しつつ、誤合致した暫定対応点を除去することで画像間の識別力を高めることが可能となる。
【００９０】
また、「局所特徴量の類似性」に基づいて暫定対応点を先に同定し、次に暫定対応点のペアのみを対象に空間制約の条件を満たすか否かを検証することによって、画像照合の際に必要となるメモリ使用量をより低く抑制可能である。
【００９１】
また、位置座標空間において近傍同士となる暫定対応点のペアのみを対象にすることで、空間制約の条件検証の回数をより低く（探索空間をより小さく）抑制可能である。
【００９２】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００９３】
例えば、上述した実施の形態では、近傍同士となる暫定対応点のペアの集合を抽出して、近傍同士となる暫定対応点のペアの各々について、全ての制約条件を満たすか否かを判定する場合を例に説明したが、これに限定されるものではない。近傍同士となる暫定対応点のペアの集合を抽出せずに、全ての暫定対応点のペアの各々について、全ての制約条件を満たすか否かを判定するようにしてもよい。
【産業上の利用可能性】
【００９４】
本発明は、非関連画像間の特徴点の合致数が高く、関連画像間の幾何変換が大きい場合でも、正確且つ高速に画像を照合することが不可欠な用途にも適用できる。
【符号の説明】
【００９５】
１０  入力部
２０  演算部
２２  暫定対応点抽出部
２４  近傍探索部
２６  空間検証部
３０、３２  特徴点抽出部
３４、３６  局所特徴量算出部
３８、４０  ベクトル量子化部
４２  ビジュアルワード探索部
４４  拡大縮小倍率検証部
４６  回転角度検証部
４８  相対位置関係検証部
５０  出力部
１００  画像照合装置
【図１】
2017006852.tif 000016
【図２】
2017006852.tif 000017
【図３】
2017006852.tif 000018
【図４】
2017006852.tif 000019
【図５】
2017006852.tif 000020
【国際調査報告】
2017006852.tif 000021
2017006852.tif 000022