(57)【要約】【課題】ビュー変化がある場合であってもロバストな特徴量を得る。【解決手段】入力画像より登録対象としての登録特徴集合を求める特徴量登録装置10であって、前記入力画像及び／又は当該入力画像を加工して得られる１つ以上の加工画像より疑似クエリ特徴集合を生成する疑似クエリ特徴生成部1と、登録特徴候補集合を生成する登録特徴候補生成部2と、前記疑似クエリ特徴集合の各要素と前記登録特徴候補集合の各要素との間でマッチングを行う特徴マッチング部31と、特徴マッチング部31によるマッチング結果に基づき、登録特徴候補集合の各要素につき、疑似クエリ特徴集合の要素との間の類似度スコア和を求める類似度スコア計算部32と、求めた類似度スコア和に基づいて選択される登録特徴候補集合の要素を用いて、登録特徴集合の要素を決定することで、前記登録特徴集合を求める登録特徴生成部33と、を備える。【選択図】図１
2018120395.tif 000002
【特許請求の範囲】
【請求項１】
入力画像より登録対象としての登録特徴集合を求める特徴量登録装置であって、
前記入力画像及び／又は当該入力画像を加工して得られる１つ以上の加工画像より疑似クエリ特徴集合を生成する疑似クエリ特徴生成部と、
登録特徴候補集合を生成する登録特徴候補生成部と、
前記疑似クエリ特徴集合の各要素と前記登録特徴候補集合の各要素との間でマッチングを行う特徴マッチング部と、
前記特徴マッチング部によるマッチング結果に基づき、前記登録特徴候補集合の各要素につき、前記疑似クエリ特徴集合の要素との間の類似度スコア和を求める類似度スコア計算部と、
前記求めた類似度スコア和に基づいて選択される前記登録特徴候補集合の要素を用いて、前記登録特徴集合の要素を決定することで、前記登録特徴集合を求める登録特徴生成部と、を備えることを特徴とする特徴量登録装置。
【請求項２】
前記登録特徴候補集合の少なくとも一部の要素同士の間においては、互いに同一対象の同一箇所から抽出された特徴である旨を規定する同一対象同一箇所情報が予め与えられており、
前記特徴マッチング部及び／又は前記類似度スコア計算部では、前記同一対象同一箇所情報を用いて、前記マッチングする処理及び／又は前記類似度スコア和を求める処理をそれぞれ行うことを特徴とする請求項１に記載の特徴量登録装置。
【請求項３】
前記特徴マッチング部では、前記疑似クエリ特徴集合の各第一要素につき、前記登録特徴候補集合の各第二要素との間でマッチングするか否かの判定を行うに際して、当該第二要素との間で前記同一対象同一箇所情報の関係がある前記登録特徴候補集合のその他の第二要素を、当該マッチングするか否かの判定材料から除外することを特徴とする請求項２に記載の特徴量登録装置。
【請求項４】
前記特徴マッチング部では、前記疑似クエリ特徴集合の各第一要素につき、前記登録特徴候補集合の各第二要素との間でマッチングするか否かの判定を、当該第一要素との類似度の順位が上位の所定位以内にある場合に、当該マッチングするものとして判定することを特徴とする請求項３に記載の特徴量登録装置。
【請求項５】
前記類似度スコア計算部では、所定種類の重み付け和によって前記類似度スコア和を求めることを特徴とする請求項２ないし４のいずれかに記載の特徴量登録装置。
【請求項６】
前記登録特徴生成部では、前記求めた類似度スコア和が最大となる前記登録特徴候補集合の要素を前記選択することを特徴とする請求項１ないし５のいずれかに記載の特徴量登録装置。
【請求項７】
前記登録特徴生成部では、前記選択された登録特徴候補集合の要素に対して、前記マッチング部によってマッチングされている各要素に基づいて、前記登録特徴集合の要素を決定することを特徴とする請求項１ないし６のいずれかに記載の特徴量登録装置。
【請求項８】
前記登録特徴生成部では、前記選択された登録特徴候補集合の要素に対して、前記マッチング部によってマッチングされている各要素を平均したものとして、前記登録特徴集合の要素を決定することを特徴とする請求項１ないし７のいずれかに記載の特徴量登録装置。
【請求項９】
前記登録特徴生成部では、前記選択された登録特徴候補集合の要素に対して、前記マッチング部によってマッチングされている各要素を平均したものを求め、当該平均した要素によって前記登録特徴候補集合を暫定更新した暫定更新集合を対象として前記特徴マッチング部及び前記類似度スコア計算部による処理を適用することで当該平均した要素について計算される類似度スコア和が、前記選択された登録特徴候補集合の要素における類似度スコア和よりも小さくなる場合、前記選択された登録特徴候補集合の要素をそのまま前記登録特徴集合の要素として採用し、当該小さくならない場合、前記平均した要素を前記登録特徴集合の要素として採用することを特徴とする請求項１ないし７のいずれかに記載の特徴量登録装置。
【請求項１０】
前記登録特徴生成部では、前記登録特徴集合の要素を１つずつ決定し、当該決定する都度、当該決定された要素に対応する前記疑似クエリ特徴集合の要素による寄与分を前記類似度スコア和から減算することで当該類似度スコア和を更新すると共に、当該更新された類似度スコア和に基づいて、且つ、前記決定された要素に対応する前記疑似クエリ特徴集合の要素は以降に前記登録特徴集合の要素を決定するための参照対象からは除外することで、前記登録特徴集合の要素の次の１つをさらに決定することを所定回数繰り返すことを特徴とする請求項１ないし９のいずれかに記載の特徴量登録装置。
【請求項１１】
前記登録特徴候補生成部では、前記疑似クエリ特徴生成部で生成された疑似クエリ特徴集合を、または、前記登録特徴生成部が既に生成した登録特徴を、前記登録特徴候補集合として採用することを特徴とする請求項１ないし１０のいずれかに記載の特徴量登録装置。
【請求項１２】
前記加工画像の各々は、前記入力画像を幾何変換したものとして、及び／又は、前記入力画像に写っている物体のテクスチャを含む所定の３Dデータに基づくリンダリングを行ったものとして、得られる画像であることを特徴とする請求項１ないし１１のいずれかに記載の特徴量登録装置。
【請求項１３】
入力画像より登録対象としての登録特徴集合を求める特徴量登録方法であって、
前記入力画像及び／又は当該入力画像を加工して得られる１つ以上の加工画像より疑似クエリ特徴集合を生成する疑似クエリ特徴生成段階と、
登録特徴候補集合を生成する登録特徴候補生成段階と、
前記疑似クエリ特徴集合の各要素と前記登録特徴候補集合の各要素との間でマッチングを行う特徴マッチング段階と、
前記特徴マッチング段階によるマッチング結果に基づき、前記登録特徴候補集合の各要素につき、前記疑似クエリ特徴集合の要素との間の類似度スコア和を求める類似度スコア計算段階と、
前記求めた類似度スコア和に基づいて選択される前記登録特徴候補集合の要素を用いて、前記登録特徴集合の要素を決定することで、前記登録特徴集合を求める登録特徴生成段階と、を備えることを特徴とする特徴量登録方法。
【請求項１４】
コンピュータを請求項１ないし１２のいずれかに記載の特徴量登録装置として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビュー変化がある場合であってもロバストな特徴量を得ることのできる特徴量登録装置、方法及びプログラムに関する。
【背景技術】
【０００２】
非特許文献１および2の様に、画像から抽出される局所特徴を用いて物体検索を行う技術がある。これらの技術では、予めデータベースに登録する画像から局所特徴を抽出し，任意のデータベース（以下、DBと略記する。）作成方法に従ってDBを構築する。実行時には、物体をカメラ等の撮影手段で撮影した画像をクエリ画像とし、局所特徴を抽出する。これらの特徴をDB内の特徴とマッチングすることによって、クエリ画像とDB画像と間の類似度を計算することで、物体検索結果を得る。
【０００３】
当該検索処理の高速化やメモリ使用量削減等のため、特徴点の持つ特徴ベクトルはVisual Word(ビジュアルワード。以下、VWと略記する。)と呼ばれる代表ベクトルに量子化される。その際には、一般的に特徴点の持つ特徴ベクトルの最近傍となるVWに量子化される。しかし、撮影された画像から抽出される特徴ベクトルは、登録時との撮影視点の差異や、撮影画像のぼけ、ぶれ等の様々な要因によって変化しうる。そのため、DBに登録された物体の同一位置から抽出された特徴ベクトルであっても、異なるVWに量子化されてしまうことがある。これを量子化誤りと呼ぶ。
【０００４】
この問題に対し、非特許文献１では、特徴点の特徴ベクトルをk近傍となる複数のVWに割り当て(Soft Assignment)た上でDBに登録することによって、量子化誤りの影響を緩和している。
【０００５】
また、非特許文献2では、元々の特徴ベクトルをよりコンパクトなバイナリベクトルに変換し、VWと合わせてデータベースに格納している。そして、クエリ側とDB側で同一VWとなった特徴の持つバイナリベクトル間の距離を測定し、類似度スコアの重み付けに利用している。また、この距離を特徴マッチングの判断にも利用している。すなわち，距離が閾値以内である場合のみマッチングする、または、クエリ側の特徴にとってデータベース側の特徴がk近傍に位置する場合のみマッチングする、という判断である。さらに、特徴点の持つオリエンテーションやスケールを利用することによって，幾何的整合性の無いマッチをフィルタリングし，検索精度を改善している。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Philbin, James, et al. "Lost in quantization: Improving particular object retrieval in large scale image databases." Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on. IEEE, 2008.
【非特許文献２】Jegou, Herve, Matthijs Douze, and Cordelia Schmid. "Hamming embedding and weak geometric consistency for large scale image search." Computer Vision-ECCV 2008. Springer Berlin Heidelberg, 2008. 304-317.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した非特許文献１，２等の従来の技術では、クエリ側とDB側でのビューの変化に対する考慮がなされていなかった。すなわち、局所特徴にはビューが変化した際の特徴点検出のロバスト性および特徴量のロバスト性があるにも関わらず、それらに対する考慮がなされていなかった。
【０００８】
なおここで、ビューとはクエリ画像およびDB画像において物体を撮影する際のカメラ視点の位置及び姿勢、光源位置及び方向、ピント設定、カメラ移動（ブレ）状態その他といったような、物体を撮影して画像を得る際にその見た目を変化させる任意の条件をいうものとする。また、画像は実際の物体をカメラで物理的に撮影して得られるもの（実写）に限らず、コンピュータグラフィックス（以下、CGと略記する。）手法で合成される画像や、当該CG手法及び実写を組み合わせて得られる画像も含むものとする。
【０００９】
上記従来技術の課題に鑑み、本発明は、ビュー変化がある場合であってもロバストな特徴量を得ることのできる特徴量登録装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、本発明は、入力画像より登録対象としての登録特徴集合を求める特徴量登録装置であって、前記入力画像及び／又は当該入力画像を加工して得られる１つ以上の加工画像より疑似クエリ特徴集合を生成する疑似クエリ特徴生成部と、登録特徴候補集合を生成する登録特徴候補生成部と、前記疑似クエリ特徴集合の各要素と前記登録特徴候補集合の各要素との間でマッチングを行う特徴マッチング部と、前記特徴マッチング部によるマッチング結果に基づき、前記登録特徴候補集合の各要素につき、前記疑似クエリ特徴集合の要素との間の類似度スコア和を求める類似度スコア計算部と、前記求めた類似度スコア和に基づいて選択される前記登録特徴候補集合の要素を用いて、前記登録特徴集合の要素を決定することで、前記登録特徴集合を求める登録特徴生成部と、を備えることを特徴とする。
【００１１】
また、本発明は、入力画像より登録対象としての登録特徴集合を求める特徴登録方法であって、前記入力画像及び／又は当該入力画像を加工して得られる１つ以上の加工画像より疑似クエリ特徴集合を生成する疑似クエリ特徴生成段階と、登録特徴候補集合を生成する登録特徴候補生成段階と、前記疑似クエリ特徴集合の各要素と前記登録特徴候補集合の各要素との間でマッチングを行う特徴マッチング段階と、前記特徴マッチング段階によるマッチング結果に基づき、前記登録特徴候補集合の各要素につき、前記疑似クエリ特徴集合の要素との間の類似度スコア和を求める類似度スコア計算段階と、前記求めた類似度スコア和に基づいて選択される前記登録特徴候補集合の要素を用いて、前記登録特徴集合の要素を決定することで、前記登録特徴集合を求める登録特徴生成段階と、を備えることを特徴とする。さらに、本発明は、コンピュータを前記特徴量登録装置として機能させるプログラムであることを特徴とする。
【発明の効果】
【００１２】
本発明によれば、ビュー変化がある場合であってもロバストな特徴量を得ることができる。
【図面の簡単な説明】
【００１３】
【図１】一実施形態に係る特徴量登録装置の機能ブロック図である。
【図２】一実施形態に係る特徴量登録装置の動作のフローチャートである。
【図３】一実施形態に係る疑似クエリ特徴生成部の詳細を示す機能ブロック図である。
【図４】画像同士に同一対象の幾何変換関係がある場合のディストラクタの関係（及びその逆としての同一対象同一箇所の関係）を説明するための図である。
【発明を実施するための形態】
【００１４】
図１は、一実施形態に係る特徴量登録装置の機能ブロック図である。当該図示する通り、特徴量登録装置10は、疑似クエリ特徴生成部1、登録特徴候補生成部2、反復処理部3及び特徴量記憶部4を備え、反復処理部3はさらに特徴マッチング部31、類似度スコア計算部32及び登録特徴生成部33を備える。
【００１５】
まず、特徴量登録装置10の全体動作は、画像を入力として読み込み、ビュー変化が発生していることが想定される当該画像に適した登録特徴集合を出力する、というものである。本発明によれば特に、クエリ側とDB側でビューの変化が想定される場合にも、特徴マッチングを介して得られる類似度スコアを最大化するような特徴集合として、登録特徴集合を出力することが可能である。
【００１６】
例えば、ビュー変化が具体的には画像の撮影の際のカメラの位置姿勢の変化である場合であれば、特徴量登録装置10によって得られる登録特徴集合は、画像を撮影する際のカメラの位置姿勢が色々と変動しても、当該変動範囲に渡って全体最適化されたものとなり、どのような位置姿勢において撮影された場合であってもロバストに特徴マッチングを可能とするものとなる。
【００１７】
さらに、本発明の一実施形態によれば、Distractor（ディストラクタ、不正解の選択肢）の存在を仮定した上での類似度スコアの最大化を目指すものとして、登録特徴集合を出力することが可能である。ここで、特徴検索問題において一般に、クエリ側の特徴にとっての不正解の選択肢、すなわちディストラクタは不可避な存在であるが、本発明においては、当該ディストラクタの存在を仮定したうえでの類似度スコアの最大化を目指すような登録特徴集合を出力することもできる。詳細は後述する。 
【００１８】
なお、特徴量登録装置10が出力する登録特徴集合とは、当該画像の特徴集合としてDBへと登録するのに上記のような観点から適したものを意味し、用途として必ずしも登録（DBその他の何らかの媒体に恒久的又は一時的に記録されること）を必要とするものではない。
【００１９】
また、特徴量登録装置10のフレームワーク（主要な処理の流れ）は次の通りである。すなわち、求めるN個のDB特徴（登録特徴）の集合をX={x1, x2, …, xN}、任意のM個の疑似クエリ特徴の集合をQ={q1, q2, …, qM}、任意のL個のディストラクタの集合をD={d1, d2, …, dL}とし、任意の制約条件の下でQから最大の類似度スコアを得ることのできるXを生成するフレームワークである。（なお、前述の通り、実施形態によってはディストラクタ集合Dの利用は省略してもよい。）
【００２０】
以上が全体概略であり、図１に示す機能ブロック間のデータ授受の流れに関して、各部の処理内容の概略は以下の通りである。
【００２１】
疑似クエリ特徴生成部1は、特徴量登録装置10への入力としての画像を読み込み、疑似クエリ特徴集合Qを生成して、特徴マッチング部31へと出力する。実施形態によっては疑似クエリ特徴生成部1はさらに、線L21で示すように当該生成した疑似クエリ特徴集合Qを登録特徴候補生成部2へも出力するようにしてもよいし、線L31で示すように当該生成する際に得られるディストラクタ情報（後述）を反復処理部3へと出力するようにしてもよい。
【００２２】
登録特徴候補生成部2は、特徴量登録装置10からの最終的な出力としての登録特徴集合を得るのに候補として用いるための登録特徴候補集合を生成し、特徴マッチング部31へと出力する。登録特徴候補集合を当該生成するための入力は線L21,L22,L23で示すような各実施形態のいずれかが可能であり、線L21で示されるように疑似クエリ特徴生成部1から得られる疑似クエリ特徴集合を用いてもよいし、線L22で示されるように登録特徴生成部33から得られる登録特徴集合を用いてもよいし、線L23で示されるように特徴量記憶部4に予め記憶されている特徴集合を用いてもよい。
【００２３】
反復処理部3は上記説明したフレームワークを実行するものであり、疑似クエリ特徴生成部1から得られる疑似クエリ特徴集合と、登録特徴候補生成部2から得られる登録特徴候補集合と、を入力とし、反復処理によって所定数N個の登録特徴集合を最終結果として出力する。詳細は図２を参照して後述するが、第一の反復処理として特徴マッチング部31及び類似度スコア計算部32において疑似クエリ特徴集合の各要素（qi）及び登録特徴候補集合の各要素（yj）を対象とした処理を行うことでマッチング結果及び類似度スコアが得られ、さらに当該得られたマッチング結果及び類似度スコアに基づく第二の反復処理を登録特徴生成部33において行うことでN個の登録特徴集合が得られる。第二の反復処理の各回においては図１に示すように得られているマッチング結果及び類似度スコアを更新すべき旨の指示が登録特徴生成部33より出力され、マッチング結果及び類似度スコアの更新が行われる。
【００２４】
反復処理部3の反復処理の各回における要素処理をそれぞれ実行するのが各部31,32,33である。特徴マッチング部31は、疑似クエリ特徴生成部1から得られる疑似クエリ特徴集合と、登録特徴候補生成部2から得られる登録特徴候補集合と、の間でマッチングを行い、マッチング結果を類似度スコア計算部32へと出力する。類似度スコア計算部32は当該得られたマッチング結果に基づいて類似度スコアを算出して登録特徴生成部33へと出力する。登録特徴生成部33では当該得られた類似度スコアに基づいて、最終出力としての登録特徴集合の要素を１つずつ、合計でN個決定する。前述の通り特徴マッチング部31及び類似度スコア計算部32が第一の反復処理を行い、登録特徴生成部33が第二の反復処理を行う。
【００２５】
一実施形態では線L22に示すように、反復処理部3で得られた登録特徴集合をさらに登録特徴候補生成部2へと出力してもよい。この場合すなわち、特徴量登録装置10の全体で所定回数（A回とする）の繰り返し処理を行い、a回目（a=1,2, ..., A-1）に反復処理部3の登録特徴生成部33から出力された登録特徴集合をその次のa+1回目の登録特徴候補生成部2（及び特徴マッチング部31）への入力とすることで、最終的にA回目に登録特徴生成部33から得られる登録特徴を特徴量登録装置10の出力とする。従って図１において、当該繰り返しを行わない場合（A=1の場合）は線L22は省略される。
【００２６】
実施形態によっては反復処理部3ではまた、線L31で示されるように疑似クエリ特徴生成部1から得られるディストラクタ情報を、または、線L32で示されるように特徴量記憶部4から得られるディストラクタ情報を、用いることでディストラクタを考慮した登録特徴集合を生成するようにしてもよい。
【００２７】
特徴量記憶部4は、画像検索の際のいわゆる一般的なDBに相当するものであり、予めマニュアル作業等で得られたものとしての各物体が撮影された各画像の特徴量を記憶しておき、線L23で示すように一実施形態において登録特徴候補生成部2へと当該特徴量を参照に供する。特徴量記憶部4は当該記憶しておく各特徴量に関してさらに、同様に予めマニュアル作業等で得られたものとしてそのディストラクタ情報を記憶しておいてもよく、一実施形態において線L32に示すように当該ディストラクタ情報を反復処理部3の参照に供するようにしてもよい。
【００２８】
図２は一実施形態に係る特徴量登録装置10の動作のフローチャートである。以下、図２の各ステップを説明しながら、図１の各部の処理内容の詳細を説明する。
【００２９】
ステップS1では、疑似クエリ特徴生成部1が入力として得た画像より、M個の要素からなる疑似クエリ特徴集合Q={q1, q2, …, qM}を生成したうえで、ステップS2へと進む。
【００３０】
図３は疑似クエリ特徴生成部1の詳細を示す機能ブロック図であり、図示する通り疑似クエリ特徴生成部1は画像加工部11及び生成部12を備える。疑似クエリ特徴生成部1へ入力された画像P0（説明のため、画像P0とする）は生成部12及び画像加工部11へと入力される。画像加工部11では当該画像P0に所定種類b個の加工処理pr1,pr2, ..., prbをそれぞれ施したものとして加工画像P1,P2, ..., Pbを得て、生成部12へと出力する。
【００３１】
画像加工部11におけるb個の加工処理はそれぞれ、加工処理の種類及び当該種類の加工処理の強さ等のパラメータを与えることで所定のものを事前に定めておく。当該加工処理は、特徴量登録装置10が出力する登録特徴集合によってさらに画像検索などを実施する際に想定されるビュー変化を網羅するものとして、所定のものを事前に定めておけばよい。
【００３２】
例えば加工処理の種類としては、相似変換、アフィン変換、射影変換などの幾何的な変換を施すものが含まれていてよい。当該幾何変換処理においてはさらに、入力された画像P0に写る物体の3Dモデルを有している場合、当該モデルにテクスチャを張り付けた上でビューを変化させた画像を生成してもよい。すなわち、要素ポリゴンのそれぞれにおけるテクスチャ情報を含む物体の3Dモデルを所定データとして与えておき、既存技術であるCGモデルとして生成（レンダリングによる生成）してもよい。さらにビュー変化として、ノイズ、ブラー、オクルージョンなどが想定される場合には、例えばノイズ付与、平滑化、マスキングなどの任意の画像処理を加工処理として採用してよい。
【００３３】
また、加工処理のパラメータも、幾何変換であれば当該幾何変換を施すための変換行列として、ノイズ付与等であれば当該付与ノイズの強さ等として与えることができる。１つの加工画像を得る際に２つ以上の加工処理を組み合わせてもよい。
【００３４】
生成部12では、入力画像P0と、画像加工部11から得られるその一連の加工画像P1,P2, ..., Pbと、より特徴量を抽出して、当該抽出された特徴量のすべてを疑似クエリ特徴集合Q={q1, q2, …, qM}として出力する。当該抽出する特徴量としては、周知のSIFT特徴量やSURF特徴量といった所定種類の局所特徴量（特徴点（キーポイント）の局所近傍で算出される特徴量）を採用することができる。
【００３５】
なお、生成部12では、入力画像P0は用いずその加工画像P1,P2, ..., Pbのみから特徴量を抽出することで疑似クエリ特徴集合Q={q1, q2, …, qM}を出力してもよい。同様に、1枚の入力画像P0を入力として用いて画像加工部11で加工することに代えて、同一物体を様々なビュー条件下において実際に撮影して得られた複数の画像が生成部12へと入力されるようにしてもよい。
【００３６】
ステップS1において疑似クエリ特徴生成部1ではさらに、画像加工部11において幾何変換を含む加工を行った場合には、ディストラクタ情報（不正解情報）（又は幾何変換関係がある場合にこれと同等の情報として同一対象同一箇所情報）も出力することができる。本発明において、ディストラクタとは、１つのクエリ特徴（qi）にとって、正解DB特徴以外の全ての特徴を意味し、具体的には（１）クエリ画像（入力画像P0）とは無関係の画像（画像P0とは別の対象が撮影されている画像）から抽出される全特徴と、（２）クエリ画像と同一対象の撮影されている画像（すなわち加工画像P1,P2, ..., Pn）から抽出されたマッチング制約条件を満たさない全特徴と、の両方を合わせた集合D(qi)（各クエリ特徴qiについて定まる集合）として定義される。ここで、あるクエリ特徴にとって「正解」と言えるDB特徴は、同じ対象の同じ箇所を記述している局所特徴となるが、撮影条件（ビュー）の変化によって全く同一とはならない。そのため、十分に「似ている」特徴を正解とみなすが、当該「似ている」基準がマッチング制約条件である。マッチング制約条件の具体例については、特徴マッチング部31の説明において後述する。
【００３７】
上記の（１）及び（２）の両方として各クエリ特徴qiについて定義されるディストラクタに関して、（１）は明白であり、図４を参照してディストラクタのうちの（２）の模式例を示す。図４では左側に示すクエリ画像P0に対して右側に示すように画像P0を幾何変換等したものとしてn=100枚の加工画像P1〜P100が生成されDB特徴（登録特徴候補）として利用される例が示されている。〇印で示すクエリ画像P0の位置p0（対象例として「家屋」の屋根の最先端の位置）から抽出された特徴qi0について、マッチング制約条件を満たすものは画像P1〜P100に関して同じく〇印で示す、画像P1における対応位置p1から抽出された特徴yj1と、画像P2における対応位置p2から抽出された特徴yj2と、画像P3における対応位置p3から抽出された特徴yj3と、…画像P100における対応位置p100から抽出された特徴yj100と、の100個である。従って、図４において△印で示される、加工画像P1〜P10から抽出される特徴のうちこれらマッチング制約条件を満たす100個の特徴以外の全ての特徴（例えば画像P1における位置p1eの特徴yj1eなど。なお、図４では△印として一部のディストラクタのみを例示し、符号もその一部のみに付している。）が、クエリ画像P0の特徴qi0のディストラクタとなる。
【００３８】
なお、図４の例のように、画像加工部11で入力画像P0に対して幾何変換Hkにより加工画像Pk(k=1,2,...)を生成する場合は、画像P0の位置p0の特徴qi0と画像Pkの位置pkの特徴yk1とが対応箇所のものであるか否かの判定は、「||pk-Hk*p0||<TH」（ここで|| ||はユークリッド距離（絶対値）、THは閾値）を満たす場合に対応箇所であるもの（同一対象同一箇所の対応があるもの）と判定することができる。すなわち、画像P0の位置p0をホモグラフィ行列等で表現される幾何変換Hkで写像した位置Hk*p0が位置pkに十分に近いと判定される場合に、対応箇所と判定することができる。逆に当該十分に近い位置以外の任意箇所で抽出された特徴量は、画像P0の位置p0の特徴qi0に対するディストラクタとなる。従って、画像加工部11で幾何変換を含む変換を行って加工画像を得た場合はこのようにして、同一対象同一箇所の対応がないものを特定することでディストラクタ情報を出力することができる。
【００３９】
ステップS2では、登録特徴候補生成部2がK個の要素からなる登録特徴候補集合Y={y1, y2, …, yK}を生成してから、ステップS3へと進む。なお、登録特徴候補集合Yとは、この中からN個の要素を選択することによってN個の登録特徴集合X={x1, x2, …, xN}を得るようにするものであるので、要素数Kに関してK>Nとなるように生成する。
【００４０】
ステップS2において当該生成する手法としては以下のような各実施形態が可能である。
【００４１】
一実施形態では、図１に線L21として示されるように、ステップS1で生成されている疑似クエリ特徴集合Qをそのまま、登録特徴候補集合Yとして採用する、すなわち、Y=Qとして生成する。
【００４２】
一実施形態では、図１に線L22として示されるように、登録特徴生成部33が生成した登録特徴集合を、登録特徴候補集合Yとして採用する。当該実施形態は、図２のフローチャートの全体を所定回数繰り返して、ステップS10で得られる登録特徴集合を所定回数だけ更新したものを最終的な出力としての登録特徴集合として採用することに相当する。
【００４３】
一実施形態では、図１に線L23として示されるように、特徴量記憶部4から所定数K個の特徴量を抽出したものを、登録特徴候補集合Yとして採用する。当該抽出はランダムに行えばよいが、特徴量が特徴空間において偏らないように抽出することが好ましい。
【００４４】
なお、特徴量記憶部4はいわゆる一般のDBであるため、疑似クエリ特徴生成部1に入力される任意の画像（未知画像）の特徴量に対して、事前知識なしでディストラクタ情報を特徴量記憶部4の特徴量に定義することはできない。なお、図４を参照して前述の通り、幾何変換の関係がある場合は同一対象同一箇所の対応がないものとしてディストラクタ情報が定義される。（以下同様）ただし、当該事前知識がある場合は、特徴量記憶部4に記憶されている特徴量の少なくとも一部にディストラクタ情報を定義しておいてもよい。当該ディストラクタ情報は図１に線L32で示すように反復処理部3へと参照に供することができる。
【００４５】
ステップS3では、以下の2重ループ処理S4〜S9によって類似度スコア計算部32が各登録特徴候補yjについて計算するその類似度スコア和score(yj)の初期値としてゼロを設定してから、ステップS4へ進む。（当該類似度スコア和score(yj)の値は、当該2重ループ処理においてステップS6でマッチング判定された場合に該当yjに関しての値が加算更新されることにより、当該2重ループ処理を抜けた時点（ステップS10に到達した時点）でその値が求まっている状態となる。）
【００４６】
ステップS4は、以下のステップS5〜S9をステップS1で生成した各疑似クエリ特徴qiについて繰り返し実施する旨を表すダミーステップであり、今回の処理対象のqiを設定したうえでステップS5へと進む。ステップS5は、以下のステップS6〜S8をステップS2で生成した登録特徴候補yjについて繰り返し実施する旨を表すダミーステップであり、今回の処理対象のyjを設定したうえでステップS6へと進む。
【００４７】
ステップS6は、当該処理対象に設定されている疑似クエリ特徴qiと登録特徴候補yjとがマッチングするか否かの判定を特徴マッチング部31が行ったうえで、ステップS7へと進む。ステップS7では、直近のステップS6でマッチング判定が得られた場合に、類似度スコア計算部32が当該処理対象に設定されている登録特徴候補yiに関しての現状の類似度スコア和score(yi)の値を加算更新してから、ステップS8へと進む。（直近のステップS6でマッチング判定が得られなかった場合、ステップS7では加算更新は行わず、そのままステップS8へと進む。）
【００４８】
なお、当該2重ループ内の上記ステップS6,S7の各処理の詳細は当該2重ループ処理の説明後に行う。
【００４９】
ステップS8では、全ての登録特徴候補yjについて以上のステップS5〜S7の処理が完了したか否かを判定し、完了していればステップS9へと進み、未完了であればステップS5に戻り、未処理の登録特徴候補yjを処理対象に設定して上記を繰り返す。ステップS9では、全ての疑似クエリ特徴qiについて以上のステップS4〜S8の処理が完了したか否かを判定し、完了していればステップS10へと進み、未完了であればステップS4に戻り、未処理の疑似クエリ特徴qiを処理対象に設定して上記を繰り返す。
【００５０】
以上、ステップS4〜S9における各qi及び各yjに関する2重ループ処理を終えてステップS10に至った時点で、特徴マッチング部32による一連のマッチング結果と、類似度スコア計算部32による各yjに関しての最終的な類似度スコア和score(yj)と、が求まっている状態となっている。以下、当該マッチング処理及び類似度スコア計算の詳細を順に説明する。
【００５１】
まず、ステップS6のマッチング処理に関して、特徴マッチング部31が、予め指定された制約条件（マッチング判定条件）に基づき、疑似クエリ特徴集合Qの各要素qiにつき、登録特徴候補集合Yの各要素yjの中からマッチングするものmatch(qi)を求める。すなわち、「{}」の記号で集合要素を列挙することで形式的に記載すれば、2重ループ処理を終えた時点で以下のようなマッチング結果が得られることとなる。これを結果リスト１と呼ぶ。
match(q1)={y11, y12, ...}, match(q2)={y21, y22, ...}, ...
match(qi)={yi1, yi2, ...}, ...., match(qN)={yN1, yN2, ... }      …（結果リスト１）
【００５２】
ステップS6において当該マッチング判定するための制約条件は様々なものが可能であり、例えば以下のようなものが挙げられる。当該各手法のいずれか又は任意の組み合わせを制約条件としてよい。
（手法１）クエリ側の特徴（qi）とDB側の特徴（yj）が同一のVWに量子化される。
（手法２）ディストラクタが存在する特徴ベクトル空間において、クエリ側の特徴ベクトル（qi）にとってDB側の特徴ベクトル（yj）がk近傍に位置する。
（手法３）クエリ側の特徴ベクトル（qi）とDB側の特徴ベクトル間（yj）の距離が閾値以内である。
（手法４）クエリ側の特徴とDB側の特徴の持つオリンテーションの差分が閾値以内である。
（手法５）クエリ側の特徴とDB側の特徴の持つスケールの比が閾値以内である。
【００５３】
なお、手法２においてk近傍とは、qiと、qiにとって類似度が上位のk位に含まれるyjとをマッチングする手法を意味する。すなわち、手法２ではクエリ側の特徴ベクトル（qi）との類似度が上位の側のk個がマッチング結果match(qi)として得られる。
【００５４】
なお、登録特徴候補集合Yの中には、現在注目しているDB側の特徴(yj)と同じ位置から抽出された特徴yが複数含まれている可能性があるが、それらはk近傍探索時のランキングから除外するようにしてよい。具体的には以下の[1]〜[3]のようにすればよい。
【００５５】
[1]予め，yjと座標が一致する他のy（同一対象同一箇所の関係にあるもの）をリスト化しておく。例えば、図４の例において（画像P0を除く）画像P1〜P100から疑似クエリ特徴集合が抽出されている場合であれば、list(yj1)={yj2, yj3, ..., yj100}である。同様にlist(yj2)={yj1,yj3,yj4, ..., yj100}となる。list(yj3)等も同様に定義しておくことができる。
[2] qiと各yの特徴ベクトル間距離を測定し、小さい順にソートしたランキングを作成する。このとき、list(yj)の要素は，ランキングに含めない。（yj自身は含める。）すなわち、現在注目しているyjと互いに同一対象同一箇所の関係にある一連のy∈list(yj)は、ランキングから除外する。（換言すれば、現在注目しているyjと、list(yj)に属さないその他のyと、のみがqiとの間の類似度ランキング作成対象となる。）
[3] 上記のように求めたランキングの上位k件以内にyjが含まれていれば、制約条件を満たしたとみなし、qiとyjとをマッチングする。
【００５６】
以上の[1]〜[3]の手順により、上位k件の中に真の正解が最大1つしか含まれない状況を再現することができる。これは、本発明において同じ画像を変換した大量の画像をマッチングの対象に含めることに起因した、例外的な処理に相当する。
【００５７】
なお、上記及び手法４，５において述べている「特徴のオリエンテーション差および/またはスケール比」とは、SIFT特徴量等として特徴ベクトルを求める際に求まるオリエンテーション及びスケールに関しての差及び比を意味する。
【００５８】
また、ステップS7にて類似度スコア計算部32は、直近のステップS6でマッチング判定が得られた場合に当該登録特徴候補yjに関する類似度スコア和score(yj)を当該qiの寄与として加算更新することで、2重ループ処理を終えた時点で最終的な類似度スコア和score(yj)を得た状態となる。
【００５９】
まず、当該求まる類似度スコア和score(yj)は、前述の各疑似クエリ特徴qiに関して求まっている結果リスト１を、各登録特徴候補yjから見たマッチング結果match(yj)として、以下のような結果リスト２に書き換えたうえで、当該結果リスト２に属するqiの類似度スコア和として求まることとなる。なお、結果リスト１と結果リスト２とは、内容としては等価である。
match(y1)={q11, q12, ...}, match(y2)={q21, q22, ...}, ...
match(yj)={qj1, qj2, ...}, ...., match(yK)={qK1, qK2, ... }      …（結果リスト２）
【００６０】
ループ処理内においては具体的に、類似度スコア和を求める処理では、予め指定された計算法に基づき、上記得られることとなる結果リスト２に属する要素qi（ステップS6でマッチング判定された要素qi）に関して加算することで、各登録特徴候補yjの類似度スコア和score(yj)（リストmatch(yj)内の各要素qと当該登録特徴候補yjとの類似度のスコア和）を計算することとなる。当該加算のための重みづけは様々なものが可能であり、例えば以下のようなものが挙げられる。
【００６１】
（計算法１）重み付けの値として「1」（固定値）を用いる。すなわち、ステップS6にてyjとqiとがマッチング判定されるごとにスコア和score(yi)に「１」を加算することによって、ループ処理を終えた時点で以下のようなスコア和score(yj)が求まることとなる。すなわち、結果リスト２におけるmatch(yj)の要素数が大きいほど類似度スコア和score(yj)が大きいものとして得られる。
score(yj)=リストmatch(yj)に属する要素の個数。
【００６２】
（計算法２）重み付けの値として、既存手法であるtf-idf（Term Frequency - Inverse Document Frequency）を用いる。すなわち、リストmatch(yj)に属する特徴ベクトルqのtf-idf値をtfidf(q)と表記すると、以下の式で当該リスト内のtf-idf値の総和として類似度スコア和score(yj)が求まる。なお、値tf-idf(q)は特徴ベクトルqをVWに量子化したうえで、既存手法に従って求めることができる。
【００６３】
【数１】
2018120395.tif 000003
【００６４】
（計算法３）重み付けの値として式「kthd2-d2」を用いる。ここでdはクエリ側とリファレンス側の特徴ベクトル間の距離，kthdはクエリ側の特徴にとってk番目に近い特徴との特徴ベクトル間の距離である。すなわち、リストmatch(yj)に属する特徴ベクトルqに関して求まる「kthd2-d2」の値をf(q)と書くと、上記tf-idfの場合と同様に以下の式でリスト内総和として求まることとなる。
【００６５】
【数２】
2018120395.tif 000004
【００６６】
ここで、「kthd2-d2」は、以下に掲げる非特許文献３に開示のLocal Naive-Bayes Nearest-Neighborと呼ばれる画像のクラス分類手法を画像検索に適用した際のスコア関数である。kthd2-d2はVWに量子化した後でも特徴ベクトルを用いて計算してもよいし，非特許文献1のように、特徴ベクトルをコンパクトに変換したHamming embeddingと呼ばれるベクトル間の距離を用いてもよい。
[非特許文献３] McCann and D. G. Lowe, "Local naive bayes nearest neighbor for image classification," in Proc. of CVPR, 2012.
【００６７】
なお、計算法３においては特徴マッチング部31の（手法２）で説明したのと同様に、手順[1]〜[3]によってランキングを作成したうえで、当該ランキングにおけるk番目に近い特徴ベクトルを求めるようにしてもよい。
【００６８】
以上、計算法１〜３に限らず、その他の任意の既存の画像検索のためのスコア関数（重み付け関数）を用いて類似度スコア和score(yj)を計算することができる。
【００６９】
ステップS10では、登録特徴生成部33が、以下のN回の繰り返しステップS11〜S14で最終結果（当該最終結果はステップS15で出力される）を得るための登録特徴集合の初期値として空集合（φ）を設定してから、ステップS11へと進む。ステップS11は、以下のステップS12〜S14をN回繰り返すことを表すためのダミーステップであり、そのままステップS12へと進む。
【００７０】
ステップS12では、登録特徴生成部33が以下の（手順１）、（手順２）により登録特徴集に新たな要素xn（n=1,2, ,,,, Nであり、nは当該繰り返しステップS12〜S14の現時点での繰り返し回数を表すものとする。）を追加してから、ステップS13へと進む。
【００７１】
（手順１）各登録特徴候補yjの中から、最大の類似度スコアscore(yj)を持つ登録特徴候補ymaxを選択する。すなわち、式表記すればインデクスmaxは以下のように定まる。
max=argmax(score(yj))
（手順２）この登録特徴候補ymaxに紐づく疑似クエリ特徴集合match(ymax)の特徴ベクトルを平均化したものを追加する特徴ベクトルxnとする。
【００７２】
上記の手順２ではさらに同様にして、特徴ベクトルxnのみならず、オリエンテーションo、スケールs、および座標uの少なくとも１つをそれぞれ平均化した特徴を、登録特徴fnとしてもよい。例えばこれら全てを登録特徴とする場合はfn=(xn, on, sn, un)のように各量を列挙したものとして登録特徴が得られる。
【００７３】
上記の手順２では次のような追加実施形態も可能である。すなわち、手順２における特徴の平均化によって、結果的に疑似クエリ特徴集合から得られる類似度スコアの和が小さくなる可能性がある。そのため、手順2において平均化された特徴を用いて特徴マッチング部31および類似度スコア計算部32の処理を再度行い、結果的に類似度スコアの和が小さくなっていた場合、平均化を行わないという判断を行ってもよい。
【００７４】
すなわち、当初の（手順１）において選択されたscore(ymax)と、（手順２）で平均化して求めたxnによるscore(xn)と、を比較して、「score(ymax)＞score(xn)」となっている場合、平均化したxnを登録対象として採用しないようにしてよい。逆に類似度スコア和が大きくなる場合、以上の通り平均化を行ったxnを登録特徴集合の要素として採用すればよい。当該平均化された特徴を用いてscore(xn)を計算する際は、登録特徴候補集合Yにおいて、平均化される対象となった複数の特徴を平均化された１つの特徴に置き換えた暫定集合Y'を対象として、（すなわち、集合Yの代わりに暫定集合Y'を入力として用いて、）特徴マッチング部31及び類似度スコア計算部32の処理を行うようにすればよい。例えばxn=(y1+y2+y3)/3と3個の平均で登録特徴を得た場合、3個あったy1,y2,y3を1個のxnに置き換えるようにすればよい。なお、平均化を行わない判断を下した場合は、平均化せずにymaxをそのままxnとして登録すればよい。
【００７５】
ステップS13では、登録特徴生成部33が直近のステップS12の（手順１）で決定されたymaxに紐づく疑似クエリ特徴集合match(ymax)（ymaxに対する疑似クエリ特徴のマッチング結果リスト）の各要素を、全てのその他のyj（ymax自身も含む）に紐づく疑似クエリ特徴集合match(yj)={qj1, qj2, ...}から除外する更新を行うと共に、match(ymax)の各要素から与えられたスコア和への寄与分をその他の類似度スコア和score(yj)から減算する更新を行ったうえで、ステップS14へと進む。当該減算する更新とはすなわち、スコア和score(yi)を計算するためのmatch(yi)からmatch(ymax)に属する要素を除外した「match(yi) ＼match(ymax)」を用いて、スコア和score(yi)を計算しなおすことに相当する。「＼」は差集合演算であり、以下でも同様である。
【００７６】
ステップS13による当該更新により、登録特徴候補集合Yを以下のように更新してステップS4〜S9の2重ループ処理を再度実施した場合に得られるマッチング結果及び類似度スコア和とほぼ同様のものとして更新されたマッチング結果及び類似度スコア和を、2重ループ処理を再度行うことなく高速に得ることができる。
Y=Y＼match(ymax)
【００７７】
また、当該ステップS11〜S14の繰り返し回数がn回目であるとすると、n回目のステップS13で上記のように更新された疑似クエリ特徴集合match(yj)={qj1, qj2, ...}（すなわち更新された結果リスト２）及び更新された類似度スコア和score(yj)が、次のn+1回目のステップS12の判断で利用されることとなる。（なお、一度でもymaxとして選択されたもの（y[選択済]とする）は、そのスコア値score(y[選択済])が以降の繰り返し処理ではその値が更新されてゼロとなるため、また、そのマッチング結果としてのリストmatch(y[選択済])も空集合となるため、（手順1）の選択から除外されることとなる。）
【００７８】
ステップS14では登録特徴生成部33が当該時点においてN個の要素からなる登録特徴集合が得られているか否かを判定し、得られていなければ新たな要素を追加すべくステップS11へと戻って上記を繰り返し、得られていればステップS15へと進む。ステップS15では登録特徴生成部33が以上の繰り返しステップS11〜S14で得られたN個の要素からなる登録特徴集合を最終結果として出力して、当該図２のフローは終了する。
【００７９】
以上、本発明によれば、ビュー変化がある場合でもロバストな特徴量を得ることができる。また、ディストラクタが存在する特徴ベクトル空間において、多様なビューにおけるクエリ特徴とマッチする可能性の高い登録特徴集合を生成することができる。さらに、より高い類似度スコアを与える登録特徴を優先的に選択することにより、大規模なデータベースに対する画像検索の精度を改善することができる。以下、補足事項を述べる。
【００８０】
（１）図２のフロー全体を繰り返す実施形態（繰り返しの2回目以降では図１の線L22の入力が行われる実施形態）、すなわち、一度の処理で得られた登録特徴集合を、新たな登録特徴候補とみなして、終了条件を満たすまで処理を反復する実施形態は例えば次のようにすることができる。
【００８１】
例えば、1回目の登録特徴候補を疑似クエリ特徴集合（M>N）に設定し、M'個（M>M'>N）の登録特徴集合を得る。それを新たな登録特徴候補とみなしてM''個（M'>M''>N）の登録特徴集合を得る、という処理を、N個の登録特徴を得るまで繰り返してもよい。あるいは、1回目の処理で得られたN個の登録特徴を新たな登録特徴候補とみなして処理を行い、結果的に得られる類似度スコアの和に変化が無くなるまで処理を繰り返してもよい。
【００８２】
（２）本発明におけるマッチングの制約条件、類似度スコア計算方法、疑似クエリ特徴集合、ディストラクタは、実行時の検索処理に則しているほど本発明の効果が期待される。すなわち、マッチングの制約条件および類似度スコア計算方法は実行時に利用するマッチング方法および類似度スコア計算方法と内容的に一致し、疑似クエリ特徴集合はユーザが実際に撮影した画像から得られるものに類似し、ディストラクタ関係が与えられる要素集合の内容およびその要素数は、実際の検索データベースに類似していることが望ましい。
【００８３】
（３）本発明は、コンピュータを特徴量登録装置10として機能させるプログラムとしても提供可能である。当該コンピュータには、CPU(中央演算装置)、メモリ及び各種I/Fといった周知のハードウェア構成のものを採用することができ、CPUが特徴量登録装置10の各部の機能に対応する命令を実行することとなる。
【符号の説明】
【００８４】
10…特徴量登録装置、1…疑似クエリ特徴生成部、2…登録特徴候補生成部、31…特徴マッチング部、32…類似度スコア計算部、33…登録特徴生成部、4…特徴量記憶部
【図１】
2018120395.tif 000005
【図２】
2018120395.tif 000006
【図３】
2018120395.tif 000007
【図４】
2018120395.tif 000008