(57)【特許請求の範囲】
【請求項１】
質問画像群の各質問画像より局所特徴を抽出する局所特徴抽出部と、
前記各質問画像より抽出された局所特徴と、参照画像より予め抽出された局所特徴と、の間で幾何検証を行うことで、質問画像及び参照画像の間での特徴点対応組としてのインライアを算出する第一幾何検証部と、
前記質問画像群から選出した第一の質問画像及び第二の質問画像の間で、前記抽出された局所特徴によって幾何検証を行うことで、当該第一の質問画像及び第二の質問画像の間での特徴点対応組としてのインライアを算出する第二幾何検証部と、
第一の質問画像及び参照画像の間で前記第一幾何検証部で算出されたインライアと、第一の質問画像及び第二の質問画像の間で前記第二幾何検証部で算出されたインライアと、を統合することにより、当該参照画像との間で、第一の質問画像及び第二の質問画像の統合されたインライアを算出し、当該統合されたインライアに基づいて当該参照画像と前記質問画像群との類似度を算出するインライア統合部と、を備えることを特徴とする類似度算出装置。
【請求項２】
前記インライア統合部では、前記統合するに際して、第一の質問画像及び参照画像の間で前記第一幾何検証部で算出されたインライアに対して、第二の質問画像及び参照画像の間で前記第一幾何検証部で算出されたインライアのうち当該第二の質問画像のインライアにおける特徴点が、第一の質問画像及び第二の質問画像の間で前記第二幾何検証部で算出されたインライアにおける特徴点と一致しているものを合算することを特徴とする請求項１に記載の類似度算出装置。
【請求項３】
前記インライア統合部では、前記統合することにより、当該参照画像との間で、第一の質問画像及び第二の質問画像の統合されたインライアを算出し、さらに、当該統合されたインライアを、前記質問画像群より選出する第一の質問画像及び第二の質問画像の組み合わせに渡って集合和を取り、当該統合され集合和を取られたインライアに基づいて前記類似度を算出することを特徴とする請求項１または２に記載の類似度算出装置。
【請求項４】
前記インライア統合部では、第一の質問画像及び第二の質問画像の間で前記第二幾何検証部で算出されたインライアにおける構成インライア数が所定閾値に満たないような第一の質問画像及び第二の質問画像の組み合わせを、前記集合和を取る対象から除外することを特徴とする請求項３に記載の類似度算出装置。
【請求項５】
前記インライア統合部では、前記統合するに際して、参照画像の１つの特徴点に対して、第一の質問画像の特徴点及び第二の質問画像の特徴点の両者が対応している場合、当該両者のうち片方のみを残すことを特徴とする請求項１ないし４のいずれかに記載の類似度算出装置。
【請求項６】
前記第一幾何検証部にて幾何検証される参照画像は複数存在し、
当該複数の参照画像より予め抽出された局所特徴と、前記各質問画像より抽出された局所特徴と、を比較して、各質問画像と各参照画像との類似度を算出する個別類似度算出部をさらに備え、
前記第一幾何検証部では、前記個別類似度算出部で算出された類似度が上位と判定される参照画像についてのみ、質問画像との間で幾何検証を行い、
前記質問画像群の全体に関して前記個別類似度算出部で算出された各参照画像との類似度に基づいて、複数の参照画像のうち、当該質問画像群の全体に類似している候補としての候補参照画像を選定する候補参照画像選定部をさらに備え、
前記インライア統合部では複数の参照画像のうち当該候補参照画像のみを対象として、統合されたインライアを算出することを特徴とする請求項１ないし５のいずれかに記載の類似度算出装置。
【請求項７】
前記第一幾何検証部では、質問画像及び参照画像の間で特徴点対応組としてのインライアを、質問画像及び参照画像の所定の組み合わせ順番に従って算出し、当該順番に従って算出している途中で、算出されたインライアにおける構成インライア数が所定値以上となった場合には、当該所定値以上となった参照画像を、前記質問画像群に類似するものとして出力することを特徴とする請求項６に記載の類似度算出装置。
【請求項８】
コンピュータを請求項１ないし７のいずれかに記載の類似度算出装置として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の質問画像を入力とし、単一の参照画像との幾何検証によって得られるインライアを統合することによって、一部の特徴点が得られなくなるようなノイズに頑健な類似度算出を実現する類似度算出装置及びプログラムに関する。
【背景技術】
【０００２】
非特許文献１のように、画像から抽出される局所特徴を用いて物体検索を行う方法が
ある。この方法では、物体をカメラ等の撮影手段で撮影した画像（質問画像）から局所特徴を抽出し、予め登録された物体の写る画像（参照画像）の局所特徴と比較することによって、物体を検索する。検索の正確性を高めるため，類似度上位N件の参照画像と質問画像の間で幾何検証(geometric verification)を行う。そして、幾何検証における条件を満たした特徴点対応組（inlier）の数を新たな画像間類似度とする。
【０００３】
この従来技術に関して、参照画像と質問画像に同一の物体が含まれているか否かを、閾値で判定したい場合もある。画像間類似度の閾値が大きいほど、検索システムの適合率が高くなるためである。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Philbin. J, Chum. O, Isard. M, Sivic. J, and Zisserman. A, "Object retrieval with large vocabularies and fast spatial matching," In Computer Vision and Pattern Recognition, pp. 1-8, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述の幾何検証では、次のような課題がある。すなわち、同一の物体を含む参照画像と質問画像間においても、オクル−ジョンや白飛び、視点変化等の様々なノイズのために一部の特徴点が得られず、その結果十分なinlier数が得られないことがある。
【０００６】
本発明は、上記従来技術の課題に鑑み、一部の特徴点が得られなくなるようなノイズがあるような場合であっても頑健に類似度を算出することのできる類似度算出装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、本発明は、質問画像群の各質問画像より局所特徴を抽出する局所特徴抽出部と、前記各質問画像より抽出された局所特徴と、参照画像より予め抽出された局所特徴と、の間で幾何検証を行うことで、質問画像及び参照画像の間での特徴点対応組としてのインライアを算出する第一幾何検証部と、前記質問画像群から選出した第一の質問画像及び第二の質問画像の間で、前記抽出された局所特徴によって幾何検証を行うことで、当該第一の質問画像及び第二の質問画像の間での特徴点対応組としてのインライアを算出する第二幾何検証部と、第一の質問画像及び参照画像の間で前記第一幾何検証部で算出されたインライアと、第一の質問画像及び第二の質問画像の間で前記第二幾何検証部で算出されたインライアと、を統合することにより、当該参照画像との間で、第一の質問画像及び第二の質問画像の統合されたインライアを算出し、当該統合されたインライアに基づいて当該参照画像と前記質問画像群との類似度を算出するインライア統合部と、を備えることを特徴とする。
【０００８】
また、前記インライア統合部では、前記統合するに際して、第一の質問画像及び参照画像の間で前記第一幾何検証部で算出されたインライアに対して、第二の質問画像及び参照画像の間で前記第一幾何検証部で算出されたインライアのうち当該第二の質問画像のインライアにおける特徴点が、第一の質問画像及び第二の質問画像の間で前記第二幾何検証部で算出されたインライアにおける特徴点と一致しているものを合算することを特徴とする。
【０００９】
さらに、本発明は、コンピュータを前記類似度算出装置として機能させるプログラムであることを特徴とする。
【発明の効果】
【００１０】
本発明によれば、同一の物体を撮影していることが想定される複数の質問画像と、単一の参照画像との幾何検証によって得られるインライアを統合することによって、一部の特徴点が得られなくなるようなノイズに対しても頑強に、参照画像との間のインライアを算出し、これに基づいて類似度を算出することができる。
【図面の簡単な説明】
【００１１】
【図１】一実施形態に係る類似度算出装置の機能ブロック図である。
【図２】一実施形態に係る類似度算出装置の動作のフローチャートである。
【図３】参照用局所特徴抽出部及び局所特徴抽出部の処理内容を説明するための図である。
【図４】第一幾何検証部及び第二幾何検証部の処理内容を説明するための図である。
【図５】候補参照画像選定部の処理内容を説明するための図である。
【図６】インライア統合部の処理内容を説明するための図である。
【図７】一実施形態に係るインライア統合による類似度算出のフローチャートである。
【図８】一実施形態に係る類似度算出装置の機能ブロック図である。
【発明を実施するための形態】
【００１２】
図１は、一実施形態に係る類似度算出装置の機能ブロック図である。類似度算出装置10は、参照用局所特徴抽出部1、参照特徴蓄積部2、局所特徴抽出部3、個別類似度算出部4、第一幾何検証部5、候補参照画像選定部6、第二幾何検証部7、インライア統合部8及びインライア蓄積部9を備える。
【００１３】
図２は、一実施形態に係る類似度算出装置10の動作のフローチャートである。以下、図２の各ステップを説明しながら、図１の各部の動作概要を説明する。また、図３〜図６は、図１の各部の処理内容を説明するための模式的な例を示す図であり、以下の説明において適宜、参照する。なお、図３は参照用局所特徴抽出部1及び局所特徴抽出部3を説明するための図であり、図４は第一幾何検証部5及び第二幾何検証部7を説明するための図であり、図５は候補参照画像選定部6を説明するための図であり、図６はインライア統合部8を説明するための図である。
【００１４】
図２にて、ステップS100では、多様な認識対象物体がそれぞれ撮影された参照画像群を入力として受け取った参照用局所特徴抽出部1が、各参照画像より局所特徴を抽出して参照特徴蓄積部2へと蓄積してから、ステップS200へ進む。図３の例では[1]に、１つの参照画像RP1より一連の局所特徴RF1が抽出された例が示されており、局所特徴RF1はそのIDが1〜8でそれぞれ指定される8つの局所特徴となっている。
【００１５】
ステップS200では、類似度算出装置10が各部2〜9の機能により、局所特徴抽出部3に入力された質問画像群より局所特徴を抽出し、ステップS100で蓄積した参照画像の局所特徴を用いてインライアを統合することにより、データ線L2で示すように、インライア統合部8において質問画像群と参照画像との類似度を算出する。あるいは、当該算出の途中において、質問画像群の中で参照画像との類似度が高いと判定されるものが見つかった場合は、データ線L1で示すように、第一幾何検証部5においてその類似度を出力することもできる。
【００１６】
当該ステップS200において、各部2〜9は以下のように機能する。
【００１７】
まず、局所特徴抽出部3は、同一の物体を撮影したM(>1)枚の質問画像群を入力として受け取り、各質問画像から局所特徴を抽出して個別類似度算出部4、第一幾何検証部5及び第二幾何検証部7へと出力する。図３の例では、[2],[3]にそれぞれ、当該M枚の質問画像のうちの2枚の例として質問画像QP1,QP2が示され、それぞれ一連の局所特徴QF1,QF2が抽出された例が示されている。
【００１８】
図３の[2],[3]に示す質問画像QP1,QP2は、撮影されている物体が同図の[1]に示す参照画像RP1の物体（建物）である場合を例としている。従って、撮影がノイズ等なく理想的な状況でなされたとするならば、[1]の一連の局所特徴RF1におけるID1〜8で指定される局所特徴に対応する局所特徴が全て質問画像QP1,QP2から抽出されるはずである。しかし、[2],[3]に示す質問画像QP1,QP2では、オクルージョン領域OCL1,OCL2の存在によって一部分の局所特徴が抽出できない場合が例として示されている。
【００１９】
すなわち、[2]の一連の局所特徴QF1においては、理想的には[1]のID1〜8に対応するID11〜18の8個の局所特徴が抽出されるべきところを、質問画像QP1のオクルージョン領域OCL1によりID5に対応すべきID15の局所特徴は抽出不能となり、ID11〜14,16〜18の7個のみの局所特徴が抽出されている。同様に、[3]の一連の局所特徴QF2においては、理想的には[1]のID1〜8に対応するID21〜28の8個の局所特徴が抽出されるべきところを、質問画像QP2のオクルージョン領域OCL2によりID2,3に対応すべきID22,23の局所特徴は抽出不能となり、ID21,24〜28の6個のみの局所特徴が抽出されている。
【００２０】
本発明によれば、質問画像QP1QP2等のようにオクルージョン等で撮影されている物体から本来抽出されるべき局所特徴が抽出不能となっている場合であっても、インライア統合部8において後述するような統合処理により、参照画像RP1から抽出されるべき一連の局所特徴RF1をいわば復元したうえで、参照画像RP1との類似度を算出することができる。なお、当該図３の例は、図４，６においても共通の例として利用する。
【００２１】
図１の各部2〜9の説明に戻り、個別類似度算出部4では、バグオブビジュアルワーズ(Bag-of-Visual-Words)その他の公知の画像間類似度算出方法によって、局所特徴抽出部3の抽出した各質問画像の局所特徴と、参照特徴蓄積部2に蓄積されている各参照画像と、の類似度を算出し、各質問画像につきそれぞれ類似度が上位のN件（Nは所定数）となる参照画像がいずれであったかの結果を第一幾何検証部5及び候補参照画像選定部6へと出力する。
【００２２】
第一幾何検証部5は、個別類似度算出部4が上記出力した結果における各質問画像とその類似度上位N件の参照画像との間で幾何検証を行い、当該幾何検証の結果として得られるインライア（幾何的な拘束条件を満たす特徴点の対応組）を候補参照画像選定部6へ出力すると共に、インライア蓄積部9に蓄積させる。
【００２３】
なお、第一幾何検証部5では、当該幾何検証の際に質問画像・参照画像間で得られたインライアの数が閾値S以上（Sは所定値）となるようなものがあった場合、当該質問画像によって当該参照画像を認識できたものとし、そこで処理を終了することができる。すなわち、データ線L1で示すように、当該閾値S以上のインライアの数を当該参照画像と質問画像との類似度として出力して類似度算出装置10全体としての処理（図２のステップS200）を終了し、候補参照画像選定部6以降の処理によりデータ線L2に示すような類似度を出力することを省略してもよい。詳しくは図７を参照して後述する。
【００２４】
図４の[1],[2]に、第一幾何検証部5による幾何検証の模式的な例が示されている。図４では、図３の質問画像QP1,QP2に対して個別類似度算出部4において参照画像RP1が上位類似度のものとして決定されたものとし、質問画像QP1,QP2と参照画像RP1との間でインライアを求めた例が示されている。
【００２５】
すなわち、図４の[1]では、[11]において質問画像QP1の局所特徴QF1の位置を変換行列H1-1によって参照画像RP1の座標系に変換して局所特徴QF10となすことが示され、[12]において当該共通の参照画像RP1の座標系において参照画像RP1の局所特徴RF1と変換された局所特徴QF10とで対応付け可能なものを選出して、太線に示すようなインライアの関係を得ることが示されている。当該インライアは{参照画像RP1における特徴ID, 質問画像QP1における特徴ID}というペアの形式で示すと、{ID1, ID11}, {ID3, ID13}, {ID4, ID14}, {ID8, ID18}である。
【００２６】
また、図４の[2]でも同様に、[21]において質問画像QP2の局所特徴QF2の位置を変換行列H2-1によって参照画像RP1の座標系に変換して局所特徴QF20となすことが示され、[22]において当該共通の参照画像RP1の座標系において参照画像RP1の局所特徴RF1と変換された局所特徴QF20とで対応付け可能なものを選出して、太線に示すようなインライアの関係を得ることが示されている。当該インライアは{参照画像RP1における特徴ID, 質問画像QP2における特徴ID}というペアの形式で示すと、{ID4, ID24}, {ID5, ID25}, {ID6, ID26}, {ID7, ID27}である。
【００２７】
候補参照画像選定部6では、第一幾何検証部5がデータ線L1で示す類似度の出力を行わなかった場合に、個別類似度算出部4の結果（M枚の質問画像のそれぞれにおける類似度が上位N件となるような参照画像がいずれであるかの結果）を受け取り、当該結果に高割合で含まれると判定される参照画像がいずれであるかを、第二幾何検証部7へと出力する。
【００２８】
なお、上記処理を行う候補参照画像選定部6の役割は、計算量の削減である。すなわち、参照特徴蓄積部2にその局所特徴が蓄積されている全ての参照画像のうち、局所特徴抽出部3に入力された質問画像群において撮影されている物体が撮影されている可能性が高いものを事前に絞り込み、第二幾何検証部7以降の処理対象として設定することで、全ての参照画像に対して第二幾何検証部7以降の処理をおこなう場合よりも計算量を削減する。
【００２９】
第二幾何検証部7では、局所特徴抽出部3に入力されたM枚の質問画像群のうち、所定手法で選択された一連の2枚（ペア）の間で幾何検証を実施し、インライアの数が閾値U以上（Uは所定値）となるペアを、幾何的整合が取れているものとしてインライア蓄積部9及びインライア統合部8へと出力する。なお、第二幾何検証部7の処理はインライア統合部8での統合処理のための前処理に相当する。
【００３０】
図４では[3]に、第二幾何検証部7による幾何検証を図４の[1],[2]（及び図３）に示したのと共通の質問画像QP1,QP2のペア間で実施した例が示されている。すなわち、[31]において質問画像QP2の局所特徴QF2の位置を変換行列H12-1によって質問画像QP1の座標系に変換して局所特徴QF21となすことが示され、[32]において当該共通の質問画像QP1の座標系において質問画像QP1の局所特徴QF1と変換された局所特徴QF21とで対応付け可能なものを選出して、太線に示すようなインライアの関係を得ることが示されている。当該インライアは{質問画像QP1における特徴ID, 質問画像QP2における特徴ID}というペアの形式で示すと、{ID11, ID21}, {ID14, ID24}, {ID16, ID26}, {ID17, ID27}, {ID18, ID28}である。
【００３１】
インライア統合部8では、候補参照画像選定部6で選定された参照画像のそれぞれに関して、局所特徴抽出部3に入力されたM枚の質問画像群との間の類似度を表すものとして、当該M枚の質問画像群における統合された類似度を出力する。当該出力により図２のステップS200は完了する。
【００３２】
当該統合処理の概要は次の通りである。すなわち、第二幾何検証部7で得られた幾何的な整合が取れたインライアを、類似度算出の対象となる参照画像における座標系において足し合わせることで、当該参照画像に対するインライアとして統合する。さらに、当該統合されたインライアを、第二幾何検証部7が出力した全ペアに関して足し合わせることにより、最終的なインライアを得ることができる。
【００３３】
なお、インライアは{参照画像における局所特徴ID, 質問画像における局所特徴ID}というペアの形で与えられるため、上記のように統合し足し合わせる際に、参照画像における同一の局所特徴IDに対して質問画像における複数の局所特徴IDが対応付けられることとなった場合、当該複数のうち1つの局所特徴IDのみを残し、他のIDは削除するようにしてよい。
【００３４】
図６は、図３，４の例と共通の例として、インライア統合部8の処理を模式的に示している。図６における上段側の[31],[32]は、第二幾何検証部7で得られた幾何的な整合が取れたインライアの例であり、図４の[3]内で[31],[32]として示したものと同一の例が再掲されている。すなわち、質問画像QP1,QP2間でのインライアが示されている。そして、類似度算出の対象となる参照画像が図３のRP1である場合に、その座標系において質問画像QP1,QP2のインライアを統合する例が図６において[11],[12],[41],[42]として示されている。
【００３５】
まず、[41]に示すように、質問画像QP2の局所特徴としては、対象としている参照画像RP1の座標系に変換した局所特徴QF210を用いる。この際、当初の局所特徴QF2の全て(ID21,24,25,26,27,28の合計6個の局所特徴)を利用するのではなく、[32]に示すように第二幾何検証部7によって質問画像QP1との間で幾何的整合の取れているもののみ(ID21,24,26,27,28の合計5個の局所特徴)を選別して、対象としている参照画像RP1の座標系に変換して局所特徴QF210となす。
【００３６】
当該選別により、質問画像QP2の局所特徴のうち、質問画像QP1,QP2の両者に写っている同じ物体に対応する（と想定される）局所特徴を自動で選別することができる。
【００３７】
なお、質問画像QP2の局所特徴を参照画像RP1の座標系における局所特徴QF210へと変換する関係は、第一幾何検証部5で質問画像QP2と参照画像RP1との間で幾何検証した際の関係（図４の[2]の変換H2-1）を用いてもよいし、第一幾何検証部5で質問画像QP1と参照画像RP1との間で幾何検証した際の関係（図４の[1]の変換H1-1）と第二幾何検証部7で質問画像QP1,QP2間で幾何検証部した際の関係（図４の[3]の変換H12-1）の積（変換H1-1 H12-1）を用いてもよい。図６の[41]には積（変換H1-1 H12-1）を用いる場合が記載されている。
【００３８】
さらに、[42]に示すように、当該選別され且つ対象としている参照画像RP1の座標系に変換された局所特徴QF210と参照画像RP1の局所特徴RF1とのインライア{ID4, ID24}, {ID6, ID26}, {ID7, ID27}を求める。
【００３９】
ここで、[42]に示すインライアは、既に計算済みの結果より自動で求めることができる。すなわち、質問画像QP2と参照画像RP1との間のインライアとして第一幾何検証部5で得られたもの（図４の[2]の[22]）のうち、質問画像QP2の側の局所特徴が、第二幾何検証部7において質問画像QP1の局所特徴と幾何的整合の取れているもののみを選別することで、[42]に示すインライアを求めることができる。
【００４０】
すなわち、第一幾何検証部5の結果として図４の[2]の[22]では{ID4, ID24}, {ID5, ID25}, {ID6, ID26}, {ID7, ID27}の4個のインライアが得られているが、このうちID25は第二幾何検証部7の検証結果において幾何的整合は取れていないため削除したものが、図６の[42]の3個のインライアである。
【００４１】
一方、図６の[11],[12]に示すように、質問画像QP1の局所特徴としては、第一幾何検証部5で参照画像RP1との間で幾何的整合の取れたものを全て利用する。すなわち、図６の[11],[12]は図４の[1]内の[11],[12]と同一であり、[12]に示すインライア{ID1, ID11}, {ID3, ID13}, {ID4, ID14}, {ID8, ID18}に含まれるものを質問画像QP1の局所特徴とする。
【００４２】
そして、図６にて[12]及び[42]に示すのが、参照画像RP1に対するインライアとして、質問画像QP1,QP2のインライアを統合する処理の例である。すなわち、[12]に示す質問画像QP1の局所特徴を参照画像RP1の座標で表現した局所特徴QF10においてインライアとなっている{ID1, ID11}, {ID3, ID13}, {ID4, ID14}, {ID8, ID18}と、[42]に示す質問画像QP2の局所特徴のうち質問画像QP1の局所特徴と幾何的整合の取れたものを選別し、参照画像RP1の座標系で表現した局所特徴QF210においてインライアとなっている{ID4, ID24}, {ID6, ID26}, {ID7, ID27}と、が統合される。
【００４３】
当該統合の際に、インライア{ID4, ID14}と{ID4, ID24}とは共に参照画像RP1のID4に対応するものであるので、片方のみを残す、例えば前者の{ID4, ID14}を残し後者の{ID4, ID24}は削除する。この際、ランダムに片方を選択して残してもよいし、対応する特徴ベクトル間の距離等に基づいて、例えば距離が小さいものを残すようにしてもよいし、付与されたIDの数値が大きいあるいは小さい方を残すようにしてもよい。
【００４４】
こうして、参照画像RP1に関して質問画像QP1,QP2のインライアを統合した結果はQP1起因の4個とQP2起因の3個のうち{ID4, ID24}を削除した2個との6個となる。具体的には以下に掲げる通りである。
{ID1, ID11}, {ID3, ID13}, {ID4, ID14}, {ID8, ID18}, {ID6, ID26}, {ID7, ID27}
【００４５】
上記の統合において、次のような効果を見て取ることができる。すなわち、質問画像QP1における参照画像RP1とのインライアに関して、単独の質問画像QP1から抽出された局所特徴においては取得できなかったID6,ID7に対応するものが、質問画像QP2（に対して質問画像QP1と幾何的整合を取ったもの）の局所特徴によって補充されて取得されている。本発明においてはこのようにして、オクルージョン等のノイズで取得不能となったインライアを取得することができる。
【００４６】
また、図６ではM枚の質問画像のうち単独の2枚のペアに関して統合処理を行う例が示されているが、その他の一連のペアにおいても同様に統合処理を実施し、一連の統合結果を足し合わせることにより、さらに補充されたインライアを取得することができる。図６の[12],[42]の例ではID2,ID5に対応するインライアは未取得であるが、QP1,QP2以外のその他のペアにおける統合処理から、ID2,ID5に対応するインライアも取得されることが期待される。
【００４７】
以上、図２の各ステップにおける図１の各部の動作の概要を説明した。以下、当該各部の動作の詳細を説明する。
【００４８】
[参照用局所特徴抽出部1及び局所特徴抽出部3について]
参照用局所特徴抽出部1及び局所特徴抽出部3ではそれぞれ参照画像及び質問画像群を対象として局所特徴を抽出する。当該抽出する処理は両部1,3において共通であり、以下の通りである。
【００４９】
局所特徴抽出処理では、入力された画像（参照画像又は質問画像群）から特徴点検出器を用いて特徴点を検出する。さらに、特徴量抽出器を用いて検出した特徴点位置における画像の局所的な特徴を局所特徴量と呼ばれるベクトル形式で抽出する。局所特徴抽出アルゴリズムには、一般的に知られているSIFT（スケール不変特徴量変換；Scale invariant feature transform）やSURF（Speeded Up Robust Features）、ORB（oriented BRIEF）、FREAK（Fast Retina Keypoint）等を利用することができる。これらの局所特徴は座標p=(x,y)，方向θ，スケールs，及び特徴ベクトルfにより特徴付けられる。また、通常一枚の画像から検出された特徴群は、プログラム（参照用局所特徴抽出部1や局所特徴抽出部3を実現するプログラム）上では配列に格納され，その配列の添え字を特徴点IDとして識別することができる。
【００５０】
[参照特徴蓄積部2について] 
参照特徴蓄積部2は、参照画像毎に、参照特徴蓄積部2で抽出された局所特徴（参照特徴）を蓄積し、個別類似度算出部4及び第一幾何検証部5からの参照に供する。
【００５１】
[個別類似度算出部4について] 
個別類似度算出部4では、単一の質問画像から抽出された局所特徴（質問特徴）を入力とし、参照特徴蓄積部2に蓄積された局所特徴を参照し、参照画像毎に類似度を算出することを、質問画像群の各画像について実施する。個別類似度算出部4における類似度算出方法には、一般的に知られているバグオブビジュアルワーズ（Bag-of-Visual-Words）等を利用することができる。
【００５２】
[第一幾何検証部5及び第二幾何検証部7について]
第一幾何検証部5は1枚の質問画像と1枚の参照画像との間で幾何検証を行い、第二幾何検証部7は2枚の質問画像間で幾何検証を行う。処理対象となっている画像はこのように異なるが、当該幾何検証の処理は両部5,7において共通であり、詳細は以下の通りである。なお、幾何検証処理の模式的な例は図４に示した通りである。
【００５３】
幾何検証処理では、異なる2枚の画像から抽出された局所特徴を入力とし、当該2枚の画像間において幾何的な拘束条件を満たす特徴点対応組（インライア）を算出する。初めに、局所特徴における座標pのマッチングを行う。マッチングの方法としては，局所特徴における特徴ベクトルfの距離が最も近いもの同士をマッチングさせてもよいし、他の方法でマッチングしてもよい。次に、マッチングされた特徴点対応組に対して、RANSAC(RANdom  SAmple Consensus)アルゴリズム等のロバスト推定法を用いて，一方の座標系から他方の座標系へのホモグラフィー(Homography)行列を算出する。最後に、一方の特徴点の座標をホモグラフィー行列を用いて射影し、対応している他方の特徴点の座標との距離がt以内（tは判定用の所定閾値）であれば、その特徴点対応組をインライアと判定する。
【００５４】
[候補参照画像選定部6について] 
候補参照画像選定部6では、M枚の質問画像群に対して、個別類似度算出部4が出力した類似度上位N件の参照画像IDを入力とし、その中に高確率で含まれる参照画像IDを選定する。参照画像IDの選定方法としては、M枚の質問画像に対して類似度上位N件に連続で指定回（所定値n回）以上含まれた場合に選定するようにしてもよいし、指定割合以上含まれた場合に選定するようにしてもよいし、その他の方法でもよい。
【００５５】
ここで、連続で指定回数以上含まれる場合に選定する際の連続とは、M枚の質問画像が時系列で並んでいるものとし、当該時系列上での連続である。
【００５６】
図５に、候補参照画像選定部6の処理の例を示す。[1]には入力例としてM=3枚の質問画像群に対して上位N=3件の参照画像IDの例が示されている。この場合、類似度上位N=3件内に連続してn=2回以上含まれた場合に選定するようにした結果が[2]に示され、ID=1の1枚の参照画像が選定されている。また、類似度上位N=3件内に合計して2回以上含まれた場合（割合で2/3以上含まれた場合）に選定するようにした結果が[3]に示され、ID=1,ID=2,ID=4の3枚の参照画像が選定されている。
【００５７】
[インライア蓄積部9について]
インライア蓄積部9は、第一幾何検証部5が出力した参照画像・質問画像間のインライアと、第二幾何検証部7の出力した質問画像間のインライアと、を蓄積し、インライア統合部8に対して当該各インライアを参照に供する。
【００５８】
[インライア統合部8について] 
インライア統合部8では、同一の参照画像に対して複数種類の質問画像との間で幾何検証を行った結果であるインライア群（前者）と、質問画像間で幾何検証を行った結果であるインライア群（後者）と、を入力とし、当該前者及び後者を統合したインライアを出力する。ここで、前者のインライア群は第一幾何検証部5より出力され、後者のインライア群は第二幾何検証部7により出力され、それぞれインライア蓄積部9へと蓄積されている。当該統合処理は以下（処理１）〜（処理４）の通りである。
【００５９】
（処理１）初めに、上記後者のインライア群を構成している各インライア（質問画像QPiと質問画像QPjとのインライアとする）につき、次の判断を行う。すなわち、質問画像QPiと質問画像QPjとの間で幾何検証を行った結果となるインライアの数を数え、閾値U以上であれば以降の処理に利用し、そうでなければ破棄する旨の判断を行う。
【００６０】
当該閾値判断により、閾値U以上の個数となるインライアは最終的に統合して得られるインライアの一部分を構成することとなり、閾値U未満の個数で破棄されたインライアは最終的に統合して得られるインライアを構成しないこととなる。当該閾値判断により、質問画像QPi,QPjが共通の物体を撮影しているか、また、少なくとも片方に大きすぎるノイズ等が現れていないか、等を判断し、最終的に統合して得られるインライアを適切なものとすることができる。
【００６１】
（処理２）上記（１）にて閾値U以上の判断となった質問画像QPi,QPj間のインライアに対して、合算処理を行う。当該合算処理は具体的には、対象としている同一の参照画像をRPkとすると、以下の通りである。当該合算処理は部分的な統合処理に相当する。
【００６２】
すなわち、参照画像RPkと一方の質問画像QPiとの間のインライアINL(RPk,QPi)に対して、参照画像RPkともう一方の質問画像QPjと間のインライアINL(RPk,QPj)のうち、当該もう一方の質問画像QPjのインライアにおける特徴点（局所特徴）が質問画像QPi,QPj間のインライアINL(QPi,QPj)における特徴点（局所特徴）と一致しているものを合算する。
【００６３】
当該合算の具体例は図６にて既に模式的に示してある。上記の一般的な合算を図６の例にあてはめると次の通りである。すなわち、参照画像RPk=RP1, 質問画像QPi,QPj=QP1,QP2とした例となっているのが図６であり、各インライアは以下に掲げる通りである。
【００６４】
INL(RP1,QP1)= {ID1,ID11},{ID3,ID13},{ID4,ID14},{ID8,ID18} …（図６の[12]）
INL(RP1,QP2)= {ID4,ID24}, {ID5,ID25}, {ID6,ID26}, {ID7,ID27} …（図４の[22]）
INL(QP1,QP2)={ID11,ID21}, {ID14,ID24}, {ID16,ID26}, {ID17,ID27}, {ID18,ID28} …（図６の[32]）
【００６５】
従って、参照画像RP1ともう一方の質問画像QP2との間のインライアINL(RP1,QP2)のうち、当該もう一方の質問画像QP2のインライアにおける特徴点（局所特徴）が質問画像QP1,QP2間のインライアINL(QP1,QP2)における特徴点（局所特徴）と一致しているものは以下の通りである。
{ID4,ID24}, {ID6,ID26}, {ID7,ID27} …（図６の[42]）
【００６６】
上記インライアを参照画像RP1と一方の質問画像QP1との間のインライアINL(RP1,QP1)に合算することにより、以下を得る。
{ID1,ID11},{ID3,ID13},{ID4,ID14},{ID8,ID18},{ID4,ID24},{ID6,ID26},{ID7,ID27} …（図６の[12]及び[42]）
【００６７】
（処理３）上記（処理２）にて合算して得たインライアにおいて、参照画像RPkのある局所特徴IDに対して質問画像QPi,QPjの両者の局所特徴IDが重複して対応しているものがある場合、そのいずれか片方（いずれでもよい）を削除することで、当該2枚の質問画像QPi,QPjを統合したインライアINL[統合](QPi,QPj)を得る。
【００６８】
上記の（図６の[12]及び[42]）の例であれば、参照画像RP1の局所特徴ID4に対して質問画像QP1の局所特徴ID14と質問画像QP2の局所特徴ID24とが重複して対応している、すなわち、局所特徴ID4に対して重複したインライア{ID4,ID14}及び{ID4,ID24}が存在するので、このいずれか片方を削除する。例えば{ID4,ID24}を削除して、以下のように統合されたインライアINL[統合](QP1,QP2)を得ることができる。
INL[統合](QP1,QP2)= {ID1,ID11},{ID3,ID13},{ID4,ID14},{ID8,ID18},{ID6,ID26},{ID7,ID27}
【００６９】
（処理４）上記の（処理１）〜（処理３）では質問画像のある組み合わせQPi,QPjに対して、（処理２）で破棄されない場合に当該組み合わせQPi,QPj間の統合されたインライアINL[統合](QPi,QPj)が求まっている。従って、当該破棄されずに求まった全ての組み合わせQPi,QPjについて得られたインライアを合算することにより、入力されたM枚の質問画像QP1,QP2,…,QPMに対する参照画像RPkの類似度を表すものとしてのインライアILN[統合](QP1,QP2,…,QPM)を以下の(式１)のように求める。
【００７０】
【数１】
0006399658.tif 000002
【００７１】
なお、上記の式で集合和を取る際には、上記の（処理３）と同様に、１つの参照画像RPkの局所特徴IDについては1つのインライアのみをカウントするように和を取るものとし、1つの参照画像RPkの局所特徴IDに対応する2以上の質問画像の局所特徴IDが存在する場合、そのうちの1つのみを残すものとする。
【００７２】
また、参照画像RPkと入力されたM枚の質問画像QP1,QP2,…,QPMとの類似度としては、上記求めた統合されたインライアILN[統合](QP1,QP2,…,QPM)の要素数（構成インライア数）を利用することができ、インライア統合部8における出力とすることができる。
【００７３】
以上、図１の各部1〜9のそれぞれにおける個別動作について詳細に説明した。
【００７４】
図７は、類似度算出装置10の各部2〜9がインライア統合により類似度を算出する際の一実施形態に係る動作のフローチャートである。なお、図７のフローは、図２のステップS200の詳細の一実施形態に相当する。図７の各ステップは以下の通りである。
【００７５】
ステップS1では、局所特徴抽出部3がM枚の質問画像の入力を受け取ってから、ステップS2へと進む。なお、当該入力されるM枚の質問画像においては、参照特徴蓄積部2に参照画像から抽出された局所特徴を有するような物体が撮影され続けていることが想定されている。当該複数M枚の質問画像は、動画像における一連のフレームとして取得されてもよいし、ユーザが個別にM回、静止画の撮影を行うことで取得されてもよいし、その他の手法によって取得されてもよい。
【００７６】
ステップS2では、M枚の質問画像のうちI番目(I=1,2,…, M)のものを以下ステップS3〜S8での処理対象に設定してから、ステップS3へ進む。なお、ステップS2,S9はI番目の各質問画像についての繰り返し処理を定義したものであり、ステップS2,S9で囲まれるステップS3〜S8がI番目の各質問画像について実行される。
【００７７】
ステップS3では、当該処理対象のI番目の質問画像より局所特徴抽出部3が局所特徴を抽出してから、ステップS4へ進む。ステップS4では、当該処理対象のI番目の質問画像より抽出された局所特徴を、参照特徴蓄積部2に蓄積された各参照画像RPk(k=1,2,…)の局所特徴と比較することにより、個別類似度算出部4が、I番目の質問画像と各参照画像との類似度を算出してから、ステップS5へ進む。
【００７８】
ステップS5では、ステップS4で得られたI番目の質問画像と各参照画像との類似度の結果において、類似度上位J(J=1,2,…,N)番目の参照画像を処理対象に設定してから、ステップS6へ進む。なお、ステップS5,S8は、類似度上位J(J=1,2,…,N)番目の参照画像の当該順位のインデクスJについての繰り返し処理を定義したものであり、ステップS5,S8で囲まれるステップS6,S7が各インデクスJにつき繰り返し実行される。当該繰り返す順番はJ=1,2,…,Nのように、最上位の1番目から初めて所定のN番目に至るまで昇順（順位では降順）とすることができるが、その他の所定の順番でもよい。
【００７９】
ステップS6では、第一幾何検証部5が当該I番目の質問画像と当該J番目の参照画像との間で幾何検証を行ってからステップS7へ進む。ステップS7では、ステップS6の幾何検証で得られたインライア数が所定の閾値S以上であるか否かによって場合分けが行われ、閾値S以上であった場合、第一幾何検証部5が前述の図１におけるデータ線L1で示す出力を類似度算出装置10からの最終結果として得たうえで、当該図７のフローは終了する。すなわち、M枚の質問画像に類似しているのは当該J番目の参照画像であり、その類似度は直近のステップS7で得られたインライア数であるという出力を最終結果として得たうえで、当該図７のフローを終了する。
【００８０】
なお、ステップS7で肯定判断を得てフローを終了する場合は、参照特徴蓄積部2に複数の参照画像の局所特徴が蓄積されておりこの中から質問画像に類似しているものを探すという検索用途において、次のような効果を奏することができる。すなわち、M枚の質問画像のうちの1枚において参照画像のうちの１つと十分に類似していると判断されるものが見つかったので、当該見つかった時点で処理を終了することにより計算量を抑制することができる。
【００８１】
一方、ステップS7で否定判断であった場合（インライア数が所定の閾値S未満であった場合）、ステップS8へ進む。ステップS8では順位インデクスJ=1,2,…,Nの全てのJについて以上のステップS6,S7の処理が完了したか否かが判定され、完了していればステップS9へ進む。一方、未完了であればステップS5に戻り、処理が未完了のインデクスJを処理対象に設定したうえでステップS6,S7の処理を継続する。
【００８２】
ステップS9ではインデクスIで指定される全ての質問画像につき以上のステップS3〜S8の処理が完了したか否かが判定され、完了していればステップS10へ進む。一方、未完了であればステップS2へ戻り、処理が未完了のインデクスI（未処理のI番目の質問画像）を処理対象に設定したうえで、ステップS3〜S8の処理を継続する。
【００８３】
ステップS10では、候補参照画像選定部6が、以上の繰り返された一連のステップS4の結果（M枚の質問画像のそれぞれに対しての上位N件の参照画像の結果）を参照して、当該M枚の質問画像に類似していると考えられる候補としての参照画像（候補参照画像）を選定してから、ステップS11へ進む。
【００８４】
ステップS11では、候補参照画像のうち1枚を以下のステップS12〜S17の処理対象に設定してから、ステップS12へ進む。なお、ステップS11,S18は、候補参照画像の各々についての繰り返し処理を定義したものであり、ステップS11,S18で囲まれるステップS12〜S17が候補参照画像の各々を対象として繰り返し実行される。
【００８５】
ステップS12では、M枚の質問画像の中から2枚の組み合わせQPi,QPjを以下のステップS13〜S15の処理対象に設定してから、ステップS13へ進む。なお、ステップS12,S16は、M枚の質問画像の中から2枚の組み合わせQPi,QPjの各々についての繰り返し処理を定義したものであり、ステップS12,S16で囲まれるステップS13〜S15が当該2枚の組み合わせの各々を対象として繰り返し実行される。
【００８６】
ここで、ステップS12〜S16の繰り返し処理の対象となる質問画像の2枚の組み合わせQPi,QPjに関しては、M枚の質問画像の中から選ぶ所定の組み合わせとすればよい。例えば、M枚の質問画像のうち隣接する2枚の全ての組み合わせ(QP1及びQP2、QP2及びQP3、…、QPM-1及びQPM)としてM-1通りを用いてもよいし、M枚の中から2枚を選ぶ全ての組み合わせ（組み合わせ総数=MC2=M(M-1)/2通り）としてもよい。
【００８７】
ステップS13では、当該処理対象に設定された質問画像の2枚の組み合わせQPi,QPj間で、第二幾何検証部7が幾何検証を実施してから、ステップS14へ進む。ステップS14では、ステップS13の幾何検証の結果のインライア数が所定の閾値U以上であるか否かが判定され、閾値U以上であればステップS16へ進み、閾値U未満であればステップS15へ進む。
【００８８】
ステップS15では、インライア数が当該閾値U未満であった組み合わせQPi,QPjのインライアを破棄する旨の判断を下してから、ステップS16へ進む。
【００８９】
ステップS16では、以上のステップS13〜S15の処理が、処理対象として想定している全ての質問画像の組み合わせQPi,QPjについて完了したか否かが判定され、完了していればステップS17へ進み、未完了であればステップS12に戻り、未完了の組み合わせQPi,QPjを処理対象に設定したうえでステップS13〜S15を継続する。
【００９０】
ステップS17では、当該対象としている候補参照画像RPkに関して、以上のステップS12〜S16のループ処理で得られた一連の結果に基づき、M枚の質問画像についての統合されたインライアをインライア統合部8が出力してから、ステップS18へ進む。
【００９１】
なお、インライア統合部8に関して前述した（処理１）〜（処理４）が、以上のステップS14〜S17に相当し、ステップS17では前述の(式1)に従って統合されたインライアを出力する。従って例えば、ステップS17における統合の際、ステップS15を経由して破棄の判断がなされた質問画像の組み合わせQPi,QPjは、統合対象には利用されないこととなる。
【００９２】
ステップS18では、ステップS10で選定された全ての候補参照画像について以上のステップS12〜S17の処理が完了したか否かが判定され、完了していればステップS19へ進み、未完了の候補参照画像があればステップS11に戻り、未完了のものを処理対象に設定したうえでステップS12〜S17の処理を継続する。
【００９３】
ステップS19では、一連の候補参照画像につきそれぞれステップS17で得られた結果を比較して、インライア統合部8がそのうちM枚の質問画像に最類似と判断される参照画像（すなわち、統合して得られたインライア数が最大となるような参照画像）を出力して、当該図７のフローは終了する。最類似のものを出力する場合、類似度算出装置10は自身が算出した類似度に基づいて、M枚の質問画像に類似するものを参照特徴蓄積部2から見つけ出す検索機能を担うこととなる。
【００９４】
また、ステップS19は最類似と判定される１つを出力し、上記のように検索機能を実現する他にも、類似度上位と判定されるものを出力するようにしてもよい。また、ステップS19は省略され、一連のステップS17で得られる結果をそれぞれ類似度算出装置10からの出力として採用するようにしてもよい。
【００９５】
以上、本発明よれば、対象物を連続的に撮影する等によって取得された質問画像群に対して、適合率が高く、かつ一部の特徴点が得られなくなるようなノイズに対して頑健な類似度を算出することができる。特に、質問画像を複数入力することによって、単一の質問画像で得られなかった一部の特徴点を、他の質問画像を用いて補完する効果が期待できる。また、当該算出された類似度に基づいて検索システムないし装置を実現することもできる。
【００９６】
以下、本発明における（説明の流れの観点からの）補足的事項を説明する。
【００９７】
（補足１）以上の説明においても適宜言及したが、類似度算出装置10の図１の構成において、個別類似度算出部4及び候補参照画像選定部6に関しては、次のような役割を果たすものである。すなわち、参照特徴蓄積部2に複数の参照画像に関する局所特徴が蓄積されており、当該複数の参照画像の中から入力されたM枚の質問画像群に類似するものを見つけ出す際に、類似度上位の可能性が高いものに予め絞り込むことで計算量を削減するという役割であり、類似度算出装置10によって検索装置を実現する場合に好適な役割である。
【００９８】
従って、参照特徴蓄積部2に1枚のみの参照画像から抽出された局所特徴が蓄積されており、当該単独の参照画像との間での類似度（統合されたインライア）を算出する場合や、複数の参照画像から抽出された局所特徴が蓄積されているが、その全てとの間で類似度を算出する場合には、個別類似度算出部4及び候補参照画像選定部6を省略してもよい。
【００９９】
図８に、上記のように個別類似度算出部4及び候補参照画像選定部6を省略した際の一実施形態に係る類似度算出装置10の機能ブロック図を示す。当該構成における動作は以上の説明より明らかであるが、図１の構成との差異点に注目して説明すると以下の通りである。
【０１００】
すなわち、局所特徴抽出部3では、M枚の質問画像よりそれぞれ抽出した局所特徴を第一幾何検証部5及び第二幾何検証部7に出力する。参照特徴蓄積部2は、1枚以上の参照画像RPkの局所特徴を蓄積し、第一幾何検証部5の参照に供する。
【０１０１】
第一幾何検証部5では、（図１のように個別類似度算出部4による上位のものに限定されず）M枚の質問画像の各々と、参照特徴蓄積部2にその局所特徴が蓄積された全ての各参照画像との間で幾何検証を実施する。すなわち、図７のフローにおいては、ステップS5が「類似度上位J番目の参照画像を処理対象に設定」から、「ある1枚の参照画像を処理対象に設定」へと変更され、ステップS8の繰り返し判断も「参照特徴蓄積部2にその局所特徴が蓄積された全ての参照画像について処理が完了したか否か」という判断へと変更される。
【０１０２】
また、同様に、候補参照画像選定部6が省略されることにより、第二幾何検証部7及びインライア統合部8においても、参照特徴蓄積部2にその局所特徴が蓄積された全ての参照画像に関して処理が行われる。すなわち、図７のフローにおいては、ステップS10の候補参照画像選定の処理が省略されると共に、ステップS11は、「１枚の候補参照画像を処理対象に選定する」ものから「1枚の参照画像を処理対象に選定する」ものへと変更され、対応するステップS18も、「参照特徴蓄積部2にその局所特徴が蓄積された全ての参照画像について処理が完了したか否か」という判断へと変更される。
【０１０３】
なお、ステップS19に関しては以上説明したのと同様にして、最類似のものや類似度上位のものを出力するようにしてもよい。
【０１０４】
（補足２）インライア統合部8では、統合されたインライアにおける構成インライア数をそのまま類似度として出力するものとして説明したが、その他にも統合されたインライアに基づいて類似度を算出するようにしてもよい。例えば、統合されたインライアを構成する各インライアにおける局所特徴の特徴ベクトルf同士の距離の総和を求め、当該総和が小さいほど類似度が大きいものとして算出するようにしてもよい。当該距離の計算に際してさらに、局所特徴における特徴ベクトルfに加えて、スケールs及び／又は方向θも考慮して、距離計算を実施するようにしてもよい。例えば、当該3つの量を合わせたベクトル(f,s,θ)間の距離を計算するようにしてもよい。
【０１０５】
（補足３）図４，６等のインライアの説明においては、模式的に示すために異なる画像間で座標系を共通のものに揃えたうえで太線によって対応関係を表現しているが、インライアは異なる画像間での幾何的整合の取れた局所特徴同士の対応関係であり、図４，６のように座標系を変換した情報を含んでいなくともよい。ただし、当該対応関係を求める際には座標系の変換の計算は行われることとなる。
【０１０６】
（補足４）図１や図８に示す類似度算出装置10の任意の一部分をサーバ等の外部構成によって実現して、ネットワークを介して各部における情報をやりとりすることにより本発明を実施してもよい。
【０１０７】
（補足５）本発明は、コンピュータを類似度算出装置10の各部1〜9の全て又はその任意の一部分として機能させるプログラムとしても提供可能である。当該コンピュータには、CPU(中央演算装置)、メモリ及び各種I/Fといった周知のハードウェア構成のものを採用することができ、CPUが類似度算出装置10の各部の機能に対応する命令を実行することとなる。
【符号の説明】
【０１０８】
10…類似度算出装置、1…参照用局所特徴抽出部、2…参照特徴蓄積部、3…局所特徴抽出部、4…個別類似度算出部、5…第一幾何検証部、6…候補参照画像選定部、7…第二幾何検証部、8…インライア統合部8…インライア蓄積部
【図１】
0006399658.tif 000003
【図２】
0006399658.tif 000004
【図３】
0006399658.tif 000005
【図４】
0006399658.tif 000006
【図５】
0006399658.tif 000007
【図６】
0006399658.tif 000008
【図７】
0006399658.tif 000009
【図８】
0006399658.tif 000010