画像検索システム
【課題】精度の高い十分な個数の対応点ペアに基づいて、画像検索を高精度で行える画像検索システムを提供する
【解決手段】クエリ画像および各検索対象画像の各特徴点から局所特徴量を抽出する局所特徴量抽出部１と、クエリ画像および各検索対象画像の局所特徴量同士を比較し、類似度が所定の第１条件を満足する特徴点のペアを第１対応点ペアとして抽出する第１対応点ペア抽出部２と、クエリ画像および検索対象画像のペアごとに、対応点ペアに基づいて比較領域を限定する比較領域限定部３と、クエリ画像および検索対象画像のペアごとに、各比較領域の局所特徴量同士を比較し、類似度が所定の第２条件を満足する特徴点のペアを第２対応点ペアとして抽出する第２対応点ペア抽出部４と、第２対応点ペアの個数に基づいて検索結果を出力する検索結果出力部５とを具備した。
【解決手段】クエリ画像および各検索対象画像の各特徴点から局所特徴量を抽出する局所特徴量抽出部１と、クエリ画像および各検索対象画像の局所特徴量同士を比較し、類似度が所定の第１条件を満足する特徴点のペアを第１対応点ペアとして抽出する第１対応点ペア抽出部２と、クエリ画像および検索対象画像のペアごとに、対応点ペアに基づいて比較領域を限定する比較領域限定部３と、クエリ画像および検索対象画像のペアごとに、各比較領域の局所特徴量同士を比較し、類似度が所定の第２条件を満足する特徴点のペアを第２対応点ペアとして抽出する第２対応点ペア抽出部４と、第２対応点ペアの個数に基づいて検索結果を出力する検索結果出力部５とを具備した。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像検索システムに係り、特に、クエリ画像に類似した画像を多数の検索対象画像の中から検索する際に、類似の比較が容易な領域を予め抽出し、当該領域を対象に検索を行う画像検索システムに関する。
【背景技術】
【０００２】
建物など剛体の画像をロバストに検出する手法の一つとして、非特許文献１にSIFT(Scale Invariant Feature Transform)が開示されている。このSIFTでは、クエリ画像および検索対象画像の双方から予め局所特徴量が抽出され、各画像の局所特徴量間のユークリッド距離Lに基づいて最近傍探索が実行される。そして、距離の近い局所特徴量同士が対応点ペアとされ、最終的に対応点ペアの多い検索対象画像が検索結果とされる。このとき、最近傍の特徴点の対応点マッチング精度を高めるために、最も近い距離L1のみならず２番目に近い距離L2も求められ、両者の比(L1/L2：ratio of distances)が所定の閾値t以下であれば対応点とされるが、閾値tよりも大きければ対応点とされない。
【０００３】
非特許文献１では、予備実験においてt=0.85で急激な誤対応点増加が確認されたことからt=0.8としている。しかしながら、閾値tを小さな値に設定すれば、対応点の精度は高くなる傾向を示すものの、対応点ペアが少なくなるので検索精度を高くできるとは限らない。すなわち、非特許文献１では閾値tを適正値に設定することが難しかった。
【０００４】
このような技術課題に対して、特許文献１には、所定数の対応点ペアが得られるように、対応点ペアが少なければ閾値tを段階的に上げ、多ければ閾値tを段階的に下げるといったように、抽出される対応点ペアの個数に応じて閾値tを適応的に変更する技術が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−１４０６１３号公報
【非特許文献】
【０００６】
【非特許文献１】David G. Lowe，"Distinctive image features from scale-invariant keypoints" International Journal of Computer Vision, 60, 2 (2004), pp.91-110.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記の特許文献１では、所定の閾値tで得られる対応点ペアが少ないと、閾値tが適応的に上昇するので対応点ペアが増える。しかしながら、もともと同一物体が画像内に含まれていないために対応点ペアが少ないクエリ画像および検索対象画像のペアについても閾値tが上げられてしまうので、本来であれば対応点ペアとされない特徴点同士までもが対応点ペアとされてしまうという問題があった。
【０００８】
本発明の目的は、上記した従来技術の課題を解決し、精度の高い十分な個数の対応点ペアに基づいて、画像検索を高精度で行える画像検索システムを提供することにある。
【課題を解決するための手段】
【０００９】
上記の目的を達成するために、本発明は、クエリ画像に類似した画像を検索対象画像の集合から検索する画像検索システムにおいて、以下のような手段を講じた点に特徴がある。
【００１０】
(1)クエリ画像および各検索対象画像の各特徴点から局所特徴量を抽出する局所特徴量抽出手段と、クエリ画像および各検索対象画像の局所特徴量同士を比較し、類似度が所定の第１条件を満足する特徴点のペアを第１対応点ペアとして抽出する第１対応点ペア抽出手段と、クエリ画像および検索対象画像のペアごとに、前記対応点ペアに基づいて比較領域を限定する比較領域限定手段とを具備し、クエリ画像および検索対象画像のペアごとに、比較領域同士を比較することを特徴とする。
【００１１】
(2)クエリ画像および検索対象画像のペアごとに、各比較領域の局所特徴量同士を比較し、類似度が所定の第２条件を満足する特徴点のペアを第２対応点ペアとして抽出する第２対応点ペア抽出手段と、第２対応点ペアの個数に基づいて検索結果を出力する検索結果出力手段とを具備し、第２条件が第１条件よりも緩いことを特徴とする。
【発明の効果】
【００１２】
本発明によれば、以下のような効果が達成される。
(1)クエリ画像および各検索対象画像内に、比較的厳しい条件を満足する対応点ペアに基づいて比較領域を設定すると共に、対応点ペアが得られない非類似の検索対象画像を予め排除したので、クエリ画像および各検索対象画像の類似度を、各比較領域内に比較的緩やかな条件で設定した対応点ペアの個数に基づいて判別すれば、精度の高い十分な個数の対応点ペアに基づいて画像検索を行えるようになる。
(2)クエリ画像および各検索対象画像内に、比較的厳しい条件を満足する対応点ペアに基づいて比較領域を設定すると共に、対応点ペアが得られない非類似の検索対象画像を予め排除し、クエリ画像および各検索対象画像の類似度を、各比較領域内に比較的緩やかな条件で設定した対応点ペアの個数に基づいて判別するので、精度の高い十分な個数の対応点ペアに基づいて画像検索を行えるようになる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態に係る画像検索システムのブロック図である。
【図２】対応点の仮登録方法を模式的に示した図である。
【図３】対応点の本登録方法を模式的に示した図である。
【図４】比較領域の限定方法（その１）を模式的に示した図である。
【図５】比較領域の限定方法（その２）を模式的に示した図である。
【図６】本発明の一実施形態の動作を示したフローチャートである。
【図７】対応点ペアの仮登録手順を示したフローチャートである。
【図８】対応点ペアの本登録手順を示したフローチャートである。
【図９】クエリ画像および一の検索対象画像の一例を示した図である。
【図１０】仮登録された対応点ペアの一例を示した図である。
【図１１】仮登録された対応点ペアの一部のみが本登録される例を示した図である。
【図１２】本登録された対応点ペアの一例を示した図である。
【図１３】比較領域の限定方法を示した図である。
【図１４】比較領域の一例を示した図である。
【図１５】比較領域における対応点ペアの仮登録手順を示したフローチャートである。
【図１６】比較領域における対応点ペアの本登録手順を示したフローチャートである。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の最良の実施形態について詳細に説明する。図１は、本発明の一実施形態に係る画像検索システムの主要部の構成を示したブロック図であり、ここでは、本発明の説明に不要な構成は図示が省略されている。
【００１５】
局所特徴量抽出部１は、クエリ画像Iqおよび多数の検索対象画像Iw(k)の各特徴点を基準にして局所特徴量fq(i)，fw(k,j)を抽出する。符号kは検索対象画像の識別子である。局所領域の特定には、非特許文献１に開示されているDifference of Gaussian (DoG)によるスケールスペース内の極値に基づく特徴点抽出が用いられる。この特徴点抽出の結果、特徴点の位置およびその領域範囲(スケール)が算出される。特徴領域内の特徴記述子としては、輝度勾配の方向ヒストグラムが用いられる。
【００１６】
このような方向ヒストグラムは、特徴領域の各ピクセルの輝度勾配を算出し、それに重みを付けてヒストグラムを生成し、最も多いbin領域の方向を基準にして、その方向に特徴領域の回転を行い、再度輝度方向の方向ヒストグラムを作成し、さらに前記ヒストグラムをブロックに分割し、各ブロック内で方向ヒストグラムを算出し、これを正規化してベクトル化することにより得られる。本実施形態では、ブロック内の輝度方向を８方向、対象領域内を１６分割しているため、一つの特徴記述子は８＊１６＝１２８次元となる。
【００１７】
これら特徴記述子の特徴として、局所領域の特徴を生成するのでオクルージョンに耐性があり、特徴点に対してスケールを決定するので画像サイズに不変であり、また輝度勾配に基づき画像平面内で回転を行うので画像平面に対する回転に不変であることなどが挙げられる。さらに、エッジ成分を利用しているので輝度変化に耐性がある。このような特徴点検出が画像の全てのピクセルに対して行われるが、ある特徴点が極値を取った場合でも特徴点として不適な場合は特徴領域から除外される。
【００１８】
本実施形態では、クエリ画像Iqの各局所特徴量fq(i)が次式(1)で表される。pq(i)は同次座標で表した特徴点の位置、σq(i)は特徴点が発見されたスケール、dq(i)は特徴記述子であり、符号iはクエリ画像Iqの特徴点識別子である。
【００１９】
fq(i)＝｛pq(i)，σq(i)，dq(i)｝ ・・・(1)
【００２０】
同様に、各検索対象画像Iw(k)の局所特徴量fw(k,j)は次式(2)で表される。pw(k,j)は同次座標で表した特徴点の位置、σw(k,j)は特徴点が発見されたスケール、dw(k,j)は特徴記述子であり、符号jは検索対象画像Iw(k)の特徴点識別子である。
【００２１】
fw(k,j)＝｛pw(k,j)，σw(k,j)，dw(k,j)｝ ・・・(2)
【００２２】
第１対応点ペア抽出部２は、仮登録部２１および本登録部２２を含み、クエリ画像Iqの各特徴点の局所特徴量と全ての検索対象画像Iw(k)の各特徴点の局所特徴量とを比較し、局所特徴量の類似度が高い特徴点のペアを対応点ペアとして登録する。
【００２３】
前記仮登録部２１は、クエリ画像Iqの各特徴点について、全ての検索対象画像Iw(k)の各特徴点を対象に局所特徴量の最近傍探索を行い、検索対象画像ごとに、局所特徴量間の距離に基づいて類似度を算出する。
【００２４】
本実施形態では、各特徴点の局所特徴量fq(i)，fw(k,j)間の類似度が、次式(3)で与えられる各特徴記述子dq(i)，dw(k,j)間のユークリッド距離Lで代表される。
【００２５】
L＝|dq(i)−dw(k,j)| ・・・(3)
【００２６】
そして、前記ユークリッド距離Lが最も近い距離L1となる特徴点および２番目に近い距離L2となる特徴点を各検索対象画像Iw(k)から探索し、更に各距離L1，L2が所定の第１条件を満足する場合のみ、前記距離L1を与える特徴点のペアを対応点ペアとして仮登録する。
【００２７】
図２は、対応点ペアの仮登録方法を示した図である。図示した例では、クエリ画像Iqと一の検索対象画像Iw(k)とのペアに着目しており、クエリ画像Iqの局所特徴量fq(1)と検索対象画像Iw(k)の局所特徴量fw(k,1)との距離がL1、局所特徴量fw(k,2)との距離がL2である。そして、距離L1が所定の基準距離Lref1以下であり、かつ距離比L1/L2が所定の基準比Rref1（例えば、０．８）以下なので、距離L1を与える特徴点のペアが対応点ペアとして仮登録されている。
【００２８】
これに対して、クエリ画像Iqの局所特徴量fq(2)と局所特徴量fw(k,3)との距離がL1、局所特徴量fw(k,4)との距離がL2であるが、距離L1が所定の基準距離Lref1よりも大きいか、あるいは距離比L1/L2が基準比Rref1（例えば、０．８）よりも大きいので、距離L1を与える特徴点のペアであっても対応点ペアとして仮登録されていない。
【００２９】
図１へ戻り、前記本登録部２２は、仮登録された全ての対応点ペアの検索対象画像Iw(k)側の対応点について、クエリ画像Iqの各特徴点を対象に局所特徴量の最近傍探索を同様に行い、距離L1，L2が前記仮登録条件と同等の本登録条件を満足するクエリ画像Iqの特徴点が前記対応点ペアのクエリ画像Iq側の対応点と一致していれば、当該対応点ペアを本登録する。
【００３０】
図３は、対応点ペアの本登録方法を示した図である。図示した例では、クエリ画像Iqの局所特徴量fq(1)と検索対象画像Iw(k)の局所特徴量fw(k,1)、およびクエリ画像Iqの局所特徴量fq(2)と検索対象画像Iw(k)の局所特徴量fw(k,2)とが共に対応点ペアとして仮登録されている。そして、各対応点ペアの検索対象画像Iw(k)側の対応点の局所特徴量fw(k,1)，fw(k,2)とクエリ画像Iqの全ての特徴点の局所特徴量fq(i)との最近傍探索が行われた結果、局所特徴量fw(k,1)と対応点ペアの条件を満足するクエリ画像Iqの特徴点が当該対応点ペアのクエリ画像Iq側の対応点と一致しているので、当該対応点のペアは本登録されている。
【００３１】
これに対して、局所特徴量fw(k,2)と対応点ペアの条件を満足するクエリ画像Iqの特徴点は当該対応点ペアのクエリ画像Iq側の対応点と一致していないので、当該対応点のペアは本登録されていない。
【００３２】
図１へ戻り、比較領域限定部３は、クエリ画像Iqと検索対象画像Iw(k)との組合せごとに、本登録された対応点ペアの対応点およびその局所特徴量に基づいて、画像の類似度を算出する際に比較対象となる領域を限定する。
【００３３】
図４、５は、クエリ画像Iqと一の検索対象画像Iw(k)との組合せについて、本登録された複数の対応点ペアに基づいて比較領域Aが限定される様子を模式的に示した図であり、図４に示したように、全ての対応点ペアの範囲を含む矩形あるいは楕円形の閉領域が、それぞれ比較領域Aq(k)，Aw(k)とされる。あるいは図５に示したように、対応点ペアの分布密度が高い矩形あるいは楕円形の閉領域が、それぞれ比較領域Aq(k)，Aw(k)とされても良い。なお、各検索対象画像Iw(k)において限定される比較領域Aw(k)は一つであるが、クエリ画像Iqでは検索対象画像Iw(k)ごとに比較領域Aq(k)が限定されることになる。
【００３４】
図１へ戻り、第２対応点ペア抽出部４は、仮登録部４１および本登録部４２を含み、比較領域Aが限定されたクエリ画像Iqおよび検索対象画像Iw(k)の組合せごとに、クエリ画像Iqの比較領域Aq内の各特徴点の局所領域と各検索対象画像Iw(k)の比較領域Aw(k)内の各特徴点の局所特徴量とを比較し、前記第１対応点ペア抽出部２と同様の手順で対応点ペアを抽出する。
【００３５】
前記仮登録部４１は、クエリ画像Iqの比較領域Aq(k)内の各特徴点について、各検索対象画像Iw(k)の比較領域Aw(k)内の各特徴点を対象に局所特徴量の最近傍探索を同様に行い、検索対象画像Iw(k)ごとに、前記距離L1，L2が仮登録条件を満足する最近傍の特徴点を探索し、前記距離L1を与える特徴点のペアを対応点ペアとして仮登録する。なお、当該仮登録部４１における仮登録条件は前記仮登録部２１における仮登録条件よりも緩和されている。
【００３６】
前記本登録部４２は、仮登録された全ての対応点ペアの検索対象画像Iw(k)側の対応点について、クエリ画像Iqの比較領域Aq(k)内の各対応点を対象に局所特徴量の最近傍探索を同様に行い、本登録条件を満足する最近傍の特徴点が前記対応点ペアのクエリ画像Iq側の対応点と一致していれば、当該対応点ペアを本登録する。なお、当該本登録部４２における本登録条件も前記本登録部２２における本登録条件より緩和されている。
【００３７】
検索結果出力部５は、前記クエリ画像Iqの比較領域Aq(k)および検索対象画像Iw(k)の比較領域Aw(k)を対象とする対応点ペアの探索結果を参照し、対応点ペアが最多である唯一の検索対象画像、あるいは上位Nベストの複数の検索対象画像を検索結果として出力する。
【００３８】
次いで、フローチャートを参照して本発明の一実施形態の動作を詳細に説明する。図６は、本発明の一実施形態の動作を示したメインフローである。
【００３９】
ステップＳ１では、局所特徴量抽出部１において、クエリ画像Iqから各特徴点を基準にした局所領域の特徴量fq(i)が抽出され、さらに全ての検索対象画像Iw(k)から各特徴点を基準にした局所領域の特徴量fw(k,j)が抽出される。ステップＳ２では、検索対象画像Iw(k)の一つが今回の注目画像として選択される。ステップＳ３では、前記第１対応点ペア抽出部２の仮登録部２１において、クエリ画像Iqの各特徴点と局所特徴量が一致または類似する検索対象画像Iw(k)の特徴点とを対応点ペアとして仮登録する仮登録処理が実行される。
【００４０】
図７は、前記仮登録処理の手順を示したフローチャートであり、ステップＳ１０１では、クエリ画像Iqから抽出された局所特徴量fq(i)の一つが選択される。ステップＳ１０２では、今回の検索対象画像Iw(k)の各局所特徴量fwt(j)とクエリ画像Iqの今回の注目特徴量fq(i)との類似度が、各特徴量間の距離（ユークリッド距離）Lとして算出される。ステップＳ１０３では、局所特徴量の距離Lが近い上位２つ（L1，L2）の特徴点ペアが抽出される。
【００４１】
ステップＳ１０４では、距離L1が基準距離Lef1以下であり、かつ距離比(L1/L2)が基準比tref1以下であるか否かが判定される。これらの仮登録条件がいずれも満足されれば、両者の類似度が高いと判定されるのでステップＳ１０５へ進み、距離L1を与える特徴点ペアが対応点ペアとして仮登録される。
【００４２】
ステップＳ１０６では、クエリ画像Iqの全ての局所特徴量fq(i)に関して上記の処理が完了したか否かが判定される。完了していなければステップ１０１へ戻り、クエリ画像Iqの局所特徴量fq(i)を切換ながら上記の各処理が繰り返される。これにより、今回注目した一の検索対象画像Iw(k)とクエリ画像Iqとの対応点ペアの仮登録が完了する。ここでは、図９に示したクエリ画像Iqおよび一の検索対象画像Iw(k)のペアについて、図１０に示したように、１１個の対応点ペアが仮登録されたものとして説明を続ける。
【００４３】
図６のメインフローへ戻り、ステップＳ４では、前記第１対応点ペア抽出部２の本登録部２２において、前記ステップＳ３とは逆の視線で、各対応点ペアの検索対象画像Iw(k)側の対応点とクエリ画像Iqの特徴点との間で最近傍探索が行われる。そして、最も類似度の高いクエリ画像Iqの特徴点が、前記対応点ペアのクエリ画像Ip側の対応点と一致すれば、当該対応点ペアが本登録される。
【００４４】
図８は、上記本登録処理の手順を示したフローチャートであり、ステップＳ２０１では、仮登録されている対応点ペアの一つが選択される。ステップＳ２０２では、対応点ペアの一方である検索対象画像Iw(k)側の対応点とクエリ画像Iqの各特徴点とを対象に局所特徴量間の距離Lが算出される。ステップＳ２０３では、距離Lが近い上位２つ（L1，L2）の特徴点ペアが抽出される。
【００４５】
ステップＳ２０４では、距離L1が基準距離Lef1以下であり、かつ距離比(L1/L2)が基準比tref1以下であるか否かが判定される。これらの本登録条件がいずれも満足されればステップＳ２０５へ進む。ステップＳ２０５では、前記距離L1を与えるクエリ画像Iqの特徴点が前記対応点ペアのクエリ画像Iq側の対応点と一致しているか否かが判定される。一致していればステップＳ２０６へ進み、前記仮登録されている今回の対応点ペアが本登録される。
【００４６】
ステップＳ２０７では、仮登録されている全ての対応点ペアに関して上記の処理が完了したか否かが判定される。完了していなければステップＳ２０１へ戻り、残りの対応点ペアに関して上記の各処理が繰り返される。これにより、今回注目した一の検索対象画像Iw(k)とクエリ画像Iqとの対応点ペアの本登録が完了する。
【００４７】
ここでは、図１１に示したように、クエリ画像Iqおよび一の検索対象画像Iw(k)のペアについて、前記仮登録された１１個の対応点ペアのうち、破線で示した４個の対応点は本登録されず、図１２に整理して示したように、７個の対応点ペアのみが本登録されたものとして説明を続ける。
【００４８】
図６のメインフローへ戻り、ステップＳ５では、今回注目した一の検索対象画像Iw(k)について、本登録された対応点ペアの有無が判定され、本登録された対応点ペアがあればステップＳ６へ進む。ステップＳ６では、クエリ画像Iqと今回注目の一の検索対象画像Iw(k)とのペアについて、本登録された対応点ペアに基づいて、両者の類似度を算出する際の比較対象となる領域を限定する「比較領域の限定処理」が、前記比較領域限定部３において実行され、クエリ画像Iqおよび検索対象画像Iw(k)のそれぞれに比較領域Aq(k)，Aw(k)が設定される。
【００４９】
図１３，１４は、前記比較領域の限定方法の一例を示した図であり、図１３に示したように７つの対応点ペアが本登録されていれば、図１４に示したように、これら７個の対応点ペアを包含する最小の矩形領域が比較領域Aq(k)，Aw(k)として設定される。
【００５０】
ステップＳ７では、全ての検索対象画像Iw(k)に関して上記の処理が完了したか否かが判定される。完了していなければステップＳ２へ戻り、注目する一の検索対象画像Iw(k)を切り換えながら上記の各処理が繰り返され、対応点ペアが本登録されているクエリ画像Iqおよび検索対象画像Iw(k)の全ペアについて比較領域Aq(k)，Aw(k)が設定される。
【００５１】
このようにして比較領域Aq(k)，Aw(k)の設定が完了するとステップＳ８以降へ進み、クエリ画像Iqと各検索対象画像Iw(k)とを前記比較領域Aq(k)，Aw(k)で比較して検索結果を得る検索手順が実行される。
【００５２】
ステップＳ８では、前記比較領域Aw(k)の設定された検索対象画像Iw(k)の一つが、今回の注目画像として選択される。ステップＳ９では、前記第２対応点ペア抽出部４の仮登録部４１において、クエリ画像Iqの比較領域Aq(k)内の各特徴点と局所特徴量が一致または類似する検索対象画像Iw(k)の比較領域Aw(k)内の特徴点とを対応点ペアとして仮登録する仮登録処理が実行される。
【００５３】
図１５は、前記仮登録処理の手順を示したフローチャートであり、ステップＳ３０１では、クエリ画像Iqの比較領域Aq(k)から局所特徴量fq(i)の一つが選択される。ステップＳ３０２では、今回の検索対象画像Iw(k)の比較領域Aw(k)内の各局所特徴量fwt(j)とクエリ画像Iqの今回の局所特徴量fq(i)との類似度が距離Lとして算出される。ステップＳ３０３では、距離Lが短い上位２つ（L1，L2）の特徴点ペアが抽出される。
【００５４】
ステップＳ３０４では、距離L1が基準距離Lef2以下であり、かつ距離比(L1/L2)が基準比tref2以下であるか否かが判定される。前記基準距離Lef2および基準比tref2は、前記第１対応点ペア抽出部２における基準距離Lef1および基準比tref2よりも緩和されている。すなわち、Lef1＜Lef2、tref1＜tref2である。これらの仮登録条件がいずれも満足されれば、両者の類似度が高いと判定されるのでステップＳ３０５へ進み、距離L1を与える特徴点のペアが対応点ペアとして仮登録される。
【００５５】
ステップＳ３０６では、クエリ画像Iqの比較領域Aq(k)内の各局所特徴量fq(i)に関して上記の処理が完了したか否かが判定される。完了していなければステップ３０１へ戻り、クエリ画像Iqの局所特徴量fq(i)を切換ながら上記の各処理が繰り返される。
【００５６】
図６のメインフローへ戻り、ステップＳ１０では、前記第２対応点ペア抽出部４の本登録部４２において、前記ステップＳ９とは逆の視線で、各対応点ペアの検索対象画像Iw(k)側の対応点とクエリ画像Iqの比較領域Aq(k)内の各特徴点との間で局所特徴量の類似度が算出される。そして、最も類似度の高い局所特徴量の特徴点が、前記対応点ペアのクエリ画像Ip側の対応点と一致すれば、当該対応点ペアが本登録される。
【００５７】
図１６は、上記本登録処理の手順を示したフローチャートであり、ステップＳ４０１では、仮登録されている対応点ペアの一つが選択される。ステップＳ４０２では、対応点ペアの一方である検索対象画像Iw(k)側の対応点とクエリ画像Iqの比較領域Aq(k)内の各特徴点を対象に局所特徴量間の距離Lが算出される。ステップＳ４０３では、距離Lが近い上位２つ（L1，L2）の特徴点ペアが抽出される。
【００５８】
ステップＳ４０４では、距離L1が基準距離Lef2以下であり、かつ距離比(L1/L2)が基準比tref2以下であるか否かが判定される。これらの本登録条件がいずれも満足されればステップＳ４０５へ進む。ステップＳ４０５では、前記距離L1を与えるクエリ画像Iqの特徴点が前記対応点ペアのクエリ画像Iq側の対応点と一致しているか否かが判定される。一致していればステップＳ４０６へ進み、前記仮登録されている今回の対応点ペアが本登録される。
【００５９】
ステップＳ４０７では、仮登録されている全ての対応点ペアに関して上記の処理が完了したか否かが判定される。完了していなければステップＳ４０１へ戻り、残りの対応点ペアに関して上記の各処理が繰り返される。これにより、今回注目した一の検索対象画像Iw(k)とクエリ画像Iqとの対応点ペアの本登録が完了する。
【００６０】
図６のメインフローへ戻り、ステップＳ１１では、上記の処理が全ての検索対象画像Iw(k)に関して完了したか否かが判定される。完了していなければステップＳ８へ戻り、検索対象画像Iw(k)を切換ながら上記の各処理が繰り返される。ステップＳ１２では、検索対象画像Iw(k)が前記本登録された対応点ペアの個数でソートされ、対応点ペアが最多である唯一の検索対象画像、あるいは上位Nベストの複数の検索対象画像が検索結果として出力される。
【符号の説明】
【００６１】
１…局所特徴量抽出部，２…第１対応点ペア抽出部，３…比較領域限定部，４…第２対応点ペア抽出部，５…検索結果出力部，２１，４１…仮登録部，２２，４２…本登録部
【技術分野】
【０００１】
本発明は、画像検索システムに係り、特に、クエリ画像に類似した画像を多数の検索対象画像の中から検索する際に、類似の比較が容易な領域を予め抽出し、当該領域を対象に検索を行う画像検索システムに関する。
【背景技術】
【０００２】
建物など剛体の画像をロバストに検出する手法の一つとして、非特許文献１にSIFT(Scale Invariant Feature Transform)が開示されている。このSIFTでは、クエリ画像および検索対象画像の双方から予め局所特徴量が抽出され、各画像の局所特徴量間のユークリッド距離Lに基づいて最近傍探索が実行される。そして、距離の近い局所特徴量同士が対応点ペアとされ、最終的に対応点ペアの多い検索対象画像が検索結果とされる。このとき、最近傍の特徴点の対応点マッチング精度を高めるために、最も近い距離L1のみならず２番目に近い距離L2も求められ、両者の比(L1/L2：ratio of distances)が所定の閾値t以下であれば対応点とされるが、閾値tよりも大きければ対応点とされない。
【０００３】
非特許文献１では、予備実験においてt=0.85で急激な誤対応点増加が確認されたことからt=0.8としている。しかしながら、閾値tを小さな値に設定すれば、対応点の精度は高くなる傾向を示すものの、対応点ペアが少なくなるので検索精度を高くできるとは限らない。すなわち、非特許文献１では閾値tを適正値に設定することが難しかった。
【０００４】
このような技術課題に対して、特許文献１には、所定数の対応点ペアが得られるように、対応点ペアが少なければ閾値tを段階的に上げ、多ければ閾値tを段階的に下げるといったように、抽出される対応点ペアの個数に応じて閾値tを適応的に変更する技術が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−１４０６１３号公報
【非特許文献】
【０００６】
【非特許文献１】David G. Lowe，"Distinctive image features from scale-invariant keypoints" International Journal of Computer Vision, 60, 2 (2004), pp.91-110.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記の特許文献１では、所定の閾値tで得られる対応点ペアが少ないと、閾値tが適応的に上昇するので対応点ペアが増える。しかしながら、もともと同一物体が画像内に含まれていないために対応点ペアが少ないクエリ画像および検索対象画像のペアについても閾値tが上げられてしまうので、本来であれば対応点ペアとされない特徴点同士までもが対応点ペアとされてしまうという問題があった。
【０００８】
本発明の目的は、上記した従来技術の課題を解決し、精度の高い十分な個数の対応点ペアに基づいて、画像検索を高精度で行える画像検索システムを提供することにある。
【課題を解決するための手段】
【０００９】
上記の目的を達成するために、本発明は、クエリ画像に類似した画像を検索対象画像の集合から検索する画像検索システムにおいて、以下のような手段を講じた点に特徴がある。
【００１０】
(1)クエリ画像および各検索対象画像の各特徴点から局所特徴量を抽出する局所特徴量抽出手段と、クエリ画像および各検索対象画像の局所特徴量同士を比較し、類似度が所定の第１条件を満足する特徴点のペアを第１対応点ペアとして抽出する第１対応点ペア抽出手段と、クエリ画像および検索対象画像のペアごとに、前記対応点ペアに基づいて比較領域を限定する比較領域限定手段とを具備し、クエリ画像および検索対象画像のペアごとに、比較領域同士を比較することを特徴とする。
【００１１】
(2)クエリ画像および検索対象画像のペアごとに、各比較領域の局所特徴量同士を比較し、類似度が所定の第２条件を満足する特徴点のペアを第２対応点ペアとして抽出する第２対応点ペア抽出手段と、第２対応点ペアの個数に基づいて検索結果を出力する検索結果出力手段とを具備し、第２条件が第１条件よりも緩いことを特徴とする。
【発明の効果】
【００１２】
本発明によれば、以下のような効果が達成される。
(1)クエリ画像および各検索対象画像内に、比較的厳しい条件を満足する対応点ペアに基づいて比較領域を設定すると共に、対応点ペアが得られない非類似の検索対象画像を予め排除したので、クエリ画像および各検索対象画像の類似度を、各比較領域内に比較的緩やかな条件で設定した対応点ペアの個数に基づいて判別すれば、精度の高い十分な個数の対応点ペアに基づいて画像検索を行えるようになる。
(2)クエリ画像および各検索対象画像内に、比較的厳しい条件を満足する対応点ペアに基づいて比較領域を設定すると共に、対応点ペアが得られない非類似の検索対象画像を予め排除し、クエリ画像および各検索対象画像の類似度を、各比較領域内に比較的緩やかな条件で設定した対応点ペアの個数に基づいて判別するので、精度の高い十分な個数の対応点ペアに基づいて画像検索を行えるようになる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態に係る画像検索システムのブロック図である。
【図２】対応点の仮登録方法を模式的に示した図である。
【図３】対応点の本登録方法を模式的に示した図である。
【図４】比較領域の限定方法（その１）を模式的に示した図である。
【図５】比較領域の限定方法（その２）を模式的に示した図である。
【図６】本発明の一実施形態の動作を示したフローチャートである。
【図７】対応点ペアの仮登録手順を示したフローチャートである。
【図８】対応点ペアの本登録手順を示したフローチャートである。
【図９】クエリ画像および一の検索対象画像の一例を示した図である。
【図１０】仮登録された対応点ペアの一例を示した図である。
【図１１】仮登録された対応点ペアの一部のみが本登録される例を示した図である。
【図１２】本登録された対応点ペアの一例を示した図である。
【図１３】比較領域の限定方法を示した図である。
【図１４】比較領域の一例を示した図である。
【図１５】比較領域における対応点ペアの仮登録手順を示したフローチャートである。
【図１６】比較領域における対応点ペアの本登録手順を示したフローチャートである。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の最良の実施形態について詳細に説明する。図１は、本発明の一実施形態に係る画像検索システムの主要部の構成を示したブロック図であり、ここでは、本発明の説明に不要な構成は図示が省略されている。
【００１５】
局所特徴量抽出部１は、クエリ画像Iqおよび多数の検索対象画像Iw(k)の各特徴点を基準にして局所特徴量fq(i)，fw(k,j)を抽出する。符号kは検索対象画像の識別子である。局所領域の特定には、非特許文献１に開示されているDifference of Gaussian (DoG)によるスケールスペース内の極値に基づく特徴点抽出が用いられる。この特徴点抽出の結果、特徴点の位置およびその領域範囲(スケール)が算出される。特徴領域内の特徴記述子としては、輝度勾配の方向ヒストグラムが用いられる。
【００１６】
このような方向ヒストグラムは、特徴領域の各ピクセルの輝度勾配を算出し、それに重みを付けてヒストグラムを生成し、最も多いbin領域の方向を基準にして、その方向に特徴領域の回転を行い、再度輝度方向の方向ヒストグラムを作成し、さらに前記ヒストグラムをブロックに分割し、各ブロック内で方向ヒストグラムを算出し、これを正規化してベクトル化することにより得られる。本実施形態では、ブロック内の輝度方向を８方向、対象領域内を１６分割しているため、一つの特徴記述子は８＊１６＝１２８次元となる。
【００１７】
これら特徴記述子の特徴として、局所領域の特徴を生成するのでオクルージョンに耐性があり、特徴点に対してスケールを決定するので画像サイズに不変であり、また輝度勾配に基づき画像平面内で回転を行うので画像平面に対する回転に不変であることなどが挙げられる。さらに、エッジ成分を利用しているので輝度変化に耐性がある。このような特徴点検出が画像の全てのピクセルに対して行われるが、ある特徴点が極値を取った場合でも特徴点として不適な場合は特徴領域から除外される。
【００１８】
本実施形態では、クエリ画像Iqの各局所特徴量fq(i)が次式(1)で表される。pq(i)は同次座標で表した特徴点の位置、σq(i)は特徴点が発見されたスケール、dq(i)は特徴記述子であり、符号iはクエリ画像Iqの特徴点識別子である。
【００１９】
fq(i)＝｛pq(i)，σq(i)，dq(i)｝ ・・・(1)
【００２０】
同様に、各検索対象画像Iw(k)の局所特徴量fw(k,j)は次式(2)で表される。pw(k,j)は同次座標で表した特徴点の位置、σw(k,j)は特徴点が発見されたスケール、dw(k,j)は特徴記述子であり、符号jは検索対象画像Iw(k)の特徴点識別子である。
【００２１】
fw(k,j)＝｛pw(k,j)，σw(k,j)，dw(k,j)｝ ・・・(2)
【００２２】
第１対応点ペア抽出部２は、仮登録部２１および本登録部２２を含み、クエリ画像Iqの各特徴点の局所特徴量と全ての検索対象画像Iw(k)の各特徴点の局所特徴量とを比較し、局所特徴量の類似度が高い特徴点のペアを対応点ペアとして登録する。
【００２３】
前記仮登録部２１は、クエリ画像Iqの各特徴点について、全ての検索対象画像Iw(k)の各特徴点を対象に局所特徴量の最近傍探索を行い、検索対象画像ごとに、局所特徴量間の距離に基づいて類似度を算出する。
【００２４】
本実施形態では、各特徴点の局所特徴量fq(i)，fw(k,j)間の類似度が、次式(3)で与えられる各特徴記述子dq(i)，dw(k,j)間のユークリッド距離Lで代表される。
【００２５】
L＝|dq(i)−dw(k,j)| ・・・(3)
【００２６】
そして、前記ユークリッド距離Lが最も近い距離L1となる特徴点および２番目に近い距離L2となる特徴点を各検索対象画像Iw(k)から探索し、更に各距離L1，L2が所定の第１条件を満足する場合のみ、前記距離L1を与える特徴点のペアを対応点ペアとして仮登録する。
【００２７】
図２は、対応点ペアの仮登録方法を示した図である。図示した例では、クエリ画像Iqと一の検索対象画像Iw(k)とのペアに着目しており、クエリ画像Iqの局所特徴量fq(1)と検索対象画像Iw(k)の局所特徴量fw(k,1)との距離がL1、局所特徴量fw(k,2)との距離がL2である。そして、距離L1が所定の基準距離Lref1以下であり、かつ距離比L1/L2が所定の基準比Rref1（例えば、０．８）以下なので、距離L1を与える特徴点のペアが対応点ペアとして仮登録されている。
【００２８】
これに対して、クエリ画像Iqの局所特徴量fq(2)と局所特徴量fw(k,3)との距離がL1、局所特徴量fw(k,4)との距離がL2であるが、距離L1が所定の基準距離Lref1よりも大きいか、あるいは距離比L1/L2が基準比Rref1（例えば、０．８）よりも大きいので、距離L1を与える特徴点のペアであっても対応点ペアとして仮登録されていない。
【００２９】
図１へ戻り、前記本登録部２２は、仮登録された全ての対応点ペアの検索対象画像Iw(k)側の対応点について、クエリ画像Iqの各特徴点を対象に局所特徴量の最近傍探索を同様に行い、距離L1，L2が前記仮登録条件と同等の本登録条件を満足するクエリ画像Iqの特徴点が前記対応点ペアのクエリ画像Iq側の対応点と一致していれば、当該対応点ペアを本登録する。
【００３０】
図３は、対応点ペアの本登録方法を示した図である。図示した例では、クエリ画像Iqの局所特徴量fq(1)と検索対象画像Iw(k)の局所特徴量fw(k,1)、およびクエリ画像Iqの局所特徴量fq(2)と検索対象画像Iw(k)の局所特徴量fw(k,2)とが共に対応点ペアとして仮登録されている。そして、各対応点ペアの検索対象画像Iw(k)側の対応点の局所特徴量fw(k,1)，fw(k,2)とクエリ画像Iqの全ての特徴点の局所特徴量fq(i)との最近傍探索が行われた結果、局所特徴量fw(k,1)と対応点ペアの条件を満足するクエリ画像Iqの特徴点が当該対応点ペアのクエリ画像Iq側の対応点と一致しているので、当該対応点のペアは本登録されている。
【００３１】
これに対して、局所特徴量fw(k,2)と対応点ペアの条件を満足するクエリ画像Iqの特徴点は当該対応点ペアのクエリ画像Iq側の対応点と一致していないので、当該対応点のペアは本登録されていない。
【００３２】
図１へ戻り、比較領域限定部３は、クエリ画像Iqと検索対象画像Iw(k)との組合せごとに、本登録された対応点ペアの対応点およびその局所特徴量に基づいて、画像の類似度を算出する際に比較対象となる領域を限定する。
【００３３】
図４、５は、クエリ画像Iqと一の検索対象画像Iw(k)との組合せについて、本登録された複数の対応点ペアに基づいて比較領域Aが限定される様子を模式的に示した図であり、図４に示したように、全ての対応点ペアの範囲を含む矩形あるいは楕円形の閉領域が、それぞれ比較領域Aq(k)，Aw(k)とされる。あるいは図５に示したように、対応点ペアの分布密度が高い矩形あるいは楕円形の閉領域が、それぞれ比較領域Aq(k)，Aw(k)とされても良い。なお、各検索対象画像Iw(k)において限定される比較領域Aw(k)は一つであるが、クエリ画像Iqでは検索対象画像Iw(k)ごとに比較領域Aq(k)が限定されることになる。
【００３４】
図１へ戻り、第２対応点ペア抽出部４は、仮登録部４１および本登録部４２を含み、比較領域Aが限定されたクエリ画像Iqおよび検索対象画像Iw(k)の組合せごとに、クエリ画像Iqの比較領域Aq内の各特徴点の局所領域と各検索対象画像Iw(k)の比較領域Aw(k)内の各特徴点の局所特徴量とを比較し、前記第１対応点ペア抽出部２と同様の手順で対応点ペアを抽出する。
【００３５】
前記仮登録部４１は、クエリ画像Iqの比較領域Aq(k)内の各特徴点について、各検索対象画像Iw(k)の比較領域Aw(k)内の各特徴点を対象に局所特徴量の最近傍探索を同様に行い、検索対象画像Iw(k)ごとに、前記距離L1，L2が仮登録条件を満足する最近傍の特徴点を探索し、前記距離L1を与える特徴点のペアを対応点ペアとして仮登録する。なお、当該仮登録部４１における仮登録条件は前記仮登録部２１における仮登録条件よりも緩和されている。
【００３６】
前記本登録部４２は、仮登録された全ての対応点ペアの検索対象画像Iw(k)側の対応点について、クエリ画像Iqの比較領域Aq(k)内の各対応点を対象に局所特徴量の最近傍探索を同様に行い、本登録条件を満足する最近傍の特徴点が前記対応点ペアのクエリ画像Iq側の対応点と一致していれば、当該対応点ペアを本登録する。なお、当該本登録部４２における本登録条件も前記本登録部２２における本登録条件より緩和されている。
【００３７】
検索結果出力部５は、前記クエリ画像Iqの比較領域Aq(k)および検索対象画像Iw(k)の比較領域Aw(k)を対象とする対応点ペアの探索結果を参照し、対応点ペアが最多である唯一の検索対象画像、あるいは上位Nベストの複数の検索対象画像を検索結果として出力する。
【００３８】
次いで、フローチャートを参照して本発明の一実施形態の動作を詳細に説明する。図６は、本発明の一実施形態の動作を示したメインフローである。
【００３９】
ステップＳ１では、局所特徴量抽出部１において、クエリ画像Iqから各特徴点を基準にした局所領域の特徴量fq(i)が抽出され、さらに全ての検索対象画像Iw(k)から各特徴点を基準にした局所領域の特徴量fw(k,j)が抽出される。ステップＳ２では、検索対象画像Iw(k)の一つが今回の注目画像として選択される。ステップＳ３では、前記第１対応点ペア抽出部２の仮登録部２１において、クエリ画像Iqの各特徴点と局所特徴量が一致または類似する検索対象画像Iw(k)の特徴点とを対応点ペアとして仮登録する仮登録処理が実行される。
【００４０】
図７は、前記仮登録処理の手順を示したフローチャートであり、ステップＳ１０１では、クエリ画像Iqから抽出された局所特徴量fq(i)の一つが選択される。ステップＳ１０２では、今回の検索対象画像Iw(k)の各局所特徴量fwt(j)とクエリ画像Iqの今回の注目特徴量fq(i)との類似度が、各特徴量間の距離（ユークリッド距離）Lとして算出される。ステップＳ１０３では、局所特徴量の距離Lが近い上位２つ（L1，L2）の特徴点ペアが抽出される。
【００４１】
ステップＳ１０４では、距離L1が基準距離Lef1以下であり、かつ距離比(L1/L2)が基準比tref1以下であるか否かが判定される。これらの仮登録条件がいずれも満足されれば、両者の類似度が高いと判定されるのでステップＳ１０５へ進み、距離L1を与える特徴点ペアが対応点ペアとして仮登録される。
【００４２】
ステップＳ１０６では、クエリ画像Iqの全ての局所特徴量fq(i)に関して上記の処理が完了したか否かが判定される。完了していなければステップ１０１へ戻り、クエリ画像Iqの局所特徴量fq(i)を切換ながら上記の各処理が繰り返される。これにより、今回注目した一の検索対象画像Iw(k)とクエリ画像Iqとの対応点ペアの仮登録が完了する。ここでは、図９に示したクエリ画像Iqおよび一の検索対象画像Iw(k)のペアについて、図１０に示したように、１１個の対応点ペアが仮登録されたものとして説明を続ける。
【００４３】
図６のメインフローへ戻り、ステップＳ４では、前記第１対応点ペア抽出部２の本登録部２２において、前記ステップＳ３とは逆の視線で、各対応点ペアの検索対象画像Iw(k)側の対応点とクエリ画像Iqの特徴点との間で最近傍探索が行われる。そして、最も類似度の高いクエリ画像Iqの特徴点が、前記対応点ペアのクエリ画像Ip側の対応点と一致すれば、当該対応点ペアが本登録される。
【００４４】
図８は、上記本登録処理の手順を示したフローチャートであり、ステップＳ２０１では、仮登録されている対応点ペアの一つが選択される。ステップＳ２０２では、対応点ペアの一方である検索対象画像Iw(k)側の対応点とクエリ画像Iqの各特徴点とを対象に局所特徴量間の距離Lが算出される。ステップＳ２０３では、距離Lが近い上位２つ（L1，L2）の特徴点ペアが抽出される。
【００４５】
ステップＳ２０４では、距離L1が基準距離Lef1以下であり、かつ距離比(L1/L2)が基準比tref1以下であるか否かが判定される。これらの本登録条件がいずれも満足されればステップＳ２０５へ進む。ステップＳ２０５では、前記距離L1を与えるクエリ画像Iqの特徴点が前記対応点ペアのクエリ画像Iq側の対応点と一致しているか否かが判定される。一致していればステップＳ２０６へ進み、前記仮登録されている今回の対応点ペアが本登録される。
【００４６】
ステップＳ２０７では、仮登録されている全ての対応点ペアに関して上記の処理が完了したか否かが判定される。完了していなければステップＳ２０１へ戻り、残りの対応点ペアに関して上記の各処理が繰り返される。これにより、今回注目した一の検索対象画像Iw(k)とクエリ画像Iqとの対応点ペアの本登録が完了する。
【００４７】
ここでは、図１１に示したように、クエリ画像Iqおよび一の検索対象画像Iw(k)のペアについて、前記仮登録された１１個の対応点ペアのうち、破線で示した４個の対応点は本登録されず、図１２に整理して示したように、７個の対応点ペアのみが本登録されたものとして説明を続ける。
【００４８】
図６のメインフローへ戻り、ステップＳ５では、今回注目した一の検索対象画像Iw(k)について、本登録された対応点ペアの有無が判定され、本登録された対応点ペアがあればステップＳ６へ進む。ステップＳ６では、クエリ画像Iqと今回注目の一の検索対象画像Iw(k)とのペアについて、本登録された対応点ペアに基づいて、両者の類似度を算出する際の比較対象となる領域を限定する「比較領域の限定処理」が、前記比較領域限定部３において実行され、クエリ画像Iqおよび検索対象画像Iw(k)のそれぞれに比較領域Aq(k)，Aw(k)が設定される。
【００４９】
図１３，１４は、前記比較領域の限定方法の一例を示した図であり、図１３に示したように７つの対応点ペアが本登録されていれば、図１４に示したように、これら７個の対応点ペアを包含する最小の矩形領域が比較領域Aq(k)，Aw(k)として設定される。
【００５０】
ステップＳ７では、全ての検索対象画像Iw(k)に関して上記の処理が完了したか否かが判定される。完了していなければステップＳ２へ戻り、注目する一の検索対象画像Iw(k)を切り換えながら上記の各処理が繰り返され、対応点ペアが本登録されているクエリ画像Iqおよび検索対象画像Iw(k)の全ペアについて比較領域Aq(k)，Aw(k)が設定される。
【００５１】
このようにして比較領域Aq(k)，Aw(k)の設定が完了するとステップＳ８以降へ進み、クエリ画像Iqと各検索対象画像Iw(k)とを前記比較領域Aq(k)，Aw(k)で比較して検索結果を得る検索手順が実行される。
【００５２】
ステップＳ８では、前記比較領域Aw(k)の設定された検索対象画像Iw(k)の一つが、今回の注目画像として選択される。ステップＳ９では、前記第２対応点ペア抽出部４の仮登録部４１において、クエリ画像Iqの比較領域Aq(k)内の各特徴点と局所特徴量が一致または類似する検索対象画像Iw(k)の比較領域Aw(k)内の特徴点とを対応点ペアとして仮登録する仮登録処理が実行される。
【００５３】
図１５は、前記仮登録処理の手順を示したフローチャートであり、ステップＳ３０１では、クエリ画像Iqの比較領域Aq(k)から局所特徴量fq(i)の一つが選択される。ステップＳ３０２では、今回の検索対象画像Iw(k)の比較領域Aw(k)内の各局所特徴量fwt(j)とクエリ画像Iqの今回の局所特徴量fq(i)との類似度が距離Lとして算出される。ステップＳ３０３では、距離Lが短い上位２つ（L1，L2）の特徴点ペアが抽出される。
【００５４】
ステップＳ３０４では、距離L1が基準距離Lef2以下であり、かつ距離比(L1/L2)が基準比tref2以下であるか否かが判定される。前記基準距離Lef2および基準比tref2は、前記第１対応点ペア抽出部２における基準距離Lef1および基準比tref2よりも緩和されている。すなわち、Lef1＜Lef2、tref1＜tref2である。これらの仮登録条件がいずれも満足されれば、両者の類似度が高いと判定されるのでステップＳ３０５へ進み、距離L1を与える特徴点のペアが対応点ペアとして仮登録される。
【００５５】
ステップＳ３０６では、クエリ画像Iqの比較領域Aq(k)内の各局所特徴量fq(i)に関して上記の処理が完了したか否かが判定される。完了していなければステップ３０１へ戻り、クエリ画像Iqの局所特徴量fq(i)を切換ながら上記の各処理が繰り返される。
【００５６】
図６のメインフローへ戻り、ステップＳ１０では、前記第２対応点ペア抽出部４の本登録部４２において、前記ステップＳ９とは逆の視線で、各対応点ペアの検索対象画像Iw(k)側の対応点とクエリ画像Iqの比較領域Aq(k)内の各特徴点との間で局所特徴量の類似度が算出される。そして、最も類似度の高い局所特徴量の特徴点が、前記対応点ペアのクエリ画像Ip側の対応点と一致すれば、当該対応点ペアが本登録される。
【００５７】
図１６は、上記本登録処理の手順を示したフローチャートであり、ステップＳ４０１では、仮登録されている対応点ペアの一つが選択される。ステップＳ４０２では、対応点ペアの一方である検索対象画像Iw(k)側の対応点とクエリ画像Iqの比較領域Aq(k)内の各特徴点を対象に局所特徴量間の距離Lが算出される。ステップＳ４０３では、距離Lが近い上位２つ（L1，L2）の特徴点ペアが抽出される。
【００５８】
ステップＳ４０４では、距離L1が基準距離Lef2以下であり、かつ距離比(L1/L2)が基準比tref2以下であるか否かが判定される。これらの本登録条件がいずれも満足されればステップＳ４０５へ進む。ステップＳ４０５では、前記距離L1を与えるクエリ画像Iqの特徴点が前記対応点ペアのクエリ画像Iq側の対応点と一致しているか否かが判定される。一致していればステップＳ４０６へ進み、前記仮登録されている今回の対応点ペアが本登録される。
【００５９】
ステップＳ４０７では、仮登録されている全ての対応点ペアに関して上記の処理が完了したか否かが判定される。完了していなければステップＳ４０１へ戻り、残りの対応点ペアに関して上記の各処理が繰り返される。これにより、今回注目した一の検索対象画像Iw(k)とクエリ画像Iqとの対応点ペアの本登録が完了する。
【００６０】
図６のメインフローへ戻り、ステップＳ１１では、上記の処理が全ての検索対象画像Iw(k)に関して完了したか否かが判定される。完了していなければステップＳ８へ戻り、検索対象画像Iw(k)を切換ながら上記の各処理が繰り返される。ステップＳ１２では、検索対象画像Iw(k)が前記本登録された対応点ペアの個数でソートされ、対応点ペアが最多である唯一の検索対象画像、あるいは上位Nベストの複数の検索対象画像が検索結果として出力される。
【符号の説明】
【００６１】
１…局所特徴量抽出部，２…第１対応点ペア抽出部，３…比較領域限定部，４…第２対応点ペア抽出部，５…検索結果出力部，２１，４１…仮登録部，２２，４２…本登録部
【特許請求の範囲】
【請求項１】
クエリ画像に類似した画像を検索対象画像の集合から検索する画像検索システムにおいて、
クエリ画像および各検索対象画像の各特徴点から局所特徴量を抽出する局所特徴量抽出手段と、
クエリ画像および各検索対象画像の局所特徴量同士を比較し、類似度が所定の第１条件を満足する特徴点のペアを第１対応点ペアとして抽出する第１対応点ペア抽出手段と、
クエリ画像および検索対象画像のペアごとに、前記対応点ペアに基づいて比較領域を限定する比較領域限定手段とを具備し、
クエリ画像および検索対象画像のペアごとに、前記比較領域同士を比較することを特徴とする画像検索システム。
【請求項２】
前記クエリ画像および検索対象画像のペアごとに、各比較領域の局所特徴量同士を比較し、類似度が所定の第２条件を満足する特徴点のペアを第２対応点ペアとして抽出する第２対応点ペア抽出手段と、
前記第２対応点ペアの個数に基づいて検索結果を出力する検索結果出力手段とを具備し、
前記第２条件が第１条件よりも緩いことを特徴とする請求項１に記載の画像検索システム。
【請求項３】
前記第１対応点ペア抽出手段は、
クエリ画像の各特徴点の局所特徴量と各検索対象画像の各特徴点の局所特徴量とを比較し、類似度が前記第１条件を満足する特徴点のペアを対応点ペアとして仮登録する仮登録手段と、
前記仮登録された各対応点ペアの検索対象画像側の対応点の局所特徴量とクエリ画像の各特徴点の局所特徴量とを比較し、類似度の高い特徴点が前記対応点ペアのクエリ画像側の対応点と一致していると、当該対応点ペアを本登録する本登録手段とを具備したことを特徴とする請求項１に記載の画像検索システム。
【請求項４】
前記第２対応点ペア抽出手段は、
クエリ画像の前記比較領域内の各特徴点の局所特徴量と各検索対象画像の前記比較領域内の各特徴点の局所特徴量とを比較し、類似度が前記第２条件を満足する特徴点のペアを対応点ペアとして仮登録する仮登録手段と、
前記仮登録された各対応点ペアの検索対象画像側の対応点の局所特徴量とクエリ画像の前記比較領域内の各特徴点の局所特徴量とを比較し、類似度の高い特徴点が前記対応点ペアのクエリ画像側の対応点と一致していると、当該対応点ペアを本登録する本登録手段とを具備したことを特徴とする請求項２に記載の画像検索システム。
【請求項５】
前記比較領域限定手段は、全ての対応点を含む閉領域を比較領域とすることを特徴とする請求項１ないし４のいずれかに記載の画像検索システム。
【請求項６】
前記比較領域限定手段は、対応点の分布密度が高い閉領域を比較領域とすることを特徴とする請求項１ないし４のいずれかに記載の画像検索システム。
【請求項１】
クエリ画像に類似した画像を検索対象画像の集合から検索する画像検索システムにおいて、
クエリ画像および各検索対象画像の各特徴点から局所特徴量を抽出する局所特徴量抽出手段と、
クエリ画像および各検索対象画像の局所特徴量同士を比較し、類似度が所定の第１条件を満足する特徴点のペアを第１対応点ペアとして抽出する第１対応点ペア抽出手段と、
クエリ画像および検索対象画像のペアごとに、前記対応点ペアに基づいて比較領域を限定する比較領域限定手段とを具備し、
クエリ画像および検索対象画像のペアごとに、前記比較領域同士を比較することを特徴とする画像検索システム。
【請求項２】
前記クエリ画像および検索対象画像のペアごとに、各比較領域の局所特徴量同士を比較し、類似度が所定の第２条件を満足する特徴点のペアを第２対応点ペアとして抽出する第２対応点ペア抽出手段と、
前記第２対応点ペアの個数に基づいて検索結果を出力する検索結果出力手段とを具備し、
前記第２条件が第１条件よりも緩いことを特徴とする請求項１に記載の画像検索システム。
【請求項３】
前記第１対応点ペア抽出手段は、
クエリ画像の各特徴点の局所特徴量と各検索対象画像の各特徴点の局所特徴量とを比較し、類似度が前記第１条件を満足する特徴点のペアを対応点ペアとして仮登録する仮登録手段と、
前記仮登録された各対応点ペアの検索対象画像側の対応点の局所特徴量とクエリ画像の各特徴点の局所特徴量とを比較し、類似度の高い特徴点が前記対応点ペアのクエリ画像側の対応点と一致していると、当該対応点ペアを本登録する本登録手段とを具備したことを特徴とする請求項１に記載の画像検索システム。
【請求項４】
前記第２対応点ペア抽出手段は、
クエリ画像の前記比較領域内の各特徴点の局所特徴量と各検索対象画像の前記比較領域内の各特徴点の局所特徴量とを比較し、類似度が前記第２条件を満足する特徴点のペアを対応点ペアとして仮登録する仮登録手段と、
前記仮登録された各対応点ペアの検索対象画像側の対応点の局所特徴量とクエリ画像の前記比較領域内の各特徴点の局所特徴量とを比較し、類似度の高い特徴点が前記対応点ペアのクエリ画像側の対応点と一致していると、当該対応点ペアを本登録する本登録手段とを具備したことを特徴とする請求項２に記載の画像検索システム。
【請求項５】
前記比較領域限定手段は、全ての対応点を含む閉領域を比較領域とすることを特徴とする請求項１ないし４のいずれかに記載の画像検索システム。
【請求項６】
前記比較領域限定手段は、対応点の分布密度が高い閉領域を比較領域とすることを特徴とする請求項１ないし４のいずれかに記載の画像検索システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１５】
【図１６】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１５】
【図１６】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１０−２０４９０８（Ｐ２０１０−２０４９０８Ａ）
【公開日】平成２２年９月１６日（２０１０．９．１６）
【国際特許分類】
【出願番号】特願２００９−４９１５８（Ｐ２００９−４９１５８）
【出願日】平成２１年３月３日（２００９．３．３）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２２年９月１６日（２０１０．９．１６）
【国際特許分類】
【出願日】平成２１年３月３日（２００９．３．３）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]