(57)【要約】【課題】リファレンス画像とクエリ画像とが異なる視点から撮影された場合に、高精度な幾何検証を実現するプログラム、装置及び方法を提供する。【解決手段】クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合から、点対応の組を任意に複数選択する第１のステップと、選択された複数の点対応の組を用いて、リファレンス画像をクエリ画像系へ射影するHomography行列Ｈを算出する第２のステップと、Homography行列Ｈを用いてリファレンス画像の特徴点ｐを射影することによって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|が、所定角度以下であるか否かを判定する第３のステップとを有し、真と判定された点対応の組の数が、所定数以上となるまで、第１のステップから第３のステップを繰り返すように実行するHomography行列判定手段としてコンピュータを機能させる。【選択図】図１
2015007919.tif 000002
【特許請求の範囲】
【請求項１】
局所特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度をHomography行列Ｈに基づいて算出するべく、装置に搭載されたコンピュータを機能させるプログラムであって、
クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合から、点対応の組を任意に複数選択する第１のステップと、
選択された複数の点対応の組を用いて、リファレンス画像をクエリ画像系へ射影するHomography行列Ｈを算出する第２のステップと、
前記Homography行列Ｈを用いて前記リファレンス画像の特徴点ｐを、クエリ座標系へ射影する第３のステップと、
前記リファレンス画像の特徴点ｐの射影によって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|を算出する第４のステップと
を有し、
前記角度誤差|θH−θ'|が所定角度以下となる点対応の組の数が、所定数以上となるまで、第１のステップから第４のステップまでを繰り返す
ように実行するHomography行列判定手段としてコンピュータを機能させることを特徴とするプログラム。
【請求項２】
前記Homography行列判定手段の第４のステップについて、
リファレンス画像の特徴点ｐと、当該特徴点ｐから局所特徴の方向θへ所定長だけ離れた点ａとをクエリ画像系へ射影し、リファレンス画像からクエリ画像系へ射影された特徴点ｐから点ａへの方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'とから、角度誤差|θH−θ'|が算出される
ようにコンピュータを機能させることを特徴とする請求項１に記載のプログラム。
【請求項３】
前記Homography行列Ｈは、３行×３列（h11〜h33）であり、
リファレンス画像の特徴点ｐ＝（ｘ，ｙ，１）
クエリ画像の特徴点      ｐ'＝（ｘ'，ｙ'，１）    （ベクトルの第３成分ｓ＝１）
点ａ＝（ｘ＋cosθ，ｙ＋sinθ，１）
点ａについてクエリ画像系への射影  ａ'＝ｓ1・Ｈ・ａ
点ｐについてクエリ画像系への射影  ｐ'＝ｓ2・Ｈ・ｐ
（Ｘ，Ｙ，０）＝ｓ1・Ｈ・ａ−ｓ2・Ｈ・ｐ
θH＝tan-1（Ｙ／Ｘ）
によって算出するようにコンピュータを機能させることを特徴とする請求項２に記載のプログラム。
【請求項４】
前記Homography行列判定手段によって出力された前記Homography行列を用いて、クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合における全ての点対応の組について、
前記リファレンス画像の特徴点ｐを射影することによって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|が、所定角度以下である
ものを近傍点対応（inliner）と判定する全特徴点判定手段としてコンピュータを更に機能させることを特徴とする請求項１から３のいずれか１項に記載のプログラム。
【請求項５】
前記Homography行列判定手段によって出力された前記Homography行列を用いて、クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合における全ての点対応の組について、
リファレンス画像の特徴点ｐをクエリ画像系に射影した点と、クエリ画像の特徴点ｐ'との距離誤差が、所定閾値以内である
ものを近傍点対応（inliner）と判定する全特徴点判定手段としてコンピュータを更に機能させることを特徴とする請求項１から３のいずれか１項に記載のプログラム。
【請求項６】
前記Homography行列判定手段によって出力された前記Homography行列を用いて、クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合における全ての点対応の組について、
前記リファレンス画像の特徴点ｐを射影することによって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|が、所定角度以下であって、且つ、
リファレンス画像の特徴点ｐをクエリ画像系に射影して点と、クエリ画像の特徴点ｐ'との距離誤差が、所定閾値以内である
ものを近傍点対応（inliner）と判定する全特徴点判定手段としてコンピュータを更に機能させることを特徴とする請求項１から３のいずれか１項に記載のプログラム。
【請求項７】
前記全特徴点判定手段によって判定されたinlierの数を、類似度とする類似度算出手段としてコンピュータを更に機能させることを特徴とする請求項４から６のいずれか１項に記載のプログラム。
【請求項８】
前記類似度算出手段は、前記Homography行列判定手段及び前記全特徴点判定手段の処理を複数回繰り返すように制御すると共に、前記inlierの数が最大となる点対応の組を導出し、その際のinlierの数を類似度とする
ようにコンピュータを機能させることを特徴とする請求項７に記載のプログラム。
【請求項９】
クエリ画像及びリファレンス画像から局所特徴点の特徴点集合を抽出する局所特徴点抽出手段と、
クエリ画像から抽出された各特徴点に対し、最も類似するリファレンス画像の特徴点を対応付け組集合を導出するマッチング手段と
を更に有し、マッチング手段によって導出された前記組集合は、前記Homography行列判定手段及び前記全特徴点判定手段へ出力される
ようにコンピュータを機能させることを特徴とする請求項１から８のいずれか１項に記載のプログラム。
【請求項１０】
局所特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度をHomography行列Ｈに基づいて算出する装置であって、
クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合から、点対応の組を任意に複数選択する第１のステップと、
選択された複数の点対応の組を用いて、リファレンス画像をクエリ画像系へ射影するHomography行列Ｈを算出する第２のステップと、
前記Homography行列Ｈを用いて前記リファレンス画像の特徴点ｐを、クエリ座標系へ射影する第３のステップと、
前記リファレンス画像の特徴点ｐの射影によって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|を算出する第４のステップと
を有し、
前記角度誤差|θH−θ'|が所定角度以下となる点対応の組の数が、所定数以上となるまで、第１のステップから第４のステップまでを繰り返す
ように実行するHomography行列判定手段を有することを特徴とする装置。
【請求項１１】
装置を用いて、局所特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度をHomography行列Ｈに基づいて算出する方法であって、
クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合から、点対応の組を任意に複数選択する第１のステップと、
選択された複数の点対応の組を用いて、リファレンス画像をクエリ画像系へ射影するHomography行列Ｈを算出する第２のステップと、
前記Homography行列Ｈを用いて前記リファレンス画像の特徴点ｐを、クエリ座標系へ射影する第３のステップと、
前記リファレンス画像の特徴点ｐの射影によって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|を算出する第４のステップと
を有し、
前記角度誤差|θH−θ'|が所定角度以下となる点対応の組の数が、所定数以上となるまで、第１のステップから第４のステップまでを繰り返す
ことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、局所特徴を用いて画像間の類似度を算出する技術に関する。特に、特徴点集合で表されるリファレンス画像（検索対象の画像）の集合から、同じく特徴点集合で表されるクエリ画像（検索キーとなる画像）に類似したリファレンス画像を高精度に検索する技術に関する。
【背景技術】
【０００２】
近年、局所特徴点（特徴ベクトル）に基づいた画像認識や検索技術が注目されている。画像認識では、画像から抽出した様々な特徴量を利用する方法が一般的であるが、高精度な認識を実現するために、撮影条件による物体の見え方の変化（大きさ、方向、明るさ等）に対して、ロバストな特徴量抽出技術が用いられる。例えば、ＳＩＦＴ(Scale-Invariant Feature Transform)やＳＵＲＦ(Speeded Up Robust Features)、ＯＲＢ(Oriented FAST and Rotated BRIEF)のようなアルゴリズムが、回転やスケールの変化にロバストであって、広く利用されている。
【０００３】
局所特徴量を用いた類似度画像検索には、特徴ベースマッチング(Feature-Based Matching)と称される技術が用いられる。これは各画像から特徴点や特徴領域を抽出し、その周囲の領域から特徴量を算出し、その特徴量を比較することで画像間のマッチングを実行する。
【０００４】
従来、クエリ画像と保存画像から抽出した特徴点を対応付け、その対応付けの確からしさを示すスコアを投票し、クエリ画像とマッチングする保存画像を求める技術が開示されている（例えば特許文献１参照）。
【０００５】
ここで、認識精度を高めるために、幾何検証の処理を実行することも好ましい。例えば、リファレンス画像とクエリ画像と間のHomography行列を推定し、そのHomography行列によって定義される拘束条件を満たす対応組(inlier)の数をスコアとして利用する技術がある（例えば非特許文献１参照）。Homography行列の推定には、一般的に、２枚の画像間がアフィン変換で表現されると仮定して、ＲＡＮＳＡＣ(RANdom SAmple Consensus)等のロバスト推定技術が用いられる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１３−０７３３３３号公報
【非特許文献】
【０００７】
【非特許文献１】J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman,"Object Retrieval with Large Vocabularies and Fast Spatial Matching",in Proc of CVPR, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、前述した従来技術によれば、リファレンス画像とクエリ画像とが異なる視点から撮影されたものである場合、Homography行列による幾何検証の処理が不十分であるために、誤った対応組をinlierと判定してしまうという問題があった。
【０００９】
そこで、本発明は、リファレンス画像とクエリ画像とが異なる視点から撮影された場合に、高精度な幾何検証を実現するプログラム、装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明によれば、局所特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度をHomography行列Ｈに基づいて算出するべく、装置に搭載されたコンピュータを機能させるプログラムであって、
クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合から、点対応の組を任意に複数選択する第１のステップと、
選択された複数の点対応の組を用いて、リファレンス画像をクエリ画像系へ射影するHomography行列Ｈを算出する第２のステップと、
Homography行列Ｈを用いてリファレンス画像の特徴点ｐを、クエリ座標系へ射影する第３のステップと、
リファレンス画像の特徴点ｐの射影によって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|を算出する第４のステップと
を有し、
角度誤差|θH−θ'|が所定角度以下となる点対応の組の数が、所定数以上となるまで、第１のステップから第４のステップまでを繰り返す
ように実行するHomography行列判定手段としてコンピュータを機能させることを特徴とする。
【００１１】
本発明のプログラムにおける他の実施形態によれば、
Homography行列判定手段の第４のステップについて、
リファレンス画像の特徴点ｐと、当該特徴点ｐから局所特徴の方向θへ所定長だけ離れた点ａとをクエリ画像系へ射影し、リファレンス画像からクエリ画像系へ射影された特徴点ｐから点ａへの方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'とから、角度誤差|θH−θ'|が算出される
ようにコンピュータを機能させることも好ましい。
【００１２】
本発明のプログラムにおける他の実施形態によれば、
Homography行列Ｈは、３行×３列（h11〜h33）であり、
リファレンス画像の特徴点ｐ＝（ｘ，ｙ，１）
クエリ画像の特徴点      ｐ'＝（ｘ'，ｙ'，１）    （ベクトルの第３成分ｓ＝１）
点ａ＝（ｘ＋cosθ，ｙ＋sinθ，１）
点ａについてクエリ画像系への射影  ａ'＝ｓ1・Ｈ・ａ
点ｐについてクエリ画像系への射影  ｐ'＝ｓ2・Ｈ・ｐ
（Ｘ，Ｙ，０）＝ｓ1・Ｈ・ａ−ｓ2・Ｈ・ｐ
θH＝tan-1（Ｙ／Ｘ）
によって算出するようにコンピュータを機能させることも好ましい。
【００１３】
本発明のプログラムにおける他の実施形態によれば、
Homography行列判定手段によって出力されたHomography行列を用いて、クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合における全ての点対応の組について、
リファレンス画像の特徴点ｐを射影することによって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|が、所定角度以下である
ものを近傍点対応（inliner）と判定する全特徴点判定手段としてコンピュータを更に機能させることも好ましい。
【００１４】
本発明のプログラムにおける他の実施形態によれば、
Homography行列判定手段によって出力されたHomography行列を用いて、クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合における全ての点対応の組について、
リファレンス画像の特徴点ｐをクエリ画像系に射影した点と、クエリ画像の特徴点ｐ'との距離誤差が、所定閾値以内である
ものを近傍点対応（inliner）と判定する全特徴点判定手段としてコンピュータを更に機能させることも好ましい。
【００１５】
本発明のプログラムにおける他の実施形態によれば、
Homography行列判定手段によって出力されたHomography行列を用いて、クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合における全ての点対応の組について、
リファレンス画像の特徴点ｐを射影することによって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|が、所定角度以下であって、且つ、
リファレンス画像の特徴点ｐをクエリ画像系に射影して点と、クエリ画像の特徴点ｐ'との距離誤差が、所定閾値以内である
ものを近傍点対応（inliner）と判定する全特徴点判定手段としてコンピュータを更に機能させることも好ましい。
【００１６】
本発明のプログラムにおける他の実施形態によれば、
全特徴点判定手段によって判定されたinlierの数を、類似度とする類似度算出手段としてコンピュータを更に機能させることも好ましい。
【００１７】
本発明のプログラムにおける他の実施形態によれば、
類似度算出手段は、Homography行列判定手段及び全特徴点判定手段の処理を複数回繰り返すように制御すると共に、inlierの数が最大となる点対応の組を導出し、その際のinlierの数を類似度とする
ようにコンピュータを機能させることも好ましい。
【００１８】
本発明のプログラムにおける他の実施形態によれば、
クエリ画像及びリファレンス画像から局所特徴点の特徴点集合を抽出する局所特徴点抽出手段と、
クエリ画像から抽出された各特徴点に対し、最も類似するリファレンス画像の特徴点を対応付け組集合を導出するマッチング手段と
を更に有し、マッチング手段によって導出された組集合は、Homography行列判定手段及び全特徴点判定手段へ出力される
ようにコンピュータを機能させることも好ましい。
【００１９】
本発明によれば、局所特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度をHomography行列Ｈに基づいて算出する装置であって、
クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合から、点対応の組を任意に複数選択する第１のステップと、
選択された複数の点対応の組を用いて、リファレンス画像をクエリ画像系へ射影するHomography行列Ｈを算出する第２のステップと、
Homography行列Ｈを用いてリファレンス画像の特徴点ｐを、クエリ座標系へ射影する第３のステップと、
リファレンス画像の特徴点ｐの射影によって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|を算出する第４のステップと
を有し、
角度誤差|θH−θ'|が所定角度以下となる点対応の組の数が、所定数以上となるまで、第１のステップから第４のステップまでを繰り返す
ように実行するHomography行列判定手段を有することを特徴とする。
【００２０】
本発明によれば、装置を用いて、局所特徴点集合で表されるクエリ画像とリファレンス画像との間の類似度をHomography行列Ｈに基づいて算出する方法であって、
クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合から、点対応の組を任意に複数選択する第１のステップと、
選択された複数の点対応の組を用いて、リファレンス画像をクエリ画像系へ射影するHomography行列Ｈを算出する第２のステップと、
Homography行列Ｈを用いてリファレンス画像の特徴点ｐを、クエリ座標系へ射影する第３のステップと、
リファレンス画像の特徴点ｐの射影によって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|を算出する第４のステップと
を有し、
角度誤差|θH−θ'|が所定角度以下となる点対応の組の数が、所定数以上となるまで、第１のステップから第４のステップまでを繰り返す
ことを特徴とする。
【発明の効果】
【００２１】
本発明のプログラム、装置及び方法によれば、リファレンス画像とクエリ画像とが異なる視点から撮影された場合に、高精度な幾何検証を実現することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明における類似度算出装置の機能構成図である。
【図２】本発明におけるフローチャートである。
【図３】リファレンス画像とクエリ画像との間における特徴点対応の組を表す説明図である。
【図４】本発明における画像間の第１の処理を表す説明図である。
【図５】本発明における画像間の第２の処理を表す説明図である。
【発明を実施するための形態】
【００２３】
以下では、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２４】
本発明によれば、以下のように２つの実施の形態に区分できる。
（１）類似度算出機能：局所特徴点集合で表されるクエリ画像とリファレンス画像との間における、単一の静止画像同士の類似度を算出する。
（２）検索装置：類似度算出機能を用いて、大量のリファレンス画像の中から、クエリ画像に写る１つ以上のリファレンス画像を検索する。
尚、以下では、本発明を、類似度算出装置として説明する。
【００２５】
図１は、本発明における類似度算出装置の機能構成図である。
【００２６】
図１によれば、類似度算出装置１は、局所特徴点集合で表されるクエリ画像とリファレンス画像とを入力し、それら画像間の類似度をHomography行列Ｈに基づいて算出する。類似度算出装置は１は、局所特徴点抽出部１１と、マッチング部１２と、Homography行列判定部１３と、類似度算出部１５と、リファレンス特徴点蓄積部１６とを有する。これら機能構成部は、類似度算出装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現できる。
【００２７】
図２は、本発明におけるフローチャートである。図１における各機能構成の処理の流れは、図２のような方法としても理解できる。図３は、リファレンス画像とクエリ画像との間における特徴点対応の組を表す説明図である。図４及び図５は、本発明における画像間の処理を表す説明図である。以下では、図１の類似度算出装置１の機能構成の説明の中で、図２〜図５を参照する。
【００２８】
［局所特徴点抽出部１１］
局所特徴点抽出部１１は、リファレンス画像及びクエリ画像を入力する。ここで、リファレンス画像とクエリ画像とは、異なる視点となる場合が多い（図３（ａ）参照）。リファレンス画像は、対象物が正面から撮影された画像である場合が多いのに対し、クエリ画像は、撮影者の状況によって様々な視点から撮影された画像である場合が多い。従って、リファレンス画像とクエリ画像との間では、高精度な幾何検証を実現する必要がある。
【００２９】
局所特徴点抽出部１１は、クエリ画像及びリファレンス画像それぞれから、局所特徴点の特徴点集合を抽出する（図２のＳ１１参照）。
局所特徴点の抽出アルゴリズムとしては、例えばＳＩＦＴやＳＵＲＦ、ＯＲＢが用いられる。これらの局所特徴点は、「座標ｐ＝(x,y)」「方向θ」「特徴量ベクトルf」によって記述される（図３（ｂ）参照）。尚、クエリ画像の局所特徴点と、リファレンス画像の局所特徴点とは、その特徴ベクトルについて同じ次元数である。
【００３０】
ＳＩＦＴの場合、１枚の画像からは１２８次元の特徴点集合が抽出される。ＳＩＦＴとは、スケールスペースを用いて特徴的な局所領域を解析し、そのスケール変化及び回転に不変となる特徴ベクトルを記述する技術である。
ＳＵＲＦの場合、ＳＩＦＴよりも高速処理が可能であって、１枚の画像から６４次元の特徴点集合が抽出される。
ＯＲＢの場合、バイナリコードによる特徴記述としてＢＲＩＥＦ(Binary Robust Independent Elementary Features)を用いて、１つのコンテンツから２５６ビットのバイナリ特徴ベクトルの集合が抽出される。特に、ＯＲＢによれば、ＳＩＦＴやＳＵＲＦと比較して、同等以上の精度を保持すると共に、数百倍の高速化を実現することができる。
【００３１】
抽出されたリファレンス画像の特徴点集合とクエリ画像の特徴点集合とは、マッチング部１２へ出力される。ここでは、類似度算出装置として説明しているが、本発明を検索装置に適用した場合、リファレンス画像の特徴点集合は、リファレンス特徴点蓄積部１６へ出力される。
【００３２】
本発明を検索装置に適用した場合、リファレンス特徴点蓄積部１６は、大量のリファレンス画像における局所特徴点の特徴点集合を蓄積する。リファレンス画像には、同一の物体又は同一カテゴリに属する少なくとも１つのインスタンス（対象物、マーカ）が写っている。そして、検索装置として、検索キーとなる「クエリ画像」を入力し、そのクエリ画像に写る１枚以上のリファレンス画像を検索する。
【００３３】
［マッチング部１２］
マッチング部１２は、リファレンス画像の特徴点ｐとクエリ画像の特徴点ｐ'とをマッチングさせる（図２のＳ１２参照）。具体的には、リファレンス画像の特徴点それぞれについて、クエリ画像の中で最も類似する特徴点とを対応付ける（図３（ｃ）参照）。これによって、特徴点の点対応の集合が生成される。
ここで、クエリ画像の１つの特徴点に、リファレンス画像の複数の特徴点が対応付けられることがある。この場合、クエリ特徴点から見て最も類似するリファレンス特徴点のみを点対応として残し、その他の点対応を削除してもよい。
これら局所特徴点の点対応の集合は、Homography行列判定部１３及び類似度算出部１５へ出力される。
【００３４】
［Homography行列判定部１３］
（Ｓ１３１）Homography行列判定部１３は、クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合から、点対応の組を任意（ランダム）に複数選択する（図４（ａ）参照）。具体的には、ランダムに４組の点対応（ｐ1,ｐ1'）（ｐ2,ｐ2'）（ｐ3,ｐ3'）（ｐ4,ｐ4'）が選択される。
リファレンス画像の特徴点ｐとクエリ画像の特徴点ｐ'とは、以下のように表される。
【数１】
2015007919.tif 000003
ｘ座標：第１成分
ｙ座標：第２成分
ｓ＝１：第３成分（正規化）
【００３５】
（Ｓ１３２）次に、Homography行列判定部１３は、リファレンス画像の特徴点ｐとクエリ画像の特徴点ｐ'との点対応の集合から、Homography行列Ｈ（３行×３列（h11〜h33））を算出する（図４（ｂ）参照）。このとき、「ｐ'＝ｓ・Ｈ・ｐ」の関係が成立する。
【数２】
2015007919.tif 000004
【００３６】
クエリ画像及び対象リファレンス画像は、類似度が高いほど、特徴ベクトル同士が射影幾何学的に線形となる。従って、平面射影変換行列であるHomography行列Ｈによって、座標を置き換えることができる。即ち、Homography行列Ｈは、リファレンス画像をクエリ画像系へ射影するためのものである。
Homography行列Ｈの未知パラメータ数は、８個（h11〜h33、h33=1）であり、一組の点対応は２個の制約式を与える。従って、この行列Ｈは、４組以上の対応点があれば、最小二乗法によって算出することができる。
【００３７】
（Ｓ１３３）次に、Homography行列判定部１３は、先に算出したHomography行列Ｈを用いてリファレンス画像の特徴点ｐを、クエリ座標系へ射影する（図４（ｃ）参照）。ここで、リファレンス画像の特徴点ｐと、当該特徴点ｐから局所特徴の方向θへ所定長（例えば単位長１）だけ離れた点ａも、クエリ画像系へ射影する。
【数３】
2015007919.tif 000005
【００３８】
リファレンス画像の特徴点ｐ及び点ａを、クエリ画像系へ射影した点は、以下のように表される。
点ａについてクエリ画像系への射影  ａ'＝ｓ1・Ｈ・ａ
点ｐについてクエリ画像系への射影  ｐ'＝ｓ2・Ｈ・ｐ
hiT：  Ｈの行ベクトル
【数４】
2015007919.tif 000006
【００３９】
そして、以下の式によって算出される座標（Ｘ，Ｙ）と、逆正接関数を用いることによって方向θHを算出する。
【数５】
2015007919.tif 000007
【００４０】
（Ｓ１３４）次に、Homography行列判定部１３は、リファレンス画像の特徴点ｐの射影によって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|を算出する（図４（ｃ）参照）。方向θHは、具体的には、リファレンス画像からクエリ画像系へ射影された特徴点ｐから点ａへの方向である。
【００４１】
（Ｓ１３５）そして、Homography行列判定部１３は、角度誤差|θH−θ'|が所定角度以下となる点対応の組の数が、所定数以上となるまで、Ｓ１３１（第１のステップ）からＳ１３４（第４のステップ）までを繰り返す（図５（ａ）参照）。所定数とは、１組から４組までのいずれであってもよい。
そして、最終的に算出されたHomography行列Ｈは、全特徴点判定部１４へ出力される。
【００４２】
[全特徴点判定部１４]
全特徴点判定部１４は、Homography行列判定部１２によって出力されたHomography行列Ｈを用いて、リファレンス画像の特徴点全点を、クエリ座標系へ射影する（図２のＳ１４１参照）。そして、クエリ画像の特徴点ｐ'とリファレンス画像の特徴点ｐとの点対応集合における全ての点対応の組について、近傍点対応（inliner）か否かを判定する（図２のＳ１４２参照、図５（ｂ）参照）。ここでは、以下の３つの判定方法があって、いずれであってもよい。最終的に計数されたinlinerの数が、類似度算出部１５へ出力される。
【００４３】
（判定１）リファレンス画像の特徴点ｐを射影することによって得られた方向θHと、その点対応となるクエリ画像の特徴点ｐ'の方向θ'との角度誤差|θH−θ'|が、所定角度以下であるものをinlinerと判定する。所定角度としては、例えば２０°程度であってもよい。
【００４４】
（判定２）リファレンス画像の特徴点ｐをクエリ画像系に射影した点と、クエリ画像の特徴点ｐ'との距離誤差（ユークリッド距離）が、所定閾値以内であるものをinlinerと判定する。距離誤差は、例えば以下のように算出される。
｜ｐ'−ｓ2Ｈｐ｜
尚、距離誤差の算出方法は、マンハッタン距離等の他の公知の方法を用いてもよい。
【００４５】
（判定３）判定１及び判定２の両方の条件が成立した際に、inlinerと判定する。
【００４６】
［類似度算出部１５］
類似度算出部１５は、全特徴点判定部１４によって判定されたinlierの数を、類似度とする（図２のＳ１５参照）。ここで、類似度算出部１５は、Homography行列判定部１３及び全特徴点判定部１４の処理を複数回繰り返すように制御すると共に、inlierの数が最大となる点対応の組を導出し、その際のinlierの数を類似度とする。
【００４７】
以上、詳細に説明したように、本発明のプログラム、装置及び方法によれば、リファレンス画像とクエリ画像とが異なる視点から撮影された場合に、高精度な幾何検証を実現することができる。具体的には、リファレンス画像系からクエリ画像系へのHomography行列を用いて、リファレンス画像の特徴点の方向を補正することによって、従来技術に角度成分を加えた幾何検証を実現し、inlierの誤判定を削減することができる。
【００４８】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００４９】
１  類似度算出装置
１１  局所特徴点抽出部
１２  マッチング部
１３  Homography行列判定部
１４  全特徴点判定部
１５  類似度算出部
１６  リファレンス特徴点蓄積部
【図１】
2015007919.tif 000008
【図２】
2015007919.tif 000009
【図３】
2015007919.tif 000010
【図４】
2015007919.tif 000011
【図５】
2015007919.tif 000012